Проблема тупиков и методы борьбы с тупиками

Понятие тупика двух процессов

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

Заблокированные процессы не потребляют время ЦП, но удерживают ресурсы и не выполняют полезной работы.

Модель Холта

Процессы представляются квадратами, а ресурсы – кружками, в которых показано количество ресурсов. Дуга, соединяющая процесс и ресурс, означает запрос единицы ресурса.

Рисунок 1-9 запрос 2 х единиц R1

Дуга, соединяющая ресурс и процесс – показывает выделение ресурса процессу.

Рисунок 1-10 - P2 владеет одной единицей ресурса R2

Пример модели Холта.

Рисунок 1-11 –модель Холта граф используемых ресурсов

В некоторый момент времени P1 запрашивает 2 единицы R1 и запрашивает 1 единицу R2. P2 – запрашивает 1 единицу R2 и владеет 2 единицами R1.

Каждому процессу нужны все требуемые ресурсы, чтобы он мог продолжить выполнение. Предположим, что процесс Р1 получил бы теперь запрошенную им единицу R2. Если удовлетворить запрос Р1 на ресурс R2 это может привести к тупиковой ситуации. P1 не сможет продолжиться до тех пор, пока Р2 не освободит единицу ресурса R1, а процесс Р2 не сможет продолжиться до тех пор, пока Р1 не освободит единицу R2.

Если не удовлетворить Р1 – отдать Р2 – он завершится.

Пример тупика двух конкурирующих процессов.

Процесс_1 Процесс_2

* *

* *

1: P(S2); 5: P(S1);

* *

* *

2: P(S1); 6: P(S2);

* *

* *

3: V(S1); 7: V(S1);

* *

* *

4: V(S2); 8: V(S2);

* *

Возникновение тупика возможно, Если выполнена последовательность 1..5 – теперь тупик неизбежен.