Obsah

IN-POS . Modely distribuovaných systémů

Zadání

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:

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ů,…

Synchronizace

Cristianův algoritmus synchronizace hodin

Klient pošle dotaz časovému serveru a od získaného času přičte polovinu obrátky dotazu.

Berkeley algoritmus synchronizace hodin

  1. MASTER uzel se periodicky ptá na čas SLAVE uzlů.
  2. Přičte polovinu obrátky.
  3. 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

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|

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í.

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.

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).

Commit protokoly

Řeší atomicitu distribuované transakce.

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.

Problém vzájemného vyloučení

Řešení vzájemného vyloučení

Token ring

Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolující vstup do kritické sekce.
  • lineární složitost
  • ➕ Splněna podmínka bezpečnosti.
  • ➕ Splněna podmínka živosti.
  • ➕ Podmínka spravedlnosti splněna zajištěním maximálně jednoho předběhnutí od jiného procesu.
  • ➖ Ztrátu příznaku je nutné řešit distribuovanou volbou procesu, který jej vygeneruje.
  • ➖ Výpadek jednoho uzlu nutné řešit rekonstrukcí kruhu.

Raymond (tree)

Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolujícího vstup do kritické sekce.

Příznak se předává po kostře grafu tak, aby se dodržela podmínka spravedlnosti na bázi časového pořadí vzniků žádostí.

  • Uzel držící příznak je kořenem stromu.
  • Uzel žádá o vstup do KS svého rodiče, ten jej předává po cestě ke kořeni.
  • Při předání příznaku se konfigurace stromu aktualizuje.
  • ➕ Vzájemná výlučnost splněna trvale.
  • ➕ Nemůže dojít ani k uváznutí ani ke stárnutí.

Suzuki-Kasami (token-passing)

Vzájemně se vylučující procesy si cyklicky předávají jediný exemplář příznaku (TOKEN) povolujícího vstup do kritické sekce.

Příznak se předává na bázi cykličnosti uspokojování žádosti procesů.

Přehled nově generovaných a dosud nesplněných žádostí se udržuje distribuovaně v uzlech a v příznaku.

  • Proces pro žádost o vstup do KS odesílá všem uzlům REQUEST zprávu.
  • Uzel držící příznak po výstupu z KS odešle vybranému z procesů příznak.
  • Procesy si drží čísla žádostí od ostatních, token obsahuje pole s vyhověnými žádostmi.
  • Postupuje se cyklicky, přes procesy, které mají zájem.
  • ➖ Procesy se musí navzájem znát.

Ricard-Agrawala (distribuovaná fronta)

Proces požadující vstoupit do kritické sekce pošle žádost o vstup s časovým razítkem všem ostatním.
  • Jestliže je příjemce v KS, neodpovídá a zařadí požadavek do fronty.
  • Jestliže příjemce není v KS a ani do ní nechce vstoupit, pak pošle zpět potvrzení práva vstupu do KS.
  • Jestliže příjemce není v KS, ale chce do ní vstoupit (sám vyslal žádost), porovná časovou značku své a přijaté žádosti.
    • Pokud byla vlastní žádost odeslána dříve, neodpovídá a uloží žádost do fronty.
    • Pokud byla přijatá žádost odeslána dříve, pošle zpět potvrzení práva vstupu do KS.
  • Až získá proces souhlas od všech, vstupuje do KS.
  • Po opuštění KS proces odešle potvrzení všem procesům, které má ve frontě.
  • ➕ Je splněna podmínka bezpečnosti.
  • ➕ Je splněna podmínka živosti.
  • ➕ Komunikační složitost je lineární.
  • ➖ Proces musí znát ostatní.
  • ➖ Výpadek jednoho procesu způsobí kolaps celého systému. ⇒ Vhodné pro malé a stabilní množiny procesů.

Maekawa (hlasovací kvórum)

Každý proces obdrží jeden příznak (hlas).

Proces požadující vstup do KS žádá o příznak procesy ve svém kvóru.

  • kvůrum = podmnožina procesů, navzájem se protínají
  • Oslovený jej pošlu pokud jej ještě vlastní a sám se v KS nenachází.

Proces s hlasy od procesů v jeho kvóru vstupuje do KS. Po vystoupení hlasy vrací původním majitelům.

Podmínky kvóra:

  • bezpečnost:
    • Každá dvojice volebních okrsků má alespoň jeden společný prvek.
    • Každý má pouze jeden hlas. ⇒ Nemohou být současně zvoleny dva procesy.
  • spravedlnost
    • Velikost okrsků je konstantní a každý proces je ve stejném počtu okrsků.
    • Všechny procesy potřebují pro vstup do KS stejný počet hlasů

Uváznutí

Množina procesů P uvázla, jestliže každý proces Pi z P čeká na událost (uvolnění prostředků, zaslání zprávy), kterou vyvolá pouze některý z procesů P.

Stárnutí = požadavky 1 nebo více procesů z P nebudou splněny v konečném čase

Nutná a postačující podmínka uváznutí
Metody ochrany proti uváznutí

Ochrana před uváznutím prevencí

Obcházení uváznutí

Bankéřův algoritmus

  • Algoritmus používaný u zdrojů, kterých se přiděluje určité množství.
  • Když vstoupí novy proces do systému, musí deklarovat maximální počet instanci všech tříd, které bude pro svůj běh potřebovat. Tato maxima nesmi přesahovat celkový počet zdrojů v systému. Když uživatel požaduje množinu zdrojů, musí systém zjistit nepřevede-li alokace těchto zdrojů systém do nebezpečného stavu. Pokud by tomu tak bylo, musí proces čekat než jiný proces neuvolní dostatek zdrojů. V případe opačném jsou zdroje procesu alokovány.
  • Pro zajištěni chodu bankéřova algoritmu je třeba udržovat množství datových struktur. Tyto struktury kódují stav systému alokace zdrojů. Nechť n je celkový počet procesu v systému a m je počet typu zdrojů. Potřebujeme následující datové struktury:
    • Volny: vektor delky m indikujici pocet volnych instanci kazdeho typu zdroje. Jestlize Volny(j) = k, potom je v systemu k volnych instanci zdroje Rj.
    • Max: matice typu (n,m) definujici maximalni pozadavek kazdeho procesu na kazdou tridu zdroju. Jestlize Max(i,j) = k, potom proces Pi muze pozadat maximalne o k instanci zdroje Rj.
    • Alokace: matice typu (n,m) definujici pocet zdroju kazde tridy aktualne alokovany kazdemu procesu. Jestlize Alokace(i,j) = k, potom proces Pi ma momentalne alokovano k instanci zdroje tridy Rj.
    • Potreba: matice typu (n,m) definujici zbyly pocet instanci zdroje kazde tridy nutny k dokonceni ulohy. Jestlize Potreba(i,j) = k, potom proces Pi potrebuje k dokonceni sve ulohy dalsich k instanci tridy Rj.
  • Uvedene datove struktury se v case meni jak co do velikosti, tak co do hodnoty. Pro zjednoduseni prezentace Bankerova algoritmu definujme nasledujici vztah: Necht X a Y jsou vektory delky n. Potom X < = Y tehdy a jen tehdy, jestlize X(i) < = Y(i) pro vsechna i = 1, .. ,n. Napriklad jestlize X = (1, 7, 3, 2) a Y = (0, 3, 2, 1), potom Y < = X. Dale X < Y tehdy, jestlize X < = Y a zaroven X < > Y.
  • Kazdou radku matic Alokace a Potreba muzeme zpracovavat jako vektor a oznacovat jako Alokacei a Potrebai. Vektor Alokacei specifikuje zdroje, ktere jsou aktualne alokovany procesu Pi a vektor Potrebai specifikuje dalsi zdroje, ktere proces Pi potrebuje pro sve dokonceni.

Uvazujme system s peti procesy P0 az P4 a tri zdroje typu A, B, C.

  • Zdroj typu A ma 10 instanci
  • zdroj typu B ma 5 instanci
  • zdroj typu C 7 instanci

Necht v case t0 je system v nasledujicim stavu:

Alokace Max Volny
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3
  • Obsah matice Potreba je definovan rozdilem Max - Alokace a je tedy:
Potreba
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
  • V teto situaci je system v bezpecnem stavu. Sekvence < P1, P3, P4, P2, P0,> je bezpecna sekvence.

Detekce a obnova po uváznutí

Způsoby řešení uváznutí:

Ignorování hrozby uváznutí

Uváznutí v distribuovaném prostředí

Distribuovaná transakce

transakce zahrnující operace prováděné ve více uzle DS formou dílčích subtransakcí.
  • koordinátor
    • registruje spuštění transakce
    • registruje participanty (příp. dělí transakci na subtransakce)
    • řeší akce při ukončování
  • správce
    • udržuje deník pro obnovu transakcí
    • participuje na schématu řízení souběžnosti
  • participant
    • může kdykoliv volat koordinátora požadavkem abort-transaction, pokud není schopen pokračovat v řešení subtransakce.

Problém volby vedoucího prvku

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ý proces se během existence může nacházet ve třech stavech:

  • nerozhodnutý (ve skupině běží volba)
  • vůdce (volba skončila)
  • není vůdce (volba skončila)

Ring algorithm (LeLann)

Každý proces posílá své ID po kruhu.
  • Kruh je jednosměrný, každý proces má jednoho souseda a komunikace probíhá ve FIFO režimu.
  • Z příchozích zpráv si uzel postupně zapamatovává ID ostatních a zprávy přeposílá dál po kruhu.
  • Po přijetí zprávy s vlastním ID zná proces všechny procesy v kruhu a za vodce zvolí proces s nejmenším/největším ID.

Ring algorithm (Chang, Roberts)

Využitelnou topologií je obousměrný kruh. Každý proces má jednoho souseda (následníka) a uchovává si id vůdce v elected.
  • Každý proces je ve stavu participant, nebo non-participant.
    • Iniciálně jsou všichni non-participant.
  • Proces zahajující volební běh se označí za participant a pošle volící zprávu election(P_i) následníkovi.
  • Následník se rozhoduje:
    • P_i > P_{i+1}: přepošle election(P_i)
    • P_i < P_{i+1} a není účastníkem volby: přepošle election(P_{i+1}) a označí se za účastníka volby
    • P_i < P_{i+1} a je účastníkem volby: přijatou zprávu nepřeposílá = ruší volební běh P_i; volební běh P_{i+1} běží
    • P_i = P_{i+1}: P_{i+1} získal volící zprávu, kterou vyslal
      • přepne se do stavu vůdce
      • označí se za non-participant
      • pošle po kruhu ukončovací zprávu elected(P_i) (ostatní si označí vůdce a zruší účast)
  • ➕ sledování stavu participant/non-participant umožňujue likvidovat zbytečné násobné běhy.
  • ➖ výpadek uzlu značí výpadek celé úlohy
  • nejhorší případ: O(n*n) zpráv
  • očekávaný počet zpráv: O(n log n) zpráv

Ring algorithm (Hirschberg-Sinclair)

Využitelnou topologií je obousměrný kruh.
  • Iniciátor v jednotlivých fázích r=0,1,.. posílá svou identitu do vzdálenosti 2^r nesoucí průzkumovou zprávu.
  • Identity cestující po kruhu jsou likvidovány jako u algoritmu Chang-Roberts.
  • Do další fáze vstupují pouze vítězové. (vítěz ve fázi = nejvyšší ID do vzdálenosti 2^r)
    • Ostatní pouze přeposílají zprávy.
  • složitost: O(n log n)

Bully algorithm (Garcia-Molina)

Proces s nejvyšším ID si vynucuje svou vůdcovskou roli.

Použitelnost:

  • Proces může poslat zprávu každému z ostatních procesů.
  • Mohou se vyskytovat výpadky uzlů.
    • Poznán na základě timeoutu.
  • Komunikační systém je spolehlivý (neztrácí se zprávy).

Když se proces rozhodne volit, zvolí sebe a zašle o tom zprávu všem procesům s vyšší prioritou.

Pokud proces přijme zprávu o volebním běhu:

  • má určitě vyšší prioritu ⇒ vrátí zamítavou odpověď
  • sám spouští volební běh → zašle zprávu všem procesům s vyšší prioritou

Odpovědi:

  • Když proces dostane zamítavou odpověď, existuje proces s vyšší prioritou ⇒ proces ukončí svůj volební běh.
  • Když nedostane zamítavou odpověď, volbu vyhrál.
    • Nastaví se jako nový vůdce a pošle o tom všem ostatním procesům zprávu.

Pokud proces obnoví svůj běh, okamžitě zahajuje volební běh a nastane jedna ze dvou možností:

  • Stane se vůdcem.
  • Dozví se, kdo je vůdcem.

Vliv topologie a její znalosti/neznalosti na složitost řešení problému

FIXME: nejsem si 100% jistý, co se zde očekává (resp. z čeho čerpat)

Horní odhad pro problém

Existuje algoritmus, který pro všechny topologie, vstupy, časování,… pracuje správně a vymění nejvíc f(n) zpráv.

Dolní odhad pro problém

Pro každý algoritmus existuje kombinace topologie, vstupu, časování,… že buď nepracuje správně, nebo vymění alespoň f(n) zpráv.

Zdroje