Операционные системы. Курс лекций



Тупики. - часть 3


5.    Процесс П5 занимает ресурс Р3 и хочет получить Р5;

6.    Процесс П6 занимает ресурс Р6 и хочет получить Р2;

7.    Процесс П7 занимает ресурс Р5 и хочет получить Р4.

 

 

Рассмотрим алгоритм, который изучает граф и завершается когда находит цикл или когда показывает, что цикла нет. В алгоритме используется структура данных называющаяся список узлов L. Во время работы алгоритма на ребрах графа ставится метка, говорящая о том, что ребро проверено. Для каждого узла N выполняется 5 шагов:

1.    Задаются начальное условие: L- пустой список(все ребра не маркированные);

2.    Текущий узел добавляется в конец списка L и проверяется количество появлений узла в списке. Если узел присутствует в двух местах, значит, граф содержит цикл и работа алгоритма завершается;

3.    Для заданного узла определяется, выходит ли из него хотя бы одно не маркированное ребро, если да то к шагу 4, нет то к 5;

4.    Выбирается любое, не маркированное исходное ребро, помечается и за тем по нему осуществляется переход к новому текущему узлу и выполняется шаг 3;

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

 

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

m- число классов ресурсов,

- количество ресурсов класса 1 и т.д.

- вектор существующих ресурсов.

В любой момент времени некоторые из ресурсов могут оказаться заняты следовательно, вводится понятие A- вектор доступных ресурсов, C- матрица текущего распределения, R- матрица запросов.

Матрица текущего распределения показывает, какие и сколько ресурсов в данный момент использует процесс

 

 

 

 

R- показывает сколько ресурсов может потребоваться каждому процессу.




Начало  Назад  Вперед