Понятие тупиковой ситуации при выполнении параллельных вычислительных процессов

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

При параллельном исполнении процессов могут возникать тупиковые ситуации, когда два или более процесса блокируют друг друга, вынуждая ожидать наступле­ния события, связанного с освобождением ресурса. Самым простым является слу­чай, когда каждый из двух процессов ожидает ресурс, занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжить исполнение и освободить в конечном итоге ресурс, необходимый другому процессу. Эта ситу­ация называется тупиком, дедлоком (dead lock¹), или клинчем. Говорят, что в муль­типрограммной системе процесс находится в состоянии тупика, если он ждет события, которое никогда не произойдет. Тупики чаще всего возникают из-за кон­куренции несвязанных параллельных процессов за ресурсы вычислительной сис­темы, но иногда к тупикам приводят и ошибки программирования взаимодейству­ющих вычислений.

' Dead lock (англ.) — смертельное объятие.

248_______________________ Глава 8. Проблема тупиков и методы борьбы с ними

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

- повторно используемые (Reusable Resource, RR), или системные (System Re­
source, SR), ресурсы;

- потребляемые, или расходуемые, ресурсы (Consumable Resource, CR).

Системные ресурсы (SR) есть конечное множество идентичных единиц некоторо­го вида ресурсов, обладающих следующими свойствами [54]:

- число единиц ресурса в системе неизменно;

- каждая единица ресурса либо доступна, либо выделена одному и только одно­
му процессу (разделение отсутствует или не принимается во внимание, так как
не оказывает влияния на распределение ресурсов, а значит, и на возникновение
тупиковой ситуации);

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

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

Расходуемые ресурсы (CR) отличаются от ресурсов типа SR в нескольких важных отношениях [17].

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

- Процесс «потребитель» уменьшает число единиц ресурса, сначала запрашивая
и затем приобретая (потребляя) одну или более единиц. Единицы ресурса, ко­
торые приобретены, в общем случае не возвращаются ресурсу, а потребляются
(расходуются). Эти свойства потребляемых ресурсов присущи многим синхро­
низирующим сигналам, сообщениям и данным, порождаемым как аппаратурой,
так и программным обеспечением, и могут рассматриваться как ресурсы типа
CR при изучении тупиков. В их число входят: прерывания от таймера и уст­
ройств ввода-вывода; сигналы синхронизации процессов; сообщения, содержа­
щие запросы на различные виды обслуживания или данные, а также соответ­
ствующие ответы.

Для исследования параллельных процессов и, в частности, проблемы тупиков было разработано несколько моделей. Одной из них является модель повторно используе­мых ресурсов Холта [54]. Согласно этой модели система представляется как набор (множество) процессов и набор ресурсов, причем каждый из ресурсов состоит из

Примеры тупиковых ситуаций и причины их возникновения_____________________ 249

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

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

Пример одного из состояний системы из двух процессов с ресурсами типа SR пред­ставлен на рис. 8.1.

Рис. 8.1. Пример модели Холта

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

Примеры тупиковых ситуаций и причины их возникновения

Для понимания основных причин возникновения тупиков рассмотрим несколько простых характерных примеров.

250_______________________ Глава 8. Проблема тупиков и методы борьбы с ними

Пример тупика на ресурсах типа CR

Пусть имеется три процесса Пр1, Пр2 и ПрЗ, которые вырабатывают сообщения Ml, M2 и МЗ соответственно. Эти сообщения представляют собой ресурсы типа CR. Пусть процесс Пр1 является потребителем сообщения МЗ, процесс Пр2 дол­жен получить сообщение Ml, а ПрЗ ожидает сообщение М2 от процесса Пр2. Та­ким образом, каждый из этих трех процессов является и поставщиком, и потреби­телем одновременно, и вместе они образуют кольцевую систему (рис. 8.2) передачи сообщений через почтовые ящики (ПЯ).

Рис.8.2. Кольцевая схема взаимодействия процессов

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

Листинг 8.1. Вариант псевдокода без тупиковой ситуации

Пр1:

ПОСЛАТЬ СООБЩЕНИЕ (Пр2, Ml. ПЯ2): ЖДАТЬ СООБЩЕНИЕ (ПрЗ. МЗ. ПЯ1);

Пр2:

ПОСЛАТЬ СООБЩЕНИЕ (ПрЗ, М2. ПЯ3); ЖДАТЬ СООБЩЕНИЕ (Пр1. Ml. ПЯ2);

ПрЗ:

ПОСЛАТЬ СООБЩЕНИЕ (Пр1. МЗ. ПЯ1): ЖДАТЬ СООБЩЕНИЕ (Пр2. М2. ПЯЗ);

Примеры тупиковых ситуаций и причины их возникновения_____________________ 251

Листинг 8.2. Вариант псевдокода с тупиковой ситуацией

Пр1:

ЖДАТЬ СООБЩЕНИЕ (ПрЗ, МЗ. ПЯ1): ПОСЛАТЬ СООБЩЕНИЕ (Пр2. Ml. ПЯ2);

Пр2:

ЖДАТЬ СООБЩЕНИЕ (Пр1. Ml. ПЯ2): ПОСЛАТЬ СООБЩЕНИЕ (ПрЗ. М2. ПЯЗ):

ПрЗ:

ЖДАТЬ СООБЩЕНИЕ (Пр2. М2. ПЯЗ): ПОСЛАТЬ СООБЩЕНИЕ (Пр1. МЗ. ПЯ1):

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

Пример тупика на ресурсах типа CR и SR

Пусть некоторый процесс Пр1 должен обменяться сообщениями с процессом Пр2 и каждый из них запрашивает некоторый ресурс R, причем Пр1 требует три едини­цы этого ресурса для своей работы, а Пр2 — две единицы и только на время обра­ботки сообщения. Всего же имеется только четыре единицы ресурса R. Запрос и освобождение ресурса можно реализовать через соответствующий монитор с про­цедурами REQUESTER, N) — запрос N единиц ресурса R, и RELEASE(R, N) — освобожде­ние (возврат) N единиц ресурса R. Обмен сообщениями будем осуществлять через почтовый ящик MB. Фрагменты программ Пр1 и Пр2 приведены в листинге 8.3.

Листинг 8.3. Пример тупика на ресурсах CR и SR

Пр1: REQUEST ( R. 3 ) ;

SEND_MESSAGE ( Пр2. сообщение, MB ): WAIT_ANSWER ( ответ, MB ):

RELEASE ( R. 3 ):

Пр2: WAIT_MESSAGE ( Пр1. сообщение, MB ):
REQUEST ( R. 2 ):
ОБРАБОТКА СООБЩЕНИЯ:
RELEASE ( R. 2 ): продолжением

252_______________________ Глава 8. Проблема тупиков и методы борьбы с ними

Листинг 8.3(продолжение)

SEND_ANSWER ( ответ. MB ):

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

Пример тупика на ресурсах типа SR

Предположим, что существуют два процесса Пр1 и Пр2, разделяющих два ресурса типа SR: R1 и R2. Пусть взаимное исключение доступов к этим ресурсам реализует­ся с помощью семафоров S1 и S2 соответственно. Процессы Пр1 и Пр2 обращаются к ресурсам так, как показано на рис. 8.3 [17].

Процесс Пр 1 Процесс Пр 2

1: P(S2); (5):P(S1);

2: P(S1); (6):P(S2);

3: V(S1); (7):V(S1);

4: V(S2); (8):V(S2);

Рис. 8.З. Пример последовательности операторов для двух процессов, которые могут привести к тупиковой ситуации

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

Горизонтальная ось задает выполнение процесса Пр1, вертикальная — процесса Пр2. Вертикальные линии, пронумерованные от 1 до 4, соответствуют операторам 1-4 процесса Пр1; аналогично горизонтальные линии, пронумерованные от 5 до 8, соответствуют операторам 5-8 программы Пр2. Точка па плоскости определяет состояние вычислений в некоторый момент времени. Так, точка А соответствует ситуации, при которой процесс Пр1 начал исполнение, но не достиг оператора 1, а процесс Пр2 выполнил оператор 6, но не дошел до оператора 7. По мере выпол-

Примеры тупиковых ситуаций и причины их возникновения_____________________ 253

нения точка будет двигаться горизонтально вправо, если исполняется процесс Пр 1, и вертикально вверх, если исполняется процесс Пр2.

Рис. 8.4. Пространство состояний системы двух параллельных конкурирующих процессов

Интервалы исполнения, во время которых ресурсы R1 и R2 используются каж­дым процессом, показаны с помощью фигурных скобок. Линии 1-8 делят простран­ство вычислений на 25 областей, каждая из которых соответствует определенному состоянию в распределении ресурсов в процессе вычислений. Закрашенные се­рым цветом состояния являются недостижимыми из-за взаимного исключения процессов Пр1 и Пр2 при доступе к ресурсам R1 и R2.

Рассмотрим последовательность исполнения 1-2-5-3-6-4-7-8, представленную тра­екторией Т1. Когда процесс Пр2 запрашивает ресурс R1 (оператор 5), ресурс недо­ступен (оператор выполнен, семафор закрыт). Поэтому процесс Пр2 заблокиро­ван в точке В. Как только процесс Пр1 достигнет оператора 3, процесс Пр2 деблокируется по ресурсу R1. Аналогично в точке С процесс Пр2 будет заблоки­рован при попытке доступа к ресурсу R2 (оператор 6). Как только процесс Пр1 достигнет оператора 4, процесс Пр2 деблокируется по ресурсу R2.

Если же, например, выполняется последовательность 1-5-2-6, то процесс ПР1 за-блокируется в точке X при выполнении оператора 2, а процесс Пр2 заблокируется в точке Y при выполнении оператора 6. При этом процесс ПР1 ждет, когда процесс Пр2 выполнит оператор 7, а Пр2 ждет, когда Пр 1 выполнит оператор 4. Оба процесса бу­дут находиться в тупике, ни Пр1, ни Пр2 не смогут закончить выполнение. При этом все ресурсы, которые получили оба процесса, становятся недоступными для других

254_______________________ Глава 8. Проблема тупиков и методы борьбы с ними

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

Исследования проблемы тупиков показали, что для возникновения тупиковой ситуации необходимо одновременное выполнение следующих четырех условий [17, 54]:

- условия взаимного исключения, при котором процессы осуществляют моно­польный доступ к ресурсам;

- условия ожидания, при котором процесс, запросивший ресурс, ждет до тех пор, пока запрос не будет удовлетворен, при этом удерживая ранее полученные ре­сурсы;

- условия отсутствия перераспределения, при котором ресурсы нельзя отобрать у процесса, если они ему уже выделены;

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

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