Uhrensynchronisation #

Einführung #

In einem zentralisierten System ist die Zeit eindeutig. Das Betriebssystem gibt in der Regel die Uhr vor. Das bedeutet, dass alle Prozesse auf dem gleichen Betriebssystem konsistent sind. Wenn beispielsweise eine Datei gespeichert wurde und diese anschliessend kompiliert wird, hat das Resultat eine neuere Uhrzeit als die Quelldatei. Es spielt dabei keine Rolle, wenn die Uhr um ein paar Sekunden nachgeht, da die relative Ordnung stimmt.

Wird jedoch in einem verteilten System gearbeitet ist es nicht mehr so einfach, die richtige Zeit zu kennen. Dennoch ist es sehr wichtig. Man stelle sich eine Dateisynchronisation von mehreren Computern mit falschen Uhren vor. Welche Version ist die aktuellste?

NTP - Network Time Protocol #

Wenn mehrere Computer die identische Uhrzeit benötigen, könnten sie einen Dritten bitten, ihnen diese mitzuteilen. Das funktioniert, ist aber nicht ganz exakt, da die Übertragungszeit nur geschätzt werden kann.

In einem Diagramm sieht das Protokoll wie folgt aus:

B sendet die aktuelle Uhrzeit \(T_1\) an A. A notiert sich die Empfangszeit in \(T_2\) und gibt eine Antwort mit \(T_2\) und aktueller Uhrzeit \(T_3\) zurück. B empfängt die Nachricht und speichert die Empfangszeit in \(T_4\) . B kennt also alle Zeitstempel von \(T_1\) bis \(T_4\)

\(\Delta t_{req}\) und \(\Delta t_{res}\) ist nun die Differenz der Ankunftszeiten also die Zeit, die es dauert, um die Nachricht zuzustellen.

Sie berechnet sich wie folgt:

\( \Delta t_{req} = T_2 - T_1 \)

sowie

\( \Delta t_{res} = T_4 - T_5 \) .

Es kann also geschätzt werden, dass die Übertragungszeit etwa die Hälfte beider Werte ist:

\( \Delta t_{rtt} = \frac{\Delta t_{req} + \Delta t_{res}}{2} \)

Die korrekte Uhrzeit beim Zeitpunkt \(T_4\) ist für B also \(T_3 + \Delta t_{rtt}\) . Folglich muss B die Uhr wie folgt korrigieren:

\( \Delta t_{\text{von B zu A}} = T_3 + \Delta t_{rtt} - T_4 \)

Berkley Algorithmus #

Bei NTP ist der Zeitserver passiv. Beim Berkley Algorithmus fragt der Zeitserver die Computer regelmässig nach der aktuellen Zeit und berechnet einen Durchschitt. Anschliessend teilt er den Computern die korrekte Uhrzeit mit, damit diese sie dann korrigieren können. Dieser Algorithmus hat den entscheidenden Vorteil, dass er kein Netzwerkzugang benötigt. So können mehrere Rechner, die nicht am Netz hängen synchronisiert werden. Es gilt jedoch zu beachten, dass die korrekte Uhrzeit vermutlich nicht mit der korrekten Uhrzeit übereinstimmt. Solange das System von Computer aber nicht mit anderen Computern kommuniziert, ist das nicht weiter tragisch, da die relative Uhrzeit korrekt ist.

Logische Uhr von Lamport #

Die Lamport Uhr definiert “nur” eine logische Uhr, dass heisst es gibt keine absolute Uhrzeit wie wir sie von Weckern und Ähnlichem kennen. Lamport hat eine Beziehung zwischen zwei “Events” definiert, die er “happens-before” nennt. In den meisten Texten werden die Events zwischen Prozessen ausgetauscht. Prozesse können hier im weiteren Sinne also Systeme mit einer Uhr als Zähler aufgefasst werden. Jeder Event erhöht dann diesen Zähler. Lamport stellt ausserdem zwei wichtige Regeln auf.

Wenn a und b Events im selben Prozess sind und a vor b eintritt, dann ist a happens-before b (a -> b) wahr.
Wenn a ein “Versand-Event” ist, dass von einem Prozess ausgesendet wird und b das dazugehörige “Empfangs-Event” ist, dass von einem anderen Prozess empfangen wurde, dann gilt auch a happens-before b (a -> b) ist wahr. Denn es kann nur etwas empfangen werden, dass vorher versandt wurde.

Beispiel #

Es gibt 3 Prozesse (P1 bis P3), die 4 Events ( \(e_1\) bis \(e_4\) ) untereinander austauschen. Die 3 Prozesse haben eine relative Uhr, die bei 0 startet und unterschiedlich schnell ticken. Die unterstehende Tablelle stellt diese Situation dar.

So kann jedoch keine globale Ordnung erstellt werden. Deshalb soll im nächsten Schritt die Uhr jeweils korrigiert werden, sobald erkannt wurde, dass die Uhr zu hinterherhinkt. Das für zu folgendem Ergebnis:

Nun ist eine partielle Ordnung möglich. Es gibt jedoch noch die Situation, dass gleiche Zähler vorkommen können. Das können wir verhindern, indem im Zähler die Prozess-Id angehängt wird. Beispielsweise ist der Zähler 20 im Prozess 1 dann 20.1 und im Prozess 3 dann 20.3. Es ist zu beachten, dass auch mit dieser Erweiterung keine globale Ordnung hergestellt werden kann. Denn der Prozess 2 und 3 ist beispielsweise bis zum \(e_2\) nebenläufig.