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


Grafe de precedenta - Algoritmul ordonarii

algoritmi

+ Font mai mare | - Font mai mic






DOCUMENTE SIMILARE

Trimite pe Messenger
Evaluarea corectitudinii algoritmilor
SISTEME EXPERT - Teoria si dezvoltarea sistemelor expert
Programare liniara si intreaga - Linear and Integer Programming
Tipuri de limbaje de programare
ATESTAT – ALGORITMI
PROIECT ASDN - Dispozitiv de comanda pentru doua lifturi alaturate
Algoritmi - Probleme laborator
Problema liniilor si suprafetelor ascunse in grafica 3D. Algoritmul PAINTER
Metoda „programarii dinamice”
Metoda Greedy - Aplicatii

 

Agenda

1.      Grafe de precedenta


2.      Algoritmul ordonarii initiale - Stampilele tranzactiilor (stamplie temporale)

3.      Algoritmul ordonarii totale

4.      Algoritmul de ordonare partiala

5.      Algoritmul de ordonare partiala cu mai multe versiuni

 

  1. Grafe de precedenta

 

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:

(1)    READ (Pagina)

(2)    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.


  1. Algoritmul ordonarii initiale - Stampilele tranzactiilor (stamplie temporale)

 

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:

  1. spatiu poate fi semnificativ, de exemplu (cativa octeti)/pagina;
  2. modificarea unei stampile, de exemplu intr-o operatie de citire implica o operatie de I/E auxiliara.

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:

  • controlerul cauta identificatorul granulei in tabel;
  • daca l-a gasit → este egala cu stampila respectiva;
  • daca nu, valoarea m (a ultimei stampile eliminate) este o margine a stampilelor.

  1. Algoritmul ordonarii totale

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

  • In primul caz, Ti va fi relansat cu o stampila i>j pentru a nu se crea un nou conflict. Este posibil ca Ti sa intre in conflict cu o alta tranzactie Tj’ si sa fie din nou suspendata; procesul poate continua la infinit. Pentru a evita se poate asocia o stampila superioara tuturor celor din tabel, dar se pot crea noi conflicte.
  • In al doilea caz,  Tj poate fi relansat cu aceeasi stampila. Intr-adevar o stampila mai mica, mai veche, devine prioritara si deci nu se pune problema relansarii la infinit a tranzactiilor. Metoda de rezolvare: relansarea lui Tj necesita urmatoarele operatii:
    • restaurarea versiunilor precedente precum si stampilele granulelor accesate;
    •  asigurarea noului control in functie de stampilele tranzactiilor; daca ordinea nu este respectata trebuie reluata tranzactia care a accesat granula inainte de Tj.

  1. Algoritmul de ordonare partiala

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

  1. Algoritmul de ordonare partiala cu mai multe versiuni

Ordonarea partiala – ameliorata prin utilizarea mai multor granule. Pentru fiecare granula g sistemul intretine:

  • un ansamblu de stampile de scriere cu valorile asociate , fiecare dintre acesta corespunzand unei versiuni i;
  • o multime de stampile de citire

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

5              7

 

8              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

5              6

 

6                 7           

 

8              8

 

A doua versiune posibila este anularea lui T6 si reluarea cu o stampila superioara 10:

      WW        RR

      WW        RR

   WW        RR

      WW        RR

5              7

 

8                8           

 

10           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:

  • 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 de 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.

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:

  • 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 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

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1268
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