Методы и алгоритмы обнаружения тупиков

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

Допустим, в системе один ресурс каждого типа. Тогда необходимо построить граф распределения ресурсов между процессами. Если в графе обнаружится цикл – наличествует тупиковая ситуация.

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

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