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/13 22:05] lachmanfrantisek |
mgr-szz:in-pos:4-pos [2020/04/12 16:56] (aktuální) |
||
---|---|---|---|
Řádek 44: | Řá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 98: | Řá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 113: | Řádek 124: | ||
* zná zprávy v "éteru" | * 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). | * 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> | </box> | ||
Řádek 355: | Řádek 389: | ||
* **participant** | * **participant** | ||
* může kdykoliv volat koordinátora požadavkem ''abort-transaction'', pokud není schopen pokračovat v řešení subtransakce. | * může kdykoliv volat koordinátora požadavkem ''abort-transaction'', pokud není schopen pokračovat v řešení subtransakce. | ||
- | </box> | ||
- | |||
- | |||
- | ==== Detekce ukončení ==== | ||
- | |||
- | == 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> | </box> | ||
Řádek 387: | Řá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: |