ным. Запросы ресурсов могут происходить в порядке, указанном на рис. 3.6, г.

Если эти шесть запросов будут осуществлены в такой последовательности, в результате мы получим шесть фафов, показанных на рис. 3.6, д~к. После запроса 4 процесс А блокируется в ожидании ресурса S (см. рис. 3.6, з). На двух следующих шагах также блокируются процессы В и С, в конечном счете приводя к циклу и взаимоблокировке на рис. 3.6, к.

Однако, как мы упоминали ранее, операционная система не обязана запускать процессы в каком-то особом порядке. В частности, если выполнение отдельного запроса приводит в тупик, операционная система вправе просто приостановить процесс без удовлетворения запроса (то есть не выполняя план процесса) до тех пор, пока это безопасно. На рис. 3.6 операционная система могла бы приостановить процесс В вместо того, чтобы отдавать ему ресурс S, если бы она знала о предстоящей взаимоблокировке. Работая только с процессами А и С, мы могли бы получить порядок запросов ресурсов и их возвратов, продемонстрированный на рис. 3.6, л, вместо показанного на рис. 3.6, г. Такая последовательность действий отражена графами на рис. 3.6, м-с, и она не приводит к тупику.

После шага с процесс В может получить ресурс S, потому что процесс А уже закончил свою работу, а процесс С имеет в своем распоряжении все необходимые ему ресурсы. Даже если затем процесс В, когда он запросит ресурс Т, будет заблокирован, система не повиснет. Процесс В всего лишь будет ждать завершения работы процесса С.

Позже в этой главе мы изучим подробный алгоритм для принятия решений о распределении ресурсов, которые не приведут к взаимоблокировке. В данный момент важно понять, что графы ресурсов являются инструментом, позволяющим нам увидеть, станет ли заданная последовательность запросов/возвратов ресурсов причиной тупиковой ситуации. Мы всего лишь шаг за шагом осуществляем запросы и возвраты ресурсов и после каждого шага проверяем граф на содержание циклов. Если они есть, мы зашли в тупик; если нет, значит, взаимоблокировки тоже нет. Хотя мы рассматривали фафы ресурсов для случая, когда в системе присутствует по одному ресурсу каждого типа, фафы также можно построить для обработки ситуации с несколькими одинаковыми ресурсами [44]. Вообще говоря, при столкновении с взаимоблокировками практикуются четыре стратегии.

1. Пренебрежение проблемой в целом. Если вы проигнорируете проблему, возможно, затем она проигнорирует вас.

2. Обнаружение и восстановление. Позволить взаимоблокировке произойти, обнаружить ее и предпринять какие-либо действия.

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

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

Мы по очереди изучим каждый из этих методов в следующих четырех разделах.

Запросить R Запросить S Освободить R Освободить S

Запросить S Запросить Т Освободить S Освободить Т

Запросить Т Запросить R Освободить Т Освободить R

1. А запрашивает R

2. В запрашивает S

3. С запрашивает Т

4. А запрашиваете

5. В запрашивает Т

6. С запрашивает R Взаимоблокировка

Ш1 Ш1

S [Т R S Т

1. А запрашивает R

2. С запрашивает Т

3. А запрашивает S

4. С запрашивает R

5. А освобождает R

6. А освобождает S Нет взаимобпокировки

® ® © ® © ®

© ©

© ©

R S Т

А)©©<1 ®©©*1

R S Т

R S Т

п р С

Рис. 3.6. Пример возникновения взаимоблокировки и способы избежать ее

3.3.3. Страусовый алгоритм

Самым простым подходом является страусовый алгоритм : воткните голову в песок и притворитесь, что проблемы вообще не существует. Различные люди отзываются об этой стратегии по-разному. Математики считают ее полностью неприемлемой и говорят, что взаимоблокировки нужно предотвращать любой ценой. Инженеры спрашивают, как часто встает подобная проблема, как часто система попадает в аварийные ситуации по другим причинам и насколько серьезны последствия взаимоблокировок. Если взаимоблокировки случаются в среднем один раз в пять лет, а сбои операционной системы, ошибки компилятора и поломки компьютера из-за неисправности аппаратуры происходят раз в неделю, то большинство инженеров не захотят добровольно уступать в производительности и удобстве для того, чтобы ликвидировать возможность взаимоблокировок.

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

Теперь предположим, что система UNIX имеет 100 ячеек процессов. Работают десять программ, каждой необходимо создать 12 (под)процессов. После образования каждым процессом девяти процессов 10 исходных и 90 новых процессов заполнят таблицу до конца. Теперь каждый из десяти исходных процессов попадает в бесконечный цикл, состоящий из попыток разветвления и отказов, то есть возникает взаимоблокировка. Вероятность того, что произойдет подобное, минимальна, но это могло бы случиться. Должны ли мы отказаться от процессов и вызова fork, чтобы устранить данную проблему?

Максимальное количество открытых файлов также ограниченно размером таблицы i-узлов, следовательно, когда таблица заполняется целиком, возникает та же самая проблема. Пространство для подкачки файлов на диск является еще одним офаниченным ресурсом. Фактически почти каждая таблица в операционной системе представляет собой ресурс, имеющий пределы. Должны ли мы упразднить их все из-за того, что теоретически ожидаема ситуация, когда в фуппе из п процессов каждый может потребовать 1/п от целого, а затем попытаться получить еще часть?

Большая часть операционных систем, включая UNIX и Windows, игнорируют эту проблему. Они исходят из предположения, что большинство пользователей скорее предпочтут иметь дело со случающимися время от времени взаимоблокировками, чем с правилом, по которому всем пользователям разрешается только один процесс, один открытый файл и т. д. Если бы можно было легко устранить взаимоблокировки, не возникло бы столько разговоров на эту тему. Сложность заключается в том, что цена достаточно высока, и в основном она, как мы вскоре увидим, исчисляется в наложении неудобных ограничений на процессы. Таким образом, мы столкнулись с неприятным выбором между удобством и корректностью и множеством дискуссий о том, что более важно и для кого. При всех этих условиях трудно найти верное решение.