Sisteme distribuite - cursuri

Cursul 1

Sisteme Distribuite

2Bibliografie recomandat Grigora D., Modele de calcul distribuit, Ed. Specturm, Iai, 1999. Muhl, G., Fiege L, Pietzuch P., Distributed event based systems,

Springer-Verlag Berlin Heidelberg, Germania, 2006 Pstravanu O. Sisteme cu evenimente discrete Tehnici calitative

bazate pe formalismul reelelor Petri, Ed. Matrix Rom, Bucureti, 1997. Pfister G., In search of clusters, Prentice Hall, 1995. Raynal, M. , Distributed Algorithms and Protocols, John Wiley &Sons

Ltd, 1988. Raynal, M., Helary,J.M., Syncronisation and Control of Distributed

Systems and Programs , John Wiley &Sons Ltd, 1988. Sloam, M., Kramer, J. "Distributed Systems and Computer Networks ",

Prentice Hall 1987. Tanenbaum A. S. Reele de calculatoare, Computer Press Agora, 1997. Tanenbaum A. S., Modern Operating Systems, Prentice Hall,

USA,1992. Tanembaumm A. S., "Distributed Systems", Prentice Hall 1993. Zaharia M. H., Fluxuri de producie n medii distribuite, Ed. F.C.

Renaterea Romn,Iai,2000.

Cresterea numarului de host-uri din Ianuarie 1994 pn n 2013

Evoluia principalelor clase de arhitecturi.S ca la r

S ecvent ia l P re fe tch

S u p rap u ne ri Inst r P a ra le lism fu nc t io na l

U nita t i fu nc t io na le P ip e linem u lt ip le

V ec to ria le V ec to ria leim p lic ite exp lic ite

M em o rie R eg ist ruca tre m em o rie c a t re reg is t ru

S IM D M IM D

P ro ceso a re A rii d e M u lt ica lcu la to a re M u lt ip ro ceso a re a so c ia t ive p ro ceso are

Modelul cu acces uniform la memorie

De obicei este cunoscut sub acronimul UMA (Uniform Memory Acces).

Structura specific este prezentat n figura

P1 . . . Pn

Interconectare sistem (bus , matrice, reea multistagiu .a.)

I/O SM1 . . . SMn

a. Cu memorii locale distribuiteb. Ierarhic cu clustere

Modelul cu acces neuniform la memorieDe obicei este referit ca NUMA (Non-Uniform Memory Acces) i are dou variante:1. NUMA cu memorii locale distribuite2. NUMA ierarhic

Modelul cu acces la memorie cache

n literatura de specialitate este denumit COMA(Cache Only Memory Acces) este prezentat n

Modelul sistemelor slab cuplate

Este cel mai general model arhitectonic

Multicalculatoare cu memorie distribuit

9Introducere Nivelul pn la care urc dependena de main,

propus de Li (mai jos)

10

Introducere

Apare ntrebarea "toate cele treidimensiuni de definire a unui sistemde calcul trebuie s fie distribuitepentru a putea declara un sistem cadistribuit" sau este una suficient.

La aceast ntrebare s-au ncercatmai multe rspunsuri, dintre careunul l reprezint modelul lui Enslow(1978)

11

Introducere Din acest punct de vedere o definiie mai

practic este cea prezentat de Sloam &Kramer i anume:

"Un sistem de calcul distribuit este acela ncare un numr de procesoare i zone destocare de date autonome suport procesrii / sau interaciuni cu bazele de date nscopul cooperrii comune pentru a obine unrezultat comun. Procesele coordoneazactivitile, schimb informaii prin intermediulunei reele de comunicaii".

12

Introducere Tanenbaum propune urmtoarea

definiie:

Un sistem este distribuit doar dacexistena nodurilor autonome estetransparent pentru utilizatorii sistemului se comport virtual ca un singurcalculator.

"You know you have a distributed system when the crash of a computer you've never heard of stops you from getting any work done."

(Leslie Lamport, Distribution email, May 28, 1987,

Cum il inteleg aftomatistii?...

Sisteme de calcul distribuit (Distributed Computing Systems) Sisteme folosite pentru realizare de task-uri ce necesita putere mare

de calcul

Sisteme distribuite de informatii (Distributed Information Systems)

Posibilitatea integrrii unor sisteme eterogene este unul din principalele aspecte n care

platformele de mesagerie joac un rol cheie. Un Message Oriented Middleware (MOM)

ofer abilitatea de procesare a cererilor n mod asincron,

20

GFS: Architecture (2)

Avantajele oferite de MOM sunt urmtoarele:

posibilitatea integrrii de componente eterogene, rulnd pe platforme diferite, ntr-un sistem informatic distribuit;

reducerea strangulrilor n sistem decuplarea aplicaiilor, prin interschimbul asincron de mesaje,

dac necesarul de prelucrare este mai ridicat pentru anumite componente, acestea pot, n mod dinamic, beneficia de multiple instane ale aceluiai proces;

Scalabilitatea

Hw

sw

22

AvantajeCosturi reduse S-a demonstrat economic c este mult mai ieftin s

se foloseasc mai multe sisteme de calcul larezolvarea unei probleme complexe, dect unsupercalculator.

Acesta are un cost foarte mare i este dedicat, ngeneral, numai unui flux continuu de probleme decalcul de foarte mari dimensiuni.

n aplicaiile de control industrial apare o mareeconomie de cablu prin plasarea procesorului lngsursa datelor, rezultatele putnd fi vehiculate serial.

23

AvantajeModularitate i simplitate a softului

Sistemele distribuite pot fi construite ntr-omanier foarte modularizat,unde fiecarecomponent permite interfaarea cu restulsistemului (celelalte componente) sau serviciifoarte bine definite.

Flexibilitate i extensibilitate

Modularitatea sistemului permite schimbareasau modificarea elementelor de calcul fr aderanja major operaiile n curs dedesfurare.

24

AvantajeFiabilitate i integritate

Sistemele distribuite au proprietatea de aputea continua operaiunile indiferent destarea unei pri a sistemului.

Folosirea mai multor noduri de calculpermite ca, n cazul defectrii sau blocriiunei resurse, sistemul s continueactivitatea resursele critice, n acest caz,pot avea control dublu sau triplu.

25

AvantajePerformana

Performana este n general definit ntermenii timpului de rspuns la un anumitgrad de ncrcare.

Timpul de rspuns poate fi sczut, nmod particular dac majoritateaprocesrii este fcut local.

26

DezavantajeLipsa cunotinelor despre starea global

n fluxul de control al unui algoritm centralizatdeciziile se pot lua n funcie de stareantregului sistem.

Chiar dac starea sistemului se poate deducedin valorile pe care le au mai multe variabile,aceasta poate fi determinat n mod corect,deoarece n procesul de inspectare a valorilorlor, nici una dintre variabile nu poate fimodificat de un alt proces.

27

DezavantajeLipsa unui timp global

Evenimentele care constituie executarea unuialgoritm centralizat formeaz o mulime totalordonat conform apariiei lor temporale.Relaia de ordonare temporal indus asupraevenimentelor care constituie execuia unuialgoritm distribuit nu este o relaie de ordinetotal.

Exist perechi de evenimente pentru care sepoate decide care dintre ele s-a produs primuli care al doilea, dar acest lucru nu estevalabil ntotdeauna.

28

DezavantajeNedeterminismul

Comportamentul unui programcentralizat poate fi descris n funcie dedatele de intrare.

Pentru un anumit set de date de intrare,comportamentul este identic.

Spre deosebire de aceasta,comportamentul unei aplicaii distribuiteeste de obicei nedeterminist.

29

Comunicaiile

Probleme specifice comunicaiilor

Din punct de vedere al comunicaiei un

sistem distribuit trebuie s se poat

realiza:

Un schimb sigur de informaii ntre

noduri; aceast proprietate este

asigurat prin ajungerea la destinaie a

mesajelor transmise, lipsa erorilor n

mesaje ca i a copiilor multiple.

Centralised versus Distributedcomputing Computing

Cursul 2

Model?

Modele?

2Model Modelul unui sistem trebuie s rspund

urmtoarelor ntrebri:

Care sunt principalele interaciuni dinsistem?

Cum interacioneaz acestea?

Care sunt caracteristicile care afecteazcomportamentul lor individual i global?

3Model

n cazul particular al modelrii sistemelorde calcul paralel i distribuit orice modeldin aceast categorie trebuie s includ:

Conceptul de proces combin activitateaacestuia cu protecia spaiului dememorie rezervat lui i are urmtoarelecaracteristici:

4Modelul ..

1. are propria stare care, de obicei,se refer la setul abstract de dateaflat n procesare de acesta.

2. n modelul cu transfer de mesaje

3. n modelul cu memorie comun

Un sistem distribuit este format din entiti (procese, procesoare, calculatoare) care comunic i care i modific starea ca urmare a producerii unui eveniment intern, sau a unei operaii de comunicaie - emisie (send), recepie (receive).

5

sistemului distribuit ca sistem cu tranziii

Sistemul distribuit parcurge lanul de configuraii 1, 2, 3, 4, 5, 6, 7,

6

n figura s-au trasat evoluiile n timp a dou procese, A i B, care aparin aceluiai sistem distribuit.

Ele sunt observabile din exterior, dar un proces nu poate s cunoasc starea sistemului.

Procesul A i schimb starea ca urmare a producerii unor evenimente, n secvena emisie, intern i, apoi, recepie.

Procesul B i modific starea ca urmare a producerii evenimentelor recepie, intern i emisie.

Copyright: [email protected], 2003 7

O configuraie a sistemului const din mulimea tuturor strilor proceselor componente i colecia mesajelor n tranzit. Astfel, pe figura , se poate observa c n configuraia a sistemului, exist un mesaj n tranzit, de la procesul A ctre procesul B. 8

Evoluia n pai discrei a unui sistem distribuit sugereaz adoptarea ca model a unui sistem cu tranziii.

Acesta este definit prin mulimea configuraiilor sistemului, mulimea configuraiilor iniiale, care este o submulime a mulimii configuraiilor i o relaie de tranziie binar, definit i cu valori pe mulimea configuraiilor.

9

La un sistem cu tranziii ordonarea evenimentelor se face pe baza relaiei de cauzalitate i nu a unui timp global, care, aa cum s-a precizat anterior, nu poate fi folosit din punct de vedere practic.

Aceasta nseamn c dac, n cadrul aceluiai proces, un eveniment se produce naintea altuia, se spune c l precede cauzal.

10


Model cand Din punct de vedere al modelului anterior

descris se observ c este perfect aplicabil,evident cu anumite diferenieri, att n cazulcalculului paralel ct i al celui distribuit.

Din punct de vedere al schimbului deinformaii ntre elementele de calcul (care potfi att hard ct i soft) exist dou clase demodele: cu schimb de mesaje i cu memoriecomun.

12

Model aplicaii Exist urmtoarele modele de organizare

a aplicaiilor distribuite:

1. aplicaii tip client-server:

2. aplicaii pe cluster:

3. aplicaii distribuite colaborative:

13

Model aplicaii

metacalculul:

Se observ c aceste categorii auaprut prin creterea gradat adistribuiei geografice, a numruluide utilizatori i a numrului deresurse implicate.

14

Model client server

Este cel mai utilizat.

Exist procese specializate

n timpul execuiei diferite procese pot fiatt client, ct i server; de exempluserverul de fiiere poate deveni clientpentru serverul care ofer timpul curent.

15

Model client server Activitile din timpul execuiei unei aplicaii

distribuite sunt asociate, de obicei, abstractizrii deproces i ele nu vor putea s existe dect ca priale aplicaiei.

Problema care se pune sub acest aspect poate fiprivit tot ca o problem de descompunere ianume:

Ce reprezint fiecare activitate (proces) ntr-oaplicaie distribuit i cum se servete aceasta dediferitele ei uniti (obiecte)?

Dou tipuri de scheme de baz sunt curent ntlniten organizarea activitilor din aplicaiile distribuite:scheme procedurale i scheme modulare.

16

Model client server - RPCSchemele procedurale - apel de procedur

la distan

Schema procedural este clasic i este ceamai rspndit n prezent pentru organizareaaplicaiilor.

Adoptarea unei organizri procedurale naplicaiile distribuite ridic ns o serie deaspecte noi, toate pornind de la faptul cdistribuirea face inerent cerina caprocesele s se poat propaga i ladistan, dincolo de graniele fizice ale uneisingure maini.

17

Model client server - RPC

Trebuie observat c interaciunile care au locntr-o organizare procedural a proceselorsunt interaciuni de tipul master-slave.

Cnd este programat o interaciune client-server, fiecare dintre procesele implicate,clientul i serverul, trebuie n esen stransmit fiecare cte o pereche de mesaje.

18

Model client server - RPC Din acest motiv apar complicaii referitoare la

realizarea transferului transparent la distan alargumentelor de tip pointer i la apelurile prinreferin. (Java why?)

Sub aspectul sincronizrii, RPC are printradiie un caracter sincron. Sunt posibile iforme mai generale de RPC, cum sunt RPCasincron i RPC de grup.

19

Model client server

Schema modular, transfer explicit demesaje

Schema modular sau cu activiti rezidenteprezint o analogie evident cu arhitecturadistribuit de baz, ceea ce permite o mareflexibilitate n descrierea interaciunilor dintreprocesele unei aplicaii.

Procesele au fiecare o memorie proprie icomunic ntre ele prin transfer explicit demesaje.

20

Model client server Constrngerile rezultate asupra structurii

obiectelor care servesc drept rezidenpentru procese sunt mai puternice dectschema procedural, aprnd problemespecifice de descompunere i control.

Cerinele de modularitate i de distribuire facn aa fel nct procesele gzduite pediferitele uniti ale aplicaiei s nu dispun demijloace implicite de comunicaie, astfel ceste definit i utilizat un mijloc neconvenionalde comunicaie, mesajul.

21

Model client server

Diferenierea modelelor de transfer demesaje poate fi fcut din perspectivediverse cum ar fi:

schema de desemnare utilizat pentruspecificarea sursei i a destinaiei;

momentul cnd se decide care sunt sursa idestinaia unui mesaj;

22

Model client server Cea mai simpl schem de desemnare este

desemnarea direct sau explicit: sursa idestinaia sunt specificate prin nume deprocese.

Schema este uor de implementat i deutilizat, constituind o bun cale pentruimplementarea algoritmilor de tip pipeline,deoarece fluxul informaiei este constant petoat durata execuiei programului distribuit.

23

Model client server

Desemnarea prin nume globale este deregul asociat conceptului de cutiepotal (mailbox) care permite maimultor procese s poat trimite mesajectre aceasta i, la rndul lor, mai multeprocese s recepioneze mesaje dinrespectiva zon.

24

Model client server

O a doua cale de difereniere aschemelor de transfer de mesaje estecea legat de momentul n care sedecide sursa i destinaia unui mesaj.

Dac sursa i destinaia se fixeaz nmomentul compilrii, se spune c serealizeaz o desemnare static acanalului logic.

25

Model client server Un alt aspect important, utilizat pentru

difereniere modelelor de transfer de mesaje,l constituie structura de comunicaie facilitatde model. Pot exista mai multe alternative:

structuri de tip unu la unu;

structuri de tip mai muli ctre unu;

structuri de tip mai muli ctre mai muli;

structuri de tip unu ctre mai muli.

26

Model client server Structurile de comunicaie mai muli ctre

unul sunt utile n special dac proceselecomunicante coopereaz n maniera client-server, mai muli clieni pot beneficia deserviciile unui singur server.

Structurile de tip unul ctre mai muli sunttipice pentru comunicaii de grup (multicast),n particular broadcast la nivelul aplicaiilordistribuite.

27

Model client server Un sistem client-server este realizat pe trei nivele,

cel al prezentrii, cel al aplicaiei i cel al accesuluila date.

Separarea fizic a celor trei nivele se numetepartiionarea aplicaiei. ntotdeauna nivelulprezentrii va fi implementat de ctre client.

mprirea celorlalte dou nivele ntre client i serverconduce la cinci stiluri client - server diferite:

Multilayer multitier - comments

Gestiunea

Resurselor

29

Alocarea resurselor n general, funcia de alocare a

resurselor sistemului nu estencredinat unui singur locator, ci estedistribuit ntre mai multe locatoare,situate pe elemente de prelucraredistribuit.

Pentru implementarea schemelor dealocare, sunt necesare informaii privindstarea resurselor existente n sistem.

30

Alocarea resurselor

Exist dou clase mari de soluii privindgestiunea reprezentrilor de stare decare au nevoie procesele dedicatealocrii de resurse.

Una dintre ele este meninerea unuicatalog unic.

n acest caz o reprezentare unic a striiresurselor este partajat ntre toateprocesele dedicate

31

Alocarea resurselor O a doua modalitate este distribuirea

catalogului strii.

Acesta poate fi distribuit n ntregime sauparial. n prima variant, catalogul estereplicat pe fiecare element de prelucrare,situaie n care este necesar meninereaconsistenei copiilor multiple ale cataloguluide stare.

n a doua variant, pe fiecare element deprelucrare este ntreinut un catalog al striiresurselor locale.

32

Alocarea resurselor singulare

Alocarea unei resurse singularelocalizat pe un element de prelucrare alsistemului poate fi fcut pentru a fiposibil un acces exclusiv sau concurent.

Accesul exclusiv la o resurs singularpoate fi implementat de un locator (numitserver), care este nsrcinat cugestiunea respectivei resurse.

33


Serverul S poate fi programat simplementeze orice strategie referitoarela satisfacerea cerinelor:

controlul drepturilor de acces,

tratarea cererilor ntr-o anumit ordine

etc.

Aceast strategie nu poate asigura nici oform de paralelism la accesare

34


Implementarea acestei scheme de alocare poate fi fcut n dou moduri:

cererile de la proceselesolicitante

cererile de acces

35

Alocarea resurselor multiple

Execuia unei aplicaii compus din maimulte procese ce pot fi executate nparalel, poate genera cereri de acces lao multitudine de resurse, posibillocalizate pe elemente de prelucraredistincte.

tranzactia

36


Cazul accesului la resurse multiple poatefi privit i din punct de vedere alconcurenei apare problema creriiproceselor concurente.

Crearea proceselor concurente serealizeaz prin detectarea secvenelordin program care sunt independente,unele fa de celelalte.

37


Relaia de ordine este indicat prindependena de date:

dependena de curs (flow dependence)

antidependen (antidependence)

dependen de ieire (outputdependence)

dependen I/E (I/O dependence)

O relaie de condiionare suplimentareste dictat de ordinea de execuie.


Alocarea resurselor multiple Fiind date dou procese, P1 i P2, cu datele

de intrare I1 , respectiv I2 i datele de ieireO1, respectiv O2, ele se pot executaconcurent dac sunt independente i nucreeaz rezultate confuze (condiiile luiBernstein):

I1 O2 = , I2 O1 = i O1 O2 =

Execuia concurent a celor dou proceseproduce aceleai rezultate, indiferent dacsunt executate secvenial, n orice ordine, saun paralel.

39

Alocarea resurselor multiple Printre resursele cele mai importante ale

sistemului cu prelucrare distribuit se numrprocesoarele.

Gestiunea lor adecvat este cheia obineriiunor performane corespunztoareobiectivelor urmrite de sistem.

O soluie ar fi prelucrarea arborescent,aceast metod nu este complet distribuit,dar funcioneaz bine n practic i este itolerant la erori.

40

Alocarea resurselor multiple Procesoarele executante se afl numai

pe ultimul nivel al arborelui pentru acrete tolerana la defecte: la defectareaun master mai exist alt ramur cu unmaster disponibil.

n vederea satisfacerii cererilor dealocare, fiecare procesor conductorntreine un catalog cu informaiile destare relativ la toate procesoarelepornind de la el n jos pe arbore.

41

Alocarea resurselor multiple Dac acesta constat c numrul de

procesoare subordonate este insuficientpentru realizarea calculelor, atunci el trimitecererea ctre procesorul superior lui.

Dac nici acolo nu sunt suficiente capaciti ladispoziie, cererea se va propaga pe arbore nsus pn la satisfacerea ei, din acel momentalocarea proceselor la procesoare devenindefectiv.

42


Alocarea se realizeaz conform unui algoritmde tip licitaie.

n momentul n care un server primetemesajul cerere, acesta rspunde cu un mesajce conine condiiile n care poate satisfacecererea (costul serviciului su), n funcie dencrcarea resursei gestionate de el.

Solicitantul alege oferta cea mai convenabili anun ofertantul sau ofertanii respectivi.

43

Problema excluziunii mutuale Este n specific sistemelor care folosesc zone de

memorie comun pentru a realiza comunicarea ntreprocese.

nainte de a accesa o zon de memorie comun unproces trebuie s aib asigurat att excluziuneamutual ct i coerena datelor.

Mono vs cluster

44

Abordarea centralizat O posibilitate este simularea metodelor

specifice unui sistem monoprocesor.

n acest caz se alege un proces ca fiindcoordonator.

Principiile de alegere a mainii gazd pentruacesta sunt destul de variate, totui o metoddestul de rspndit este plasarea lui pesistemul cu cea mai mare adres din reea.

n momentul apariiei unei noi cereri setesteaz dac aceasta este vid, caz n carerespectivul proces primete permisiuneafolosirii zonei.

45

Abordarea centralizat

n caz contrar cererea se insereaz n coad iar procesul este anunat. n acest caz procesul poate intra automat n ateptare sau i poate continua lucrul.

Dei abordarea centralizat sufer deproblema suprancrcrii la nivelul procesuluide control precum i de o rat sczut atoleranei la defecte deoarece toat aplicaiaeste blocat dac procesul conductor cade,ea prezint urmtoarele avantaje:

46

Abordarea distribuit Ricart i Agrawala 1981.

Metoda pornete de la premisaexistenei unei ordini totale a tuturorevenimentelor din sistem.

Cnd un proces dorete accesul ntr-oregiune critic el va crea un mesaj careva conine identificatorul propriu, numelezonei de acces precum i timpul la cares-a realizat respectiva cerere.

47

Abordarea distribuit Ricart i Agrawala

n cazul recepionrii unui astfel demesaj tratarea lui este realizat funciede regiunea critic cerut.

Dac procesul receptor nu acceseazmomentan respectiva zon atunci vatrimite un mesaj de validare.

n caz contrar cererea va fi introdusntr-o coad de ateptare.

48

Abordarea distribuit Ricart i Agrawala

La ieirea din zon acest proces va trimitetuturor un anun care va debloca cozile deateptare algoritmul relundu-se.

i acest algoritm este fr blocaje.

Dar este mult mai puin tolerant la defectedeoarece acum exist n puncte critice.Problema poate fi corectat cu preul dublriinumrului de mesaje.

Dac un proces nu este de acord el va trimiteaceast ntiinare ctre cel care a generatcererea.

49

Abordarea distribuit algoritm pe inel Datorit problemelor legate de asigurarea

unei ordini temporale s-au ncercat i alteabordri care s nu in cont de aceasta.

Pentru fiecare resurs critic se va asocia unpermis de acces unic.

Procesele care folosesc aceast resurs suntorganizate ntr-un inel.

Ordonarea proceselor poate fi realizat pebaza adresei mainii de origine.

50

Abordarea distribuit algoritm pe inel Dac are nevoie o va folosi i la terminare va

trimite mai departe permisul.

n caz contrar permisul va fi trimis imediat lavecinul din list.

Funcie de direcia de parcurgere a listeivecinul va fi cel din dreapta sau cel dinstnga.

Detectarea pierderii permisului este dificildeoarece nu este prevzut o cuanttemporal fix pentru folosirea respectiveiresurse critice.

Cursul 3

1

Intro Stocarea distribuit, uzual sub form de fiiere,

a devenit rapid important o dat cu succesul arhitecturilor de tip reea i staii de lucru.

Dac fiecare staie necesit spaiul propriu de stocare, atunci schimbul de date este minimal.

Oricum nu acesta este cazul ntr-un sistem distribuit.

2

O dat ce utilizatorilor le este permis conectarea la orice main i schimbul liber de fiiere i se ateapt ca mediul de lucru s nu fie alterat atunci modelele clasice de reele nu mai sunt viabile.

Soluiile pentru aceste probleme se afl nsistemele de stocare distribuite.

3

Caracteristici - Acces transparent

Ideal, un DFS ar trebui s apar clienilor ca pe un sistem convenional, centralizat, de fiiere.

Multiplicitatea i dispersia serverelor i a dispozitivelor de stocare ar trebui s fie transparent.

Asta nseamn c interfaa client a unui DFS nu artrebui s fac diferena ntre fiiere locale si remote.

4

Datele comuneUn spaiu de stocare distribuit trebuie s

satisfac un numr de cerine generale:

Este necesar asigurarea unei metode de a avea acces n comun la o zon de date ntre mai multe aplicaii.

De obicei aceasta se rezum la un acces comun la citire unde copiile primite de aplicaii sunt manipulate independent.

5

Transparena locaiei Localizarea fizic propriu zis a datei trebuie s

fie ascuns pentru programator aceasta neavnd o poziie neaprat stabil.

Este evident c aceast mobilitate trebuie s fie supus restriciilor implicite de securitate

Exist mai multe moduri de numire a schemelorDFS.

6

Controlul distribuit Trebuie ca s nu existe o structur unic de control

pentru respectivul spaiu.

Dac acest aspect nu pune probleme deosebite la structurile de dimensiuni mici i medii n cazul sistemelor mari, cum ar fi zone comune de stocare ntre corporaii diferite, poate deveni problematic.

De obicei controlul datelor se prefer a rmne separat peste o anumit dimensiune.

7

Securitatea Reelele sunt nesigure.

Chiar dac li se poate garanta integritatea n sisteme mici, sistemele mari care folosesc reele accesibile publicului sunt sensibile la atacuri.

Deci este necesar protecia datelor confideniale mpotriva accesului neautorizat i protecia sistemului mpotriva simulrii unui utilizator i main recunoscute de acesta

8

Stabilitate i fiabilitateUn astfel de sistem trebuie s fac fa cderilor

ce pot aprea la mainile din reea.

Cderile trebuiesc acceptate/tolerate fr ca datele s fie afectate.

De asemenea este de dorit ca problemele aprute s poat fi gestionate dinamic

9

Folosirea tehnicilor de cacheCererile de acces ale unui fiier remote sunt

realizate prin dou metode complementare.

Cu servicii remote, cererile de accesare suntlivrare serverului.

Serverul le acceseaz i rezultatul e trimisclientului.

10

Problema inconsistenei la nivelul memoriei poate apreaatunci cnd accesele la memorie ajung s apar n alt ordinedect cea specific execuiei programului

.

Modul n care este observat de ctre procesorcomportamentul memoriei comune ntr-un sistemmultiprocesor care implementeaz acest sistem, senumete model de memorie.

Specificaiile de proiectare ale unui astfel de model trebuies rspund la urmtoarele ntrebri fundamentale:

Comportament

Ambiguitati

general

Ordinea programului este ordinea n care apar accesele lamemorie n cazul execuiei unui singur proces n cazul ncare nu s-a realizat vreo operaie de control superior (nivelsistem de operare) asupra execuiei programului respectiv.

Dubois a definit n 1986 trei operaii primitive de memorie ce pot fi folosite pentru a putea defini modelele de consisten a memoriei:

Se consider a fi realizat o operaiune de citire de ctre procesul Pi, innd cont de procesul Pk, numai n momentul n care acesta ncearc s realizeze o scriere n aceeai zona iar rezultatul acestei scrieri nu afecteaz valoarea citit de Pi.

Se consider realizat o operaiune de scriere de ctre

procesul Pi, innd cont de Pk, numai n momentul n careo cerere de citire realizat de acesta, la aceeai locaie,ntoarce valoarea depus la scriere.

O citire se consider a fi valabil la nivel global dac este

realizat innd cont de toate procesele i dac scrierean acea zona a fost de asemenea realizat innd cont de

toate procesele.

A fost introdus de Goodman n 1992 i se refer lafaptul c operaiunile de scriere iniiate de fiecareprocesor respect ntotdeauna ordinea program.

Totui ordinea operaiilor de scriere iniiate de douprocesoare poate s nu respecte ordinea programului.

Cu alte cuvinte consistena la scriere este observat defiecare procesor dar ordinea citirilor de la fiecareprocesor nu este restricionat atta timp ct nuimplic alte procesoare.

1. nainte de a permite o citire, innd cont i de celelalteprocesoare, trebuie ca toate accesele de citire anterioare s fifost terminate.

2. nainte de a permite o scriere, innd cont i de celelalteprocesoare, trebuie ca toate accesele anterioare de citire sauscriere s fi fost terminate.

De fapt acest model permite ca operaiile de citire careurmeaz unei operaii de scriere s evite operaia de scriere.

Unul dintre cele mai lejere modele de memorie a fostpropus de Gharachorloo n 1990.

Acesta necesit ca accesele pentru sincronizare dintr-unprogram s fie identificate i clasificate ca rechiziionate(aquire - cum ar fi o operaiune de lock) sau eliberate(release - cum ar fi un-lock).

O operaie de rechiziionare este o operaie de citire carecapt accesul la un set de date n timp ce eliberarea esteo operaie de scriere care d o astfel de permisiune (deacces pentru citire la un set de date).

1. nainte de execuia unei operaiuni obinuitede citire sau scriere trebuie ca toate acceseleanterioare de tip rechiziionare s fi fost realizate.

2. nainte de execuia unei operaiuni de eliberaretrebuie ncheiate toate operaiunile obinuite decitire i scriere.

3. Accesele speciale sunt consistente numai lanivel procesor unul fa de cellalt.

Problema coerenei cache-ului

ntr-o ierarhie de memorie specific unui sistemmultiprocesor pot aprea inconsistene la nivelul dateloratt la nivele adiacente de memorie ct i n cadrul aceluiainivel.

Exemplul tipic este cel dat de copiile locale din cache fa decele din zona din memoria comun.

n momentul n care ne referim la aspecte legate deasigurarea coerenei la nivele ce implic memoria cacheapare o problem referit ca problema coerenei cache-ului.

Protocol cu scriere imediat (Write-Through)

n acest caz starea copie din cache se schimb innd contde operaiunile de citire, scriere sau nlocuire.

n figura sunt prezentate cele dou stri posibile ale unuibloc din cache care poate fi o copie a blocului din memoriacomun i poate afla n dou stri: valid sau invalid n cazulfolosirii tehnicii de scriere imediat.

Fie un alt procesor j (cu ji) care ncearc s lucreze curespectivul bloc. Toate procesoarele pot realiza citirea (R(i),R(j)) fr probleme.

Protocol cu scriere imediat

De fiecare dat cnd un alt procesor scrie W(j) n copia lui dincache toate celelalte copii sunt invalidate.

Protocol cu scriere ntrziat (Write-Back)

n acest caz starea valid a unui cache care folosete aceastpolitic poate fi mprit n dou stri distincte una descriere-citire (RW) i una numai de citire (ROnly) dup cumse observ n figura .

Starea invalid (INV) corespunztoare cazului dirty saucnd copia este incorect sau nu exist este echivalent custarea invalid de la modelul menionat anterior.

Aceast schem este specific unui protocol de proprietate(n sensul controlului momentan absolut ownershipprotocol).

Protocol cu scriere ntrziat

n starea INV se intr numai cnd un alt procesor imodific W(j) copia local sau i nlocuiete Z(i) acea copie.Starea RW corespunde situaiei n care numai aceast copie(de pe procesorul i) exist n sistem.

Este evident c sunt permise numai operaiunile de localede scriere sau citire (R(i), W(i)).

nainte ca un bloc s poat fi modificat trebuie obinutcontrolul pentru acces exclusiv prin lansarea unei operaiunide tip RO pe magistral n scopul anunrii restului deprocesoare, prin intrarea cache-urilor locale n starea RO,despre preluarea controlului.

Protocol cu scriere unic (Write Once)

A fost propus n 1983 de Goodman J. i mbinavantajele ambele metode anterior prezentate.

n scopul reducerii traficului pe magistral primaoperaiune de scriere a unui bloc din cache folosetetehnica de scriere imediat.

Aceasta va conduce la invalidarea celorlalte copii cti la transmiterea modificrii n memoria comun.

Protocolul cu scriere unic

Schema de lucru este prezentat n figura, unde prin liniicontinue sunt referite comenzile iniiate de procesorul local iarprin linii punctate sunt indicate comenzile iniiate de alteprocesoare prin intermediul magistralei sistem, sub forma unuigraf ce conine urmtoarele stri:

Valid: blocul din memoria cache care este identic cu cel dinmemoria principal a fost citit din aceasta i nu a fost modificat

Invalid: blocul fie nu exist n memoria cache fie nu coincide cucopia din memoria principal

Rezervat: datele au fost scrise exact o singur dat de lanceperea citirii din memoria comun. Copia din cache esteidentic cu cea din memoria comun care este singura copieexistent.

Dirty: blocul din cache a fost modificat mai mult de o dat iarrespectiva modificare nu a fost propagat. n acest caz avem ocopie unic n sistem.

Din punct de vedere al celorlalte procesoare existurmtoarele posibile comenzi externe primite de lamagistral: read invalidate care citete din bloc iinvalideaz toate copiile i write invalidate careinvalideaz toate copiile unui bloc.

Lipsa unui bloc din cache (read miss) apare atunci cndprocesorul dorete s citeasc un bloc care nu se afl ncache.

n aceste condiii se va iniia o operaiune de citire pemagistral.

Dac nu exist copii marcate ca interzise (dirty) nseamnc memoria comun deine o copie corect i deci o vafurniza.

n cazul n care exist un bloc n cache i poate fi scris(write hit), dac copia este dirty sau rezervat, atuncioperaiunea de scriere este realizat local i noua stare estedirty.

Dac noua stare este valid atunci toate celelalte copii suntinvalidate, memoria comun trece la scriere imediat iarstarea rezultat este rezervat dup prima scriere.

Cnd un procesor nu poate realiza scrierea n cache-ul local(write miss) aceasta nseamn c copia trebuie ssoseasc fie din memoria comun fie dintr-un cache dirty.

Cnd blocul dorit este disponibil pentru citire (read hit):se poate oricnd realiza ntr-un cache local fr a puneprobleme de coeren.

Atunci cnd avem o situaie de nlocuire a blocului (blockreplacement) dac o copie este dirty nseamn ctrebuie nti scris n memoria comun prin nlocuireablocului. Dac copia este clean, situaie cnd aceasta estevalid, rezervat sau invalid, nu se va face nici o nlocuire.

Se observ c acest protocol necesit o linie special amagistralei care s poat realiza inhibarea memorie comunecnd o copie este invalid i o operaiune de citire amagistralei este necesar dup o situaie de inexisten ablocului dorit la citire.

Servicii cu stare versus servicii fr stare

Exist dou moduri de abordare a problemei stocriiinformaiei pe server n momentul n care un clientacceseaz fiiere de pe alt system:

ori serverul urmrete fiecare fiier accesat de fiecareclient,

sau pur i simplu pune la dispoziie blocuri pe masur ce sunt cerute de client, fr a-l interesa cum sunt folositeacele blocuri.

n primul caz avem de-a face cu un serviciu bazat pe stare,

n cel de-al doilea cu servicii care nu sunt bazate pe stare.

32

Un serviciu fr stare este descris ca o conexiune ntreclient i server n timpul unei sesiuni.

Ori prin nchiderea fiierului sau prin mecaismul de garbage-collection serverul trebuie s i curee spaiulprincipat de memorie folosit de clienii care nu mai suntactivi.

Punctul principal legat de tolerana la erori ntr-un serviciunecaracterizat de stare este acela c serverul menineinformaia legt de clieni.

Un serviciu de fiiere necaracterizat de stare evitinformaiile despre stare fcnd n aa fel nct fiecarecerere s conin informaii despre sine.

33

Replicarea fiierelor Replicarea fiierelor pe diferite maini ntr-un sistem de

fiiere distribuit este un mod bun de a mbuntidisponibilitatea.

Replicarea pe mai multe maini poate crete iperformana: selectarea unei replici mai apropiate poateduce la timpi de acces mai mici.

Cerinele de baza ale schemei de replicare este ca replicidiferite ale aceluiai fiier s existe pe maini independentela cderi.

34

Este de dorit s se ascund detaliile replicrii fa de useri.

Maparea unui fiier replicat ntr-o replic particular este un task al schemei de nume.

Existena replicii ar trebui s nu fie vizibil la nivele superioare.

La nivele inferioare replicile trebuie s poat s fie difereniate prin nume diferit.

Alt cerin legat de transparen este s se realizezecontrolul replicilor la un nivel superior.

Controlul replicrii include determinarea nivelului replicriii a locului unde se depun replicile. n aceste situaii, vrems expunem aceste detalii userilor.

35

Principala problem a replicrii este legat de updatare.

Din punctul de vedere al utilizatorului, replica unui fiiertrebuie s denote aceeai entitate logic i, de aceea, un update asupra oricrei replici trebuie s se reflecte asupratuturor celorlalte replici.

Mai exact, consistena semantic trebuie pstrat ntreaccesul replicilor.

Dac consistena nu este de importan major, atunci eapoate fi sacrificat n avantajul disponibilitii i a performanei

36

Sistemul NFS(Network File Sistem) NFS a fost proiectat de Sun Microsystems din SUA, pentru

a crea un sistem distribuit de stocare pentru mainile lor.

Acesta permite o bun transparen la acces, toate fiierele sistem au fost combinate ntr-un arbore sistem coninut de un singur fiier,

In practic totui aceast abordare este destul de complicat ne nevoia de a furniza date specifice la locaii fixe (n UNIX) fiecare sistem necesit date diferite dar provenind din acelai loc.

37

Din nefericire NFS nu ofer o soluie complet.

Exist o slbiciune la nivelul securitii.

Pn recent, schimbul de informaii ntre maini se fcea la nivel de fiiere text adic datele puteau fi citite de oricine.

Criptarea poate furniza protecia datelor precum i verificarea/autorizarea accesului la date

Deci accesul unei maini pe alta este permis doar cu cheia de criptare/decripare specific.

38

Problema inconsistenei cache n NFS

39

Aceast politic de tip write-through garanteaz securitatea datelor dar implic modificarea simultan a copiilor existente n reea.

NFS nu gestioneaz foarte bine cazul cderilor mainii.

Prin definiie UNIX -ul o dat ce face o scriere n fiier (apel write()) i nu sunt raportate erori asta nseamn c data a fost scris corect.

40

NFS V4 Difer fundamental de versiunile anterioar.

Cea mai semnificativ schimbare este accea c protocoluleste acum bazat pe stare, asta nsemnnd c serverulmenine starea sesiunii clientului din momentul n careeste deschis remote un fiier i pn la nchidera sa.

De aceea, protocolul NFS are acum operaiile open() iclose(); vesiunile anterioare de NFS, care nu sunt bazate pe stare, nu pun la dispoziie astfel de operaii.

Mai mult, versiunile anterioare specific protocoaleseparate pentru montarea sistemelor de fiiere remote ipentru a le bloca.

41

Adiional, V4 a mrit abilitatea clienilor de a face cache cufiierele de date local.

Aceast capabilite mbunteste performanele sistemuluidistribuit de fiiere, dndu-le clienilor abilitatea de a rezolva mai multe accese din cacheul local, n loc de a-i pune s treac prin server.

V4 le ofer abilitate clienilor de a cere lockuri pe fiierelede pe servere. Dac serverul acord permisiunea, clientulmenine lockul pn cnd este eliberat sau pn i expirperioada.

42

SNF Sprite Network File system Acest sistem de operare a fost creat la Berkley SUA pentru a

ndeplini funcii similare ca i NFS oferind soluii similare n problema transparenei accesului i a transparenei locaiilor. Proiectanii lui au inut cont de problemele NFS -ului i au ncercat s le corecteze fr a pierde din performan sau flexibilitate. Cele trei probleme majore rezolvate sunt:

1. Evitarea ca fiierele temporare s fie scrise napoi dac nu este necesar

2. Evitarea ntrzierii operaiunii de scriere datorit vitezei reelei

3. Garantarea faptului c cea mai recent scriere va fi vzut de toi clienii.

43

Pentru obinerea acestor eluri Sprite folosete servere de stare care menin informaia despre cine acceseaz reeaua i cum o acceseaz.

Cnd un fiier este accesat de un client, serverul informeaz despre operaiune mpreun cu tipul operaiei.

Cnd un fiier este deschis de un client nu mai apar probleme indiferent de modul de lucru pentru c datele sunt prelucrate local n cache deci nu sunt comune nimnui.

44

Mecanismul "calback" n SPRITE45

Din punct de vedere al stabilitii Sprite este mai bun ca NFS.

Cderile i refacerea datelor dup acea sunt rezolvate prin folosirea unei combinaii ntre o bun structurare a fiierelor sistem i o stare distribuit meninut de fiierele sistem ale clienilor.

Un server NFS se poate bloca i reporni fr a avea cunotin despre programele clienilor.

Sprite folosete serverele de stare care menin informaii despre fiecare client i dac este necesar ncercarea de recuperare a datelor, sau nu, n caz de cdere a serverului.

46

Curs 4

1

Sistemul NFS(Network File Sistem) NFS a fost proiectat de Sun Microsystems din SUA,

pentru a crea un sistem distribuit de stocare pentru mainile lor.

Acesta permite o bun transparen la acces, toate fiierele sistem au fost combinate ntr-un arbore sistem coninut de un singur fiier,

In practic totui aceast abordare este destul de complicat ne nevoia de a furniza date specifice la locaii fixe (n UNIX) fiecare sistem necesit date diferite dar provenind din acelai loc.

2

Din nefericire NFS nu ofer o soluie complet.

Exist o slbiciune la nivelul securitii.

Pn recent, schimbul de informaii ntre maini se fcea la nivel de fiiere text adic datele puteau fi citite de oricine.

Criptarea poate furniza protecia datelor precum i verificarea/autorizarea accesului la date

Deci accesul unei maini pe alta este permis doar cu cheia de criptare/decripare specific.

3

Problema inconsistenei cache n NFS

4

Aceast politic de tip write-through garanteaz securitatea datelor dar implic modificarea simultan a copiilor existente n reea.

NFS nu gestioneaz foarte bine cazul cderilor mainii.

Prin definiie UNIX -ul o dat ce face o scriere n fiier (apel write()) i nu sunt raportate erori asta nseamn c data a fost scris corect.

5

O situaie similar apare atunci cnd se face citirea unei date din cache iar serverul nu rspunde.

Dup cum se observ o rezolvare posibil a acestor probleme este abandonarea operaiunii n curs de desfurare dup un timp fr reacie de la server-client, din pcate aceast metod nu prezint interes.

Sunt rezolvate totui cteva probleme de management distribuit.

De exemplu protecia este asigurat de atribute de fiier tip standard UNIX owner group etc.

Acest lucru d rezultate cnd reeaua este administrat centralizat i fiecrui client din reea i se poate da o identificare unic n reea.

6

NFS V4 Difer fundamental de versiunile anterioar.

Cea mai semnificativ schimbare este accea cprotocolul este acum bazat pe stare, asta nsemnnd cserverul menine starea sesiunii clientului dinmomentul n care este deschis remote un fiier i pnla nchidera sa.

De aceea, protocolul NFS are acum operaiile open() iclose(); vesiunile anterioare de NFS, care nu suntbazate pe stare, nu pun la dispoziie astfel de operaii.

Mai mult, versiunile anterioare specific protocoaleseparate pentru montarea sistemelor de fiiere remotei pentru a le bloca.

7

Adiional, V4 a mrit abilitatea clienilor de a facecache cu fiierele de date local.

Aceast capabilite mbunteste performanelesistemului distribuit de fiiere, dndu-le clienilorabilitatea de a rezolva mai multe accese din cacheullocal, n loc de a-i pune s treac prin server.

V4 le ofer abilitate clienilor de a cere lockuri pe fiierele de pe servere.

dac serverul acord permisiunea, clientul meninelockul pn cnd este eliberat sau pn i expirperioada.

8

Noile mecanisme de locking i cacheing sunt bazate pe conceptual delegrii, unde serverul delegresponsabiliti pentru un lock pe fiier i coninutclientului care a cerut lockul.

Clientul delegate menine n cache versiunea curent a fiierului i alti clieni pot s cear clientului delegateun lock i coninutul fiierului pn cnd fiieruldelecat va elibera lockul i delegarea.

9

SNF Sprite Network File system Acest sistem de operare a fost creat la Berkley SUA

pentru a ndeplini funcii similare ca i NFS oferind soluii similare n problema transparenei accesului i a transparenei locaiilor.

Proiectanii lui au inut cont de problemele NFS -ului i au ncercat s le corecteze fr a pierde din performan sau flexibilitate. Cele trei probleme majore rezolvate sunt:

1. Evitarea ca fiierele temporare s fie scrise napoi dac nu este necesar

2. Evitarea ntrzierii operaiunii de scriere datorit vitezei reelei

3. Garantarea faptului c cea mai recent scriere va fi vzut de toi clienii.

10

Pentru obinerea acestor eluri Sprite folosete servere de stare care menin informaia despre cine acceseaz reeaua i cum o acceseaz.

Cnd un fiier este accesat de un client, serverul informeaz despre operaiune mpreun cu tipul operaiei.

Cnd un fiier este deschis de un client nu mai apar probleme indiferent de modul de lucru pentru c datele sunt prelucrate local n cache deci nu sunt comune nimnui.

11

Sprite de asemenea folosete o politic de scriere ntrziat. n loc s trimit, pentru modificare imediat, la o scriere ctre fiierul de pe server, modificrile sunt fcute n cache-ul local i trimise prin reea pentru o real modificare numai atunci cnd s-au terminat toate modificrile n respectivul fiier.

Exist ocazii cnd Sprite face scriere nainte de terminarea tuturor modificrilor.

Una din cazuri, i cel mai simplu este atunci cnd cache-ul clientului este plin i pentru a face spaiu se trimit modificrile procesul relundu-se.

12

Mecanismul "calback" n SPRITE13

Din punct de vedere al stabilitii Sprite este mai bun ca NFS.

Cderile i refacerea datelor dup acea sunt rezolvate prin folosirea unei combinaii ntre o bun structurare a fiierelor sistem i o stare distribuit meninut de fiierele sistem ale clienilor.

Un server NFS se poate bloca i reporni fr a avea cunotin despre programele clienilor.

Sprite folosete serverele de stare care menin informaii despre fiecare client i dac este necesar ncercarea de recuperare a datelor, sau nu, n caz de cdere a serverului.

14

Alt problem curent este legat de resincronizarea fiierelor sistem UNIX cu clienii dup cderea unui server, aprnd necesitatea verificrii consistenei fiierelor sistem.

Pe un Sun 4 cu harddisk de 2 Gb spaiu pe disc aceast procedur poate dura cel puin 15 minute.

Sprite ncearc s remedieze aceast problem prin folosirea fiierelor de nregistrri sistem structurate n locul celor bazate pe o modificare convenional.

Acest fiier de nregistrri mpreun cu verificarea periodic a lui formeaz un sistem de fiiere similar sau mai bun ca performane dect UNIX-ul, posednd n plus i avantajul scderii timpului de refacere

15

Periodic zon de verificare este scris pe disc ntr-o poziie fixat (de fapt sunt meninute dou asemenea zone care sunt modificate alternativ n scopul evitrii erorilor de scriere din diverse motive).

Aceast zon conine suficiente informaii pentru a permite nregistrrilor s fie indexate i citite n mod eficient. i, de asemenea face ca sistemul s posede puncte n care consistena s fie garantat.

Fr aceste informaii citirea unui fiier de pe disc ar necesita examinarea ntregului fiier de nregistrri pentru a putea reface fiierul n cazul unei cderi a sistemului.

16

Sistemul de operare Decorum Decorum folosete principii similare cu Sprite

pentru a furniza un sistem de operare de tip UNIX dar capabil s lucreze pe maini distribuite.

Pentru interfaare un sistem virtual de fiiere (VFS Virtual File System) este ataat sistemului .

Interfaa permite de asemenea ca diferite fiiere la nivel fizic s fie folosite simultan de clieni care pot vedea acelai fiier n aceiai manier.

Un avantaj major este faptul c fiiere NFS pot fi folosite de clienii Decorum fr modificri.

17

Sunt folosite mai multe tipuri de etichete:

de date (data token) - permit clientului s citeasc sau s scrie (depinznd de subtipul etichetei) un numr de octei dintr-un fiier.

de stare (status token) - permit clientului s citeasc sau s scrie (depinznd de subtipul etichetei) informaia de stare asociat cu un fiier.

de blocare (lock token) - permit clientului blocheze citirea sau scrierea (depinznd de subtipul etichetei) unui numr de octei dintr-un fiier.

de deschidere (open token) - d clientului dreptul de a deschide un fiier ntr-un mod particular (depinznd de subtipul etichetei).

18

Etichetele de diferite tipuri nu interacioneaz ntre ele atta timp ct se refer la diferite elemente (proprieti) ale fiierului.

Acordarea i revocare acestor etichete este similar cu mecanismul de rechemare (callback) existent n Sprite.

Din acest punct de vedere putem spune c Spriteposed o singur etichet care spune dac cu un fiier se poate lucra n stilul cache sau nu.

n comparaie cu Sprite, Decorum are o granularitate mult mai mic relativ la controlul lucrului cu cache.

19

Protecia este simpl fiind asigurat de funciile UNIX standard.

n plus sunt adugate liste de control al accesului (ACL Acces Control List).

Consistena datelor este meninut prin copii pe servere.

Aceste servere sunt responsabile de mirroring-ul(crearea unei copii a unei zone sau chiar a ntregului dispozitiv de stocare, n scopul creterii toleranei la erori a sistemului ) continuu al sistemului folosind o politic de replicare lent, care garanteaz ca va face copii ale datelor ntr-o perioad maxim de timp.

20

n general nu trebuie ca durata de replicare s fie mic deci eforturile se ndreapt n continuare spre scderea costului de multiplicare.

Decorum ndeplinete multe din cerinele unui sistem de stocare distribuit.

Capacitatea de a replica fiierele sistem aa cum sunt l face foarte puternic n prevenirea cderilor de servere sau de reea.

Sistemul lui de protecie previne bine accesul utilizatorilor nedorii.

21

Sistemul de fiiere plan 9. Este un sistem de operare distribuit dezvoltat de

laboratoarele Bell de ctre proiectanii UNIX-ului.

Dei nu este compatibil cu UNIX el este proiectat ca s suporte urmtoarele maini n reea

Servere extrem de puternice (de obicei multiprocesor) furnizeaz puterea de calcul pentru utilizatori

Servere de fiiere - furnizeaz zonele de stocare date

Terminale grafice dedicate - permite o interfa grafic pentru utilizatori

22

Plan 9 nu are o transparen a datelor coerent i nici protocol de coeren a datelor.

n multe cazuri comunicaia dintre serverul de date i serverul procesor este presupus a fi suficient de rapid ca s nu mai trebuiasc s lucreze cu cache.

Fr cache dispar problemele legate de coeren.

Oricum Plan 9 este proiectat s lucreze cu o varietate de tipuri de reea incluznd i cele lente .

23

Cnd un fiier de pe server este deschis de ctre un client indiferent dac este de date sau executabil se returneaz o cheie de 64 bii ctre client.

O parte a acestei chei identific fiierul iar restul identific tipul fiierului.

Aceast cheie este comparat cu fiecare din cheile inute de orice seciune aflat n seciunea cache a fiierului clientului.

Dac cheile sunt identice atunci datele din cache pot fi terse iar data trebuie recitit de pe server.

24

Soluia abordat pentru a realiza transparena locaiilor i a accesului este ca fiecare grup de procese s aib propriul namespace (identificator a spaiului de memorie comun) care i permite s construiasc i s modifice cum dorete zona proprie de lucru.

Este posibil pentru orice utilizator s construiasc un mediu de lucru (environment) similar neavnd importan de unde se face accesul fa de locaia datelor.

Aceast abilitate de a construi namespace individuale ajut managementul distribuit, din moment ce fiecare aplicaie poate construi un fiier sistem care i trebuie relativ la ceea ce serverul poate oferi.

26

Pentru a realiza pornirea sistemului se folosete un identificator special de utilizator none.

Schema de acces nu este ca n NFS unde o main considerat ca de nencredere este automat mapatca alii. Oricum folosirea numelor textuale i a unei politici orientat dup numele utilizatorului permite controlul distribuit simplu a utilizatorului .

Plan 9 atac problema sistemelor mari distribuite prin relaxarea multora dintre semanticile UNIX-ului clasic. Soluia autentificrii este adecvat dar nu att de flexibil ct ar trebui.

27

AFS Andrew este un mediu computaional distribuit,

gndit i implementat la Universitatea Carnegie Mellon. Sistemul de fiiere Andrew consitiuiemecanismul de schimb de informaii ntre clienii dinacel mediu.

Transarc Corporation a preluat dezvolarea AFS. Ei aufost apoi preluai de IBM.

IBM a produs de atunci cteva implementricomerciale de AFS.

AFS a fost apoi ales ca sstemul de fiiere distribuitpentru o coaliie din industrie, rezultnd TransarcDFS, care e parte a sistemului computaional distribuita organizaiei OFS.

28

Majoritatea vendorilor de UNIX, precum i Microsoft, suport ssistemul DCE, precum i DFS-ul su care este bazat pe AFS. Se continu lucrul n ncercarea de a facedin DCE un DFS cross-platform general acceptat.

Cum AFS i Transarc DFS sunt similare, vom descrieAFS n cele ce urmeaz i ne vom referi la Transarc DFS atunci cnd va fi specificat explicit acesta.

AFS ncearc s rezolve multe dintre problemeleDFSurilor mai simple, cum ar fi NFS, i este cel DFS-ulneexperimental cu cele mai multe facilitai.

Conine un spaiu de nume uniform, un sistem de sharing independent de locaie, cacheing pe clientoferind consisten cacheului i autentificare securizat folosind Kerberos.

29

AFS face distincia ntre maini client (uneori numitestaii de lucru) i serverele dedicate.

Serverele i clienii rulau la nceput doar versiunea 4.2 de BSD UNIX, dar AFS a fost portat i pe alte sisteme de operare.

Clienii i serverele sunt interconecti de o reea de LANuri sau WANuri.

Clineii au un spaiu de nume de fiiere partiionat: un spaiu de nume local i unul shared.

Serverele dedicate, numite colectiv Vice, dup numelesoftwareului pe care l ruleaz, pun la dispoziia clienilorspaiul de nume sharat sub forma unui sistem de fiiereierarhic omogen, identic, transparent din punctul de vedere a locaiei.

30

Tot locale sunt fiierele temporare i fiierele pe careposesorul staiei, din motive de asigurare a intimitii, dorete explicit s le salveze local.

Vzute mai n amnunt, clienii i serverele suntstructurate n clustere interconectate de un WAN. Fiecare cluster este constituit dintr-o colecie de staiide lucru dintr-un LAN i un reprezentant Vice, numitserver de cluster, i fiecare cluster este conectat la WAN printr-un router.

Descompunerea n clustere este fcut n specialpentru a adresa problema scalabilitii.

Pentru performane optimale, staiile trebuie sfoloseasc serverul din clusterul lor n cea mai mare parte din timp, de aceea referinele ntre clustere suntrelativ infrecvente.

31

Pe scurt, cteva probleme adiionale legate de designulAFSului:

Mobilitatea clientului. Clienii sunt capabili sacceseze orice fiier n spaiul de nume sharat de oricestaie de lucru. Un client poate observa o degradare a performanelor iniiale din cauza chacheinguluifiierelor cnd se acceseaz fiiere de pe o alt staiedect cea obinuit.

Securitatea. Interfaa Vice este considerat ca fiind o limitare a siguranei, pentr c nici un program clientnu e executat pe maina Vice. Autentificarea itransmiterea securizat sunt realizate ca parte a comunicaiei bazate pe pachete a paradigmei RPC.

32

Protecia. AFS pune la dispoziie liste de accespentru a proteja directoare i biii normali UNIX pentru protecia fiierelor.

Lista de acces poate conine informaii despre aceiuseri care au dreptul s acceseze un director, precum i informaii despre userii care nu au acestdrept.

De aceea este uor de specificat c oricine cuexcepia, s zicem, a lui Jim, are dreptul s accesezeun director.

AFS ofer suport pentru aciuni ca citire, scriere, cutare, inserare, administrare, blocare i tergere.

33

Spaiul de nume comun Spaiul de nume comun al AFS este constituit din

componente unitare, numite volume.

Volumele sunt componente unitare mici.

Tipic, ele sunt asociate cu fiierele de pe un singurclient.

Puine volume pot sta pe o singur partiie i ele suntcapabile s creasc (pn la o anumit cot) sau sscad ca mrime.

Conceptual, volumele sunt legate ntre ele printr-un mecanism similar cu mecanismul mount din UNIX.

Totui, diferena de granularitate e semnificativ, deoarece n UNIX doar o partiie de disc (care coninesistemul de fiiere) poate folosi mount.

34

Identificatorul unic face posibil reutilizareanumrului nodului, coninnd nite structuri de date compacte.

Fid-urile sunt transparente la locaii, de aceea mutareafiierelor de la server la server nu invalideazconinutul directoarelor din cache.

Informaiile despre locaii sunt inute ntr-o baz de date replicat pe fiecare server.

Un client poate identifica locaia fiecrui volum dinsistem prin interogarea bazei de date.

Agregarea fiierelor n volume face posibilmeninerea bazei de date la valori acceptabile.

35

n timpul transferului volumului, serverul caretransmite poate n continuare s realizezeupdateuri, caresunt transmise mai tarziu spre noulserver.

La un moment dat, volumul este dezactivat pentrupuin timp, astfel nct modificrile s fie procesate; apoi, noul volum devine disponibil dinnou la noua locaie.

Operaia de transmitere a volumului este atomic.

Dac oricare dintre servere cade, operaia este oprit.

36

Operaii pe fiiere i consistena semantic

Pricipiul arhitectural fundamental al AFS este cachingul fiierelor ntregi de pe servere.

n mod corespunztor, o staie client interacioneazcu serverul Vice numai n timpul operaiilor de deschidere i nchidere a fiierelor, i chiar i aceastinteraciune nu este tot timpul necesar.

Citirea i scrierea fisierelor nu duce la interaciuniremote (n contrast cu metoda remote-service).

Aceasta distincie cheie are ramificaii impornatntepentru performan, i pentru semantic i operaii cufiiere.

37

Venus ar putea contacta Vice numai cnd un fiier e fiier e deshis sau nchis; citirea i scrierea byte-ilorindividuali ai fiierelor sunt fcute direct pe copia dincache i trec peste Venus.

Aceasta face ca citirea de pe unele locaii nu suntvizibile imediat n alte locaii.

Cacheingul este mai apoi exploatat pentru altedeschideri ale fiierului care a fist ncarcat n cache.

Venus presupune c intrrile n cache (fie ele fiieresau directoare) sunt valide doar dac altceva nu se specific.

38

Cnd un client face cacheul unui fiier sau al unuidirector, serverul i updateaz informaia desprestare pentru a nregistra aceast cacheing.

Spunem c clientul are un callback pe acel fiier.

Serveul notfic clientul nainte s ii permit altuiclient s modifice fiierul.

ntr-un asemenea caz, spuenm c serverulndeprteaz callbackul de pe fiier de la fostulclient.

Un client poate folosi un fiier din cache doarpentru a-l deschide atta timp ct fiierul are callback.

39

De aceea, singura ocazie n care Venus contacteazVice este atunci cnd se face deschiderea unui fiiercare ori nu e n cache sau care a avut callbackul revicati la nchiderea local modific fiierul.

n esena, AFS impementez semantica sesiunii.

Singura excepie este aceea a altor operaii cu fiieredect readurile i writeurile primitive (de exempluschimbarea proteciei la nivel de director), care suntvizibile oriunde pe reea imediat dup ce operaia se termin.

n ciuda mecanismului de callback, traficul cauzat de validrea cacheului este sczut, de obicei pentru a nlocui callbackurile pierdute din cauza cderilormainii sau a reelei.

40

Venus face cache i pentru directoare i linkurisimbolice, pentru traducerea cilor.

Fiecare componet din spaiul de nume din directoareeste prencrcat pentru el, dac nu este deja n cache sau dac clientul nu are un callback.

Venus realizeaz cutri pe directoarele prencrcate, folosind fidurile.

Nicio cerere nu este trimis de la un server la altul.

Urmtoarele cereri de deschidere asupra acestui fiiernu vor provoca comunicare n reea, cu excepiacazului n care un callback este oprit pe o componenta numelui cii.

41

Implementarea Procesele client sunt interfaate cu un kernel UNIX cu

un set uzual de cereri de sistem.

Kernelul este puin modificat pentru a detecta referinele la fiierele Vice din operaiile relevante ipentru a nainta cererile la procesul client Venus de pe staia de lucru.

Venus face o traducere a spaiului de numecomponent cu componet, aa cum a fost descris maisus. Are un cache de mapare care asociaz volumele culocaiile de pe server pentru a elimina riscul de interogare a serverului pentru o locaie de volum deja cunoscut.

Dac un volum nu exist n cache , Venus contacteazorice server cu care are deja o conexiune, cere locaiainformaiei, i introduce informaia n cacheul mapat.

42

Sistemul de fiiere UNIX este utilizat ca un sistem de stocare de nivel sczut att pentru clienii ct i pentruserverele AFS. Cacheul clientului este un director local pe discul staiei.

n acest director sunt fiiere ale cror nume suntsurtturi spre intrrile din cache. Att Venus ct iprocesele de pe servere acceseaz fiierele UNIX directdup litera nodului pentru a evita rutina de traducerecale-nume-nod.

Pentru c interfaa nodului intern nu e vizibil la procesele de nivel client (att Venus ct i proceseleserver sunt procese client), un set coerent de cereriadiionale de sistem au fost adugate.

43

Chacheul de status este meninut n memorie pentru a permite un serviciu stat() rapid.

Datele din cache sunt rezidente pe discul local, dar sistemul de bufferare de intrare-ieire al UNIX face un cacheing a blocurilor discului n memorie ntr-un modtransparent pentru Venus.

Un singur proces de nivel client pe fiecare server de fiiereface toate cererile de fiiere pentru client.

Acest proces folosete un pachet proces uor cu o planificare nepreemptiv pentru a servi concurent maimulte cereri ale clienilor.

44

Curs 5

1

LBProblema echilibrrii ncrcrii a aprut o

dat cu dezvoltarea mainilor de calcul paralel.

Este poate una din cele mai importante probleme din domeniul calculului de mare performan.

2

La ora actual, o dat cu dezvoltarea rapid a Internetului i mai ales a ratelor de transfer suportate de acesta, s-a pus problema muncii cooperative, a mai multor staii n calculul aceleiai aplicaii, dar fr folosirea unui sistem centralizat

3

n arhitecturile strns cuplate una dintre problemele era dependena prea strns a performanelor algoritmului de arhitectura hardware.

La ora actual aceste probleme specifice iniial numai calcului paralel se regsesc i n sistemele de operare sau i aplicaiile de uz comun.

4

n general prin ncrcarea unui sistem se nelege procentul de resurse folosite la un moment dat de o aplicaie sau un grup de aplicaii.

ncrcarea unui sistem este legat de performana acestuia.

Putem spune c un sistem ncrcat peste o anumit limit, chiar dac mai poateaccepta noi probleme spre rezolvare, nu maisatisface cererile n timpul lui normal de rezolvare.

5

Deoarece echilibrarea ncrcrii este o tehnic de folosire optim a resurselor de calcul rezult c trebuie realizat o foarte fin analiz de rentabilitate nainte de alegerea unei tehnici anume.

Evident c n forme rudimentare exist implementat att la nivel de sistem de operare ct i la nivel de aplicaie.

6

Algoritmul generic al unei echilibrri a ncrcrii

7

Echilibrarea static a ncrcrii Echilibrarea ncrcrii poate fi realizat att static

ct i dinamic.

n cazul abordrii statice toate calculele sunt realizate nainte de lansarea n execuie a aplicaiei.

Acest tip de echilibrare mai este cunoscut n literatura de specialitate i sub denumiri ca problema maprii sau a planificrii (scheduling).

8

Chiar dac prin analiza algoritmului de calcul s-a propus o metod de mapare care s minimizeze timpii mori de execuie nimeni nu poate garanta c toate task-urile se vor termina cam n acelai interval temporal ceea ce conduce imediat la idea c ntrzierea mare a unui singur task poate anula efectele echilibrrii n momentul n care se ntlnete un punct de sincronizare sau de colectare a rezultatelor.

9

Cea mai mare parte a algoritmilor de planificare static folosete una din metodele urmtoare: teoria grafurilor, programarea matematic, euristici.

n primul caz, att aplicaia, ct i sistemul hardware sunt modelate sub forma unor grafuri, ntre care se ncearc gsirea unui omomorfism, sau o partiionare minimal (algoritmul min cut).

10

Metodele din programarea matematic s-au impus, datorit uurinei formulrii obiectivului urmrit: minimizarea unei funcii cost, n prezena unor restricii.

Funciile cost propuse se refer la minimizarea timpului total de comunicare ntre procese, sau a timpului total de comunicaie la care se adaug o component ponderat ce corespunde timpului de execuie a proceselor ntr-un sistem eterogen .

11

Oricare ar fi funcia cost i restriciile adoptate, problema poate fi rezolvat ca una de programare neliniar cu variabile bivalente.

Metodele euristice ncearc s furnizeze o soluie apropiat de cea optim, ntr-un timp rezonabil .

12

In timp ce furnizeaz rezultate mai bune, algoritmiiiterativi depind de soluia iniial .

De aceea, se propune executarea unei variante greedy, pentru a obine o prim soluie, care este apoimbuntit cu un algoritm iterativ.

Cea mai rspndit metod folosete grupareaproceselor ntr-o list, conform unor anumite criterii fie n ordinea descresctoare a timpilor de execuie, nordinea impus de terminarea execuiei la termene fixe.

13

Cel mai apropiat vecin n aceast schem fiecare procesor rmas

fr job-uri, cere noi job-uri de la vecinii apropiai cum ar fi de exemplu ntr-un hipercub unde sunt log(n) vecini.

14

Round and Robin Asincron Fiecare procesor menine o variabil int

(target) independent.

De fiecare dat cnd procesorul rmne n ateptare, citete valoarea intei locale i trimite o cerere de treab ctre un procesor particular.

15

Round and Robin Global n acest caz variabila int este ntr-un prim procesor

(root).

Cnd un procesor cere un job, primete variabila int, iar radacina incrementeaz respectiva variabil.

16

Metode de planificare dinamic. n acest caz task-urile sunt alocate la procesoare n

timpul execuiei programului.

Exist dou tipuri de abordri centralizat idescentralizat.

17

Abordarea centralizat Procesul conductor are imaginea global asupra

rezolvrii problemei.

18

Sarcini cu dimensiuni neprecizate apar cel mai des la aplicarea algoritmilor de cutare pentru care un task poate genera un numr oarecare de copii sau poate trimite imediat rezultatele ctre printele lui.

O abordare tipic n cazul implementrii este folosirea unei cozi pentru task-urile care ateapt s fie executate.

19

Dei abordarea centralizat este foarte rspndit eaare o serie de dezavantaje dintre care cel maiimportant este ncrcarea aprut la nivelul procesuluiconductor.

Acesta nu poate deservi dect un proces subordonat la un moment dat.

20

Abordarea descentralizat O prim soluie rezult direct din modelul fermei de

procesoare prin partiionarea att a fermei ct i a problemei astfel nct fiecare conductor primete o subproblem.

Se observ c aceast abordare este parial distribuit.

21

n cealalt situaie se merge pe redirijarea sarcinilor suplimentare de ctre procesul sau procesorul care este suprancrcat ctre receptorii care au o ncrcare medie sau sub medie.

Datorit calculului suplimentar necesar analizei permanente a ncrcrilor locale din sistem aceast metod este folosit n cazul sistemelor cu ncrcare mic i mijlocie.

22

O prim abordare relativ la implementare poate fi realizat folosind tehnica round and robin.

23

Etapele specifice realizrii echilibrrii dinamice

O soluie practic pentru problema echilibrrii ncrcrii dinamice poate implica urmtoarele etape:

Evaluarea ncrcrii unde se realizeaz o estimare a ncrcrii procesorului trebuie realizat pentru a determina dac exist un eventual dezechilibru.

24

Determinarea profitabilitii unde se verific dac costul dezechilibrului depete costul echilibrrii ncrcrii, atunci echilibrarea ncrcrii poate fi iniiat.

25

Calcularea vectorului de transfer al ncrcrii

Este calculat pe baza msurtorilor fcute n prima faz cnd se calculeaz vectorul de transfer al ncrcrii pentru a echilibra procesoarele.

Un algoritm ar fi SID propus de Willebeek. n acest caz se pornete de la premisa ca taskurile sunt infinit divizibile i ncrcarea unui procesor este reprezentata de un numr real.

26

Algoritmul DASUD se bazeaz pe algoritmul SID, care a fost mbuntit pentru a ncorpora caracteristici noi, care detecteaz dac un domeniu(toi vecinii imediai ai unui procesor) este echilibrat sau nu.

Dac domeniul nu este echilibrat, excesul de ncrcare este distribuit vecinilor dup diferite criterii, depinznd de distribuia ncrcrii lor.

27

Comportamentul algoritmului DASUD poate fi divizat n trei etape, potrivit valorilor parametrilor anteriori, care servesc la msurarea dezechilibrului unui domeniu la care procesorul i aparine.

28

Selecia taskurilor Se efectueaz n acord cu vectorul de transfer calculat

n faza anterioar.

Exist dou opiuni pentru satisfacerea vectorului de transfer dintre dou procesoare.

29

Migrarea taskurilor Se realizeaz transferul efectiv al task-urilor de la un

computer la altul.

Aceasta trebuie s conserve integritatea strii unuitask, incluznd orice mesaj sosit de pe canalele de comunicaie.

30

Echilibrarea prin predicia ncrcrilor

Din nefericire, la proiectarea aplicaiilor specifice sistemele de operare Microsoft nu se poate atinge o finee de echilibrare dorit, din cauza modului limitat n care o aplicaie poate avea acces la resursele sistemului .

Pentru multe aplicaii proiectarea se bazeaz pe faptul c un task lansat la distan (indiferent de modelul de calcul folosit) poate fi blocat sau ntrziat suficient ca rezultatul muncii sale s nu mai fie folositor .

31

Acest lucru poate fi evitat dac proiectarea aplicaiei este abordat diferit.

Cea mai comun situaie este aceea n care serverul consider un task neutilizabil (dead) n momentul n care, din cauza suprancrcrii staiei pe care se afl, nu mai lucreaz normal.

32

Gestionarea taskurilor n proiectarea unei aplicaii distribuite granularitatea

acesteia trebuie luat ntotdeauna n consideraie.

Totui, influena acestui factor poate fi redus, dac se folosete o nou abordare.

n cazul sistemelor de operare Microsoft, controlul fin al alocrii resurselor este sczut fa de UNIX.

33

Decizia cu privire la cantitatea de munc ce poate fi distribuit este complicat, de fapt reprezint o problem NP dificil.

De obicei soluiile propuse rezolv numai anumite subclase de probleme .

34

Din nefericire, idea general susinut de raiuni economice, este c un sistem de operare distribuit trebuie s fie transparent din punctul de vedere al folosirii resurselor locale de ctre ali utilizatori din reea .

De asemenea, este bine ca orice aplicaie distribuit s urmeze aceeai gndire de prelucrare.

35

Predicia ncrcrii Idea de baz provine dintr-un model propus de Bhat

[Bha98] legat de folosirea capacitilor de calcul ale unei staii atunci cnd proprietarul este plecat.

Se definete un planificator S pentru furtul de timpi de lucru, unde S=t0,t1,t2, i are definiia temporal prezentat n ecuaia

36

0

00

1101 kiftttT

kif

kk

k

Dac utilizatorul staiei B nu s-a rentors n timpul Tk=k+tk, cantitatea de munc executat pn n acest moment este wk, dac ns se ntoarce nainte de scurgerea lui Tk atunci perioada de mprumut a resurselor ia sfrit i munca efectuat pn n acest moment este w0+w1++wk-1.

37

yxyxundectwdef

kk ,0max,

De asemenea sunt introduse dou funcii de probabilitate p i q, dup cum urmeaz:

- q este funcia de risc a unui episod i are proprietatea

p este funcia de descretere a duratei de via pentru un episod:

38

Folosind funcia de risc marginal q+, putemreprezenta, pe p conform relaiei

39

t

x

t

i

iqdxxqtp0 0

11

n aceste condiii, munca estimat pentru un episodde furt de timp este dat n relaia

0 0

,i i

iiii TpwTpctpSE

O alta abordare in calculul distribuit este memoria virtual distribuit (DistributedShared Memory DSM).

Din nefericire mainile paralele cu memorie comun fie au memoria fizic nescalabil, fie lucreaz n regim de transfer de mesaje, lucru care face programarea complex i greoaie.

DSM ofer posibilitatea scalabilitii fr pierderea uurinei de programare.

2

1. Un sistem de tip DSM trebuie s aib cel puin un model de coeren bine definit.

2. De asemenea trebuie sa posede un mecanism explicit de blocare a accesului la date,

3. Nu toate sistemele DSM pot fi scalabile.

4. Implementarea hard-soft.

3

Unele sisteme de tip DSM sunt implementate la nivel hard, altele prin soft.

Sistemele implementate la nivel hard sunt mai rapide dar cu preul unei anumite rigiditi din punct de vedere al modelelor de coeren suportate.

Aici apar ntrebrile curente n cazul proiectrii unui sistem:

ce compromis se va face ?

cte nivele vor fi implementate hard

i cte soft

pentru a obine un sistem ct mai eficient ?.

4

n principiu, este de ateptat ca performanele aplicaiilor ce folosesc DSM s fie mai rele dect n cazul folosirii tehnicilor de transfer de mesaje, atta timp ct transferul de mesaje este o extensie direct a mecanismelor de comunicaie sistem i datorit faptului c DSM este implementat ca un strat separat ntre aplicaie i sistemul de transfer de mesaje.

Totui cteva implementri ale algoritmilor DSM au demonstrat c acesta poate fi competitiv cu transferul de mesaje n termeni de performan pentru multe aplicaii.

5

n plus dac aplicaia are un grad rezonabil de localizare relativ la accesarea datelor, ncrcarea de comunicaii este amortizat de accesri multiple n memorie, fapt ce reduce accesrile de comunicaie.

n al doilea, rnd multe aplicaii paralele / distribuite se execut n faze iar fiecare faz de calcul este precedat de o faz de schimb de date; timpul necesar schimbului de date este dictat de ncrcarea existent la nivelul comunicaiilor.

6

Sistemul

Retea Comunicatii

CPU 1

CPU n

MMUPage Mgr

: Memorie

Nod0

CPU 1

CPU n

MMUPage Mgr

: Memorie

Nod 1

CPU 1

CPU n

MMUPage Mgr

: Memorie

Nod 2

Distributed Shared Memory(exista numai virtual)

Data = read(address); write(address, data);

addresa

Memoria distribuita este simulata

Exemplu proces care scrie in memorie#include "world.h" struct shared { int a,b; };

Program Writer:main(){

int x;struct shared *p;methersetup(); /* Initialize the Mether run-time */p = (struct shared *)METHERBASE;

/* overlay structure on METHER segment */p->a = p->b = 0; /* initialize fields to zero */while(TRUE) { /* continuously update structure fields */

p >a = p >a + 1;p >b = p >b - 1;

}}

Exemplu proces care citeste din memorie

Program Reader:main(){

struct shared *p;methersetup();p = (struct shared *)METHERBASE;while(TRUE) { /* read the fields once every second */

printf("a = %d, b = %d\n", p >a, p >b);sleep(1);

}}

Memorie comuna distribuita realizata software (Virtual shared memory)

Se foloseste mecanismul de management al memoriei virtuale pentru gestiunea memorieicomune IVY (U.of Irvine), TreadMark (Wisconsin U.)

ul Single Writer vs Multiple-Writer .

tip NUMA, NORA sau clustere de calculatoare

Un exemplu simplu de memorie comunarealizata soft

Citire Date

PC A PC B

Pagina comuna Lipsa Pagina!

Calculator

Intrerupere

Protocol de tip Single Writer

Scriere datePC A PC B

Pagina comuna

Citire date

Cerere

CerereWrite back

Write back

PC gazdaW

PC A W

PC A,B

Protocol de tip Multiple Writers

Scriere date

PC A PC B

Twin

Pagina comuna

PC gazda


PC A PC B

Twin

Pagina comuna

PC gazda


PC A PC B

Twin

Pagina comuna

CerereWrite back

PC gazda

Modele de consistenta a memoriei pentru memoria

comuna distribuita implementata software (SDSM)

SDSMGestiunea implica resurse procesorImposibilitatea gestiunii intreruperiolor

- Eager Release ConsistencyMunin)- Lazy Release ConsistencyTreadMarks)- Entry Release Consistency (Midway)

Modele de consistenta relazata extinse

Numarul de mesaje trebuie redus

Eager Release Consistency

p1

p2

w(x) w(y) w(z) rel

x y z

p1

p2

w(x) w(y) w(z) rel

x,y,z



p1

p2

w(x)

w(y)

acq

acq

rel

rel

Pagina

Y modificat

X modificat

X modificat

diff

p1

p2

p3

p4acq r(x)

w(x) rel

acq w(x) rel

acq w(x) rel

Lazy Release Consistency

p1

p2

p3

p4

w(x) rel

w(x) rel

w(x) rel

r(x)

Lazy Release Consistency

acq

acq

acq

Entry Release Consistency

datele comune si obiectele de sincronizare sunt asociate

achizitia si eliberarea se executa pe un obiect de sincronizare

prin introduecerea in cache a obiectului de sincronizare

blocuilor lipsa in cache (miss) vor fi reduse prin realizarea unei asocieri intre obiect si datele comune corespunzatoare

Entry Release Consistency

p1

p2

w(x)acq S rel S

acq S w(x) r(y) rel S

S, x,y

p3w(z)acq R rel R w(z)acq R rel R

Cel mai cunoscut algoritm pentru implementarea DSM este cel al lui Li care este foarte bun pentru o clas mare de algoritmi.

n algoritmul lui Li cunoscut ca SVM spaiul comun de adrese este partiionat n pagini, iar copii ale paginilor sunt distribuite ntre gazde, folosind un protocol de tipul multipli cititori/un singur scriitor.

25

Un avantaj al algoritmului lui Li este c acesta poate fi integrat uor n memoria virtual meninut de sistemul de operare a gazdei.

Dac o pagin de memorie comun este stocat local pe o gazda ea poate fi mapatn spaiul virtual de adrese al aplicaiei de pe gazd

O accesare la o pagina inexistent (fault page) transfer controlul unui gestionar (handler ) de erori de acest tip .

26

Protocolul de meninere a coerenei sistemului este similar cu cel folosit la meninerea consistenei memoriilor cachen sistemele multiprocesor cu memorie comun.

Pentru aplicaii paralele i distribuite, DSM poate ascunde complexitatea comunicaiei fa de aplicaie

n acest tip de sisteme, DSM obine transparena total

27

Eterogenitatea ntr-un sistem distribuit apare ntr-un numr de forme.

Arhitectura hard a mainilor poate fi diferit, chiar i setul de instruciuni, reprezentarea datelor, mrimea paginilor i numrul de procesoare ale gazdei.

De asemenea sistemul de operare, limbajele de programare i compilatoarele lor, chiar i protocoalele de comunicaii pot fi definite.

28

Memoria comun distribuit n sisteme eterogene este folositoare pentru aplicaii paralele i distribuite n scopul exploatrii resurselor existente pe diverse tipuri de gazde n acelai timp.

De exemplu aplicaiile CAM ce realizeaz controlul unei linii de producie automatizate n timp real.

29

Sincronizarei

sisteme tranzacionale

31

Sicronizarea n sistemele distribuite ntr-un sistem strns cuplat, regiunile critice,

excluziunea mutual, i alte probleme desincronizare sunt rezolvate uzual folosindsemafoare i monitoare.

Aceste metode nu se pot aplica prea bine nsistemele distribuite deoarece ele sunt tipiceexistenei unei memorii comune.

Una din problemele majore n realizarea uneisincronizri este timpul, deci trebuie realizat osincronizare a ceasurilor mainilor din sistem.

32

Sicronizarea n sistemele distribuite n general un algoritm distribuit are

urmtoarele caracteristici:

1. Informaia relevant este mprtiat pediverse maini;

2. Procesele iau decizii bazndu-se peinformaiile locale;

3. Un singur punct de cdere n sistem poate fievitat;

4. Nu exist ceas comun sau o resurs care sgenereze un timp global.

33

Sicronizarea n sistemele distribuite Din primele trei puncte rezult c nu putem face

colectare centralizat de informaii.

De exemplu pentru a realiza alocarea resurselor nueste n general folosit metoda trimiterii tuturorcererilor la un singur proces care s le examineze caapoi s accepte sau s resping cererile bazndu-se pepropriile tabele de date.

Aceasta deoarece ntr-un sistem mare s-ar realiza osuprancrare a respectivului proces, fr a lua nconsiderare de cazul n care acest proces s-ar bloca ide implicaiile acestui fapt.

34

Ceasuri logice Indiferent ct de precise ar fi ceasurile CMOS,

existente pe diverse staii de lucru ce opereazntr-un sistem distribuit, totui exist diferenen timp ntre ele.

Atta timp ct lucreaz numai cu procese ifiiere de pe acea main deviaia referinei detimp nu deranjeaz, ns la un sistem distribuitacest lucru conduce la pierderea sincronizriiglobale.

O modalitate de a rezolva problema a fostpropus de Lamport.

35

Ceasuri logiceDe fapt problema este mai complex.

Nu se poate renuna complet lasincronizarea temporal dar se poateconveni ntre maini c este ora X chiardac nu este exact acea or la toate.

Pentru clasele de algoritmi care suportaceast metod de lucru acest tip de ceaseste denumit ceas logic.

36

Ceasuri logice - LamportPentru a realiza sincronizarea ceasurilor logice

Lamport a definit o funcie de tipul "s-antmplat nainte" notat cu .

De exemplu a b, a s-a ntmplat nainte de b.

Aceast relaie se poate observa n dou cazuri:

Dac avem a i b evenimente aparinnd aceluiaiproces i a apare nainte de b atunci ab esteadevrat.

Dac a este un eveniment al unui mesaj transmisde un proces i b este un eveniment al unui mesajrecepionat de alt proces de asemenea ab esteadevrat.

37

Ceasuri logice - LamportDac avem nevoie de o cale de a msura timpul

pentru fiecare eveniment a atunci acestuia i sepoate asigna o valoare temporal T(a), cuproprietatea c

ab implic T(a)

38

Ceasuri logice - Lamport

1. Dac a apare dup b n acelai proces:

T(a) >T(b);

2. Dac a i b reprezint emiterea i recepia unuimesaj T(a)

39

Ceasuri fizice Din motive ca eficiena i redundan se

folosesc ceasuri fizice multiple, lucru carepune dou probleme:

Cum s realizm sincronizarea lor cu lumeareal?

Cum s le sincronizm ntre ele?

40

Ceasuri fizice n primul caz se folosete sincronizarea:

cu frecvena de alimentare a reelei

prin recepia semnalelor generate de staii pe undescurte

prin recepia semnalelor generate prin satelit.

Fiecare main are un numrtor intern care produceo ntrerupere de cte H ori pe secund. La depirevariabila temporal este incrementat.

S notm cu T aceast valoarea timpului intern i cuTp(t) timpul notat de maina p atunci cnd timpul realeste t, deci Tp(t)=t pentru orice p i t.

41

Ceasuri fiziceDin punct de vedere matematic dac exist o

constant care satisface relaia de mai josatunci se consider c lucrm n cadrulspecificat. este specificat de fabricani idenumit rata maxim de eroare.

Dac dou ceasuri au eroarea n direcii inversefa de timpul real la timpul t dup ce au fostsincronizate atunci se vor deprta cu 2t.

.

Sisteme distribuite - cursuri

Documents

Transcript of Sisteme distribuite - cursuri