hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
mgr-szz:in-pos:4-pos [2019/06/09 12:17] lachmanfrantisek pojmy, hodiny, globalni stav |
mgr-szz:in-pos:4-pos [2020/04/12 16:56] |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| - | ====== IN-POS 4. Modely distribuovaných systémů ====== | ||
| - | |||
| - | ===== Zadání ===== | ||
| - | |||
| - | * Základní pojmy a principy, synchronní a asynchronní komunikace. | ||
| - | * Synchronizace. | ||
| - | * Detekce ukončení. | ||
| - | * Problém vzájemného vyloučení a problém uváznutí a jejich řešení. | ||
| - | * Problém volby vedoucího prvku. | ||
| - | * Vliv topologie a její znalosti/neznalosti na složitost řešení problému. | ||
| - | |||
| - | |||
| - | * PA150, IV100 | ||
| - | |||
| - | ===== Vypracování ===== | ||
| - | |||
| - | ==== Základní pojmy a principy, synchronní a asynchronní komunikace. ==== | ||
| - | |||
| - | <box 90% red|Distribuovaný systém> | ||
| - | Systém jehož hardwarové nebo softwarové komponenty počítačů mohou komunikovat a koordinovat svou činnost pouze předáváním zpráv. | ||
| - | </box> | ||
| - | |||
| - | DS: | ||
| - | * 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í. | ||
| - | * ostatní se o stavu nedozvídají | ||
| - | |||
| - | <box 90% red|Middleware> | ||
| - | Softwarová vrstva ležící mezi aplikacemi a OS poskytující aplikacím aplikacím programovací abstrakci a maskování heterogenity podpůrných sítí, počítačů, operačních systému, programovacích jazyků,... | ||
| - | </box> | ||
| - | |||
| - | |||
| - | * Režimy DS | ||
| - | * **Synchronní výměna zpráv** | ||
| - | * výpočty probíhají v synchronních krocích (řízených globálními hodinami) | ||
| - | * v každém běhu komponenty vyšlou a přijmou zprávy a provedou výpočet | ||
| - | * přenos zprávy je kratší než jeden tik globálních hodin | ||
| - | * **Asynchronní výměna zpráv** | ||
| - | * globální čas neexistuje | ||
| - | * komponenty řízeny lokálními hodinami | ||
| - | * délka přenosu zpráv je neomezena | ||
| - | |||
| - | ==== Synchronizace ==== | ||
| - | |||
| - | <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. | ||
| - | </box> | ||
| - | |||
| - | <box 90% blue|Berkeley algoritmus synchronizace hodin> | ||
| - | - MASTER uzel se periodicky ptá na čas SLAVE uzlů. | ||
| - | - Odečte polovinu obrátky. | ||
| - | - Zprůměruje a odešle aktuální hodnotu SLAVE uzlům. | ||
| - | </box> | ||
| - | |||
| - | <box 90% blue|Network Time Protocol> | ||
| - | * Možnost přesné synchronizace s UTC v Internetu. | ||
| - | * Časové servery tvoří hierarchickou strukturu. | ||
| - | * Módy synchronizace: | ||
| - | * Multicast: jeden server odesílá informace o čase skupině. | ||
| - | * 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 | ||
| - | </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> | ||
| - | |||
| - | === Globální stav === | ||
| - | |||
| - | <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> | ||
| - | |||
| - | |||
| - | |||
| - | ==== Detekce ukončení ==== | ||
| - | ==== Problém vzájemného vyloučení a problém uváznutí a jejich řešení ==== | ||
| - | ==== Problém volby vedoucího prvku ==== | ||
| - | ==== Vliv topologie a její znalosti/neznalosti na složitost řešení problému ==== | ||
| - | |||
| - | ===== Zdroje ===== | ||
| - | |||
| - | * slidy pa150 (podzim 2017) | ||
