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

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

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