Graf čekání

Wait graph (neboli graf čekání transakcí ) je nástroj používaný při vývoji DBMS a vícevláknových systémů a sloužící zejména k určení situace uváznutí . Ve skutečnosti je graf čekající transakce řízený bipartitní graf obsahující dva typy vrcholů:

vrcholy typu odpovídající transakcím nebo běžícím vláknům. Tvoří první část grafu. $T$
vrcholy typu odpovídající zdrojům a objektům, které mohou být zachyceny transakcemi. Tvoří druhou část grafu. $R$

Oblouky čekacího grafu mají také dvojí význam:

oblouky jdoucí z transakčního uzlu do zdrojového uzlu indikují, že tento zdroj již byl zachycen transakcí $(T,R)$ $T$ $R$
oblouky jdoucí z uzlu zdroje do uzlu transakce indikují, že transakce čeká na uvolnění zdroje . $(R,T)$ $R$ $T$ $R$

Nejjednodušší vlastnosti

Zdroj, který nemá žádné příchozí oblouky, je zdarma.
Pokud má vrchol transakce určitý nenulový počet příchozích oblouků, pak je odpovídající proces (samotná transakce) ve stavu čekání, to znamená, že je pozastaven a nemůže být v aktuálním čase proveden.
Pokud existuje cesta mezi dvěma transakcemi , musí být transakce provedena (dokončena) před zahájením provádění , protože ta vyžaduje uvolnění některých zdrojů zachycených transakcí . $T_{1}\rightarrow T_{2}$ $T_{1}$ $T_{2}$ $T_{1}$

Z poslední vlastnosti samozřejmě vyplývá, že mrtvá situace odpovídá cyklu na čekacím grafu.

Zdroje

Slepé uličky, rozpoznávání a ničení Archivováno 2. března 2007 na Wayback Machine