Čas v distribuovaných systémoch

V distribuovaných systémoch je synchronizácia riešená pomocou logických a fyzických hodín. Keby nebola žiadna dohoda o čase, mohol by nastať napríklad takýto problém (obr. 1): Predpokladajme že výstup.o má čas 1747, a krátko potom výstup.c je upravený ale jeho čas je 1748, pretože hodiny na počítači sú trocha pomalšie. Make nezavolá kompilátor. Výsledný spustiteľný binárny program bude potom obsahovať zmes objektov zo starých zdrojov a nových zdrojov. Takýto program potom pravdepodobne nebude fungovať.


Obrázok 1: Keď má počítač vlastné hodiny, udalosť ktorá sa udiala neskôr môže mať skorší čas.


Logické hodiny

Lamport prezentoval algoritmus na synchronizáciu hodín v distribuovanom systéme. Poukázal v ňom na to, že procesy ktoré spolu nekomunikujú, nemusia mať synchronizované hodiny. Ďalej poukázal na to, že procesy sa nemusia zhodnúť na tom aký je čas, ale na tom v akom poradí sa uskutočnili jednotlivé udalosti. Tento čas nemusí byť rovnaký ako reálny čas. Logické hodiny teda zaisťujú meranie času v celom systéme, ktorý nemusí byť rovnaký ako reálny čas.

Teraz sa pozrieme na algoritmus, ktorý Lamport predviedol pre priradenie času udalostiam. Na obrázku 2 sú tri procesy, ktoré bežia na rozličných počítačoch, každý s vlastnými hodinami, ktoré bežia vlastnou rýchlosťou. Ako vidno na obrázku hodiny procesu 0 sa posunuli o 6, hodiny v procese 1 o 8 a v procese 2 o 10. V čase 6, proces 0 pošle správu A procesu 1. Procesu 1 správa dorazí v čase 16. Keď správa nesie hodnotu času odoslania 6, proces 1 predpokladá že trvalo 10 časových jednotiek na jej cestu. Správa B od procesu 1 k procesu 2 zaberie 16 časových jednotiek. Správa C z procesu 2 do 1 odchádza v 60 a prichádza v 56, podobne správa D z procesu 1 do 0 odchádza v 64 a prichádza v 54. K takýmto udalostiam nemôže dôjsť a musí im byť zabránené. Lamport to vyriešil tak, že ak správa C bola odoslaná v čase 60, musí prísť v čase 61 alebo neskôr. Keď je správa doručená prijímateľove hodiny ukazujú hodnotu nižšiu ako je v správe, hodiny sú presunuté dopredu o jednu alebo viac časových jednotiek.


Obrázok 2: (a) Procesy s lokálnymi hodinami. (b) Korekcia hodín podľa Lamportovho algoritmu.


Fyzické hodiny

V niektorých systémoch, je nutné, aby hodiny neboli len vzájomne synchronizované, ale aby sa nelíšili od reálneho času. Pre tieto systémy je nutné zaviesť externé fyzické zdroje času. Z dôvodu výkonnosti a spoľahlivosti je obvykle použitých viac zdrojov času.

Algoritmy na synchronizáciu fyzických hodín:

  • Cristianov algoritmus
  • Berkeley algoritmus

Cristianov algoritmus

V Cristianovom algoritme existuje časový server. Časový server nastavuje svoje hodiny podľa Koordinovaného svetového času (angl. Coordinated Universal Time, UTC), čo je štandard založený na atómovom čase. Časový server potom všetky ostatné počítače v systéme synchronizuje s ním (obr. 3).


Obrázok 3: Žiadosť o presný čas.


Cristianov algoritmus funguje nasledovne:

  1. Počítač požiada server o čas.
  2. Po prijatí žiadosti, server pošle čas T zo svojich vlastných hodín.
  3. Počítač potom nastaví svoj čas ako T = TUTC + (T1 – T0 - I)/2.

Berkeley algoritmus

V Berkeley algoritme sa časový server pýta ostatných počítačov na ich čas. Podľa ich odpovede im potom povie ako nastaviť ich hodiny. Príklad tohto algoritmu je na obrázku 5 a funguje nasledovne:
  • Časový server sa opýta ostatných počítačov aký majú čas.
  • Počítače mu odpovedajú.
  • Po prijatí odpovede, časový server pošle správu ostatným počítačom. Táto správa obsahuje čas podľa ktorého si majú počítače upraviť svoje hodiny.

Obrázok 4: Berkeley algoritmus




1Pri logických hodinách:





2Kto navrhol algoritmus logických hodín?






3Aké synchronizačné algoritmy sa používajú pri fyzických hodinách?






4Ako je riešená synchronizácia v distribuovaných systémoch?






5Synchronizačné algoritmy v DS delíme na: (doplnte chýbajúce znaky)


  1. Lov algoritmus
  2. Cov algoritmus
  3. Bov algoritmus

6Zoradte udalosti pri Berkeley algoritme:


  1. Časový server sa opýta ostatných počítačov aký majú čas.
  2. Počítače mu odpovedajú.
  3. Počítače nastavujú svoj čas podľa časového servera.

7Umiestnite príbuzné slová vedľa seba:


  1. Fyzické hodiny
  2. Logické hodiny
  3. Cristianov algoritmus
  1. Lamport
  2. Synchronizácia hodín počítača s reálnym časom.
  3. Počítače synchronizuje časový server.