Vänta graf

Väntediagram (eller transaktionsväntdiagram ) är ett verktyg som används i utvecklingen av DBMS och flertrådade system och används i synnerhet för att fastställa dödläget . Faktum är att transaktionsväntningsgrafen är en riktad tvådelad graf som innehåller två typer av hörn:

hörn av typ som motsvarar transaktioner eller löpande trådar. De utgör den första delen av grafen. $T$
hörn av typ som motsvarar resurser och objekt som kan fångas upp av transaktioner. De utgör den andra delen av grafen. $R$

Väntegrafens bågar har också en dubbel betydelse:

bågar som går från transaktionsnoden till resursnoden indikerar att denna resurs redan har fångats av transaktionen $(T,R)$ $T$ $R$
bågar som går från resursnoden till transaktionsnoden indikerar att transaktionen väntar på att resursen ska frigöras. $(R,T)$ $R$ $T$ $R$

De enklaste egenskaperna

En resurs som inte har några inkommande bågar är gratis.
Om en transaktionspunkt har ett visst antal inkommande bågar som inte är noll, är den motsvarande processen (transaktionen i sig) i ett vänteläge, det vill säga den är avstängd och kan inte utföras vid den aktuella tidpunkten.
Om det finns en väg mellan två transaktioner måste transaktionen exekveras (slutföras) innan exekveringen börjar , eftersom den senare kräver frigöring av vissa resurser som fångas upp av transaktionen . $T_{1}\rightarrow T_{2}$ $T_{1}$ $T_{2}$ $T_{1}$

Av den sista egenskapen följer uppenbarligen att dödlägessituationen motsvarar en cykel på väntande graf.

Källor

Återvändsgränder, erkännande och förstörelse Arkiverad 2 mars 2007 på Wayback Machine