Будем считать, что на момент времени t1 состояние системы описывается графом. Имеется 2 процесса P1 и P2),чки означают количество единиц ресурса.) стрелки означают запрос единицы ресурса, стрелки к процессу - получение единицы ресурса. Допустим, что в момент времени t2 процесс P1 получит единицу ресурса R2. в результате образовался тупик, т. к процесс P1 ждет 2 ух ресурсов, а их ему не хватает, т.к 2 отданы процессу P2. процессу P2 не хватает R2. оба процесса будут ждать бесконечно долго.
Замечание: Еслибы в момент t2 ресурс R2 был бы отдан процессу P2, тогда было бы все нормально, т.е. P2 работал бы т.к получил бы все необходимые ресурсы. А P1 ждал бы.
Допустим, что имеются 3 процесса взаимодействующие через почтовые ящики.
Допустим, что P1 является потребителем М1 через Р3. процесс Р2 получает сообщения М1 от Р1. А процесс Р3 сообщения М2 от Р2.
Образуется замкнутый цикл. Допустим, что процессы работают по следующему алгоритму, а именно: каждый из них сначала получает сообщение, потом ждет сообщение.
Р1: послать сообщение (Р2,М1, на2)
Ждать сообщение (Р3, М1 на 1)
Р2: послать сообщение (Р3, М2 на 3)
Ждать сообщение (Р1, М2 на 2)
Р3: послать сообщение (Р1, М3 на 1)
Ждать сообщение (Р2, М2 на 3)
При данном алгоритме реализация процессов будет нормальна функционировать.
Рассмотрим другой алгоритм:
Р1: Ждать сообщение (Р3, М1 на 1)
Послать сообщение (Р2,М1, на2)
Р2: Ждать сообщение (Р1, М2 на 2)
Послать сообщение (Р3, М2 на 3)
Р3: Ждать сообщение (Р2, М2 на 3)
Послать сообщение (Р1, М3 на 1)
Второй вариант неправильный, т.к все три процесса оказываются в тупике. Каждый из них ждет и будет ждать долго. В данном примере тупиковая ситуация возникла из-за неправильного алгоритма.
Борются с тупиковой ситуацией разные ОС по-разному. Существует 3 основных метода борьбы с тупиками:
Предупреждение тупиков.
Обход тупиков.
Распознавание тупика с последующим восстановлением.
Все методы чрезвычайно сложные, как правило, базируются на анализе событийного графа, изображаемого с помощью сетей ПЕТРИ. Построение анализа сложная и дорогостоящая (с точки зрения большого расхода ресурсов) операция.
1. Основная идея методов предупреждения тупиков заключается в том, что запрещается создавать опасные ситуации для тупиков. Как правило, это метод используется только в системах реального времени. ОС более просты по своему построению и рассчитана, как правило, на узкий круг задач. Заранее известны возможные варианты решения прикладных задач. С учетом этого запрещается входить в опасные ситуации.
2. Второй метод предполагает запрет входа процессов в опасные ситуации. ОС постоянно описывает текущую ситуацию по использованию ресурсов и если видит, что какой-то процесс запрашивая ресурс, создает опасную ситуацию, которая может привести к тупику, то такой процесс временно останавливается и ставится в состояние «ожидания».
3. Метод распознавания состоит в том, что система не прогнозирует тупиков, и если он случился, то только тогда система описывает ситуацию и начинает принимать методы по восстановлению (по принципу что удастся спасти). Метод используется чаще и дешевле других методов, система работает быстрее.