2015-06-20 12 views
6

Ich versuche derzeit, Lamport Zeitstempel zu verstehen. Betrachten wir zwei Verfahren P1 (Herstellung Ereignisse a1, a2 , ...) und P2 (Herstellung Ereignisse b1, b2 , ...). Lassen Sie C (e) den Lamport Zeitstempel zugeordnet Ereignis und e bezeichnen. Ich Zeitstempel für jedes Ereignis erstellt, wie in den Wikipedia article about Lamport timestamps beschrieben:Logische Uhren: Lamport Timestamps

enter image description here

Laut Wikipedia die folgende Beziehung für alle Veranstaltungen e1 wahr, e2:

Wenn e1 geschah vor e2, dann C (e1) < C (e2).

die bei a1 und b2 aussehen lassen. Offensichtlich a1 passiert ist, bevor b2, und da C (A1) = 1 undC (b2) = 3, die Beziehung gilt: C (a1) < C (b2).

Problem: Die Beziehung für b3 und a3 nicht wahr halten. Offensichtlich geschah b3 vor a3. Jedoch C (b3) = 4 und C (a3) ​​= 3. So C (b3) < C (a3) ​​ tut nicht gelten.

Was habe ich falsch verstanden? Hilfe wird sehr geschätzt!

Antwort

1

Ich entdeckte meinen Fehler.Ich schrieb:

Wenn e1 vor e2 passiert ist, dann C (e1) < C (e2).

Allerdings definiert Lamport "geschah vor" als Teilbestellung. Dies ist, was Wikipedia über teilweise geordnete Mengen sagt:

Eine solche Beziehung heißt eine partielle Ordnung, um die Tatsache widerzuspiegeln, dass nicht jedes Paar von Elementen verwandt sein muss: für einige Paare kann es sein, dass keines der Elemente vorangeht andere in der Pose.

Nach Lamports Definition von "passiert ist, bevor", b3 und a3 nicht verwandt sind, so b3 nicht "geschehen, bevor" a3, damit die equasion in der Frage angegeben muss nicht wahr sein.

1

Lamport geht davon aus, dass: wir können die physikalische Zeit im Allgemeinen nicht verwenden, um die Reihenfolge eines beliebigen Paares von Ereignissen zu ermitteln, die darin vorkommen. Im vorgeschlagenen Beispiel ignorieren Sie diese Annahme.

P1 und P2 Inkrementen ihre Uhren unabhängig voneinander. Wenn ein Ereignis auftritt, sendet der sendende Prozess seinen aktuellen Wert an den Zielprozess, der überprüft, ob der empfangene Wert kleiner als sein aktueller Wert ist. Ist dies der Fall, ändert sich der aktuelle Wert in den empfangenen Wert + 1, andernfalls wird der empfangene Wert verworfen. In Ihrem Fall P1 und P2 senden Sie keine Ereignisse a3 und b3.

3

Ja, diese Definition könnte etwas verwirrend sein. Es stimmt, was alle anderen bisher gesagt haben, aber vielleicht fehlt ein Wort, um das System besser zu verstehen. - gleichzeitige

Wenn Sie verarbeitet p1 und p2 auf der gleichen Maschine laufen, es ist wirklich nicht zu viel von einer Notwendigkeit Lamport Uhren zu verwenden (vielleicht einige sehr speziellen Fall). Stattdessen können Sie einfach die von Ihrem Betriebssystem bereitgestellte Uhr verwenden. Aber was, wenn p1 und p2 auf Computern sind, die durch ein langsames und unzuverlässiges Netzwerk getrennt sind?

Lamport geht davon aus, dass Sie Ihrer lokalen Uhr nicht vertrauen können und dass Sie keinen globalen Status des verteilten Systems haben, in dem Ereignisse auf 2 verschiedenen Computern aufgetreten sind. Dann rufen Sie diese Ereignisse gleichzeitig auf.

Wenn Sie die Ausführung des verteilten Systems Debuggen würde und Sie würden Ereignisse a3 und b3 natürlich man davon ausgehen würde, a3 geschah vor b3 sehen. In Ihrem speziellen Fall würden Sie jetzt behaupten, yeah, aber das ist falsch. Da die Ereignisse jedoch nicht miteinander in Beziehung stehen, da sie nicht miteinander kommunizieren, wird angenommen, dass die Reihenfolge gleichzeitig ist, und in einem solchen Fall spielt es keine Rolle, welche zuerst oder zweite für die gesamte Ausführung von das System.

Da Computer und Netzwerke werden so schnell arbeiten und immer noch sehr genau, es ist manchmal schwer zu verstehen, lassen Sie uns etwas anders in der gleichen Sache aussehen:

p1 und p2 sind zwei Menschen paar 100 Jahre leben Vorbei in zwei verschiedenen Tälern. Sie kommunizieren miteinander über Pidgins und reden nie darüber, wann sie eine bestimmte Aufgabe erledigt haben, was sie getan haben. Auf diese Weise konnte niemand wissen, wer, wenn a3 passiert vor b3 oder umgekehrt, daher passiert sie gleichzeitig. Vielleicht nicht niemand, Gott beobachtet von oben auf p1 und p2 könnte es sehen.

Leider, wenn Sie ein verteiltes System haben, können Sie nicht Gott sein und beobachten p1 und p2 zugleich, nur aus dem Grund, dass Nachrichten von p1 könnte länger dauern als von p2. Also, obwohl Ihr Überwachungssystem (Gott) die Informationen von b3 erhalten hat, bevor es die Informationen über a4 erhalten hat bedeutet es nicht, dass sie in dieser Reihenfolge passierten, vielleicht dauerte die Pakete mit Informationen über a4 nur noch länger oder langsamer Pfad.

Am Ende gibt es noch eine Sache namens vector clocks. Jeder Prozess hat eine Lamport-Uhr für jeden Prozess im System. Der Schlüssel hier ist, Event ein nur vor Ereignisse b die b passieren würde, wenn alle Lamport Uhren ein waren kleiner oder gleich. Wenn Sie es an Ihrem kleinen Beispiel ausprobieren, werden Sie sehen, dass kein Ereignis vor dem anderen passiert ist => sie sind gleichzeitig.