Sočasno izvajanje transakcij - Odpravljanje mrtve zanke

Mrtvo zanko je potrebno najprej odkriti, nato pa pristopimo k njenemu razreševanju. V ta namen lahko uporabimo čakalni graf.

Čakalni graf

Primer čakalnega grafa brez cikla:

Čakalni graf je usmerjni graf G = < V, P >

V

množica vozlišč, v kateri vsak predstavlja po eno aktivno transakcijo T_i

P

množica usmerjenih povezav (T_i, T_j), ki predstavljajo čakanje transakcije T_i na odobritev zaseženja podatka, ki ga ima zaseženega transakcija T_j

Mrtva zanka

Mrtva zanka se v grafu kaže kot cikel. V njem se lahko nahajata dve ali več transakcij, ki druga drugo čakajo na sprostitev zaseženj

Primer mrtve zanke, v kateri se nahajajo tri transakcije: T1, T2, T3.

Za odpravljanje mrtve zanke je zadolžen SUPB, ki ves čas vzdržuje čakalni graf.

Spremembe v grafu nastopijo:

• ob neodobrenih zahtevah po zaseženjih
• ob zaključkih transakcij

Odpravljanje mrtve zanke

Ko SUPB zasledi v grafu cikel, se mora lotiti odpravljanja mrtve zanke. Odpravi jo tako, da eno izmed transakcij v mrtvi zanki izbere za žrtev in prekine njeno izvajanje. S tem, ko se ena izmed transakcij v mrtvi zanki prekine, izgine iz čakalnega grafa tudi njeno vozlišče in vse pripadajoče povezave, kar pomeni, da cikla več. Po razveljavitvi ažuriranj prekinjene transakcije, eni izmed preostalih transakcij odobri zahtevano zaseženje, prekinjena transakcija pa se vrne v ponovno izvajanje.

Izbiranje žrtve

SUPB izbere žrtev preko enega od naslednjih kriterijev:

• čas izvajanja transakcij ("starost") do nastopa mrtve zanke,
• predvideni čas izvajanja transakcij do njihovega zaključka,
• število odobrenih zaseženj,
• število izvedenih ažuriranj.

Ne glede na izbrani kriterij je potrebno poskrbeti, da ne bo vedno znova razveljavljena ena in ista transakcija.

Razvoj čakalnega grafa