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

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

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

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

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