Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Algoritmul de blocare in doua faze

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Recursivitate - Recursivitate in cascada
Arbori asociati expresiilor aritmetice
Liste - Arbori
SYSAMO-SISTEM EXPERT PENTRU AMORTIZAREA IMOBILIZARILOR CORPORALE
Sisteme de numeratie utilizate in tehnologia digitala
Liste inlantuite - Inserarea unui nod intr-o lista simplu inlantuita circulara
Utilizarea teoriei NP-completitudinii in abordarea algoritmilor euristici
Tehnici de programare
Analiza complexitatii algoritmilor
Parcurgerea grafurilor in adancime

Agenda

  1. Algoritmul de blocare in doua faze

1.1.      Principii de baza



1.2.      Protocolul de blocare

1.3.      Algoritmi de blocare

1.4.      Blocarea in 2 faze

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

  1. Algoritmul de blocare in doua faze

1.1.            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 incorectetrecand 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=(cij)

cucij=1 daca operatiile sunt compatibile si cij=0 daca nu. Compatibilitatile se definesc prin:

C =

sau DBTG:

1.2.            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 inceputulunei 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 Ti , a unui vector de biti:

A(g,i)’ = [a1, a2,…, ae]

cu aj=1 daca modul Mj este in curs de executie pentru tranzactia Ti , 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’ = [m1, m2,…, me]

unde mj = 1 daca modul Mj 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 Tp 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 Tp → 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 Tp;

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 Tq;

EndIf

EndDo

EndUNLOCK.

Unde M’ este modul de operare cerut de tranzactia curenta Tq.

1.3.            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.

  1. 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 T1 siT2 – doua tranzactii. Primul a obtinut blocarea unei granule g1 in punere la zi si asteapta deblocarea granulei g2. Tranzactia T2 a blocat granula g2 si ar vrea sa consulte protejat g1.

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

  1. Graful de asteptare

 

G(T,Γ) – T – ansamblul tranzactiilor concurente T= partajand granuleleg1, g2, …, gm si Γ relatia „asteapta” definit prin Tp „asteapta” Tq ó Tp asteptablocarea unei granule gi care a fost blocata de Tq.

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.

  1. Grafe de precedenta (discutat in cursul anterior)

Precedenta poate fi definita in orice executie fara operatii simultane, in urma separarii operatiilor compatibile.

D. Precedenta S – executie fara operatii simultane. Ti precede Tj (se noteaza cu Ti < Tj) ó exista doua operatii nepermutabile Oi si Oj ca Oi din Ti precede peOj din Tj.




Pornind de la notiunea de precedenta se poate construi un graf care sa caracterizeze tranzactiile dintr-o executie.

Graful de precedentavarfuri = tranzactii & exista un arc intre Ti si Tj ó Ti precede Tj (adica Ti < Tj).

T. O conditie suficienta ca o executie sa fie serializabila este ca graful de precedenta – fara cicluri.

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

  1. Graful de alocare

 

Este format din doua multimi de varfuri:

·         Multimea T de tranzactii;

·         G de granule.

Un arc care leaga granula Gi de tranzactia Tp ó daca Tp 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 interblocareasi deci cu un circuit in graful de asteptare. In aceasta situatie existenta unui circuit in graful de alocare este echivalent cu existenta interblocajului.

  1. 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 Ti cere blocarea unei granule care este blocata de Tj intr-un mod incompatibil, Ti asteapta Tj, daca i<j, adica tranzactia mai veche asteapta una mai noua → Ti„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 Ti cere blocarea unei granule care este blocata de Tj intr-un mod incompatibil, Ti asteapta Tj numai daca i>j, adica tranzactia Ti provoaca suspendarea lui Tj 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.

  1. 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 tranzactiaTk 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 Tk. 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(gi,Q,k) care permite testarea faptului ca cererea Q a tranzactieiTk, pe granula gi 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 gi din R

Do while cererea Q a lui Tk care asteapta gieste nemarcata

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

Marcheaza Q;

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

If N(k)=0 Then

Elimina Tk din T

Adauga granulele blocate de Tk 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 T2 ).

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.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1340
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site