Pagina documente » Informatica, Matematica » Sisteme distribuite. Modelarea sistemelor distribuite

Cuprins

lucrare-licenta-sisteme-distribuite.-modelarea-sistemelor-distribuite
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-sisteme-distribuite.-modelarea-sistemelor-distribuite


Extras din document

CUPRINS
INTRODUCERE
CAPITOLUL 1. CONCEPTUL DE TIMP
i1.1. Introducere
i1.2. Modelarea sistemelor distribuite
CAPITOLUL 2. EXCLUDEREA MUTUALA
i2.1. Problematica
i 2.2. Algoritmul lui Lamport
i2.3. Algoritmul lui Ricart si Agrawala
i2.4. Algoritmul centralizat
CAPITOLUL 3. STARE GLOBALA
i3.1. Taieturi consistente
i3.2. Instatanee globale ale proceselor
i3.3. Instantanee globale ale proceselor si canalele
CAPITOLUL 4. PREDICATE GLOBALE
i4.1. Problematica
i4.2. Predicate liniare
CAPITOLUL 5. PREDICATE GLOBALE CONJUNCTIVE
i5.1. Predicate conjunctive slabe
i5.2. Algoritm centralizat pentru WCP bazat pe vectori ceas
i5.3. Algoritm centralizat pentru WCP bazat pe dependenta directa
i5.4 Algoritm distribuit pentru WCP bazat pe
vectori ceas
i5.5. Un algoritm centralizat pentru predicate conjunctive generalizate
i5.6. Un ceas vector bogat si algoritmul de detectie GCP distribuit
CAPITOLUL 6. PREDICATE GLOBALE RELATIONALE
i6.1 Predicate relationale cu doua variabile intregi
i6.2 Predicate relationale cu N variabile booleene
i6.3 Predicate pentru sume maginite
CAPITOLUL 7. PREDICATE GLOBALE
i7.1 Secvente globale
i7.2 Logica predicatelor globale
i7.3 Predicate conjunctive tari
CAPITOLUL 8. PREDICATE ALE FLUXULUI DE CONTROL
i8.1 Introducere
i8.1 Logica LRDAG
i8.3 Exemple
i8.4 Algoritmul descentralizat pentru detectie
CAPITOLUL 9. RELATII DE ORDINE
i 9.1 Relatii de ordine intre mesaje
i9.2 Ordinea FIFO a mesajelor
i9.3 Odinea cauzala a mesajelor
i9.5 Ordonarea sincrona a mesajelor
CAPITOLUL 10. CALCULUL
i10.1. Functii globale
i 10.2 Calculari repetate
CONCLUZII

Alte date

?Introducere

Evolutia sistemelor de operare moderne este strans legata de introducerea unor modele si concepte noi, menite sa asigure o cat mai buna servire a utilizatorilor si ocupare a resurselor, concomitent cu cresterea sigurantei de functionare a sistemului.

Pentru sistemele de calcul in prezent se cunosc doua cai de crestere a vitezei de calcul : prin cresterea vitezei procesorului sau prin cresterea numarului de procesoare.

Un sistem concurent format din procesoare care lucreaza in maniera “lock – step” se numeste sistem sincron. Un sistem concurent in care procesoarele sunt slab cuplate lucrand independent una de cealalta se numeste sistem asincron. Sistemele asincrone se pot de asemenea departaja in sisteme bazate pe divizarea memoriei si sisteme bazate pe mesaje. Vom numi sistemele bazate pe divizarea memoriei: sisteme paralele. Aceste sisteme realizeaza comunicarea intre procesoare printr-o zona comuna de memorie. Sistemele concurente care constau din mai multe calculatoare conectate printr-o retea se numesc sisteme distribuite.

Vom preciza cateva dintre avantajele si dezavantajele pe care le ofera sistemele distribuite comparativ cu sistemele paralele.

Avantaje :

- Divizarea resurselor : de exemplu un procesor poate fi partajat de mai multe aplicatii.

- Divizarea datelor : sistemele de baze de date distribuite se definesc ca o colectie de baze de date corelate logic, fiecare baza fiind asociata unui nod al retelei, impreuna cu un mecanism de acces care face aceasta colectie transparenta pentru utilizator. Sistemele distribuite au un comportament similar.

- Structura geografica: unele aplicatii sunt in sine distribuite geografic.

- Simplitate logica : programele distribuite sunt mult mai simple.

- Fiabilitate : defectarea unui calculator nu afecteaza hotarator sistemul global.

- Modularitatea : destul de usor pot fi adaugate sau sterse noi procesoare.

- Costuri scazute: ratiunile economice nu pot fi neglijate.

Dezavantaje:

- Comunicatii greoaie : in special in cazul in care un procesor trebuie sa transmita o valoare tuturor celorlalte procesoare.

- Sincronizare greoaie : se folosesc mesajele.

Capitolul 1. Conceptul de timp

§1.1. Introducere

O utilizare importanta a conceptului de timp este aceea de ordonare a evenimentelor. Vom spune ca evenimentul ? apare inaintea evenimentului ? daca momentul fizic in care ? are loc, t?, este mai mic decat t?, momentul in care ? se produce. Aceste cereri de acces, ordonate, sunt utilizate la niste mecanisme de ceas care pot inregistra t? si t?.

Multe aplicatii utilizeaza relatii de cauza si efect. Observam ca daca e este cauza lui f, atunci e trebuie sa apara inaintea lui f. Deci, relatia de precedenta cauzala este o submultime a relatiei de “aparitie inainte”. Vom construi mecanisme menite sa furnizeze informatii despre relatia cauzala.

Precedenta cauzala este o relatie mult mai uzitata decat relatia de “apare inainte”. O ratiune importanta este ca ne intereseaza de regula corectitudinea distribuirii programului pe procesoare. Aceasta implica ca daca f apare dupa e intr-o executie, atunci in afara de e cauzeaza f, f apare posibil inainte de e in diferite executii. Astfel relatia de precedenta cauzala este independenta de viteza de executie, in timp ce relatia de “aparitie inainte” nu. Mentionam ca vom folosi un singur ceas care sa furnizeze ordinea evenimentelor.

§1.2. Modelarea sistemelor distribuite

Vom numi proces un program secvential in curs de executare, drept urmare, la fiecare moment de timp este executata cel mult o instructiune a sa. Un proces include, pe langa codul programului, o stiva continand date temporare (parametrii ai procedurilor, adrese de revenire, variabile locale sau temporare) si o sectiune de date, continand variabile globale. Subliniem ca programul in sine nu este un proces: un program este o entitate pasiva (de exemplu continutul unui fisier de pe disc), in timp ce procesul este o entitate activa, prevazuta cu un indicator care specifica urmatoarea instructiune de executat. Doua procese asociate aceluiasi program constituie doua fire de executare distincte.

Vom numi program concurent un program care creeaza mai multe procese care se executa intr-un paralelism abstract, adica nu neaparat pe procesoare distincte. În permanenta trebuie insa gandit ca si cand fiecarui proces ii este asociat in mod univoc un procesor fizic; desigur ca si implementarea trebuie gandita astfel incat sa permita acest lucru.

Aproape intotdeauna, executarea concurenta a proceselor impune o anumita cooperare intre ele, deci sunt necesare anumite mecanisme care sa asigure comunicarea si sincronizarea intre procese. Atentia principala este indreptata deci asupra modalitatilor in care pot fi realizate interactiunile dorite si mai putin asupra a ceea ce realizeaza programele secventiale in parte.

Vom considera un sistem “message – passing” slab cuplat fara memorie partajata sau ceas partajat. Un program distribuit consta dintr-o multime de n procese, notata {P1, … , Pn} ce comunica intre ele numai via mesaje asincrone. Nu vom presupune nimic despre ordinea sau corectitudinea mesajelor.

La un nivel foarte abstract, executia unui sistem distribuit poate fi definita ca o multime de evenimente. Leslie Lamport a fost primul care a recunoscut importanta relatiei de ordine dintre evenimente intr-un sistem distribuit. El a postulat ca aceasta relatie, pe care o numeste “se intampla inainte”, este ireflexibila si tranzitiva. Vom numi aceasta relatie de precedenta cauzala.

Ne preocupa o singura rulare r a programului distribuit. Fiecare proces Pi in aceasta rulare genereaza executia si 0,ei 0, si 1,ei 1, … , ei l-1,si l care este o secventa finita de stari locale si evenimente in procesul Pi. Starea corespunde valorilor tuturor variabilelor procesului. Multimea variabilelor include program counter-ul. Astfel, cu exceptia nedeterminismului intern, evenimentul ce urmeaza a se executa este complet determinat de stare si de mesajul receptionat.

O rulare r este un vector de evolutii cu r[i] evolutia procesului Pi. Vom defini relatia de precedenta locala, notata cu Acum, relatia de precedenta cauzala, notata ?, poate fi definita ca inchiderea tranzitiva a uniunii S?t doar daca 1. (s 2. ?n: (S~~?n) AND (u?t)

În terminologia diagramei timp – proces, se intelege ca exista un domeniu de la starea s la starea t. Intuitiv, relatia de precedenta cauzala este o ordine partiala peste multimea de stari locale.

Vom spune ca s si t sunt concurente si notam s||t daca avem: NOT(s?t) AND NOT(t?s)

Fie Si secventa de stari locale din Pi si . Atunci o executie a unui program distribuit ce consta din procesele P1, …, PN poate fi modelata cu triplul (S1,…,SN,~~?). Vom numi structura deposet (multime partial ordonata decompozata), furnizand (S,?), o ordine partiala ce satisface urmatoarele doua conditii naturale : prima, ca nu exista nici un mesaj de primit (imediat) dupa starea initiala sau trimis dupa starea finala in orice secventa Si, a doua : exista cel mult un mesaj de trimis sau primit intre oricare doua stari consecutive. Formalizand definim starile initiala si finala. Init(i):= minSi respectiv Final(i):= max Si. Vom utiliza Init(s) sau Final(s) pentru a nota ca s este stare initiala sau stare finala. Deci suntem in masura sa formulam urmatoarea:

Definitia 1.1

Un deposet este un triplu (S1, … , SN, ~~?) astfel incat (S,?) este o ordine partiala ireflexiva care satisface :

(D1) ?i: NOT(?u : u~~?Init(i))

(D2) ?i : NOT(?u: Final(i) ~~?u)

(D3) SVom utiliza deposet-ul ca model formal al executiei programelor distribuite.

Ne propunem sa specificam si sa verificam programe, descriind o metoda bazata pe structura deposet. Pasii metodei sunt :

1. Programul este specificat utilizand relatiile S2. Proprietatiile dorite ale programului sunt specificate utilizand ?, -/? si alte astfel de relatii. Este important sa notam conceptele de timp, conceptul de timp global si de stare globala sunt evitate in aceasta abordare, orice variabila are un unic inteles intr-o stare locala. Astfel, s.v reprezinta valoarea variabilei v in starea s.

3. Proprietatile dorite sunt deduse utilizand proprietati ale programului.

Pentru orice pereche de stari consecutive, s