Условия возникновения тупиков

Концепция ресурса

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

Как устройства, так и данные могут являться ресурсами.

Некоторые виды ресурсов допускают разделение между процессами, то есть являются разделяемыми устройствами (например, память, процессор, диски), другие не допускают разделение между процессами, то есть являются выделенными ( например, лентопротяжное устройство).Чаще всего тупики связаны с выделенными ресурсами, то есть тупики возникают, когда процессу дается эксклюзивный доступ к устройствам, файлам и другим ресурсам.

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

а) запросить (request) ресурс;

б) использовать (use) ресурс;

в) освободить (release) ресурс.

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

Будем предполагать, что когда запрос отклонен, процесс переходит в состояние ожидания.

Природа запроса сильно зависит от ОС. В некоторых системах имеется системный вызов request для прямого запроса на ресурс. В других - единственные ресурсы, о которых ОС знает - специальные файлы, которые только один процесс имеет право открывать за раз. Это делается обычным вызовом open. Если файл уже используется, вызывающий процесс блокируется, пока ресурс не освободится.

В 1971 г. Коффман, Элфик и Шошани сформулировали следующие четыре условия для возникновения тупиков.

1. Условие взаимоисключения (Mutual exclusion). Каждый ресурс выделен в точности одному процессу или доступен. Процессы требуют предоставления им монопольного управления ресурсами, которые им выделяются.

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

3. Условие неперераспределяемости (No preemtion). Ресурс, данный ранее, не может быть принудительно забран у процесса. Освобождены они могут быть только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс удерживает за собой один или более ресурсов, требующихся другим процессам цепи.

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

Обычно тупик моделируется прямым графом, наподобие того, что изображен на рис.8.1, состоящим из узлов двух видов: прямоугольников процессов и эллипсов ресурсов. Стрелки, направленные от ресурса к процессу, показывают, что ресурс выделен данному процессу.