PA160
Synchronizace času
Čas na jednom uzlu
■ Hodiny resp. časovač (timer)
■ Oscilující krystal křištálu - Čítač
* Každá oscilace sníží hodnotu o jedna
* Přerušení při hodnotě nula
Každé přerušení je tik
■ Holding register
* Iniciace čítače po přerušení
■ Po přerušení zvýšen uložený čas
PA160 2 Jaro 2006
Vícenásobní procesory
■ Každý uzel má vlastní časovač
■ Čas není automaticky synchronizován
■ Časové pokřivení (clock skew)
■ Vazba na absolutní reálný čas
■ Problémy
■ Vzájemná synchronizace uzlů
■ Synchronizace s reálným časem
PA160
3
Jaro 2006
Absolutní čas
■ Původní definice časové jednotky
■ 1 sekunda je 1/86400 slunečního dne
■ Aktuální - atomové hodiny
■ Přechody Cesia 133
■ 1 sekunda je doba za niž proběhne 9192 631 770 přechodů
■ Mezinárodní atomový čas
■ Průměr měření cca 50 světových laboratoří
PA160
4
Jaro 2006
Universal Coordinated Time, UTC
Atomový a sluneční čas se rozcházejí Skoková sekunda
■ Kompenzace rozchodu s rotací Země
■ Přidána když rozdíl mezi slunečním a atomových časem vzroste na 800 ms
Výsledný čas je Univerzální koordinovaný čas (Universal Coordinated Time, UTC)
■ Nahradil GMT
UTC dostupné celosvětově
60 5 Jaro 2006
Synchronizace hodin
Základní východiska
■ Množina uzlů s vlastními hodinami
■ Přerušení H krát za sekundu
Cp(t) je čas měřený hodinami na stroji p
■ Ideálně Cp{ť) = t pro všechna p
■ Realita: Pokud existuje p takové, že platí
dC
i-P^Si + P
pak hodiny Cp pracují se specifikací p.
■ p definováno výrobcem (Maximální rychlost posunu času)
■ Chceme-li, aby se hodiny rozešly nejvýše o S, musíme je synchronizovat nejméně každých S/2p sekund
60 6 Jaro 2006
Cristianův algoritmus
■ Máme časový server
■ Nejlépe napojený na absolutní čas
■ Každých 6/2p posílá každý uzel dotaz serveru
■ Server odpoví (jak nejrychleji může) s vlastním (UTC) časem
■ Naivní řešení: Uzel změní svůj čas
PA160
7
Jaro 2006
Problémy
■ Podstatný - reakce na zpoždění
■ Čas přestane mít lineární průběh
* Nečekané a nežádoucí efekty
■ Řešení
* Snížení absolutního času na přerušení
■ Malý - doba komunikace
■ Změř čas mezi zasláním (T0) a přijetím (Ti) požadavku
■ Přičti čas přenosu (T0 + 2i)/2
■ Možno ještě započítat čas zpracování na serveru (je-li znám)
PA160 8 Jaro 2006
Berkeley algoritmus
■ Aktivní časový server
■ Periodicky se dotazuje uzlů na jejich absolutní čas
■ Spočítá průměrný čas podle časů uzlů
■ Pošle všem tento nový čas
■ Vhodné pokud sever nemá absolutní čas
PA160
9
Jaro 2006
Decentralizovaná řešení
■ Resynchronizační intervaly
■ Globálně dohodnutý „počátek" T0
■ itý interval začíná v čase T0 + iR
■ itý interval končí v čase T0 + (i + 1)R
■ R je dohodnutý systémový parametr
■ Všichni pošlou broadcast se svým časem na začátku každého intervalu
■ Zpracování na uzlu
■ Dojde S zpráv
■ Spočítá se průměr (s vyloučením m odlehlých hodnot)
■ Možné zlepšení při znalosti doby propagace zpráv
PA160 10 Jaro 2006
NTP protokol
■ Network Time Protocol
- NTP version 3 (RFC1305), version 2 (RFC1119), version 1 (RFC1059)
- S(imple)NTP: RFC1769
■ Hierarchická organizace
■ Stratům 1 přímo napojené na absolutní čas
■ Celkem až 16 úrovní (Stratům 16)
■ Vysoce škálovatelné
■ Více jak jeden server
■ Možná reakce na výpadek či ztrátu přesnosti
■ Servery tik.cesnet.cz a tak.cesnet.cz
PA160 11 Jaro 2006
Logický čas
■ Absolutní čas není vždy důležitý
■ Podstatný relativníčas (souvislost dějů)
■ Logický čas
■ Nevyžaduje absolutní synchronizaci
■ Potřeba shody na uspořádání
PA160
12
Jaro 2006
Lamportovy časové známky
Relace „událo se dříve" (happens-before)
a —► b znamená, že se všechny procesy dohodly, že a nastalo dříve než 6.
Současně platí, že pokud a událost je zaslání konkrétní zprávy a b je událost přijetí téže zprávy, pak nutně a —> b
Vlastnosti
■ a —► b je tranzitivní
■ Události x a y jsou souběžné (concurrent), pokud neplatí ani x —► y ani
y —► a?
60 13 Jaro 2006
Realizace
Každý proces má vlastní logické hodiny
Pro události uvnitř jednoho procesu je zajištění relace „událo se před" triviální
Synchronizace mezi procesy probíhá jako součást zasílání zpráv
■ Každá zpráva obsahuje časovou známku odesílatele {Ts
■ Pokud je čas přijímajícího (Tr) menší (mladší) než časová známka v přijímané zprávě, nastaví se Tr = Ts + 1
Dodatečná podmínka
■ Žádné dvě události nenastanou ve stejný čas
60 14 Jaro 2006
Shrnutí
■ Lamportův algoritmus umožňuje zajistit globální čas v distribuovaném systému
■ Vlastnosti
■ Pokud a nastane před 6 ve stejném procesu, C(a) < C(b)
■ Pokud je a zaslání a 6 přijetí téže zprávy, C (a) < C{b)
■ Pro všechny různé události a a 6 platí C(a) / C{b)
■ Algoritmus umožňuje globální uspořádání událostí v distribuovaném systému
PA160
15
Jaro 2006