Добавлен: 29.10.2018
Просмотров: 48197
Скачиваний: 190
516
Глава 6. Взаимоблокировка
Рис. 6.12. Ресурсная взаимоблокировка в сети
Когда пакет поступает в маршрутизатор от одного из хостов, он помещается в буфер
для последующей передачи другому маршрутизатору, затем следующему, до тех пор
пока не будет передан по назначению. Эти буферы являются ресурсами, и их количе-
ство выражается конечным числом. На рис. 6.12 у каждого маршрутизатора есть только
восемь буферов (на практике у них имеются миллионы буферов, но это не меняет сути
потенциальной взаимоблокировки, а только влияет на частоту ее возникновения). Пред-
положим, что все пакеты с маршрутизатора A нужно передать маршрутизатору B, все
пакеты с маршрутизатора B должны быть отправлены на маршрутизатор C, все пакеты
с C должны уйти к D, а все пакеты с D должны уйти к A. Но ни один пакет не может быть
перемещен, поскольку на другом конце нет свободного буфера и мы имеем дело с клас-
сической ресурсной взаимоблокировкой, хотя и в центре коммуникационной системы.
6.7.3. Активная взаимоблокировка
В некоторых ситуациях процесс старается проявить вежливость, отказавшись от уже
приобретенной блокировки, как только замечает, что не может получить следющую
блокировку, в которой нуждается. Затем он ждет, скажем, несколько миллисекунд
и повторяет попытку. В принципе, в таком поведении нет ничего плохого, и оно по-
могает обнаружить взаимоблокировку и избавиться от нее. Но если другой процесс
делает то же самое в точности в то же самое время, эти процессы попадут в ситуацию,
похожую на ту, когда два человека пытаются разминуться на улице и каждый из них
вежливо уходит в сторону, но из этого ничего не выходит, поскольку они пытаются
одновременно уйти в одну и ту же сторону. Рассмотрим атомарный примитив try_lock,
с помощью которого вызывающий процесс проверяет мьютекс и либо захватывает его,
либо возвращает ошибку. Иными словами, он никогда не блокируется. Программисты
могут использовать этот примитив совместно с примитивом acquire lock, который также
пытается захватить блокировку, но блокируется, если блокировка недоступна. Теперь
представим себе два запущенных в параллель процесса (возможно, на разных ядрах),
использующих два ресурса (листинг 6.3). Каждому из них нужны два ресурса, и они ис-
пользуют примитив try_lock, чтобы попытаться заполучить необходимые блокировки.
Если попытка терпит неудачу, процесс освобождает уже удерживаемую блокировку
и повторяет попытку. В листинге 6.3 первый процесс запускается и получает ресурс 1,
в то же время запускается второй процесс и получает ресурс 2. Затем они пытаются по-
лучить вторую блокировку и терпят неудачу. Проявляя вежливость, они освобождают
текущую удерживаемую блокировку и повторяют попытку. Эта процедура повторяется
до тех пор, пока пользователю (или другой заинтересованной строне) не надоест и он
6.7. Другие вопросы
517
не избавит один из процессов от его страданий. Понятно, что ни один из процессов не
заблокирован, и можно даже сказать, что какие-то действия совершаются, следователь-
но, это не взаимоблокировка. Но ситуация не получает развития, поэтому мы получаем
некий эквивалент — активную взаимоблокировку (livelock).
Листинг 6.3. Вежливые процессы, которые могут вызвать активную
взаимоблокировку
void process A(void) {
acquire lock(&resource 1);
while (try lock(&resource 2) == FAIL) {
release lock(&resource 1);
wait fixed time();
acquire lock(&resource 1);
}
use both resources( );
release lock(&resource 2);
release lock(&resource 1);
}
void process A(void) {
acquire lock(&resource 2);
while (try lock(&resource 1) == FAIL) {
release lock(&resource 2);
wait fixed time();
acquire lock(&resource 2);
}
use both resources( );
release lock(&resource 1);
release lock(&resource 2);
}
Активная взаимоблокировка может возникать совершенно неожиданно. В некоторых
системах общее количество разрешенных процессов определено числом записей в та-
блице процессов. Таким образом, элементы таблицы процессов являются конечными
ресурсами. Если системный вызов ветвления — fork — не выполняется из-за того, что
таблица полна, разумным подходом со стороны программы, осуществляющей fork,
будет подождать некоторое время и повторить попытку.
Теперь предположим, что у UNIX-системы имеется 100 элементов в таблице процессов.
Запущено 10 программ, каждой из которых необходимо создать 12 дочерних процессов.
После того как каждый процесс создал 9 процессов, 10 исходных и 90 новых процессов
полностью используют таблицу. Каждый из 10 исходных процессов теперь находится
в бесконечном цикле попытки ветвления и отказа, то есть попадает во взаимоблокиров-
ку. Вероятность того, что это произойдет, невелика, но это может случиться. Должны
ли мы ликвидировать процессы и вызов fork, чтобы устранить проблему?
Максимальное количество открытых файлов также ограничено размером таблицы
i-узлов, поэтому при ее заполнении возникает аналогичная проблема. Еще одним
ограниченным ресурсом является пространство для свопинга на диске. Фактически
почти каждая таблица в операционной системе представляет собой конечный ресурс.
Должны ли мы упразднять все это, поскольку может случиться так, что в коллекции из
n процессов каждый может потребовать 1/n всего количества ресурсов, а затем каждый
попытается потребовать еще один ресурс? Наверное, это не самая лучшая идея.
518
Глава 6. Взаимоблокировка
Большинство операционных систем, включая UNIX и Windows, просто игнорируют
проблему, предполагая, что большинство пользователей предпочтут редкую активную
взаимоблокировку (или даже обычную взаимоблокировку) правилу, ограничиваю-
щему всех пользователей одним процессом, одним открытым файлом и по одному
экземпляру всего остального. Если бы эти проблемы могли быть устранены без затрат,
то и говорить было бы не о чем. Проблема в том, что цена слишком высока, главным
образом из-за накладывания совершенно неудобных ограничений на процессы. Таким
образом, мы столкнулись с неприятным компромиссом между удобством и корректно-
стью и множеством дискуссий о том, что из них важнее и для кого.
6.7.4. Зависание
Проблемой, тесно связанной как с обычной, так и с активной взаимоблокировкой, явля-
ется зависание. В динамической системе запрос ресурсов происходит постоянно. Для
того чтобы принять решение, кто и когда какой ресурс получит, нужна определенная
политика. Эта политика, хотя бы и разумная, может привести к тому, что некоторые
процессы никогда не будут обслужены, даже если они не находятся в состоянии вза-
имоблокировки.
В качестве примера рассмотрим распределение принтера. Представим себе, что система
использует некий алгоритм, гарантирующий, что распределение принтера не приводит
к взаимоблокировкам. Теперь предположим, что несколько процессов разом захотели
получить принтер в свое распоряжение. И кто его получит?
Один из возможных алгоритмов предусматривает передачу принтера тому процессу,
у которого самый маленький файл для вывода на печать (предположим, что подобная
информация доступна). Такой подход до максимума увеличивает число счастливых
клиентов и представляется вполне справедливым. А теперь посмотрим, что получится
на работающей системе, где у одного процесса есть для вывода на печать огромный
файл. Как только принтер освободится в очередной раз, система осмотрится и выберет
процесс с самым коротким файлом. Если поток процессов с короткими файлами не ис-
сякает, процесс с огромным файлом не получит принтер никогда. Он просто намертво
зависнет (будет отложен навсегда, даже если не будет заблокирован).
Зависания можно избежать за счет использования политики распределения ресурсов
«первым пришел — первым и обслужен». При таком подходе процесс, ожидающий
дольше всех, обслуживается следующим. В конечном итоге любой заданный процесс
со временем станет самым старшим в очереди и получит необходимый ему ресурс.
Стоит заметить, что некоторые не различают зависание и взаимоблокировку, поскольку
в обоих случаях нет движения вперед. Другие же чувствуют фундаментальную разницу,
поскольку процесс можно легко запрограммировать на то, чтобы попытаться сделать
что-нибудь n раз, и если все попытки провалятся, попытаться сделать что-нибудь дру-
гое. А заблокированный процесс такого шанса не имеет.
6.8. Исследования в области взаимоблокировок
Если на заре разработки операционных систем и был какой-нибудь предмет, на иссле-
дование которого не жалели ни сил, ни средств, так это взаимоблокировки. Причиной
этому являлось то, что обнаружение взаимоблокировок — это небольшая красивая
6.9. Краткие выводы
519
задача из области теории графов, которую один аспирант с математическими наклонно-
стями может разжевать за 4 года. Были изобретены всевозможные алгоритмы, один эк-
зотичнее и непрактичнее другого. Большинство этих разработок тихо почило в бозе, но
до сих пор появляются статьи, посвященные различным аспектам взаимоблокировок.
Последние работы, посвященные взаимным блокировкам, включают исследования
иммунитета от взаимоблокировок (Jula et al., 2011). Основная идея этого подхода за-
ключается в том, что приложения обнаруживают взаимоблокировки, как только они
происходят, а затем сохраняют их «сигнатуры», чтобы при последующих запусках из-
бежать подобных взаимоблокировок. В то же время есть работы (Marino et al., 2013),
посвященные использованию параллельного контроля, чтобы в первую очередь обе-
спечить невозможность возникновения взаимоблокировок.
Другим направлением исследований является попытка вхождения во взаимоблокировки
и их обнаружения. Последние работы по обнаружению взаимоблокировок были пред-
ставлены Pyla и Varadarajan (2012). Работа, выполненная Cai и Chan (2012), предостав-
ляет новую динамическую схему обнаружения взаимоблокировок, которая многократно
сокращает блокировочные зависимости, в которых нет входящих или исходящих границ.
Проблема взаимной блокировки проявляется повсеместно. В работе Wu (2013) опи-
сывается система управления взаимоблокировками для автоматизированных произ-
водственных систем. Такие системы моделируются с использованием сетей Петри
с целью поиска необходимых и достаточных условий для обеспечения управления
взаимными блокировками.
Существует также большой объем исследований, касающихся обнаружения распре-
деленных взаимоблокировок, особенно в высокопроизводительных вычислениях.
Например, существует значительный объем работ по планированию на основе обна-
ружения взаимоблокировок. Wang и Lu (2013) представили алгоритм планирования
рабочего процесса вычислений при ограниченных возможностях хранилищ данных.
В еще одной работе (Hilbrich et al., 2013) описывается обнаружение взаимоблокировки
в ходе выполнения программ для MPI. И наконец, существует огромное количество
теоретических работ по обнаружению распределенных взаимоблокировок. Но мы не
станем рассматривать здесь эти исследования, потому что, во-первых, они выходят за
рамки тематики данной книги, а во-вторых, ни одно из них даже отдаленно не прибли-
зилось к практическому применению в реальных системах. Их главное предназначение,
похоже, состоит в обеспечении работой специалистов по теории графов, чтобы они не
пошли на улицу с протянутой рукой.
6.9. Краткие выводы
Взаимные блокировки являются потенциальной проблемой любой операционной
системы. Они возникают в том случае, если все участники группы процессов заблоки-
рованы в ожидании события, которое может быть вызвано только действиями другого
участника группы. Эта ситуация приводит к тому, то все процессы пребывают в со-
стоянии вечного ожидания. Зачастую событие, которое ожидается процессом, — это
высвобождение какого-нибудь ресурса, удерживаемого другим участником группы.
Еще одна ситуация, допускающая возникновение взаимоблокировки, связана с тем,
что вся группа процессов обмена данными ожидает сообщения, канал связи пуст и не
выставлено никакого времени ожидания.
520
Глава 6. Взаимоблокировка
Ресурсных взаимоблокировок можно избежать, отслеживая безопасные и небезопасные
состояния. Безопасное состояние характеризуется наличием последовательности со-
бытий, гарантирующей успешное завершение работы всех процессов. Небезопасное со-
стояние таких гарантий не дает. Алгоритм банкира позволяет уклониться от взаимобло-
кировки, не удовлетворяя запроса, если тот вовлечет систему в небезопасное состояние.
Ресурсные взаимоблокировки могут быть структурно предупреждены за счет по-
строения такой системы, в которой они конструктивно невозможны. К примеру, если
позволить процессу удерживать в любой момент времени только один ресурс, можно
разрушить условия циклического ожидания, необходимые для возникновения взаи-
моблокировки. Ресурсная взаимоблокировка может быть также предотвращена за счет
нумерации всех ресурсов и принуждения процессов запрашивать эти ресурсы в строго
возрастающем порядке.
Но ресурсная взаимоблокировка не едина в своем роде. Для ряда систем потенциаль-
ную проблему составляют еще и коммуникационные взаимоблокировки, хотя с ними
зачастую можно справиться, установив подходящее время ожидания ответа.
Активные взаимоблокировки похожи на обычные тем, что могут остановить все про-
движение процессов вперед, но технически они отличаются, поскольку в них участву-
ют фактически не заблокированные процессы. Эффекта зависания можно избежать
за счет политики распределения ресурсов по принципу «первым пришел — первым
и обслужен».
Вопросы
1. Приведите пример взаимоблокировки, возникающей из-за неудачной политики.
2. Студенты, работающие на персональных компьютерах в лаборатории информа-
тики, отправляют свои файлы на распечатку через сервер, который создает оче-
редь на печать на своем жестком диске. При каких условиях может возникнуть
взаимоблокировка, если дисковое пространство для буфера печати ограничено
определенным объемом? Как можно избежать возникновения взаимоблокировки?
3. Какой из ресурсов в предыдущем вопросе можно отнести к выгружаемому, а ка-
кой — к невыгружаемому?
4. В листинге 6.1 ресурсы высвобождаются в порядке, обратном их запросу. А не
лучше ли было бы возвращать их в другом порядке?
5. Для возникновения взаимоблокировки нужны четыре условия (взаимное ис-
ключение, удержание и ожидание, невыгружаемость и циклическое ожидание).
Приведите пример, показывающий, что этих условий недостаточно для возник-
новения ресурсной взаимоблокировки. А когда этих условий достаточно для воз-
никновения ресурсной взаимоблокировки?
6. На городских улицах возникают условия круговой блокировки, называемой проб-
кой, при которой перекрестки блокируются машинами, которые затем блокируют
машины, находящиеся за ними, которые, в свою очередь, также блокируют ма-
шины, пытающиеся выехать на предыдущий перекресток, и т. д. Все перекрестки,
окружающие городской квартал, заполнены транспортными средствами, блоки-
рующими встречное движение по кругу. Пробка является ресурсной взаимобло-
кировкой, и проблема заключается в синхронизации соперничества. Алгоритм