Добавлен: 29.10.2018
Просмотров: 48193
Скачиваний: 190
506
Глава 6. Взаимоблокировка
6.5.2. Безопасное и небезопасное состояние
При дальнейшем рассмотрении алгоритмов уклонения от взаимоблокировок исполь-
зуется информация, представленная на рис. 6.4. В любой заданный момент времени
существует текущее состояние, содержащее E, A, C и R. Состояние считается безопас-
ным
, если существует какой-то порядок планирования, при котором каждый про-
цесс может доработать до конца, даже если все процессы внезапно и срочно запросят
максимальное количество ресурсов. Это положение проще всего проиллюстрировать
с помощью примера, в котором используется один ресурс. На рис. 6.7, а показано со-
стояние, в котором процесс A удерживает 3 экземпляра ресурса, но в конечном счете
может затребовать 9 экземпляров. Процесс B в этот момент удерживает 2 экземпляра,
но позже может затребовать в общей сложности еще 4. Процесс C также удерживает 2
экземпляра, но может затребовать еще 5. В системе есть всего 10 экземпляров данного
ресурса, 7 из которых уже распределены, а 3 пока свободны.
Рис. 6.7. Состояние а является безопасным
Состояние на рис. 6.7, а является безопасным, потому что существует такая последова-
тельность предоставления ресурсов, которая позволяет завершиться всем процессам.
А именно — планировщик может просто запустить в работу только процесс B на то
время, пока он запросит и получит 2 дополнительных экземпляра ресурса, что приведет
к состоянию, изображенному на рис. 6.7, б. Когда процесс B завершит свою работу, мы
получим состояние, показанное на рис. 6.7, в. Затем планировщик может запустить
процесс C, что со временем приведет нас к ситуации, показанной на рис. 6.7, г. По за-
вершении работы процесса C мы получим ситуацию, показанную на рис. 6.7, д. Теперь
процесс A наконец-то может получить необходимые ему 6 экземпляров ресурса и также
успешно завершить свою работу. Таким образом, состояние, показанное на рис. 6.7, а,
является безопасным, поскольку система может избежать взаимоблокировки с помо-
щью тщательного планирования процессов.
Теперь предположим, что исходное состояние системы показано на рис. 6.8, а, но в дан-
ный момент процесс A запрашивает и получает еще один ресурс и система переходит
в состояние, показанное на рис. 6.8, б. Сможем ли мы найти последовательность, которая
гарантирует безопасную работу системы? Давайте попробуем. Планировщик может дать
поработать процессу B до того момента, пока он не запросит все свои ресурсы (рис. 6.8, в).
В итоге процесс B успешно завершается, и мы получаем ситуацию, показанную на
рис. 6.8, г. В этом месте мы застряли: в системе осталось только 4 свободных экзем-
пляра ресурса, а каждому из активных процессов необходимо по 5 экземпляров. И не
существует последовательности действий, гарантирующей успешное завершение всех
6.5. Уклонение от взаимоблокировок
507
Рис. 6.8. Состояние б небезопасно
процессов. Следовательно, решение о предоставлении ресурса, которое перевело си-
стему из состояния, показанного на рис. 6.8, а, в состояние, показанное на рис. 6.8, б, из
безопасного в небезопасное состояние. Если из состояния, показанного на рис. 6.8, б,
запустить процесс A или C, то ни один из них не заработает. Возвращаясь назад, нужно
сказать, что запрос процесса A не должен был удовлетворяться.
Следует отметить, что небезопасное состояние само по себе не является состоянием
взаимоблокировки. Начиная с состояния, показанного на рис. 6.8, б, система может
поработать некоторое время. Фактически может даже успешно завершиться работа
одного из процессов. Кроме того, процесс A может высвободить один ресурс еще до
запроса дополнительного ресурса, позволяя успешно завершить работу процессу C,
а системе в целом избежать взаимоблокировки. Таким образом, разница между без-
опасным и небезопасным состоянием заключается в том, что в безопасном состоянии
система может гарантировать, что все процессы закончат свою работу, а в небезопасном
состоянии такой гарантии дать нельзя.
6.5.3. Алгоритм банкира для одного ресурса
Алгоритм планирования, позволяющий избегать взаимоблокировок, был разработан
Дейкстрой (Dijkstra, 1965) и известен как алгоритм банкира. Он представляет собой
расширение алгоритма обнаружения взаимоблокировок, представленного в разделе
«Обнаружение взаимоблокировки при использовании одного ресурса каждого типа».
Модель алгоритма основана на примере банкира маленького городка, имеющего дело
с группой клиентов, которым он выдал ряд кредитов. (Много лет назад банки не давали
кредиты, пока не убеждались в том, что они могут быть возвращены.) Алгоритм про-
веряет, ведет ли выполнение каждого запроса к небезопасному состоянию. Если да, то
запрос отклоняется. Если удовлетворение запроса к ресурсу приводит к безопасному
состоянию, ресурс предоставляется процессу. На рис. 6.9, а показаны четыре клиента:
A, B, C и D, каждый из которых получил определенное количество единиц кредита (на-
пример, 1 единица равна 1000 долларов). Банкир знает, что не всем клиентам тотчас же
понадобится максимальная сумма их кредита, поэтому для обслуживания их потребно-
стей он зарезервировал только 10 единиц, а не все 22, которые нужны клиентам. (Чтобы
провести аналогию с компьютерной системой, будем считать, что клиенты — это про-
цессы, единицы — накопители на магнитной ленте, а банкир — операционная система.)
Клиенты занимаются своими делами, время от времени запрашивая ссуды (то есть за-
прашивая ресурсы). В какой-то определенный момент возникает ситуация, показанная
на рис. 6.9, б. Это состояние не представляет опасности, поскольку при оставшихся
508
Глава 6. Взаимоблокировка
Рис. 6.9. Состояния распределения ресурсов: а — безопасное;
б — безопасное; в —небезопасное
двух единицах банкир может отложить выполнение любых запросов, за исключением
запроса клиента C, позволяя C завершить свои дела и высвободить все четыре своих
ресурса. Имея в своем распоряжении четыре единицы ресурса, банкир может позволить
получить необходимые единицы либо D, либо B и т. д.
Рассмотрим, что получится, если запрос от B одной дополнительной единицы будет
удовлетворен в ситуации, показанной на рис. 6.9, б. Мы получим небезопасную ситу-
ацию, показанную на рис. 6.9, в. Если все клиенты внезапно запросят максимальные
ссуды, банкир не сможет удовлетворить никого из них и мы получим взаимоблокиров-
ку. Небезопасное состояние необязательно приводит к взаимоблокировке, поскольку
клиенту может и не понадобиться максимальная сумма кредита, но банкир не может
рассчитывать на это.
Алгоритм банкира рассматривает каждый запрос по мере поступления и проверяет,
приведет ли его удовлетворение к безопасному состоянию. Если да, то запрос удовлет-
воряется, в противном случае запрос откладывается до лучших времен. Чтобы понять,
является ли состояние безопасным, банкир проверяет, может ли он предоставить до-
статочно ресурсов для удовлетворения запросов какого-нибудь клиента. Если да, то
эти ссуды считаются возвращенными, после чего проверяется следующий ближайший
к пределу займа клиент и т. д. Если в конечном счете все ссуды могут быть погашены,
состояние является безопасным и исходный запрос можно удовлетворить.
6.5.4. Алгоритм банкира для нескольких типов ресурсов
Алгоритм банкира может быть распространен на работу с несколькими ресурсами. На
рис. 6.10 показано, как он работает. Здесь изображены две матрицы. Левая матрица по-
казывает, сколько экземпляров каждого ресурса в данный момент выделено каждому из
пяти процессов. Правая показывает, сколько экземпляров ресурсов все еще необходимо
каждому процессу для завершения его работы. На рис. 6.5 эти матрицы назывались C
и R. Как и в случае с ресурсом одного типа, процессы перед выполнением своей работы
должны сообщить об общих потребностях в ресурсах, чтобы система в любой момент
могла вычислить правую матрицу.
Три вектора, изображенные справа от матриц, показывают соответственно существую-
щие ресурсы (вектор E), занятые ресурсы (вектор P) и доступные ресурсы (вектор A).
6.5. Уклонение от взаимоблокировок
509
Рис. 6.10. Алгоритм банкира для системы с несколькими типами ресурсов
Судя по значению вектора E, в системе имеется шесть накопителей на магнитной ленте,
три плоттера, четыре принтера и два привода Blu-ray-дисков. Из них заняты в данный
момент пять накопителей, три плоттера, два принтера и два привода Blu-ray-дисков.
Этот факт можно установить путем сложения значений четырех столбцов, соответ-
ствующих ресурсам, в левой матрице. Вектор доступных ресурсов — это разница между
количеством присутствующих в системе ресурсов и количеством ресурсов, использу-
емых в настоящее время.
Теперь может быть изложен алгоритм проверки состояния на безопасность.
1. Ищем в матрице R строку, соответствующую процессу, чьи неудовлетворенные
потребности в ресурсах меньше или равны вектору A. Если такой строки не
существует, то система в конце концов войдет в состояние взаимоблокировки,
поскольку ни один процесс не сможет доработать до успешного завершения (пред-
полагается, что процессы удерживают все ресурсы, пока не завершат свою работу).
2. Допускаем, что процесс, чья строка была выбрана, запрашивает все необходимые
ему ресурсы (возможность чего гарантируется) и завершает свою работу. Отмечаем
этот процесс как завершенный и прибавляем все его ресурсы к вектору A.
3. Повторяем шаги 1 и 2 до тех пор, пока либо все процессы будут помечены как
завершенные (в этом случае исходное состояние было безопасным), либо не оста-
нется процессов, чьи запросы могут быть удовлетворены (в этом случае система
не была в безопасном состоянии).
Если на шаге 1 подходят для выбора несколько процессов, то неважно, который из них
будет выбран: фонд доступных ресурсов либо увеличивается, либо в худшем случае
остается таким же.
Теперь вернемся к примеру, показанному на рис. 6.10. Текущее состояние безопасно.
Предположим, что процесс B теперь сделал запрос на принтер. Этот запрос может быть
удовлетворен, поскольку получающееся в результате состояние по-прежнему безопасно
(процесс D может завершить свою работу, затем это же могут сделать процесс A или
процесс E, а затем и все остальные).
510
Глава 6. Взаимоблокировка
Представим теперь, что после выделения процессу B одного из двух оставшихся
принтеров E затребует последний принтер. Удовлетворение этого запроса уменьшит
значение вектора доступных ресурсов до (1 0 0 0), что приведет к взаимоблокировке.
Совершенно ясно, что запрос процесса E должен быть на некоторое время отклонен.
Дейкстра впервые опубликовал алгоритм банкира в 1965 году. С тех пор практически
каждая книга по операционным системам дает его подробное описание. Различным
аспектам этого алгоритма было посвящено бесчисленное количество статей. К сожале-
нию, мало у кого из авторов хватило смелости показать, что хотя алгоритм замечателен
в теории, на практике он по существу бесполезен, поскольку нечасто можно определить
заранее, каковы будут максимальные потребности процессов в ресурсах. Кроме того, ко-
личество процессов не фиксированно, оно динамически изменяется по мере входа поль-
зователей в систему и выхода их из нее. И более того, ресурсы, считавшиеся доступными,
могут внезапно пропасть (накопитель на магнитной ленте может сломаться). Таким об-
разом, на практике лишь немногие системы, если таковые вообще имеются, используют
алгоритм банкира для уклонения от взаимоблокировок. Но в некоторых системах для
предотвращения взаимных блокировок используются эвристические правила, подобные
алгоритму банкира. Например, сети могут дросселировать трафик, когда использование
буфера превысит, скажем, 70 %, при оценке, что оставшихся 30 % будет достаточно для
завершения обслуживания текущих пользователей и возвращения их ресурсов.
6.6. Предотвращение взаимоблокировки
Как все-таки можно избежать взаимоблокировок в реальных системах? Ведь мы уже
убедились в том, что уклониться от них по сути невозможно, поскольку для этого
требуется информация о будущих запросах, о которых ничего не известно. Чтобы
ответить на этот вопрос, вернемся назад к четырем условиям, сформулированным
Коффманом и его коллегами (Koffman at al., 1971), и посмотрим, смогут ли они дать
нам ключ к решению проблемы. Если мы сможем гарантировать, что хотя бы одно из
этих условий никогда не будет выполнено, то взаимоблокировки станут структурно
невозможными (Havender, 1968).
6.6.1. Атака условия взаимного исключения
Сначала предпримем атаку на условие взаимного исключения. Если в системе нет
ресурсов, отданных в единоличное пользование одному процессу, мы никогда не по-
падем в ситуацию взаимоблокировки. Данные проще всего сделать доступными только
для чтения, чтобы процессы могли их использовать одновременно. Но также понятно,
что если позволить двум процессам одновременно печатать данные на принтере, то
это приведет к хаосу. За счет использования очереди на печать (спулинга) выдавать
свои выходные данные могут сразу несколько процессов. В этой модели единственным
процессом, который фактически запрашивает физический принтер, является демон
1
принтера. Так как демон не запрашивает никакие другие ресурсы, взаимоблокировки,
связанные с принтером, можно исключить.
1
Демон — служебная программа в некоторых операционных системах (преимущественно ос-
нованных на UNIX), работающая в фоновом режиме без непосредственного взаимодействия
с пользователем.