Simulare de sisteme

Specificarea problemelor.

O problema se poate specifica la nivelul interfetei dintre algoritmul ce o rezolva si mediul extern.

O specificare de problema P este o multime de evenimente de intrare in(P), o multime de evenimente de iesire out(P) (cele doua multimi constituind interfata lui P) si o multime seq(P) de secvente admisibile de evenimente de intrare si evenimente de iesire (care precizeaza interleavingurile permise dintre intrari si iesiri).

Fiecare eveniment de intrare sau de iesire are un nume si poate avea asociate date ca parametri.

Exemplu. Problema excluderii mutuale pentru n procesoare:

evenimente de intrare: T_i, E_i, 0 i n-1, unde

T_i indica faptul ca utilizatorul i doreste sa încerce sa intre în sectiunea critica.

E_i indica faptul ca utilizatorul i doreste sa iasa din sectiunea critica.

evenimentele de iesire: C_i, R_i 0 i n-1, unde

C_i indica faptul ca utilizatorul i poate acum sa intre în sectiunea critica.

R_i indica faptul ca utilizatorul i poate acum sa intre în sectiunea remainder.

o secventa a a acestor evenimente este admisibila daca pentru "i:

a|i cicleaza (T_i,C_i,E_i,R_i)

ori de câte ori C_i apare în a, atunci "j eveniment asociat lui j ce apare în a înaintea lui C_i nu este l_j.

(Conditia 1 arata ca utilizatorul si algoritmul interactionaza propriu; ea impune utilizatorului un mod corect de comportare. Conditia 2 afirma ca nu doi utilizatori simultan în sectiunea critica).

Sisteme de comunicatie

În problemele de simulare vom fi interesati în implementarea unor anumite tipuri de sisteme de comunicatie între procesoare pe baza unor primitive.

Aceste sisteme de comunicatie vor fi descrise cu ajutorul unei specificatii de problema.

Exemple

1. Transmiterea asincrona de measej point-to-point

interfata:

send_i (M): eveniment de intrare asociat procesorului p_i care trimite o multime M (eventual vida) de mesaje. Fiecare mesaj include o indicatie a trimitatorului si a destinatarului; exista cel mult un mesaj pentru fiecare destinatar si perechea transmitator-destinatar trebuie sa fie compatibila cu topologia sistemului.

recv_i(M): eveniment de iesire asociat procesorului p_i în care o multime M de mesaje este primita. Fiecare mesaj trebuie sa-l aiba pe p_i ca destinatar.

multimea secventelor admisibile.

Fie a o secventa de evenimente de intrare si iesire.

Notam cu R multimea tuturor mesajelor ce apar în toate evenimentele recv_i(M) din a si cu S multimea tuturor mesajelor ce apar în toate evenimentele send_i(M) din a. Exista o functie K:R S care asociaza fiecarui mesaj din R un mesaj cu 16116m128q acelasi continut din S a.î.:

Integrity: K este bine definita. Orice mesaj primit a fost în prealabil trimis. Nu este permisa coruptia mesajelor.

No duplicates: K este injectiva. Nici un mesaj nu este primit mai mult de o data.

Liveness: K este surjectiva. Orice mesaj trimis va fi primit.

Observatie. Aceste proprietati vor fi modificatecând se vor considera si defectiunile în sistem.

Broadcast asincron

interfata (la un sistem cu broadcast asincron de baza).

bc-send_i(m): eveniment de intrare în care procesorul p_i, trimite un mesaj m tuturor procesoarelor.

bc-recv_i(m,j): eveniment de iesire în care procesorul p_i primeste mesajul m, în prealabil difuzat de p_j.

multimea secventelor admisibile. Fie a o secventa de evenimente de intrare si de iesire.

Exista K o aplicatie care asociaza fiecarui bc-recv_i(m,j) din a un evniment precedent bc-send_j(m) a.î.

Integrity: K este bine definita (orice mesaj primit a fost în prealabil trimis).

No duplicates: Pentru ficare procesor p_i i n-1, restrictia lui K la evenimentele bc-recv_i este injectiva (nici un mesaj nu este primit mai mult de o data de un procesor).

Liveness: Pentru ficare procesor p_i i n-1, restrictia lui K la evenimentele bc-recv_i este surjectiva (orice mesaj trimis este primit de fiecare procesor).

Observatie: Din nou s-a presupus ca nu exista defectiuni.

Procese

Pe fiecare procesor se vor executa bucati de cod care implementeaza sistemul de comunicatie dorit. Deci nu va mai fi corect sa identificam "algoritmul" cu procesorul, pentru ca avem procese multiple ce se executa pe acelasi procesor. Vom folosi notiunea de nod iar sistemul de comunicatie va fi reprezentat ca o cutie neagra în care este implementata o "stiva de protocoale".

Un sistem este o colec

tie de noduri p₀,...,p_n-1, un sistem de comunicatie C si un mediu extern E.

C si E nu sunt explicit modelate ca procese. Ele vor fi date ca specificatii de probleme, care impun conditii asupra comportarii lor.

În fiecare nod exista o stiva de nivele cu acelasi numar de nivele. Fiecare nivel interior comunica cu cele doua nivele adiacente. Nivelul de jos comunica cu sistemul de comunicatie si nivelul de sus cu mediul extern.

Fiecare proces este modelat ca un automat cu o multime (posibil infinita) de stari si o multime de stari initiale. Tranzitiile dintre stari sunt declansate de aparitia evenimentelor procesului. Un proces are patru tipuri de evenimente:

intrari din nivelul de deasupra (sau nivelul exterior daca este nivelul de sus).

iesiri catre nivelul de deasupra.

intrari din nivelul de dedesubt (sau sistemul de comunicatii daca este nivelul de jos) .

iesiri catre nivelul de dedesubt.

Evenimentele de tipul 1 si 2: interfata - top a procesului

Evenimentele de tipul 3 si 4: interfata - bottom a procesului.

Un eveniment este activat într-o stare a procesului daca exista o tranzitie din acea stare, etichetata cu acel eveniment.

Un eveniment de intrare poate fi activat în orice stare a procesului.

Evenimentele de iesire sunt activate de functia de tranzitie a procesului.

Intrarile din mediul extern si din sistemul de comunicatii sunt intrarile nodului.

Procesele de pe un singur nod interactioneaza a.î. numai un numar finit de evenimente (diferit de intrarile nodului) sunt activate de o intrare în nod.

O configuratie a sistemului specifica o stare pentru orice proces de pe orice nod (configuratia nu include starea sistemului de comunicatie). O configuratie initiala contine numai stari initiale ale proceselor.

O executie a sistemului este un sir C₀, F , C₁, F ,C₂,.... alternativ de configuratii si evenimente, începând cu o configuratie si, daca este finit, sfârsind cu o configuratie a.î.:

Configuratia C₀ este o configuratie initiala.

"i 1 evenimentul F_i este activat în configuratia C_i-1 si configuratia C_i este rezultatul lui F_i actionând pe C_i-1. (Orice componenta de stare este aceeasi în C_i ca si în C_i-1 cu exceptia (cel mult doua) proceselor pantru care F_i este eveniment). Starile acestor procese se schimba conform functiei de tranzitie a acestor procese.

"i 1, daca F_i nu este o intrare pentru un nod, atunci i > 1 si este un eveniment pe acelasi nod ca si F_i-1. (Primul eveniment trebuie sa fie o intrare pe un nod).

"i 1 daca F_i estte intrare pe un nod atunci în C_i-1 nu a fost avtivat nici un alt eveniment (diferit de un eveniment de intrare în nod).

Observatie: Din 3. si 4. rezulta ca un nod este declansat de o intrare în nod (din exterior sau din sistemul de comunicatie) si aceasta declansare cauzeaza un lant de evenimente pe acest nod care apare atomic pâna ce alet evenimente nu mai sunt declansate.

Planificarea unei executii este sirul evenimentelor din executie.

Daca a este o executie atunci top(a) (respectivc bot(a)) este restrictia planificarii lui a la evenimentele din inerfata top (respectiv bottom) a nivelului top (respectiv bottom).

O executie este fair daca orice eveniment (diferit de o intrare într-un nod) care este activat va apare (odata si odata; executia nu se opreste prematur, când mai exista pasi de urmat).

O executie a are calitatea de a fi user-compliant pentru o specificatie de problema P, daca mediul extern satisface restrictiile de intrare ale lui P: pentru orice prefix a F a lui a unde F este o intrare din mediul extern, daca a' este prefix al unui element din seq(P), atunci asa este si a F

O executie este corecta pentru sistemul de comunicatie C daca bot(a este un element al lui seq(C). (Sistemul de comunicatie este corect, în conformitate cu specificatiile de problema a lui C).

O executie este (P,C) - admisibila daca estge fair, user - compliant pentru specificatia de problema P si corecta pentru sistemul de comunicatii C.

Atunci când P si C sunt clare din context executia se va numi admisibila.

Simulare

Sistemul de comunicatii C, simuleaza (global) sistemul de comunicatii C₂ daca exista o colectie de procese unul pentru fiecare nod numit Sim (procesul de simulare) care satisface:

Interfata top a lui Sim este interfata lui C₂.

Interfata bottom alui Sim este interfata lui C₁.

Pentru orice executie (C₂, C₁) - admisibila a lui Sim exista un sir s în seq(C₂) a.î. s=top(a

(Executia simularii în topul sistemului de comunicatie C₁ produce aceleasi aparitii în mediul extern pe care le face sistemul de comunicatii C₂).

O definitie mai slaba a simularii, este simularea locala.

O executie a este local user - compliant pentru o specificatie de problema P, daca " a F un prefix al lui a, unde F este o intrare din mediul extern, daca s seq(P) a.î. a'|i este prefix al lui s'|i pentru "i , atunci s seq(P) a.î. a F|i este un prefix al lui s'|i pentru "i (mediul extern satisface restrictiile de intrare ale lui P pentru fiecare nod, dar nu neaparat global).

O executie este (P,C) - local admisibila daca este fair, local user - compliant si corecta pentru sistemul de comunicatii C.

Definitia simularii locale este aceeasi cu a simularii globale cu exceptia conditiei 3 care devine acum:

Pentru orice executie (C₂, C₁) - local admisibila a a lui Sim s seq(C₂) a.î. s|i=top(a)|i "i 0 i n-1.

Conventii de pseudocod

Vom descrie un algoritm asincron de tip MP ca o lista de evenimente de intrare si iesire.

Fiecare eveniment va avea un nume si se vor descrie schimbarile locale care vor fi cauzate de aparitia acestui eveniment, într-un pseudocod secventia uzual.

Pe lânga schimbarile locale de stare, aparitia unui eveniment poate cauza si activarea unor evenimante de iesire. Acestea vor fi indicate astfel: "enable input X". Daca rezultatul unui eveniment de iesire este dezactivarea lui (nu se fac alte schimbari locale) nu va fi trecut în lista de evenimente.

Broadcast and multicast

Pentru a specifica calitatea unui serviciu de broadcast (proprietati ce vor fi descrise mai jos) interfata descrisa mai anterior pentru un serviciu broadcast de baza se modifica astfel:

bc-send_i(m,qos): eveniment de intrare asociat procesorului p_i, care trimite un mesaj m tuturor procesoarelor; qos este un parametru ce descrie calitatea serviciului cerut.

bc-recv_i(m,j,qos): eveniment de iesire în care procesorul p_i primeste mesajul m în prealabil difuzat de p_j; qos este ca mai sus.

Observatie: Atunci când ne referim la un serviciu broadcast de baza vom considera qos=basic. Un mesaj difuzat este primit si de transmitator.

Operatiile bc - send si bc - recv nu sunt blocante: nu se asteapta ca un mesaj sa fie primit de toate procesoarele iar operatia bc - recv actioneaza în modul de lucru bazat pe întreruperi.

Se pot discuta doua categorii de calitati prin adaugarea de noi proprietati pentru secventele admisibile (pe lânga cele ale situatiei qos=basic: integrity, no duplicates, liveness).

Ordonare

Un sistem de broadcast single-source FIFO (qos=ssf) satisface proprietatile lui basic si

Single-Source FIFO " m₁, m₂ si " p_i, p_j daca p_i trimite m₁ înainte de al

trimite pe m₂ , atunci p_j nu-l primeste pe m₂ înaintea lui m₁.

Un sistem de broadcast total ordonat (qos=to) satisface proprietatile lui basic si

Totally Ordered " m₁, m₂ si " p_i, p_j daca m₁ este primit în p_i înaintea lui m₂ , atunci m₂ nu este primit în p_j înaintea lui m₁.

În cele doua conditii, primit este un bc - recv cu qos pe una din cele doua valori iar trimis este un bc - send cu qos corespunzator.

Pentru a defini al treilea model de broadcast cu ordonare este necesar sa extindem relatia de aparitie a unui eveniment înaintea altuia, la mesaje.

Se presupune ca toate comunicarile de la un nivel superior al aplicatiei se executa numai cu bc - send si bc - recv (nu exista mesaje "behind of the scenes").

Definitie: Data o secventa de evenimente bc - send si bc - recv spunem ca mesajul m₁ se întâmpla înaintea mesajului m₂ daca

evenimentul bc - recv pentru m₁ se întâmpla înaintea evenimentului bc - send pentru m₂ sau

m₁ si m₂ sunt trimise de acelasi procesor si m₁ este trimis înaintea lui m₂.

Un sistem de broadcast ordonat cauzal, qos=co, satisface proprietatile lui basic si

Causally Ordered " m₁, m₂ si " p_i daca m₁ se întâmpla înaintea lui m₂ atunci m₂ nu-i primit de p_i înaintea lui m₁.

Exemple

Siguranta în functionare (Reliability)

Un sistem de broadcast este reliable (în prezenta a f defecte) daca pentru orice secventa a de bc - send si bc - recv sunt satisfacute conditiile: Integrity, No duplicates iar Liveness se modifica astfel:

Nonfaulty Liveness: Daca se considera restrictia lui K la evenimentele asociate procesoarelor nedefecte atunci K este surjectiva (toate mesajele difuzate de un procesor nedefect sunt primite odata si odata de procesoarele nedefecte).

Faulty Liveness: Daca un procesor nedefect are un eveniment bc - recv caruia K îi asociaza un eveniment bc - send al unui procesor defect, atunci orice procesor nedefect are un eveniment bc - recv caruia K îi asociaza acelasi eveniment bc - send (orice mesaj trimis de un procesor defect este sau primit de toate procesoarele nedefecte sau de niciunul).

Observatie: Conditiile nu depind de tipul de defectiune a procesoarelor; vom considera totusi numai defectiuni de tip crash.

Anumite combinatii de proprietatilor ale serviciilor de tip broadcast au nume specifice date de importanta lor practica:

broadcast atomic = broadcast reliable cu t.o.

broadcast FIFO atomic = broadcast atomic cu ssf.

broadcast cauzal atomic = broadcast atomic cu c.o.

(ultimele doua sunt echivalente).

Implementarea serviciilor de broadcast

1. Basic

Se implementeaza simplu în topul unui sistem point-to-point MP fara defectiuni.

Când apare un bc - send pentru un mesaj m la un procesor p_i, p_i foloseste sistemul point-to-point MP pentru a trimite o copie a lui m la toate procesoarele.

Când un procesor primeste mesajul de la p_i pe sistemul point-to-point, executa evenimentul bc - recv pentru m si i.

2. ssf

Se implementeaza în topul unui sistem basic. Fiecare procesor asigneaza un numar de ordine pentru fiecare mesaj pe care îl difuzeaza; acesta este incrementat cu 1 ori de câte ori un nou mesaj este difuzat. Primitorul unui mesaj de la p_i cu numar de secventa T asteapta pâna se executa bc - recv_i cu qos=ssf a tuturor mesajelor de la p_i cu numarul de ordine mai mic decât T.

3. t.o.

Un algoritm nesimetric

Se bazeaza din nou pe un sistem de broadcast basic. Pentru a difuza un mesaj m, procesorul p_i îl trimite utilizând basic unui procesor central p_c care asigneaza un numar de ordine si îl difuzeaza folosind basic.

Procesoarele executa receive pentru sitemul cu t.o. în ordinea specificata de numarul de ordine al mesajelor, asteptând daca este necesar pâna primesc toate mesajele cu numar de ordine mai mic.

Clar, ordinea în care se executa receive pentru sistemul cu t.o. este aceeasi la toate procesoarele si anume cea în care au fost trimise de procesorul central.

Rolul procesorului central poate fi preluat si de alte procesoare cu ajutorul unui token de identificare care sa circule printre procesoare.

Un algoritm nesimetric

Ideea este de a asigna timestamp-uri mesajelor.

Algoritmul se bazeaza pe un sistem de broadcast cu calitati ssf.

Agoritm de broadcast t.o. (codul pentru p_i, 0 i n-1)

Initial ts[j]=0, 0 j n-1 si pending este vida.

atunci când apare bc - send_i(m,to):

ts[i]:=ts[i] +1

adauga<m,ts[i],i> la pending

enable bc - send_i(<m,ts[i]>,ssf)

atunci când apare bc - recv_i(<m,T>,j,ssf) ji :

// ignora mesajele catre el însusi

ts[j]:=T

adauga<m,T,j> la pending

if T>ts[i] then

ts[i]:=T

enable bc - send_i(<ts-up,T>,ssf)

//difuzeaza un mesaj de actualizare a timestamp-ului

atunci când bc - recv_i(<ts-up,T>,j,ssf) ji:

ts[j]:=T

enable bc - recv_i(m,j,to) atunci când

<m,T,j> este intrarea în pending cu cel mai mic (T,j) si

T ts[k] "k

result: remove<m,T,j> din pending

Explicatii

Fiecare procesor mentine un contor crescator: timestamp-ul sau, folosit pentru a stampila mesajele pe care vrea sa le difuzeze. În plus, fiecare procesor are un vector în care estimeaza timestamp-urile celorlalte procesoare. Intrarea j din acest vector semnifica faptul ca p_i nu va primi (înca o data) un mesaj de la p_j cu un timestamp mai mic sau egal cu acea valoare.

Aceste componente ale vectorului sunt actualizate cu ajutorul timestampe-urilor asociate mesajelor sau folosind un mesaj special de actualizare trimis de p_j.

Timestamp-ul propriu al fiecarui procesor va fi mai mare sau egal cu estimarea sa a timestamp-urilor celorlalte procesoare. Atunci când procesorul trbuie sa-si mareasca timestamp-ul pentru a asigura conditia precedenta va trimite un mesaj de actualizare a timestamp-urilor tuturor celorlalte procesoare.

Fiecare procesor mentine o multime de mesaje ce asteapta sa fie primite (pentru sistemul cu t.o.). Un mesaj cu timestamp-ul T este primit t.o., atunci când orice intrare în vector este mai mare sau egala decât T. Fie a o executie fair a algoritmului care este corecta pentru sistemul de comunicatii ssf.

Lema 1: Pentru "procesor p_i si "bc - send_i(m,to) din a, p_i asigneaza lui m un timestamp unic si aceste timestamp-uri sunt asignate în ordine crescatoare în raport cu aparitiile lor în a

Lema 2: Timestamp-urile asignate mesajelor din a, împreuna cu id-urile procesoarelor formeaza o ordine totala (aceasta ordine este numita ordinea timestamp).

Teorema: Algoritmul precedent este algoritm de broadcast t.o.

Demonstratie

Trebuie demonstrat ca au loc conditiile:

Integrity, No Duplicates, Liveness si Total Ordering.

Primele doua sunt satisfacute deoarece sistemul ssf pe care se bazeaza algoritmul le satisface.

Liveness: Presupunem ca exista un procesor p_i care are o intrare în pending care astepta la nesfârsit. Fie <m,T,j> intrarea blocata în pending cu cel mai mic (T,j).

Întrucât procesoarele asigneaza timestamp-urile în ordine crescatoare odata si odata <m,T,j> va fi cea mai mica intrare în multimea pending a lui p_i. Pentru a fi blocata trbuie sa existe k a.î. T>ts[k] în p_i la nesfârsit. Deci la un moment dat p_i nu mai creste ts[k]. Fie T' cea mai mare valoare pe care p_i o da lui ts[k]. Clar, k i. Deci de la un loc încolo p_i nu mai primeste mesaje de la p_k (în sistemul ssf). Deci p_k nu va mai trimite mesaje cu timestamp-ul mai mare decât T'. Dar aceasta înseamna ca p_k nu va primi mesajul <m,T,j> de la p_j contrazicând corectitudinea sistemului ssf.

Total Ordering: Presupunem ca p_i executa bc - recv_i(m₁,j₁,to) si apoi

bc - recv_i(m₂,j₂,to). Trebuie sa aratam ca (T₁,j₁)< (T₂,j₂) unde T_i este timestamp-ul lui m_i, (i=1,2).

Cazul I: <m₂,T₂,j₂> este în pending_i atunci când bc - recv _i(m₁,j₁,to) apare. Atunci, clar, (T₁,j₁)< (T₂,j₂) întrucât, altfel, m₂ ar fi fost acceptat înaintea lui m₁.

Cazul II: <m₂,T₂,j₂> nu este în pending_i atunci când bc - recv _i(m₁,j₁,to) apare.

Avem T₁ ts_i[j₂]. Deci p_i a primit un mesaj m de la (pe sistemul ssf) înaintea acestui moment cu timestamp-ul T T₁. Din proprietatea ssf, trimite m₂ dupa ce el trimite m si deci timestamp-ul T₂ al lui m₂ este mai mare decât T. Deci T₂ > T₁.

Cauzalitate

Sa observam ca timestamp-ul asignat unui mesaj m difuzat de p_i este strict mai mare decât timestamp-ul oricarui mesaj primit de p_i dupa primirea mesajului m. Deci:

Teorema: Algoritmul precedent este un algoritm de broadcast c.o.

Observatie: Cauzalitatea se poate obtine si fara t.o., pornind de la un sistem de broadcast basic si folosind timestamp-urile vectoriale. O ratiune pentru aceasta, este aceea ca se poate obtine calitatea c.o. chiar în prezenta defectiunilor în timp ce t.o. nu poate fi asigurata în prezenta defectiunilor.

Reliabilitate

Vom implementa un serviciu de broasdcast reliabil în topul unui sistem cu MP point-to-point în prezenta a f caderi. Interfata sistemului MP point-to-point este fomata din evenimente de intrare send_i(M), recv_j(M) unde M este o multime de mesaje, ficare mesaj incluzând o indicatie a trimitatorului si a primitorului. Secventele admisibile se definesc având urmatoarea proprietate (procesoarele sunt partitionate în defecte si nedefecte primele fiind în numar de cel mult f).

Integrity: Orice mesaj primit de un procesor p_i i-a fost în prealabil trimis de

un procesor.

No duplicates: Nici un mesaj trimis nu este primit mai mult de o singura

data.

Nonfaulty Liveness Orice mesaj trimis de un procesor nedefect la un

procesor nedefect va fi odata si odata primit.

Algoritmul de broadcast reliabil (codul pentru p_i, 0 i n-1)

la aparitia lui bc - send_i(m,reliable):

enable bc - send_i(<m,i>,basic)

la aparitia lui bc - recv_i(<m,k>,j,basic):

if m nu a fost deja primit then

enable bc - send_i(<m,k>,basic)

enable bc - recv_i(m,k,basic)

Teorema: Algoritmul precedent este un algoritm de broadcast reliabil.

Observatii

Calitatea de ssf se obtine exact ca în cazul lipsei caderilor.

Broadcast-ul t.o. reliabil nu se poate obtine atunci când sistemul pe care se bazeaza este asincron (altfel s-ar putea rezolva problema consensului în sisteme asincrone)

Broadcast-ul c.o. se obtine utilizând algoritmul dat pe un sistem de broadcast reliabil.

Toate problemele de implementare precedente pot fi extinse pentru a considera asa numitul multicast în care un mesaj trebuie trimis la un grup de procesoare si nu la toate. Implementarile sunt simple atunci când grupurile sunt statice. Atunci când grupurile se pot modifica, în fiecare executie apar probleme la întretinerea dinamica a lor.

Memorie Partajata Distribuita

Memoria Partajata Distribuita (Distributed Shared Memory), DSM, este o simulare a unui sistem de comunicatie bazat pe memorie partajata cu ajutorul unui sistem de tip transmitere mesaje (MP).

Programul de simulare va fi numit MCS (memory consistency system) care este alcatuit din procese locale în fiecare procesor p_i. Schematic:

Pentru simplitate, vom considera ca obiectele din memoria partajata sunt registri read/write.De asemenea, nu vom considera defectiuni ale procesoarelor.

Fiecare obiect partajat are o specificare secventiala care indica comportarea dorita a obiectului în absenta concurentei.

O specificare secventiala consta dintr-o multime de operatii si o multime de secvente de operatii (multimea secventelor legale de operatii).

Exemplu: Un obiect read/write X suporta operatiile read si write.

Invocarea unui read este read_i (X) si raspunsul return_i (X, v), unde i indica nodul si v valoarea returnata.

Invocarea unui write este write_i (X, v) si raspunsul ack_i (X)

O secventa de operatii este legata daca fiecare read returneaza valoarea celui mai recent write precedent (valoarea initiala daca aceasta nu exista).

Sistem de comunicatie Linearizable Shared Memory ( LSM)

Intrari: invocari ale obiectelor partajate.

Iesiri: raspunsuri din obiectele partajate.

Secventele admisibile: O secventa s de intrari si iesiri este admisibila daca satisface:

Correct interaction "i s I este un sir alternat de invocari si raspunsuri

pereche, începând cu o invocare (fiecare procesor trebuie sa

astepte un raspuns de la un obiect înainte de a invoca un alt

obiect; este interzis accesul tip pipeline)

Liveness " invocare are un raspuns pereche.

Linerizability: Exista o permutare a tuturor operatiilor din s a.î.

pentru orice obiect O, p O este legala (adica apartine specificarii secventiale a lui O)

daca raspunsul la operatia o₁, apare în s înainte de invocarea operatiei o₂, atunci o₁ apare înaintea lui o₂ în p

(Este posibila o reordonare a operatiilor din secventa a a.î. sa respecte

semantica obiectelor -exprimata de specificarile secventiale- si

ordonarea dupa timpul real de aparitie a evenimentelor, în toate nodurile.)

Exemplu: Fie x si y registri, initializati cu 0.

Atunci s = write₀(x, 1) write₁(y, 1) ack₀(x) ack₁(y) read₀(y) read₁(x) return₀(y,1) return₁(x, 1) este liniarizabila întrucât p = w₀w₁r₁r₀ este o permutare care satisface conditiile din definitie.

Însa, s = write₀(x, 1) write₁(y, 1) ack₀(x) ack₁(y) read₀(y) read₁(x) return₀(y,0) return₁ (x, 1) nu-i liniarizabila.

Pentru a respecta semantica lui y, r₀ trebuie sa preceada w₁. Dar aceasta nu respecta ordonarea dupa timpul real pentru ca w₁ precede r₀ în s

Sistemul de comunicatie memorie partajata secvential consistenta

Aceleasi intrari si iesiri iar secventele admisibile s satisfac Correct interaction, Liveness si

Sequentially consistent: Exista o permutare p a operatiilor din s a.î.

pentru orice obiect O, p|O este legala.

daca raspunsul pentru operatia o₁ în nodul p_i (oarecare) apare în s înaintea invocarii operatiei o₂ în nodul p_i, atunci o₁ apare înaintea lui o₂ în p

Observatii

Se cere deci ca sa se pastreze ordinea operatiilor din acelasi nod care nu se suprapun si nu pentru toate operatiile.

În exemplul precedent s este secventa consistenta, permutarea dorita este w₀r₀w₁r₁. Deci conditia de liniarizare este mai tare decât conditia de consistenta secventiala. Exista secvente care nu sunt secvential consistente:

s = write₀(x, 1) write₁(y, 1) ack₀(x) ack₁(y) read₀(y) read₁(x) return₀(y,0) return₁(x,0).

Pentru a respecta semantica lui x si y trebuie ca r₀ sa preceada w₁ si r₁ sa preceada w₀. Pentru a respecta ordinea evenimentelor din p₁ trebuie ca w₁ sa preceada r₁. Din tranzitivitate rezulta ca r₀ precede w₀ care încalca ordinea evenimentelor în p₀.

Algoritmi

Vom presupune ca sistemul MP de baza suporta broadcast t.o. (am aratat cum poate fi implementat). Pentru a evita confuzia vom folosi:

tbc - send_i(m) pentru bc - send_i(m,t.o.) si

tbc - recv_i(m) pentru bc - recv_i(m,t.o.)

Toti algoritmii folosesc replicarea completa: exista o copie locala a oricarui obiect partajat în starea procesului MCS din fiecare nod. (Asa cum se face, de exemplu în ORCA; gestionarea copiilor în alt stil este posibila dar aceasta este o alta problema).

Algoritm pentru simularea unui DSM liniarizabil

Atunci când procesul MCS dintr-un nod primeste o cerere sa citeasca sau sa scrie un obiect partajat:

MCS trimite un mesaj broadcast continând cererea si asteapta sa-si primeasca mesajul sau.

Dupa primirea mesajului, executa raspunsul pentru operatia ce asteapta (returnând valoarea copiei obiectului pe care o detine el pentru un read si executând ack pentru write).

Ori de câte ori un proces MCS primeste un mesaj difuzat pentru un write, actualizeaza copia obiectului, în mod corespunzator.

Teorema: Daca sistemul de broadcast este total ordonat atunci algoritmul precedent simuleaza un DSM liniarizabil.

Demonstratie: Fie a o executie admisibila a algoritmului (fair, user compliant pentru sistemul cu memorie partajata si corecta pentru sistemul broadcast de comunicatie). Trebuie sa demonstram ca top(a) este liniarizabil. Fie s= top(a). Ordonam operatiile din s dupa ordinea totala a broadcast-urilor asociate lor din a si obtinem o permutare p

p respecta semantica obiectelor. Fie x un obiect read/write. p|x sete secventa operatiilor ce acceseaza x. Cum broadcast-urile sunt t.o., orice proces MCS primeste mesajele pentru operatiile asupra lui x în aceeasi ordine, care este ordinea lui p, si gestioneaza x corect.

p respecta ordonarea dupa timpul real de aparitie a operatiilor în a

Presupunem ca o₁ se termina în a înainte ca operatia o₂ sa înceapa.

Atunci broadcast-ul corespunzator lui o₁, a fost primit de initiatorul sau înainte ca broadcast-ul lui o₂ sa fie trimis de initiatorul sau. Evident, boadcastul lui o₂ este ordonat dupa cel al lui o₁. Deci operatia o₁ apare în p înaintea lui o₂.

Observatie: Cum un serviciu broadcast t.o. se poate implementa în topul unui sistem MP point-to-point, rezulta ca un DSM liniarizabil se poate implementa în topul unui sistem MP.

Nu este evident de ce trebuie difuzat un mesaj pentru operatia read, atâta timp cât nu se modifica nici o copie a obiectului ca rezultat al primirii mesajului de citire. Consideram algoritmul în care read-ul returneaza imediat valoarea din copia procesului MCS respectiv si renunta la broadcast.

Fie o executie în care valoarea initiala a lui x este 0. Procesorul p_i invoca o scriere a lui 1 în x si executa un tbc - send pentru write. Mesajul difuzat ajunge la procesorul p_j care-si actualizeaza copia sa locala a lui x pe 1, dupa care, sa spunem, executa un read pe x ce returneaza valoarea noua 1. Consideram un al treilea procesor p_k care nu a primit mesajul de broadcast al lui p_i si are înca valoarea copiei lui x pe 0. Presupunem ca p_k citeste x (dupa ce p_j executa read, dar înainte de a primi broadcastul lui p_i); clar va obtine valoarea 0.

Nici o permutare a acestor trei operatii nu poate fi si conforma cu specificatia lui read/write si sa pastreze ordonarea dupa timpul real de aparitie a operatiilor în a

Totusi acest algoritm îndeplineste conditia de consistenta secventiala.

Algoritm de consistenta secventiala cu read local

(codul pentru procesorul p_i)

Initial, copy[x] pastreaza valoarea initiala a obiectului partajat x pentru orice x.

atunci când apare read_i(x):

enable return_i(x, copy[x])

atunci când apare write_i(x,v):

enable tbc - send_i(x,v)

atunci când apare tbc - recv_i(x,v) din p_j :

copy[x]:=v

if j=i then enable ack_i(x)

Fie a o executie admisibila a algoritmului.

Lema 1 Pentru orice procesor p_i copiile locale ale lui p_i sunt actualizate de operatiile write în aceeasi ordine în fiecare procesor si aceasta ordine pasteraza ordinea operatiilor write asociate fiecarui procesor.

Aceasta ordine va fi numita ordine tbcast.

Lema 2 Pentru orice procesor p_i si orice obiecte partajate x si y daca un read r al obiectului y urmeaza dupa un write w asupra obiectului x în top(a)|i atunci readul r al copiei locale a lui p_i a lui y urmeaza dupa write-ul w al lui p_i asupra copiei locale a lui x.

Din cele doua leme rezulta.

Teorema: Algoritmul precedent implementeaza un DMS secvential consistent cu read local.

Demonstratie: Trebuie demonstrat ca top(a) satisface conditia de consistenta secventiala.

Constructia lui p

Ordonam write-urile din p conform ordinii tbcast. Trebuie sa mai inseram read-urile. Pentru fiecare read din a parcurs de la stânga la dreapta: Read-ul r executat de p_i asupra lui x este plasat imediat dupa ultima aparitie din p asociata (1) aparitiei precedente din a asupra lui p_i (read sau write asupra oricarui obiect) si (2) write-ului care a cauzat ultima actualizare a copiei locale a lui x detinuta de p_i, care precede punctul în care returul lui r a fost activat.

În caz de egalitate se foloseste id-ul procesoarelor pentru stabilirea ordinii (de exemplu daca orice procesor citeste un obiect inainte ca orice procesor sa scrie un obiect atunci p începe cu read-ul lui p₀, urmat de read-ul lui p₁ s.a.m.d).

Trebuie demonstrat ca top(a)|i=p|i. Din constructe, pentru un procesor p_i fixat ordinea relativa a doua read sau a doua write este aceeasi în top(a)|i ca si în p|i. Ceea ce trebuie aratat este ca r si w sunt în aceasta ordine si aceasta rezulta din codul algoritmului. În plus trebuie aratat ca p este legala.

Se poate inversa rolul celor doua operatii:

Facem write-ul local si read-ul încet (datorita tbc - send-urilor)

Algoritmul de consistenta secventiala cu write local

(codul pentru procesorul p_i 0 i n-1)

Initial, copy[x] pastreaza valoarea initiala a obiectului partajat x pentru " x si num=0.

Atunci când apare read_i(x):

if num=0 then enable return_i(x,copy[x])

atunci când apare write_i(x,v):

num:=num+1

enable tbc - send_i(x,v)

enable ack_i(x)

atunci când apare tbc - recv_i(x,v) din p_j:

copy[x]:=v;

if j=i then

num:=num-1

if num=0 and (exista un read care asteapta pe x) then

enable return_i(x,copy[x])

Ideea algoritmului: Când apare un write(x) în p_i se trimite un mesaj de broadcast ca si în algoritmul precedent; totusi el este confirmat imediat. Când apare un read(x) în p_i, daca p_i nu are actualizari care asteapta (pe " obiect nu numai pe x) atunci returneaza valoarea curenta a copiei sale a lui x. Altfel, asteapta pâna primeste mesajul de broadcast pentru toate write-urile pe care el le-a initiat si abia atunci returneaza. Aceasta se realizeaza mentinând un contor al tuturor write - broadcasturilor initiate de el si asteapta pâna acesta este zero.

În esenta, algoritmul implementeaza un pipeline pentru actualizarea write-urilor generate de acelasi procesor.

Teorema: Algoritmul precedent implementeaza un DMS secvential consistent cu write local.

Observatie: Acest algoritm, ca si precedentul nu asigura linearitatea.

Margini inferioare

Vom presupune ca DSM a fost implementat în topul unui sistem de tip MP, point-to-point.

Adaptam definitia unei executii cu timpi (timed execution) pentru sistemul simulat, considerând ca numai evenimentelor de intrare într-un nod li s-au asignat timpi, celelalte evenimente din nod mostenind timpii evenimentelor de intrare în nod, care le-au declansat.

În plus vom considera ca:

orice mesaj are o întârziere într-un interval [d-u,d], unde 0 < u d.

Pentru un MCS fixat si o operatie op vom nota cu t_op timpul, în cazul cel mai nefavorabil, peste toate executiile admisibile, necesitat de operatia op (diferenta dintre timpul real de aparitie a raspunsului si timpul real de aparitie al invocarii).

Teorema 1: Pentru orice MCS secvential consistent care asigura doua obiecte partajate read/write, t_read + t_write d.

Demonstratie: Fie un MCS secvential consistent si doua obiecte partajate x si y, initial 0 amândoua.

Exista o executie admisibila a a lui MCS a.î.

top(a ) = write₀(x, 1) ack₀(x) read₀(y) return₀(y,0)

si write începe la timpul 0 iar read raspunde inaintea timpului d.

Presupunem, în plus, ca orice mesaj trimis in a are intirzierea d. Rezulta ca nici un mesaj n-a fost primit de nici un nod la momentul de timp când read primeste raspunsul.

Similar, exista o executie admisibila a a lui MCS a.î.

top(a ) = write₁(y, 1) ack₁(y) read₁(x) read₁(x) return₁(x,0)

write apare la timpul 0, raspunsul la read apare înaintea timpului d. Deci nici un mesaj n-a fost primit în nici un nod la momentul de timp când read primeste raspunsul.

Vom construi o noua executie a care combina comportarea lui p₀ în a (în care p₀ scrie x si citeste y) cu comportamentul lui p₁ în a (scrie y si citeste x). Cum amândoua operatiile pe fiecare procesor se termina înainte de momentul d, p₀ nu stie despre opearatiile lui p₁ si invers. Deci procesoarele returneaza aceeasi valoare în a pe care ele le fac în a a ). Dupa timpul d în a, se permite ca orice mesaj ce asteapta sa fie livrat, dar este deja prea târziu pentru a mai afecta valorile returnate anterior. Clar, aceste valori sunt inconsistente cu conditia de consistenta secventiala.

Formal, fie a_i|i (i=0,1) si h_i prefixul cel mai lung al lui a_i|i ce se termina înaintea timpului d, si a'=merge(h h a' este prefixul unei executii admisibile a. Dar top(a) este exact secventa s din observatia de dupa definitia conditiei de secvential consistenta, care s-a vazut ca nu-i secvential consistenta.

Observatie: Marginea inferioara obtinuta este valabila în particular si pentru MCS liniarizabil. În acest caz se poate spune chiar mai mult.

Teorema 2: Pentru orice MCS liniarizabil care asigura un obiect partajat read/write scris de doua procesoare si citit de un al treilea

Demonstratie: Fie un MCS liniarizabil si un obiect partajat x initial 0 care este citit de p₀ si scris de p₁ si p₂. Presupunem prin reducere la absurd ca .

Exista o executie admisibila a a lui MCS a.î.

top(a) = write₁(x, 1) ack₁(x) write₂(x, 2) ack₂(x) read₀(x) return₀(x,2).

write₁(x,1) apare la timpul 0, write₂(x,2) apare la timpul u/2 si read₀(x) apare la timpul u.

întârzierile mesajelor în a sunt: d din p₁ la p₂; d-u din p₂ la p₁ si d-u/2 pentru orice alta pereche ordonata de procesoare.

Fie b=shift(a,<0,u/2,-u/2>) adica îl dam pe p₁ înainte cu u/2 si pe p₂ înapoi cu u/2.

b este înca admisibila, întrucât întârzierea mesajelor din p₁ sau în p₂ devine d-u, întârzierea mesajelor din p₂ sau în p₁ devine d si toate celelalte întârzieri ramân neschimbate.

Dar top(b)=write₂(x, 2) ack₂(x) write₁(x, 1) ack₁(x) read₀(x) return₀(x,2). Dar aceasta încalca liniarizabilitatea deoarece read-ul lui p₀ ar trebui sa returneze 1 si nu 2.

Teorema 3: Pentru orice MCS care asigura un obiect partajat x citit de doua procesoare si scris de un al treilea

Demonstratie: Fie un MCS liniarizabil si x un obiect partajat, initial 0 care este scris de p₀ si citit de p₁ si p₂. Presupunem prin reducere la absurd ca

Ideea demonstratiei este aceeasi ca în teorema precedenta, numai ca este ceva mai elaborata.

Fie . Consideram a o executie admisibila a lui MCS în care toate întârzierile mesajelor sunt d-u/2 comtinând urmatoarele evenimente:

La momentul u/4, p₀ face un write₀(x,1)

La un moment intre si , p₀ face ack₀(x). ( si deci write-ul lui p₀ se termina în acest interval).

La momentul , p₁ face read₁(x) 0 i 2k.

La un moment între si , p₁ face return₁(x,V_2i) 0 i 2k.

La momentul , p₂ face read₂(x) 0 i 2k.

La un moment între si , p₂ face return₂(x,V_2i+1) 0 i 2k.

Deci în top(a), read-ul lui p₁ al lui V₀ precede write-ul lui p₀, read-ul lui p₂ al lui V_4k+1 urmeaza dupa write-ul lui p₀, nu avem read-uri suprapuse si ordinea citirilor valorilor din x este V₀, V₁, V₂,...,V_4k+1.

Din liniarizabilitatea v₀=0 si V_4k+1=1. j 0 j 4k a.î. V_j=0 si V_j+1=1. Presupunem ca j este par deci V_j este rezultatul unui read al lui p₁.

Definim b=shift(a,<0,0,-n/4>) adica îl dam înapoi pe p₂ cu n/4. b este admisibila, întrucât întârzierea mesajelor în p₂ devine d-n, întârzierea mesajelor din p₂ devine d si celelalte întârzieri ramân neschimbate.

Rezultatul shift-arii este ca s-a schimbat ordinea operatiilor read în raport cu

v₁, v₀, v₃, v₂,...,v_j+1, v_j,..... Deci în top(b) avem v_j+1=1 citit înaintea lui v_j=0, care violeaza liniarizabilitatea.

Simulari tolerante la defectiuni ale obiectelor read-write

Simularea unui obiect de nivel înalt cu unul de nivel jos este utila pentru proiectarea algoritmilor folosind primele obiecte desi executia se face într-un sistem realist ce dispune doar de ultimele.

Vom prezenta simulari de sisteme cu memorie partajata în topul altor tipuri de obiecte cu memorie partajata sau în topul unui sistem asincron de tip transmisie de mesaje, în prezenta defectiunilor de tip crash.

Considerarea caderilor se poate face în doua moduri echivalente: definim un sistem de memorie partajata care sa permita defectiuni sau modificam definitia simularii pastrând definitia sistemelor de memorie partajata libere de defectiuni.

Sistem cu memorie partajata f-rezilient

Intrarile sunt invocari ale obiectelor partajate si iesirile sunt raspunsuri de la obiectele partajate. Se presupune o partitie a procesoarelor cu doua clase, procesoare defecte si nedefecte, numarul celor defecte este mai mic sau egal cu f. O secventa s de i|o este admisibila daca urmatoarele proprietati au loc:

Correct Interaction: Pentru fiecare procesor p_i, s|i este sir alternat de invocari si raspunsuri pereche, începind cu o invocare.

Nonfaulty Liveness: Orice invocare a unui procesor nedefect are un raspuns pereche.

Extended Liniarizability: Exista o permutare p a tuturor operatiilor complete din s (cele care au raspuns) si a unei submultimi a operatiilor incomplete a.î.:

p|o este legala pentru orice obiect o.

Daca în s, raspunsul la operatia o₁ apare înaintea invocarii lui o₂ , atunci o₁ apare înaintea lui o₂ în p

Vom studia daca sistemul de comunicatie C₁ poate simula sistemul de comunicatie C₂ , unde C₂ este un sistem cu memorie partajata cu un anumit tip de obiecte care admite f caderi de procesoare, iar C₁ este un sistem de comunicatie (sau cu memorie partajata sau de tip MP) care admite f caderi de procesoare.

De fapt vom discuta cazul f=n-1, numit wait-free datorita definitiei urmatoare echivalente.

O simulare a unui sistem de tip memorie partajata (fara defectiuni) de catre alt sistem de tip memorie partajata (tot fara defectiuni) se numeste wait-free daca:

Pentru orice executie admisibila a a programului de simulare, daca a' este un prefix în care un procesor p_i are o operatie incompleta (exista în a' o invocare din mediul extern în p_i fara un raspuns pereche) a a b, atunci b|p_i contine raspunsul la aceasta operatie.

(Orice operatie trebuie sa fie capabila sa se termine în orice punct fara asistenta altor procesoare, f=n-1; operatiile pe procesoarele nedefecte se desfasoara normal).

Observatie: Conditia de liniarizabilitate corespunde intuitiei ca operatiile (de nivel înalt) apar ca fiind executate atomic într-un anumit moment în timpul executiei lor. Acest moment se afla undeva între invocarea si raspunsul la operatie si se numeste punct de liniarizabilitate. Un mod de a demonstra ca o secventa este liniarizabila este acela de a asigna explicit fiecarei operatii un punct de liniarizabilitate. Acesta va asigura ordinea temporala a operatiilor ce nu se suprapun. Daca se arata în plus ca fiecare nod returneaza valoarea operatorului write cu punctul de liniarizabilitate cel mai recent ce precede operatorul read, am demonstrat ca executia este liniarizabila.

Vom prezenta în continuare urmatorul lant de simulari wait-free ale registrelor de tip read-write.

Binar - Multivaluat

Un registru este single - reader (s - r) daca exista un singur procesor (cititorul) ce poate citi din el si single - writer daca exista un singur procesor (scriitorul) ce poate scrie în el, (s - w).

Simularea unui registru cu K valori, de tip s - r, s - w cu ajutorul unor registre s - r, s - w cu valori binare.

Pentru simplitate vom considera un singur registru R cu K valori si doua procesoare bine definite scriiorul si cititorul. Pentru simularea lui R, vom considera un tablou de K registri binari B[0..K-1]. Valoarea i va fi reprezentata de un 1 în componenta B[i] si 0 în celelalte. Deci, valorile posibile ale lui R sunt .

O operatie read(R) va fi simulata prin scanarea vectorului B începând cu indicele 0 si returnând prima componenta egala cu 1 (daca exista). O operatie write(R,v) va fi simulata punând 1 în B[v] si si stergând componenta egala cu 1 ce corespunde valorii precedente a lui R.

Acest scenariu simplu functioneaza în cazul operatiilor R si W care nu se suprapun.

Daca operatiile cititorului sunt în ordine read(R,2) read(R,1)iar ale scriitorului write(R,1) write(R,2) atunci, o liniarizare a acestor operatii va trebui sa se pastreze ordinea operatiilor fiecarui procesor. Pentru a fi îndeplinit semantica registrului R va trebui ca write(R ,1) sa apara înainte de read(R,2) pe cînd write(R,1) trebuie sa apara înainte de read(R,1) si dupa read(R,2). Deci, sau ordinea operatiilor read sau ordinea operatiilor write trebuie schimbata. Algoritmul urmator rezolva aceasta problema a inversiunilor "nou - vechi" ale valorilor.

Algoritmul de liniarizare registru multi-valuat cu registre binare

Initial registrii partajati B[0].....B[K-1] sunt 0 cu exceptia lui B[i]=1, unde i este valoarea initiala a lui R

când apare read(R): //cititorul citeste din registrul R

i:=0

while B[i]=0 do i:=i+1

up,v:=i

for i:=up-1 downto 0 do

if B[i]=1 then v:=i

return(R,v)

când apare write(R,v): //scriitorul scrie valoarea v în registrul R

B[v]:=1

for i:=v-1 downto 0 do B[i]:=0

ack(R)

Evident , algoritmul este wait-free; fiecare write executa cel mult K operatii write de nivel jos iar fiecare read executa cel mult 2K-1 operatii read de nivel jos.

Pentru a demonstra ca algoritmul este corect trebuie sa aratam ca orice executie edmisibila este liniarizabila, admite o permutare a operatiilor de nivel înalt a.î. sa se pastreze ordinea operatiilor care nu se suprapun si în care orice read returneaza valoarea ultimului write precedent.

Fixam o executie a admisibila a algoritmului. Cum a este corecta pentru sistemul de comunicatie cu registre binare, operatiile cu registre binare sunt liniarizabile. Deci fiecare operatie de nivel jos admite un punct de liniarizabilitate.

Asociem fiecarei configuratii a executiei a o "valoare actuala" a registrului multivaluat R: valoarea actuala a lui R este

În aceasta definitie valoarea lui B(i) este în raport cu punctele de liniarizabilitate ale operatiilor de nivel jos.

Construim o liniarizare a lui a. Punctele de liniarizabilitate al operatiei write(R,k) este imediat dupa prima configuratie din intervalul ei în care b[k]=1 si B[0]=...=B[k-1]=0. La terminare alui write(R,k) (atunci când apare ack(R)) aceasta este situatia, dar punctul de liniarizabilitate poate fi mai înainte (daca, de exemplu valoarea precedenta a lui R a fost mai mare decât k, el este imediat dupa executia operatiei de nivel jos B[k]:=1).

Punctul de liniarizabilitate a lui read(R) care se termina cu return(R,k) este imediat dupa prima configuratie din intervalul ei, în care k este asignat variabilei locale v, (linia 3 sau 5).

Lema 1: Valoarea actuala a lui R ramâne fixa între doua puncte de liniarizabilitate ale operatiei write consecutive de nivel înalt.

Lema 2: Pentru fiecare operatie read r (de nivel înalt) din 2, r returneaza valoarea scrisa în R de operatia write (de nivel înalt) cu ultimul punct de liniarizabilitate înaintea ultimului punct de liniarizabilitate al lui r.

Din cele doua leme rezulta urmatoarea

Teorema. Algoritmul precedent reprezinta o simulare wait-free a unui registru K-valuat folosind K registri binari s-r, s-w, în care fiecare operatie necesita O(K) operatii de nivel jos.

Single - reader Multi - reader

Mai multe procesoare (n) citesc din acelasi registru. Vom permite existenta unui singur scriitor pentru fiecare registru. Registrului R i se va asocia o colectie de n registre s - w, s - r Val[i] i=1,n , unul pentru fiecare cititor.

Un scenariu simplu de simulare:

write(R,v) va obliga cititorul sa parcurga toate cele n registre Val[i] si sa memoreze v în ele.

read(R) : cititorul i returneaza valoarea din Val[i].

Din pacate aceasta simulare este incorecta, exista executii care nu sunt liniarizabile.

Exemplu

Valoarea initiala a registrului este 0. Scriitorul p_w doreste sa scrie 1 în registru. Consideram urmatoarea secventa de operatii:

p_w starteaza operatia de write(R,1), scriind 1 în Val[1]

p₁ citeste din R si returneaza 1 din Val[1]

p₂ citeste din R si returneaza 0 din Val[2]

p_w primeste ack dupa scrierea lui 1 în Val[1], scrie 1 în Val[2] si confirma (ack) scrierea sa (de nivel superior).

Citirea lui p₁ trebuie ordonata dupa scrierea lui p_w si citirea lui p₂ înaintea scrierii lui p_w. Deci citirea lui p₁ trebuie ordonata dupa citirea lui p₂.Totusi, citirea lui p₁ apare înaintea citirii lui p₂.

Are loc urmatoarea teorema:

Teorema

În orice simulare wait-free a unui registru s - w, m - r cu orice numar de registre s - r, s - w, cel putin un cititor trebuie sa scrie.

Solutia pentru simulare va necesita ca cititorii sa-si scrie unii altora creind o ordine între ei. Înainte de a returna valoarea din read-ul sau, un cititor îi va anunta pe ceilalti aceasta valoare. Un cititor va citi valoarea scrisa de scriitor pentru el, dar si valorile anuntate de ceilalti cititori. Va alege cea mai recenta valoare pe care el a citit-o. Vom presupune ca registrele pot lua un numar nemarginit de valori. În aceasta ipoteza, scriitorul poate asocia un numar întreg drept timestamp (a câta oara a scris) pentru fiecare valoare scrisa. În continuare vom referi o valoare ca fiind perechea ce contine o valoare reala si numarul sau de ordine.

Se vor folosi tablourile de registre s - r :

Val[i]: valoarea scrisa de p_w pentru cititorul p_i 1 i n

Report[i,j]: Val returnata de cea mai recenta operatie read

executata de p_i; scris de p_i si citit de p_j 1 i,j n

Algoritm de simulare a unui registru m - r R cu registri s - r

Initial, Report[i,j]=Val[i]=(v₀,0) 1 i,j n (unde v₀ este valoarea initiala a

lui R)

când apare read_r(R) : //cititorul r citeste din registrul R

(v[0],s[0]):=Val(v) // cea mai recenta valoare raportata lui p_r , de scriitor

for i:=1 to n do

(v[i],s[i]):=Report[i,r] // cea mai recenta valoare raportata lui p_r , de p_i

fie j a. î. s[j]=max(s[0],s[1],...,s[n])

  for i:=1 to n do

Report[r,i]:= (v[j],s[j]) // p_r raporteaza fiecarui cititor p_i

return_r(R,r[j])

când apare write(R,v) : //scriitorul scrie în registrul R

seq:=seq+1

for i:= to n do

Val[i]:=(v,seq)

ack(R)

Algoritmul este wait-free : fiecare operatie simulata executa un numar fix de oparatii de nivel jos (n pentru write si 2n+1 pentru read).

Liniarizabilitatea se demonstreaza considerind o executie admisibila a oarecare si construind explicit permutarea p

Single - writer Multi - writer

Ideea algoritmului de simulare. Fiecare scriitor anunta valoarea pe care intentioneaza sa o scrie, tuturor cititorilor (scriindu-le-o în registrul fiecaruia, registru de tip s - w, m - r). Fiecare cititor citeste toate valorile scrise de scriitori si o alege pe cea mai recenta dintre ele. Depistarea valorii cea mai recenta se face cu ajutorul unui timestamp asociat fiecarei valori. Spre deosebire de algoritmul precedent, timestamp-ul nu este generat de un singur procesor (unicul writer) ci de mai multe procesoare (toti scriitorii posibili).

Scriitorii sunt p₀,...,p_m-1 iar cititorii sunt toate procesoarele p₀,p₁,...,p_n-1. Se vor folosi tablourile de registri s - w, m - r :

TS[i] timestamp-ul vectorial al scriitorului p_i 0 i m-1. Este scris de p_i si citit de toti scriitorii.

Val[i] Ultima valoare scrisa de scriitorul p_i 0 i m-1, împreuna cu timestamp-ul vectorial asociat cu acea valoare. Scris de p_i si citit de toti cititorii.

Algoritm de simulare a unui registru m - w R cu registri s - w

Initial, TS[i]=<0,...,0> si

Val[i] este valoarea initiala a lui R 0 i m-1

când apare read_r(R):  // cititorul p_r citeste din registrul R, 0 r n

for i:=0 to m-1 do (v[i],t[i]):=Val[i]  //v,t sunt locale

fie j a.î. t[j]=max  // maximul lexicografic

return_r(R,v[j])

când apare write_w(R,v):  //scriitorul p_w scrie v în R, 0 w m-1

ts:=NewCTS()  //ts este local

val[w]:=(v,ts)

ack_w(R)

procedure NewCTS_w()  //scriitorul p_w obtine un nou timestamp vectorial

for i:=1 to m do lts[i]:=TS[i].[i]

lts[w]:=lts[w]+1

TS[w]:=lts

return lts

Simularea registrilor partajati în sisteme de tip MP

În cazul existentei defectiunilor, metoda descrisa pentru simularea memoriei partajate în topul unui sistem broadcast t.o., bazata pe asteptarea confirmarii din sistemul MP, nu mai functionaza. Atunci când exista defectiuni, un procesor nu poate fi sigur ca va primi un mesaj trimis catre el. Mai mult, nu poate astepta o confirmare de la destinatar, pentru ca acesta poate pica.Vom folosi toate procesoarele ca extra - memorie pentru a implementa fiecare registru partajat (nu numai scriitorii si cititorii acelui registru). Desigur, valorile sunt acompaniate de numare de ordine. Metoda pe care o vom descrie functioneaza în ipoteza ca numarul procesoarelor defecte f satisface f < n/2 (se poate demonstra ca nu este posibila o simulare a unui registru read/write în topul unui sistem asincron MP daca n 2f).

Consideram un registru particular ce va fi simulat. Când scriitorul doreste sa scrie o valoare în acest nou registru, incrementeaza un numar de ordine si trimite un mesaj <newval> continând noua valoare si numarul de ordine, tuturor procesoarelor.

Fiecare primitor actualizeaza o variabila locala cu aceasta informatie, daca numarul de ordine asociat este mai mare decât valoarea curenta a numarului de ordine din variabila locala; în orice eveniment receptorul trimite un mesaj de <ack>.

Odata ce scriitorul primeste <ack> de la cel putin procesoare el termina de scris. Cum n>2f si deci avem garantia ca va termina de scris.Când cititorul doreste sa citeasca un registru, el trimite un mesaj de tip <request> tuturor procesoarelor. Fiecare procesor trimite înapoi un mesaj de tip <value> continând informatia curenta pe care o detine. Odata ce cititorul primeste <value> de la cel putin procesoare, el returneaza valoarea cu cel mai mare numar de secventa dintre cele primite.

Comunicarea cu procesoare garanteaza un quorum pentru fiecare operatie read sau write. Cum în aceste quorum-uri avem majoritatea procesoarelor, va exista un procesor în intersectia oricarui quorum al unui read cu orice quorum al unui write. Acesta garanteaza faptul ca ultima valoare scrisa va fi obtinuta.

Pentru a evita problemele potentiale legate de asincronie, si scriitorul si cititorul mentin o variabila locala status [0..n-1] pentru a guverna comunicarea; status[j] contine una din valorile:

not-sent: mesajul pentru cea mai recenta operatie n-a fost înca trimis lui p_j (pentru ca p_j n-a confirmat un mesaj anterior)

not-acked: mesajul pentru cea mai recenta operatie a fost trimis lui p_j dar n-a fost confirmat de p_j

acked: mesajul pentru cea mai recenta operatie a fost confirmat de p_j

În plus, fiecare procesor are un numarator num-acks cu care-si numara raspunsurile primite în timpul operatiei curente.

Algoritm pentru simularea unui registru read/write cu MP

(codul pentru unicul scriitor)

Initial status[j]=acked pentru "j, seq=0 si pendinng=false

Când apare write_w(v): // procesorul p_w scrie în registru

pendinng:=true

seq:=seq+1

num-acks:=0

for "j do

if status[j]=ackd then //are raspuns dat pentru operatia precedenta

enable send_w<newval, (v,seq)> to p_j

status[j]:=not-acked

else status:=not-sent

Când apare <ack> de la p_j:

if not pending then status[j]:=acked //nici o operatie în executie

else if status[j]=not-sent then //raspuns la un mesaj precedent

enable send_w(<newval>, (v,seq)> to p_j

status[j]:=not-acked

else //raspuns la operatia curenta

status[j]:=acked

num-acks:= num-acks+1

if then //confirmare de la majoritatea

pending:=false

enable ack_w

Algoritm pentru simularea unui registru read/write cu MP

(Codul pentru unicul cititor p_i)

Initial status[j]=acked pentru "j, seq=0 si pendinng=false

Când apare read_i():

pendinng:=true

num-acks:=0

for "j do

if status[j]=acked then //are raspuns dat pentru operatia precedenta

enable send_i<request> to p_j

status[j]:=not-acked

else status:=not-sent

Când apare receive<value, (v,s)>

if not pending then status[j]:=acked //nici o operatie în executie

else if status[j]=not-sent then //raspuns la un mesaj precedent

enable send_i<request> to p_j

status[j]:=not-acked

else //raspuns la operatia curenta

if s>seq then

status[j]:=acked

num-acks:= num-acks+1

if then

pending:=false

enable return_i(val)

Algoritm pentru simularea unui registru read/write cu MP

(codul pentru orice procesor p_i 0 i n-1, inclusiv p_w si p_i)

Initial last=(v₀,0) unde v₀ este valoarea initiala a registrului simulat

Când apare receive_w<newval,(v,s)> :

last:=(v,s)

enable send_i(ack) to p_w

Când apare receive _i(request):

3.enable send_i(value, last) to p_i