PA160
Synchronizace Casu
vr
Cas na jednom uzlu
Hodiny resp. časovač (timer)
■ Oscilující krystal křiStálu Čítač
* Každá oscilace sníží hodnotu o jedna
* Přerusení při hodnote nula
Každe prerusení je tik
■ Holding register
* Iniciace cítace po prerusení
■ Po přerusení žvysen uloženy cas
PA160
2
Jaro 2010
Distribuované počítače
■ Každý uzel má vlastní časovači
v
■ Cas není automatický sýnchronizovan
■ Casove pokřivení (clock skew)
■ Vazba na absolutní realný cas
■ Problemý
■ Vzajemna sýnchronizace uzlU
■ Sýnchronizace s realným casem
PA160
3
Jaro 2010
Absolutní čas
■ Původní definice časové jednotky
■ 1 sekunda je 1/86400 slunečního dne
■ Aktůainí-atomove hodiny
■ Přechody Cesia 133
■ 1 sekunda je doba za niž probehne 9 192 631 770 přechodů
■ Mezinarodní atomový čas
■ Průmer meření cca 50 svetových laboratoří
PA160
4
Jaro 2010
Universal Coordinated Time, UTC
■ Atomový a sluneční čas se rozcházejí
■ Skoková sekunda
■ Kompenzace rozchodu s rotací Zeme
■ Pridana kdýz rozdíl mezi slunecním a atomových casem vzroste na 800 ms
■ Výsledný cas je Univerzalní koordinovaný cas (Universal Coordinated Time, UTC)
■ Nahradil GMT
■ UTC dostupne celosvetove
PA160 5 Jaro 2010
Synchronizace hodin
■ Základní východiska
■ Množina uzlů s vlastními hodinami
■ PreruSení H krat za sekundu
■ Cp(t) je Cas meéřený hodinami na stroji p
■ Idealne Cp(t) = t pro vsechna p
■ Realita: Pokud existuje p takove, že platí
dC dt
pak hodiný Cp pracují se specifikací p.
■ p definovano výrobcem (Maximalní rychlost posunu casu)
■ Chceme-li, abý se hodiný rozeslý nejvýse o ô, musíme je synchronizovat nejmene kazdých ô/2p sekund
PA160 6 Jaro 2010
Cristianuv algoritmus
■ Máme časový server
■ Nejlépe napojený na absolutní čas
■ Každých 6/2p posílá káždý uzel dotaz serveru
■ Server odpoví (jak nejrychleji mUže) s vlastním (UTC) časem
■ Naivní řesení: Uzel zmení svUj čas
PA160
7
Jaro 2010
Problémy
■ Podstatný - reakce na zpoždění
■ Čas přestane mít lineární průběh
* NeCekane a neZadoůcí efektý
* Čas nemůže bežet „pozpatků"
■ Resení
* Snížení absolutního Casů na přerůsení
* „Zastavíme" Cas
■ Malý - doba komůnikace
■ Zmeř Cas mezi zaslaním (T0) a přijetím (Ti) požadavků
■ PriCti Cas přenosů (T0 + T1)/2
■ Možno jestee zapoCítat Cas zpraCovaní na serverů (je-li znam)
PA160 8 Jaro 2010
Berkeley algoritmus
Aktivní časový server
■ Periodický se dotazuje uzlů na jejičh absolutní čas
■ Spočíta průmerný čas podle časů uzlů
■ Posle vsem tento nový čas
Vhodne pokud sever nema absolutní čas
■ Obdoba UTC - čas, na nemZ se uzlý shodnou
PA160
9
Jaro 2010
Decentralizovaná řeSení
■ Resýnchronizační intervaly
■ Globalne dohodnutý „počatek" T0
■ i-tý interval začína v čase T0 + iR
■ i-tý interval končí v čase T0 + (i + 1)R
■ R je dohodnutý sýstemový parametr
■ Vsičhni poslou broadčast se svým časem na začatku kazdeho intervalu
■ Zpračovaní na uzlu
■ Dojde S zprav
■ Spočíta se prumer (s výloučením m odlehlýčh hodnot)
■ Mozne zlepsení při znalosti dobý propagače zprav
PA160 10 Jaro 2010
NTP protokol
■ Network Time Protocol
■ NTP version 3 (RFC1305), version 2 (RFC1119), version 1 (RFC1059)
■ S(imple)NTP: RFC1769
■ Hierarchická organizace
■ Stratum 1 přímo napojene na absolutní Cas
■ Celkem aZ 16 Úrovní (Stratum 16)
■ Vysoce skalovatelne
■ Více jak jeden server
■ MoZna reakce na výpadek ci ztratu přesnosti
■ Servery tik.cesnet.cz a tak.cesnet.cz
PA160 11 Jaro 2010
Logický čas
■ Absolutní cas není vždy duležity
■ Podstatny relativní cas (souvislost deju)
■ Logický čas
■ Nevyžaduje absolutní synchronižaci
■ Potřeba shody na usporadaní
PA160
12
Jaro 2010
Lamportovy časové známky
■ Relace „událo se dříve" (happens-before)
■ a — b znamená, že se vSechny procesy dohodly, že a nastalo dříve než b.
■ SouCasne platí, že pokud a je udalost zaslaní konkretní zpravy a b je udalost přijetí teze zpravy, pak nutne a — b
■ Vlastnosti
a — b je tranzitivní ■ Udalosti x a y jsou souběžné (concurrent), pokud neplatí ani x — y ani
y — x
PA160
13
Jaro 2010
Realizace
■ Kazdy proces ma vlastní logicke hodiny
■ Pro udalosti ůvnitr jednoho procesů je zajisteení relace ,,ůdaio se před'' trivialní
■ Synchronizace mezi procesy probíha jako soůcast zasílaní zprav
■ Kazda zprava obsahůje casovoů znamků odesílatele (Ts)
■ Pokůd je cas prijímajícího (Tr) mensí (mladsí) nez casova znamka v přijímane zprave, nastaví se Tr = Ts + 1
■ Dodatecna podmínka
■ Zadne dve ůdalosti nenastanoů ve stejny cas
PA160
14
Jaro 2010
Shrnutí
■ Lamportův algoritmus umožňuje zajistit globální (logický) čas v distribuovaném sýstemu
■ Vlastnosti
■ Pokud a nastane pred b ve stejném procesu, C (a) < C (b)
■ Pokud je a zaslaní a b přijetí teže zpravý, C (a) < C (b)
■ Pro vsechný ruzne udalosti a a b platí C (a) = C (b)
■ Algoritmus umoznuje globalní uspořadaní udalostí v distribuovanem sýstemu
PA160
15
Jaro 2010