Граф распределения ресурсов

Задачу установления факта возникновения тупиковой ситуации удобно ре­шать с помощью графа распределения ресурсов. На рис. 1 представлены два основных типа отношений (рис. 1, а) на графе (запрос ресурса и владение им) и простейший пример системы в состоянии кругового ожидания —(тупика) (рис 1, б)

Рис. 1. Примеры графа распределения ресурсов

Для обнаружения тупиков выполняется редукция (приведение) графа. Су­ществует правило редукции — для каждого незаблокированного процесса (т. е. процесса, все запросы которого могут быть удовлетворены) нужно уб­рать все входящие и исходящие дуги. Граф полностью приводим, если после редукции он не содержит ни одной дуги. В системе отсутствуют тупиковые ситуации, если соответствующий граф полностью приводим.

2. Сеть Петри — помеченный ориентированный граф с двумя типами вершин: позициями и переходами. Позиции изображаются кругами, переходы — квадратами, а пометки — жирными точками в позициях.

Разметка — функция, которая ставит в соответствие пометкам позиции це­лое неотрицательное число. Разметка может быть изменена с помощью сра­батывания (запуска) перехода. Переход называется запускаемым, если в каж­дой позиции, из которой ведет стрелка в данный переход, есть хотя бы одна метка. Запуск перехода заключается в том, что из каждой позиции, из кото­рой ведет стрелка, число пометок уменьшается на единицу. А в каждую по­зицию, в которую ведет стрелка, число пометок увеличивается на единицу.

Семантически позиции удобно рассматривать как некоторые условия, а пе­реходы как некоторые события, происходящие в системе. Разметка называ­ется живучей, если каждый из переходов в системе может быть запущен бес­конечное число раз. Когда достигается разметка, при которой ни один из переходов не может быть запущен, говорят, что сеть Петри " зависла". Если разметка живучая, то система не остановится.

Рис. 2. Моделирование взаимного исключения с помощью сети Петри

На рис. 2 выполнено моделирование взаимного исключения между двумя процессами с помощью сети Петри.

Позиции, помеченные КУ1 и КУ2, представляют соответственно критические участки первого и второго процесса. При текущей разметке могут быть за­пущены переходы Р11 или Р21. Если запускается переход Р11, то позиция КУ1 получает пометку (система входит в критический участок). При этом второй процесс не может войти в КУ2, поскольку разделяемая позиция явля­ется пустой. Теперь может быть запущен только переход Р12. После его за­пуска система возвращается в исходное состояние.