hledat
Toto je starší verze dokumentu!
—-
Obsah
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.
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.
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í
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ů,…
- 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
Cristianův algoritmus synchronizace hodin
Klient pošle dotaz Časovému serveru a od získaného času odečte polovinu obrátky dotazu.
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.
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
- 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
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)
Ze vztahu TS(A)<TS(B) nevyplývá A→B.
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|
Globální stav
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).
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)
