| CATEGORII DOCUMENTE |
Agenda
Grafe de precedenta
Algoritmul ordonarii initiale - Stampilele tranzactiilor (stamplie temporale)
Algoritmul ordonarii totale
Algoritmul de ordonare partiala
Algoritmul de ordonare partiala cu mai multe versiuni
Precedenta poate fi definita in orice executie fara operatii simultane, de exemplu in urma separarii operatiilor compatibile.
D. Precedenta - S - executie fara operatii simultane. Ti precede Tj (notat cu Ti < Tj) exista doua operatii nepermutabile Oi si Oj ca Oi din Ti precede pe Oj din Tj.
Notiunea de precedenta → graf de precedenta.
Graful de precedenta - varfuri = 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.
Exemplu: Pentru exemplul din cursul 9:
T1: A+1 → A
T2: A * 2 → A
T1: B+1 → B
T2: B * 2 → B
Graf fara circuit pentru tranzactii serializabile.
Daca luam exemplul:
T1: A+1 → A
T2: A*2 → A
T2: B * 2 → B
T1: B +1 → B
Nu este serializabil si graful de precedenta este:
are ciclu.
Caz particular: granula = pagina. Operatii coerente pe pagina:
READ (Pagina)
WRITE (Pagina)
Daca - granule, operatiile de baza - pentru construirea altor operatii, sunt READ(granula) si WRITE(granula) → pentru evitarea conflictelor sistemul tranzactional trebuie sa asigure separabilitata celor 2 operatii de baza - prin operatii de sincronizare de tip semafor care permit excluderea executiei simultane a operatiilor READ/WRITE pe aceeasi granula.
In sistemele practice, se pot executa toate separarile si apoi permutarile pe granule diferite. Anumite operatii pe aceeasi granula sunt nepermutabile:
(Ti - READ g) (Tj - WRITE g) nu sunt permutabile deoarece Ti citeste o granula inainte ca Tj s-o scrie si deci Ti< Tj .
(Ti - WRITE g) (Tj - READ g) nu sunt permutabile deoarece Ti scrie o granula inainte ca Tj s-o citeasca si deci Ti< Tj.
(Ti - WRITE g) (Tj - WRITE g) nu sunt permutabile deoarece Ti scrie o granula inainte ca Tj s-o scrie si deci Ti< Tj.
→ trebuie algoritmi de control a accesului concurent - previna precedentele READ/WRITE, WRITE/READ, WRITE/WRITE.
Prima metoda - impiedicarea executiilor neserializabile prin ordonare la lansare in executie & verificarea executiei conflictuale pe aceeasi granula se efectueaza intr-o ordine prededfinita → fiecare tranzactie primeste o referinta unica - stampila a tranzactiei, care permite determinarea ordinii alese.
Stampila tranzactiei (Transaction timestamp) - Valoare numerica asociata unei tranzactii si care permite ordonarea acesteia in raport cu alte tranzactii.
In sistemele centralizate stampilele pot fi generate automat de calculator - mai dificil pentru sistemele distribuite.
Stampilele pe granule - Pentru a se asigura ca tranzactiile opereaza pe granule in ordinea stabilita se memoreaza ultima stampila de tranzactie care a operat pe granula →
D. Stampila de granula (Granule timestamp) - valoare numerica ce retine stampila ultimei tranzactii care a operat pe ea.
Pentru o mai buna distinctie intre operatiile efectuate se introduc: stampila de citire (stampila ultimei tranzactii care a efectuat operatia READ pe granula) si stampila de scriere (stampila ultimei tranzactii care a efectuat operatia WRITE pe granula).
Gestiunea stampilelor de control a granulelor, pentru asigurarea controlului concurent, se poate realiza prin rezervarea unui spatiu pentru stampila in memoria auxiliara → 2 inconveniente:
O metoda de evitare este generarea tabelelor de stampile in memorie si eliminarea eventual a celor vechi in cazul umplerii tabelei (Bernstein) - observatie - trebuie retinute numai stampilele tranzactiilor care se executa simultan cu tranzactia in curs - conflicte pot apare numai intre tranzactii concurente → stampilele pot fi memorate in MO in tabele de dimensiune limitata. Fiecare intrare in tabel contine: identificatorul granulei + stampila; se mai adauga o intrare cu valoarea m a ultimei stampile epurate din tabela.
Controlul se executa dupa un algoritm de tipul:
Consta in verificarea faptului ca accesul tranzactiilor la granule se realizeaza in ordinea lansarii si este detectata prin stampile. Daca 2 tranzactii Ti cu stampila i si Tj cu stampila j cu i<j opereaza pe aceeasi granula, controlerul care verifica accesul la granula verifica faptul ca Ti precede Tj. In caz contrar va suspenda executia uneia dintre tranzactii.
Dezavantaj: acest algoritm nu face distinctie intre operatii de citire/scriere si deci suspenda si citiri (READ/RREAD) care nu sunt conflictuale.
Avantaj: nu necesita decat o stampila/granula.
Pseudocod:
Procedure READ (Ti,g); /* g - granula accesata de Ti */
If (E(g) ≤ i) Then /* E(g) - stampila granulei g */
Executa citirea;
E(g) := i;
Else
ABORT; /* suspenda tranzactiile */
EndIf
EndREAD.
Procedure WRITE (Ti,g); /* g - granula accesata de Ti */
If (E(g) ≤ i) Then /* E(g) - stampila granulei g */
Executa scrierea;
E(g) := i;
Else
ABORT; /* suspenda tranzactiile */
EndIf
EndWRITE.
Problema relansarii se pune in functie de faptul ca a fost suspendata tranzactia care a cerut operatia (Ti) sau tranzactia care a efectuat operatia conflictuala (Tj).
Ordonantarea totala ordoneaza toate operatiile. In realitate trebuie ordonate numai cele nepermutabile: READ/WRITE, WRITE/READ, WRITE/ WRITE → numai acestea trebuie verificate.
La fiecare granula se asociaza 2 stampile R si W, adica stampila tranzactiei cele mai noi care a executat citirea, respectiv scrierea pe granula. La READ se verifica corectitudinea s-a fata de WRITE deci ultima stampila W. La WRITE se verifica corectitudinea fata de READ si WRITE.
Procedure READ (Ti,g); /* g - granula accesata de Ti */
If (W(g) ≤ i) Then
Executa citirea;
R(g) := MAX (R(g),i);
Else
ABORT; /* suspenda tranzactiile */
EndIf
EndREAD.
Procedure WRITE (Ti,g); /* g - granula accesata de Ti */
If ((R(g) ≤ i) AND (W(g) ≤ i)) Then
Executa scrierea;
W(g) := i;
Else
ABORT; /* suspenda tranzactiile */
EndIf
EndWRITE.
Algoritmul de ordonantare partiala
Trebuie observat ca algoritmul de ordonarii partiale produce ABORTAREA inutila a scrierii pe o granula. Intre-adevar, daca i<W(g) si i≤R(g) trebuie doar ignorarea scrierii, deoarece este o scriere a unei informatii depasite. Aceasta se numeste "regula de scriere a lui Thomas":
Procedure WRITE (Ti,g); /* g - granula accesata de Ti */
If (R(g) ≤ i) Then
IF (W(g) ≤ i) Then
Executa scrierea;
W(g) := i;
EndIF
Else
ABORT; /* suspenda tranzactia */
EndIf
EndWRITE.
Algoritmul de ordonantare partiala cu regula de scriere a lui Thomas
Ordonarea partiala - ameliorata prin utilizarea mai multor granule. Pentru fiecare granula g sistemul intretine:
Se pot ordona citirile fata de scrieri fara a fi nevoie niciodata de reluarea unei tranzactii care citeste - suficient sa livreze tranzactiei Ti care cere citirea granulei g a versiunii granulei care are stampila de scriere imediat inferioara lui i. Astfel Ti va precede toate tranzactiile care doresc sa faca scrieri cu stampile mai mari decat i si va fi dupa cele inferioare → Ti va fi corect secventializat. Totul de petrece ca si cum Ti ar urma imediat dupa scrierea cu stampila imediat inferioara. Algoritmul de control a citirii cu ordonarea partiala multi-versiune este:
Procedure READ (Ti,g);
j:= numarul ultimei versiuni a lui g;
Do While WWj(g) >i
j:=j-1;
EndDo;
Executa citirea granulei g;
RRj(g) := MAX (RRj(g),i);
EndREAD;
Se poate forta de asemenea ordonarea scrierilor lui Ti inserand o versiune creata de Ti dupa stampila imediat inferioara, fie Vj(g). Daca in urma re-secventializarii scrierii, o tranzactie Tk (k>i) a citit o versiune Vj(g), atunci aceasta citire trebuie re-secventializata. Acest fapt nu este posibil decat daca Tk este suspendat. Pentru a evita suspendarea tranzactiilor terminate, se va prefera reluarea scrierii lui Ti cu o noua stampila i mai mare decat k.
Procedure WRITE (Ti, g);
j:= numarul ultimei versiuni a lui g;
Do While WWj(g)>i
j:=j-1;
EndDo;
If RRj(g)>i Then ABORT j;
Else
Executa scrierea inserand o versiune (j+1) a lui g;
WWj+1(g) :=i;
EndIf;
EndWRITE;
Modul de aplicare a algoritmului are 2 posibilitati de reluare.
Situatia tranzactiilor in conflict la momentul initial poate fi:
Versiunea 1 Versiunea 2 Versiunea 3
|
WW RR |
WW RR |
WW RR |
|
|
7 |
8
Exista deci 3 versiuni a granulei, create succesiv de tranzactiile 1,5 si 8. Versiunea 1 este citita de tranzactia 1, 2 de 7 si 3 de 8.
Presupunem ca tranzactia T6 vrea sa efectueze o scriere dupa ce a citit versiunea a 2-a a granulei create prin T5. j:=3 si se aplica algoritmul de la inceput WW3(g)=8>6. Se face j:=j-1 → j=2. WR2(g)=5<6. Se verifica acum daca RR2(g)=7>6 - da → suspenda T7 este anulat, scrie T6 si se reia T7 cu aceeasi stampila in noua versiune creata, are loc situatia:
|
WW RR |
WW RR |
WW RR |
WW RR |
|
|
6 |
7
8
A doua versiune posibila este anularea lui T6 si reluarea cu o stampila superioara 10:
|
WW RR |
WW RR |
WW RR |
WW RR |
|
|
|
7 |
|||
8
0
6. Algoritmul de blocare in doua faze
Principii de baza
Pana aici controlul 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. Deci, metoda consta in detectarea executiilor neserializabile si suspendarea tranzactiilor.
Strategia bazata pe blocare consta in 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 este 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)
cu cij=1 daca operatiile sunt compatibile si cij=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:
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:
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.
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 Mj este in curs e executie pentru tranzactia Ti , pe granula g si 0 daca nu.
Analog presupunem ca modurile de operare cerute de executarea unui LOCK(g.M) se definesc printr-un vector de biti:
M = [m1, m2,., me]
Notand cu:
- reuniunea 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
)
unde cu ' s-a notat transpusa vectorului.
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,p) = A(g,p) M';
Else "elimina (q,M1) din Q[g]";
"blocheaza tranzactia Tq;
EndIf
EndDo
EndUNLOCK.
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 n 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 serializabile.
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 si 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 scriere, 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 afectata a priori ca in cazul ordonarii initiale (totale sau partiale) ci de momentul in care se ajunge la blocarea maxima.
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:
Interblocarea este o problema de blocare dificil de rezolvat. Exista 3 modalitati de rezolvare:
pe baza de grafe.
Exemplu: Fie T1 si T2 - 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 dicuta 2 tipuri de grafe si anume graful de asteptare si cel de alocare utilizate pentru semnalarea si solutionarea interblocarii.
|
Politica de confidentialitate | Termeni si conditii de utilizare |
Vizualizari: 2944
Importanta: 
Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved
