Задачу установления факта возникновения тупиковой ситуации удобно решать с помощью графа распределения ресурсов. На рис. 1 представлены два основных типа отношений (рис. 1, а) на графе (запрос ресурса и владение им) и простейший пример системы в состоянии кругового ожидания —(тупика) (рис 1, б)
Рис. 1. Примеры графа распределения ресурсов
Для обнаружения тупиков выполняется редукция (приведение) графа. Существует правило редукции — для каждого незаблокированного процесса (т. е. процесса, все запросы которого могут быть удовлетворены) нужно убрать все входящие и исходящие дуги. Граф полностью приводим, если после редукции он не содержит ни одной дуги. В системе отсутствуют тупиковые ситуации, если соответствующий граф полностью приводим.
2. Сеть Петри — помеченный ориентированный граф с двумя типами вершин: позициями и переходами. Позиции изображаются кругами, переходы — квадратами, а пометки — жирными точками в позициях.
Разметка — функция, которая ставит в соответствие пометкам позиции целое неотрицательное число. Разметка может быть изменена с помощью срабатывания (запуска) перехода. Переход называется запускаемым, если в каждой позиции, из которой ведет стрелка в данный переход, есть хотя бы одна метка. Запуск перехода заключается в том, что из каждой позиции, из которой ведет стрелка, число пометок уменьшается на единицу. А в каждую позицию, в которую ведет стрелка, число пометок увеличивается на единицу.
Семантически позиции удобно рассматривать как некоторые условия, а переходы как некоторые события, происходящие в системе. Разметка называется живучей, если каждый из переходов в системе может быть запущен бесконечное число раз. Когда достигается разметка, при которой ни один из переходов не может быть запущен, говорят, что сеть Петри "зависла". Если разметка живучая, то система не остановится.
Рис. 2. Моделирование взаимного исключения с помощью сети Петри
На рис. 2 выполнено моделирование взаимного исключения между двумя процессами с помощью сети Петри.
Позиции, помеченные КУ1 и КУ2, представляют соответственно критические участки первого и второго процесса. При текущей разметке могут быть запущены переходы Р11 или Р21. Если запускается переход Р11, то позиция КУ1 получает пометку (система входит в критический участок). При этом второй процесс не может войти в КУ2, поскольку разделяемая позиция является пустой. Теперь может быть запущен только переход Р12. После его запуска система возвращается в исходное состояние.