Глава_3 (1085731), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Атака условия циклического ожидания

Остается только одно условие. Циклическое ожидание можно устранить несколь­кими способами. Один их них: просто следовать правилу, гласящему, что процессу дано право только на один ресурс в конкретный момент времени. Если нужен вто­рой ресурс, процесс обязан освободить первый. Но подобное ограничение неприем­лемо для процесса, копирующего огромный файл с магнитной ленты на принтер. Другой способ уклонения от циклического ожидания заключается в поддерж­ке общей нумерации всех ресурсов, как показано на рис. 3.11, а. Тогда действует следующее правило: процессы могут запрашивать ресурс, когда хотят этого, но все запросы должны быть сделаны в соответствии с нумерацией ресурсов. Процесс может запросить сначала принтер, затем накопитель на магнитной ленте, но не может сначала потребовать плоттер, а затем принтер.

1. Ф отонаборное устройство

2. С

   A

   B

   канер

3. Плоттер

4. Н акопитель на магнитной ленте

5

I

J

. Устройство для чтения компакт-дисков

а б

Рис_ч3.11. Пронумерованные ресурсы (а); граф ресурсов (б)

При выполнении такого правила граф распределения ресурсов никогда не бу­дет иметь циклов. Покажем, что это так, в случае двух процессов (рис. 3.11, б). Мы можем попасть в тупик, только если процесс А запросит ресурс j, а процесс В обратится к ресурсу i. Предположим, что ресурсы i и j различны, значит, они име­ют разные номера. Если i > j, тогда процессу А не позволяется запрашивать ресурс j, потому что его номер меньше, чем номер уже имеющегося у него ресурса. Если же i <j, тогда процесс В не может запрашивать ресурс i, потому что этот номер меньше номера уже занятого им ресурса. Так или иначе, взаимоблокировка невозможна.

При работе с несколькими процессами сохраняется та же самая логика. В каж­дый момент времени один из предоставленных ресурсов будет иметь наивысший номер. Процесс, использующий этот ресурс, уже никогда не запросит другие заня­тые ресурсы. Он или закончит свою работу или, в худшем случае, запросит ресурс с еще большим номером, а любой такой ресурс окажется доступен. В итоге процесс завершит работу и освободит свои ресурсы. На этот момент сложится ситуация, ког­да ресурс с высшим номером уже занят каким-то другим процессом, который так­же сможет закончить свою работу. То есть существует алгоритм, по которому все процессы завершатся без попадания в тупик.

Вариантом этого алгоритма является схема, в которой отбрасывается требова­ние приобретения ресурсов в строго возрастающем порядке, но сохраняется усло­вие, что процесс не может запросить ресурсы с меньшим номером, чем уже у него имеющиеся. Если процесс на начальной стадии запрашивает ресурсы 9 и 10, затем освобождает их, то это равнозначно тому, как если бы он начал работу заново, по­этому нет причины теперь запрещать ему запрос ресурса 1.

Несмотря на то что систематизация ресурсов с помощью их нумерации устра­няет проблему взаимоблокировки, бывают ситуации, когда невозможно найти по­рядок, удовлетворяющий всех. Когда ресурсы включают в себя области таблицы процессов, дисковое пространство для подкачки данных, закрытые записи базы данных и другие абстрактные ресурсы, число потенциальных ресурсов и вариан­тов их применений может быть настолько огромным, что никакая систематизация не сможет работать.

В табл. 3.1 подведены итоги различных методов для предотвращения тупиков.

Таблица 3.1. Методы предотвращения тупиков
Условие Метод

В заимное исключение Организовывать подкачку данных

Удержание и ожидание Запрашивать все ресурсы на начальной стадии

Нет принудительной выгрузки ресурса Отобрать ресурсы

Циклическое ожидание Пронумеровать ресурсы и упорядочить

С опутствующие вопросы

В этом разделе мы обсудим несколько разных вопросов, имеющих отношение к взаимоблокировкам. Сюда входят двухфазовое блокирование, тупик без ресурсов и «голодание».

Двухфазовое блокирование

Хотя и избежание, и предотвращение блокировок в общем случае не являются многообещающими, для отдельных прикладных задач известно немало прекрас­ных алгоритмов специального назначения. Например, во многих системах баз дан­ных очень часто выполняется операция, которая просит заблокировать несколько записей и затем обновить все заблокированные записи. Когда одновременно рабо­тает несколько процессов, появляется реальная опасность взаимоблокировки.

Часто используемый подход называется двухфазовым блокированием. В пер­
вой фазе, то есть на первом этапе, процесс пытается заблокировать все требуемые
записи по одной за раз. Если операция успешна, процесс переходит ко второму
этапу, выполняя обновление и освобождение блокировок. Никакой настоящей
работы на первом этапе не совершается.

Если во время первой фазы какая-либо необходимая запись оказывается уже заблокированной, процесс просто освобождает все свои блокировки и начинает первую фазу заново. В некотором смысле этот метод похож на схему, в которой запрос всех необходимых ресурсов происходит заранее, или, по крайней мере, пе­ред тем, как произойдет что-то необратимое. В некоторых версиях двухфазового блокирования, если блокировка встретилась во время первой фазы, не происхо­дит возврата ресурсов и возобновления процесса. В таких версиях может возник­нуть тупиковая ситуация.

Но эту стратегию нельзя обобщить. В системах реального времени и системах контроля процессов, например, недопустимо частично завершить процесс из-за того, что ресурс недоступен, а потом опять начинать все заново. Также недопусти­мо перезапускать процесс, если он прочел или написал сообщение в сети, обновил файлы и сделал что-нибудь еще, что не может быть безопасно повторено. Алго­ритм работает только в тех ситуациях, когда программист очень тщательно подго­товил все таким образом, что программу можно остановить в любой точке первой фазы и запустить заново. Многие программы не могут быть структурированы таким образом.

Тупики без ресурсов

До сих пор все наши рассуждения были сконцентрированы на взаимоблокиров­ках ресурсов. Один процесс хочет получить что-то, что есть у другого процесса, и должен ждать, пока тот не отдаст это что-то. Тем не менее взаимоблокировки также могут происходить и в других ситуациях, включая те, в которых ресурсы вообще не участвуют.

Например, может случиться, что два процесса заблокировали друг друга: каж­дый ждет, когда другой выполнит некое действие. Такое часто случается с сема­форами. В главе 2 мы видели примеры, в которых процесс должен был выполнить системный вызов down на двух семафорах, обычно на семафоре mutex и еще на од­ном. Если эту операцию выполнить в неправильном порядке, то в результате по­лучится взаимоблокировка.

Голодание

«Голодание» является проблемой, тесно связанной с взаимоблокировкой. В дина­мических системах постоянно происходят запросы к ресурсам. Необходима неко­торая политика принятия решений о том, когда, кто и какой ресурс получит. Эта политика хотя и кажется разумной, может привести к тому, что некоторые про­цессы никогда не получат требуемое, хотя они и не будут заблокированы.

Например, рассмотрим процесс предоставления принтера. Представим, что си­стема использует некоторый вид алгоритма, гарантирующий, что предоставление принтера процессу не приводит к взаимоблокировке. Теперь предположим, что несколько процессов одновременно хотят воспользоваться принтером. Какой из них должен получить этот ресурс?

Один возможный алгоритм предоставления ресурсов отдает принтер процессу с наименьшим файлом для печати (предполагается, что подобная информация доступна). Такой подход максимизирует количество счастливых обслуженных клиентов и кажется прекрасным. Теперь рассмотрим, что произойдет в сильно за­груженной системе, когда один из процессов должен распечатать огромный файл. Каждый раз, когда принтер освобождается, система выбирает процесс с наиболее коротким файлом. Если в системе есть постоянный поток процессов с небольши­ми файлами, принтер никогда не будет предоставлен процессу с огромным фай­лом. Процесс просто «умрет от голода» (будет отложен на неопределенный срок, несмотря на то, что даже не будет заблокирован).

«Голодания» можно избежать, если использовать стратегию распределения ре­сурсов по принципу «первым пришел — первым обслужен». При таком подходе процесс, ожидающий дольше всех, обслуживается следующим. В итоге любой про­цесс в некоторый момент станет самым старшим в очереди и, таким образом, по­лучит необходимый ресурс.

Исследования в области взаимоблокировок

Если когда-либо и существовал предмет, на исследования которого не жалели усилий на заре эпохи создания операционных систем, то им были тупиковые ситуации. Так происходило по следующей причине: обнаружение взаимобло­кировок является приятной небольшой проблемой из теории графов, в которую имеющие степень в математике студенты могли вонзить свои зубы и переже­вывать эту проблему в течение 3-х или 4-х лет. Были изобретены самые разно­образные алгоритмы, каждый последующий все экзотичнее и непрактичнее пре­дыдущего. В конечном итоге исследования в данной области прекратились. Только изредка появляется новая статья, посвященная данной теме (например, [171]). Когда операционные системы хотят обнаружить или предотвратить взаимоблоки­ровку, что некоторые из них и делают, они используют один из методов, обсуж­давшихся этой главе.

Однако существует еще одно небольшое изыскание по обнаружению распре­деленных взаимоблокировок. Мы не будем рассматривать его здесь, потому что (1) это выходит за рамки данной книги и (2) ничто из этого даже отдаленно не практикуется в реальных системах. Кажется, его главная функция — давать рабо­ту исследователям в области теории графов, в противном случае пополнивших бы очереди на бирже труда.

Резюме

Взаимоблокировка — это потенциальная проблема любой операционной системы. Она происходит, когда в группе процессов каждый получает монопольный доступ к некоторому ресурсу и каждому требуется еще один ресурс, принадлежащий дру­гому процессу в группе. Все процессы оказываются заблокированными, и ни один никогда не сможет заработать снова.

Взаимоблокировки можно избежать, отслеживая, которое состояние является безопасным, а которое нет. Безопасное состояние — это то, в котором существует последовательность действий, гарантирующая, что все процессы смогут окончить свою работу. В небезопасном состоянии таких обязательств дать нельзя. Алгоритм банкира избегает тупиков, не выполняя запрос, если тот приводит систему в небез­опасное состояние.

Взаимоблокировки можно предотвратить структурно, построив систему таким образом, что тупиковая ситуация никогда не возникнет по построению. Например, если позволить процессу использовать только один ресурс в любой момент време­ни, не выполнится необходимое для возникновения тупиков условие цикличес­кого ожидания. Взаимоблокировки также можно предотвратить, если перенуме­ровать все ресурсы и затем требовать от процессов создания запросов в строго возрастающем порядке. «Голодания» можно избежать, если использовать страте­гию распределения ресурсов «первым пришел — первым обслужен».

Вопросы

1. Приведите пример взаимоблокировки, взятый из области политики.

2. Студенты, работая на персональных компьютерах в лаборатории, посылают
   свои файлы для печати на сервер, записывающий файлы в область подкач­-
   ки данных на жесткий диск. При каких условиях может произойти взаимо­-
   блокировка, если дисковое пространство для подкачки данных печати огра­-
   ничено? Как можно избежать взаимоблокировки?

3. Какие ресурсы в предыдущем вопросе являются выгружаемыми, а ка-­
   кие — нет?

4. В листинге 3.1 ресурсы возвращаются в порядке, обратном их получению.
   Будет ли с тем же успехом работать эта схема, если возвращать их в другом
   порядке?

Характеристики

Список файлов книги