Logische Uhr

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Eine Logische Uhr ist eine Komponente eines Computersystems, die dafür verwendet wird, Ereignissen einen eindeutigen Zeitstempel zu geben. Anders als bei einer „normalen“ Echtzeituhr, die die physikalische Zeit misst, ist der einzige Anspruch an eine logische Uhr, dass sie monoton steigende Werte abgibt, so dass die Kausalordnung der Ereignisse erkennbar ist.

Der Zweck einer solchen Uhr ist es, Ereignisse über ihren Zeitstempel in eine Finalordnung bringen zu können. In einem System mit nur einem Prozess ist das trivial: man braucht nur einen Zähler. Interessant wird das Problem, wenn man versucht, die logischen Uhren mehrerer Prozesse (Verteilte Systeme) so zu synchronisieren, dass man eine Kausalordnung für das Gesamtsystem angeben kann. Dafür ist es vor allem notwendig, das Senden und Empfangen von Nachrichten als Ereignisse zu betrachten und mit einem Zeitstempel zu versehen.

Dass hierfür der Begriff synchronisieren verwendet wird, hat historische Gründe: Zunächst wurde versucht, die Kausalordnung über Echtzeituhren zu bestimmen, die zu diesem Zweck möglichst synchron gehalten werden müssen. Später erkannte man, dass es ausreichend und viel einfacher ist, mit einem abstrakten Zeitbegriff zu arbeiten, der sich auf die Bestimmung der Kausalität beschränkt.

Uhrenbedingung und Kausalordnung[Bearbeiten]

Damit man nun aus den Zeitstempeln eine kausale (Halb-)Ordnung ableiten kann, muss die logische Uhr das (schwache) Konsistenzkriterium für Uhren (bzw. die schwache Uhrenbedingung) erfüllen (siehe auch Happened-Before-Relation):

  • Wenn das Ereignis e1 eine Ursache des Ereignisses e2 war, dann ist der Zeitstempel von e1 kleiner als der von e2. In Zeichen:
e1 e2  \Rightarrow  C(e1) < C(e2)

Das starke Konsistenzkriterium für Uhren (oder starke Uhrenbedingung) verlangt außerdem, dass auch die Umkehrung gelten muss:

  • Wenn der Zeitstempel von e1 kleiner als der von e2, dann war das Ereignis e1 eine Ursache des Ereignisses e2. In Zeichen:
C(e1) < C(e2)  \Rightarrow  e1 e2

Wenn auch die starke Uhrenbedingung erfüllt ist, kann man an der Uhr auch ablesen, welche Ereignisse nebenläufig sind.

Aus diesen Relationen ergibt sich im Allgemeinen nur eine Halbordnung. Nicht von jedem Paar von zwei Ereignissen kann gesagt werden, dass das eine die Ursache des anderen war: Die Ereignisse können auch (kausal) unabhängig sein, man spricht dann auch von Nebenläufigkeit (oder sogar Gleichzeitigkeit – wobei dieser Begriff an sich nicht exakt ist: Siehe Relativität der Gleichzeitigkeit). In Zeichen:

\neg e_1 e_2 \and \neg e_2 e_1  \Leftrightarrow  e_1 \| e_2 \Leftrightarrow  e_2 \| e_1
Dabei ist ein Ereignis immer nebenläufig zu sich selbst: \forall e: e \| e
Die Nebenläufigkeit ist symmetrisch, aber nicht transitiv:  e_1 \| e_2 \Leftrightarrow e_2 \| e_1 , aber  e_1 \| e_2 \and e_2 \| e_3 \  \not \Rightarrow \  e_1 \| e_3: Stellen wir uns vor, das Ereignis e1 und e3 finden am selben Ort statt, so dass e1 Ursache von e3 ist, also e_1 e_3. Irgendwo anders findet völlig unabhängig das Ereignis e2 statt, es gilt also e_2 \| e_1 und  e_2 \| e_3 bzw. e_1 \| e_2 und  e_3 \| e_2 . Aus der Transitivität würde nun folgen, dass auch e_1 \| e_3 gilt – tut es aber nicht, da ja laut Annahme e_1 e_3 gilt, also e1 Ursache von e3 ist.

Der Übersichtlichkeit halber schreibt man (nach Leslie Lamport), um die kausale Abhängigkeit von Ereignissen auszudrücken,

statt e_1 e_2 e_3 auch etwas klarer: e_1 \rightarrow e_2 \rightarrow e_3

Dabei muss man allerdings aufpassen, dass man den Pfeil für „ist Ursache von“ nicht mit der semantischen Implikation (\Rightarrow) verwechselt.

Anwendung[Bearbeiten]

Logische Uhren finden ihre Anwendung vor allem in Bereichen, in denen Kausalität und Verlässlichkeit eine große Rolle spielen. Dies ist vor allem in Transaktionssystemen der Fall. Sie dienen dazu, eingehende Nachrichten und Befehle in der richtigen Reihenfolge zu bearbeiten. Insbesondere ist es unter Verwendung von logischen Uhren möglich, ein verlässliches, wohlgeordnetes Multicast-Protokoll zu entwerfen.

Allerdings sind die Verfahren zur Synchronisation von logischen Uhren in großen Systemen im Allgemeinen recht ineffizient. Deshalb wird bei den „populären“ Protokollen, die im Internet Verbreitung gefunden haben, entweder mit der „physischen“ Zeit gearbeitet – man hofft einfach, dass die Uhren der verschiedenen Rechner nicht zu unterschiedlich gehen (ein Beispiel hierfür ist HTTP). Oder man beschränkt sich auf die Synchronisation von nur zwei Systemen (Client-Server-Modell) unter Verwendung von Sequenznummern (wie bei TCP).

Verfahren[Bearbeiten]

Es gibt verschiedene Verfahren, um konsistente logische Uhren in verteilten Systemen zu realisieren. Die bekanntesten sind vermutlich:

  • die Lamport-Uhr – sie genügt mit relativ wenig Aufwand dem (schwachen) Konsistenzkriterum.
  • Vektoruhren sind etwas aufwendiger, genügen dafür aber dem starken Konsistenzkriterum.

Daneben gibt es noch diverse Verfahren, um Echtzeituhren über ein Netzwerk zu Synchronisieren. Siehe dazu u. a. den Algorithmus von Cristian und das Network Time Protocol.