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/09 18:15] lachmanfrantisek uváznutí |
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 45: | Řádek 44: | ||
<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 99: | Řádek 98: | ||
</box> | </box> | ||
- | === Globální stav === | + | |
+ | ==== Detekce ukonč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> | <box 90% blue|Global State Recording Algorithm Candy & Lamport> | ||
Řádek 116: | Řádek 126: | ||
</box> | </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> | ||
- | ==== Detekce ukončení ==== | ||
==== Problém vzájemného vyloučení ==== | ==== Problém vzájemného vyloučení ==== | ||
Řádek 338: | Řádek 369: | ||
* způsob řešení zvolený většinou OS | * 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> | ||
Řádek 344: | Řádek 396: | ||
<box 90% red|Problém volby vůdce> | <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ý 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: | Každý proces se během existence může nacházet ve třech stavech: | ||
Řádek 385: | Řádek 437: | ||
<box 90% blue|Ring algorithm (Chang, Roberts)> | <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. | + | 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''. | * Každý proces je ve stavu ''participant'', nebo ''non-participant''. | ||
Řádek 401: | Řádek 453: | ||
* ➕ sledování stavu ''participant''/''non-participant'' umožňujue likvidovat zbytečné násobné běhy. | * ➕ sledování stavu ''participant''/''non-participant'' umožňujue likvidovat zbytečné násobné běhy. | ||
* ➖ výpadek uzlu značí výpadek celé úlohy | * ➖ 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> | ||
Řádek 410: | Řádek 465: | ||
* Do další fáze vstupují pouze vítězové. (vítěz ve fázi = nejvyšší ID do vzdálenosti <m>2^r</m>) | * 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. | * Ostatní pouze přeposílají zprávy. | ||
+ | |||
+ | * složitost: O(n log n) | ||
</box> | </box> | ||
Řádek 416: | Řádek 473: | ||
Použitelnost: | Použitelnost: | ||
- | * proces může poslat zprávu každému z ostatních procesů. | + | * Proces může poslat zprávu každému z ostatních procesů. |
* Mohou se vyskytovat výpadky uzlů. | * Mohou se vyskytovat výpadky uzlů. | ||
* Poznán na základě timeoutu. | * Poznán na základě timeoutu. | ||
Řádek 439: | Řádek 496: | ||
==== 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 ===== | ===== Zdroje ===== | ||
Řádek 444: | Řádek 553: | ||
* slidy pa150 (podzim 2017) | * slidy pa150 (podzim 2017) | ||
* http://statnice.dqd.cz/mgr-szz:in-pos:1-pos | * http://statnice.dqd.cz/mgr-szz:in-pos:1-pos | ||
+ | * http://statnice.dqd.cz/mgr-szz:in-tei:8-tei |