Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
mgr-szz:in-pos:4-pos [2019/06/09 18:08] lachmanfrantisek volba vůdce |
mgr-szz:in-pos:4-pos [2020/04/12 16:56] |
||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
- | ====== IN-POS 4. Modely distribuovaných systémů ====== | ||
- | ===== Zadání ===== | ||
- | |||
- | * Základní pojmy a principy, synchronní a asynchronní komunikace. | ||
- | * Synchronizace. | ||
- | * Detekce ukončení. | ||
- | * Problém vzájemného vyloučení a problém uváznutí a jejich řešení. | ||
- | * Problém volby vedoucího prvku. | ||
- | * Vliv topologie a její znalosti/neznalosti na složitost řešení problému. | ||
- | |||
- | |||
- | * PA150, IV100 | ||
- | |||
- | ===== Vypracování ===== | ||
- | |||
- | ==== Základní pojmy a principy, synchronní a asynchronní komunikace. ==== | ||
- | |||
- | <box 90% red|Distribuovaný systém> | ||
- | Systém jehož hardwarové nebo softwarové komponenty počítačů mohou komunikovat a koordinovat svou činnost pouze předáváním zpráv. | ||
- | </box> | ||
- | |||
- | DS: | ||
- | * umožňují souběžné řešení programů | ||
- | * neexistuje globální čas | ||
- | * každá komponenta (včetně propojovací sítě) může selhávat a obnovovat činnost nezávisle na okolí. | ||
- | * ostatní se o stavu nedozvídají | ||
- | |||
- | <box 90% red|Middleware> | ||
- | Softwarová vrstva ležící mezi aplikacemi a OS poskytující aplikacím aplikacím programovací abstrakci a maskování heterogenity podpůrných sítí, počítačů, operačních systému, programovacích jazyků,... | ||
- | </box> | ||
- | |||
- | |||
- | * Režimy DS | ||
- | * **Synchronní výměna zpráv** | ||
- | * výpočty probíhají v synchronních krocích (řízených globálními hodinami) | ||
- | * v každém běhu komponenty vyšlou a přijmou zprávy a provedou výpočet | ||
- | * přenos zprávy je kratší než jeden tik globálních hodin | ||
- | * **Asynchronní výměna zpráv** | ||
- | * globální čas neexistuje | ||
- | * komponenty řízeny lokálními hodinami | ||
- | * délka přenosu zpráv je neomezena | ||
- | |||
- | ==== Synchronizace ==== | ||
- | |||
- | <box 90% blue|Cristianův algoritmus synchronizace hodin> | ||
- | Klient pošle dotaz Časovému serveru a od získaného času odečte polovinu obrátky dotazu. | ||
- | </box> | ||
- | |||
- | <box 90% blue|Berkeley algoritmus synchronizace hodin> | ||
- | - MASTER uzel se periodicky ptá na čas SLAVE uzlů. | ||
- | - Odečte polovinu obrátky. | ||
- | - Zprůměruje a odešle aktuální hodnotu SLAVE uzlům. | ||
- | </box> | ||
- | |||
- | <box 90% blue|Network Time Protocol> | ||
- | * Možnost přesné synchronizace s UTC v Internetu. | ||
- | * Časové servery tvoří hierarchickou strukturu. | ||
- | * Módy synchronizace: | ||
- | * Multicast: jeden server odesílá informace o čase skupině. | ||
- | * Procedure-call: server vrací časové razítko na žádost (de facto Cristianův alg.) | ||
- | * Symmetric: mezi 2 servery v různých úrovních; servery si opakovaně posílají časová razítka a opravují chyby | ||
- | </box> | ||
- | |||
- | |||
- | * příčinné pořadí = "stalo-se-před" | ||
- | |||
- | |||
- | * **Lokální čas** | ||
- | * budován na relaci "stalo-se-před" | ||
- | * pro události A, B v jednom procesu, kde A nastala před B: A->B | ||
- | * je-li A zaslání a B přijetí zprávy: A->B | ||
- | * platí transitivita: A->B,B->C => A->C | ||
- | * pužíván místo fyzického času | ||
- | |||
- | <box 90% blue|Lamportovy hodiny> | ||
- | * S každou událostí se sváže časové razítko. | ||
- | * Každý proces si udržuje logické (Lamportovy) hodiny. (Mapují částečné uspořádání.) | ||
- | * Odeslání zprávy: | ||
- | * Odešleme aktuální časové razítko. | ||
- | * Lokální čas zvýšíme o jedna. | ||
- | * Příjem zprávy: | ||
- | * Porovnáme přijaté časové razítko s lokálními hodinami. | ||
- | * Vezmeme větší z nich, zvýšíme o jedna a nastavíme jako lokální čas. | ||
- | * Vztah událostí: | ||
- | * A->B => TS(A) < TS(B) | ||
- | <note important>Ze vztahu **TS(A)<TS(B)** nevyplývá **A->B**.</note> | ||
- | </box> | ||
- | |||
- | <box 90% blue|Vektorové časové razítko> | ||
- | * Řeší problém s opačnou implikací u Lamprotových hodin. | ||
- | * Místo jednoho razítka pro lokální čas použijeme vektor časových razítek. (velikost = počet procesů) | ||
- | * iniciálně vyplněn nulami | ||
- | * Před odesláním proces zvýší "svůj" prvek vektoru o jedna. Pouze toto časové razítko se odesílá se zprávou. | ||
- | * Při přijetí zprávy zaktualizujeme odesilatelům prvek vektoru na maximum z lokální a přijaté hodnoty. | ||
- | * Vztah vektorových razítek: | ||
- | * V = V' iff všechny členy vektoru jsou si rovny | ||
- | * V < V' iff V[j] < V'[j] pro j=1,...|V| | ||
- | </box> | ||
- | |||
- | === Globální stav === | ||
- | |||
- | <box 90% blue|Global State Recording Algorithm Candy & Lamport> | ||
- | * **iniciátor** = proces iniciující zjištění globálního stavu | ||
- | * zaznamená momentku svého lokálního stavu a odešle MARKER všem sousedům v DS | ||
- | * MARKER získal proces, který dosud nevypracoval momentku | ||
- | * zaznamená momentku svého lokálního stavu a pošle ji iniciátorovi | ||
- | * označí vstupní kanál, ze kterého přijal MARKER", jako prázdný | ||
- | * všem ostatním sousedům pošle MARKER | ||
- | * MARKER získal proces, který již momentku vypracoval | ||
- | * zaznamená události od poslední momentky a pošle iniciátorovi | ||
- | * Iniciátor nakonec sestaví globální stav | ||
- | * zná lokální momentky všech procesů | ||
- | * zná zprávy v "éteru" | ||
- | * Kanály jsou FIFO, tedy je globální momentka smysluplná ((ne)zahrnuté zprávy jsou odděleny v kanálech MARKERy). | ||
- | </box> | ||
- | |||
- | |||
- | |||
- | ==== Detekce ukončení ==== | ||
- | ==== Problém vzájemného vyloučení a problém uváznutí a jejich řešení ==== | ||
- | |||
- | * Dva nebo více procesů obsahují **kritické sekce** sdružené s jistým sdíleným objektem, které se musí za běhu procesu **vzájemně vyloučit**. | ||
- | * privilegovaný proces = proces v kritické sekci | ||
- | |||
- | * **Podmínka bezpečnosti** = v každé konfiguraci existuje nejvýš jeden privilegovaný proces. | ||
- | * **Podmínka živosti** = Jestliže se proces snaží dostat do KS, stane se privilegovaným v konečném čase. | ||
- | * zamezuje uváznutí/stárnutí procesů | ||
- | * **Podmínka spravedlnosti** (jedna z uvedených) | ||
- | * pořadí vstupů do KS = pořadí vydání žádosti o vstup | ||
- | * každý ostatní proces DS smí žádající proces předběhnout nejvýše 1x | ||
- | |||
- | === Řešení vzájemného vyloučení === | ||
- | |||
- | * **Centralizované řešení** | ||
- | * klient-server (jeden KOORDINÁTOR řeší vzájemné vylučování libovolného počtu procesů) | ||
- | * konstantní složitost | ||
- | * request, reply+release zprávy | ||
- | |||
- | * **Distribuované řešení založené na regularitě komunikačních cest** | ||
- | |||
- | <box 90% blue|Token ring> | ||
- | Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolující vstup do kritické sekce. | ||
- | |||
- | * lineární složitost | ||
- | |||
- | * ➕ Splněna podmínka bezpečnosti. | ||
- | * ➕ Splněna podmínka živosti. | ||
- | * ➕ Podmínka spravedlnosti splněna zajištěním maximálně jednoho předběhnutí od jiného procesu. | ||
- | * ➖ Ztrátu příznaku je nutné řešit distribuovanou volbou procesu, který jej vygeneruje. | ||
- | * ➖ Výpadek jednoho uzlu nutné řešit rekonstrukcí kruhu. | ||
- | </box> | ||
- | |||
- | <box 90% blue|Raymond (tree)> | ||
- | Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolujícího vstup do kritické sekce. | ||
- | |||
- | Příznak se předává po kostře grafu tak, aby se dodržela podmínka spravedlnosti na bázi časového pořadí vzniků žádostí. | ||
- | |||
- | * Uzel držící příznak je kořenem stromu. | ||
- | * Uzel žádá o vstup do KS svého rodiče, ten jej předává po cestě ke kořeni. | ||
- | * Při předání příznaku se konfigurace stromu aktualizuje. | ||
- | |||
- | * ➕ Vzájemná výlučnost splněna trvale. | ||
- | * ➕ Nemůže dojít ani k uváznutí ani ke stárnutí. | ||
- | |||
- | </box> | ||
- | |||
- | * **Distribuované řešení založené na získání souhlasu partnerských procesů** | ||
- | |||
- | <box 90% blue|Suzuki-Kasami (token-passing)> | ||
- | Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolujícího vstup do kritické sekce. | ||
- | |||
- | Příznak se předává na bázi cykličnosti uspokojování žádosti procesů. | ||
- | |||
- | Přehled nově generovaných a dosud nesplněných žádostí se udržuje distribuovaně v uzlech a v příznaku. | ||
- | |||
- | * Proces pro žádost o vstup do KS odesílá všem uzlům REQUEST zprávu. | ||
- | * Uzel držící příznak po výstupu z KS odešle vybranému z procesů příznak. | ||
- | * Procesy si drží čísla žádostí od ostatních, token obsahuje pole s vyhověnými žádostmi. | ||
- | * Postupuje se cyklicky, přes procesy, které mají zájem. | ||
- | |||
- | |||
- | * ➖ Procesy se musí navzájem znát. | ||
- | |||
- | </box> | ||
- | |||
- | <box 90% blue|Ricard-Agrawala (distribuovaná fronta)> | ||
- | Proces požadující vstoupit do kritické sekce pošle žádost o vstup s časovým razítkem všem ostatním. | ||
- | * Jestliže je příjemce v KS, neodpovídá a zařadí požadavek do fronty. | ||
- | * Jestliže příjemce není v KS a ani do ní nechce vstoupit, pak pošle zpět potvrzení práva vstupu do KS. | ||
- | * Jestliže příjemce není v KS, ale chce do ní vstoupit (sám vyslal žádost), porovná časovou značku své a přijaté žádosti. | ||
- | * Pokud byla vlastní žádost odeslána dříve, neodpovídá a uloží žádost do fronty. | ||
- | * Pokud byla přijatá žádost odeslána dříve, pošle zpět potvrzení práva vstupu do KS. | ||
- | |||
- | * Až získá proces souhlas od všech, vstupuje do KS. | ||
- | * Po opuštění KS proces odešle potvrzení všem procesům, které má ve frontě. | ||
- | |||
- | * ➕ Je splněna podmínka bezpečnosti. | ||
- | * ➕ Je splněna podmínka živosti. | ||
- | * ➕ Komunikační složitost je lineární. | ||
- | * ➖ Proces musí znát ostatní. | ||
- | * ➖ Výpadek jednoho procesu způsobí kolaps celého systému. => Vhodné pro malé a stabilní množiny procesů. | ||
- | </box> | ||
- | |||
- | <box 90% blue|Maekawa (hlasovací kvórum)> | ||
- | Každý proces obdrží jeden příznak (hlas). | ||
- | |||
- | Proces požadující vstup do KS žádá o příznak procesy ve svém kvóru. | ||
- | * kvůrum = podmnožina procesů, navzájem se protínají | ||
- | * Oslovený jej pošlu pokud jej ještě vlastní a sám se v KS nenachází. | ||
- | |||
- | Proces s hlasy od procesů v jeho kvóru vstupuje do KS. Po vystoupení hlasy vrací původním majitelům. | ||
- | |||
- | Podmínky kvóra: | ||
- | * bezpečnost: | ||
- | * Každá dvojice volebních okrsků má alespoň jeden společný prvek. | ||
- | * Každý má pouze jeden hlas. => Nemohou být současně zvoleny dva procesy. | ||
- | * spravedlnost | ||
- | * Velikost okrsků je konstantní a každý proces je ve stejném počtu okrsků. | ||
- | * Všechny procesy potřebují pro vstup do KS stejný počet hlasů | ||
- | </box> | ||
- | |||
- | ==== Problém volby vedoucího prvku ==== | ||
- | |||
- | <box 90% red|Problém volby vůdce> | ||
- | Každž výpočet podle volebního algoritmu ve skupině procesů DS musí v konečném čase končit konfigurací, ve které je jeden jediný uzel v roli vůdce. | ||
- | |||
- | Každý proces se během existence může nacházet ve třech stavech: | ||
- | * nerozhodnutý (ve skupině běží volba) | ||
- | * vůdce (volba skončila) | ||
- | * není vůdce (volba skončila) | ||
- | </box> | ||
- | |||
- | * **skupina anonymních procesů** = procesy nemají ve skupině jedinečné id | ||
- | * nelze řešit problém volby vůdce za splnění podmínky bezpečnosti (v každém kroku všichni dostávají shodné zprávy) | ||
- | * **skupina neanonymních procesů** = procesy mají ve skupině jedinečné id | ||
- | |||
- | * **uniformní algoritmus** = procesy neznají počet procesů | ||
- | * stejný algoritmus pro jakýkoliv rozměr skupiny | ||
- | * **neuniformní algoritmus** = procesy znají počet procesů ve skupině | ||
- | * algoritmy pro různé rozměry skupiny se liší | ||
- | |||
- | * volební běh | ||
- | * Každý proces může najednou vyvolat pouze jeden běh. | ||
- | * Může probíhat několik (N) paralelních běhů. | ||
- | * Každý proces má právo i povinnost volit. | ||
- | * Volba končí ukončením všech běhů. | ||
- | |||
- | * Podmínka bezpečnosti | ||
- | * Rozhodnutí volby je zvoleným procesem nezměnitelné. | ||
- | * Vedoucím procesem je nejvýše jeden proces. | ||
- | * Každý účastník volby má nastaveno elected na id zvoleného procesu. | ||
- | * Podmínka živosti | ||
- | * Na volbě participují všechny procesy a nakonec nastaví elected na nějakou hodnotu. | ||
- | * Jeden uzel se nakonec stává vůdcem. | ||
- | |||
- | |||
- | <box 90% blue|Ring algorithm (LeLann)> | ||
- | Každý proces posílá své ID po kruhu. | ||
- | |||
- | * Kruh je jednosměrný, každý proces má jednoho souseda a komunikace probíhá ve FIFO režimu. | ||
- | * Z příchozích zpráv si uzel postupně zapamatovává ID ostatních a zprávy přeposílá dál po kruhu. | ||
- | * Po přijetí zprávy s vlastním ID zná proces všechny procesy v kruhu a za vodce zvolí proces s nejmenším/největším ID. | ||
- | </box> | ||
- | |||
- | <box 90% blue|Ring algorithm (Chang, Roberts)> | ||
- | Každý proces má jednoho souseda (následníka) a uchovává si id vůdce v elected. | ||
- | |||
- | * Každý proces je ve stavu ''participant'', nebo ''non-participant''. | ||
- | * Iniciálně jsou všichni ''non-participant''. | ||
- | * Proces zahajující volební běh se označí za ''participant'' a pošle volící zprávu <m>election(P_i)</m> následníkovi. | ||
- | * Následník se rozhoduje: | ||
- | * <m>P_i > P_{i+1}</m>: přepošle <m>election(P_i)</m> | ||
- | * <m>P_i < P_{i+1}</m> a není účastníkem volby: přepošle <m>election(P_{i+1})</m> a označí se za účastníka volby | ||
- | * <m>P_i < P_{i+1}</m> a je účastníkem volby: přijatou zprávu nepřeposílá = ruší volební běh <m>P_i</m>; volební běh <m>P_{i+1}</m> běží | ||
- | * <m>P_i = P_{i+1}</m>: <m>P_{i+1}</m> získal volící zprávu, kterou vyslal | ||
- | * přepne se do stavu vůdce | ||
- | * označí se za ''non-participant'' | ||
- | * pošle po kruhu ukončovací zprávu <m>elected(P_i)</m> (ostatní si označí vůdce a zruší účast) | ||
- | |||
- | * ➕ sledování stavu ''participant''/''non-participant'' umožňujue likvidovat zbytečné násobné běhy. | ||
- | * ➖ výpadek uzlu značí výpadek celé úlohy | ||
- | </box> | ||
- | |||
- | <box 90% blue|Ring algorithm (Hirschberg-Sinclair)> | ||
- | Využitelnou topologií je obousměrný kruh. | ||
- | |||
- | * Iniciátor v jednotlivých fázích r=0,1,.. posílá svou identitu do vzdálenosti <m>2^r</m> nesoucí průzkumovou zprávu. | ||
- | * Identity cestující po kruhu jsou likvidovány jako u algoritmu Chang-Roberts. | ||
- | * Do další fáze vstupují pouze vítězové. (vítěz ve fázi = nejvyšší ID do vzdálenosti <m>2^r</m>) | ||
- | * Ostatní pouze přeposílají zprávy. | ||
- | </box> | ||
- | |||
- | <box 90% blue|Bully algorithm (Garcia-Molina)> | ||
- | Proces s nejvyšším ID si vynucuje svou vůdcovskou roli. | ||
- | |||
- | Použitelnost: | ||
- | * proces může poslat zprávu každému z ostatních procesů. | ||
- | * Mohou se vyskytovat výpadky uzlů. | ||
- | * Poznán na základě timeoutu. | ||
- | * Komunikační systém je spolehlivý (neztrácí se zprávy). | ||
- | |||
- | Když se proces rozhodne volit, zvolí sebe a zašle o tom zprávu všem procesům s vyšší prioritou. | ||
- | |||
- | Pokud proces přijme zprávu o volebním běhu: | ||
- | * má určitě vyšší prioritu => vrátí zamítavou odpověď | ||
- | * sám spouští volební běh -> zašle zprávu všem procesům s vyšší prioritou | ||
- | |||
- | Odpovědi: | ||
- | * Když proces dostane zamítavou odpověď, existuje proces s vyšší prioritou => proces ukončí svůj volební běh. | ||
- | * Když nedostane zamítavou odpověď, volbu vyhrál. | ||
- | * Nastaví se jako nový vůdce a pošle o tom všem ostatním procesům zprávu. | ||
- | |||
- | Pokud proces obnoví svůj běh, okamžitě zahajuje volební běh a nastane jedna ze dvou možností: | ||
- | * Stane se vůdcem. | ||
- | * Dozví se, kdo je vůdcem. | ||
- | </box> | ||
- | |||
- | |||
- | ==== Vliv topologie a její znalosti/neznalosti na složitost řešení problému ==== | ||
- | |||
- | ===== Zdroje ===== | ||
- | |||
- | * slidy pa150 (podzim 2017) |