Глава_3 (Методическое пособие по Операционным системам), страница 2

Холт (Holt) показал, как можно смоделировать четыре условия возник­новения тупиков, используя направленные графы. Графы имеют два вида узлов: процессы, показанные кружочками, и ресурсы, нарисованные квадратиками. Ребро, направленное от узла ресурса (квадрат) к узлу процесса (круг), означа­ет, что ресурс ранее был запрошен процессом, получен и в данный момент ис­пользуется этим процессом. На рис. 3.1, а ресурс R в настоящее время отдан процессу А.

А

S

D

T

U

R

B

C

А б в

Рис. 3.1. Графы распределения ресурсов: ресурс занят (а); запрос ресурса (б); взаимоблокировка (в)

Ребро, направленное от процесса к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к этому ресурсу. На рис. 3.1, б процесс В ждет ресурс 5. На рис. 3.1, в мы видим взаимоблокиров­ку: процесс С ожидает ресурс Т, удерживаемый в настоящее время процессом D. Процесс D вовсе не намеревается освобождать ресурс Г, потому что он ждет ресурс U, используемый процессом С. Оба процесса будут ждать до бесконечности.

Цикл в графе означает наличие взаимоблокировки, циклично включающей про­цессы и ресурсы (предполагается, что в системе есть по одному ресурсу каждого вида). В этом примере циклом является последовательность C-T-D-V-C.

Теперь рассмотрим пример того, как можно использовать графы ресурсов. Представим, что у нас есть три процесса: А, В и С, и три ресурса: R, S и Т. Пос­ледовательность запросов и возвратов ресурсов для трех процессов показаны на рис. 3.2, а—в. Операционная система может запустить любой незаблокированный процесс в любой момент времени, значит, она может решить запустить сначала процесс А. Процесс А будет выполняться до тех пор, пока не закончит всю свою работу, затем будет запущен процесс В до его завершения и, наконец, процесс С.

Такой порядок не приводит к взаимоблокировке (потому что при нем не воз­никает соперничества за использование ресурсов), но при нем также вообще нет параллельной работы. Кроме запросов и возвратов ресурсов, процессы выполня­ют вычисления и ввод-вывод данных. Когда процессы работают последовательно, невозможна ситуация, при которой один процесс использует процессор, в то вре­мя как другой ждет завершения операции ввода-вывода. Таким образом, строго последовательная работа процессов не может быть оптимальной. С другой сто­роны, если вообще ни один процесс не выполняет операций ввода-вывода, алго­ритм «кратчайшая задача — первая» работает лучше, чем циклический, поэтому в некоторой обстановке последовательный запуск всех процессов может быть наилучшим.

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

A B C

Запросить R Запросить S Запросить T

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

Освободить S Освободить T Освободить R

B

A

C

C

а б в

1

A

C

B

A

B

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

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

3 . C запрашивает T

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

5. B запрашивает T

6

R

S

T

R

S

T

R

S

T

. C запрашивает R

Взаимоблокировка

г д е ж

A

B

C

A

B

C

A

B

C

.

R

S

T

R

S

T

R

S

T

з и к

1

B

A

B

C

A

B

C

A

B

C

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

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

3 . C запрашивает T

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

5. B запрашивает T

6

R

S

T

R

S

T

R

S

T

. C запрашивает R

Нет взаимоблокировки

л м н о

A

B

C

A

B

C

A

B

C

.

R

S

T

R

S

T

R

S

T

п р с

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

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

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

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

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

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

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

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

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

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

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

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

Теперь предположим, что система UNIX имеет 100 ячеек процессов. Работают десять программ, каждой необходимо создать 12 (под)процессов. После образова-

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