4. Проблема тупиков и её решение

4.1. Проблема тупиков, разделяемые ресурсы и модели параллельных процессов

Ранее, в разделе 3.3.5 была рассмотрена ситуация в которой два процесса заблокировали друг друга и не могли освободить разделяемый ресурс. Эта ситуация называется тупиком. Можно утверждать, что проблема тупиков порождается наличием разделяемых ресурсов.

При рассмотрении проблемы разделяемые ресурсы делятся на два класса:

• повторно используемые (RR) ресурсы, они же системные ресурсы (SR);

• потребляемые (они же расходуемые) ресурсы (CR).

Системные ресурсы SR представляют собой множество идентичных единиц некоторого вида ресурсов. Это множество единиц конечно и неизменно в операционной системе. Каждая единица ресурса либо доступна, либо выделена какому-либо процессу. Никакой процесс не может влиять на ресурс (или на его единицу), который ему не принадлежит. К системным ресурсам относятся основная и внешняя память, периферийные устройства, иногда процессоры, программное обеспечение, файлы данных, таблицы и разрешение войти в критическую секцию.

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

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

• модель повторно используемых ресурсов Хольта;

• сети Петри;

• модель пространства состояний системы.

4.2. Модель повторно используемых ресурсов Холта1

Модель Холта представляет собой граф состояний ресурсов и процессов, имеющий вершины двух типов и направленные дуги (стрелки), показывающие запрос и выделение ресурса процессу. Вершинами графа являются процессы и ресурсы. Процессы обозначаются прямоугольниками (квадратами), а ресурсы – кружками. Число точек в кружке показывает количество единиц ресурса. Условные обозначения модели Хольта приведены в табл. 4.1. Пример модели Хольта [1] для двух процессов, в которой возможен тупик, показан на рис. 4.1. На модели показано ситуация, в которой процесс ПР1 запрашивает две единицы ресурса R1 и одну единицу ресурса R2. В то же время процесс ПР2 уже захватил две единицы ресурса R1 и запросил единственную единицу ресурса R2. На долю процесса ПР1 осталась только одна единица ресурса R1 и процесс может перейти в режим ожидания.

Таблица 4.1. Условные обозначения модели Холта

Обозначение	Смысл обозначения
ПР	Процесс ПР
	Ресурс R с четырьмя единицами
	Запрос единицы ресурса
	Выделение единицы ресурса

Рис. 4.1. Пример модели Холта с тупиком

В зависимости от последовательности захвата ресурса процессами и правила освобождения ресурсов в этой ситуации, возможно, возникнет тупик. Если правило освобождения ресурса предусматривает возможность освобождения ресурса только после получения процессом всех ресурсов, и процесс ПР1 захватил ресурс R2 раньше процесса ПР2, то тупик возникнет. Тупик возникнет потому, что процесс ПР1 будет находиться в режиме ожидания недостающей единицы ресурса R1 и не сможет освободить ресурс R2, а процесс ПР2 не сможет освободить недостающую единицу ресурса R1, т.к. не имеет ресурса R2.

При обмене процессами сообщениями через почтовые ящики по кольцевой схеме (рис. 4.2) возможно возникновение тупика. Процессы ПР1, Пр2, Пр3 создают сообщения М1, М2 и М3 соответственно. Посылка сообщения является запросом разделяемого ресурса типа CR, приём сообщения – освобождением запрошенного ресурса. Следует помнить, что процесс может послать сообщение только в почтовый ящик при наличии свободного гнезда.

Рис. 4.2. Кольцевая схема обмена сообщениями через почтовые ящики

Взаимодействие процессов осуществляется посредством получения сообщений от предшествующего процесса и посылкой сообщения последующему. Текст программы, обеспечивающей отсутствие тупика, приведён на рис. 4.3.

. . .
Parbegin
ПР1:	Начало описания процесса ПР1
SAND_MASSAGE(ПР2, М1, ПЯ2);	Посылка сообщения процессу ПР2
WAIT_MASSAGE(ПР3, М3, ПЯ1);	Ожидание сообщения от процесса ПР3
. . .
ПР2:	Начало описания процесса ПР2
SAND_MASSAGE(ПР3, М2, ПЯ3);	Посылка сообщения процессу ПР3
WAIT_MASSAGE(ПР1, М1, ПЯ2);	Ожидание сообщения от процесса ПР1
. . .
ПР3:	Начало описания процесса ПР3
SAND_MASSAGE(ПР1, М3, ПЯ1);	Посылка сообщения процессу ПР1
WAIT_MASSAGE(ПР2, М2, ПЯ3);	Ожидание сообщения от процесса ПР2
. . .
Parend

Рис. 4.3. Текст программы при кольцевой схеме обмена сообщениями

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

Таким образом, при кольцевом обмене процессов сообщениями причиной тупика является неправильная последовательность операторов посылки и ожидания сообщения.

Примером другого тупика являетс тупик на ресурсах CR и SR. Два процесса ПР1 и ПР2 запрашивают у ресурса R1, имеющего тип CR, три и две единицы соответственно, а ресурс их имеет только четыре. Процессы обмениваются сообщениями, которые являются системными ресурсами SR и проходят через почтовый ящик ПЯ.

Рис. 4.4. Модель Холта, иллюстрирующая тупик

Процесс ПР1 использует ресурс для своей работы, а ПР2 – только на время обработки сообщения. Модель Хольта для такого взаимодействия процессов показана на рис. 4.4, текст программы, реализующей взаимодей­ствие процессов процессы с помощью мониторов, приведён на рис. 4.5.

Мониторы реализованы с помощью операторов REQUEST (запрос ресурса) и RELEASE (освобождение ресурса). Первый процесс захватывает ресурс R1 в самом начале работы и освобождает в конце. Второй ресурс ждёт прихода сообщения от процесса ПР1, затем запрашивает ресурс R1, затем обрабатывает сообщение и только после этого освобождает ресурс.

. . .
Parbegin
ПР1:	Начало описания процесса ПР1
REQUEST(R1,3);	Запрос 3-х единиц ресурса R1
. . .
SAND_MASSAGE(ПР2, М1, ПЯ);	Посылка сообщения М1 процессу ПР2
WAIT_ANSWER(М2, ПЯ);	Ожидание ответа М2 от процесса ПР2
. . .
RELEASE(R1,3);	Освобождение 3-х единиц ресурса R1
ПР2:	Начало описания процесса ПР2
. . .
WAIT_MASSAGE(ПР1, М1, ПЯ2);	Ожидание сообщения от процесса ПР1
REQUEST(R1,2);	Запрос 3-х единиц ресурса R1
. . .;	Обработка сообщения
RELEASE(R1,2);	Освобождение 3-х единиц ресурса R1
SAND_ANSWER(М1, ПЯ);	Посылка ответа процессу ПР1
. . .
Parend

Рис. 4.5. Текст программы при кольцевой схеме обмена сообщениями

Причиной постоянно возникающего тупика является запрос процессами ПР1 и ПР2 у ресурса R1 сразу пяти единиц, в то время как ресурс имеет их только четыре. Процесс ПР1, начав выполняться первым, захватит три единицы ресурса R1 и будет ожидать ответа от процесса ПР2. Процесс ПР2, дождавшись сообщения от процесса ПР1, будет заблокирован, т.к. запросит две единицы ресурса R1 при наличии только одной свободной единицы. Таким образом, процесс ПР1 будет ожидать ответ от процесса ПР2 и не сможет освободить ресурс R1, а ПР2 не сможет послать ответ, потому что будет заблокирован недостатком единицы ресурса R1.

Возникновение тупика возможно и на ресурсах системных ресурсах типа SR. Пусть два процесса ПР1 и ПР2 обращаются к ресурсам R1 и R2. Взаимное исключение доступов к ресурсам реализуется на семафорах S1 и S2. Работа процессов с семафорами показана на рис. 4.6, граф Хольта – на рис. 4.5, анализ состояний с помощью пространства состояний – на рис. 4.7.

. . .
Parbegin
ПР1:	Начало описания процесса ПР1	ПР2:	Начало описания процесса ПР1
. . .		. . .
1: P(S2);	Закрытие S2	5: P(S1);	Закрытие S1
. . .		. . .
2: P(S1);	Закрытие S1	6: P(S2);	Закрытие S2
. . .		. . .
3: V(S1);	Открытие S1	7: V(S1);	Открытие S2
. . .		. . .
4: V(S2);	Открытие S2	8: V(S2);	Открытие S1
. . .		. . .
		Parend

Рис. 4.6. Управление семафорами в примере тупика на системных ресурсах SR

На рис. 4.6 метками 1 – 4 показаны номера операторов процесса ПР1, а метками 4 – 8 – номера операторов процесса ПР2. На рис. 4.7 стрелки, направленные к ресурсам показывают запрос ресурса, а направленные от ресурсов – захват ресурсов. Из рис. 4.7. видно, что возможно возникновение тупиков, т.к. процессы могут одновременно запросить одни и те же ресурсы. Всё зависит от последовательности работы семафоров во времени.

Рис. 4.7. Граф модели Холта для примера тупика на ресурсах SR

ПР2 8 7 6 5 Т1 А Т2 Y X B C ПР1 1 2 3 4 Рис. 4.8. Пространство состояний процессов ПР1 и ПР2

На рис. 4.8 пунктирные линии 1 – 4 и 5 – 8 соответствуют операторам процессов ПР1 и ПР2 соответственно. Изменение состояний процессов показано жирными направленными линиями Т1 и Т2. Эти линии называются траекториями. Пересечение пунктирных линий траекториям показывает моменты выполнения операторов. В исходных состояниях обе траектории начинаются из прямоугольника, находящегося в нижнем левом углу системы координат, т.е. ни один из операторов не выполнен.

Траектория Т1 безопасна, т.е. к моменту запроса процессом ПР2 ресурсов R1 (точка В) оба ресурса захвачены процессом ПР1, и процесс ПР2 окажется в режиме ожидания (поэтому траектория Т1 не пересекает линию 5). Пересечение траекторией Т1 линии 3 показывает освобождение ресурса S1, и процесс ПР2 выполняется до оператора 6, однако, в точке С процесс ПР2 опять заблокирован, потому что ещё не освобождён ресурс R2. После выполнения оператора 4 процесс ПР2 окончательно деблокируется, и процесс ПР2 выполняется до конца, освобождая ресурсы R1 и R2.

Траектория Т2 приводит к тупику. В точке Х процессы ПР1 и ПР2 благополучно захватили ресурсы R2 и R1 соответственно, а в точке Y они обратились к уже захваченным ресурсам, процессы заблокировали друг друга.

Тупики возможны, если на графах модели Холта присутствуют обращения двух и более процессов к одним и тем же ресурсам. Тогда ответ на вопрос "Возникнет ли тупик" даст анализ траекторий процессов в пространстве их состояний.

В [1] отмечено, что для появления тупиков должны одновременно выполняться четыре условия:

• взаимное исключение не запрещает монопольный доступ к разделяемым ресурсам (условие взаимного исключения);

• удержание процессом захваченного ресурса на время ожидания доступа к недостающим для продолжения его работы разделяемым ресурсам (условие ожидания);

• невозможность перераспределения ресурсов, захваченных процессами находящимися в режиме ожидания (условие отсутствия перераспределения);

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