Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze | ||
mgr-szz:in-pos:4-pos [2019/06/08 20:40] lachmanfrantisek synchronizace |
mgr-szz:in-pos:4-pos [2020/04/12 16:56] (aktuální) |
||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
- | ====== IN-POS 4. Modely distribuovaných systémů ====== | + | ====== IN-POS . Modely distribuovaných systémů ====== |
===== Zadání ===== | ===== Zadání ===== | ||
Řádek 23: | Řádek 23: | ||
DS: | DS: | ||
* umožňují souběžné řešení programů | * 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í. | * 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í | * ostatní se o stavu nedozvídají | ||
Řádek 43: | Řádek 42: | ||
==== Synchronizace ==== | ==== Synchronizace ==== | ||
- | |||
- | * příčinné pořadí = "stalo se před" | ||
<box 90% blue|Cristianův algoritmus synchronizace hodin> | <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. | + | Klient pošle dotaz **časovému serveru** a od získaného času přičte polovinu obrátky dotazu. |
</box> | </box> | ||
<box 90% blue|Berkeley algoritmus synchronizace hodin> | <box 90% blue|Berkeley algoritmus synchronizace hodin> | ||
- MASTER uzel se periodicky ptá na čas SLAVE uzlů. | - MASTER uzel se periodicky ptá na čas SLAVE uzlů. | ||
- | - Odečte polovinu obrátky. | + | - Přičte polovinu obrátky. |
- Zprůměruje a odešle aktuální hodnotu SLAVE uzlům. | - Zprůměruje a odešle aktuální hodnotu SLAVE uzlům. | ||
</box> | </box> | ||
Řádek 63: | Řádek 60: | ||
* Procedure-call: server vrací časové razítko na žádost (de facto Cristianův alg.) | * 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 | * 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> | </box> | ||
==== Detekce ukončení ==== | ==== Detekce ukončení ==== | ||
- | ==== Problém vzájemného vyloučení a problém uváznutí a jejich řešení ==== | + | |
+ | Algoritmus synchronizace ukončení má za úkol zabezpečit následující: | ||
+ | V případě, že všechny procesy jsou ve stavu ukončen, pak se v konečném čase tuto skutečnost všechny procesy dozví. | ||
+ | |||
+ | <box 90% blue|Dijkstra-Scholten (DS)> | ||
+ | * Jestliže graf procesů je strom, pak každý listový proces při přechodu do stavu ukončen pošle signál svému otci. | ||
+ | * Jakmile proces dostane signály od všech svých synů, pošle signál svému otci. | ||
+ | * Jestliže všechny signály dostane iniciační proces, je distribuovaný výpočet ukončen. | ||
+ | </box> | ||
+ | |||
+ | |||
+ | <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> | ||
+ | |||
+ | |||
+ | === Commit protokoly === | ||
+ | |||
+ | Řeší atomicitu distribuované transakce. | ||
+ | |||
+ | |||
+ | <box 90% blue|2-fázový commit protokol> | ||
+ | Distribuovaná dohoda, zda transakci končit řádně, či krachovat v prostředí s výpadky uzlů. | ||
+ | |||
+ | * ➕ řeší problém atomického ukončení | ||
+ | * jestli jedna subtransakce krachuje, krachuje celá transakce | ||
+ | * jestli se ukončí řádně všechny subtransakce, ukončí se řádně i celá transakce | ||
+ | |||
+ | 2 fáze: | ||
+ | |||
+ | * **Hlasovací fáze** | ||
+ | * koordinátor žádá o závazek k rozhodnutí, že subtransakci řádně ukončí | ||
+ | * participant ověří subtransakci na konzistenci dat a odpoví | ||
+ | * **Fáze vydání rozhodnutí** | ||
+ | * Koordinátor vydává na základě získaných odpovědí rozhodnutí zda řádně ukončit, nebo krachovat. | ||
+ | * Zprávy commit/abort. | ||
+ | </box> | ||
+ | |||
+ | |||
+ | |||
+ | ==== Problém vzájemného vylouč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> | ||
+ | |||
+ | ==== Uváznutí ==== | ||
+ | |||
+ | Množina procesů P uvázla, jestliže každý proces Pi z P čeká na událost (uvolnění prostředků, zaslání zprávy), kterou vyvolá pouze některý z procesů P. | ||
+ | |||
+ | **Stárnutí** = požadavky 1 nebo více procesů z P nebudou splněny v konečném čase | ||
+ | * z důvodů vyšších priorit jiného procesu | ||
+ | * z důvodů prevence uváznutí apod. | ||
+ | |||
+ | == Nutná a postačující podmínka uváznutí == | ||
+ | |||
+ | * Nutné podmínky uváznutí: | ||
+ | - **vzájemné vyloučení** (**//Mutual exclusion//**) | ||
+ | * se sdíleným zdrojem může v jednom okamžiku pracovat právě jeden proces | ||
+ | - **inkrementálnost požadavků** (též postupné uplatňování požadavků, **//Hold-and-Wait//**) | ||
+ | * proces vlastnící nějaký zdroj potřebuje ke své činnosti zdroj další, který je však držen jiným procesem | ||
+ | - **nepředbíhatelnost** (**//No preemption//**) | ||
+ | * zdroje lze uvolnit pouze procesem, který tyto vlastní a to pouze dobrovolně, až je nebude potřebovat | ||
+ | |||
+ | |||
+ | * Postačující podmínka: | ||
+ | * **cyklické čekání** (též zacyklení pořadí, //Circular Wait//) | ||
+ | * důsledek prvních tří nutných podmínek | ||
+ | * existuje množina //n// procesů (//P<sub>0</sub>...P<sub>n</sub>//), kde proces //P<sub>0</sub>// čeká na uvolnění zdroje drženého procesem //P<sub>1</sub>//, //P<sub>1</sub>// čeká na uvolnění zdroje drženého //P<sub>2</sub>// atd. až //P<sub>n</sub>// čeká na uvolnění zdroje drženého //P<sub>0</sub>// | ||
+ | |||
+ | |||
+ | ==Metody ochrany proti uváznutí== | ||
+ | |||
+ | **Ochrana před uváznutím prevencí** | ||
+ | |||
+ | * zajistíme, že se systém nikdy nedostane do stavu uváznutí | ||
+ | * zrušíme platnost některé nutné podmínky | ||
+ | |||
+ | * **nepřímé metody** (zneplatnění nutné podmínky) | ||
+ | * **Virtualizací prostředků** zrušíme **//Mutual exclusion//**. | ||
+ | * **Požadováním všech prostředků najednou** zrušíme **//Hold-and-Wait//**. | ||
+ | * ➕ nemusí se nic odebírat, vhodné pro procesy s jednou nárazovou činností | ||
+ | * ➖ neefektivní, možná prodleva při zahájení procesu | ||
+ | * **Odebíráním prostředků** zrušíme **//No preemption//** | ||
+ | * Proces, jemuž byl odmítnut požadavek, uvolní vše co vlastní a o vše požádá znovu. | ||
+ | * ➕ vhodné pro prostředky s uchovatelným a obnovitelným stavem (FAP, procesor) | ||
+ | * ➖ režijní ztráty, možnost cyklického restartu | ||
+ | * **přímé metody** (nepřipuštění planosti postačující podmínky) | ||
+ | * **uspořádáním prostředků** zrušíme možnost vzniku zacyklení při čekání: procesy smí požadovat prostředky pouze ve stanoveném pořadí | ||
+ | * ➕ lze kontrolovat při kompilaci, nic se neřeší za běhu | ||
+ | * ➖ neefektivní | ||
+ | |||
+ | **Obcházení uváznutí** | ||
+ | |||
+ | * detekce potenciální možnosti vzniku uváznutí a nepřipuštění takového stavu | ||
+ | * zamezujeme současné platnosti všech nutných podmínek | ||
+ | * prostředek se nepřidělí, pokud by hrozilo uváznutí (hrozí stárnutí) | ||
+ | |||
+ | |||
+ | <box 95% round blue|Bankéřův algoritmus > | ||
+ | |||
+ | * Algoritmus používaný u zdrojů, kterých se přiděluje určité množství. | ||
+ | * Když vstoupí novy proces do systému, musí deklarovat maximální počet instanci všech tříd, které bude pro svůj běh potřebovat. Tato maxima nesmi přesahovat celkový počet zdrojů v systému. Když uživatel požaduje množinu zdrojů, musí systém zjistit nepřevede-li alokace těchto zdrojů systém do nebezpečného stavu. Pokud by tomu tak bylo, musí proces čekat než jiný proces neuvolní dostatek zdrojů. V případe opačném jsou zdroje procesu alokovány. | ||
+ | * Pro zajištěni chodu bankéřova algoritmu je třeba udržovat množství datových struktur. Tyto struktury kódují stav systému alokace zdrojů. Nechť n je celkový počet procesu v systému a m je počet typu zdrojů. Potřebujeme následující datové struktury: | ||
+ | *Volny: vektor delky m indikujici pocet volnych instanci kazdeho typu zdroje. Jestlize Volny(j) = k, potom je v systemu k volnych instanci zdroje Rj. | ||
+ | *Max: matice typu (n,m) definujici maximalni pozadavek kazdeho procesu na kazdou tridu zdroju. Jestlize Max(i,j) = k, potom proces Pi muze pozadat maximalne o k instanci zdroje Rj. | ||
+ | *Alokace: matice typu (n,m) definujici pocet zdroju kazde tridy aktualne alokovany kazdemu procesu. Jestlize Alokace(i,j) = k, potom proces Pi ma momentalne alokovano k instanci zdroje tridy Rj. | ||
+ | *Potreba: matice typu (n,m) definujici zbyly pocet instanci zdroje kazde tridy nutny k dokonceni ulohy. Jestlize Potreba(i,j) = k, potom proces Pi potrebuje k dokonceni sve ulohy dalsich k instanci tridy Rj. | ||
+ | *Uvedene datove struktury se v case meni jak co do velikosti, tak co do hodnoty. Pro zjednoduseni prezentace Bankerova algoritmu definujme nasledujici vztah: Necht X a Y jsou vektory delky n. Potom X < = Y tehdy a jen tehdy, jestlize X(i) < = Y(i) pro vsechna i = 1, .. ,n. Napriklad jestlize X = (1, 7, 3, 2) a Y = (0, 3, 2, 1), potom Y < = X. Dale X < Y tehdy, jestlize X < = Y a zaroven X < > Y. | ||
+ | *Kazdou radku matic Alokace a Potreba muzeme zpracovavat jako vektor a oznacovat jako Alokacei a Potrebai. Vektor Alokacei specifikuje zdroje, ktere jsou aktualne alokovany procesu Pi a vektor Potrebai specifikuje dalsi zdroje, ktere proces Pi potrebuje pro sve dokonceni. | ||
+ | |||
+ | |||
+ | Uvazujme system s peti procesy P0 az P4 a tri zdroje typu A, B, C. | ||
+ | *Zdroj typu A ma 10 instanci | ||
+ | *zdroj typu B ma 5 instanci | ||
+ | *zdroj typu C 7 instanci | ||
+ | Necht v case t0 je system v nasledujicim stavu: | ||
+ | | ^ Alokace ^^^ Max ^^^ Volny ^^^ | ||
+ | | ^ A ^ B ^ C ^ A ^ B ^ C ^ A ^ B ^ C ^ | ||
+ | ^ P0 | 0 | 1 | 0 | 7 | 5 | 3 | 3 | 3 | 2 | | ||
+ | ^ P1 | 2 | 0 | 0 | 3 | 2 | 2 | | ||
+ | ^ P2 | 3 | 0 | 2 | 9 | 0 | 2 | | ||
+ | ^ P3 | 2 | 1 | 1 | 2 | 2 | 2 | | ||
+ | ^ P4 | 0 | 0 | 2 | 4 | 3 | 3 | | ||
+ | |||
+ | *Obsah matice **Potreba** je definovan rozdilem **Max - Alokace** a je tedy: | ||
+ | |||
+ | | ^ Potreba^^^ | ||
+ | | ^ A ^ B ^ C ^ | ||
+ | | P0 | 7 | 4 | 3 | | ||
+ | | P1 | 1 | 2 | 2 | | ||
+ | | P2 | 6 | 0 | 0 | | ||
+ | | P3 | 0 | 1 | 1 | | ||
+ | | P4 | 4 | 3 | 1 | | ||
+ | |||
+ | *V teto situaci je system v bezpecnem stavu. Sekvence < P1, P3, P4, P2, P0,> je bezpecna sekvence. | ||
+ | |||
+ | </box> | ||
+ | |||
+ | |||
+ | **Detekce a obnova po uváznutí** | ||
+ | |||
+ | * Uváznutí povolíme, ale jeho vznik detekujeme a řešíme. | ||
+ | * OS periodicky testuje existenci uváznutí (detekce cyklu v grafu). | ||
+ | * ➕ žádný prostoj při zahájení | ||
+ | * ➖ nutnost řešit uváznutí | ||
+ | |||
+ | Způsoby řešení uváznutí: | ||
+ | |||
+ | * zrušit všechny uváznuté procesy (nejčastěji používaná metoda) | ||
+ | * návrat uváznutých procesů k poslednímu kontrolnímu bodu (možnost opakování situace) | ||
+ | * postupně rušit uváznuté procesy (podle spotřebovaného času procesoru, počtu tiskových řádků, času do dokončení procesu, priority, množství vlastněných prostředků) | ||
+ | * postupně předbíhat uváznuté procesy | ||
+ | * zamezit současné platnosti nutných podmínek | ||
+ | |||
+ | |||
+ | |||
+ | **Ignorování hrozby uváznutí** | ||
+ | |||
+ | * uváznutí je věc aplikace ne systému | ||
+ | * způsob řešení zvolený většinou OS | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | === Uváznutí v distribuovaném prostředí === | ||
+ | |||
+ | |||
+ | <box 90% red|Distribuovaná transakce> | ||
+ | transakce zahrnující operace prováděné ve více uzle DS formou dílčích subtransakcí. | ||
+ | |||
+ | * **koordinátor** | ||
+ | * registruje spuštění transakce | ||
+ | * registruje participanty (příp. dělí transakci na subtransakce) | ||
+ | * řeší akce při ukončování | ||
+ | * **správce** | ||
+ | * udržuje deník pro obnovu transakcí | ||
+ | * participuje na schématu řízení souběžnosti | ||
+ | * **participant** | ||
+ | * může kdykoliv volat koordinátora požadavkem ''abort-transaction'', pokud není schopen pokračovat v řešení subtransakce. | ||
+ | </box> | ||
+ | |||
+ | |||
==== Problém volby vedoucího prvku ==== | ==== 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)> | ||
+ | Využitelnou topologií je obousměrný kruh. 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 | ||
+ | |||
+ | * nejhorší případ: O(n*n) zpráv | ||
+ | * očekávaný počet zpráv: O(n log n) zpráv | ||
+ | </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. | ||
+ | |||
+ | * složitost: O(n log n) | ||
+ | </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 ==== | ==== Vliv topologie a její znalosti/neznalosti na složitost řešení problému ==== | ||
+ | |||
+ | FIXME: nejsem si 100% jistý, co se zde očekává (resp. z čeho čerpat) | ||
+ | |||
+ | * Efektivita algoritmu velmi závisí na topologii sítě. | ||
+ | * Zajímá nás **komunikační složitost**, případně časová složitost. | ||
+ | |||
+ | |||
+ | <box 90% red|Horní odhad pro problém> | ||
+ | Existuje algoritmus, který pro všechny topologie, vstupy, časování,... pracuje správně a vymění nejvíc f(n) zpráv. | ||
+ | </box> | ||
+ | <box 90% red|Dolní odhad pro problém> | ||
+ | Pro každý algoritmus existuje kombinace topologie, vstupu, časování,... že buď nepracuje správně, nebo vymění alespoň f(n) zpráv. | ||
+ | </box> | ||
+ | |||
+ | * Časté topologie: | ||
+ | * **úplný graf** | ||
+ | * každý komunikuje přímo s každým | ||
+ | * **kruh** | ||
+ | * každý má levého a pravého souseda | ||
+ | * všichni jsou uspořádání do kruhu | ||
+ | * **jednosměrný kruh** | ||
+ | * každý má jen jednoho souseda | ||
+ | * po N přeposláních se zpráva dostane zpět k původci | ||
+ | * **2D/3D mřížka** | ||
+ | * **strom** | ||
+ | |||
+ | * Pro tyto topologie existují často efektivnější algoritmy, protože lze spoléhat na jejich vlastnosti. | ||
+ | * Pro globální algoritmy se může efektivita lišit na základě grafových vlastností: | ||
+ | * hustota grafu | ||
+ | * orientovanost | ||
+ | * poloměr | ||
+ | |||
+ | * Pro tvorbu paralelních algoritmů je nejprve potřebné zvládnout několik principielních úloh: | ||
+ | * prohledávání uzlů | ||
+ | * shout-and-echo (4m zpráv, 2diam(G) čas) | ||
+ | * DFS (2m zpráv, 2m čas) | ||
+ | * Awerbuch (4m zpráv, 4n−2 čas) | ||
+ | * BFS: | ||
+ | * Cheung’83 (<m>m^3</m> zpráv, m čas) | ||
+ | * Cheung,Zhu’87 (<m>m^2</m> zpráv, <m>m^2</m> čas) | ||
+ | * komunikace mezi uzly | ||
+ | * volba vůdce | ||
+ | * globální algoritmus (<m>\Omega (n \log n)</m> zpráv) | ||
+ | |||
+ | |||
+ | * Další důležité parametry: | ||
+ | * jednosměrnost/obousměrnost hran | ||
+ | * (ne)znalost sítě/sousedů | ||
+ | * existuje globální čas | ||
+ | * očíslování hran | ||
+ | * identifikace jednotlivých uzlů | ||
+ | |||
+ | |||
+ | ===== Zdroje ===== | ||
+ | |||
+ | * slidy pa150 (podzim 2017) | ||
+ | * http://statnice.dqd.cz/mgr-szz:in-pos:1-pos | ||
+ | * http://statnice.dqd.cz/mgr-szz:in-tei:8-tei |