Distribuovaná synchronizace • Využití kritické sekce při vzájemném vyloučení v distribuovaném systému
Paralelní a distribuované systémy
• Logicky distribuovaný systém s vlákny • Semafory, zámky
1. Přednáška 1 Vzájemné vyloučení
• Fyzicky distribuovaný systém? • Procesy běží na různých procesorech • Distribuované algoritmy vzájemného vyloučení: Algoritmy: Centralizované Lamportův Ricart-Agrawala Maekewa Suzuki-Kasami Raymondův
§ §
Lenka Carr Motyčková!
§ § § §
DME: Centralizovaný algoritmus •
Jeden z procesů je vybrán jako koordinátor , např. proces nejvyšším ID
•
Proces, který chce vstoupit do KS pošle koordinátorovi zprávu request
•
Koordinátor rozhodne, který proces vstoupí do KS jako další a pošle tomuto procesu zprávu reply
•
Proces, který přijme zprávu reply vstoupí do KS
•
Po opuštění KS pošle proces zprávu release koordinátorovi a pokračuje ve své činnosti
•
Algoritmus potřebuje pro vstup do KS tři zprávy: •
request
•
reply
•
release
Centralizovaný algoritmus Client do true → send request; reply received → enter CS; send release;
od
server busy: boolean queue req
reply
clients
release
Server do request received and not busy → send reply; busy:= true request received and busy → enqueue sender release received and queue is empty → busy:= false release received and queue not empty → send reply to the head of the queue od
Centralizovaný algoritmus - fronta procesů
Centralizovaný algoritmus • Správnost: • Vzájemné vyloučení: proces musí opustit KS předtím, než do ní vstoupí další • Férovost: procesy vstupují do KS v pořadí, ve kterém požadovaly vstup • Uváznutí: koordinátor vydá další povolení ke vstupu do KS, pokud předchozí proces z KS vystoupí
• Nevýhody: • Vznik bottlenecku • Algoritmus selže, když se proces - koordinátor zastaví
1!
Distribuovaný algoritmus Centralizovaný koordinátor
Distribuovaný koordinátor - množina arbitrů = quorum Si
Distribuovaný algoritmus •
Pi ∈ Si
•
Každá dvojice procesů má alespoň jednoho společného arbitra :
•
Každý proces má stejnou odpovědnost v roli člena quora (D)
•
Každý proces musí vynaložit stejné úsilí při vstupu do KS:
•
Síť musí být úplně propojená
quorum - množina arbitrů: Si ∩ Sj ≠ ∅
počet quor Sk , pro která Pi ∈ Sk je D
|Si | = K
•
Kanály jsou FIFO a
Pi
jsou spolehlivé
Pj
Si
Lamportův algoritmus Předpoklady:
•
•
Velikost quora je N (D = K = N)
•
Síť musí být úplně propojená: rozeslání = broadcast
•
Kanály jsou FIFO
•
Zpráva je doručená v konečném čase
Request (Ti,i) - zpráva obsahuje časová razítka
Sj
Lamportův algoritmus •
Vstup do KS:
•
Pi uloží zprávu Request(Ti,i) do své vlastní fronty a rozešle ji
•
Pj uloží zprávu Request(Ti,i) do své vlastní fronty a odpoví procesu i : Reply(Tj,j)
•
Pi vstoupí do KS právě, když •
A) jeho vlastní požadavek je na začátku jeho vlastní fronty a
•
B) Pi přijal zprávy Reply s časovým razítkem starším než (Ti, i) od všech ostatních procesů => ! Právě
jeden proces je v KS:
! Pi
•
Každý proces si vytváří uspořádanou frontu zpráv Request(s)
musel také dostat všechny požadavky Request s časovými razítky menšími než (Ti, i)
(Pi už dostal všechny požadavky starší než je jeho vlastní)
Lamportův algoritmus •
Lamportův algoritmus
Výstup z KS: reply(Tk)
•
•
Pi odstraní svůj požadavek ze své fronty
•
Pi rozešle Release (Ti, i)
•
Pj odstraní Request (Ti,i) ze své fronty
Komunikační složitost: 3(N - 1)
… req(Ts, Po) req(Tm, Pi)
2!
Ricarto - Agrawalův algoritmus •
Princip:
•
Pj odešle zprávu Reply(Tj,j) právě když •
nežádá o vstup do KS nebo
•
jeho žádost má časové razítko (Tj, j) > (Ti,i)
Ricarto - Agrawalův algoritmus •
Algoritmus:
•
Když chce proces Pi vstoupit do KS, vygeneruje nové časové razítko, (Ti,i) , a pošle zprávu Request (Ti,i) všem ostatním procesům
•
Když proces Pj přijme zprávu Request (Ti,i), buď okamžitě odpoví nebo odpověď odloží
•
Jinak je zpráva Reply odložena na pozdější dobu
•
Když proces Pi přijme zprávy Reply od všech ostatních procesů může vstoupit do KS
•
Pi vstoupí do KS až potom, co přijme zprávy Reply od všech ostatních procesů
•
Po opuštění KS proces pošle zprávy Reply(Ti,i) všem odloženým procesům
•
2(N-1) zpráv
Ricarto - Agrawalův algoritmus • •
Algoritmus pokrač.: Rozhodnutí, zda proces Pj odpoví na zprávu Request (Ti,i) okamžitě nebo odloží odpověď, záleží na třech faktorech : •
jestliže je Pj v KS, potom odpověď procesu Pi odloží
•
jestliže Pj nechce vstoupit do KS, potom pošle procesu Pi odpověď okamžitě
•
jestliže chce proces Pj vstoupit do KS, ale ještě tak neučinil, potom srovná časové razítko svého vlastního požadavku s časovým razítkem (Ti,i) •
jestliže je časové razítko vlastního požadavku větší než (Ti,i), potom pošle okamžitě zprávu Reply(Tj,j) procesu Pi (proces Pi požádal o vstup do KS dříve)
•
jinak je odpověď Reply odložena
Ricarto - Agrawalův algoritmus
Ricarto - Agrawalův algoritmus For each process requesting an access to CS:! begin! my-request := true; #rec :=0;! broadcast ;! while #rec < N - 1 do begin! receive ; #rec ++; end! enter CS;! my-request := false; ! k := 1;! while (k < N) do begin! if Postponed[k] ! then begin send to k; ! Postponed[k] := false; end;! k++; ! end; ! end; !
Ricarto - Agrawalův algoritmus : příklad
For each process upon receipt of receive :! begin! if (my_request and (Ti,i) < (Tj,j) )! //pokud je v KS, tak podmínka vždy platí! then Postponed [j] := true! else send to j;! end!
3!
Ricarto - Agrawalův algoritmus : správnost
Ricarto - Agrawalův algoritmus: nedostatky
•
Absence uváznutí je zaručena, protože vstup do KS je řízen pořadím časových razítek
•
Proces musí znát identitu všech ostatních procesů v systému, což komplikuje dynamické přidávání a odstraňování procesů do/ze systému
•
Absence stárnutí je zaručena, (žádosti posouvají časová razítka)
•
Jestliže jeden z procesů přestane pracovat celý systém se zhroutí
• •
Pořadí časových razítek zaručuje že procesy jsou obslouženy způsobem firstcome, first served
Problém může být vyřešený kontinuálním monitorováním stavu všech procesů v systému
• •
Počet zpráv nutných ke vstupu do KS
Tento algoritmus je vhodný pro malé a stabilní systémy spolupracujících procesů
2(N – 1)
Maekawův algoritmus
Maekawův algoritmus
•
Ricarto Agrawalův algoritmus je symetrický
•
N … počet quor (podmnožin) = počet uzlů
•
Maekavův algoritmus tento požadavek uvolňuje
•
D .. Pi je členem D quor = počet duplikací
•
quorum - množina arbitrů: |S1| = … =|SN| = K
•
K .. počet procesů v každém quoru
•
Každý proces musí vynaložit stejné úsilí při vstupu do KS Každá dvojice procesů má alespoň jednoho společného arbitra:
•
Pi ∈ Si
# quor N * # členů K # duplikací D
Si ∩ Sj ≠ ∅ •
= # uzlů N
•
N *K/D=N
=> D = K
•
Je potřeba přesně N quor: N = (D - 1) K + 1
Si vždy obsahuje proces Pi
∀j: Pj je členem D quor Sk tj. každý proces má stejnou odpovědnost jako člen různých quor
Maekawův algoritmus •
z procesu Pi všem členům Si
•
Jestliže člen quora není zamčený, odpoví YES a zamče se (odpovídá na první požadavek) •
Jestliže je proces už zamčený, uloží požadavek do uspořádané fronty a na požadavek neodpoví
N = (K - 1) K + 1 => K ≈ √N
Algoritmus s předáváním příznaku •
Příznak obíhá mezi procesy
•
Příznak je zvláštní typ zprávy
•
Jestliže proces drží příznak, může vstoupit do KS
•
Procesy jsou logicky uspořádané do kruhu, stromu nebo úplného grafu
•
Když proces Pi vstoupí do KS, všichni členové jeho quora Si musí být zamčení
•
Jednosměrný kruh zaručuje absenci stárnutí procesů
•
Když proces Pi přijme zprávy YES od všech procesů Pk ∈ Si
•
Algoritmus může mít dva typy poruch:
Pi vstoupí do KS •
Když proces Pi opustí KS •
•
je K procesů,
každý je členem D quor
(K požadavků) •
v quoru
rozešle zprávy Release všem členům quora Si a odemče je
•
Ztráta příznaku – musí se zvolit jeden proces, který vlastní příznak
•
Nefunkční proces – musí se vytvořit nový logický kruh
Komunikační složitost O(K) = O(√N )
4!
Suzuki - Kasami algoritmus •
•
Suzuki - Kasami algoritmus
Příznak = obsahuje pole token[n] časových razítek, které označují •
kdy naposled proces Pi přijal příznak a vstoupil do KS
•
token [ ]
1 2
……
n
Lokální pole requests[n] časových razítek, které označují •
kdy naposled proces Pi požadoval vstup do KS
•
requests [ ] 1 2
•
Zprávy jsou doručené v konečném čase
•
Síť je úplně propojená (mesh)
•
Nejsou potřeba FIFO kanály
•
Komunikační složitost : n - 1
……
n
Suzuki - Kasami algoritmus
Raymondův algoritmus
For each process upon receipt of :! begin! requests[j] := max(requests[j], Tj);! if have_token and !using_token! then begin! k := i +1;! while (k ≠ i) do begin! if (requests[k] > token [k]) and ! have_token! then begin have_token := false;! send to k; end;! (k++) mod N; ! end; ! end;! end!
B
E
D
C
F
•
Logická stromová topologie
•
Zprávy se posílají jenom ve stromu
•
Komunikační složitost odpovídá ~ výšce stromu = log N
•
Proces, který vlastní příznak smí vstoupit do KS
•
Požadavky jsou ukládány do fronty v každém uzlu podle časových razítek
•
HOLDERA = D
E
D
A
B
HOLDERD = E
C
F
B
E
D
A
C
F
Distribuované algoritmy vzájemného vyloučení
Raymond’s algorithm A
For each process requesting an access to CS:! begin! if !have_token ! then begin broadcast ;! receive ; have_token := true; end! using_token := true; ! enter CS;! token[i] := local_time T;! using_token := false;! k := i +1;! while (k ≠ i) do begin! if (requests[k] > token [k] and have_token)! then begin have_token := false;! send to k; end; ! (k++) mod N; end; ! end!
D
A
B
C
E
F
•
HOLDERB = A
•
HOLDERC = A
•
A žádá o vstup do KS -> HOLDERA = D
•
HOLDERE = self
•
D žádá o příznak : HOLDERD = E
•
HOLDERF = D
•
•
HOLDERA = D
E opustil KS a předá příznak žádajícímu sousedovi, nastaví HOLDERE = D
HOLDERD = E
•
•
D : HOLDERD = A: pošle příznak uzlu A
5!
