Лекция 10.

Рассмотрим примеры образования тупиков:

Будем считать, что на момент времени 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. Распознавание тупика с последующим восстановлением.

Все методы чрезвычайно сложные, как правило, базируются на анализе событийного графа, изображаемого с помощью сетей ПЕТРИ. Построение анализа сложная и дорогостоящая (с точки зрения большого расхода ресурсов) операция.

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

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

3. Метод распознавания состоит в том, что система не прогнозирует тупиков, и если он случился, то только тогда система описывает ситуацию и начинает принимать методы по восстановлению (по принципу что удастся спасти). Метод используется чаще и дешевле других методов, система работает быстрее.

Организация ввода-вывода