49 - Distribuovaný broadcast, synchronizace v distribuovaných systémech Flashcards
Distribuovaný broadcast
K tomu, aby když posíláme zprávy v distribuovaných systémech, tak abychom si byli jisti, že dojdou příjemci a nepomíchaly se (tedy zprávy byly vždy doručeny a to maximálně jednou a ve správném pořadí).
Posílání zpráv používá například Lamportův algoritmus pro vzájemné vyloučení zdroje.
“In distributed systems, atomic broadcast or total order broadcast is a broadcastmessaging protocol that ensures that messages are received reliably and in the same order by all participants”
pojmy:
- m - zpráva z množiny možných zpráv, každá zpráva zahrnuje odesílatele (sender(m)) a sekvenční číslo (seq(m))
- funkce bcast(m) a deliver(m)
- např. sender(m)=p a seq(m)=i znamená, že m je i-tá zpráva poslaná procesem p
- komunikace: známe horní mez zpoždění zprávy; lokální hodiny pro každý proces
- topologie: obecná topologie grafu
• specifikace ○ m = zpráva z množiny možných zpráv ○ každá zpráva obsahuje § totožnost odesilatele: sender(m) § pořadové číslo (kolikátou zprávu odesilatel poslal): seq(m)
• Tedy deliver - doručit, znamená prakticky přijmout na straně aplikace.
3 hlavní vlastnosti broadcastu - spolehlivý broadcast
Následující 3 vlastnosti tvoří spolehlivý broadcast
platnost (validity): když se pošle, tak se doručí
dohoda (agreement): když někdo přijme, všichni prijmou
celistvost (integrity): každý přijme zprávu jen jednou
• Platnost (validity): pokud správný proces odešle zprávu, pak všem procesům je tato zpráva nakonec doručena. - (Pokud korektní proces odešle broadcast, pak všechny korektní procesy tento broadcast obdrží (dříve či později)) • Dohoda (agreement): pokud správný proces doručí zprávu (přijme ji), pak všem procesům je tato zpráva nakonec doručena. - (Pokud korektní proces obdržel broadcast, potom všechny korektní procesy obdrží broadcast také (dříve či později)) • Celistvost (Integrity): každý proces přijme zprávu jen jedenkrát. - (Každý korektní proces obdrží broadcast maximálně jednou (nedojde k zacyklení))
Další vlastnosti broadcastu a klasifikace
FIFO - když proces odešle m před n, všichni přijmou v tomto pořadí
casual - pokud m předchází n, všichni přijmou v tomto pořadí
total - všichni přijmou ve stejném pořadí
• FIFO řazení (FIFO order): pokud proces odešle zprávu m před n, tak žádný proces správný proces nesmí přijmout n před m. ○ “FIFO order” from single process • Náhodné řazení (Casual order): pokud zpráva m náhodně předchází n, tak žádný proces nesmí doručit n aniž by předtím doručil m. ○ “FIFO order” from all processes • Celkové řazení (Total order): pokud správné procesy p a q oba doručí zprávy m a n, pak p doručí m před n pokud q doručí m před n. ○ Receiving in the same order.
Klasifikace
Reliable (RBCAST) = Validity + Agreement + Integrity
FIFO (FBCAST) = reliable + FIFO Order
Causal (CBCAST) = reliable + Causal Order
Atomic (ABCAST) = reliable + Total Order
Algoritmus pro spolehlivý broadcast (RBCAST)
Odesílatel o:
bcast(R,m): //R = reliable bcast, m = zprava
- pridej do m odesilatele(m) a sekvencni_cislo(m);
- send(m) vsem sousedum, vcetne sebe;
Prijemce p: deliver(R,m): - pri receive(m) do - - if p jeste neprijal tento broadcast then - - - if sender(m) != p then send(m) vsem sousedum; - - deliver(R,m) - endif; enddo;
Synchronizace v distribuovaných systémech
V distribuovaných systémech není údaj o globálním čase (i kdyby byl, nejsme schopní kontrolovat zpoždění mezi doručením zpráv). Tedy každý uzel má vlastní hodiny. Řešíme problém vzájemného vyloučení pří požadavku více klientů v distribuovaném prostředí na sdílený zdroj. 2 možnosti:
• absence globálních a synchronizačních hodin • vzájemné vyloučení ○ existuje pevný počet procesorů, které sdílí jeden zdroj a ten může v danou chvíli používat pouze jeden procesor ○ centralizované řešení • Třídy algoritmů: ○ Timestamp-based (Lamport + optimalizace Ricart-Agrawala algoritmus) ○ Token-based (Raymond)
Synchronizace v distribuovaných systémech - Lamportovy logické hodiny
Lamportovy logické hodiny
- Není zde žádná souvislost s fyzickými hodinami, ve skutečnosti jde o časová razítka.
- !!! NEREFLEXNÍ ČÁSTEČNÉ USPOŘÁDÁNÍ Založeno na relaci mezi dvěma událostmi stalo_se_dříve(a,b) - “happens-before” !!!
- > Tyto hodiny představují nereflexní částečné uspořádání - Nicméně dá se to rozšířit i na totální uspořádání (použije se sekundární klíč, např. ID procesu)
- Vychází z pravidel fyzické kauzality (než něco přijmeme, musíme to odeslat)
- Synchronizace hodin mezi 2 procesy probíhá takto:
- Každý proces má vlastní čítač běžící různou rychlostí
- Proces 1 chce odeslat zprávu procesu 2, společně se zprávou vloží hodnotu svého čítače
- Proces 2 přijme zprávu od procesu 1 a zjistí časové razítko
- Proces 2 porovná hodnoto svého čítače s hodnotou extrahovanou z časového razítka procesu 1
- Proces 2 si nastaví hodnotu svého čítače na vyšší z těchto dvou hodnot a inkrementuje hodnotu
- V tuto chvíli jsou procesy 1 a 2 synchronizovány (ale jen na chvíli, protože jejich čítače běží obecně různě rychle)
Co se týče logických hodin, tak ty jsou založeny na inkrementování čítače.
• Procesor i má logické hodiny C_i
• Hodnota těchto hodin se inkrementuje před každou událostí na i.
• Každá událost a přiřadí hodinám hodnotu C(a).
• if a→b, then C(a)
Synchronizace v distribuovaných systémech - Lamportův algoritmus a ricart-agrawala vylepšení
• Decentralizovaný algoritmus vzájemného vyloučení.
• Předpokládá obousměrné FIFO kanály mezi procesy.
• Každý proces udržuje vlastní prioritní frontu požadavků.
○ Používá časových značek k uspořádání požadavků.
• Vyžaduje 3∗(n−1) zpráv. • Probíhá ve třech fázích: 1. Požadavek (req) 2. Potvrzení (ack) 3. Uvolnění (rel)
• Proces P požaduje zdroj posláním požadavku do všech procesů zasláním zprávy req. • Při příjmu požadavku je požadavek zařazen do fronty požadavků uspořádané dle časových značek, poslání zprávy ack. ○ Tady konečně vidíme, k čemu jsou potřeba ty logické hodiny :-) * Ukončení zpracování požadavku – odstranění požadavku z fronty a poslání zprávy rel ostatním procesům. * Přijetí zprávy rel od procesu P – odstranění požadavku procesu P z fronty. * Povolení zpracování požadavku – požadavek je na prvním místě ve frontě a je potvrzen ostatními procesy. Lamport po lopatě ○ Nějaký proces P se rozhodne, že chce přistoupit ke sdíleném zdroji. Jelikož je slušňák, tak svůj úmysl oznámí všem ostatním procesům, a to tak, že jim pošli REQ zprávu spolu se svou časovou značkou a ID. ○ Poté, co mu všechny ostatní procesy odpoví zprávou ACK, se proces podívá do své fronty požadavků, jestli je na řadě. § Pokud je na řadě, tak použije sdílený zdroj a potom všem procesům pošle zprávu REL, které je informuje, že už daný zdroj nepotřebuje. ○ Pokud není na řadě, tak počká dokud mu nepřijde REL zpráva od ostatních procesů a on se na řadu konečně dostane.
Ricart-Agrawala algorithm - prostě spojí ack a rel zprávu
Je to optimalizovaný Lamport.
• Spojuje release a reply zprávy.
○ Tedy místo 3(n−1) zpráv se posílá jenom 2(n−1)
Pokud to chápu správně, tak se REL zpráva pošle jenom tomu procesu, který je další na řadě.
Synchronizace v distribuovaných systémech - raymondův algoritmus
- token-based algoritmus
- procesy uspořádány do stromu
- samotný token představuje KS - pokud má token, může vstoupit
Problémy: hladovění, deadlock, tolerance chyb
Uzly, představující procesy v distribuovaném systému jsou uspořádány do binárního stromu. V tomto stromě se pohybuje “token”, udávající povolení ke vstupu do kritické sekce. Procesy bojují o token, pouze ten který ho má smí vstoupit do KS. Problémem je přerušení některé větve v systému - pak procesy v této větvi nemohou vstoupit do KS.
Proces který potřebuje token pošle svou žádost nejkratší cestou k procesu co ho zrovna má, po uvolnění se pošle token dalšímu čekajícímu
PRAM shrnutí
• synchronní model paralelního výpočtu ve kterém procesory komunikují sdílenou pamětí
• výpočet probíhá po krocích:
1. čtení sdílené paměti
2. lokální operace
3. zápis do sdílené paměti
• přístupy do paměti: EREW, ERCW, CREW, CRCW
• řešení zápisových konfliktů
○ COMMON: všechny zapisované hodnoty musí být shodné
○ ARBITRARY: zapisované hodnoty mohou být různé, zapíše se libovolná hodnota
○ PRORITY: procesory mají prioritu
• broadcast
○ hodnota uložená v paměti má být rozšířena mezi N procesory
○ pro CREW a CRCW řešení v konstantním čase
○ pro EREW je třeba simulovat současné čtení (P1 přečte D a zpřístupní jej P2, P1 a P2 jej zpřístupní P3 a P4…)
- Tedy v logaritmickém čase.