Čas a stav v distribuovaném prostředí
PA150 o Principy operačních systémů
Jan Staudek http://www.fi.muni.cz/usr/staudek/vyuka/
Verze: podzim 2020
Obsah přednášky
□ Čas a jeho projevy v distribuovaném prostředí
□ Řazení událostí v distribuovaném prostředí
□ Globální stav v distribuovaném prostředí
□ Distribuované algoritmy, DA
J definice kroků prováděných procesy v distribuovaném prostředí vč. vysílaných zpráv
J V PA150 se nejedná o formální kurs distribuovaných algoritmů, jde o intuitivní seznámení s problematikou z hlediska potřebné podpory ze strany operačních systémů
J důkazy správnosti a odhady složitosti probíraných distribuovaných algoritmů jsou prezentovány neformálním způsobem.
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 1
Počítač, hodiny, čas, trvání, řazení, ...
□ K čemu slouží hodiny (měření času), obecně ?
/ Stanovení času, ve kterém se událost vyskytla
J Stanovení trvání události nebo intervalu mezi 2 událostmi
/ Stanovení pořadí (časové posloupnosti) série událostí, ve kterém se tyto vyskytly
□ Kde všude při zpracování informací hraje čas důležitou roli ?
J Konzistentnost časových razítek v e-komerci
J Bezpečnostní algoritmy založené na časových razítkách (Kerberos)
J Určování pořadí řešení souběžných transakcí
/ Detekce uplynutí časových limitů, detekce uváznutí a stárnutí
J Řízení zámků souborů a zámků záznamů
J Plánování událostí a transakcí v čase
J Identikace posledních verzí souborů
/ desítky ?, stovky ? tisíce ? dalších důvodů
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 2
Časové poměry v počítači
Table 2.2 Example Time Scale of System Latencies
Event	Latency	Seated
1 CPU cycle	0.3 ns	1 s
Level 1 cache access	0.9 ns	3 s
Level 2 cache access	2+8 ns	9 s
Level 3 cache access	12.9 ns	43 s
Main memory access (DRAM, from CPU)	120 ns	6 min
Solid-state disk I/O (flash memory)	50-150 |js	2-6 days
Rotational disk I/O	1-10 ms	1-12 months
Internet: San Francisco to New York	40 ms	4 years
Internet: 5an Francisco to United Kingdom	81 ms	S years
Internet: San Francisco to Australia	183 ms	19 years
TCP packet retransmit	1-3 s	105-317 years
OS vi realization system reboot	4 $	423 years
SCSI command time-out	30 5	3 millennia
Hardware (HW) visualization system reboot	40 s	4 millennia
Physical system reboot	5 m	32 millennia
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 3
Cas v počítači, čas v síti (v DS)
□ Čas v počítači
/ V každém počítači v GHz třídě je rychlost světla (elmag signálu) (299 792 458 m/s) omezujícím faktorem
/ V 3GHz počítači se deset tiků hodin odehraje v čase, za který se světlo rozšíří na vzdálenost 1 mm
/ Jestliže se v jednom tiku se provede 1 operace,
musí se do příštího tiku získat data pro příští operaci
/ Registr CPU nemůže být dále od operační jednotky než 1/20 mm
□ Čas v síti
/ typický time-out síťových operací je 255 s
/ to odpovídá 3 bilionům (3 X 1012) operací soudobého CPU
/ pro srovnání 3 bilony sekund je cca 100 000 let
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 4
Problém řazení v čase, skluz, drift
/ Pro řazení událostí (nejen v DS) do časové posloupnosti musí platit pro všechny lokality univerzální standardní čas
J Lokální hodiny uzlů v DS jsou ale téměř jistě ve vzájemném skluzu
Síť
/ skluz, diference je okamžitá hodnota, v čase se mění - drift
J důvodem odlišnosti rychlostí běhu jednotlivých hodin od
,,skutečného"času je citlivost krystalového oscilátoru radiaci, teplotu, vibrace, věk, ...
J povolená diference běžných krystalem řízených hodin 10-6 s dává posun času o 1 s za 106 s (11 a půl dne)
J Vysoce přesné hodiny s povolenou diferencí 10-7 až 10-8 problém univerzálně neřeší
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 5
I AT, International Atomic Time , UTC, Universal Time, Coordinated
□ IAT - atomicky čas, extrémně přesný zdroj času
International Atomic Time - kmity v atomu Cesia 133, standardizovaná sekunda podle IAT = 9192 631 770 kmitů v atomu Cesia 133, drift 10"13
□ Sekundy, hodiny, roky ... (astronomický čas) se odvozují od
rotace země a rotace kolem slunce, tyto periody kolísají, astronomický a atomický čas mají tendenci se rozcházet
□ Universal Time, Coordinated, UTC
/ Korigovaný atomický čas na astronomický čas (občas se přidává ls) J Rozesílá se rádiově pozemními vysílači a satelity, komerční záležitost / Horší přesnost u koncových uživatelů času,
od zdroje UTC se rozesílaný čas pozemními
stanicemi může lišit až o 10 ms, satelitem (GPS) o cca 1 |xs
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 6
Synchronizace lokálních hodin reálného času
□ Nechť je t čas etalonových hodin (např. získaný UTC)
□ Doba přenosu od etalonu do lokálních hodin, ttrans
□ Cas synchronizovaných lokálních hodin, trecv = t + ttr a Urans bohužel neznáme, silně variuje
ans
Client
4 . *Ú
Time of day?
Server
2:50 PM + lil
2:50 PM
Time j
□ Procesy potřebují, aby byl trecv trvale udržovaný s přednastaveným stupněm přesnosti, tj. s definovanou tolerancí shody s t
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 7
Algoritmy synchronizace lokálních hodin s etalonem času
□ Cristianův algoritmus
□ Berkeley algoritmus, Berkeley Unix
□ NTP (Network Time Protocol), Internet
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 8
Cristianův algoritmus synchronizace hodin
□ DS obsahuje jistý počet důvěryhodných časových autorit,
časových serverů
□ Klient K se periodicky dotazuje časového serveru S na
hodnotu času zprávou mr
□ Server např. získává signály ze zdroje UTC, na požádání
sděluje hodnotu času podle svých hodin, t, zprávou mt
□ časový interval mezi vysláním požadavku a získáním hodnoty
času je doba obrátky, tround-triP
žádá o sdělení hodnoty času UTC
-D-1
■í
mt
sděluje hodnotu času, t Time server S
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 9
Cristianův algoritmus synchronizace hodin
j Cíl: Klient nastavuje čas Tz + Sl
Klient naměří round trip time Ô =
ôrsQ + 5resp = iT4 "      " (^3 " T2Í
Client
Server
Klient zná ď, nikoli ď,
resp
i Klient nastavuje čas 73 + VzS \
Time i
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 10
Cristianův algoritmus synchronizace hodin
□ pokud je tround-trip < A,
pak dobrá aproximace času u žadatele je trecv = t + y
□ pokud předpoklad neplatí, aproximace není věrohodná
□ jde o pravděpodobnostní algoritmus:
- tround-trip musí být dostatečně krátký, čím je menší A, tím je odhad přesnější
- čím větší přesnost se požaduje,
tím s menší pravděpodobností se dosahuje, protože často neplatí předpoklad dobré aproximace
□ výpadek serveru -
krach synchronizace, důsledek centralismu
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 11
Příklad
□ Klient se synchronizuje s časovým serverem zasíláním dotazů, dosažené doby obrátek zpráv a získané informace o čase jsou:
Roimd-trip (ms)	Time (hr:min:sec)
22	10:54:23.674
25	10:54:25.450
20	10:54:28.342
□ Na jaký čas by klient měl nastavit svoje hodiny ?
J minimální naměřená doba obrátky je 20 ms = 0,02 s
J klient by měl tudíž zvolit čas získaný s dobou obrátky 20 ms,
tudíž bude 10:54:28.342 + 0.02/2 = 10:54:28.352 s přesností ± 10 ms
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 12
Příklad, pokrač.
□ S jakou přesností je tento odhad správný je-li známo, že minimální čas mezi odesláním a příjmem zprávy v daném systému je 8 ms?
J Min, minimální doba přenosu zprávy = 8 ms
/ Když klient poslal dotaz v čase t,
server mohl odpovědět nejdříve za t + Min, a nejpozději za t + tround-trip — Min, tj. udaný čas je z rozpětí tround-trip — 2 x Min, takže přesnost je ±(tround-trip/2 — Min)
J Pokud se neznala doba Min, přesnost byla ±10 ms
J Když platí Min = 8 ms, bude přesnost za stejných podmínek dz2 ms (20/2 - 8)
/ Pokud se při Min = 8 ms požaduje přesnost nejvýše ±1 ms musí být nejvýše tround-trip = 18 ms (18/2 — 8)
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 13
Příklad, pokrač.
□ Čím větší přesnost se požaduje,
tím s menší pravděpodobností se dosáhne
/ tj. ideálně by mělo platit tround-trip = 2 X Min což je ve běžné síti málo pravděpodobné
□ Cristianův algoritmus je vhodný pro LANy
s dobře odhadnutelnou minimální dobou přenosu zpráv
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 14
Berkeley algoritmus synchronizace hodin
□ Jeden z počítačů DS je master, ostatní jsou slavě:
J Master uzel periodicky vyzývá každý slavě uzel k zaslání diference jeho času a změří příslušný tround-trip a
J ze zjištěných hodnot eliminuje (min, max) hodnoty, zbytek průměruje
J každému slavě uzlu zašle interval, o který se čas slavě uzlu liší od vypočteného průměru - udává de facto nový přesný čas
J Slavě uzly si zkorigují své lokální hodiny na nový přesný čas
□ Výpadek master uzlu lze ošetřit distribuovanou volbou
nového master uzlu
/ konkrétní algoritmus volby bude vysvětlený později
□ Konkrétní příklad (reálné měření)
/ LAN 15 uzlů, max tround—trip 10 ms; interval korekcí 25 ms, drift hodin slavě uzlů byl menší než 2 x 10-5 ms
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 15
Berkeley algoritmus synchronizace hodin
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 16
Algoritmus NTP, Network Time Protocol
□ Cristianův alg., Berkeley alg. jsou vhodné pro intranety
□ NTP, Network Time Protocol používá Internet, veřejná WAN
J Služba poskytující klientům v Internetu možnost se přesně synchronizovat s UTC (přesně = v intervalu řádově ms)
J PVhodné po zajištění spolehlivých služeb, které mohou přežít dlouhé ztráty konektivity - rekonfigurací po uplynutí time-outu
J Pro zajištění ochrany proti interferenci se zlomyslnou nebo náhodně chybující časovou službou
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 17
Algoritmus NTP, Network Time Protocol
□ Hierarchie NTP serverů
J hodiny serveru ve vrstvě 1 řídí signál UTC z vrstvy 0 J hodiny serverů ve vrstvě 2 se synchronizují s uzly vrstvy 1, J na úrovni listů jsou klientské stanice Synchronizační podsíť
			0
	■1		
T
3
N<
O
<
=3
O l/l
rekonfigurace při výpadku
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 18
Algoritmus NTP, Network Time Protocol
□ Způsoby synchronizace
J zprávy protokolů se zasílají protokolem UDP
J NTP Multicast Mode, jeden server rozesílá info o čase skupině serverů (multicast, vhodné pro LAN), málo přesná metoda
J NTP Procedure-Call Mode, časový server vrací časové razítko, na žádost, přesnější než NTP Multicast Mode, de facto Cristianův algoritmus
J NTP Symmetric Mode mezi 2 servery v různých úrovních, servery si opakovaně vyměňují zprávy s časovými razítky, opravují chyby
□ Dosahovaná minimalizace skluzu -
řádově desítky ms ve WAN řádově jednotky ms v LAN
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 19
Problém použití hodin pro synchronizaci v DS
□ Síťové hodiny lze synchronizovat s přesností nejvýše na
milisekundy
□ CPU provádějí biliony operací / s,
pro 3 GHZ CPU 1 ms = 3 000 000 operací
□ Mezi 2 hodinami, které mají být synchronizované,
je typicky prostor, ve kterém jedna CPU může provést milióny operaci, než druhá rozpozná stejné časové razítko
□ Časová razítka reálného času sama o sobě nejsou dostatečným
nástrojem pro řazení distribuovaných událostí
□ pro kooperující procesy důležité je pořadí, nikoliv přesný čas
□ nekooperující procesy nemusí být synchronizovány vůbec
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 20
Konfigurace, přechod, provedení
□ Globální stav DS daný stavem jeho procesů a zprávami
obsaženými v jeho kanálech je konfigurací DS
□ Konfigurace vzniká postupně, po krocích zvaných přechody
□ Systém přechodů sestává z
J množiny konfiguraci C
J binární relace přechodu —>• na C
J množiny iniciálních konfigurací I C. C
□ Konfigurace 7 g c je terminálni,
pokud neexistuje 7 —► S pro žádnou z S e C
□ Provedení algoritmu je posloupností konfigurací 707172 - -
kde 70 g I a ji —►      pro všechna i > 0
□ Konfigurace S je dosažitelná pokud 707172 - - - ik = S,
kde 70 g I a ji —►      pro všechna 0 < i < k
\ Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí    21 J
Události
□ Každý přechod v DS je vázaný na jistou událost
v některém z procesů DS
/ V případě synchronních DS na dvě události ve dvou procesech DS
□ Proces může generovat
vnitřní událost, událost vyslání zprávy a událost příjmu zprávy
□ Proces je iniciátor, pokud jeho první událostí je vnitřní
událost nebo vyslání zprávy
/ DA je centralizovaný, pokud existuje právě jeden iniciátor J Decentralizovaný DA může mít více iniciátorů
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 22
Příčinné pořadí Mstalo-se-před"
□ Příčinné pořadí a -< b výskytů událostí a a b v provedení DA
je nej menší tranzitivní relace taková, že platí
/ a a b události ve stejném procesu a a se vyskytla dříve než b nebo / a je událost vyslání zprávy a b je událost přijetí této zprávy
□ Pokud neplatí ani a ■< b ani b ■< a jsou události a a b souběžné
□ Permutace událostí, která respektuje příčinné pořadí,
výsledek provedení DA neovlivní
/ Takovou permutaci nazýváme výpočtem
/ Všechna konečná provedení výpočtu startující ve stejné konfiguraci končí v téže terminálni konfiguraci
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 23
Fyzické hodiny synchronizaci procesu neumožňují
□ Odlišnost driftů lokálních hodin v uzlech DS znemožňuje
použít pro řazení událostí fyzický čas
□ Idea řešení problému - (Lamport 1978)
sledovat vztah stalo-se-před místo fyzického času
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 24
Řazení událostí v distribusledovatovaném prostředí
□ Logický čas je budován na bázi relace stalo-se-před, značené -+
/ Jsou-li a a b (vnitřní) události ve stejném procesu a a se stala dříve než b, pak platí a^b
S Je-li a událost zaslání zprávy jedním procesem
a b je událost přijetí této zprávy v jiném procesu, pak platí a^b
S Jestliže platí a^b a b^c, pak platí a-^c
1. If same process and a occurs before b, then a -> b
2. If c is a message receipt of b, then b c
3. If a    b and b    c, then a c
4. a, d not related by -> so concurrent, written as a || d
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí
25
Implementace relace    běh logického času
□ S každou událostí v systému se sváže časové razítko,
TS (time stamp)
□ V každém procesu Pí udržují běh logického času
logické (Lamportovy) hodiny d
S mapují výskyt událostí ve výpočtu do částečné uspořádané množiny, ve které platí a —>• b =>* C (a) < C (b)
J logické hodiny lze implementovat např. jako čítač inkrementovaný před každou událostí v procesu, C{ = C{ + 1,
/ vysílanou zprávu proces doplní čas. razítkem, TSzpravy = C i
S při příjmu zprávy přijímající proces
nejprve nastaví na C{ — max (Ci , TSzpravy) a poté čítač času inkrementuje a poté se mu zpráva zpřístupní
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 26
Ilustrace běhu logického času
Pí
©
Pz
ft
Logical time
Physical time
□ a —6, 6 —c, c —^ d, d^f,b^g,g^h, f h
□ a -» e a e -» a, píšeme a n e, a a e jsou souběžné události
□ e m b, logický čas e < logický čas b, ale neplatí e —► b
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 27
Implementace relace    běh logického času
J Iniciálně má každý proces nulový logický čas
■ Each process PF maintains a local clock
■ Before executing an event, Ct <- Ct + 1
■ On process P, receiving a message m:
- Set C      receive event time C(c) <-1 + max{ C;, C(m)}
P1		P2
C,=2		Cj—3
/ Pro každý pár událostí A a B propojených posloupností událostí (události uskutečněné v jednom procesu nebo vyslání a příjem zprávy), pro který platí A     B, platí T S (A) < T S (B)
/ Pozor, z TS(A) < T S (B) neplyne A B Lamportova časová razítka nezachycují kauzalitu
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 28
Problém kauzality Lamportovy hodiny
P1
P2
P3
: Odmítnout ukázaní Reply dokud nepřijde Post
Time ->
* Lze odmítnout ukázání zprávy s C(message) > local clock + 1?
• Nikoli, mezery mohou být způsobeny nezávislými vysíláními,.
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 29
Příklad
□ V procesech pi,p2,P3 došlo k následujícím událostem
/ Pi : a, si,     b (událost a, vyslání zprávy 1, príjem zprávy 3, ud. b)
P2 : c, r2, «3 p3 : n, d, s2,e
□ Tyto události se vyskytly v logických časech
/ Pi : l(a),2(5l), 8(r3),9(6)
P2 : l(c), 6(r2),7(s3) p3 : 3(ri),4(d),5(s2),6(e)
□ C přiřazují každé události a délku fc nej delšího příčinného
řetězce ai —>- ... —>> a& = a
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 30
Totální uspořádání logického času
□ Dvě různé události generované ve dvou různých procesech
mohou mít identické Lamportovo časové razítko, C
□ např. žádosti o vstup do kritické sekce z více procesů,
všechny mají stejnou hodnotou C
□ spravedlivost při řešení vstupu do kritické sekce může
požadovat totální uspořádání hodnot C v celém DS
□ pak lze do časového razítka C doplnit např. id procesu a
časová razítka se shodnou hodnotou času uspořádat dle pořadí id procesů
/ id procesů musí být jedinečné a řadové, např. integer, hodnoty
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 31
Vektorové časové razítko
□ Nedostatkem (skalárního) Lamportova TS je, že
z TS(A) < T S (B) neplyne A B Lamportova časová razítka nezachycují kauzalitu
□ Toto omezení lze řešit ve skupině N procesů tím, že místo
skalárního (Lamportova) časového razítka TS, použijeme vektorové časové razítko V
S Každý proces pi si udržuje svoje vlastní vektorové razítko Ví
S Vektorové časové razítko procesu pi, tj. Ví, má tolik prvků kolik je procesů ve skupině
/ Iniciálně jsou v pi všechny prvky Ví nulové, Ví = (0, 0,...)
/ Vi[i]: logické hodiny pi, počet událostí, které se dosud nastaly v pi
S Před tím než pi vyšle zprávu m procesu p j nastaví Vi[i] := Vi[i] + 1 (událost vyslání zprávy časově orazítkuje)
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 32
Vektorové časové razítko
/ Vi[j] reprezentuje znalost logického času p j v pi, tu pi získává
z vektorového razítka připojovaného vysílačem p j ke zprávě přijaté pi
S když p j získá ve zprávě od pi časové razítko Vi,
ve svém Vj nastaví Vj[i] := max (V} [i], Vi[i]) pro i = 1, 2,... AT"
/ Poněvadž pi před vysláním zprávy inkrementoval Vi [i] a
p j inkrementuje Vj[i] pouze když dostane od pí časové razítko s větší hodnotou pro pi, platí Vj[i] < Vi[i]
S Ve vektorovém časovém razítku Vj je Vj [j] počet událostí orazítkovaných p j a
Vj[i] pro i ^ j počet událostí v p^, které příp. ovlivnily pj,
J Když událost a označíme razítkem V, každý prvek V je
čítačem událostí v jednom procesu, které kauzálně předcházejí a
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 33
Vektorové časové razítko
S Pro porovnaní vektorových časových razítek platí pravidla
V = V iff V\j] = V'[j] f or j = 1, 2,,... AT VKV'iff V[j] < V'[j] f or j = 1, 2,,... N
V < V iff V < V A 3j : V[j] < V'[j]
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 34
Vektorové časové razítko
□ Lze ukázat, že pokud o událostech a, b platí a —► b, např. a je vyslání zprávy a 6 je přijetí této zprávy pak platí V (a) < V(b)
S přijímač inkrementuje svůj čas ve V a všechny ostatní položky ve V zůstanou přinejmenším stejně velké jako ty v časovém razítku odesílatele, tedy V {a) < V(b)
S Pokud platí V (a) < V (z), pak mezi a a z existuje řetěz událostí svázaných relací „stalo se před"
/ Ze znalosti C (a) < C (z) nelze odvodit žádný závěr
/ Jsou-li události a a 6 souběžné, pak neplatí ani V (a) < V (b) ani
V (b) < V (a) a tudíž pokud události a a 6 nejsou souběžné, pak platí
iff V (a) < V(b) =^ a^b
íffV(b) < V (a) ^b^ a S Vektorové razítko vypovídá o kauzalitě vztahu událostí
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 35
Lamportovo časové razítko
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 36
Vektorové časové razítko
/   V (á) < V (f) ^ a ^ /
/ c m e, neplatí ani V (c) < V (e) ani V (é) < V (c)
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 37
lamportovo a vektorové razítko
Lamportovo
P1 C,=2		P2	
	C(a) = 1		
c(b) =
Vektorové
eó[0,o,i]
[2,2,2]
/ je-li V (a) < V(d) pak existuje řetěz událostí vázaných relací stalo-se-před mezi a a d
J mezi nezávislými událostmi neexistuje řetěz událostí vázaných relací stalo-se-před
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 38
Aplikace vektorového razítka
VC0=(020,0)  VC0-(1,0,0)
VC0-(1,1,0) (1,0,0) x (1,1,0)
Originály post
zpráva od P- je předána P:„ nečeká na žádnou událost
(0,0,0) x (1,0,0)
VC,=(0.0,0)
VC2=(0,0,0)
zpráva Dd P0Je předána P;
nečeká na žádnou událost
VC2= (1,1,0)
' P2 získává zprávu
(0,0,0) x (1,0,0)    VC2= (0,0,0)     VCa= (1,0,0) zf™ty
(0,0,0) x (1,1,0)
zpráva od P, je dána do fronty protože P2 m jsí dostat zprávu od P0
zpráva odP0je předána P, Pí nečeká na žádnou událost
Physical time ->
User 0 posts, user 1 replies to O's post; user 2 observes
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 39
Složitost výpočtu distribuovaných algoritmu
Mirou složitosti může být
□ Počet vymenovaných zpráv, budeme používat nejvíce
□ Bitová složitost
/ počet vyměňovaných bitů zprávami
J ma smysl pouze v případech velmi dlouhých zpráv
□ Časová složitost - předpoklady:
/ doba zpracování zprávy v komponentě DS je obv. zanedbatelná / zaslání zprávy spotřebuje alespoň 1 časovou jednotku
□ Vesměs nás zajímá nej horší případ a průměrný případ výpočtu
□ O-notace: Pokud ve výpočtu participuje n procesů a nej horší
provedení výpočtu má kvadratickou složitost počtu zpráv, 0(n2), pak se při tomto provedení vymění řádově n2 zpráv
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 40
Model pro studium distribuovaných algoritmu
□ Distribuovaný algoritmus DA realizuje v DS,
ve kterém participuje n > 1 procesu
□ Každý proces Pi běží na obecně na jiném uzlu sítě (procesoru)
/ běží = provádí posloupnosti událostí, např.
lokální výpočet —>• zaslání zprávy —>• přijetí zprávy
□ Pro jednoduchost vyjádření algoritmů v celé přednášce platí
1 uzel = 1 proces, uzel a proces jsou synonyma
□ Pokud se neřekne jinak, pak procesy jsou z hlediska logiky
řízení aplikace DS vzájemně rovnocenné, platí symetrie
□ V některých variantách DA procesy mohou mít asymetrické
postavení z hlediska logiky řízení aplikace (např. model klienti-server)
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 41
Model pro studium distribuovaných algoritmu
□ Zprávy vyslané jedním procesem jinému procesu jsou
a) přijímané v pořadí jejich vysílání,
b) doručované silně souvislou komunikační sítí,
tj. každý proces může komunikovat s každým procesem
(platnost podmínek a) + b) odpovídá protokolu TCP)
c) doručené v konečném čase
o rychlosti jednotlivých komunikačních kanálů nelze vyslovit žádný jiný předpoklad
□ Pokud neřekneme jinak, nedochází k výpadkům ani
komunikačních kanálů ani uzlů
/ Varianty distribuovaných algoritmů v prostředí s poruchami (výpadky) budeme studovat samostatně
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 42
Požadované vlastnosti distribuovaných algoritmu
□ Bezpečnost, Safety, Nothing bad happened yet
/ Sledovaná podmínka, cíl:
Z globálního stavu DS (stav všech procesu tvořících DS) je normálními (validními) stavovými přechody nedosažitelný jistý nežádoucí stav
/ Např. dosahuje se vzájemné vyloučení kritických sekcí procesů, zabraňuje se uváznutí procesů, ...
/ Typicky se dokazuje indukcí: jestliže X platí pro n = 1 a jestliže X platí pro n = m a pro n = m + 1, pak X platí pro všechna n
J Narušení bezpečnosti (tj. narušení dosažitelnosti cíle algoritmu) se prokazuje v konečném počtu kroků řešení
J Řešení problému nenarušující bezpečnost je korektní řešení
Podmínka bezpečnosti musí být splněná v každé konfiguraci každého provedení algoritmu, jedná se o invariant
Předpoklad P je invariantem, pokud platí P(7) pro všechny 7 G I a jestliže 7 —>- S, pak platí i P(S).
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 43
Požadované vlastnosti distribuovaných algoritmu
□ Živost, Liveness, Something good eventually happens
/ Vlastnost globálního stavu D S zajišťující, že
jistou posloupností normálních (validních) stavových prechodu je dosažitelný jistý, konkrétní žádoucí stav
J Např. v konečném počtu kroků algoritmu se zvolí vedoucí uzel v síti nebo proces žádají o vstup do kritické cesty získá právo vstoupit do kritické sekce v konečném čase
J Narušení podmínky živosti se prokazuje pouze v nekonečném počtu kroků řešení
J Korektní řešení problému (splňující podmínku bezpečnosti) nenarušující živost je úplné, kompletní řešení
J Podmínka živosti musí být splněná alespoň v jedné konfiguraci každého provedení algoritmu
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 44
Problém znalosti globálního stavu v DS
□ Platí jistá vlastnost v DS ? Detekce globální vlastnosti, např.
/ Je jistý objekt dále už nepoužívaný ?
(lze na něj aplikovat garbage collection, nikdo na něj neodkazuje) J Došlo k uváznutí ?
J Došlo k ukončení distribuovaného algoritmu ?
J Nestačí znát stav procesů, musí se znát i stav komunikačních kanálů
a. Garbage
collection object
reference
b. Deadlock
c. Termination
Nestačí znalost stavu uzlů, je nutné znát i stav komunikačních kanálů
garbage object
procesy vzájemně čekají na zprávu jeden od druhého
Všechny procesy sdělí na dotaz,
0že jsou pasivní. P1 po přijetí aktivační zprávy se stane znovu aktivní, ač již sdělil, že je pasivní
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 45
Budovaní globálního stavu DS, momentka
□ Jak odvodit globální stav kolekce procesu v asynchronním DS
ze znalosti lokálních stavů uzlů pořízených výměnou zpráv v různých okamžicích běhu času ?
□ Momentka (snapshoť) provádění jistého DA poskytuje
informaci o některé konfiguraci provádění výpočtu v DS
/ Momentku potřebujeme pro restart výpočtu po výpadku J Momentka umožní provést detekci uváznutí / Momentka usnadňuje ladění výpočtu
□ Přirozeně je žádoucí získat momentku bez zastavení výpočtu
/ Při výpočtu pak rozlišujeme
- základní zprávy řešící vlastní DA a
- řídicí zprávy získávající momentku
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 46
Budovaní globálního stavu DS, momentka, konzistentní řez
□ Momentka výpočtu podle DA v DS sestává
J z lokálních momentek stavu každého procesu a
J ze stavů kanálů všech kanálů v DS (výčet zpráv obsažených v kanálech)
□ Momentka výpočtu dle DA v DS je smysluplná, konzistentní,
pokud úplně popisuje některou konfigurací provádění DA
□ V časovém diagramu běhu procesů v DS můžeme vytvořit řez
rozdělující běh výpočtu na minulost a budoucnost vůči vztažnému bodu definovanému řezem (na události vyskytnuvší se v minulosti a na události, které teprve nastanou)
□ Konzistentní řez odpovídá konzistentnímu stavu,
ve kterém každá zpráva přijatá v minulosti dané konzistentním řezem byla rovněž v minulosti vyslaná
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 47
Problém znalosti globálního stavu v DS
/ Momentky výpočtu podle DA v DS se musí vytvářet v konzistentních řezech časových běhů procesů v DS
/ Jestliže proces pi poslal zprávu rriij procesu p j po zaznamenáním momentky svého lokálního stavu, musí proces p j vytvářet momentku svého stavu před zpracováním
P1P2
tíme
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 48
Global State Recording Algorithm, GSRA
□ V jakém stavu se se nachází systém N procesů v DS ?
□ Dovedeme to zjistit ?
J V distribuovaném systému, ve kterém neexistuje ani sdílená paměť ani systémové hodiny,
je určování okamžitého globálního stavu obtížně řešitelné.
J Jestli bude finanční systém tvořený milionem bank, které si sítí předávají 1 CZK, pak prostý dotaz postupně posílaný bankám může zjistit, že ve finančním systému není žádná CZK i že je jich tam milion
□ Proč potřebujeme znát globální stav systému N procesů v DS ?
J Pro detekci konce činnosti systému procesů v DS řešících distribuovanou aplikaci, pro detekci uváznutí procesů v DS sdílejících zdroje, při vytváření kontrolního bodu pro návrat při obnově, ...
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 49
GSRA, konzistentní řez stavu, konzistentní stav
□ Řez C je konzistentní, když platí (a g C) n (b -< a) => b g C
Konzistení řez Cut 1 Cut 2   Nekonzistentní řez
□ Zjištěný stav (snapshot) je konzistentní, pokud ho formují
události náležející konzistentnímu řezu
□ Pokud Cl -< C2, pak je C2 novější stav
/ Nás prakticky zajímá nej novější stav
/ Stav musí být zjistitelný „za pochodu", neinvazivně
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 50
Algoritmus zjištění globálního stavu DS, Chandy & Lamport
□ Model DS tvořeného N procesy
J Procesy a komunikační kanály nevypadávají,
každá vyslaná zpráva dorazí k příjemci neporušená a právě jednou
J Komunikační kanály jsou jednosměrné, pracují v režimu FIFO, každý proces může komunikovat s každým procesem, graf sítě je silně souvislý, mezi každými dvěma procesy PQ existují dva takové kanály, channel (P,Q) a channel (Q,P)
J Zjišťování globálního stavu může spustit kterýkoliv proces kdykoliv
/ Zjišťování globálního stavu nenarušuje běh procesů z pohledu aplikace
/ Každý proces je schopný zaznamenat svůj stav a
stav každého svého vstupního kanálu (co mu přišlo a dosud zpracoval)
pokud proces pi poslal zprávu procesu pj a p j ji dosud nepřevzal, pak rriij náleží stavu vstupního kanálu pi —>• p j
(taková zpráva je např. přijata službou OS, ale dosud nebyla doručena službou middleware aplikačnímu procesu)
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 51
Konstrukce momentky stavu DS, příklad 1
Process P:
Process Q:
P 0 ©	-\ channel(P, Q) ) z1--í cŕiannel(Q, P)	Q ©O • ©
■   r,nrresrt qlohal snapshot = j		
Exactly one of each token
Chybné momentky, zachycují pouze stav procesů, nikoli i stav kanálů
P. Q put tokens into channels, then snapshot
[ This snapshot misses Y, B, and O tokens j
P snapshots, then sends Y Q receives Y, then snapshots
This snapshot duplicates the Y token
©
© ©
Q
O
p		Q *0©O ® ©
1 f v ]		
t Y	A V	
	c	
	N	
P = {G}
Q = {R,P}
P = {G,Y}
Q = {Y,R, P,B,0}
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 52
Idea validního řešení momentky
□ Musí se zachytávat rovněž stav kanálů
□ Pro sledování stavu kanálů se bude vysílat
řídicí zpráva marker
□ Proces zaznamená svůj lokální stav
A
do každého svého výstupního kanálu vyšle marker
□ Každý proces si pamatuje,
zda už momentku svého lokálního stavu udělal
□ Pokud proces do přijetí markem momentku dosud nevytvořil,
udělá ji a zaznamená svůj lokální stav A do každého svého výstupního kanálu vyšle marker
V Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí    53 J
Konstrukce momentky stavu DS, příklad 2
' P snaps riots and sends marker, then sends Y
• Send Rule: Send marker on all outgoing channels
- Immediately after snapshot
- Before sending any further messages
©
V
®
o
snap: P = { G, Y>
■ At ihe same time, Q sends orange token O * Then, Q receives marker A
' Receive Rule (If not yet snapshotted)
- On receiving marker on channel c record ds state as empty
channcl(P,Q) = { }
Q = { R, P, B )
Valí dní momentky,
zachycují stav procesů, i stav kanálu
Q sends marker to P
P receives orange token 0. then marker A
Receive Rule (if already snapshotted):
- On receiving marker on e record cs state: all msgs from c since snapshot
channel(P,Q) =()
P = { G, Y }   channel(Qp) " í 0 J Q = < R, p, B }
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 54
Algoritmus určení globálního stavu DS, Chandy & Lamport
□ Proces iniciující zjištění globálního stavu - iniciátor
J zaznamená momentku svého lokálního stavu a pošle řídicí zprávu, marker, po svých výstupních kanálech všem svým sousedům v DS
□ Když marker získá proces,
který dosud nevypracoval momentku svého lokální stavu
J zaznamená momentku svého lokálního stavu a pošle ji iniciátorovi
J vstupní kanál ze kterého získal marker označí jako prázdný a pošle marker svým sousedům svými výstupními kanály
□ Když marker získá proces,
který už vypracoval momentku svého lokální stavu
J zaznamená stav vstupního kanálu, ze kterého dříve získal marker stav = všechny zprávy od posledního záznamu svého stavu do přijetí markeru a pošle ho iniciátorovi
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 55
Algoritmus určení globálního stavu DS, Chandy & Lamport
□ Iniciátor sestaví globální momentku stavu DS jakmile
zná lokálni momentky stavů všech procesů a zprávy, které byly uloženy „v etéru", nezpracované, v kanálech
□ Kanály jsou FIFO, globální momentka je smysluplná
□ Marker v kanálech odděluje zprávy na ty,
které jsou zahrnuté do momentky lokálního stavu od těch, které do něj zahrnované nejsou
□ Složitost algoritmu odpovídá
zaslání O(e) zpráv a O(d) času,
kde e je počet hran v grafu sítě a d je průměr sítě
□ Algoritmus je užitečný pro detekci platnosti
stabilní podmínky (ukončení, uváznutí, ...)
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 56
GSRA, příklad aplikace algoritmu Chandy-Lamport
Snapshot/State Recording Example
500
GS
Finanční systém tvorí 3 banky p, q a r.
Na počátku j c v každč bance 500 $, lokální stav každého uzlu je 500 $.
V bankovním systému je 1 500 $.
Žádná banka není iniciátorem GSRA, nikdo nepotřebuje znát globální stav, tj„ zda je zachováno integrit ní omezení, že ve finančním systému se nachází 1500 $
Node	Recorded State				
	state	cl	c2	c3	c4
P			{}		
q		{}			
r				0	
Jednotlivé řádky tabulky C S udržuje banka - iniciátor CSRA,
Ostatní (uzly) banky zasílají i ni c iá tort] vi lokálni momentky svých stavů a stavy svých vstupních kanálů.
Jakmile iniciátor bude znát všechny momentky, rozpozná ukončení GSRA,
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 57
GSRA, příklad aplikace algoritmu Chandy-Lamport
Snapshcť/State Recording Example (Step 1)
Banka p posílá kanálem cl 10 $ bance q a 470   spouští GSRA:
Zaznamenává svou lokální momentku okamžitého stavu (500 - 10 = 490 $) a do kanálu cl vysílá značku (M, Marker),
Současně banka q posílá
20 $ bance p kanálem c2 a 10 $ bance r kanálem c3 lokální stav banky q je 500 - 20 - 10 = 470 $
Tyto převody dosud do p a r nedorazily, jsou součástí stavu kanálů c2 a c3,
Node	Recorded Stale				
	state	cl			c4
P			0		0
q		{}			
r				0	
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 58
GSRA, příklad aplikace algoritmu Chandy-Lamport
Snapshot/State Recording Example (Step 2)
490
480
Ranka q získala prevod 10 $, zvýšila svůj stav z 470 $ na 480 $, a poté získala z kanálu cl značku.
Protože banka q získala značku,
zaznamenala lokálni momentku svého stavu 480 $
a vyslala značky na své použité
výstupní kanály c2 a c3.
Současně banka r převádí bance p 25 $ po kanálu c4. Její lokální stav je 500 - 25 = 475 $. Nezáleží na tom, jestli r udělala převod před tím nebo poté co q získala značku
Node	Recorded State				
	state	cl	c2	c3	c4
P	490		0		{}
q	480	{}			
r				{}	
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 59
GSRA, příklad aplikace algoritmu Chandy-Lamport
Snapshot/State Recorditig Example (Step 3)
Banka r získává kanálem c3 převod 10 $ a značku,
zvyšuje stav z 475 $ na 485 $ a zaznamenává lokální momentku tohoto stavu. Poté vysílá značku na svůj použitý výstupní kanál c4.
Mezitím banka p posílá dalších 20 $ kanálem cl bance q. Stav banky p klesá na 490 - 20 = 470 $.
4SÍ
Node	Recorded State				
	state	cl	c2	c3	c4
P	490		{}		{}
q	480	{}			
r	485			{}	
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 60
GSRA, příklad aplikace algoritmu Chandy-Lamport
Snapshot/State Recording Example (Step 4)
Banka q získává kanálem cl převod 20 $ zvyšuje svůj stav na 500 $,
Banka q nemění svoji
lokální momentku stavu,
změna stavu se stala po příjmu značky.
Také banka p získává převod 20 $ kanálem c2. Banka p zaznamená převod 20 S pouze jako část svého zaznamenaného stavu kanálu c2. jakmile získá z tohoto kanálu marker
Node	Recorded State				
	state	cl	c2	c3	c4
P	4'JII		{20}		í)
q	4SII	{}			
r	485			O	
Jan Staudek, FI MU Brno I PA150 - Čas a stav v distribuovaném prostředí 61
GSRA, příklad aplikace algoritmu Chandy-Lamport
Snapshot/State Recording Example (Step 5)
515
Node	Recorded State				
	state	cl	c2	c3	c4
P	490		{20}		{25}
H	480	O			
r	485			{}	
Banka p získava kanálem c4 prevod 25 $ zvyšuje svoji hodnotu na 515 $.
Když banka p získá značku z kanálu c4, je zaznamenávání lokálních momentek hotovo, všechny banky získaly značku na vsecli svých vstupních kanálech.
Tabulka ilustruje v jednotlivých rádcích finálně zaznamenané lokální momentky. Řádky tabulky mohou jednotlivé procesy posílat iniciátorovi napr. na vyžádání iniciátorem.
Globální stav systému zjišťovaný bankou p 490 + 20 +25 + 480 + 0 + 485 + 0 = 1500 $, lokální momentky stavn uzlů říkají 1455 $, stavy kanálů říkají, že 45 $ je v „etéru".
Jan Staudek, FI MU Brno    PA150 - Čas a stav v distribuovaném prostředí 62