Vektoruhr

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Eine Vektoruhr ist eine Softwarekomponente (oder ein Protokoll) zum Zuweisen von eindeutigen Zeitstempeln an Nachrichten. Sie ist also eine logische Uhr, die es erlaubt, den Ereignissen in einem Verteilten System aufgrund eines Zeitstempels eine Kausalordnung zuzuweisen (Sequentialisierung) und insbesondere die Nebenläufigkeit von Ereignissen zu ermitteln. Sie stellen eine Erweiterung der Lamport-Uhr dar, die auch der starken Uhrenbedingung genügt. Vektoruhren wurden von mehreren Wissenschaftlern unabhängig von einander entwickelt, insbesondere von Friedemann Mattern, C. J. Fidge und Frank Bernhard Schmuck.

Beispiel eines Systems von Vektoruhren

Das Vorgehen beim Betrieb von Vektoruhren ist wie folgt: Ähnlich wie bei der Lamport-Uhr führt jeder Prozess einen Zähler, der bei jedem Ereignis (insbesondere beim Senden und Empfangen von Nachrichten) erhöht wird. Aber anders als bei der Lamport-Uhr besteht hier die Uhr jedes Prozesses nicht nur aus einem Zähler, sondern aus einem Vektor (bzw. einem Array oder einem Hash) von Zählern: Jeder Prozess merkt sich den Zählerstand aller anderen Prozesse, soweit der bekannt ist. Der aktuelle Stand der Uhr wird jeder gesendeten Nachricht angehängt.

Bei jedem Ereignis wird immer nur der eigene Zähler erhöht. Wird eine Nachricht empfangen, wird aus dem aktuellen und dem empfangenen Vektor ein elementweises Maximum gebildet, um den neuen Stand der Uhr zu ermitteln.

Als Pseudocode sieht die Umsetzung einer Vektoruhr so aus: Routine zum Senden einer Nachricht:

Uhr[PID]= Uhr[PID]+1;
Zeitstempel= Uhr;
sende(Nachricht,Zeitstempel);

Dabei sei PID für jeden Prozess ein fest vorgegebener und eindeutiger Bezeichner, zum Beispiel eine Prozess ID oder eine IP-Adresse (oder auch eine Kombination aus diesen beiden). Die Felder der Uhr für die Prozesse, von denen noch keine Nachricht empfangen wurde, werden als null angenommen.

Routine zum Empfangen einer Nachricht:

(Nachricht,Zeitstempel)= empfange();
Uhr[PID]= Uhr[PID]+1;
 
for (Prozesse P) do begin
    Uhr[P]= max(Uhr[P],Zeitstempel[P]);
end;

Um nun anhand der Zeitstempel entscheiden zu können, welche Nachricht (bzw. welches Ereignis) von welcher anderen kausal abhängig ist, wird über den Ständen der Vektoruhr eine Ordnungsrelation definiert: ein Ereignis A ist eine Ursache von Ereignis B, wenn der Zähler für jeden Prozess im Zeitstempel C(A) kleiner oder gleich dem Zähler im Zeitstempel C(B) für den korrespondierenden Prozess ist. In Zeichen:

C (A) = (A 1, A 2, A 3 ... A n)

$A B \Leftrightarrow \forall_{1\le i\le n}: A_i \le B_i$

Man schreibt diese Relation auch so:

$A \Rightarrow B$

Da für Vektoruhren die Implikation in beide Richtungen gültig ist, erfüllen sie die starke Uhrenbedingung.

Eine Umsetzung der obigen Ordnungsrelation in Pseudocode (A und B seien die zu vergleichenden Zeitstempel, die Frage ist, ob A eine Ursache von B war):

procedure ist_ursache(A,B):
    for (Prozesse P) do begin
        if ( Z1[A] > Z2[B] ) then return NEIN;
    end;
     
    return JA;
end procedure;

Zu beachten ist übrigens, dass es durchaus den Fall gibt, dass weder A ⇒ B noch B ⇒ A gilt: Die Ereignisse sind dann nebenläufig, man schreibt auch A || B. Es ist gerade der entscheidende Vorteil von Vektoruhren über die einfacheren Lamport-Uhren, dass es aufgrund der Zeitstempel möglich ist, zu erkennen, welche Ereignisse nebenläufig sind. Das ergibt sich aus der Gültigkeit der starken Uhrenbedingung.

Von „http://de.wikipedia.org../../../v/e/k/Vektoruhr.html“

Kategorien: Theoretische Informatik | Verteiltes System | Uhr

Vektoruhr

aus Wikipedia, der freien Enzyklopädie

Views

Navigation

Mitmachen

Suche

Andere Sprachen