Várakozási grafikon

A várakozási grafikon (vagy tranzakcióvárási grafikon ) egy olyan eszköz, amelyet DBMS és többszálú rendszerek fejlesztésében használnak, és különösen a holtponti helyzet meghatározására használják . Valójában a tranzakcióra váró gráf egy irányított bipartit gráf , amely kétféle csúcsot tartalmaz:

tranzakcióknak vagy futó szálaknak megfelelő típusú csúcsok . Ezek alkotják a grafikon első részét. $T$
az erőforrásoknak és az objektumoknak megfelelő típusú csúcsok, amelyeket a tranzakciók rögzíthetnek. Ezek alkotják a grafikon második részét. $R$

A várakozási grafikon ívei is kettős jelentéssel bírnak:

a tranzakciós csomóponttól az erőforrás csomópontig tartó ívek azt jelzik, hogy ezt az erőforrást a tranzakció már elfoglalta ${\megjelenítési stílus (T,R)}$ $T$ $R$
az erőforrás csomóponttól a tranzakciós csomópontig tartó ívek azt jelzik, hogy a tranzakció az erőforrás felszabadítására vár. ${\megjelenítési stílus (R,T)}$ $R$ $T$ $R$

A legegyszerűbb tulajdonságok

Az az erőforrás, amelynek nincs bejövő íve, ingyenes.
Ha egy tranzakciós csúcsnak van egy bizonyos nem nulla számú bejövő íve, akkor a megfelelő folyamat (maga a tranzakció) várakozási állapotban van, azaz felfüggesztve van, és pillanatnyilag nem hajtható végre.
Ha van egy útvonal két tranzakció között , akkor a tranzakciót a végrehajtás megkezdése előtt végre kell hajtani (befejezni) , mivel az utóbbihoz a tranzakció által lefoglalt erőforrások felszabadítása szükséges . $T_{1}\rightarrow T_{2}$ $T_{1}$ $T_{2}$ $T_{1}$

Az utolsó tulajdonságból nyilvánvalóan következik, hogy a holtpont helyzet a várakozási gráf egy ciklusának felel meg.

Források

Zsákutcák, felismerés és megsemmisítés archiválva 2007. március 2. a Wayback Machine -nél