Algoritmul de blocare in doua faze

Agenda

1. Algoritmul de blocare in doua faze

Principii de baza

Protocolul de blocare

Algoritmi de blocare

Blocarea in 2 faze

2. Problema interblocarii sau a blocajului mortal
3. Graful de asteptare
4. Grafe de precedenta
5. Graful de alocare
6. Prevenirea interblocarii
7. Detectarea interblocajelor

1. Algoritmul de blocare in doua faze

Principii de baza

Pana aici gestiunea tranzactiilor s-a efectuat controland doar granulele intr-o ordine predefinita a tranzactiilor. Daca nu se respecta ordinea se suspenda temporar unele dintre tranzactiile care au intervenit in conflict → metoda consta in detectarea executiilor neserializabile si suspendarea tranzactiilor.

Strategia bazata pe blocare - prevederea generarii de executii incorecte trecand in asteptare tranzactiile care ar dori sa efectuez operatii conflictuale pe aceeasi granula.

Primul obiectiv a strategiilor de blocare - de a nu lasa sa se execute deodata decat operatii compatibile.

D. Mod de operare - clasa a unei operatii care determina compatibilitatea cu altele.

Moduri de operare clasice - citire si punere la zi (citire, adaugare, modificare, scriere).

Moduri de operare - DBTG CODAYL:

M1 = consultare neprotejata

M2 = consultare protejata

M3 = punere la zi neprotejata

M4 = punere la zi protejata

M5 = consultare exclusiva

M6 = punere la zi exclusiva

Matricea de compatibilitate a operatiilor:

C=(c_ij)

cu    c_ij=1 daca operatiile sunt compatibile si c_ij=0 daca nu. Compatibilitatile se definesc prin:

C =

sau DBTG:

Protocolul de blocare

Controler-ul nu permite executarea simultana pe aceeasi granula decat a operatiilor compatibile → trebuie sa cunoasca:

• inceputul executarii unei operatii asupra unei granule
• modul de operare
• terminarea executiei operatiei.

D. Protocol de blocare (Locking protocol) - protocol de acces la granula caracterizat prin cereri de autorizare a operatiilor si semnalarea sfarsitului acestor operatii.

Operatii specifice:

• LOCK (g,M) - permite unei tranzactii sa indice controler-ului inceputul    unei operatii pe granula g, printr-o operatie data, M;
• UNLOCK (g) - permite tranzactiei sa indice controlerului ca a terminat operatia in curs pe g.

Protocolul necesita deci executarea a 2 operatii suplimentare: LOCK si UNLOCK. De regula se blocheaza automat o tranzactie in momentul in care cauta o granula in BD. De exemplu, indicatia DBTG este de a bloca automat articolul in curs de prelucrare in tranzactie si deblocarea automata a acestuia in momentul terminarii operatiei. Pentru blocare se mai propun 2 primitive KEEP si FREE. Majoritatea sistemelor grupeaza deblocarea fie la sfarsitul tranzactiei, fie in momente in care baza este intr-o stare coerenta, daca nu s-a cerut deblocarea individuala.

1.3. Algoritmi de blocare

Autorizarea accesului simultan pe o granula a operatiilor compatibile → memorarea modurilor de actiune pe granula - se asociaza unui cuplu granula g - tranzactia T_i , a unui vector de biti:

A(g,i)' = [a₁, a₂,., a_e]

cu a_j=1 daca modul M_j este in curs de executie pentru tranzactia T_i , pe granula g si 0 daca nu, unde ' este transpusa

Analog presupunem ca modurile de operare cerute de executarea unui LOCK(g.M) se definesc printr-un vector de biti:

M' = [m₁, m₂,., m_e]

unde m_j = 1 daca modul M_j este cerut si 0 altfel.

Notand cu:

- reuniunea binara a vectorilor booleeni

- negatia vectorilor booleeni

- incluziunea vectorilor booleeni

* - produsul matricial boolean linie prin coloana.

T. Modurile de operare cerute de o primitiva LOCK(g,M) executate de o tranzactie T_p sunt compatibile cu modurile de executie pe granule g de alte tranzactii

)

Algoritmul de blocare necesita definirea unei strategii in cazul in care modurile de operare cerute de executarea unui LOCK nu sunt compatibile cu cele care se executa pe granula. Metoda cea mai simpla este de a returna un raspuns "granula ocupata". O strategie corecta este de a bloca tranzactia pana cand se elibereaza granula. Pentru fiecare granula ocupata se ataseaza un fir de asteptare Q[g]. Acest fir contine cererile de blocare (identificatorii tranzactiilor) in asteptare in ordinea prioritatilor (in general FIFO). Pentru o tranzactie T_p → algoritm blocare/deblocare:

Procedure LOCK(g,M);

If )

Then A(g,p) = A(g,p) M;

Else "insereaza (p,M) in Q[g]";

"blocheaza tranzactia T_p;

EndIf

EndLOCK.

Procedure UNLOCK (g);

A(g,p):=0;

Do while (q,M') in Q[g]

If

Then A(g,q) = A(g,q) M';

"elimina (q,M') din Q[g]";

"deblocheaza tranzactia T_q;

EndIf

EndDo

EndUNLOCK.

Unde M' este modul de operare cerut de tranzactia curenta T_q.

Blocarea in 2 faze

Algoritmii anteriori permit executarea simultana pe o granula numai a operatiilor compatibile. Noi dorim sa executam operatiile in asa fel ca executia tranzactiilor sa fie serializabila (sa dea acelasi rezultat ca executarea in succesiune a tranzactiilor). Pentru aceasta trebuie sa se restranga ordinea de executie a operatiilor LOCK si UNLOCK. Aceasta restrictie se numeste "restrictia in 2 faze".

D. Tranzactie cu 2 faze (Two phase tranaction) - Tranzactie ce nu executa LOCK dupa un UNLOCK.

O tranzactie cu blocare in 2 faze trebuie sa blocheze toate granulele pe care va opera inainte de a incepe deblocarea. Curba de evolutie tipica a numarului de granule blocate de o tranzactie in 2 faze:

Teorema - indica importanta tranzactiilor in 2 faze si care va introduce regula de utilizare a protocolului de blocare in 2 faze pentru a nu permite decat executii neserializabile.

T. Orice executie completa a unei multimi de tranzactii in 2 faze este serializabila.

regulile de utilizare a primitivelor LOCK/UNLOCK pe care trebuie sa le respecte un SGBD:

(R1) - Orice tranzactie trebuie sa execute LOCK cu modurile de operare corecte pe granula inainte de executarea operatiei pe granula;

(R2) - Orice tranzactie trebuie sa execute UNLOCK, mai repede sau mai tarziu, pe granula aleasa dupa executia operatiei;

(R3) Nici o tranzactie nu poate executa LOCK dupa un UNLOCK.

Orice controler trebuie sa verifice ca tranzactiile controleaza corect aplicarea acestor reguli. In cazul general, cand se face distinctie numai intre citire si modificare, regula R1 se traduce prin - tranzactia trebuie sa inceapa blocarea in citire, pe o granula fara intentia de modificare si in scriere, la citirea unei granule care se doreste a fi modificata.

Blocarea in 2 faze necesita ca toate tranzactiile sa treaca prin faza de blocare maxima in care-si blocheaza toate granulele asupra carora opereaza → ordinea de acces la granula este cea data de momentul atingerii acestui maxim → blocarea in 2 faze poate fi considerata o ordonare a tranzactiilor. Ordinea nu este stabilita a priori ca in cazul ordonarii initiale (totale sau partiale) ci de momentul in care se ajunge la blocarea maxima.

2. Problema interblocarii sau a blocajului mortal

D. Interblocarea (Deadlock) - situatia in care granulele au fost blocate de un grup de tranzactii astfel ca sa aiba loc 2 conditii:

• Fiecare tranzactie din grup este blocata asteptand o granula;
• Tranzactiile grupului nu pot fi deblocate decat de o tranzactie externa.

Interblocarea este o problema de blocare dificil de rezolvat. Exista 3 modalitati de rezolvare:

• Evitarea anticipata a cererilor cunoscand granulele care vor fi accesate - practic imposibil in sistemele tranzactionale;
• Prevenirea;
• Detectarea

pe baza de grafe.

Exemplu: Fie T₁ si T₂ - doua tranzactii. Primul a obtinut blocarea unei granule g₁ in punere la zi si asteapta deblocarea granulei g₂. Tranzactia T₂ a blocat granula g₂ si ar vrea sa consulte protejat g₁.

Se vor discuta 2 tipuri de grafe si anume graful de asteptare si cel de alocare utilizate pentru semnalarea si solutionarea interblocarii.

3. Graful de asteptare

G(T,Γ) - T - ansamblul tranzactiilor concurente T= partajand granulele g₁, g₂, ., g_m si Γ relatia "asteapta" definit prin T_p "asteapta" T_q T_p astepta blocarea unei granule g_i care a fost blocata de T_q.

T. Situatia de interblocare are loc graful de asteptare are un ciclu.

Reluand exemplul anterior, teorema de mai sus se aplica astfel:

Toate tranzactiile situate intr-un ciclu sunt in interblocare; in plus o tranzactie care asteapta o alta tranzactie care este in interblocaj intra si el intr-un interblocaj indirect:

Este interesant de stabilit relatia dintre graful de asteptare si cel de precedenta.

Daca o tranzactie T_i asteapta o tranzactie T_j, → T_j, blocheaza o granul g inainte de executarea lui T_i intr-un mod incompatibil. Deci operatia pentru care T_j, blocheaza granula g, se executa inaintea operatiei din T_i, → cele doua operatii sunt incompatibile si nepermutabile. Astfel, T_j precede pe T_i. → asteptarea implica precedenta, dar nu si invers. Daca in graful de asteptare se inverseaza arcele rezulta un subgraf din cel de precedenta.

5. Graful de alocare

Este format din doua multimi de varfuri:

Multimea T de tranzactii;

G de granule.

Un arc care leaga granula G_i de tranzactia T_p daca T_p a cerut si n-a obtinut alocarea granulei; arcul este valuat cu modul de operatie cerut.

T. Conditia necesara de existenta a unui interblocaj este existenta unui circuit in graful de alocare. In general conditia nu este suficienta. Se poate demonstra ca pentru suficienta trebuie ca nodurile de citire si scriere sa fie distincte. Situatia de interblocaj se determina in cadrul sistemelor clasice prin determinarea circuitelor din graful de alocare.

In general nu exista un raport direct intre graful de precedenta si cel de alocare. Daca insa singurele moduri existente sunt cel de citire si scriere, existenta unui circuit in graful de alocare este echivalent cu interblocarea si deci cu un circuit in graful de asteptare. In aceasta situatie existenta unui circuit in graful de alocare este echivalent cu existenta interblocajului.

6. Prevenirea interblocarii

Prevenirea interblocarii consta in eliminarea uneia dintre conditiile care duc la interblocare. Exista doua metode:

• preordonarea resurselor (granulelor);
• preordonarea tranzactiilor.

Prima metoda - dificil de pus in practica deoarece intr-o BD - un numar mare de granule.

A doua metoda - cunoscuta sub denumirea de DIE-WAIT / WOUND-WAIT. In cele metode se folosesc stampile pentru preordonarea tranzactiilor.

Abordarea DIE-WAIT: daca T_i cere blocarea unei granule care este blocata de T_j intr-un mod incompatibil, T_i asteapta T_j, daca i<j, adica tranzactia mai veche asteapta una mai noua → T_i    "moare" adica este suspendata. In felul acesta o tranzactie nu poate astepta decat una mai noua, deci nu putem avea circuite in graful de asteptare. Daca o tranzactie "moare", ea va fi reluata cu aceeasi stampila mai tarziu, si va deveni cea mai veche tranzactie activa, deci nu va muri definitiv.

Abordarea WOUND-WAIT este simetrica. Daca T_i cere blocarea unei granule care este blocata de T_j intr-un mod incompatibil, T_i asteapta T_j numai daca i>j, adica tranzactia T_i provoaca suspendarea lui T_j daca i<j, adica o tranzactie mai veche "omoara" tranzactia mai noua. In acest mod o tranzactie poate astepta numai dupa tranzactii mai vechi si deci nu pot apare circuite in graful de asteptare.

7. Detectarea interblocajelor

Se bazeaza pe algoritmii de detectare a ciclurilor care apar in grafele de asteptare sau de alocare. Algoritmul in esenta se bazeaza pe testarea faptului ca graful este fara cicluri si eliminarea succesiva a unor varfuri "libere".

Un varf din graful de asteptare este considerat "liber" daca tranzactia aferenta lui nu asteapta blocarea nici unei granule. Fie deci N(k) numarul granulelor pe care tranzactia T_k asteapta sa le blocheze. O prima reducere se obtine eliminand varfurile "libere", pentru care N(k)=0. Problema este deci de a recalcula valorile N(k) dupa fiecare reducere pentru a vedea daca se poate realiza reducerea urmatoare. Aceasta se realizeaza prin enumerarea cererile care pot fi satisfacute dupa fiecare reducere scazand N(k) de fiecare data cand se ia in considerare o cerere a tranzactiei T_k. Aplicarea metodei presupune 2 precautii:

• marcarea cererilor luate in calcul pentru a le marca de doua ori;
• dispunerea de o metoda de testare permanenta a faptului ca o cerere poate fi satisfacuta tinand cont de blocarile tranzactiilor care n-au fost inca eliminate din graful de asteptare.

Fie deci o procedura booleana SLOCK(g_i,Q,k) care permite testarea faptului ca cererea Q a tranzactiei    T_k, pe granula g_i poate fi satisfacuta tinand cont de starea de alocare a granulelor la tranzactiile prezente in graful de asteptare. Procedura raspunde cu True daca este posibila alocarea si False altfel.

BOOLEAN FUNCTION DETECTOR (T,N)

Begin

T= */

R = */

For g_i din R

Do while cererea Q a lui T_k care asteapta g_i este nemarcata

If SLOCK(g_i,Q,k)= True Then

Marcheaza Q;

N(k)=N(k)-1;

If N(k)=0 Then

Elimina T_k din T

Adauga granulele blocate de T_k la R

EndIf

EndIf

EndDo

EndFor

If T= Φ

Then

DETECTOR=False;

Else

DETECTOR=True;

EndIf

EndDETECTOR.

La detectarea unei situatii de interblocaj, se pune problema reciclarii unei tranzactii in asa fel ca sa se rupa ciclul din graf. Algoritmul anterior furnizeaza lista tranzactiilor in blocaj → se selecteaza o tranzactie din lista.. Nu orice reciclare este rationala.

Solutia problemei este reciclarea tranzactiei care blocheaza cel mai mare numar de alte tranzactii (in exemplu T₂ ).

Exista metode de ameliorare a algoritmilor de detectare si suspendare. De exemplu, algoritmul de detectare si suspendare sa fie lansat numai daca o tranzactie asteapta blocarea de un anumit timp.