Граф ожидания

Материал из Википедии — свободной энциклопедии

Граф ожидания (или граф ожидания транзакций) — инструмент, используемый при разработке СУБД и многопоточных систем и используемый, в частности, для определения ситуации взаимной блокировки (deadlock). Фактически, граф ожидания транзакций представляет собой ориентированный двудольный граф, содержащий вершины двух типов:

вершины типа $T$ , соответствующие транзакциям или выполняющимся потокам. Они образуют первую долю графа.
вершины типа $R$ , соответствующие ресурсам и объектам, которые могут быть захвачены транзакциями. Они образуют вторую долю графа.

Дуги, или рёбра, графа ожидания также имеют двоякий смысл:

ребра $(T, R)$ , идущие из вершины-транзакции $T$ в вершину-ресурс $R$ , обозначают, что данный ресурс уже захвачен транзакцией
ребра $(R, T)$ , идущие из вершины-ресурса $R$ в вершину-транзакцию $T$ обозначают, что транзакция ожидает, пока ресурс $R$ будет освобождён.

[править] Простейшие свойства

Ресурс, который не имеет ни одного входящего ребра, является свободным.
Если вершина-транзакция имеет некоторое ненулевое количество входящих ребёр, то соответсвующий процесс (собственно транзакция) находится в состоянии ожидания, то есть приостановлен и не может выполняться в текущий момент времени.
Если между двумя транзакциями существует путь $T_1 \rightarrow T_2$ , то транзакция $T 1$ должна быть выполнена (завершена) раньше, чем начнётся выполнение $T 2$ , поскольку последняя требует освобождения некоторых ресурсов, захваченных транзакцией $T 1$ .