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

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

При параллельном исполнении процессов могут возникать тупиковые ситуации, когда два или более процесса блокируют друг друга, вынуждая ожидать наступле­ния события, связанного с освобождением ресурса. Самым простым является слу­чай, когда каждый из двух процессов ожидает ресурс, занятый другим процессом. Из-за такого ожидания ни один из процессов не может продолжить исполнение и освободить в конечном итоге ресурс, необходимый другому процессу. Эта ситу­ация называется тупиком, дедлоком (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 ): продолжением

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

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