1.1. Definiția sistemului distribuit 1.2. Exemple de sisteme distribuite 1.3. Caracteristicile sistemelor distribuite 1.4. Istoricul sistemelor… [628623]

SISTEME DISTRIBUITE DE CALCUL
curs

CUPRINS

1. INTRODUCERE
1.1. Definiția sistemului distribuit
1.2. Exemple de sisteme distribuite
1.3. Caracteristicile sistemelor distribuite
1.4. Istoricul sistemelor distribuite
2. REȚELE DE CALCULATOARE
2.1. Clasificarea rețelelor de calculatoare
2.2. Abordarea stratificată a comunicației în rețeaua de calculatoare
2.3. Protocolul utilizat la Internet
3. COMUNICAȚIA ÎNTRE PROCESE
3.1. Introducere
3.2. Blocuri constructive pentru comunicație
3.3. Comunicația client -server
3.4. Comunicația de grup
3.5. Comunicația interprocese în UNIX
4. APELUL PROCEDURILOR ȘI INVOCAREA METODELOR LA DISTANȚĂ
4.1. Apelul procedurilor la distanță
4.2. Aspecte de proiectare
4.3. Implementarea RPC
4.4. Studi u de caz : Sun RPC
4.5. RPC de tip asincron
4.6. Invocarea metodelo r la distanță
4.7. Invocarea la distanță în Java
5. SISTEME DE OPERARE DISTRIBUITE
5.1. Introducere
5.2. Kernelul
5.3. Procese și fire de execuție
5.4. Folosirea numelor și protecția resurselor
5.5. Comunicația și invocarea
5.6. Memoria virtuală
6. SERVICIUL DE FIȘIERE
6.1. Introducere
6.2. Structura sistemului de fișiere
6.3. Interfețe
6.4. Tehnici de implementare
6.5. Sistemul Sun NFS
7. SERVICIUL DE NUME
7.1. Introducere
7.2. Un serviciu de nume model

7.3. Alte aspecte de proiectare
7.4. Sistem ul DNS
8. TIMPUL ȘI COORDONAREA
8.1. Introducere
8.2. Sincronizarea ceasurilor fizice
8.3. Ceasurile logice
8.4. Coordonarea distribuită
9. REPLICAREA
9.1. Introducere
9.2. Modelul arhitectural de bază
9.3. Consistența și ordonarea cererilor
10. TRANZACȚII ȘI DATE PARTAJATE
10.1. Introducere
10.2. C onversația dintre client și server
10.3. Tranzacții
10.4. Controlul concurenței
10.5. Restabilirea datelor
10.6. Tranzacții încuibate

Bibliografie

1. G. Coulouris, J. Dollimore, T. Kindberg, Distributed Systems: C oncepts and Design,
Addison -Wesley, 1994 , 2001, 2005, 2012 .
2. F. M. Boian, Programarea distribuită în Internet: metode și aplicații, Ed. Albastră,
Cluj-Napoca, 1998.
3. A. S. Tanenbaum, M. van Steen, Distributed Systems: Principles and Paradigms,
Prentice Hall, 2001.

1. INTRODUCERE

1.1. De finiția sistemului distribuit
Sistemul distribuit de calcul (distributed system ) constă dintr -o mulțime de procesoare
interconectate printr -o rețea de comunicație și pe care se execută programe cu control
descentralizat (fig.1.1). P rocesoarele dispun deci de autonomie în cadrul sistemului, dar
cooperează pentru îndeplinirea funcțiilor, astfel încât utilizatorul percepe sistemul
distribuit ca pe o unitate de calcul integrată, de sine stătătoare.

Fig.1.1. (adaptare după [1])

Sistemel e distribuite s -au dezvoltat din dorința de a satisface două deziderate: creșterea
vitezei de prelucrare prin execuția paralelă a calculelor și lucrul simultan a mai multor
utilizatori la stații diferite cu posibilitatea de comunicare între ei. Corespunzăt or acestor
două obiective diferă modul de implementare a sistemelor distribuite. Implementarea sub
forma sistemelor multiprocesor este cunoscută sub denumirea de sisteme distribuite
strâns cuplate (closely coupled ), la care procesoarele folosesc o memorie comună pentru
schimbul de date și au același ceas. Aplicațiile distribuite dezvoltate pe rețele de
calculatoare au condus la sistemele distribuite slab cuplate (loosely coupled ), la care
nodurile rețelei constau din calculatoare independente, cu memorie și ceas propriu.
Transferul de date în acest caz se face sub forma mesajelor transmise prin rețeaua de
comunicație.
Prezenta carte are ca obiect doar tratarea sistemelor distribuite slab cuplate.

1.2. Exemple de sisteme distribuite

În continuare se dau câte va exemple de sisteme distribuite, pornind de la primul sistem de
operare care a făcut posibilă dezvoltarea de astfel de aplicații:
 UNIX BSD (Berkeley Software Distribution ) este un sistem de operare dezvoltat la
Universitatea Berkeley în 1974, care a exti ns funcțiile sistemului de operare clasic UNIX
cu cele necesare comunicației între procese pe baza modelului client -server, făcându -l
astfel apt pentru aplicații distribuite. În acest model un proces client care rulează pe
calculatorul unui utilizator cere un serviciu de la un proces server executat (în general în
practică) pe un alt calculator din rețea. Serverul oferă acces pentru clienți la resurse
partajate, cum ar fi fișiere, baze de date, imprimante etc. Cele două procese menționate
sunt independente și separabile.
 Sun NFS (Network File System ) este un sistem distribuit de fișiere de tip UNIX
dezvoltat de firma Sun (1985), care definește mai multe protocoale:
 Protocolul NFS reprezintă protocolul de nivel înalt pentru accesul la fișiere.
 Protocolul RPC (Remote Procedure Call ) este protocolul apelului unei proceduri
la distanță.
 Protocolul XDR (External Data Representation ) descrie modul de reprezentare a
datelor de transmis, fiind independent de suportul hardware.
 Protocolul mount servește pentru interco nectarea sistemelor de fișiere aflate la
distanță.
 Protocolul NIS ( Network Information Service ) permite căutarea după informații pe
baza modelului Paginilor Galbene ( Yellow Pages ).
 Sisteme distribuite dezvoltate în medii academice: Amoeba (Universitatea de Vrije
Amsterdam), Mach (Universitatea Carnegie -Mellon SUA), Chorus (INRIA Franța),
Andrew (Universitatea Carnegie -Mellon SUA), Kerberos (Massachussets Institute of
Technology SUA).
 Sisteme distribuite cu aplicații comerciale, de exemplu pentru bănci cu re țea de
mașini ATM (Automatic Teller Machine ) pentru tranzacții pe bază de carduri.
 Aplicații distribuite dezvoltate pentru rețeaua Internet , cele mai cunoscute fiind:
 Poșta electronică (e-mail), care permite transmiterea scrisorilor prin rețea în cutia
poștală a destinatarilor aflați la distanță.
 Conectarea la un calculator aflat la distanță folosind programe ca Telnet sau
Rlogin .
 Sistemul de informații WWW (World Wide Web ) bazat pe navigarea printre
documente hipermedia păstrate pe servere WWW.
 Aplicații m ultimedia distribuite, destinate de exemplu pentru videoconferințe, cum
este sistemul Pandora dezvoltat de firma Olivetti.

1.3. Caracteristicile sistemelor distribuite

Spre deosebire de sistemele centralizate, sistemele distribuite au ca specific răspândi rea
în spațiu a elementelor hardware, descentralizarea controlului, distribuirea în sistem a
datelor și aplicațiilor. De aici rezultă următoarele caracteristici:
 Performanța sistemului în principiu nu poate fi mai mică decât a unui singur
calculator, vitez a de lucru fiind mai mare datorită prelucrării în paralel. Totuși,
performanța este afectată în mare măsură de timpul de comunicație între calculatoare,
care depinde atât de rețeaua utilizată, cât și de softul de comunicație. Sistemele distribuite
permit o oarecare flexibilitate în alocarea sarcinilor pentru o încărcare cât mai echilibrată
a procesoarelor. În această privință există mai multe modele de sisteme distribuite:
 Modelul stație de lucru – server. Acest model are arhitectura cea mai simplă, în
care stațiile de lucru conectate la o rețea locală pot cere servicii de la calculatoare
server, conectate de asemenea la rețea (fig.1.1). În acest caz performanțele
procesorului și dimensiunea memoriei stației de lucru determină mărimea aplicației
care poate f i executată de utilizator.
 Modelul bazat pe utilizarea stațiilor inactive. Acest model seamănă cu cel
precedent, deosebirea fiind în faptul că capacitatea de calcul disponibilă a stațiilor
nefolosite este alocată, printr -un soft specific, aplicațiilor care nu dispun de resurse
suficiente.
 Modelul bazinului de procesoare. Aici există mai multe calculatoare grupate într -o
colecție (bazin), care pot fi alocate dinamic aplicațiilor utilizator care cer capacitate
de calcul. Ca urmare stațiile de lucru se pot red uce chiar la simple terminale, cum
este cazul la sistemul Amoeba.
 Sisteme multiprocesor cu memorie partajată. Ele se folosesc mai ales în aplicații
de calcul paralel, precum și pe rol de calculator server de putere mare în sistemele
distribuite, putând pre lua și prelucra mai multe cereri în paralel. Sunt constituite
din mai multe procesoare independente care pot accesa aceeași memorie, ceea ce
asigură schimbul rapid de date între ele.
 Comunicația trebuie să fie posibilă între procese care se execută pe calc ulatoare
aflate la distanță. Din punctul de vedere al programatorului, comunicația se rezolvă prin
transmiterea de mesaje (message -passing ) cu ajutorul primitivelor de tip send și receive .
Mecanismul de transfer poate fi sincron sau asincron, după cum emițătorul așteaptă sau
nu confirmarea recepției unui mesaj înainte de a -l transmite pe cel următor. Există două
modele de comunicație de bază: comunicația client -server și difuzarea în grup (group
multicast ). Modelul client -server, amintit deja în subcapitolul anterior, se implementează
în general sub forma apelului de procedură la distanță RPC (Remote Procedure Call ),
care are avantajul de a ascunde protocolul de tip cerere -răspuns în fața p rogramatorului
(fig.1.2). Cererea conține în mod necesar și un identificator al procesului server, care se
obține în urma interogării serviciului de nume pe baza numelui serviciului solicitat.
Această operație poartă numele de rezolvarea sau rezoluția nume lui (name resolution ).
Difuzarea în grup înseamnă transmiterea aceluiași mesaj la mai mulți destinatari cu o
singură operație send (fig.1.3).

Fig.1.2 . (adaptare după [1])

Fig.1.3. (adaptare după [1])

Fig.1.4. (adaptare după [1])

 Partajarea resurselor face posibilă ca anumite resurse hard sau date să fie accesibile
mai multor procese aflate pe calculatoare distincte. Fiecare resursă este gestionată de un
program cu o interfață corespunzătoare, numit manager de resursă (resource manager ).
Un utilizator va comunica cu managerul de resursă atunci când dorește acces la o resursă
partajată (fig.1.4). În această accepțiune programele server lucrează ca și manageri de
resurse. În cazul datelor partajate este importantă menținerea consistenței acestora dacă se
cere actualizarea lor concurentă de către mai multe procese. Este necesar ca aceste
operații să fie efectuate în mod atomic (fără a întrepătrunde).
 Scalabilitatea reprezintă posibilitatea extinderii dimensiunii sistemului fără a
schimba principiul arhitect ural, respectiv softul de sistem și de aplicație. Pentru a diminua
efectele negative ale creșterii dimensiunii sistemului asupra performanței (prin reducerea
timpilor de răspuns, solicitarea mai intensă a serviciilor), se folosesc diferite tehnici cum
ar fi: replicarea datelor, servere multiple, păstrarea într -o memorie cache (implementată
pe cale soft) pe calculatorul clientului a unei copii a datelor accesate de la distanță în
vederea unei eventuale utilizări viitoare. Desigur că această din urmă tehnică duce la
reducerea traficului, dar ridică problema consistenței datelor. Modificarea datelor din
memoria cache a unei stații de lucru trebuie să apară și la server, respectiv la ceilalți
clienți care mai au aceste date în cache -ul propriu.
 Deschiderea presu pune publicarea interfețelor hard și soft, a standardelor de
comunicație, astfel încât sistemul să poată fi extins cu noi elemente hard și servicii. Din
această cauză structura soft a sistemelor distribuite nu mai este monolitică ca la sistemele
centraliza te, ci fiecare serviciu furnizează propria interfață către programele de aplicație
(fig.1.5). Se constituie astfel servicii deschise, care pot fi adăugate peste kernelul
sistemului de operare în funcție de necesități.

Fig.1.5. (adaptare după [1])

 Concure nța rezultă din faptul că în sistemele distribuite rulează în paralel mai multe
procese, care pot cere acces simultan la resurse partajate (fig.1.4). În acest caz se pune
problema sincronizării între cereri pentru a evita conflictele și a menține consiste nța
datelor partajate.

 Replicarea înseamnă existența mai multor copii ale datelor pe diferite calculatoare
(replicarea datelor) sau existența în sistem a mai multor calculatoare server care oferă
același serviciu (servere multiple). Problema de rezolvat în fața proiectantului este și în
această situație cea de asigurare a consistenței, în sensul ca operațiile clienților asupra
replicilor să fie făcute la fel și în aceeași ordine.
 Toleranța la defecte se realizează eficient în sistemele distribuite prin util izarea
redundanței (replicarea serverelor, a datelor) și a tehnicilor de restabilire pe cale soft
(refacerea datelor de dinainte de producerea defectului). În cazul în care procesul în care
s-a produs defectul cooperează și cu alte procese, atunci toate pr ocesele implicate trebuie
readuse la o stare consistentă, lipsită de eroare.
 Transparența constă în ascunderea separării componentelor în fața utilizatorului,
care, deși este conștient de existența mai multor calculatoare în sistem, nu trebuie să
cunoască distribuția programelor și datelor, adică a obiectelor informaționale pe acestea.
Transparența are mai multe forme:
 Transparența accesului (la fel se accesează obiectele locale și cele aflate la
distanță)
 Transparența locației (nu trebuie cunoscut locul ob iectului accesat)
 Transparența migrației (este permisă mutarea obiectului în cadrul sistemului fără
ca acest lucru să afecteze utilizatorul)
 Transparența scalării (este permisă extinderea gradată fără a schimba arhitectura
sistemului)
 Transparența concuren ței (mai multe procese pot opera concurent utilizând resurse
partajate, fără a intra în conflict)
 Transparența replicării (pot exista obiecte replicate fără ca utilizatorul să cunoască
acest lucru)
 Transparența defectării (defectul rămâne ascuns în fața ut ilizatorului)
 Transparența performanței (sistemul poate fi reconfigurat în vederea echilibrării
încărcării)
 Fiabilitatea și disponibilitatea ridicată se obțin dacă sistemul este proiectat tolerant
la defecte, astfel încât un defect apărut să fie detectat ș i mascat, iar sistemul să nu devieze
de la îndeplinirea corectă a sarcinilor. Căderea unei resurse hard nu trebuie să afecteze
funcționarea celorlalte, care eventual pot prelua prin reconfigurare sarcinile celei căzute
(de exemplu un proces server poate fi repornit pe un alt calculator).
 Securitatea este mult mai slabă decât la sistemele centralizate dacă nu se iau măsuri
speciale. Pe de o parte datele utilizatorilor, care traversează rețeaua, sunt expuse atacului
din partea intrușilor pe canalele de comuni cație, afectând astfel secretul și integritatea lor.
Pe de altă parte orice componentă soft este vulnerabilă datorită caracterului deschis și
poate fi coruptă astfel încât să furnizeze rezultate incorecte.

1.4. Istoricul sistemelor distribuite
Dezvoltarea cronologică a conceptelor legate de sistemele distribuite, precum și câteva
sisteme relevante pentru fiecare epocă a evoluției, sunt prezentate în figura 1.6.

Fig.1.6. (adaptare după [1])

2. REȚELE DE CALCULATOARE

2.1. Clasificarea rețelelor de calculatoare
Rețeaua de calculatoare asigură suportul necesar pe care se poate implementa un sistem
distribuit de calcul slab cuplat. Pe scurt prin rețea de calculatoare (computer network) se
înțelege o mulțime de calculatoare interconectate între ele printr -o rețea de comunicație.
Un calculator din rețea mai poartă denumirea de gazdă ( host). Subsistemul de
comunicație este alcătuit din totalitatea componentelor hard și soft care fac posibilă
transm iterea datelor între calculatoarele gazdă, mai exact între aplicațiile care rulează pe
acestea. Structura subsistemului de comunicație depinde atât de tehnologia rețelei de
comunicație, cât și de caracteristicile sistemului de operare utilizat.
Din punctul de vedere al ariei de întindere, rețelele de calculatoare se clasifică în
următoarele tipuri:
 Rețea locală (LAN – Local Area Network ), care cuprinde calculatoare aflate la
distanță mică (în aceeași cameră sau clădire), mediul de transmisie fiind constitui t din
cablu coaxial sau fire torsadate. Viteza de transmitere a datelor este foarte mare (de
ordinul 10 Mb /s – 100 Mb/s), întârzierile fiind mici (zeci de μs) și erorile introduse foarte
puține. Două tehnologii uzuale de LAN -uri sunt Ethernet și Token Ring .
 Rețea metropolitană (MAN – Metropolitan Area Network ), construită la nivelul
unui oraș, pentru transmisie fiind utilizate de regulă liniile telefonice (cu viteze de până la
128 kb/s) sau cablul coaxial (de exemplu de la sistemul de televiziune prin cablu ).
 Rețea de arie largă (WAN – Wide Area Network ) este o rețea care interconectează
calculatoare aflate în diferite orașe, țări sau chiar continente. Comunicația se desfășoară
pe linii telefonice închiriate, fibră optică sau se apelează la comunicația fără fir (radio sau
sateliți). Rețeaua conține elemente de comutare (PSE  Packet Switching Elements ), la
care sunt incidente mai multe linii de comunicație, transferul datelor fiind posibil la o
viteză mai mică decât la tipurile precedente de rețele. Timpul de transmisie cumulează o
întârziere de câteva milisecunde la fiecare comutator. Performanțe deosebite se obțin
totuși prin folosirea rețelei ISDN ( Integrated Services Digital Network ), care permite
transmisia sub formă digitală a datelor, vocii și imaginilo r video la viteze de peste 150
Mb/s. Rețeaua de bandă largă B -ISDN ( Broadband ISDN ), bazată pe tehnologia ATM
(Asynchronous Transfer Mode ), oferă rate de transfer și mai mari, de ordinul 600 Mb/s.
 Rețea de rețele, adică o inter -rețea (internetwork ), care c uprinde două sau mai multe
rețele interconectate (fig.2.1). Astfel, două LAN -uri interconectate sau o colecție de
LAN -uri conectate printr -un WAN formează o inter -rețea. Este de menționat faptul că
rețelele componente pot fi de tehnologii diferite, aceste diferențe fiind ascunse
programelor de aplicație. Cel mai elocvent exemplu de inter -rețea este Internetul, la care
sunt legate calculatoare de pe întreg globul și care are caracterul de a fi scalabil.

Fig.2.1. (adaptare după [1])

Elementele de interconec tare folosite la rețelele de calculatoare sunt următoarele:
 Repetorul (repeater ) se folosesc în cadrul unei rețele atunci când se efectuează
extinderea ei cu un nou segment și se dorește prevenirea problemei de atenuare a
semnalelor. Acest echipament elect ronic realizează doar o copiere pe ieșire a semnalului
analogic pe care îl recepționează, însoțită de o amplificare a acestuia.
 Puntea (bridge ) interconectează două rețele care folosesc aceeași tehnologie și mută
entitățile de date (numite cadre) dintr -o rețea în alta atunci când este necesar. În acest
scop puntea examinează toate datele vehiculate într -o rețea și dacă constată că sunt
destinate celeilalte rețele, le transmite către aceasta. Constructiv, puntea este un
echipament de calcul dedicat acestei f uncții.
 Ruterul (router ) este un calculator specializat care servește la transferul entităților de
date (sub formă de pachete) între două sau mai multe rețele realizate în tehnologii
diferite. Deosebirea esențială față de punte constă în faptul că ruterul dispune de o adresă
de rețea proprie și ca atare nu va examina decât datele care îi sunt destinate. Deci un
calculator gazdă va trimite un pachet destinat unei alte rețele către un ruter, care îl va
transmite mai departe pe calea corespunzătoare pe baza un ui tabel de rutare.
 Poarta (gateway ) reprezintă o altă denumire generică pentru ruter, folosită atunci
când acesta leagă între ele numai două rețele. Ca urmare tabelul de rutare este mai simplu
și calculele implicate mai puține, de aceea pe rol de poartă p oate fi utilizat un calculator
gazdă mai puțin încărcat, capabil să preia și această funcție.
Nodurile unei rețele de calculatoare pot fi interconectate sub forma mai multor topologii,
care diferă prin fiabilitate, cost și tipul transmisiei. Prin tipul tra nsmisiei se înțelege aici
modul în care un mesaj ajunge de la nodul sursă la nodul destinație, fiind uzuale două
feluri de rețele:

 Rețele cu difuzare, la care mesajul emis de un nod ajunge la toate celelalte noduri
prin intermediul unui mediu de transmisie unic. Un identificator conținut în mesaj
specifică destinatarul acestuia, care se va recunoaște și va prelua datele, iar restul
nodurilor le vor ignora. Exemple de astfel de rețele sunt cele de tip magistrală (liniară sau
circulară), simple din punct de v edere constructiv, dar expuse la căderea totală odată cu
defectarea magistralei. O problemă de rezolvat constă în modul de alocare a magistralei
la calculatoare în situația mai multor cereri simultane de transmisie, fiind necesară o
metodă de arbitrare. To t în categoria rețelelor cu difuzare intră și cele care dispun de
legături prin unde electromagnetice difuzate în spațiu.
 Rețele punct -la-punct, caracterizate prin faptul că mesajul circulă de la un nod la
altul până la destinație. Nodurile intermediare pă strează doar temporar mesajul și îl
transmit mai departe ( store -and-forward ). Fiabilitatea este mai mare datorită posibilității
de a exista căi alternative între două noduri, dar timpul de comunicație crește direct
proporțional cu numărul de noduri interme diare. Exemple de topologii punct -la-punct
sunt cele de tip stea, inel, arbore, rețea complet conexă și rețea parțial conexă.
În general rețelele mai puțin întinse utilizează topologii regulate (de tip magistrală, inel,
stea, arbore, complet conexă), pe câ nd rețelele WAN au topologii neregulate (sub formă
de graf parțial conex). În cazul inter -rețelelor, subrețelele componente pot fi dispuse
conform topologiilor prezentate.
In nodurile rețelei se află calculatoarele gazdă sau elementele de comutare (ruter, poartă).
Legăturile dintre ele pot fi realizate sub diferite forme: fire torsadate, cablu coaxial, fibră
optică sau unde electromagnetice în spațiu. Mediul fizic de comunicație se poate divi za în
mai multe canale logice de comunicație independente, folosin d o metodă de multiplexare.
Multiplexarea prin divizarea timpului permite nodurilor conectate la aceeași legătură ca
să utilizeze canalul succesiv, fiecare pentru o scurtă perioadă de timp. În schimb la
multiplexarea prin divizarea frecvenței se pot efectu a n transmisii simultane în același
mediu fizic, spectrul său de frecvență fiind impărțit în n benzi, câte una pentru fiecare
canal. Acest sistem de transmisie, numit și de bandă largă ( broadband ), presupune că
datele digitale utile modulează un semnal pur tător de o anumită frecvență. (Dacă nu se
aplică multiplexarea, atunci transmisia se consideră efectuată în banda de bază, adică
baseband .) Multiplexarea prin divizarea spațiului se referă la utilizarea unui mănunchi
de n legături paralele, care formează n canale independente.
În funcție de sensul de transmitere a datelor, comunicația între două noduri poate fi de
următoarele tipuri:
 simplex , dacă datele pot fi transmise într -un singur sens;
 semi -duplex , în cazul în care datele pot circula în ambele sensuri , dar nu
simultan;
 duplex , când este posibilă transmiterea concomitentă în ambele sensuri.
Transmiterea datelor la distanță lungă între două gazde dintr -o rețea punct -la-punct ridică
problema modului de utilizare eficientă a căii sau căilor de comunicație posibile. În
principiu există trei metode de partajare a liniilor existente:

 Comutarea de circuite (circuit switching ) stabilește o cale unică între sursă și
destinație pentru fiecare transmisie, care se desface doar după ce toate datele au fost
transferat e. Aceasta înseamnă că până la eliberarea căii de comunicație ea nu poate fi
folosită de alte noduri care vor să transmită, chiar dacă traficul realizat rămâne sub
posibilitățile liniilor.
 Comutarea de mesaje (message switching ) se bazează pe gruparea date lor de
transmis sub forma unui mesaj de lungime oarecare, care se transferă de la un nod la altul
până când ajunge la destinație. Avantajul față de tehnica precedentă constă în faptul că nu
se blochează la un moment dat toată calea pentru transmiterea mesa jului, ci numai
porțiunea dintre două noduri succesive. Însă, deoarece lungimea mesajului nu este
limitată, apare dezavantajul ca un mesaj lung să blocheze un canal pe timp îndelungat, iar
elementul de comutare să necesite o memorie tampon de dimensiune ma re pentru
păstrarea temporară a mesajelor.
 Comutarea de pachete (packet switching ) elimină neajunsul metodei anterioare prin
divizarea mesajului în pachete scurte de lungime fixă, care se transmit de la nod la nod
până la destinație. Aici mesajul este reas amblat din pachetele constituente. Este posibil ca
pachete aparținând la același mesaj să urmeze căi diferite și să nu ajungă la nodul final în
ordinea inițială. Această metodă este cea mai avantajoasă din punctul de vedere al
încărcării rețelei de comunic ație, iar pachetele care provin din mesaje scurte nu mai sunt
supuse la așteptări îndelungate la elementele de comutare, ele se pot transmite intercalat
printre celelalte pachete. Datorită avantajelor sale, comutarea de pachete este folosită în
majoritatea rețelelor actuale.

2.2. Abordarea stratificată a comunicației în rețeaua de calculatoare
Problema esențială de rezolvat în cadrul unei rețele de calculatoare o reprezintă
asigurarea transferului de date între două procese utilizator care se execută pe do uă gazde
diferite conectate la rețea. Pentru aceasta este nevoie de o mulțime de elemente
intermediare, atât de natură soft, cât și hard. În vederea tratării cât mai simple a acestei
probleme complexe, elementele menționate se grupează pe niveluri ierarhic e, care asigură
astfel posibilitatea unei proiectări structurate, coexistența în rețea a diferite tipuri de
calculatoare și independența aplicațiilor de tehnologia rețelei.
Conceptul organizării pe niveluri este prezentat în figura 2.2. După cum se observă la
fiecare calculator gazdă există același număr de niveluri, astfel încât nivelul i de pe o
mașină conversează cu nivelul i de pe cealaltă mașină. Această conversație pe orizontală
este însă numai virtuală, deoarece ea se realizează de fapt ca urmare a i nteracțiunii pe
verticală a nivelurilor adiacente. Astfel, din nivelul i se apeleazăs la serviciile nivelului de
sub el, fără ca să fie cunoscute detaliile de implementare a funcțiilor pe care acesta le
realizează. Fiecare nivel trebuie să cunoască mulțime a regulilor și convențiilor care
formează protocolul propriu nivelului respectiv. În protocol se specifică în principal
semnificația și formatul datelor schimbate între modulele pereche de pe același nivel. Se
poate spune că între modulele soft situate pe niveluri identice se stabilește un canal
virtual.

Fig.2.2. (adaptare după [1])

Pe lângă protocol, fiecare nivel are asociat și un serviciu , care întrunește operațiile oferite
nivelului de deasupra sa. Serviciul este definit în contextul unei interfețe di ntre două
niveluri, nivelul inferior fiind furnizorul serviciului, iar cel superior utilizatorul acesteia.
Interfața precizează nivelului ierarhic superior ce parametri trebuie să conțină un apel și
ce rezultat se furnizează, fără a conține detalii de impl ementare.
Standardizarea și publicarea protocoalelor și a interfețelor fac posibilă dezvoltarea
independentă a modulelor soft și implementarea lor pe calculatoare cu diverse procesoare
și reprezentări de date. În privința modului de reprezentare a datelor, dificultatea majoră
provine de la faptul că unele calculatoare utilizează convenția little endian (octetul cel
mai puțin semnificativ al unui număr amplasat la adresa mai mică de memorie), iar altele
convenția big endian (octetul cel mai semnificativ la a dresa mai mică).
O mulțime de protocoale, câte un ul pentru fiecare nivel, formează o stivă de protocoale
(protocol stack ). Numărul de niveluri depinde de standardul utilizat la rețeaua respectivă,
în orice caz nivelul cel mai de sus este cel al aplicației, iar cel mai de jos este nivelul fizic
conectat la mediul de comunicație. Totalitatea protocoalelor și a interfețelor este numită
arhitectura rețelei .
Organizația Internațională de Standardizare (ISO – International Standards
Organisation ) a elaborat model ul de referință OSI (Open Systems Interconnection ),
care se bazează pe șapte niveluri. Acest model nu reprezintă în sine o arhitectură, fiind
doar o propunere cadru pentru a încuraja dezvoltarea de standarde care să satisfacă
cerințele sistemelor deschise. Cele șapte niveluri ale modelului sunt următoarele:
 Nivelul fizic (1) conține circuitele electronice și componentele mecanice pentru
conectarea la mediul de comunicație. Rolul lor este de a transmite secvențe de biți între
calculatoarele interconectate, f iind responsabile de reprezentarea adecvată mediului a
biților de „0” și „1”.
 Nivelul legăturii de date (2) este responsabil de transmisia fără erori a datelor
grupate în blocuri, numite cadre.
 Nivelul rețea (3) transferă pachete de date între două calculatoare conectate direct,
stabilind dirijarea (rutarea) corespunzătoare a acestora.

 Nivelul transport (4) oferă servicii de nivel înalt (fragmentare, multiplexare,
controlul fluxului) pentru transmiterea mesaj elor primite de la nivelul superior între
calculatorul sursă și cel destinație.
 Nivelul sesiune (5) gestionează dialogul între cei doi utilizatori și sincronizarea
transferului cantităților mari de date (cum sunt fișierele).
 Nivelul prezentare (6) realizea ză conversia datelor utilizator în reprezentări
independente de calculatorul în cauză, precum și criptarea acestora.
 Nivelul aplicație (7) asigură interfețe comune de comunicație (un terminal virtual
abstract) către toți utilizatorii.
Într-un astfel de mod el stratificat, elementele de interconectare folosite în rețele lucrează
la diferite niveluri (fig.2.3). Repetorul, utilizat doar pentru refacerea semnalului atenuat
pe liniile lungi, intervine desigur pe nivelul fizic unde se tranferă șiruri de biți. Punt ea
interconectează rețele de același tip, deci care au același nivel rețea, și ca urmare mută
date sub formă de cadre la nivelul legăturii de date. În schimb ruterul, care leagă între ele
rețele de tipuri diferite, efectuează transferul de pachete de la o rețea la alta prin nivelul
rețea. De aceea într -o rețea WAN protocoalele din primele trei niveluri sunt între gazdă –
ruter sau ruter – ruter, deci între calculatoarele interconectate direct.
Într-o inter -rețea protocoalele de nivel superior (aplicație, tr ansport, inter -rețea) sunt
suprapuse peste protocoalele (de nivel legătură de date și fizic) ale rețelei reale din care
face parte calculatorul gazdă. Primele două niveluri ale modelului OSI își găsesc practic
implementarea în placa de rețea a calculatorul ui.

Fig.2.3.

Datele de transmis ale procesului utilizator de la emisie sunt furnizate nivelului aplicație,
care le transmite mai departe în jos prin stiva de protocoale. În cursul acestor operații
fiecare nivel primește datele de la n ivelul de deasupra într -un anumit format și le
completează cu eventuale noi informații (sub formă de antet) care sunt folosite de
protocolul din nivelul respectiv. Această secvență de activități poartă numele de
încapsulare , la care este important de menți onat faptul că un nivel care a primit o entitate
de date de la nivelul precedent nu face disticție între partea de antet și cea de date efective
a acestuia. La gazda de la recepție are loc activitatea inversă de dezîncapsulare , în cursul
căreia pe măsură c e datele urcă în stiva de protocoale li se elimină informațiile
suplimentare care le -au fost atașate. Bineînțeles că la fiecare nivel aceste informații sunt
folosite pentru ca nivelul să -și poată îndeplini funcția specificată. E ntitățile de date au
denumir i specifice în funcție de nivel: biți, cadre, pachete, mesaje.
Este posibil ca, în funcție de protocol, lungimea unei entități de date dintr -un anumit nivel
să fie limitată. Această limită se desemnează în octeți cu unitatea maximă de transmisie
MTU (Maxim um Transfer Unit ). Dacă datele depășesc valoarea MTU, atunci ele se
fragmentează în unități mai mici, în antetul cărora se specifică un identificator al
entității, numărul de ordine al fragmentului și numărul total de fragmente care împreună
alcătuiesc ent itatea. În principiu fragmentarea se poate aplica la orice nivel din suita de
protocoale, dar ea este caracteristică în primul rând nivelului transport . Aici mesajul
primit de la nivelul superior, dacă este prea lung, se împarte în pachete, care sunt livra te
independent la destinație de către nivelul rețea. Este posibil ca pachetele să urmeze căi
diferite și ca urmare să ajungă la destinație într -o ordine oarecare. Reasamblarea
mesajului conform ordinii inițiale ( secvențierea ) intră în sarcina nivelului tra nsport al
gazdei de la recepție, pe baza informațiilor din antetele pachetelor. Pe parcurs, dacă este
necesar, pachetele se pot subdivide mai departe în interfața de rețea (nivelul legătură de
date), în funcție de cerințele tehnologice ale rețelei de dedes ubt.
În vederea utilizării eficiente a canalelor de comunicație, nivelul transport poate utiliza
aceeași conexiune de rețea pentru mai multe conversații independente. Trebuie realizată
în acest caz operația de multiplexare a mesajelor la nivelul transport în calculatorul
gazdă de la emisie, respectiv demultiplexarea la recepție. Este posibilă însă și situația
inversă, când nivelul transport creează mai multe conexiuni la nivel rețea pentru aceeași
conexiune la nivel transport, ceea ce duce la creșterea debi tului de comunicație.
O problemă importantă este cea a controlului fluxului în nivelul transport (și alte
niveluri), ceea ce apare în situația când o gazdă rapidă transmite date către o gazdă mai
lentă. Aceasta presupune existența unui mesaj de reacție din partea receptorului care să
indice momentul când noi date pot fi trimise sau să ceară schimbarea ratei de emisie.
Astfel emițătorul va transmite date fără a depăși capacitatea de preluare a datelor de către
receptor, care depinde și de dimensiunea memorie i tampon a acestuia.
La nivelul legăturii de date pentru controlul erorilor se folosesc coduri detectoare și
corectoare de eroare. Pe baza datelor de transmis se calculează o informație de control
conform cu codul utilizat (cod Hamming, cod ciclic, suma de control), care se atașează în
coada cadrului transmis. La nodul receptor în principiu se recalculează informația de
control și se compară cu cea sosită pentru a detecta eroarea. În cazul codurilor corectoare
de eroare, dacă alterarea nu a depășit un anumi t număr de biți atunci pe baza informației
de control este posibilă refacerea datelor corecte. În schimb siguranța livrării corecte a

datelor se poate asigura numai prin returnarea unui cadru de confirmare la nodul de
emisie, în lipsa căruia acesta trebuie să trimită din nou cadrul dovedit a fi eronat. De
regulă retransmiterea se va face doar după epuizarea unui timp prestabilit în care se
așteaptă sosirea confirmării.
Scopul ierarhiei de protocoale este a transmite date de la un utilizator la altul prin
intermediul rețelei. Desigur pentru aceasta este nevoie de specificarea destinației, ceea ce
presupune utilizarea unei adrese. În funcție de nivelul stivei de protocoale se definesc mai
multe tipuri de adrese:
 numele simbolic al destinației, care este exprim at sub forma unui șir de
caractere ușor de utilizat la nivelul aplicației ;
 numărul de port, care reprezintă identificatorul unui capăt de comunicație la
nivel transport;
 adresa de rețea a unei gazde, ceea ce înseamnă adresa calculatorului în cadrul
rețelei , fiind folosită la nivel rețea;
 adresa interfeței de rețea a calculatorului, care se folosește la nivelul legăturii
de date.
În principiu fiecare aplicație are atribuit un port la nivel transport, portul fiind un punct de
comunicație definit prin soft. Ni velul transport livrează un mesaj între două porturi.
Pentru aceasta are nevoie de adresa de transport, care constă din adresa de rețea a
destinației și un număr de port la care trebuie să livreze mesajul. Adresa de rețea este
folosită pentru dirijarea pac hetelor la nivelul rețea prin ruterele aflate în nodurile rețelei,
pe baza tabelelor de rutare. Adresele interfețelor hardware sunt atașate cadrelor și se
utilizează la transferul datelor de la un calculator la altul în interiorul aceleiași rețele.
Servici ul de comunicație furnizat de un anumit nivel al ierarhiei nivelului superior poate
fi de două feluri:
 Orientat pe conexiune (connection -oriented ), care dă impresia unui „circuit virtual”
între nivelul furnizor de serviciu de la emisie și perechea sa de la destinație. (Circuitul
este virtual deoarece transferul datelor nu se face în realitate pe o cale neîntreruptă, ci tot
de la nod la nod, iar același mediu de comunicație poate fi folosit de mai multe căi
virtuale.) În prima fază a comunicației are loc sta bilirea conexiunii (pe baza adresei de
destinație), adică a unei căi între cele două părți. În a doua fază se transmit datele, toate
mesajele urmând aceeași cale deja fixată, deci ele nu mai au nevoie de cunoașterea
adresei de destinație, ci numai de ident ificatorul căii virtuale. Datele se transmit sub
forma unui șir de octeți de lungime oarecare și vor ajunge la destinație în ordinea în care
au fost trimise. În ultima fază, la inițiativa emițătorului, se desface conexiunea.
 Fără conexiune (connectionless ), situație în care entitățile de date se transmit
independent și conțin fiecare adresa de destinație. Aceste entități, numite și datagrame,
pot urma căi diferite, care sunt desemnate chiar în timpul transmisiei și ca urmare pot
ajunge în orice ordine.
Serviciul orientat pe conexiune este avantajos la transmiterea unei cantități mari de date
cu păstrarea secvențialității, la care timpul suplimentar cerut de stabilirea și desfacerea
conexiunii este neglijabil. Serviciul fără conexiune este mult mai simplu și nu necesită

timp suplimentar, fiind adecvat la transferul mesajelor scurte. La rândul său, fiecare din
cele două tipuri de servicii de comunicație poate fi:
 fiabil sau sigur (nu se pierd date), dacă se transmite către emițător o
confirmare a recepționării datelor ;
 nefiabil sau nesigur (este posibilă pierderea, duplicarea, alterarea datelor),
dacă nu se folosește confirmarea.
Din combinațiile tipurilor și a calităților anterioare rezultă teoretic patru feluri de servicii,
dar în practică se utilizează servic iile sigure orientate pe conexiune și serviciile nesigure
fără conexiune.
Comunicația la nivel transport poate fi orientată pe conexiune sau fără conexiune. Funcția
îndeplinită de nivelul transport se bazează însă pe serviciul oferit de nivelul de dedesubt ,
nivelul rețea. Fiecare tip de serviciu de la nivelul transport poate fi implementat la nivel
rețea atât sub forma unui serviciu orientat pe conexiune, cât și sub forma unui serviciu
fără conexiune. Dacă un serviciu fiabil orientat pe conexiune este imple mentat la nivel
transport peste un serviciu de tip datagramă la nivel rețea, devine posibilă asigurarea unui
serviciu sigur de către protocolul de transport într -o rețea nesigură. Acesta este un
exemplu în care organizarea pe niveluri a protocoalelor își g ăsește justificarea.
La nivelul legăturii de date se furnizează de regulă unul din următoarele servicii: sigur
orientat pe conexiune, sigur fără conexiune, nesigur fără conexiune .

2.3. Protocolul utilizat la Internet
Familia de protocoale standard folosi te în rețeaua Internet poartă numele de TCP/IP
(Transmission Control Protocol / Internet Protocol ). Locul acestora în cadrul stivei de
protocoale (diferită de modelul ISO cu 7 niveluri) se poate vedea în figura 2.4.
La nivel transport protocolul TCP/IP pre vede utilizarea adreselor de port, care sunt
numere de 16 biți. De exemplu, pentru transferul de fișiere prin FTP se utilizează portul
cu numărul 21 (exprimat în zecimal), iar pentru Telnet 23. La acest nivel aplicațiile pot
solicita unul din serviciile TC P sau UDP. Protocolul TCP (Transmission Control
Protocol ) reprezintă un serviciu orientat pe conexiune și fiabil. El este folosit în cazul
aplicațiilor ca FTP ( File Transfer Protocol ), Telnet, e -mail etc. Protocolul UDP (User
Datagram Protocol ) este un ser viciu fără conexiune și nefiabil, ordinea de livrare a
datagramelor nefiind garantată. Se folosește de către aplicații puțin pretențioase, cum ar fi
servicii de timp, DNS ( Domain Name System ), FTP simplificat etc.

Fig.2.4. (adaptare după [1])

La nivel re țea se utilizează protocolul IP (Internet Protocol ). Acesta oferă un serviciu
fără conexiune și nefiabil, fiind posibilă pierderea, întârzierea, duplicarea sau modificarea
ordinii pachetelor la livrare. De aceea, se spune că acest serviciu depune doar efor tul
maxim pentru livrare, dar fără a garanta acest lucru („best -effort service”). Protocolul IP
folosește adrese IP, care sunt numere de 32 de biți. Totalitatea adreselor IP utilizabile pe
glob sunt împărțite pe clase ( fig.2.5), fiind atribuite unitar de către NIC ( Network
Information Centre ) pentru a evita conflictele. Adresele din clasa A sunt rezervate pentru
rețele foarte mari, cele din clasa B se atribuie organizațiilor care folosesc rețele cu mai
mult de 256 calculatoare, iar cele din clasa C se atri buie celorlalți operatori de rețea.
Adresele din clasa D se folosesc pentru difuzare în grup. Adesea adresele IP se exprimă
în sistemul zecimal, sub forma a patru numere, de exemplu 215.138.216.23. Protocolul IP
transmite datele sub formă de pachete IP, cu lungimea maximă de 64 Kocteți ( fig.2.6). La
acest nivel se asigură dirijarea pachetelor prin rutere, care determină calea unui pachet pe
baza adresei IP a destinației, folosind un tabel de rutare.

Fig.2.5. (adaptare după [1])

Fig.2.6 . (adaptare după [1])

La nivel aplicație se utilizează adresarea bazată pe nume simbolice organizate pe domenii
ierarhice (fig.2.7). Un exemplu de nume de domeniu este cabinet.cs.uoradea.ro. Adresele
simbolice sunt translatate în adrese IP de către serviciul numelor de domen iu DNS
(Domain Name System ). La nivelul unei rețele concrete fizice, de exemplu Ethernet,
acestea sunt convertite mai departe în adrese de interfață de rețea (de 48 de biți) de către
protocolul ARP ( Address Resolution Protocol ). Corespondențele de tip <adr esă IP,
adresă Ethernet> ale numelor rezolvate sunt păstrate într -un cache de fiecare calculator
gazdă. Dacă numele cerut nu se află în cache, atunci se difuzează adresa IP către toate
calculatoarele din rețeaua locală. Cel care se recunoaște pe baza adres ei va returna adresa
sa Ethernet (de interfață de rețea). Dacă destinația nu se află în această rețea, pachetul de
date se trimite pentru a fi dirijat mai departe la poartă sau ruter, care are câte o adresă IP
pentru fiecare rețea la care e conectat.

Fig.2.7. (adaptare după [1])

3. COMUNICAȚIA ÎNTRE PROCESE

3.1. Introducere
Aplicațiile distribuite sunt compuse dintr -o mulțime de procese, între care trebuie
asigurată comunicația pentru transferul de date.. Există două tipuri de comunicații între
procese:
 Comunicația client -server , care se bazază pe un protocol de forma invocare –
răspuns ( request -reply ) între părțile implicate
 Difuzarea în grup , care are la bază un protocol de tip multicast (difuzare la un
grup de procese)
În vederea implementării comunicației, aplicația necesită un protocol de nivel înalt pentru
a apela la servicille din nivelul transport (TCP sau UDP în cazul Internetului). Interfața
programului de aplicație cu nivelul transport TCP presupune o comunicație sub forma
unui șir de date ( stream communication ) de lungim e oarecare între emițător și receptor.
Ca urmare aceasta necesită introducerea datelor într -o coadă la destinație, adică
tamponarea lor ( buffering ). În cazul utilizării protocolului UDP, comunicația se bazează
pe transfer de mesaje ( message passing ). Pentr u specificarea destinației, în UNIX se
utilizează socluri ( socket -uri).

3.2. Blocuri constructive pentru comunicație
Pentru a putea fi transmise ca mesaje, structurile de date din programul de aplicație
trebuie translatate într -o formă potrivită, interpre tabilă ambelor părți. Maparea
structurilor de date în mesaje constă în aplatizarea acestora, urmând ca la recepție să fie
refăcută structura inițială. Există următoarele posibilități de reprezentare a datelor
transmise:
 datele se convertesc într -o formă d e reprezentare externă agreată de
ambele părți, exemple fiind standardele XDR ( External Data
reprezentation ), Courier, ASN.1 ( Abstract Syntax Notation )
 datele se transmit sub forma originală, însoțite de un identificator al
structurii
 datele se transmit fă ră conversie, dacă părțile sunt de același tip

Compunerea datelor ( marshalling ) reprezintă procesul de asamblare a unei mulțimi de
date într -o formă potrivită pentru a fi transmise într -un mesaj. La recepție se face operația
inversă, de descompunere. Aplat izarea datelor și translatarea lor într -o reprezentare
externă se poate face sub formă explicită în programul emițător, sau automat de către un
compilator de interfață pe baza specificării tipului de date.
Pentru ca două procese să poată comunica au nevoie de o operație de tip Send pentru
transmitere, respectiv de o operație de tip Receive pentru recepție. Un exemplu de
definire a acestor primitive este dat în figura 3.1.
Forme le comunicației de date între procese pot fi:
 Comunicație sincronă , când la fieca re mesaj se face sincronizarea proceselor.
Operațiile Send și Receive sunt cu blocare, adică fiecare operație se blochează până
nu se execută cealaltă.

Fig.3.1. (adaptare după [1])

 Comunicație asincronă , la care operația Send este fără blocare, pe când Receive
poate fi cu blocare sau fără blocare , acest din urmă caz presupunând existența unui
buffer la recepție.
Destinația mesajului trebuie specificată sub forma unui identificator printr -un argument al
lui Send . Identificatorul poate fi:
 identificator in dependent de locație, un exemplu fiind portul din figura
3.2
 identificator dependent de locație, cum e cazul Internetului, unde
destinația se specifică printr -o pereche <număr port, adresă IP>

Fig.3.2. (adaptare după [1])

Din punct de vedere al fiabilită ții, mesajele pot fi nefiabile sau fiabile. Mesajul nefiabil
este cel fără confirmare sau retransmitere, ceea ce poate duce la pierderea, întârzierea,
modificarea ordinii mesajelor. Mesajul fiabil presupune confirmarea sosirii sale de către
partea receptoa re. Pentru ca receptorul să fie în stare să dea confirmarea, fiecare mesaj
necesită un identificator unic, format din:
 Identificatorul procesului emițător ( procedureId ), de exemplu numărul portului
la care se așteaptă răspunsul. Acest identificator asigură unicitatea mesajului în
cadrul sistemului.
 Identificatorul cererii ( requestId ), care este luat de la un contor din cadrul
procesului emițător. Acest identificator asigură unicitatea mesajului la
emițător.
3.3. Comunicația client -server
În general comunica ția client -server este sincronă și fiabilă, ca urmare necesită două
operații Send și două operații Receive (câte o pereche SendReceive pentru transmiterea
mesajului, respectiv a confirmării). O variantă cu trei apeluri a protocolul ui invocare –
răspuns, imp lementată de unele sisteme de oper are, folosește următoarele operații
(fig.3.3):
PROCEDURE DoOperation (serverPort: PortId; request: Message; VAR
reply:Message);
PROCEDURE GetRequest (serverPort: PortId; VAR request:Message);
PROCEDURE SendReply (client Port: PortId; reply:Message);

Fig.3.3. (adaptare după [1])

Procedura DoOperation se folosește pe partea de client pentru transmiterea cererii și
preluarea confirmării, fiind cu blocare până la recepționarea acesteia din urmă.
Argumentele folosite în oper ație sunt identificatorul portului serverului, mesajul în sine și
indicarea locului (buffer -ului) pentru încărcarea răspunsului. Procedura GetRequest se
apelează pe partea de server pentru preluarea cererii de serviciu, iar SendReply efectuează
transmitere a mesajului de răspuns. Structura mesajului, atât a cererii, cât și a răspunsului,
este cea din figura 3.4, unde requestId reprezintă numărul de ordine dat de client
mesajului, iar procedureId identifică procedura invocată a serverului.

Fig.3.4. (adaptare după [1])

Pentru cazul când nu sosește răspuns, DoOperation trebuie să utilizeze un mecanism de
temporizare ( timeout ). La expirarea timpului, tratarea se poate face prin următoarele
modalități:
 cu indicare de eroare și revenirea din operație
 cu repetare a operației până când vine răspuns sau devine probabil că
serverul s -a defectat
La a doua modalitate, cu retransmiterea cererii, este necesar ca protocolul serverului să
filtreze mesajele duplicate (cu același requestId ) pentru a nu executa în mod greșit de mai
multe ori aceeași operație. Filtrarea duplicatelor la server nu este necesară dacă operațiile
sale sunt idempotente (execuția repetată duce la același rezultat). În caz contrar, pentru a

evita producerea unui rezu ltat greșit, se analizează istoricul mesajelor de răspuns pentru a
determina dacă această cerere a mai fost prelucrată sau nu.
În cazul în care mesajul asociat invocării depășește lungimea admisă pentru un pachet,
atunci el se divizează și se transmite sub forma unei secvențe de pachete. Tratarea acestor
mesaje multipachet se poate face în două feluri:
 cu confirmare după fiecare pachet
 cu confirmare după toate pachetele
Prima metodă, desigur mai costisitoare, are avantajul prevenirii erorilor de ritm, dator ate
de exemplu spațiului insuficient de buffer la receptor.
Fiabilitatea comunicației depinde de eventuale noduri sau legături defecte, procese
căzute, ceea ce pot conduce la pierderea de mesaje. Sub acest aspect, protocoalele de tip
invocare -răspuns pot f i implementate pe baza următoarelor trei semantici ( fig.3.5):
 Protocol R (request ), când nu există confirmare din partea serverului.
 Protocol RR (request -reply ), când mesajul de răspuns al serverului
este considerat confirmare de către client.
 Protocol RRA (request -reply -acknowledge reply ), când răspunsul
serverului este la rândul său confirmat de către client. Confirmarea
conțin e requestId -ul din mesajul de răspuns, ceea ce semnifică pentru
server că toate mesajele de răspuns cu requestId mai mic au fost d eja
recepționate.

Fig.3.5. (adaptare după [1])

3.4. Comunicația de grup
În cazul în care un proces dorește să comunice cu toate procesele dintr -un grup de
procese, se folosește un mesaj de difuzare în grup ( multicast message ). Această difuzare
parțială a unui mesaj poate fi necesară în următoarele cazuri:
 toleranța la defecte prin replicarea serverelor

 replicarea datelor
 localizarea obiectelor
 transmiterea de anunțuri
Un protocol ideal de difuzare în grup trebuie să aibă următoarele proprietăți :
 Atomici tatea. O difuzare atomică a mesajului înseamnă că mesajul ori
e recepționat de toți membrii grupului, ori de nici unul (se consideră că
procesele căzute nu mai fac parte din grup). Uneori în practică o
difuzare fiabilă poate fi suficientă.
 Ordonarea. Difuz area total ordonată presupune că atunci când două
surse difuzează simultan mesaje, ele să ajungă în aceeași ordine la toți
membrii grupului. Uneori această condiție este prea restrictivă.
Implementarea comunicației de grup se poate face printr -una din urmă toarele metode:
a) Difuzarea în grup nefiabilă , care este fără confirmare din partea destinatarilor. Unele
mesaj e se pot pierde sau chiar procesul emițător se poate defecta după ce a transmis o
parte dintre mesaje. Procedura de implementare poate avea stru ctura de mai jos:
PROCEDURE multicast (destinations: ARRAY OF PortId; m: Message);
. . . . . .
FOR i: = 0 TO HIGH (destinations) DO Send (destinations (i), m) END;
b) Difuzarea în grup fiabilă , care presupune ca emițătorul să primească câte o
confirmar e de la fiecare membru al grupului. Dacă unele confirmări nu sosesc nici după
un număr de retransmiteri, procesele respective sunt eliminate din grup. Dacă emițătorul
se defectează în timpul transmiterii, difuzarea nu va fi atomică. În acest caz
responsabi litatea trebuie preluată de unul din destinatari. De aceea, după ce a dat
confirmarea, un destinatar monitorizează emițătorul (prin transmiterea unui mesaj de
control și așteptarea răspunsului) și dacă constată că e defect va prelua continuarea
operației d e difuzare. Uneori, pntru a aduce la cunoștința destinatarilor că difuzarea a luat
sfârșit, se folosește notificarea terminării de către emițător, ceea ce înseamnă însă o nouă
difuzare.
În vederea reducerii numărului mare de mesaje de confirmare, au fost d ezvoltate diverse
tehnici. Una dintre ele este confirmarea negativă , ceea ce presupune că destinatarul nu
trimite confirmare după fiecare mesaj, ci numai dacă constată (pe baza unui contor atașat
fiecărui mesaj la emisie) că un mesaj lipsește. O altă tehni că este cea a reținerii ( hold-
back ) mesajelor recepționate, furnizarea unui mesaj sosit către aplicație fiind făcută doar
în momentul în care cerințele de ordonare și atomicitate au fost îndeplinite. Asemenea
mesaje se numesc mesaje stabile , adică nu mai s unt de așteptat mesaje cu identificatori
mai mici. Generarea identificatorilor pentru ordonare se poate face:
 cu marcaje (ștampile) de timp
 cu un proces secvențor la care se trimit toate mesajele înainte de a fi
difuzate
 cu utilizarea unui protocol printre membri pentru generare

3.5. Comunicația interprocese în UNIX
În UNIX comunicația dintre două procese se bazează pe utilizarea unei perechi de socluri
(sockets ) în procesele implicate. Soclul se creează cu un apel de sistem socket , având ca
argumente dome niul (de exemplu Internet), tipul (șir sau datagram) și protocolul (TCP
sau UDP). Apelul returnează un descriptor pentru referințe ulterioare. Soclul se leagă de
o adresă de soclu de forma <nr_port, adresă_IP > cu apelul bind.
La comunicația prin datagrame se identifică câte o pereche de socluri la fiecare
transmitere, mesajul fiind transmis fără confirmare ( fig.3.6). La comunicația prin șiruri de
date, prima dată se stabilește o conexiune între perechile de socluri (fig.3.7). Serverul
ascultă cererile de st abilire a conexiunii. Dacă conexiunea este acceptată, UNIX creează
un nou soclu și îl împerechează cu soclul clientului pentru comunicație, astfel încât soclul
original poate fi folosit în continuare pentru ascultare.

Fig.3.6. (adaptare după [1])

Fig.3.7. (adaptare după [1])

4. APELUL PROCEDURILOR ȘI INVOCAREA METODELOR
LA DISTANȚĂ

4.1. Apelul procedurilor la distanță
În sistemul distribuit se urmărește ca apelul procedurilor să se facă similar cu cel
convențional folosit în limbajel de nivel înalt. Problema aici constă în faptul că procedura
apelată este executată într -un proces al unui calculator aflat, de regulă, la distanță. Apelul
procedurilor la distanță (RPC  Remote Procedure Call ) este bazat pe o comunicație
client -server, în care severul exportă o mulțime de proced uri cu care se poate opera
asupra datelor partajate. Procesul server rulează neîntrerupt și resursele sale sunt partajate
între clienți. Clientul importă procedurile serverului, adică le poate apela printr -o interfață
făcută publică.
Scopul implementării R PC este, cum s -a arătat, de a menține semantica apelului
convențional. Acest lucru întâmpină însă anumite probleme:
 transmiterea parametrilor de intrare se poate face numai prin valoare în
mesajul de invocare (datorită spațiilor diferite de adrese, argumen tele și
rezultatul nu pot conține pointer -i)
 returnarea parametrilor de ieșire se face de asemenea prin valoare în
mesajul de răspuns (uneori serverul poate returna referințe opace, care pot
fi folosite de client ca argument la un nou apel, fără a fi însă interpretată)
 inaccesibilitatea variabilelor globale ale clientului de către procedura la
distanță
 necesitate a aplatizării structurilor de date pentru a fi transmise
Întrucât interfața RPC nu este neapărat convenabilă pentru programele clientului,
utiliza rea serviciilor de către programul de aplicație e ajutată de pachetul utilizator
(fig.4.1). Acesta are rolul de a a scunde RPC față de programul de aplicație. Astfel
programatorul nu va lucra în limbajul de definire a interfeței RPC.

Fig.4.1. (adaptare după [1])

4.2. Aspecte de proiectare
Există două clase de sisteme RPC:
 Integrate într -un limbaj de programare (de exemplu la sistemele Cedar, Argus,
Arjuna).
 Cu limbaj de definire a interfeței (cum este cazul la Sun, ANSA, Mach). O
definiție a interfeței RPC specifică acele caracteristici ale procedurii care sunt
vizibile de către client. Aceste specificații de forma (nume, tipul parametrilor)
reprezintă semnătura procedurii (fig.4.2). Pentru ca interfața să fie utilizabilă în
diferite limbaje de programare e ste nevoie de compilatoare de interfață.

Fig.4.2. [1]

Deoarece oricare RPC se poate defecta (server defect, identificator invalid în apel etc.),
este nevoie de un mecanism de tratare a excepțiilor, care să raporteze erorile la programul
client. Acest mecanism are două părți:
 indicarea excepției
 tratarea (handler -ul) excepției
Fiabilitatea apelului RPC este influențată de modul de implementare a protocolului de
invocare -răspuns: dacă se reia sau nu mesajul de invocare în caz de neprimire a unui
răspuns, dacă se face sau nu filtrarea duplicatelor, dacă se reexecută procedura serverului
sau se retransmite răspunsul pe baza unui istoric. Semanticile posibile de care depinde
fiabilitatea RPC sunt (fig.4.3 ):
 Maybe. Nu se reia invocarea în cazul î n care mesajul de răspuns nu a fost
recepționat, ca urmare este doar posibil ca procedura la distanță să fi fost
executată. Această metodă nu se utilizează în practică.
 At-least -once. Mesajul de invocare se retransmite, dar nu se aplică filtrarea
duplicate lor, deci clientul nu va ști câte apeluri au fost făcute de fapt (cel puțin

unul în mod sigur). Ca urmare se reexecută procedura serverului, metoda fiind
utilizabilă numai dacă operațiile serverului sunt idempotente.
 At-most -once. Fiind făcută filtrarea du plicatelor, operația serverului nu se
reexecută, dar se retransmite răspunsul. Dacă clientul recepționează un răspuns,
atunci se garantează că procedura server a fost executată o singură dată. Această
metodă este folosită în mod uzual.

Fig.4.3. (adaptare după [1])

Din punct de vedere al transparenței apelului în programul client, RPC poate fi:
 transparent, când apelul la distanță din partea clientului nu se deosebește în
sintaxă de un apel local (de exemplu la Sun)
 netransparent, când apelul la distanță folosește o notație aparte (de
exemplu la ANSA)

4.3. Implementarea RPC
Softul care implementează sistemul RPC are trei sarcini principale : prelucrările de
interfață, tratarea comunicației și legarea.
a) Prelucrările de interfață servesc pentru integrarea mecanismului RPC în programele
clientului și serverului scrise în limbaj convențional. Aceste prelucrări cuprind
compunerea, respectiv descompunerea argumentelor și livrarea cererii la procedura
corespunzătoare a serverului (fig.4.4) :
 Programul client fol osește o procedură cotor (stub procedure ) la fiecare apel,
care convertește apelul local într -un apel la distanță conform definiției de
interfață. Sarcinile principale ale procedurii cotor sunt:
 compunerea argumentelor
 împachetarea argumentelor în mesaj îm preună cu un identificator de
procedură (practic un număr de ordine)

 descompunerea răspunsului
 Programul server utilizează un dispecer , care pe baza identificatorului de
procedură alege una din procedurile cotor și îi predă argumentele. Sarcinile sale
principale sunt:
 descompunerea argumentelor
 apelul procedurii de servire
 compunerea răspunsului (eventual raportarea unei erori)

Fig.4.4. (adaptare după [1])

Definițiile de interfață, scrise într -un limbaj de definire a interfeței, sunt compilate de un
compi lator de interfață . Compilatorul de interfață generează:
 procedura cotor a clientului
 procedura cotor a serverului
 operațiile de compunere și descompunere
 header -ele procedurilor serverului
b) Tratarea comunicației are rolul de a transmite și recepționa me saje, utilizând o formă
de comunicare de tip invocare -răspuns.
c) Legarea înseamnă maparea numelui textual al serviciului apelat într -un identificator
de comunicație al serverului. Această mapare se efectuează de un serviciu de nume numit
binder . În mod ti pic un binder include următoarele proceduri:
PROCEDURE Register (serviceName: String ; serverPort: Port; version: integer)
PROCEDURE Withdraw ( serviceName: String ; serverPort: Port; version:
integer)

PROCEDURE LookUp ( serviceName: String ; version: integer): Port
Procedura Register se folosește de server pentru exportarea interfeței prin înregistrarea
numelui serviciului oferit și a numărului de port. Serverul își poate șterge înregistrarea
folosind procedura Withdraw . Procedura LookUp se folosește de client pentru a identifica
portul unui anumit serviciu, deci la importarea interfeței. Deoarece toate serviciile din
sistem depind de binder, acesta trebuie făcut tolerant la defecte prin replicarea tabelelor
sale pe mai multe servere.
Localizarea binder -ului trb uie să fie posibilă tuturor clienților și serverelor și se poate face
printr -una din următoarele metode:
 rularea binder -ului pe un calculator cu adresă cunoscută
 furnizarea adresei curente a binder -ului de către sistemul de operare în
run-time (în timpul e xecuției)
 difuzarea unui mesaj de localizare a binder -ului atunci când clientul și
serverul încep execuția
4.4. Studi u de caz : Sun RPC
Acest sistem utilizează pentru specificarea unei interfețe RPC un limbaj de definire a
interfeței, numit XDR (un exemplu e dat în fig.4.5). Pe baza definiției de interfață
compilatorul de interfa ță (rpcgen ) va genera:
 procedurile cotor ale clientului
 procedura main a serverului, dispecerul, procedurile cotor ale
serverului
 procedurile de compunere și descompunere
 un fișier h eader cu constantele și tipurile comune clientului și
serverului

Fig.4.5. [1]

Programul client importă serviciul de interfață (procedura clnt_create din fig.4.6).
Procedura întoarce un client_handle , care conține informațiile de comunicar e
(descriptorul și adresa de soclu). Apelul la distanță se face indirect prin apelarea
procedurii cotor a clientului ( read_2 ). Aceasta la rândul său va apela procedura de
invocare clnt_call (similară cu DoOperation , de tip at -least-once), care va face invo carea
serverului.
Programul server constă din:
 procedurile server (fig.4.7), care utilizează prototipurile din fișierele
header create de rpcgen
 procedura main , care creează un soclu și exportă interfața la serviciul
de legare
 dispecerul
 procedurile de com punere/descompunere a argumentelor

Fig.4.6. [1]

Fig.4.7. [1]

Legarea este locală, pe fiecare calculator fiind un așa -numit portmapper . La pornirea
serverului, acesta se înregistrează la portmapper -ul local. La pornirea cl ientului, se face o
invocare la distanță a portmapper -ului serverului, de la care află numărul de port.

4.5. RPC de tip asincron
Metoda RPC asincron permite lansarea de cereri consecutive la server fără așteptarea
răspunsului la apelul precedent ( fig.4.8 ). Astfel nu se blochează clientul, se reduce timpul
și pot fi emise cereri consecutive către mai multe servere. Cererile consecutive la același
server pot fi înșiruite î ntr-un buffer la client și trimise împreună printr -o singură
comunicație.

Fig.4.8. (adaptare după [1])

4.6. Invocarea metodelor la distanță
Obiectul (object ) reprezintă o entitate software autonomă, care încapsulează date și codul
operațiilor posibile asupra acestora. Operații asupra datelor se pot efectua numai prin
invocarea metod elor pe care le pune la dispoziție obiectul la nivelul interfeței sale
(fig.4.9). Detaliile de implementare ale unei metode nu sunt vizibile la nivelul interfeței
obiectului. Invocația unei metode poate modifica starea obiectului respectiv sau poate
determ ina invocația unei metode al unui alt obiect în cazul invocațiilor încuibate
(fig.4.10). Pentru a putea fi referit, fiecare obiect dispune de câte un identificator propriu
(OID – Object Identifier ). Obiectele similare aparțin unei clase , prin care se speci fică
variabilele și implementarea metodelor, precum și semnătura corespunzătoare fiecărei
metode (tipul argumentelor și al rezultatelor). Fiecare obiect nou creat reprezintă de fapt
câte o instanță a unei clase. Clasele sunt organizate ierarhic, permițând moștenirea datelor
și metodelor clasei părinte, la care se pot adăuga eventuale extensii.

Fig.4.9. (adaptare după [1])

Fig.4.10. [1]

Obiectele sistemului distribuit sunt în general puternic interconectate, invocându -se unul
pe altul pri n aceste conexiuni, ceea ce ridică probleme de migrație și replicare. O altă
problemă este cea a obiectelor partajate din aplicațiile multiutilizator (de exemplu în
figura 4.11, obiectele la distanță O1 și O2 partajează obiectul local O3). În primul rând,
pentru a menține consistența obiectelor partajate, metodele sale trebuie să fie atomice. Pe
lângă aceasta, poate fi necesar ca informația să fie de lungă viață, adică să existe obiecte
persistente care supraviețuiesc și dacă nu se mai lucrează cu ele. (În general, pentru a
economisi memorie, obiectele care nu mai dispun de referințe sunt distruse de un colector
de gunoaie.) Obiectele persistente se păstrează sub formă aplatizată pe disc și la nevoie se
activează, respectiv se pasivizează în mod transparent.

Fig.4.11. [1]

În sistemele distribuite obiectele sunt răspândite la diferite procese sau calculatoare.
Invocarea unei metode trebuie fă cută prin trimiterea unui mesaj la distanță, operație care
se numește Remote Method Invocation (RMI). Mesajul trebuie să conțină un
identificator al obiectului aflat la distanță (ROID – Remote Object Identifier ). Se impune
ca RMI să fie transparent, adică un obiect trebuie să fie capabil de invocarea unui alt
obiect indiferent dacă acesta este local sau se află la distanță. Pentru aceasta, fiecare
obiect la distanță trebuie să dispună de un proxy local, care se comportă ca un obiect local
față de cel care invocă, dar în loc să execute metoda, transmite mesajul mai departe
obiectului la distanță. Obiectul de stinație astfel accesat are un obiect skeleton (schelet) , a
cărei clasă are ca și metode procedurile cotor server. Desfășurarea unui RMI se poate
urmări pe figura 4.1 2, pe care se identifică următorii pași:
 obiectul X invocă proxy -ul local
 metoda cotor a p roxy-ului compune ROID -ul, numele metodei și argumentele
într-un mesaj
 modulul de comunicație transmite mesajul de cerere ( Request ), care e
recepționat de modulul de comunicație al destinației
 dispecerul, pe baza ROID -ului și a numelui metodei, invocă o me todă cotor a
skeleton -ului obiectului A
 skeleton -ul descompune argumentele și invocă metoda corespunzătoare din
obiectul A
 rezultatul se compune de skeleton și se transmite într -un mesaj de răspuns
(Reply )
 proxy -ul descompune răspunsul și îl furnizează cli entului

Fig.4. 12. (adaptare după [1])

Gestionarea proxy -urilor și a ROID -urilor este asigurată de către modulul ROID, care are
un tabel de corespondență între identificatorii locali și cei la distanță. Sistemul distribuit
bazat pe obiecte trebuie să disp ună de un serviciu de nume oricât de simplu, care să
realizeze maparea numelor textuale în identificatori ROID. Tipurile datelor care pot fi
transmise ca argumente se definesc printr -un limbaj de definire a interfeței (IDL –

Interface Definition Language ). Compilatorul de interfață este cel care pe baza definiției
va genera automat proxy -ul și skeleton -ul.
Limbajul de definire a interfeței (IDL) este folosit pentru definirea interfețelor, a tipurilor,
atributelor și semnăturii metodelor. Definiția unei interfețe IDL este similară cu definiția
interfeței unei clase, având un nume și o mulțime de metode accesibile clienților.
Interfața IDL poate avea și atribute proprii obiectelor (de genul variabilelor), metodele
pentru accesarea și actualizarea lor fiind gen erate automat de către compilatorul de
interfață. Semnătura unei metode definește numele său, numele și tipul parametrilor
utilizați, precum și numele și tipul rezultatului. Semnătura specifică de asemenea numele
și parametrii unei eventuale excepții care se poate produce în urma invocării. Tot
semnătura poate specifica semantica folosită la apel, cea implicită fiind de tip at-most –
once . Un exemplu simplu de definire a interfeței este dat în figura 4.13. Obiectul la
distanță Association , a cărui interfață e ste aici definită, face asociere între un șir de
caractere introdus de la tastatură ( key) și un șir de date ( value ). În semnăturile metodelor
parametrii in sunt de intrare, iar cei out sunt argumentele returnate. În afară de cele patru
metode invocabile as upra obiectului, este definită și o excepție, argumentul său fiind
furnizat astfel încât să permită raportarea cauzei excepției către client.

Fig.4.13. [1]

4.7. Invocarea la distanță în Java
În Java RMI fiecare obiect la distanță trebuie să aparțină unei clase Remote , care
implementează o interfață la distanță. Astfel, fiecare interfață la distanță va extinde
interfața Remote furnizată în pachetul java.rmi . În exemplul din figura 4.14 este
arătată interfața Java Remote (la distanță) numită Association (care extinde clasa
Remote ) la un obiect care reprezintă o mulțime de asocieri la distanță. Parametrii de
intrare reprezintă la interfața Java Remote parametrii ordinari Java, iar cei de ieșire o

singură valoare returnată. Interfața Java defin ește un nou tip și este dată sub forma unui
set de metode abstracte (fără implementare). Fiecare metodă trebuie să arunce excepția
RemoteException sau o excepție specifică aplicației.

Fig.4.14. [1]

Fig.4.15. [1]

Proiectul exemplului ales este dat în figura 4.15. Obiectul client utilizează RMI pentru a
invoca metodele din interfața Association . Asocierile sunt stocate în obiectul Hashtable
(având clasa definită în pachetul java.util), fiind folosite metodele acestuia astfel:
 putAssociation folosește metoda put a lui Hashtable pentru înregistrarea unei
asocieri
 getAssociation folosește metoda get a lui Hashtable pentru obținerea valorii
asociate cheii furnizate
 deleteAssociation folosește metoda remove a lui Hashtable pentru ș tergerea
unei asocieri
 enumerate folosește metoda elements a lui Hashtable la invocarea unei
enumerări

Metoda elements produce un obiect Java local numit Enumeration (având clasa definită
în pachetul java.util). Pentru a furniza clientului valorile return ate de la invocarea
metodei enumerate , se definește o interfață la distanță RemoteEnumeration (fig.4.16).
Astfel clientul, prin invocarea metodelor nextElement și hasMoreElements poate obține
asocierile din tabel unul câte unul.

Fig.4. 16. [1]

Când se creează un obiect la distanță, el este înregistrat în Java RMI Registry . Acesta
este un server de nume, care furnizează o instanță a clasei Naming , având metode ( bind și
lookup ) pentru înregistrarea și căutarea de obiecte la distanță. Obiectul client din figura
4.15 dispune de doi identificatori ROID: cel al obiectului Association a fost obținut de la
Java RMI Registry, iar cel al obiectului RemoteEnumeration s-a obținut ca și rezultat al
invocării lui enumerate .

Fig.4.17. [1]

Fig.4.18. [1]

Clasa unui obiect la distanță trebuie să implementeze interfața sa la distanță. Figura 4.17
arată clasa RemoteEnumerationImpl , care implementează interfața la distanță
RemoteEnumeration și extinde clasa UnicastRemoteObject . Implementarea clasei pentru
obiectul la distanță Association este dată în figura 4.18. Clasele proxy și skeleton sunt

generate de compilatorul RMI (numit rmic), aplicat fișierelor care conțin implementările
claselor ( RemoteEnumerationImpl și AssociationImp l).
Obiectul având interfața la distanță Association este pornit prin furnizarea clasei
AssociationImpl interpretorului Java. Clasa skeleton se va încărca automat. Clasa client
(având implementarea din figura 4.19) va căuta numele „Association” în RMI Regi stry,
apoi va verifica dacă ROID -ul returnat este de tip Association . În continuare programul
va apela de câteva ori putAssociation , pentru a stoca câteva asocieri. După aceea va
invoca enumerate , și va obține în consecință un ROID al instanței lui
RemoteE numeration . Cu acest identificator va accesa asocierile, folosind cele două
metode ale enumerării la distanță.

Fig.4.19. [1]

În concluzie, Java RMI oferă o implementare clară a invocării metodelor la distanță, dar
presupune ca toate obiect ele implicate să fie scrise în Java.

5. SISTEME DE OPERARE DISTRIBUITE

5.1. Introducere
Similar cu un sistem de operare convențional, sistemul de operare distribuit constă dintr -o
colecție de elemente soft care simplifică munca de programare și permite rularea unei
mari varietăți de aplicaț ii. Spre deosebire de sistemul de operare convențional, cel
distribuit este modular și extensibil, permițând adăugarea de noi componente în funcție
de cerințele aplicațiilor. Sarcina sistemului de operare este de a permite programarea
convenabilă a sistemu lui distribuit, prezentând către aplicații o abstractizare a resurselor
(canale de comunicație și procese în loc de rețele și procesoare). Implementarea se
realizează printr -o colecție de kernel -e și procese server, care reprezintă de fapt
manageri de resu rse, prin care se asigură o gestionare transparentă a resurselor
indiferent de locul acestora în rețea. Față de managerii de resurse se pot formula
următoarele cerințe:
 Încapsularea , care presupune existența unei interfețe utilizabile pentru
efectuarea de operații asupra resurselor.
 Prelucrarea concurentă , ceea ce înseamnă ca să permită partajarea
resurselor și accesul concurent la acestea din partea clienților.
 Protecția , adică asigurarea protecției resurselor față de accese ilegale.
În caz de invocare a u nei resurse, sistemul trebuie să asigure:
 Rezoluția numelui, în vederea localizării resursei.
 Comunicația pentru transmiterea argumentelor și a rezultatului.
 Planificarea operației în cadrul kernelului sau a serverului.

5.2. Kernelul
Kernelul reprezintă u n program care se poate executa cu privilegii de acces complet la
resursele fizice ale calculatorului gazdă, adică în mod supervizor. Procesele utilizator au
drepturi limitate, fiind executate în mod utilizator. Kernelul instaurează câte un spațiu de
adres ă împreună cu drepturi de acces pentru fiecare proces, p entru a putea proteja
procesele între ele. I nvocarea resurselor gestionate de kernel se face prin apeluri de
sistem folosind capcane ( traps ), care sunt de fapt întreruperi prevăzute în program.
Un sis tem de operare distribuit are caracter deschis , spre deosebire de cel convențional,
care dispune de kernel monolitic. Caracterul deschis este asigurat de arhitectura
organizată în jurul unui mikrokernel , care conține numai funcțiile de bază ale sistemului
de operare: gestionarea proceselor, a memoriei, a comunicației locale între procese.
Celelalte servicii de sistem sunt încărcate dinamic în funcție de cerințe, fiind invocate
prin RPC (fig.5.1). Avantajele acestei arhitecturi sunt deschiderea, modularitate a,
probabilitatea redusă a defectelor, portabilitatea.

Fig.5.1. (adaptare după [1])

Arhitectura microkernelului are în componență (fig.5.2):
 Managerul de procese, cu rol de creare a proceselor și de efectuare a unor
operații de nivel scăzut asupra acesto ra.
 Managerul de fire de execuție, care asigură crearea, sincronizarea și
planificarea firelor.
 Managerul de comunicație, care asigură comunicația între firele atașate la
procese locale.
 Managerul de memorie, pentru gestionarea memoriei fizice, a memoriei
virtuale și a memoriilor cache.
 Supervizorul, care servește la dispecerizarea întreruperilor, a apelurilor de
sistem prin capcane și a excepțiilor.

Fig.5.2. (adaptare după [1])

5.3. Procese și fire de execuție
Într-o accepțiune generală, procesul poate f i considerat ca fiind format dintr -un mediu de
execuție și unul sau mai multe fire de execuție. Mediul de execuție reprezintă colecția
acelor resurse gestionate de kernelul local (spațiu de adrese, resurse de sincronizare,
resurse de comunicație) la care p rocesul are acces. Firul de execuție (thread ) constituie o
abstractizare a unei activități din cadrul procesului Rolul firelor este de a crește
concurența prelucrării, firele aparținând aceluiași proces având acces la resursele
mediului de execuție al proc esului respectiv, dar sunt protejate față de firele aparținând
altor medii. Spațiul de adrese este format din regiuni continue care nu se suprapun
(fig.5.3). În unele cazuri (kernel, librării, date comune, zone de comunicație) o regiune
poate fi partajată între mai multe spații de adrese.

Fig.5.3. (adaptare după [1])

Crearea unui nou proces constă din următoarele activități:
 alegerea unui calculator gazdă, pe baza unei strategii de alocare (de exemplu
de echilibrare a încărcării sistemului)
 crearea unui m ediu de execuție
 static, pe baza unei liste care prevede dimensiunile regiunilor
 prin moștenirea regiunilor de la procesul părinte
 crearea unui fir de execuție
În caz de moștenire a regiunilor, una din abordări prevede folosirea partajată a spațiului
de ad rese al procesului părinte cu noul proces, iar într -o altă abordare se face o copie
identică a acesteia pentru a fi la dispoziția noului proces. O soluție intermediară (numită
copy -on-write ), menită să asigure un plus de eficiență, prevede doar copierea lo gică

(adică partajarea) spațiului, copierea fizică fiind făcută atunci când unul din procese
efectuează o operație de scriere în spațiul respectiv . Porturile de comunicație nu pot fi
moștenite sau partajate.
Firele de execuție pot fi utilizate:
 la server ( fig.5.4), când fiecare fir recepționează cereri prin ac elași port și
efectuează aceeași procedură de prelucrare
 la client ( fig.5.5), când primul fir pune rezultatele într -un buffer, de unde al
doilea le preia și efectuează un RPC la server, astfel primul nef iind blocat cu
așteptarea răspunsului
Firele de execuție sunt de preferat proceselor multiple, deoarece sunt mai simplu de
gener at și ges tionat. Fiind un singur spațiu de adrese, comutarea de la un fir la altul e mai
ușoară, dar nu există protecție între ele.

Fig.5.4. (adaptare după [1])

Fig.5.5. (adaptare după [1])

Programarea firelor este concurentă, lucru sprijinit de anumite limbaje. Sunt aici de
amintit librăriile C Threads dezvoltate pentru sistemul de op erare distribuit Mach , precum
și GNU Threads dezvoltate pentru sistemul Sun. Crearea, distrugerea sincronizarea firelor
de execuție se poate face în mod dinamic folosind ap eluri de sistem . Apelul de creare a
unui nou fir întoarce un identificator pentru acesta.

Planificarea firelor poate fi:
 preemtivă, când un fir aflat în execuție poate fi suspendat de altul
 nepreemtivă, când un fir nu poate fi suspendat de altul
Implementa rea firelor se poate face la nivel utilizator (sub forma unei librării de
proceduri legate de programele de aplicație) sau la nivel de kernel.

5.4. Folosirea numelor și protecția resurselor
Pentru identificarea unei resurse de către client, este nevoie de doi identificatori unici
(fig.5.6):
 identificatorul de comunicație, pentru a desemna portul serverului care
gestionează resursa
 identificatorul serviciului (necesar dacă nu e alocat câte un port fiecărui
server)

Fig.5.6. (adaptare după [1])

Pentru clien ți este de dorit ca localizarea resursei să fie transparentă. Acest lucru se
asigură de către subsistemul de comunicație implementat de kernel. Transparența poate fi
de două feluri:
 transparența locației, când la o reconfigurare a sistemului relocarea
serviciului (care presupune mobilitatea resursei) este transparentă, dar
resursa nu poate fi accesată pe perioada mutării
 transparența migrației, când resursa e accesibilă și în timpul mutării
Protecția resurselor urmărește faptul ca fiecare proces să poată ac cesa numai resursele pentru
care dispune de dreptul de acces. Protecția se realizează cu ajutorul domeniului de protecție ,
care reprezintă o noțiune abstractă căruia îi aparține o colecție de procese și o listă de tipul
<resursă, drepturi de acces >, prin c are se specifică resursele la care procesele din domeniul

respectiv pot avea acces și drepturile aferente. Implementarea concretă se poate face prin două
metode, utilizând:
 capabilități, când accesul este permis numai dacă procesul solicitant dispune
de ca pabilitatea cerută (capabilitatea fiind un identificator greu de falsificat)
 liste de control, când fiecare resursă dispune de câte o listă cu domeniile
care pot avea ac ces la ea și drepturile corespunzătoare

5.5. Comunicația și invocarea
Invocarea unei p roceduri locale sau la distanță de către un proces prin intermediul
sistemului de operare implică schimbarea spațiului de adrese și implicit a domeniului de
protecție. Transferul de mesaje între două procese aflate pe calculatoare diferite este
asigurat de kernelul sistemului de operare prin primitivele de tip Send și Receive . În acest
caz invocarea necesită și comunicație prin rețea, ceea ce afectează în mod hotărâtor
performanța RPC (fig. 5.7). Întârzierea introdusă crește desigur în funcție de lungimea
datelor de transmis (argumente, rezultate), fiind mai mare dacă aceste date trebuie
divizate pe mai multe pachete.

Fig.5.7. (adaptare după [1])
Pentru creșterea eficienței în cazul unui apel local (pe același calculator), s -a elaborat
mecanismul L RPC ( Light weight RPC ), bazat pe utilizarea unei regiuni partajate între
client și server . Transferul argum entelor, respectiv a rezultatului se face printr -o stivă
comună și implică următorii pași (fig.5.8):
1. argumentele sunt compuse și depuse în stivă
2. se apelează ker nelul (prin trap), clientul îi prezintă capabilitățile
3. kernelul comută contextul în mediul serverului ( upcall )
4. se execută procedura și se depun rezultatele în stivă
5. firul revine la kernel, care îl comută înapoi în mediul clientului

Fig.5.8. (adaptare după [1])

5.6. Memoria virtuală
Memoria virtuală reprezintă un concept pentru extinderea dimensiunii memoriei
principale, fiind implementată transparent prin combinarea memoriei principale cu
memoria de masă (dispozitivul de stocare, în particular discul hard ). Gestionarea
memoriei virtuale se face prin paginare, spațiul de memorie virtual fiind împărțit pe zone
de dimensiuni fixe numite pagini. În caz de solicitare a unei date, dacă aceasta nu se află
în memoria principală se generează o excepție ( page fault ) și pagina respectivă se aduce
de pe dispozitivul de stocare în memoria principală. Problema în sistemul distribuit o
reprezintă faptul că, spre deosebire de sistemul convențional, memoria de masă se poate
afla pe un alt calculator. Paginile acesteia sunt gestionate de un manager de memorie
numit pager (mapper ) extern (fig.5.9). Pentru a mapa un obiect de memorie într -o
regiune a spațiului de adrese a procesului de pe calculatorul solicitant, kernelul de pe
acest calculator transmite o cerere către pagerul extern. După aceea are loc un schimb de
mesaje, prin intermediul rețelei, pentru aducerea paginii de la pager, respectiv
transmiterea datelor actualizate către acesta (în vederea asigurării consistenței datelor).
Pagerul funcționează de fapt ca un server a flat la distanță.

Fig.5.9. (adaptare după [1])

6. SERVICIUL DE FIȘIERE

6.1. Introducere
Rolul unui seviciu de fișiere este de a permite organizarea, citirea/scrierea/ștergerea
fișierelor , gestionarea numelor acestora , protecția și partajarea fișierelor. Într -un sistem
de operare convențional, sistemu l de fișiere are o organizare ierarhică, compusă din
următoarele module:
 modulul director, care asociază nume de fișier la identificatori de fișiere
 modulul de fișiere, care atribuie identificatori fișierelor
 modulul de control a accesului, care verifică d reptul de execuție a operației
solicitate
 modulul de acces la fișiere, care citește su scrie date de fișier sau atribute
 modulul de bloc, care accesează și alocă blocuri pe disc
 modulul de dispozitiv, care efectuează oper ațiile de intrare/ieșire cu discul
Într-un sistem distribuit, serviciul de fișiere trebuie să permită programelor utilizator
accesul fișierelor aflate la distanță (prin RPC). Următoarele caracteristici sunt valabile, în
parte sau în totalitate, acestor sisteme:
 transparența accesului  aceleași operații se folosesc pentru acceul fișierelor
locale și a celor la distanță
 transparența locației  fișierele pot fi relocate fără modificarea numelor
căilor de acces
 transparența concurenței  permite accesul simultan al mai multor clienți la
același fișier
 transparența defectării  defectarea clientului sau întreruperea funcționării
serverului nu trebuie să ducă la inconsistență
 transparența performanței  funcționarea trebuie să rămână corectă la
schimbarea încărcării sistemului
 transparența replică rii  pot exista copii ale aceluiași fișier pe mai multe
servere
 transparența migrației  permite mobilitatea fișierelor
 eterogenitatea hardware și a sistemelor de operare
 scalabilitatea sistemului

6.2. Structura sistemului de fișiere
Componentele sistemu lui de fișiere al unui sistem distribuit sunt următoarele (fig.6.1):

 Serviciul plat de fișiere , care prmite efectuarea de operații de
citire/scriere/ștergere asupra fișierelor. Pentru fiecare fișier nou generează câte
un identificator unic de fișier (UFID) , care va fi folosit mai târziu la orice
referire ulterioară.
 Serviciul de directoare , care efecuează maparea între nume le textual și UFID –
ul fișierului, efectuând căutarea după identificator pe baza numelui de fișier. El
permite crearea/modificarea intrăr ilor în directoare, fișierele directoare fiind
păstrate în serviciul plat de fișiere (structura ierarhică de fișiere este asigurată
de modulul client). Ca urmare serviciul de directoare reprezintă un client
pentru serviciul plat de fișiere. Serviciul de di rectoare face și verificarea
autorizării utilizatorului pentru acces.
 Modulul client , care rulează pe fiecare calculator, oferă o interfață unică către
utilizatori pentru operații cu fișiere și care ascunde componentele de nivel
scăzut ale sistemului. Modu lul client este responsabil și de localizarea fișierelor
aflate la distanță. El poate gestiona un cache la client pentru eficientizarea
acceselor.

Fig.6.1. (adaptare după [1])

Un fișier conține date și atribute. Datele și o parte din atribute sunt gest ionate de serviciul
plat de fișiere, iar celelalte atribute de către serviciul de directoare (cele nehașurate din
fig.6.2).
În vederea asigurării toleranței la defecte a sistemului de fișiere se pot prevedea diferite
măsuri. O astfel de măsură este proiect area interfeței RPC cu operații idempotente, astfel
încât un eventual acces repetat să nu ducă la actualizări eronate a le datelor. O altă măsură

prevede proiectarea de servere fără stare ( stateless ), care pot fi repornite cu reluarea
corectă a funcției dup ă defectare, fără a fi necesară restabilirea stării anterioare.

Fig.6.2. (adaptare după [1])

6.3. Interfețe
Serviciul plat de fișiere asigură operațiile din fig.6.3. C u excepția lui Create , toate aceste
operații sunt idempotente, permițând utilizarea sem anticii RPC de tip at-least -once .
Interfața este potrivită pentru implementarea serverelor fără stare.

Fig.6.3 . (adaptare după [1])

Modulul client furnizează o interfață de nivel înalt pentru programele de aplicație în
vederea accesului la sistemul plat de fișiere . Un exemplu de utilizare în programul de
aplicație îl reprezintă procedura CopyFile , care face copierea unui fișier:

File2: =Create();
FOR i:=1 TO Length(File1) BY MAX DO
Write(File2, i, Read(File1, i, MAX));
END

Definiția interfeței R PC a serviciului de directoare este dată în fig.6.4. Serviciul de
directoare gestionează anumite atribute ale unui fișier:
 contorul de referințe (numărul de înregistrări care există în director pentru
acest fișier)
 proprietarul (identificatorul celui care a făcut prima înregistrare a fișierului în
director)
 tipul (fișier sau director)
 lista de control a accesului (lista celor autorizați pentru acces și drepturile lor)

O structură ierarhică de directoare și fișiere, confortabilă utilizatorilor, poate fi
implementată de către modulul client, care va folosi la rândul său serviciul plat de fișiere
și serviciul de directoare.

Fig.6.4. (adaptare după [1])

6.4. Tehnici de implementare
Pentru a permite implementarea sistemului de fișiere pe mai multe servere, se i ntroduce noțiunea de grup
de fișiere. Acesta reprezintă o colecție de fișiere amplasate pe același calculator. Identificatorul grupului
trebuie să fie unic, de exemplu se poate genera prin concatenarea adresei IP a calculatorului cu un nuăr
întreg obținut de la un contor:

Separarea serviciului de fișiere de cel de directoare poate conduce la goluri de spațiu pe
disc, în cazul în care un program (numit program delicvent) care a creat un fișier, se
termină fără a înregistra UFID -ul fișie rului într -un director sau fără a șterge fișierul.
Rezolvarea problemei intră în responsabilitatea modulului client, care trebuie să conțină o
operație de forma

CreateFile (Name, Dir )
unde Name e numele fișierului și Dir reprezintă UFID -ul directorului în care se face
înregistrarea.
Protecția resurselor în fața accesului neautorizat se realizează:
 în serviciul plat de fișiere pe bază de capabilități, drepturile de acces fiind
codificate însăși în UFID
 în serviciul de directoare pe baza listei de control, pe care se verifică
autorizarea accesului în funcție de identitatea utilizatorului și a modului de
acces solicitat
În serviciul plat de fișiere UFID -ul fiind folosit drept capabilitate, el trebuie gener at astfel
încât să asigure unicitatea și să fie greu de falsificat. De exemplu, se poate construi prin
concatenarea identificatorului de grup, a numărului de ordine al fișierului (în cadrul
grupului), a unui număr aleator (stocat împreună cu atributele fiș ierului, dar inaccesibil cu
GetAttributes ) și a unui câmp de permisie (pentru a permite accesul selectiv din partea
diferiților clienți):

La crearea fișierului se returnează UFID -ul setat cu drepturi depline, dar la cereri de
Lookup ale altor clienți, se returnează cu autorizări selective. Pentru creșterea securității,
câmpurile „nr. aleator” și „de permisie” se criptează de serviciul de directoare:

Se păstrează și un duplicat necriptat al biților de permisie, pent ru a permite oricărui
program client sau server să examineze permisiunile incluse în UFID. Pentru criptare,
respectiv decriptare, s erviciul de directoare și serviciul plat de fișiere pot utiliza aceeași
cheie secretă, dar această soluție oferă securitate r edusă. O altă metodă utilizează pentru
criptare o funcție cunoscută, iar serverul plat de fișiere aplică aceeași funcție

unidirecțională pentru copia numărului aleator (păstrat împreună cu fișierul) și biții de
permisie necriptați din UFID. Rezultatul aces tei noi criptări se compară cu câmpul criptat
din UFID -ul furnizat pentru autorizarea accesului.
Serviciul plat de fișiere este responsabil de stocarea fișierelor pe disc. Fiecare fișier se
păstrează sub forma unei mulțimi discontinue de blocuri (pagini). Indicatorul (pointerul)
blocurilor componente ale fișierului se stochează împreună cu atributele fișierului într -un
index de bloc (fig.6.5 ). La crearea unui fișier se obține doar un index de bloc, care va fi
apoi completat cu pointeri pe măsura creșterii f ișierului.

Fig.6.5. (adaptare după [1])

În cazul unui acces la un fișier, pentru a -l putea localiza, pe baza UFID -ului trebuie
determinate următoarele două elemente:
 identitatea serverului  se efectuează de către modulul client prin apelarea
funcției GetServerPort a serviciului plat de fișiere, care prezintă o interfață de
forma:
GetServerPort (FileGroupID )  PortID  REPORTS (UnknownFileGroup )
 adresa fișierului  constă din localizarea indexului de bloc al fișierului și se
face de către serviciul plat c are păstrează fișierul, pe baza corespondenței:
nr. fișier  adresă index de bloc
Pentru creșterea performanței, în general se implementează câte o memorie cache la server și
la client:
 Cache -ul serverului reține copiile celor mai recent utilizate blocuri. La
operațiile de tip GetBlock și PutBlock ale modulului de transfer a blocurilor
din cadrul serviciului plat de fișiere se verifică prima dată dacă pointerul de
bloc împreună cu blocul e prezent sau nu în cache. În caz afirmativ blocul se
ia din cache, și numai în caz contrar de pe disc.

 Cache -ul clientului păstrează copiile celor mai recent utilizate blocuri, atribute
și intrări de directoare. La orice operație de tip Read sau Write din partea
programului utilizator către modulul client, se verifică dacă se află sau nu în
cache blocul care conține data cerută și în caz afirmativ se furnizează de aici.

6.5. Sistemul Sun NFS ( Network File System )
În general fiecare calculator din sistemul NFS are instalate module client și server.
Fiecare client își poate c onstrui propria ierarhie de fișiere în care montează de la distanță
(remoute mount ) fișiere aflate pe alte calculatoare server (fig.6.6). Pentru a elimina
inconvenientul montării, la fiecare client poate rula un Automounter , care acționează
automat în cazu l în care utilizatorul face referire la o cale către un fișier nemontat.
Același fișier poate avea căi diferite la clie nți diferiți. Sistemul NFS nu rezolvă
transparența replicării, a concurenței și scalabilitatea.

Fig.6.6. [1]

Implementa rea sistemului NFS este arătată în fig.6.7. Serviciul de directoare și serviciul
plat de fișiere sunt integrate în NFS server. La client există un portmapper , care face
legarea la serviciu pe bază de nume în loc de număr de port. Comunicația cu serverul se
face prin RPC, interfața NFS a serverului conținând operații similare cu cele definite la
punctul 6.3 ( lookup, create, remove, getattr, setattr, read, write, rename etc.). Pentru a
distinge între fișierele locale și cele aflate la distanță, la client s -a implementat un sistem
virtual de fișiere (VFS). Fiecare nod al său conține un indicator, care este o referință dacă
fișierul e local. Pentru fișierele aflate la distanță, în loc de UFID se utilizează un file-
handle , care are structura:

Fig.6.7. (adaptare după [1])

La fiecare acces clientul trimite informația de autentificare ( UserID, GroupID ) care se
compară cu drepturile de acces din atributele fișierului.
În fiecare server NFS rulează la nivel utilizator câte un serviciu de montare a fișierelor.
La o comandă Mount (remoteHost, path, localName ) a clientului acesta returnează file-
handle -ul directorului specificat prin path.
Cache -ul serverului este implementat prin metoda write -through (actualizările se
operează imediat și pe disc), de oarece datele fiind scrise de către client, el nu va ști că ele
s-au pierdu t în caz de cădere a serverului. În c ache-ul clientului, fiecare bloc se păstrează
împreună cu o ștampilă de timp pentru a preveni inconsistența. Pentru a valida blocurile
din cache ale unui fișier, clientul cere de la server ultimul timp când fișierul a fost
modificat și dacă acesta e diferit de cel din cache, atunci invalidează toate blocurile din
cache aparținătoare fișierului respectiv. Transmiterea blocurilor modificate către se rver în
vederea actualizării pe disc, se poate face de către un bio-daemon , care rulează
independent la fiecare client.

7. SERVICIUL DE NUME

7.1. Introducere
Serviciul de nume se apelează de către clienți pentru a obține informații despre resurse
sau obiecte, atunci când se dă numele acestora. Informațiile obținute pot fi adrese sau, în
general, atribute ale unui utilizat or, calculator, domeniu de rețea, serviciu, fișier.
Exemplul din figura 7.1 arată modul în care, pentru a accesa un fișier aflat pe un
calculator server, se obține de la serviciul de nume un identificator al resursei pe baza
numelui textual.

Fig.7.1. (adaptare după [1])

Asocierea dintre numele și atributele unui obiect se numește legare (binding ). Atributele
la rândul lor pot fi numere sau alte nume (texte). Acele atribute, care nu pot fi reduse mai
departe, reprezintă primitive (de exemplu o adresă Ether net).
Numele se pot referi la:
 un obiect în cadrul unui serviciu, legarea fiind atunci efectuată chiar de acel
serviciu
 o resursă în cadrul sistemului distribuit, caz în care legarea este efectuată de
un server de nume
Serverul de nume păstrează o bază de date cu legături între numele textual și atribute.
Operația de returnare a atributelor pe baza numelui poartă numele de rezolvarea
(rezoluția) numelui (name resolution ). Cerințele care se ridică față de un server de nume
sunt în general următoarele:
 să ges tioneze un număr arbitrar de mare de nume
 să aibă durată lungă de viață (să suporte multe modificări)

 să prezinte disponibilitate ridicată
 să permită izolarea defectelor
 să prezinte toleranță la neîncredere față de clienți
7.2. Un serviciu de nume model
Spațiul numelor reprezintă totalitatea numelor valide recunoscute de serverul de nume.
Partiționarea spațiului de nume poate fi făcută:
 fizic, când în nume apare explicit numele serverului (de exemplu
numeProprietar @numeServer )
 organizațional, când în nume s e regăsește divizarea administrativă ier arhică
a organizației
Pentru exemplificare se prezintă în continuare un serviciu simplu de nume, denumit SNS
(Simple Name Service ). Pentru ca spațiul să fie mai ușor gestionabil, el este partiționat
organizațional. N umele de directoare și subdirectoare apar ca și prefixe despărțite cu
puncte în sintaxa unui nume, de exemplu: .cs.distrib.gene . Numele pure (care nu conțin
adresă), permit relocarea obiectelor în cadrul sistemului. Un domeniu al numelor
reprezintă un subs pațiu al numelor pentru care există o singură autoritate administrativă
care poate atribui nume în cadrul său (un exemplu de domeniu este .cs. … .)
Serverul SNS păstrează înregistrări de forma
< Nume > < Tip, Valoare >
prin care se asociază unu i nume textual niște atribute. A tributele posibile la acest sistem
sunt date în figura 7.2. Procedurile oferite de SNS permit căutarea după atribute pe baza
numelui, precum și efectuarea, respectiv ștergerea unei înregistrări în baza de date:

Fig.7.2. (adaptare după [1])

Rezoluția numelui este în general un proces iterativ, în care numele derivat se prezintă
repetat unui alt context, până se obțin atributele primitive. La SNS contextul corespunde
unui director, de exemplu pentru rezol varea numelui .cs.distrib.gene contextele
consecutive sunt:

În cazul organizațiilor mari, informațiile legate de nume se păstrează pe mai multe
servere, care stochează partiții diferite ale bazei de date. Structura logică a spațiului de
nume SNS este mapată pe mai multe servere fizice (fig.7.3). Fiecare server păstrează
datele pentru unul sau mai mulți subarbori, prec um și numele directorului din nivelul
superior.

Fig.7.3. [1]

Procesul de localizare a datelor printre mai multe servere pentru rezolvarea unui nume se
numește navigare . Navigarea se efectuează de către un agent utilizator (UA  User
Agent ), care rulează pe fiecare calculator, fiind partajat între toate procesele de pe acesta
(fig.7.4 ). Dacă clientul solicită rezolvarea unui nume, atunci se adresează agentului UA
local, care, începând cu serverul rădăcină, navighează în jos în ierarhia de servere până

obține atributele. Pentru a nu fi necesară de fiecare dată traversarea ierarhiei, UA
păstrează într -un cache înregistrări cu perechi de forma:
 < nume, atribute >  permite rezolvarea imediată a numelui
 < prefixNume, numeServer >  ușurează navigarea
 < numeServer, adresaServer >  elimină necesitatea apelării serverului
rădăcină
Pe lâ ngă câ știgul evident de performanță, prin păstrarea acestui cache devine posibilă și
tolerarea unor servere defecte.

Fig.7.4. [1]

7.3. Alte aspecte de proiectare
În funcție de elementul pe baza căruia se face căutarea obiectelor, există două tipuri de
servicii de nume :
 white page service , la care căutarea este pe bază de nume
 yellow page service , la care căutare se face pe bază de atribute
Metode le de navigare pot fi clasificate în felul următor:
 Navigare iterativă , când UA contactează succesi v serverele de nume, până
rezolvă numele (fig.7.4).
 Navigare cu difuzare în grup (multicast ), când UA difuzează numele de
rezolvat tuturor serverelor de nume, și numai cel care păstrează atributele va
răspunde.
 Navigare controlată de server , când UA apele ază un server de nume care
coordonează rezoluția și trimite înapoi rezultatul. Această navigare poate fi
nerecursivă sau recursivă (fig.7.5). La metoda recursivă UA contactează un
server oarecare, care comunică iterativ sau prin multicast ce celelalte, pân ă

rezolvă numele. La metoda recursivă, UA contactează un server, care dacă nu
conține numele va contacta un alt server ș. a. m. d.

Fig.7.5. [1]

7.4. Sistemul DNS ( Domain Name System )
Sistemul DNS constituie serviciul de nume utilizat de I nternet. Numele sistemului sunt
nume de domenii, de exemplu dcs.qmw.ac.uk . Ele au o organizare ierarhică și pot fi
partiționate organizațional (de exemplu cu terminațiile com, edu, gov, mil, … ) sau
geografic (de exemplu terminate în us, uk, fr, ro, … ).
Serviciile oferite de DNS sunt următoarele:
 rezoluția numelor de host (pe baza numelui de domeniu returnează adresa IP)
 localizarea hosturilor de mail pe baza adresei de e -mail
 rezoluția inversă (returnarea numelui pe baza adresai IP)
 livrarea de informaț ii despre host
 furnizarea listei serviciilor disponibile la host
Baza de date DNS este distribuită pe o rețea de servere (fig.7.6). Fiecare server este
responsabil de câte o zonă (indicată în paranteză pe fig.7.6), pentru care păstrează datele
de mai jos:
 atributele pentru numele din zona respectivă (mai puțin subdomeniile
administrate pe un alt server)
 numele și adresele serverelor care furnizează date autoritare din zonă
 numele și adresele serverelor autoritare din subzonele delegate
 parametri de manageme nt ai zonei (legate de memorii cache, replicare)

Fig.7.6. [1]

Datele fiecărei zone trebuie să fie replicate pe cel puțin două servere independente:
 un server primar ( master ), care conține fișierele cu date autoritare
 servere secundare, ca re preiau datele de pe serverul primar și verifică periodic
actualitatea lor
Oricare server poate depune în cache -ul propriu date obținute de la servere autoritare
(rezultă servere caching -only). Datele din cache au însă un timp de viață (time-to-live), la
expirarea căruia trebuie contactat din nou serverul autoritar.
Agentul utilizator se numește aici resolver . El acceptă cereri pe care le compune în
mesaje (pachete UDP), comunicând apoi prin protocol request -reply cu unul sau mai
multe servere, fiind perm isă atât navigarea recursivă, cât și cea iterativă.
Datele unei zone se păstrează de servere în fișiere, pe tipuri, sub formă de înregistrări
numite resource records . Există câte o astfel de înregistrare pentru fiecare nume de
domeniu.

8. TIMPUL ȘI COORDONAREA

8.1. Introducere
Noțiunea timpului este importantă în sistemele distribuite din mai multe motive. În
primul rând pentru a putea ordona evenimente apărute în calculatoare diferite, este
necesară sincronizarea ceasurilor calculatoa relor. Această sincronizare poate fi externă
(raportată la o sursă autoritară) sau internă (numai între calculatoare). Alte situații în care
este nevoie de utilizarea timpului apar la utilizarea algoritmilor pentru menținerea
consistenței datelor distribui te, verificarea autenticității cererilor la un server sau
eliminarea duplicatelor.
Ceasurile calculatoarelor din sistemele distribuite se clasifică în două tipuri:
 Ceasuri fizice (physical clocks ), care contorizează timpul derivat de la un
oscilator cu fre cvența fixă și stabilă.
 Ceasuri logice (logical clocks ), care urmăresc doar stabilirea unei ordini a
evenimentelor.

8.2. Sincronizarea ceasurilor fizice
Fiecare calculator are propriul ceas fizic, care poate fi folosit pentru a marca momentul
producerii u nui eveniment. Cu toate că baza de timp este asigurată de oscilatoare cu
cuarț, datorită diferențelor de parametri ai circuitelor și a condițiilor de mediu, între
ceasurile diferitelor calculatoare există o derivă . Rata derivei este exprimată sub forma
raportului dintre abaterea ceasului respectiv față de un ceas de referință și valoarea
acestei referințe (
tt ).
Există mai multe feluri de timpi de referință :
 Timpul internațional atomic , care definește secunda ca fiind 1 s = 9 192 631 770
perioade de tranziție între două stări ale Cs133.
 Timpul astronomic , care este derivat din mișcările de revoluți e și de rotație ale
Pământului.
 Timpul universal coordonat (UTC), care constituie standardul internațional
difuzat prin radio și sateliți geosta ționari. El este bazat pe timpul atomic, dar
câteodată se inserează sau șterge o secundă, pentru a fi în acord cu timpul
astronomic. Dacă un calculator dispune de receptor pentru timpul UTC, se pune
problema ajustării ceasului său față de acest timp. Întru cât acest lucru nu este
totdeauna realizabil în mod convenabil prin hard, se preferă ajustarea prin soft,
care înseamnă furnizarea către aplicație a unui timp S(t) modificat față de cel hard
H(t) cu un factor de compensare (t):

S(t) = H(t) + (t) = (1+ a) H(t) + b
Factorul de compensare este de forma (t)=aH(t)+b, unde a și b sunt constante
determinate corespunzător derivei.

Pentru sincronizarea ceasurilor calculatoarelor unui sistem distribuit au fost elaborate mai
multe metode:

1) Metoda lui Cristian se bazează pe interogarea unui server de timp cu receptor UTC.
Un proces P care dorește să -și sincronizeze ceasul, solicită printr -un mesaj mr timpul de
la un server de timp S (fig.8.1). Serverul va insera în mesajul de răspuns mt timpul t pe
care-l arată ce asul său propriu. Ca urmare P își va seta ceasul la un timp estimat dat de
tP = t + Tround/2
unde Tround este intervalul de timp dintre momentul emiterii lui mr și momentul
recepționării lui mt. Dacă timpul de transmisie dintre P și S este de forma
Ttrans = min + x (x0),
unde min reprezintă timpul de transmisie fără încărcare de trafic și conflicte, atunci
intervalul în care e situat timpul estimat de către P va fi
tP  [ t + min, t + Tround  min ]
și
tP = ( t + Tround  min )  ( t + min ) = Tround  2 min
Acuratețea este deci de  ( Tround/2  min ), fiind cu atât mai bună, cu cât Tround este mai
mic. Pentru a tolera căderea lui S, s-a propus difuzarea mesajului mr la un grup de servere
sincronizate UTC și utilizarea primului răspuns primit.

Fig.8.1. [1]

2) Algoritmul Berkeley asigură sincronizarea internă între un grup de calculatoare, unul
fiind desemnat master , restul fiind considerate slave . Masterul efectuează periodic
interogarea calculatoarelor slave și face media timpilor ob ținuți (inclusiv al său), apoi
trimite fiecărui slave cantitatea cu care trebuie să -și ajusteze ceasul. Pentru eliminarea
erorilor introduse de calculatoarele căzute sau cele care furnizează timpi falși, se
efectuează o medie tolerantă la defecte, alegând doar timpii car e nu diferă între ei cu mai
mult decât o valoare maximă specificată. De asemenea, pentru menținerea acurateții se

elimină citirile care corespund unui timp de transmisie mai mare decât o valoare maximă
stabilită dinainte.

3) Protocolul NTP (Network Time Protocol ) este cel folosit la rețeaua Internet.
Sincronizarea ceasurilor are loc în subrețele de sincronizare organizate ierarhic (fig.8.2):
 un server primar, sincronizat la UTC
 servere secundare, sincronizate la serverul primar
 stații de luc ru ale utilizatorilor, sincronizate la servere secundare

Fig.8.2. [1]

Evident acuratețea scade spre straturile inferioare. Sincronizarea dintre servere se poate
face printr -una din următoarele modalități:
 difuzarea în grup, când un server difuzează periodic timpul la celelalte servere
din cadrul unei rețele locale, metoda oferind o acuratețe slabă
 apelul de procedură, care este bazat pe algoritmul lui Cristian, oferind o
acuratețe mai mare
 sincronizarea simetrică, când o pereche de servere schimbă între ele mesaje
care poartă informații de timp, metoda aceasta oferind cea mai mare acuratețe
Sincronizarea simetrică a unui server A față de un server B se face printr -un schimb de
mesaje ( m și m’) între ele (fig.8.3). Mesajul m’ (recepționat la momentul Ti) poartă
ștampilele de timp Ti3, Ti2 și Ti1. (Toți acești timpi sunt dați de ceasurile locale ale
calculatoarelor.) Notând cu tm, respectiv tm’, timpul de transmitere al mesajului m,
respectiv m’, și cu o offsetul dintre ceasuri, se poate sc rie:
Ti2 = Ti3 + tm + o
Ti = Ti1 + tm’  o
Întârzierea datorată transmisiei este:
di = tm + tm’ = (Ti2  Ti3)  (Ti1  Ti) = a  b

Calculul offsetului se face prin scăderea primelor două relații:
2o = a + b + (tm’  tm)
o = (a + b)/2 + ( tm’  tm)/2
Pe baza acestei expresii, offsetul estimat se consideră a fi:
oi = (a + b)/2
Offsetul real nu se poate calcula, dar el se încadrează în intervalul:
oi  di/2  o  oi + di/2
Evident, cu cât întârzierea di este mai mică, măsurarea este mai precisă, dar nu se poate
garanta o limită superioară a erorii (serviciul este de tip best-effort service ). Pentru a
efectua o sincronizare cât mai exactă, serverul face o filtrare a datelor: se rețin ultimele
opt perechi de forma < oi, di>, dintre care se alege acel offset, care corespunde întârzierii
di minime:
  i j j d min do oˆ 

Schimbul de mesaje de sincronizare se face în general între două servere situate în același
nivel, sau între un server și două servere situate în stratul inferior.

Fig.8.3. [1]

8.3. Ceasurile logice
În sistemele distribuite apare adesea necesitatea ordonării evenimentelor . Aceasta se
bazează pe următoarele principii:
 două evenimete în cadrul unui proces se consideră că se succed în ordinea
apariției
 evenimentul emiterii unui me saj precede evenimentul recepției sale
Cu aceste ipoteze, se poate defini ordonarea cauzală a evenimentelor, folosind o relație
de tip happened -before (notată cu „ ”):

HB1) dacă există procesul p, în care evenimentul x a apărut înaintea lui y, atunci x
 y

HB2) pentru orice mesaj m transmiterea apare înaintea recepției, adică
send( m)  receive( m)
HB3) dacă x  y și y  z, atunci x  z

De exemplu, pentru cazul din figura 8.4, se pot scrie relațiile de ordonare a  b, c  d, b
 c, d  f, a  f, dar a și e sunt concurente ( a  e).

Fig.8.4. [1]

Relațiile HB pot fi implementate cu ajutorul ceasului logic (al lui Lamport), care
reprezintă un contor soft monoton crescător, fără nici o legătură cu ceasul fizic. Fiecare
proces p are propriul ce as logic și marchează un eveniment din cadrul său cu ștampila de
timp ( timestamp ) Cp(a), după următoarele reguli:

LC1) Cp este incrementat înaintea oricărui eveniment din p (Cp := Cp + 1)
LC2) a. dacă p transmite mesajul m, acesta transportă ștampila de t imp t = Cp
b. dacă q recepționează ( m, t), atunci se fixează Cq := max ( Cq, t) și se aplică
LC1 pentru marcarea evenimentului recepției

În exemplul din figura 8.5 evenimentele din fiecare proces au fost marcate cu ștampilele
de timp logice confor m regulilor de mai sus, astfel C(a)=1, C(b)=2 ș.a.m.d. Se poate
observa că a  b implică C(a) < C(b), dar C(b) > C(e) nu implică e  b, deci
evenimentele b și e nu pot fi ordonate. Rezultă că ceasul logic asigură doar o ordonare
parțială a evenimentelor. P entru a putea face o ordonare totală , s-a introdus ștampila de
timp globală dată de perechea ( Ta, pa), unde Ta reprezintă ștampila de timp locală a
evenimentului a în cadrul procesului pa (practic fiecare proces primește câte un număr de
ordine ca identifi cator). Ca urmare , relați a de ordine totală
(Ta, pa) < (Tb, pb)
este adevărată dacă și numai dacă Ta < Tb, sau Ta = Tb și pa < pb. (Ordonarea totală a
evenimentelor nu înseamnă neapărat că ele s -au produs succesiv, ci doar că ele sunt
considerate a fi puse în ordine.)

Fig.8.5. [1]

8.4. Coordonarea distribuită
Coordonarea distribuită este necesară în două cazuri: la excluderea reciprocă a mai
multor procese care doresc acces simultan la o resursă partajată, precum și la alegerea
unui proces care joacă un rol particular în sistem.
a) Excluderea reciprocă (mutual exclusion ) se bazează pe următoarele cerințe privind
intrarea în secțiunea critică (SC):

ME1 (siguranța): cel mult un
proces se poate afla la un
moment dat în SC
ME2 (supraviețuirea) : un proces care solicită intrarea îm SC va putea eventual primi accesul
ME3 (ordonarea): accesul în SC se acordă în ordinea „happened -before”

Câțiva algoritmi uzuali de excludere reciprocă folosiți în sisteme distribuite sunt
prezentați succint mai jos:

 Algoritmul cu server central. Cererile de intrare în SC se adresează unui
server, care va acorda dreptul de acces (tokenul) procesului următor din coada
de așteptare (fig.8.6). Dacă serverul cade. atunci trebuie să aibă loc un proces
de alegere a unui nou server (dintre clienți).
 Algoritmul lui Ricart și Agrawala. Un proces pi care solicită acces în SC
difuzează o cerere care poartă ștampila de timp globală <T, pi>, unde T
reprezintă valoarea ceasului său logic. El va putea intra în SC numai dacă a
adunat toate răspunsurile de la celelalte procese. Un proces furnizează răspuns
la o cerere numai dacă el nu se află și nu a solicitat intrarea în SC, sau dacă
așteaptă să intre în SC, dar ștampila sa de timp este mai mare decât a
solicitantului răspunsului. Un e xemplu este arătat în figura 8.7 , unde p1 și p2

doresc simultan acces în SC. Va câștiga p2, care are ștampila de timp mai mică
(34) decât p1 (41). Căderea oricărui proces duce la blocarea algoritmului.
 Algoritmul în inel. Procesele, aranjate într -un inel l ogic pasează tokenul de la
unul la altul, acesta fiind reținut de procesul care a solicitat acces în SC
(fig.8.8). Acest algoritm nu satisface cerința ME3. Dacă un proces cade, e
necesară reconfigurarea sistemului.

Fig.8.6. (adaptare după [1])

Fig.8.7. (adaptare după [1])

Fig.8.8. [1]

b) Alegerea (election ) presupune selectarea unui proces unic dintre toate procesele vii
(care nu sunt căzute) dintr -un grup. Algoritmi uzuali de alegere sunt următorii:

 Algoritmul „bully”. Principiul este de a alege dintre supraviețuitori procesul
cu cel mai mare identificator. Pentru a începe algoritmul, un proces inițiator
transmite mesajul „election” către toate procesele cu identificatori mai mari și
apoi așteaptă un răspuns („answer”). Dacă nu sosește nici un răspuns, atunci el
se consideră a fi cel ales și transmite mesajul „coordinator” către toate
procesele cu identificatori mai mici. Un exemplu este dat în figura 8.9, unde
se alege ca și coordonator procesul p2, după căderea succesivă a lui p4 și p3.
 Algoritmul în inel. Se urmărește selectarea procesului cu cel mai mare
identificator prin transmiterea mesajelor în inel (fig.8.10). Procesul care
începe algoritmul devine „participant” și transmite mesajul „election” cu
identificatorul său. Un proces c are recepționează mesajul, compară
idenficatorul din mesaj cu al său și dacă e mai mare, transmite mesajul mai
departe. În caz contrar va transmite mai departe mesajul înlocuind
identificatorul din acesta cu cel al său. Dacă un proces primește înapoi
propr iul identificator, atunci devine „coordinator” și trimite mesajul „elected”
prin care își anunță identitatea de câștigător.

Fig.8.9. [1]

Fig.8.10. (adaptare după [1])

9. REPLICAREA

9.1. Introducere
Replicarea în sistemul distribuit înseamnă gestionarea de copii ale datelor și ale altor
resurse. Prin replicare se urmărește atingerea mai multor scopuri:
 îmbunătățirea performanțelor, prin existența de memorii cache la cl ienți cu
copii ale datelor pentru accesare rapidă, respectiv prin distribuirea de copii la
mai multe servere
 creșterea disponibilității, prin posibilitatea solicitării unui serviciu de la un
server alternativ, dacă primul server a căzut (disponibilitatea e ste dată de
A=1pn, unde p reprezintă probabilitatea defectării unui server din totalul de
n)
 toleranța la defecte, asigurată de prelucrarea în paralel a cererilor pe mai multe
servere
Cerințele care se ridică față de implementarea replicării sunt următoar ele:
 transparența, ceea ce înseamnă că clienții nu trebuie să fi conștienți de
existența mai multor copii fizice în sistem
 consistența, ceea ce presupune ca copiile replicate să fie identice
Gestionarea replicilor se poate face în mai multe feluri:
 Modelul asincron. Operațiile clientului se satisfac de către serverul local, care
comunică câteodată (eventual periodic) actualizările celorlalte servere. Astfel
controlul se redă clientului imediat după prelucrarea locală. Datorită modului de
actualizare asincro nă, copiile de pe diferite servere nu sunt tot timpul consistente.
De exemplu, un tabel de corespondență replicat pe mai multe servere poate diferi
ca ordine și conținut la doi utilizatori diferiți .
 Modelul sincron. Se efectuează actualizarea imediată a ce rerilor clienților pe toate
serverele, ceea ce duce la ordonarea totală a acestora. Numai după procesarea
cererilor pe toate serverele se dă înapoi controlul clientului. Fiind efectuată
actualizarea imediată la toate serverele, se asigură consistența stric tă, dar sistemul
este mai lent decât la tehnica precedentă.
 Schema bazată pe quorum. La o operație a clientului se contactează pentru
actualizare o parte din servere, dar nu toate.
 Schema bazată pe ordonare cauzală. Se permite prelucrarea unor cereri în al tă
ordine la servere diferite, dar fără a atenta la cauzalitate. De exemplu, un răspuns
la o scrisoare nu poate apărea nicăieri în tabelul de corespondență înainte de
srisoarea însăși ( Re:X trebuie să apară după X).

Mecanismul general de menținere a consis tenței îl constituie difuzarea parțială a
mesajului de actualizare la acel grup de procese, care gestionează replicile respective.
Desigur replicarea întroduce anumite penalități de performanță (datorită comunicațiilor
multiple pentru actualizări) față de un sistem fără mai multe copii, dar nu și la operațiile
de citire.

9.2. Modelul arhitectural de bază
Modelul general de gestionare a datelor replicate este arătat în figura 9.1. Cererile
clienților (C) sunt adresate componentei front -end (FE), care poate fi un proces sau un
pachet utilizator. Acesta comunică prin transfer de mesaje cu managerii de replici
(replica managers  RM), care reprezintă procese ce conțin replicile și efectuează direct
operații asupra lor. Cererile cli enților pot fi numai de citire (read) sau de actualizare
(update ).

Fig.9.1. (adaptare după [1])

Câteva arhitecturi distribuite care fac posibilă replicarea sunt următoarele :
 Arhitectura gossip (fig.9.2). Fiecare FE comunică cu un singur RM, iar managerii
schimbă între ei mesaje „goss ip” (=bârfă) pentru a transmite actualizările.
 Modelul copiei primare ( fig.9.3). La fiecare actualizare FE comunică cu același
server primar.
 Editorul partajat (fig.9.4). Asigură colaborarea utilizatorilor dintr -un grup
(groupware ). Fiecare proces are atât rol de client, cât și de RM, pe lângă care
există un modul FE.

Fig.9.2. [1]

Dezideratele urmărite (disponibilitatea ridicată și timpi de răspuns mici) impun soluții
extreme contradictorii. În vederea unei disponibilități ridicate, FE nu se poate baza pe un
singur manager, deoarece acesta se poate defecta. În schimb, obținerea unui timp de
răspuns mic presupune ca FE să contacteze cât mai puțini manageri de replici.

Fig.9.3. (adaptare după [1])

Fig.9.4. [1]

9.3. Consi stența și ordonarea cererilor
Deoarece asigurarea unei ordonări totale a cererilor la toate replicile este scumpă, este de
dorit restrângerea constrângerilor de ordonare. Ca urmare, în practică se întâlnesc
următoarele tipuri de ordonări :
 Ordonarea totală. Se asigură dacă oricare ar fi două cereri r1 și r2, la toți RM ori
r1 e procesat înaintea lui r2, ori r2 înaintea lui r1. Asemenea exemple de cereri
total ordonate sunt t1 și t2 în figura 9.5. (Este de menționat că ordonarea totală nu
implică și cauzalitatea.)
 Ordonarea cauzală. Dacă r1 a avut loc înaintea lui r2, atunci r1 trebuie prelucrat
înaintea lui r2 la toți RM. Exemple sunt cererile c1 și c2 din figura 9.5.
 Ordonarea sincroni zată. Dacă r1 este ordonat sincronizat, atunci el trebuie
procesat ori înaintea lui r2 la toți RM, ori după r2 la toți RM, indiferent de
ordonarea declarată a lui r2. Un exemplu este ordonarea sincronizată a cererii s din
figura 9.6 în raport cu c1 și t1.
În vederea ordonării cererilor sosite la un RM, acestea sunt reținute într -o coadă (hold-
back ) fără a fi prelucrate, până la satisfacerea cerințelor de ordonare ( fig.9.7). Se spune că
un mesaj de cerere este stabil la un RM, dacă toate cererile precedente lui, conform
criteriului de ordonare, au fost deja procesate. Cererile stabile se transferă în coada de
prelucrare (livrare), ca urmare nici un mesaj nu va fi prelucrat fără respectarea ordinii.

Fig.9.5. [1]

Fig.9.6. [1]

Fig.9.7. (adaptare după [1])
Pentru implementarea cerințelor de ordonare a cererilor există mai multe tehnici.
a) Implementarea ordonării totale se realizează prin atribuirea de identificatori total
ordonați cererilor transmi se de FE -uri către RM -uri. Exis tă două metode:

 Toate cererile se trimit unui proces secvențor , care atribuie acestora
identificatori în ordine crescătoare și le transmite mai departe către RM -uri.
Această metodă se utilizează de exemplu la protocolul ISIS ABCAST
(causally and totally o rdered multicast ). (ISIS reprezintă o implementare a
serviciilor bazate pe grupuri de procese, care prezintă o interfață de
programare, sub forma unei librării, în vârful sistemului de operare UNIX.)
 Identificatorii se atribuie pe bază de acord distribuit . Algoritmul se poate
urmări pe figura 9.8 :

1. FE transmite cererea cu un identificator temporar către toate RM -urile.
2. Fiecare RM răspunde cu un identificator propus, care este egal cu
max {Fmax, Pmax}+1+ i/N
unde Fmax este cel mai mare identificator agreat pân ă în acel moment,
Pmax este identificatorul cel mai mare propus de acest RM, i reprezintă
numărul de ordine al RM -ului respectiv, iar N este numărul total de
RM-uri. RM -ul respectiv va pune în coada sa de reținere cererea în
cauză, pe baza acestui identifi cator propus.
3. FE colectează propunerile și alege identificatorul maxim agreat, pe
care îl transmite RM -urilor. Acestea își vor reorganiza cozile de
reținere, dacă e necesar.

Fig.9.8. (adaptare după [1])

b) Implementarea ordonării cauzale se face cu ștamp ile de timp vectoriale la fiecare
RM. O astfel de ștampilă de timp VTi reprezintă o arie de numere, câte unul pentru
fiecare RM, care arată câte actualizări au fost făcute din solicitarea fiecărui RM la nodul
care păstrează ștampila (fig.9.9). Fiecare RM p ăstrează un vector care reflectă propria
versiune a datelor (de exemplu a unui tabel de corspondență), iar fiecare FE păstrează
vectorul care reprezintă ultima versiune citită. De exemplu, pentru situația din figură,
dacă FE are vectorul (2, 3, 4) și citeș te o dată de la RM1, atunci în urma unificării
vectorilor, va avea (3, 4, 4). Pentru implementarea ordonării cauzale, trebuie respectate
următoarele reguli:
 FE are voie să citească doar de la o versiune cel puțin la fel de avansată ca
cea a ultimei citiri
 actualizarea unei replici se poate face doar după ce ace asta conține toate
actualizările anterioare
Algoritmul de actualizare a vectorilor, utilizat și la protocolul ISIS CBCAST ( causally
ordered multicast ), are următorii pași:

1. Toate procesele pi (adică fi ecare RM) inițializează vectorii VTi = 0.
2. Când pi face o actualizare a datelor sale, atunci efectuează
VTi [i] := VTi [i] + 1
și va pune în mesajele sale vectorul vt = VTi
3. Când pj prelucrează o cerere sosită de la pi cu vectorul vt, atunci:
3.1. pj actuali zează propriul vector conform cu
VTj := unificare (VTj, vt)
unde unificare (u, v)[k] = max {u[k], v[k]}
3.2. mesajul se transfer ă în coada de livrare dacă el este următorul
așteptat de la pi, adică
vt[i] = VTj [i] + 1
și toate mesajele cauzale anterioare care au fost livrate la pi înainte ca acesta să fi transmis mesajul
curent, au fost livrate și la pj, adică
VTj [k]  vt[k] ( k ≠ i)

Relația de ordine parțială „ ” se definește astfel încât u  v  u[k]  v[k] pentru orice
k=1, 2, …, n. Se poate arăta , că pentru două evenimente e (cu ștampila u) și f (cu ștampila
v) este adevărată relația u ≤ v dacă și numai dacă e  f (e s-a întâmplat înaintea lui f).

Fig.9.9. [1]

10. TRANZACȚII ȘI DATE PARTAJATE

10.1. Introducere
În sistemul distribuit coexistă procese client care inițiază activități , și procese server care
așteaptă cereri de la clienți și efectuează operația cerută. Pentru o funcționare corectă ,
față de programe le server se ridică câteva probleme de fiabiliate și consistență:
 Clienții trebuie să aibă acces la datele partajate gestionat e de server fără a interferi
unul cu altul.
 Datele gestionate de server trebuie să fie recuperabile după o eventuală defectare,
pentru a fi la dispoziția clienților pe timp îndelungat.
 Uneori clienții trebuie să poată efectua secvențe indivizibile de operații server
(tranzacții ).
 Serviciile bazate pe date partiționate între mai multe servere trebuie să poată
gestiona tranzacții distr ibuite.
Un program server gestionează în general resurse partajate între clienți. Aceste resurse
pot fi legat e de aplicație (de exemplu mesaj e e-mail, înregistrări bancare) sau generice
(cum ar fi fișiere, impr imante). Serverul încapsulează resursa, adică accesul este posibil
clienților prin invocarea unei operații a serverului la nivelul interfeței de apel. De
exemplu, un serviciu de adresă, care asociază adresa la numele unei persoane, poate
furniza următoarele operații:
LookUp (name)  address
returneaz ă adresa corespunzătoare numelui
AddAddress (name, address)
adaugă o nouă înregistrare conținând un nume și o adresă
ModifyAddress (name, address)
modifică adresa asociată unui nume
DeleteAddress (name)
șterge înregistrarea corespunzătoare numelui
Opera țiile serverului efectuate la cererea diferiților clienți pot câteodată interferi, ceea ce
ar putea duce la valori incorecte al e datelor. De exemplu, în cazul serviciului de adresă de
mai înainte, ar putea fi solicitate simultan două operații ModifyAddress asupra ac eluiași
nume. Într-o abordare cu fire multiple, fiecare operație va fi executată de câte un fir al
serverului. Pentru ca citirile/scrierile asupra datelor să nu ducă la inconsistență, este
necesar ca operațiile solicitate să fie atomice , adică un fir să nu poată accesa aceleași date
până când primul fir nu și -a terminat acțiunea. Acest lucru se poate realiza printr -un
mecanism de excludere mutuală între firele de execuție.
Se poate întâmpla ca operația solicitată de un client să nu poată fi servit ă până când o
operație cerută de un alt client asupra aceleiași resurse nu este terminată. În această

situație este de preferat ca operația clientului să nu fie refuzată, ci clientul să fie ținut în
așteptare. Pentru aceasta serverul trebuie să fie capabil de suspendarea cererilor care nu
pot fi executate imediat, continuarea preluării de cereri de la alți clienți și reluarea
cererilor suspendate când ele pot fi executate. Pentru a putea deservi mai mulți clienți
simultan, serverul utilizează câte un nou fi r pentru fiecare nouă cerere. Firul care nu își
poate continua execuția se va autosuspenda printr -o primitivă de tip Wait , iar un alt fir va
putea relua execuția firului suspendat printr -o primitivă de tip Signal . Astfel devine
posibilă îmbunătățirea coope rației clienților prin sincronizarea operațiilor serverului.

10.2. Conversația dintre client și server
Conversația (conversation ) poate fi privită ca o interacțiune mai lungă între client și
server, în care acesta din urmă transmite câte unul datele dintr -un șir de rezultate. Astfel,
în loc ca clientul să aștepte după o cantitate mare de date, devine posibilă activitatea
concomitentă a serverului și clientului.
Într-o conversație serv erul trebuie să țină minte starea la care a ajuns în deservirea
clientulu i. Programarea serverului se simplifică d acă serverul utilizează câte un fir pentru
fiecare conversație , deoarece în acest caz fiecare fir va trebui să țină cont doar de propria
poziție în șirul de date care trebuie accesat.
Întrucât pentru implementarea c onversației serverul trebuie să păstreze informații pentru
fiecare din clienți, el este un server cu stare (stateful server ). Informația constă în fiecare
caz din identificatorul conversației și poziția următoarei înregistrări de accesat. Serverul
cu stare este însă vulnerabil la un client slab proiectat sau care se defectează. De
exemplu, dacă mai mulți clienți nu își închid conversația, se poate ajunge la depășirea
spațiului de memorie alocat pentru păstrarea informațiilor de stare. De aceea, serverele
prevăd o limită de timp, după care nu mai păstrează informațiile pentru un anumit client.
O altă problemă este posibilitatea utilizării de identificatori de conversație ilegali de către
clienți slab proiectați, ceea ce poate conduce la interferența cu secven țele de date ale altor
clienți.
Pentru a implementa conversația, serviciul de adresă din paragraful precedent trebuie
completat cu următoarele operații invocabile de către clienți:
OpenConversation ( )  conversationId
cere pornirea unei conversații cu se rverul – returnează un identificator
pentru conversație
CloseConversation (conversationId )
indică terminarea conversației
NextAddress (conversationId )  (name, address) – REPORTS EndOfSquence
returnează numele și adresa din următoarea înregistrare ; dacă nu mai sunt
înregistrări, returnează o raportare de eroare
Cu ajutorul acestor operații, programul clientului pentru a obține detaliile tuturor
înregistrărilor stocate la server, va arăta în felul următor:
conversationId:=Address $OpenConversation ( ) ;

REPE AT
entry:=Address$NextAddress (conversationId);
(*process results*)
UNTIL ErrorReport = EndOfSequence
Address$CloseConversation (conversationId)
Conversația primește la deschidere un identificator de la server. Serverul va trebui să
păstreze pentru fiecare conversație câte o variabilă de stare, care să conțină identificatorul
conversației și o referință la următoarea înregistrare de prelucrat.

10.3. Tran zacții
Tranzacția (transaction ) reprezintă o succesiune de operații legate între ele pe care un
client le efectuează asupra unui server. Din punctul de vedere al clientului, operațiile din
tranzacție formează un singur pas, transformând datele serverului dintr -o stare consistentă
în alta.
Pentru a exemplifica o tranzacție, fie un server care păstrează datele pentru toate conturile
unei bănci. Operațiile care se pot solicita de la acest server bancar sunt:
Deposit (Name, Amount)
depune suma Amount în contul Name
Withdraw (Name, Account)
retrage suma Amount din contul Name
GetBalance (Name)  Amount
returnează balanța contului Name
BranchTotal ( )  total
returnează suma tuturor balanțelor
O tranzacție prin care clientul transferă 100 $ din contul A în B și 200 $ din C în B va
conține șirul de operații din fig ura 10.1. La rândul său, o operație din cadr ul tranzacției
poate fi descompusă la nivelul serverului în mai multe operații de citire și scriere. De
exemplu, operați a Deposit , poate fi definită astfel:
Deposit (Name, amount):
balance:=Name.Read ();
Name.Write (balance + amount)

Fig.1 0.1. [1]
Pentru a păstra consistența datelor și în cazul unor tranzacții concurente, este nevoie de
tranzacții atomice . O astfel de tranzacție se caracterizează prin:

 Indivizibilitate – efectele intermediare ale operațiilor componente nu trebuie să fie
vizibile.
 Izolare (se rializabilitate) – fiecare tranzacție trebuie să fie executată fără a
interferi cu alte tranzacții.
 „Totul sau nimic” – ori se încheie cu succes și efectele sale apar în datele vizate,
ori (în caz de defectare) nu are nici un efect . Legată de această propr ietate este
cerința de durabilitate, ceea ce înseamnă că în caz de încheiere cu succes efectele
tranzacției sunt salvate în dispozitivul de stocare permanent .
Când serverul confirmă încheierea unei tranzacții, toate modificările de date
corespunzătoare tra nzacției trebuie să fie disponibile în dispozitivul de stocare
permanent. Modificările de pe parcursul tranzacției se fac numai în memoria operativă.
Astfel, în caz de defectare a serverului, datele de dinaintea tranzacției devin
recuperabile .
Proprietatea de izolare a tranzacțiilor ar presupune ca în caz de tranzacții solicitate
simultan, ele să fie executate într -o ordine serială. Acest lucru este însă inacceptabil în
practică pentru servere ale căror date sunt partajate printre foarte mulți utilizatori
interactivi. De accea, pentru a maximiza concurența, se acceptă execuția întrețesută a
operațiilor aparținătoare la mai multe tranzacții, cu condiția ca ele să fie executate serial
echivalent , adică să aibă același efect ca și o execuție strict serială.
Un serviciu tranzacțional (transactional service ) este acela la care clientul specifică
secvența de operații care compun o tranzacție, iar serverul garantează păstrarea
proprietății atomice a întregii secvențe. Din operațiile serviciului tranzacțional va face
parte o operație OpenTransaction cu care clientul va prefața secvența, precum și o
operație CloseTransaction pentru a marca sfârșitul tranzacției (fig.1 0.2). Identificatorul
tranzacției, returnat de OpenTransaction , va fi folosit de client în operațiile c onsecutive
aparținătoare tranzacției, până la cea de închidere.

Fig.1 0.2. (adaptare după [1])

O tranzacție se poate termina în următoarele feluri (fig.1 0.3):
 Încheiată cu succes (comisă) – se confirmă clientului că toate modificările asupra
datelor au fost înregistrate

 Abandonat ă (din cauza unui conflict, defectare etc. ) – nici un efect parțial al
tranzacției nu trebuie să apară asupra datelor. Abandonarea poate fi provocată de
client (cu o operație AbortTransaction ) sau de server.

Fig.1 0.3. [1]

Din punct de vedere al comp ortării serverului în caz de defectare în timpul unei
tranzacții , pot exista urm ătoarele situații:
 Se oprește serverul. După repornire el va abandona toate tranzacțiile necomise și
va utiliza o procedură de restabilire a datelor la valoarea produsă de ulti ma
tranzacție comisă.
 Se oprește clientul. Serverul acordă fiecărei tranzacții un timp limită, după
expirarea căruia abandonează tranzacția.
Din punctul de vedere al clientului, dacă serverul se oprește în timpul tranzacției, el va
primi raportarea unei erori de time -out la următoarea operație. În situația în care serverul
repornește încă înainte de încheierea tranzacției , clientul va fi informat la următoarea
operație că tranzacția nu mai e validă la server. În ambele cazuri, utilizatorul din partea
clientului trebuie să ia o decizie asupra continuării sau nu a taskului din care face parte
tranzacția.

10.4. Controlul concurenței
În cazul unor tranzacții concurente, la serviciului bancar pot să apară două pro bleme care
duc la inconsistență: pierderea unei actualizări, respectiv recăpătarea de date false. În
continuare se prezintă pe câte un exemplu aceste probleme și modul lor de rezolvare.
1. Pierderea actualizării (lost updat e). În fig ura 10.4 tranzacția T transferă 4 $ de pe
contul A pe B, iar tranzacția U transferă 3 $ de pe C pe B. Presupunând că valorile inițiale
ale celor trei conturi sunt 100$, 200$ și 300$, în urma tranzacțiilor balanța contului B ar
trebui să crească cu 7 $. Permițând însă o execuție co ncurentă a tranzacțiilor , cu operații
întrețesute, operațiile tranzacțiilor ar putea să se execute la server în ordinea de pe figură.

Se observă că acest lucru duce la o valoare incorectă de 204 $ pe contul B. Problema a
fost generată de faptul că ambele tr anzacții au citit valoarea veche a lui B înainte de a o
modifica. Rezolvarea este posibilă, dacă se permite doar o astfel de întrețesere a
operațiilor în care efectul global este același ca și cum tranzacțiile ar fi fost efectuate unul
după altul. O asemen ea execuție serial echivalentă este exemplificată în figura 1 0.5.

Fig.1 0.4. [1]

Fig.1 0.5. [1]
2. Recăpătarea inconsistentă (inconsistent retrieval ). În fig.1 0.6 se prezintă două
tranzacții: una (T) care mută o sumă de pe un cont pe altul, cealaltă (U) care ob ține suma
balanțelor tuturor conturilor. Presupunând că în ambele conturi există inițial 200 $,
rezultatul căpătat de U (300$) este fals. Problema se datorează faptului că tranzacția T a
efectuat numai retragerea sumei de pe contul A până în momentul în car e U a calculat
suma. Problema se poate rezolva printr -o întrețesere serial echivalentă a tranzacțiilor, de

exemplu conform figurii 1 0.7. Astfel se obține același rezultat ca și cum tranzacția de
recăpătare ar fi fost executată în totalitate înainte sau dup ă tranzacția de actualizare.

Fig.1 0.6. [1]

Rezolvarea ambelor probleme enunțate a fost posibilă prin impunerea unei anumite
constrângeri în ordinea de execuție a operațiilor celor două tranzacții, și anume
respectarea principiului de echivalență serială (serial equivalence ). O întrețesere serial
echivalentă presupune ca toate accesele unei tranzacții la o anumită dată partajată să fie
serializate în raport cu accesele celorlalte tranzacții la acea dată. Toate perechile de
operații generatoare de conflict ap arținând la două tranzacții diferite trebuie să fie
executate în aceeași ordine. Astfel se obține ca efectul celor două tranzacții concurente să
fie același ca și cum ar fi fost executate în ordine (ordinea fiind însă indiferentă).

Fig.1 0.7. [1]

Principiul echivalenței seriale a tranzacțiilor stă la baza protocoalelor de gestionare a
accesului concurent la datele partajate:
 Blocarea ( blocking ) – data partajată este blocată de prima tranzacție care face
acces la ea, astfel încât nu se permite accesul nici une i alte tranzacții până la
terminarea (comiterea sau abandonul) primeia.
 Controlul optimist (optimistic concurency control ) – tranzacțiile sunt derulate în
mod concurent până când sunt gata să comită, atunci se face o verificare a
eventualelor conflicte. În caz de conflict, o tranzacție este abandonată sau se
repornește.
 Utilizarea ștampilelor de timp ( timestamping ) – fiecărei tranzacții i se asignează o
ștampilă de timp la pornire și apoi la fiecare acces data accesată primește ștampila
de timp a tranzacție i care face operația. Dacă se constată că efectuarea unei
operații este deja întârziată în raport cu ordinea în timp a tranzacțiilor, atunci
tranzacția din care face parte operația va fi abandonată și repornită.

10.5. Restabilirea datelor
Un serviciu tran zacțional trebuie să înregistreze efectele tuturor tranzacțiilor comise, dar
nu are voie să modifice datele pentru tranzacțiile abandonate. Legat de tranzacțiile
abandonate se ridică două probleme care pot duce la inconsistența datelor: citirile
„murdare” și scrierile premature.
1. Citiri „murdare” (dirty reads ). Problema este cauzată de interacțiunea dintre o
operație de citire a unei tranzacții și o operație de scriere anterioară asupra aceleiași date
a unei alte tranzacții , care urmează să fie abandonată . De exemplu, în cazul tranzacțiilor
serial echivalente din figura 1 0.8, U citește contul A după ce T îl modifică. Presupunând
că tranzacția T abandonează după ce U a comis, contul A va fi restabilit la valoarea
inițială (100 $). Rezultă că U a făcut o citi re „murdară”, asupra unei valori inexistente,
situație care nu mai poate fi restabilită. Strategia de urmat este de a întârzia comiterea de
către tranzacția la care există posibilitatea unei citiri „murdare” până după comiterea
tuturor celorlalte tranzacți i ale căror stări necomise a u fost observate. În exemplul
considerat, U va întârzia comiterea până după ce T comite, iar dacă T abandonează, și U
trebuie să abandoneze.
Deoarece în exemplul precedent, pentru ca restabilirea să se facă corect, tranzacția U
trebuie de asemenea să abandobeze după ce T abandonează. Este însă posibil ca alte
tranzacții să depindă de efectele produse de U, ca urmare și ele trebuie să abandoneze. O
astfel de situație poat e conduce la abandonuri în cascadă (cascading aborts ), dacă și
alte tranzacții sunt nevoite să abandoneze. Pentru prevenirea abndonurilor în cascadă
trebuie introdusă restricția ca într-o tranzacție să fie permisă o citire de date numai după
ce o altă tranzacție care făcuse în prealabil o scriere asupra datei respe ctive a fost comisă
sau abandonată. Aceasta este evident o condiție mai strictă decât cea de restabilire în caz
de citiri „murdare”.

Fig.1 0.8. [1]

2. Scrieri premature (premature writes ). Problema apare ca urmare a interacțiunii dintre
operațiile de scrier e ale diferitelor tranzacții asupra aceleiași date. Dacă într -o asemenea
situație una din tranzacții abandonează, este posibil ca restabilirea datelor să conducă la
valori incorecte. De exemplu, tranzacțiile serial echivalente din figura 1 0.9 efectuează
câte o depunere în contul A , cu valoarea inițială de 100 $. Când tranzacția T abandonează,
valoarea contului ar trebui să fie 105 $. Principiul o perației de restabilire este însă de a
reface valoarile de dinainte de operațiile de scriere ( before images ). Imagi nea de dinainte
a lui T fiind 100 $, în urma abandonului lui T se va restabili această valoare a contului, și
nu cea corectă. Pentru a asigura rezultatul corect, se impune restricția ca o operație de
scriere să fie întârziată până când alte tranzacții care au modificat anterior data respectivă
să fie comise sau abandonate.

Fig.1 0.9. [1]
Se poate constata că pentru a evita ambele probleme enunțate, atât operațiile de citire, cât
și cele de scriere trebuie întârziate pînă la comitere a sau abandonarea unei alte tranzacții
care în prealabil a modificat data respectivă. Această restricție reprezintă cerința de
execuție strictă (strict execution ) a tranzacțiilor.
Pentru ca toate modificările pe care le face o tranzacție asupra datelor să poată fi anulate
în cazul în care tranzacția abandonează, toate operațiile de scriere se fac asupra
versiunilor tentative (tentative versions ) ale datelor, aflate în memoria volatilă.
Versiunile tentative al datelor sunt transferate (în cadrul unei operații atomice) în

dispozitivul d e stocare permanent numai când tranzacția face comiterea. Cu ocazia
abandonării unei tranzacții, versiunile sale tentative sunt șterse din memorie.

10.6. Tranzacții încuibate
O tranzacție poate fi structurată sub forma unei mulțimi de tranzacții încuibate (nested
transactions ) organizate ierarhic , eventual pe mai multe niveluri. Tranzacțiile încuibate
prezintă următoarele avantaje:
1. Tranzacțiile încuibate situate pe același nivel pot rula simultan (chiar pe servere
diferite), crescând astfel gradul de concu rență în sistem.
2. Tranzacțiile încuibate pot să comită sau să abandoneze independent unul de altul,
făcând astfel sistemul mai robust. Abandonarea unei tranzacții încuibate nu
implică în mod necesar și abandonarea părintelui, în schimb comiterea unei
tranza cții încuibate este condiționată de comiterea părintelui.
Pentru exemplificare , fie o tranzacție Transfer al serviciului bancar, care mută o sumă de
bani de pe un cont pe altul. Aceasta poate fi structurată ca și o pereche de tranzacții
încuibate, Withdraw și Deposit (fig.1 0.10). Când ambele tranzacții încuibate (T 1 și T 2)
comit, atunci și tranzacția Transfer poate comite. Însă în situați a în care T 1 abandonează
(de exemplu din cauza neacoperirii contului) și T 2 comite, tranzacția părinte T poate lua
decizi a de abandonare. Deoarece abandonarea tranzacției părinte condiționează
abandonarea tranzacțiilor descendente, urmează că și T 2 trebuie să abandoneze și să
anuleze efectele sale.
Uneori tranzacți a părinte poate să decidă comiterea, chiar dacă unele tranzac ții
descendente abandonează. Acesta este cazul într -o tranzacție de difuzare a poștei către
mai mulți destinatari, structurat astfel încât livrarea c ătre fiecare destinatar în parte se
face de câte o tranzacție încuibată. Dacă una sau mai multe dintre aces te tranzacții
abandonează, tranzacția părinte mai poate lua decizia de a comite, ceea ce duce la
rezultatul că toate tranzacțiile încuibate reușite vor comite de asemenea.

Fig.1 0.10. [1]