Scalabilitatea

Scalabilitatea reprezinta posibilitatea extinderii dimensiunii sistemului fara a schimba principiul arhitectural, respectiv softul de sistem si de aplicatie. Pentru a diminua efectele negative ale cresterii dimensiunii sistemului asupra performantei (prin reducerea timpilor de raspuns, solicitarea mai intensa a serviciilor), se folosesc diferite tehnici cum ar fi: replicarea datelor, servere multiple, pastrarea intr-o memorie cache (implementata pe cale soft) pe calculatorul clientului a unei copii a datelor accesate de la distanta in vederea unei eventuale utilizari viitoare. Desigur ca aceasta din urma tehnica duce la reducerea traficului, dar ridica problema consistentei datelor. Modificarea datelor din memoria cache a unei statii de lucru trebuie sa apara si la server, respectiv la ceilalti clienti care mai au aceste date in cache-ul propriu.

1.2 Deschiderea presupune publicarea interfetelor hard si soft, a standardelor de comunicatie, astfel incat sistemul sa poata fi extins cu noi elemente hard si servicii. Din aceasta cauza structura soft a sistemelor distribuite nu mai este monolitica ca la sistemele centralizate, ci fiecare serviciu furnizeaza propria interfata catre programele de aplicatie (fig.1.5). Se constituie astfel servicii deschise, care pot fi adaugate peste kernelul sistemului de operare in functie de necesitati.

Transparenta consta in ascunderea separarii componentelor in fata utilizatorului, care, desi este constient de existenta mai multor calculatoare in sistem, nu trebuie sa cunoasca distributia programelor si datelor, adica a obiectelor informationale pe acestea. Transparenta are mai multe forme: Transparenta accesului (la fel se acceseaza obiectele locale si cele aflate la distanta)

Transparenta locatiei (nu trebuie cunoscut locul obiectului accesat)

Transparenta migratiei (este permisa mutarea obiectului in cadrul sistemului fara ca acest lucru sa afecteze utilizatorul)

Transparenta scalarii (este permisa extinderea gradata fara a schimba arhitectura sistemului)

Transparenta concurentei (mai multe procese pot opera concurent utilizand resurse partajate, fara a intra in conflict)

Transparenta replicarii (pot exista obiecte replicate fara ca utilizatorul sa cunoasca acest lucru)

Transparenta defectarii (defectul ramane ascuns in fata utilizatorului)

Transparenta performantei (sistemul poate fi reconfigurat in vederea echilibrarii incarcarii)

Repetorul - transerul semnalului analogic

- Puntea - muta entitatile de date

- Routerul- transferul entitatilor de date (sub forma de pachete)

- Poarta- transferul entitatilor de date (sub forma de pachete)

- Retele cu difuzare- date

- Retele punct-la-punct- date

Comutarea de circuite- date

- Comutarea de mesaje- date

Comutarea de pachete- pachete

Comutarea de circuite (circuit switching) stabileste o cale unica intre sursa si destinatie pentru fiecare transmisie, care se desface doar dupa ce toate datele au fost transferate. Aceasta inseamna ca pana la eliberarea caii de comunicatie ea nu poate fi folosita de alte noduri care vor sa transmita, chiar daca traficul realizat ramane sub posibilitatile liniilor

Comutarea de pachete (packet switching) elimina neajunsul metodei anterioare prin divizarea mesajului in pachete scurte de lungime fixa, care se transmit de la nod la nod pana la destinatie. Aici mesajul este reasamblat din pachetele constituente. Este posibil ca pachete apartinand la acelasi mesaj sa urmeze cai diferite si sa nu ajunga la nodul final in ordinea initiala. Aceasta metoda este cea mai avantajoasa din punctul de vedere al incarcarii retelei de comunicatie, iar pachetele care provin din mesaje scurte nu mai sunt supuse la asteptari indelungate la elementele de comutare, ele se pot transmite intercalat printre celelalte 727e48h pachete. Datorita avantajelor sale, comutarea de pachete este folosita in majoritatea retelelor actuale

2.4 Nivelul fizic (1) contine circuitele electronice si componentele mecanice pentru conectarea la mediul de comunicatie. Rolul lor este de a transmite secvente de biti intre calculatoarele interconectate, fiind responsabile de reprezentarea adecvata mediului a bitilor de "0" si "1".

Serviciul fara conexiune este mult mai simplu si nu necesita timp suplimentar, fiind adecvat la transferul mesajelor scurte.

La randul sau, fiecare din cele doua tipuri de servicii de comunicatie poate fi:

-fiabil sau sigur (nu se pierd date), daca se transmite catre emitator o confirmare a receptionarii datelor

-nefiabil sau nesigur (este posibila pierderea, duplicarea, alterarea datelor), daca nu se foloseste confirmarea.

Protocolul TCP

La nivel transport protocolul TCP/IP prevede utilizarea adreselor de port, care sunt numere de 16 biti. De exemplu, pentru transferul de fisiere prin FTP se utilizeaza portul cu numarul 21 (exprimat in zecimal), iar pentru Telnet 23. La acest nivel aplicatiile pot solicita unul din serviciile TCP sau UDP.

(Transmission Control Protocol) reprezinta un serviciu orientat pe conexiune si fiabil. El este folosit in cazul aplicatiilor ca FTP (File Transfer Protocol), Telnet, e-mail, DNS (Domain Name System) etc Se foloseste la nivelul Transport

Protocolul UDP

La nivel transport protocolul TCP/IP prevede utilizarea adreselor de port, care sunt numere de 16 biti. De exemplu, pentru transferul de fisiere prin FTP se utilizeaza portul cu numarul 21 (exprimat in zecimal), iar pentru Telnet 23. La acest nivel aplicatiile pot solicita unul din serviciile TCP sau UDP.

(User Datagram Protocol) este un serviciu fara conexiune si nefiabil, ordinea de livrare a datagramelor nefiind garantata. Se foloseste de catre aplicatii putin pretentioase, cum ar fi servicii de timp, FTP simplificat etc. SE foloseste la nbivelul Transport

La nivel retea se utilizeaza protocolul IP (Internet Protocol). Acesta ofera un serviciu fara conexiune si nefiabil, fiind posibila pierderea, intarzierea, duplicarea sau modificarea ordinii pachetelor la livrare. De aceea, se spune ca acest serviciu depune doar efortul maxim pentru livrare, dar fara a garanta acest lucru ("best-effort service"). Protocolul IP foloseste adrese IP, care sunt numere de 32 de biti.. Se fol la nivelul retea

. Ce rol are protocolul ARP?

Adresele simbolice sunt translatate in adrese IP de catre serviciul numelor de domeniu DNS (Domain Name System). La nivelul unei retele concrete fizice, de exemplu Ethernet, acestea sunt convertite mai departe in adrese de interfata de retea (de 48 de biti) de catre protocolul ARP (Address Resolution Protocol). Corespondentele de tip <adresa IP, adresa Ethernet> ale numelor rezolvate sunt pastrate intr-un cache de fiecare calculator gazda. Daca numele cerut nu se afla in cache, atunci se difuzeaza adresa IP catre toate calculatoarele din reteaua locala. Cel care se recunoaste pe baza adresei va returna adresa sa Ethernet (de interfata de retea). Daca destinatia nu se afla in aceasta retea, pachetul de date se trimite pentru a fi dirijat mai departe la poarta sau ruter, care are cate o adresa IP pentru fiecare retea la care e conectat.

Compunerea datelor (marshalling) reprezinta procesul de asamblare a unei multimi de date intr-o forma potrivita pentru a fi transmise intr-un mesaj. La receptie se face operatia inversa, de descompunere. Aplatizarea datelor si translatarea lor intr-o reprezentare externa se poate face sub forma explicita in programul emitator, sau automat de catre un compilator de interfata pe baza specificarii tipului de date.

Comunicatie sincrona, cand la fiecare mesaj se face sincronizarea proceselor. Operatiile Send si Receive sunt cu blocare, adica fiecare operatie se blocheaza pana nu se executa cealalta.

Comunicatie asincrona, la care operatia Send este fara blocare, pe cand Receive poate fi cu blocare sau fara blocare , acest din urma caz presupunand existenta unui buffer la receptie.

O varianta cu trei apeluri a protocolul invocare-raspuns, implementata de unele sisteme de operere, foloseste urmatoarele operatii (fig.3.3):

PROCEDURE DoOperation (serverPort: PortId; request: Message; VAR reply:Message);

PROCEDURE GetRequest (serverPort: PortId; VAR request:Message);

PROCEDURE SendReply (clientPort: PortId; reply:Message);

Procedura DoOperation se foloseste pe partea de client pentru transmiterea cererii si preluarea confirmarii, fiind cu blocare pana la receptionarea acesteia din urma. Argumentele folosite in operatie sunt identificatorul portului serverului, mesajul in sine si indicarea locului (buffer-ului) pentru incarcarea raspunsului. Procedura GetRequest se apeleaza pe partea de server pentru preluarea cererii de serviciu, iar SendReply efectueaza transmiterea mesajului de raspuns.

Protocol R (request), cand nu exista confirmare din partea serverului.

3.6 Protocol RR (request-reply), cand mesajul de raspuns al serverului este considerata confirmare de catre client.

3.7 Protocol RRA (request-reply-acknowledge reply), cand raspunsul serverului este la randul sau confirmat de catre client. Confirmarea contin requestId-ul din mesajul de raspuns, ceea ce semnifica pentru server ca toate mesajele de raspuns cu requestId mai mic au fost deja receptionate.

Difuzarea in grup fiabila, care presupune ca emitatorul sa primeasca cate o confirmare de la fiecare memsbru al grupului. Daca unele confirmari nu sosesc nici dupa un numar de retransmiteri, procesele respective sunt eliminate din grup. Daca emitatorul se defecteaza in timpul transmiterii, difuzarea nu va fi atomica. In acest caz responsabilitatea trebuie preluata de unul din destinatari. De aceea, dupa ce a dat confirmarea, un destinatar monitorizeaza emitatorul (prin transmiterea unui mesaj de control si asteptarea raspunsului) si daca constata ca e defect va prelua continuarea operatiei de difuzare. Uneori, pntru a aduce la cunostinta destinatarilor ca difuzarea a luat sfarsit, se foloseste notificarea terminarii de catre emitator, ceea ce inseamna insa o noua difuzare.

IN cazul difuzatii fiabile emitatorul primeste raspuns de la destnatar sau destinatari iar incazul difuzrii nefiabile nu se primeste nici n raspuns

. In UNIX comunicatia dintre doua procese se bazeaza pe utilizarea unei perechi de socluri (sockets) in procesele implicate. Soclul se creeaza cu un apel de sistem socket, avand ca argumente domeniul (de exemplu Internet), tipul (sir sau datagram) si protocolul (TCP sau UDP). Apelul returneaza un descriptor pentru referinte ulterioare. Soclul se leaga de o adresa de soclu de forma <nr_port, adresa_IP> cu apelul bind.

necesitatea aplatizarii structurilor de date pentru a fi transmise. Intrucat interfata RPC nu este neaparat convenabila pentru programele clientului, utilizarea serviciilor de catre programul de aplicatie e ajutata de pachetul utilizator (fig.4.1). Acesta are rolul de a ascunde RPC fata de programul de aplicatie. Astfel programatorul nu va lucra in limbajul de definire a interfetei RPC.

Maybe. Nu se reia invocarea in cazul in care mesajul de raspuns nu a fost receptionat, ca urmare este doar posibil ca procedura la distanta sa fi fost executata. Aceasta metoda nu se utilizeaza in practica.

3 At-least-once. Mesajul de invocare se retransmite, dar nu se aplica filtrarea duplicatelor, deci clientul nu va sti cate apeluri au fost facute de fapt (cel putin unul in mod sigur). Ca urmare se reexecuta procedura serverului, metoda fiind utilizabila numai daca operatiile serverului sunt idempotente.

4 At-most-once. Fiind facuta filtrarea duplicatelor, operatia serverului nu se reexecuta, dar se retransmite raspunsul. Daca clientul receptioneaza un raspuns, atunci se garanteaza ca procedura server a fost executata o singura data. Aceasta metoda este folosita in mod uzual.

Programul client foloseste o procedura cotor (stub procedure) la fiecare apel, care converteste apelul local intr-un apel la distanta conform definitiei de interfata.

Sarcinile principale ale procedurii cotor sunt:

1. compunerea argumentelor

2. impachetarea argumentelor in mesaj impreuna cu un identificator de procedura (practic un numar de ordine)

3. descompunerea raspunsului

Legarea inseamna maparea numelui textual al serviciului apelat intr-un identificator de comunicatie al serverului. Aceasta mapare se efectueaza de un serviciu de nume numit binder. In mod tipic un binder include urmatoarele proceduri

Pe baza definitiei de interfata compilatorul de interfata (rpcgen) va genera:

1. procedurile cotor ale clientului

2. procedura main a serverului, dispecerul, procedurile cotor ale serverului

3. procedurile de compunere si descompunere

4. un fisier header cu constantele si tipurile comune clientului

Metoda RPC asincron permite lansarea de cereri consecutive la server fara asteptarea raspunsului la apelul precedent . Astfel nu se blocheaza clientul, se reduce timpul si pot fi emise cereri consecutive catre mai multe servere. Cererile consecutive la acelasi server pot fi insiruite imtr-un buffer la client si trimise impreuna printr-o singura comunicatie.

Managerul de procese, cu rol de creare a proceselor si de efectuare a unor operatii de nivel scazut asupra acestora.

1. Managerul de fire de executie, care asigura crearea, sincronizarea si planificarea firelor.

2. Managerul de comunicatie, care asigura comunicatia intre firele atasate la procese locale.

3. Managerul de memorie, pentru gestionarea memoriei fizice, a memoriei virtuale si a memoriilor cache.

4. Supervizorul, care serveste la dispecerizarea intreruperilor, a apelurilor de sistem prin capcane si a exceptiilor.

5.2 procesul poate fi considerat ca fiind format dintr-un mediu de executie si unul sau mai multe fire de executie

la server (fig.4.3), cand fiecare fir receptioneaza cereri prin aclasi port si efectueaza aceeasi procedura de prelucrare.

la client (fig.4.4), cand primul fir pune rezultatele intr-un buffer, de unde al doilea le preia si efectueaza un RPC la server, astfel primul neffind blocat cu asteptarea raspunsului

. O solutie intermediara (numita copy-on-write), menita sa asigure un plus de eficienta, prevede doar copierea logica (adica partajarea) spatiului, copierea fizica fiind facuta atunci cand unul din procese efectueaza o operatie de scriere in spatiul respectiv. Porturile de comunicatie nu pot fi mostenite sau partajate.

identificatorul de comunicatie, pentru a desemna portul serverului care gestioneaza resursa identificatorul serviciului (necesar daca nu e alocat cate un port fiecarui server

Capabilitati, cand accesul este permis numai daca procesul solicitant dispune de capabilitatea ceruta (capabilitatea fiind un identificator greu de falsificat) liste de control, cand fiecare resursa dispune de cate o lista cu domeniile care pot avea aces si drepturile corespunzatoare

Transferul de mesaje intre doua procese aflate pe calculatoare diferite este asigurat de kernelul sistemului de operare prin primitivele de tip Send si Receive. In acest caz invocarea necesita si comunicatie prin retea, ceea ce afecteaza in mod hotarator performanta RPC (fig.4.6). Intarzierea introdusa creste desigur in functie de lungimea datelor de transmis (argumente, rezultate), fiind mai mare daca aceste date trebuie divizate pe mai multe pachete

Memoria virtuala reprezinta un concept pentru extinderea dimensiunii memoriei principale, fiind implementata transparent prin combinarea memoriei principale cu memoria de masa (dispozitivul de stocare, in particular discul hard).

Rolul unui seviciu de fisiere este de a permite organizarea, citirea/ scrierea /stergerea, gestionarea numelor, protectia si partajarea fisierelor

Serviciul plat de fisiere, care prmite efectuarea de operatii de citire/scriere/stergere asupra fisierelor. Pentru fiecare fisier nou genereaza cate un identificator unic de fisier (UFID), care va fi folosit mai tarziu la orice referire ulterioara.

6.3 Serviciul de directoare, care efecueaza maparea intre nume textual si UFID-ul fisierului, efectuand cautarea dupa identificator pe baza numelui de fisier. El permite crearea/modificarea intrarilor in directoare, fisierele directoare fiind pastrate in serviciul plat de fisiere (structura ierarhica de fisiere este asigurata de modulul client). Ca urmare serviciul de directoare reprezinta un client pentru serviciul plat de fisiere. Serviciul de directoare face si verificarea autorizarii utilizatorului pentru acces.

6.4 Modulul client, care ruleaza pe fiecare calculator, ofera o interfata unica catre utilizatori pentru operatii cu fisiere si care ascunde componentele de nivel scazut ale sistemului. Modulul client este responsabil si de localizarea fisierelor aflate la distanta. El poate gestionarea unui cache la client pentru eficientizarea acceselor.

In general fiecare calculator din sistemul NFS are instalate module client si server. Fiecare client isi poate construi propria ierarhie de fisiere in care monteaza de la distanta (remoute mount) fisiere aflate pe alte calculatoare server

Comunicatia cu serverul se face prin RPC, interfata NFS a serverului continand operatii similare cu cele definite la punctul 6.3 (lookup, create, remove, getattr, setattr, read, write, rename etc

Serviciul de nume se apeleaza de catre clienti pentru a obtine informatii despre resurse sau obiecte, atunci cand se da numele acestora. Informatiile obtinute pot fi adrese sau, in general, atribute ale unui utilizator, calculator, domeniu de retea, serviciu, fisier

Asocierea dintre numele si atributele unui obiect se numeste legare

Operatia de returnare a atributelor pe baza numelui poarta numele de rezolvarea (rezolutia) numelui (name resolution

Procesul de localizare a datelor printre mai multe servere pentru rezolvarea unui nume se numeste navigare
7.4 Serverul SNS pastreaza inregistrari de forma

< Nume > < Tip, Valoare >

Procedurile oferite de SNS permit cautarea dupa atribute pe baza numelui, precum si efectuarea, respectiv stergerea unei inregistrari in baza de date:

Navigare cu difuzare in grup (multicast), cand UA difuzeaza numele de rezolvat tuturor serverelor de nume, si numai cel care pastreaza atributele va raspunde.

Sistemul DNS constituie serviciul de nume utilizat de Internet. Numele sistemului sunt nume de domenii, de exemplu dcs.qmw.ac.uk. Ele au o organizare ierarhica si pot fi partitionate organizational (de exemplu cu terminatiile com, edu, gov, mil, ) sau geografic (de exemplu terminate in us, uk, fr, ro, ).

Baza de date DNS este distribuita pe o retea de servere (fig.7.6). Fiecare server este responsabil de cate o zona (indicata in paranteza pe fig.7.6), pentru care pastreaza datele de mai jos:

atributele pentru numele din zona respectiva (mai putin subdomeniile administrate pe un alt server)

1. numele si adresele serverelor care furnizeaza date autoritare din zona

2. numele si adresele serverelor autoritare din subzonele delegate

3. parametri de management ai zonei (legate de memorii cache, replicare)

Ceasuri fizice (physical clocks), care contorizeaza timpul derivat de la un oscilator cu frecventa fixa si stabila.

8.2 Ceasuri logice (logical clocks), care urmaresc doar stabilirea unei ordini a evenimentelor

Timpul international atomic

Timpul astronomic

Timpul universal coordonat

Metoda lui Cristian se bazeaza pe interogarea unui server de timp cu receptor UTC. Un proces P care doreste sa-si sincronizeze ceasul, solicita printr-un mesaj m_r timpul de la un server de timp S fig.8.1). Serverul va insera in mesajul de raspuns m_t timpul t pe care-l arata ceasul sau propriu. Ca urmare P isi va seta ceeasul la un timp estimat dat de

t_P = t + T_round/2

unde T_round este intervalul de timp dintre momentul emiterii lui m_r si momentul receptionarii lui m_t. Daca timpul de transmisie dintre P si S este de forma

T_trans = min + x (x³

unde min reprezinta timpul de transmisie fara incarcare de trafic si conflicte, atunci intervalul in care e situat timpul estimat de catre P va fi

t_P I [ t + min,    t + T_round min ]

si

Dt_P = ( t + T_round min ) ( t min ) = T_round 2 min

Acuratetea este deci de ( T_round/2 min ), fiind cu atat mai buna, cu cat T_round este mai mic. Pentru a tolera caderea lui S, s-a propus difuzarea mesajului m_r la un grup de servere sincronizate UTC si utilizarea primului raspuns primit.

Algoritmul Berkeley asigura sincronizarea interna intre un grup de calculatoare, unul fiind desemnat master, restul fiind considerate slave. Masterul efectueaza periodic interogarea calculatoarelor slave si face media timpilor obtinuti (inclusiv al sau), apoi trimite fiecarui slave cantitatea cu care trebuie sa-si ajusteze ceasul. Pentru eliminarea erorilor introduse de calculatoarele cazute sau cele care furnizeaza timpi falsi, se efectueaza o medie toleranta la defecte, alegand doar timpii car nu difera intre ei cu mai mult decat o valoare maxima specificata. De asemenea, pentru mentinerea acuratetii se elimina citirile care corespund unui timp de transmisie mai mare decat o valoare maxima stabilita dinainte

-un server primar, sincronizat la UTC

servere secundare, sincronizate la serverul primar

statii de lucru ale utilizatorilor, sincronizate la servere secundare

sincronizarea simetrica, cand o pereche de servere schimba intre ele mesaje care poarta informatii de timp, metoda aceasta oferind cea mai mare acuratete

8.9 In sistemele distribuite apare adesea necesitatea ordonarii evenimentelor. Aceasta se bazeaza pe urmatoarele principii:

doua evenimete in cadrul unui proces se considera ca se succed in ordinea aparitiei

evenimentul emiterii unui mesaj precede evenimentul receptiei sale

Cu aceste ipoteze, se poate defini ordonarea cauzala a evenimentelor, folosind o relatie de tip happened-before (notata cu " "):

HB1) daca xista procesul p, in care evenimentul x a aparut inaintea lui y, atunci x y

HB2) pentru orice mesajul m transmiterea apare inaintea receptiei, adica
send(m) receive(m)

HB3) daca x y si y z, atunci x z

Relatiile HB pot fi implementate cu ajutorul ceasului logic (al lui Lamport), care reprezinta un contor soft monoton crescator, fara nici o legatura cu ceasul fizic. Fiecare proces p are propriul ceas logic si marceheaza un eveniment din cadrul sau cu stampila de timp (timestamp) C_p(a), dupa urmatoarele reguli:

LC1) C_p este incrementat inaintea oricarui eveniment din p (C_p := C_p + 1)

LC2) a. daca p transmite mesajul m, acesta transporta stampila de timp t = C_p

b. daca q receptioneaza (m, t), atunci se fixeaza C_q := max (C_q, t) si se aplica LC1 pentru marcarea evenimentului receptiei

Pentru a putea face o ordonare totala, s-a introdus stampila de timp globala data de perechea (T_a, p_a), unde T_a reprezinta stampila de timp locala a evenimentului a in cadrul procesului p_a

Excluderea reciproca (mutual exclusion) se bazeaza pe urmatoarele cerinte privind intrarea in sectiunea critica (SC):

ME1 (siguranta): cel mult un proces se poate afla la un moment dat in SC

ME2 (supravietuirea): un proces care solicita intrarea im SC va putea eventual primi accesul

ME3 (ordonarea): accesul in SC se acorda in ordinea "happened-before"

Algoritmul cu server central. Cererile de intrare in SC se adreseaza unui server, care va acorda dreptul de acces (tokenul) procesului urmator din coada de asteptare (fig.8.6). Daca serverul cade. atunci trebuie sa aiba loc un proces de alegere a unui nou server (dintre clienti

Algoritmul lui Ricart si Agrawala. Un proces p_i care solicita acces in SC difuzeaza o cerere care poarta stampila de timp globala <T, p_i>, unde T reprezinta valoarea ceasului sau logic. El va putea intra in SC numai daca a adunat toate raspunsurile de la celelalte procese. Un proces furnizeaza raspuns la o cerere numai daca el nu se afla si nu a solicitat intrarea in SC, sau daca asteapta sa intre in SC, dar stampila sa de timp este mai mare decat a solicitantului raspunsului. Un exemplu este aratat in figura 8.7. Caderea oricarui proces duce la blocarea algoritmului.

Algoritmul in inel. Procesele, aranjate intr-un inel logic paseaza tokenul de la unul la altul, acesta fiind retinut de procesul care a solicitat acces in SC (fig.8.8). Acest algoritm nu satisface cerinta ME3. Daca un proces cade, e necesara reconfigurarea sistemului.

Algoritmul "bully". Principiul este de a alege dintre supravietuitori procesul cu cel mai mare identificator. Pentru a incepe algoritmul, un proces initiator transmite mesajul "election" catre toate procesele cu identificatori mai mari si apoi asteapta un raspuns ("answer"). Daca nu soseste nici un raspuns, atunci el se considera a fi cel ales si transmite mesajul "coordinator" catre toate procesele cu identificatori mai mici. Un exemplu este dat in figura 8.9, unde se alege ca si coordonator procesul p₂, dupa caderea succesiva a lui p₄ si p₃.

8.17 Algoritmul in inel. Se urmareste selectarea procesului cu cel mai mare identificator prin transmiterea mesajelor in inel (fig.8.10). Procesul care incepe algoritmul devine "participant" si transmite mesajul "election" cu identificatorul sau. Un proces care receptioneaza mesajul, compara idenficatorul din mesaj cu al sau si daca e mai mare, transmite mesajul mai departe. In caz contrar va transmite mai departe mesajul inlocuind identificatorul din el cu cel al sau. Daca un proces primeste inapoi propriul identificator, atunci devine "coordinator" si trimite mesajul "elected" prin care isi anunta identitatea de castigator.

Replicarea in sistemul distribuit inseamna gestionarea de copii ale datelor si ale altor resurse. Prin replicare se urmareste atingerea mai multor scopuri:

1. imbunatatirea performantelor, prin existenta de memorii cache la clienti cu copii ale datelor pentru accesare rapida, respectiv prin distribuirea de copii la mai multe servere

2. cresterea disponibilitatii, prin posibilitatea solicitarii unui serviciu de la un server alternativ, daca primul server a cazut (disponibilitatea este data de A=1 pn, unde p reprezinta probabilitatea defectarii unui server din totalul de n)

3. toleranta la defecte, asigurata de prelucrarea in paralel a cererilor pe mai multe servere

transparenta, ceea ce inseamna ca clientii nu trebuie sa fi constienti de existenta ,ai multor copii fizice in sistem

consistenta, ceea ce presupune ca copiile replicate sa fie identice

Modelul asincron. Operatiile clientului se satisfac de catre serverul local, care comunica cateodata (eventual periodic) actualizarile celorlalte servere. Astfel controlul se reda clientului imediat dupa prelucrarea locala. Datorita modului de actualizare asincrona, copiile de pe diferite servere nu sunt tot timpul consistente. De exemplu, un tabel de corespondenta replicat pe mai multe servere poate diferi ca ordine si continut la doi utilizatori diferiti

9.5 Modelul sincron. Se efectueaza actualizarea imediata a cererilor clientilor pe toate serverele, ceea ce duce la ordonarea totala a acestora. Numai dupa procesarea cererilor pe toate serverele se da inapoi controlul clientului. Fiind efectuata actualizarea imediata la toate serverele, se asigura consistenta stricta, dar sistemul este mai lent decat la tehnica precedenta.

Modelul general de gestionare a datelor replicate este aratat in figura de mai jos. Cererile clientilor (C) sunt adresate componentei front-end (FE), care poate fi un proces sau un pachet utilizator. Acesta comunica prin transfer de mesaje cu managerii de replici (replica managers RM), care reprezinta procese ce contin replicile si efectueaza direct operatii asupra lor. Cererile clintilor pot fi numai de citire (read) sau de actualizare (update).

Arhitectura gossip (fig.9.2). Fiecare FE comunica cu un singur RM, iar managerii schimba intre ei mesaje "gossip" (=barfa) pentru a transmite actualizarile.

Modelul copiei primare (fig.9.3). La fiecare actualizare FE comunica cu acelasi server primar.

Editorul partajat (fig.9.4). Asigura colaborarea utilizatorilor dintr-un grup (groupware). Fiecare proces are atat rol de client, cat si de RM, pe langa care exista un modul FE

Ordonarea totala. Se asigura daca oricare ar fi doua cereri r1 si r2, la toti RM ori r1 e procesat inaintea lui r2, ori r2 inaintea lui r1. Asemenea exemple de cereri total ordonate sunt t1 si t2 in figura 9.5. (Este de mentionat ca ordonarea totala nu implica si cauzalitatea.)

Fig.9.5.

Ordonarea cauzala. Daca r1 a avut loc inaintea lui r2, atunci r1 trebuie prelucrat inaintea lui r2 la toti RM. Exemple sunt cererile c1 si c2 din figura 9.5.

Fig.9.6.

Ordonarea sincronizata. Daca r1 este ordonat sincronizat, atunci el trebuie procesat ori inaintea lui r2 la toti RM, ori dupa r2 la toti RM, indiferent de ordonarea declarata a lui r2. Un exemplu este ordonarea sincronizata a cererii s din figura 9.6 in raport cu c1 si t1.

Pentru implementarea cerintelor de ordonare a cererilor exista mai multe tehnici.

a) Implementarea ordonarii totale

B ) Implementarea ordonarii cauzale

Se spune ca un mesaj de cerere este stabil la un RM, daca toate cererile precedente lui, conform criteriului de ordonare, au fost deja procesate.

Implementarea ordonarii totale se realizeaza prin atribuirea de identificatori total ordonati cererilor transmisi de FE-uri catre RM-uri. Exista doua metode:

Toate cererile se trimit unui proces secventor, care atribuie acestora identificatori in ordine crescatoare si le transmite mai departe catre RM-uri. Aceasta metoda se utilizeaza de exemplu la protocolul ISIS ABCAST (causally and totally ordered multicast). (ISIS reprezinta o implementare a serviciilor bazate pe grupuri de procese, care prezinta o interfata de programare, sub forma unei librarii, in varful sistemului de operare UNIX.)

Identificatorii se atribuie pe baza de acord distribuit. Algoritmul se poate urmari pe figura 9.8

FE transmite cererea cu un identificator temporar catre toate RM-urile.

Fiecare RM raspunde cu un identificator propus, care este egal cu

max +1+i/N

FE colecteaza propunerile si alege identificatorul maxim agreat, pe care il transmite RM-urilor. Acestea isi vor reorganiza cozile de retinere, daca e necesar.

9.15 Implementarea ordonarii cauzale se face cu stampile de timp vectoriale la fiecare RM. O astfel de stampila de timp VT_i reprezinta o arie de numere, cate unul pentru fiecare RM, care arata cate actualizari au fost facute din solicitarea fiecarui RM la nodul care pastreaza stampila (fig.9.9). Fiecare RM pastreaza un vector care reflecta propria versiune a datelor (de exemplu a unui tabel de corspondenta), iar fiecare FE pastreaza vectorul care reprezinta ultima versiune citita. De exemplu, pentru situatia din figura, daca FE are vectorul (2, 3, 4) si citeste o data de la RM1, atunci in urma unificarii vectorilor, va avea (3, 4, 4). Pentru implementarea ordonarii cauzale, trebuie respectate urmatoarele reguli:

1. FE are voie sa citeasca doar de la o versiune cel putin la fel de avansata ca cea a ultimei citiri

2. Actualizarea unei replici se poate face doar dupa ce aceesta contine toate actualizarile anterioare

Obiectul (object) reprezinta o entitate software autonoma, care incapsuleaza date si codul operatiilor posibile asupra acestora

Obiectele similare apartin unei clase, prin care se specifica variabilele si implementarea metodelor, precum si semnatura corespunzatoare fiecarei metode

Clasele sunt organizate ierarhic, permitand mostenirea datelor si metodelor clasei parinte, la care se pot adauga eventuale extensii

Invocarea unei metode trebuie fauta prin trimiterea unui mesaj la distanta, operatie care se numeste Remote Method Invocation (RMMesajul trebuie sa contina un identificator al obiectului aflat la distanta (ROID - Remote Object Identificator). Se impune ca RMI sa fie transparent, adica un obiect trebuie sa fie capabil de invocarea unui alt obiect indiferent daca acesta este local sau se afla la distanta. Pentru aceasta, fiecare obiect la distanta trebuie sa dispuna de un proxy local, care se comporta ca un obiect local fata de cel care invoca, dar in loc sa execute metoda, transmite mesajul mai departe obiectului la distanta. Obiectul destinatie astfel accesat are un obiect skeleton (schelet), a carei clasa are ca si metode procedurile cotor server

Desfasurarea unui RMI se poate urmari pe figura 10.4, pe care se identifica urmatorii pasi:

1. obiectul X invoca proxy-ul local

2. metoda cotor a proxy-ului compune ROID-ul, numele metodei si argumentele intr-un mesaj

3. modulul de comunicatie transmite mesajul de cerere (Request), care e receptionat de modulul de comunicatie al destinatiei

4. dispecerul, pe baza ROID-ului si a numelui metodei, invoca o metoda cotor a skeleton-ului obiectului A

5. skeleton-ul descompune argumentele si invoca metoda corespunzatoare din obiectul A

6. rezultatul se compune de skeleton si se transmite intr-un mesaj de raspuns (Reply)

7. proxy-ul descompune raspunsul si il furnizeaza clientului

Obiectele sistemului distribuit sunt in general puternic interconectate, invocandu-se unul pe altul prin aceste conexiuni, ceea ce ridica probleme de migratie si replicare. O alta problema este cea a obiectelor partajate din aplicatiile multiutilizator (de exemplu in figura 10.5, obiectele la distanta O1 si O2 partajeaza obiectul local O3). In primul rand, pentru a mentine consistenta obiectelor partajate, metodele sale trebuie sa fie atomice. Pe langa aceasta, poate fi necesar ca informatia sa fie de lunga viata, adica sa existe obiecte persistente care supravietuiesc si daca nu se mai lucreaza cu ele. (In general, pentru a economisi memorie, obiectele care nu mai dispun de referinte sunt distruse de un colector de gunoaie.) Obiectele persistente se pastreaza sub forma aplatizata pe disc si la nevoie se activeaza, respectiv se pasivizeaza in mod transparent.

CORBA (Common Object Request Broker Architecture) constituie un standard pentru sisteme distribuite deschise bazate pe interfete orientate pe obiecte. Interfetele obiectelor sunt definite in IDL, permitand clientilor si obiectelor sa fie implementate in diferite limbaje. Clientii in CORBA nu sunt neaparat obiecte, ei pot fi orice fel de programe.

Componentele arhitecturii CORBA sunt ilustrate in figura 10.7. Clientul utilizeaza cotoare client, la fel ca la arhitectura client-server, cotoarele server fiind incluse in skeleton-ul IDL. Uneori clientul necesita invocarea unui obiect a carui interfata nu a fost cunoscuta in momentul compilarii si deci nu dispune de un cotor pentru acesta. Pentru asemenea cazuri, CORBA furnizeaza o interfata de invocare dinamica, care permite legarea dinamica a mesajelor clientului in timpul rularii. Termenul de implementarea obiectului (object implementation) se refera la un fisier executabil care contine programul de executat in cadrul procesului server. Implementarea unui obiect consta din declaratiile variabilelor, codul metodelor si un program main. Cand implementarea unui obiect este activata, atunci se executa programul main, care creeaza o instanta a obiectului (folosind un constructor) si initializeaza variabilele sale. Implementarile obiectelor se inregistreaza in depozitul de implementare (implementation repository) la instalarea programelor. Acesta este un server de nume, care mapeaza numele serviciilor la numele de cale ale fisierelor executabile continand implementarile obiectelor. Adaptorul de obiecte (object adaptor)face ca o metoda a obiectului la distanta sa fie invocabila clientului: face inregistrarile implementarilor in depozit si le acceseaza la nevoie, activeaza implementarile obiectelor, creeaza ROID, efectueaza translatarea intre ROID si OID local folosit in implementari, include dispecerul care paseaza RMI obiectului corespunzator.

In rezumat, ordinea actiunilor unui RMI este urmatoarea:

1. clientul contacteaza adaptorul de obiecte

2. adaptorul de obiecte contacteaza depozitul de implermentare

3. adaptorul de obiecte activeaza implementarea obiectului in cadrul procesului server

4. clientul invoca metoda utilizand translatarea ROID, functia de dispecerizare si skeleton-ul IDL

Serverul CORBA poate fi de doua feluri (fig.10.9):

partajat, cand toate obiectele serverului se afla in acelasi proces, cererile clientilor fiind puse intr-o coada de asteptare

nepartajat, cand exista cate un obiect pe proces, cererile clientilor la obiecte diferite fiind satisfacute in procese separate

Definitia unei interfete IDL este similara cu definitia interfetei unei clase, avand un nume si o multime de metode accesibile clientilor. Interfata IDL poate avea si atribute proprii obiectelor (de genul variabilelor), metodele pentru accesarea si actualizarea lor fiind generate automat de catre compilatorul de interfata. Semnatura unei metode defineste numele sau, numele si tipul parametrilor utilizati, precum si numele si tipul rezultatului. Semnatura specifica de asemenea numele si parametrii unei eventuale exceptii care se poate produce in urma invocarii. Tot semnatura poate specifica semantica folosita la apel, cea implicita fiind de tip at-most-once. Un exemplu simplu de definire a interfetei este dat in figura 10.10.

Ordinea actiunilor unui RMI este urmatoarea:

1. incercarea clientului de a contacta un obiect la distanta este directionata la orbixd

2. orbixd foloseste depozitul de implementare pentru a cauta - pe baza numelui serviciului - numele fisierului care contine implementarea obiectului

3. orbixd porneste serviciul prin lansarea fisierului executabil

4. clientul transmite mesajele sale si primeste raspunsurile direct de la obiect

Pe baza definitiei de interfata scrisa in IDL, compilatorul Orbix IDL genereaza urmatoarele componente:

1. un fisier header corespunzator clasei din interfata, pentru a putea fi inclus in clienti si/sau in implementarea obiectului

2. o implementare a clasei proxy pentru client

3. un dispecer BOA (Basic Object Adaptor)

4. skeleton-ul IDL si cotoarele server

11.3. Tranzactii

Tranzactia (transaction) reprezinta o succesiune de

operatii legate intre ele pe care un client le efectueaza asupra unui server.

Din punctul de vedere al clientului, operatiile din tranzactie formeaza un singur pas,

transformand datele serverului dintr-o stare consistenta in alta.

Pentru a exemplifica o tranzactie, fie un server care pastreaza datele pentru toate conturile unei banci.

Operatiile care se pot solicita de la acest server bancar sunt:

Deposit (Name, Amount)

depune suma Amount in contul Name

Withdraw (Name, Account)

retrage suma Amount din contul Name

GetBalance (Name) Amount

returneaza balanta contului Name

BranchTotal ( ) total

returneaza suma tuturor balantelor

O tranzactie prin care clientul transfera 100$ din contul A in B si 200$ din C in B

va contine sirul de operatii din figura 11.1. La randul sau, o operatie din

cadrul tranzactiei poate fi descompusa la nivelul serverului in

mai multe operatii de citire si scriere. De exemplu, operatie Deposit, poate fi definita astfel:

Deposit (Name, amount):

balance:=Name.Read ();

Name.Write (balance + amount

Pentru a pastra consistenta datelor si in cazul unor tranzactii concurente, este nevoie de tranzactii atomice.

O astfel de tranzactie se caracterizeaza prin:

Indivizibilitate - efectele intermediare ale operatiilor componente nu trebuie sa fie vizibile.

Izolare (serializabilitate) - fiecare tranzactie trebuie sa fie executata fara a interferi cu alte tranzactii.

"Totul sau nimic" - ori se incheie cu succes si efectele sale apar in

datele vizate, ori (in caz de defectare) nu are nici un efect. Legata de aceasta proprietate este

cerinta de durabilitate, ceea ce inseamna ca in caz de incheiere cu succes efectele

tranzactiei sunt salvate in dispozitivul de stocare permanent.

Cand serverul confirma incheierea unei tranzactii, toate modificarile de date

corespunzatoare tranzactiei trebuie sa fie disponibile in dispozitivul de stocare

permanent. Modificarile de pe parcursul tranzactiei se fac numai in memoria operativa.

Astfel, in caz de defectare a serverului, datele de dinaintea tranzactiei devin recuperabile.

Un serviciu tranzactional (transactional service) este acela la care clientu

l specifica secventa de operatii care compun o tranzactie, iar serverul garanteaza

pastrarea proprietatii atomice a intregii secvente. Din operatiile serviciului tranzactional

va face parte o operatie OpenTransaction cu care clientul va prefata secventa,

precum si o operatie CloseTransaction pentru a marca sfarsitul tranzactiei (fig.11.2). I

dentificatorul tranzactiei, returnat de OpenTransaction, va fi folosit de client in operatiile

consecutive apartinatoare tranzactiei, pana la cea de inchidere.

O tranzactie se poate termina in urmatoarele feluri (fig.11.3):

Incheiata cu succes (comisa) - se confirma clientului ca toate

modificarile asupra datelor au fost inregistrate

Abandonata (din cauza unui conflict, defectare etc.) - nici un efect

partial al tranzactiei nu trebuie sa apara asupra datelor.

Abandonarea poate fi provocata de client (cu o operatie AbortTransaction) sau de server.