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 15:34] lachmanfrantisek vliv topologie |
mgr-szz:in-pos:4-pos [2020/04/12 16:56] (aktuální) |
||
---|---|---|---|
Řá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 114: | Řá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 356: | Řá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 388: | Řá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: |