Обнаружение взаимоблокировки при использовании одного ресурса каждого типа

Начнем с самого простого случая, когда используется только один ресурс каждого типа.

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

Действие алгоритма основано на выполнении следующих шагов:

1. Для каждого узла N, имеющегося в графе, выполняются следующие пять шагов,
использующих узел Nb качестве начального.

2. Инициализируется (очищается) список L, а со всех ребер снимаются пометки.

3. Текущий узел добавляется к концу списка L, и проводится проверка, не появит­
ся ли этот узел в списке L дважды. Если это произойдет, значит, граф содержит
цикл (отображенный в списке L) и алгоритм прекращает работу.

4. Для заданного узла определяется, нет ли каких-нибудь отходящих от него непо­
меченных ребер. Если такие ребра есть, осуществляется переход к шагу 5, если
их нет, осуществляется переход к шагу 6.

5. Произвольно выбирается и помечается непомеченное отходящее от узла ребро.
Затем по нему осуществляется переход к новому текущему узлу, и алгоритм
возвращается к шагу 3.

6. Если этот узел является первоначальным узлом, значит, граф не содержит ни­
каких циклов, и алгоритм завершает свою работу. В противном случае алгоритм
зашел в тупик. Этот узел удаляется, и алгоритм возвращается к предыдущему
узлу, то есть к тому узлу, который был текущим перед только что удаленным
узлом, данный узел делается текущим и осуществляется переход к шагу 3.

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