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

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

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

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

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

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

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

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

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

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