hledat
Rozdíly
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: | ||
