Warum ist die Konsensnummer für Test & Set 2?

Laut Wikipedia ,

Die Test-and-Set-Operation kann das wartefreie Konsensproblem für nicht mehr als zwei gleichzeitige Prozesse lösen.

Warum kann es das Problem nicht für mehr als zwei Prozesse lösen?

Um sicherzustellen, dass wir uns auf derselben Seite befinden, betrachten wir zunächst die folgenden drei Definitionen:

Definition. Test-and-Set ist ein Befehl zum Lesen, Ändern und Schreiben in einem Binärregister (sagen wir einfach, 0 und 1 sind mögliche Werte), in dem ein Thread den alten Wert erhält und 1 schreibt.

Definition. Ein Konsens wird zwischen Threads erreicht, wenn sich alle Threads für denselben Wert (die Konsistenzanforderung) und alle Threads für einen Wert entscheiden, der tatsächlich von einem der Threads vorgeschlagen wurde (die Gültigkeitsanforderung).$n$$n$

Definition. Ein Konsensprotokoll ist wartungsfrei, wenn jeder Methodenaufruf in einer endlichen Anzahl von Schritten beendet wird.

Folgen Sie nun zwei Beweisskizzen.

Behauptung 1. Die Konsenszahl von Test und Satz beträgt mindestens 2. Beweis. Angenommen, wir haben zwei Threads 0 und 1, die einen Konsens erzielen müssen. Wir könnten dies tun, indem wir jeden Thread dem unten stehenden Konsensprotokoll folgen lassen:

1. Schreiben Sie Ihren vorgeschlagenen Wert in , wobei die Thread-ID und ein Array der Größe 2 ist.t $A[t]$$t$$A$
2. Führen Sie den Test-and-Set-Befehl für ein Register , wobei auf 0 initialisiert ist.$R$$R$
3. Wenn der Rückgabewert 0 ist, waren Sie zuerst: return . Ansonsten waren Sie Zweiter: Geben Sie .A [ | t - 1 | $A[t]$$A[|t-1|]$

Sie können sich davon überzeugen, dass Konsens und Wartefreiheit gegeben sind. $\square$

(Für den nächsten Beweis werde ich einige Beweise und Definitionen verschachteln, da ich denke, dass dies das Verfolgen erleichtern wird.)

Behauptung 2. Die Konsenszahl von Test und Satz beträgt höchstens 2. Beweis. Im Widerspruch. Angenommen, wir haben drei Threads , und , die über die Werte , und entscheiden möchten , und wir haben ein gültiges wartefreies Konsensprotokoll, das mit Test-and-Set (und atomaren Lese- und Schreibvorgängen) implementiert wird ).B C a b $A$$B$$C$$a$$b$$c$

Wir können den Konsensprozess als gerichteten Baum darstellen, wobei:

• Die Wurzel ist der Zustand, in dem keiner der Threads eine Bewegung ausgeführt hat.
• Das linke Kind eines Knotens repräsentiert den Zustand, der sich nach einem Zug von ergibt , das mittlere Kind repräsentiert den Zustand, der sich nach einem Zug von ergibt , und das rechte Kind repräsentiert den Zustand, der sich nach einem Zug von ergibt ;B $A$$B$$C$
• Ein Blattknoten repräsentiert einen Zustand, in dem alle Threads beendet sind. Einem Blattknoten ist ein Wert , oder , wobei der Wert davon abhängt, welcher Wert für diese bestimmte Ausführung festgelegt wurde.b $a$$b$$c$

Definition. Ein Staat sei multivalent, wenn das Ergebnis des Konsensprozesses noch nicht feststeht. Mit anderen Worten, nicht alle möglichen Verschachtelungen der verbleibenden Züge führen zum gleichen Ergebnis. Lassen Sie einen Staat sein univalent , wenn das Ergebnis des Konsensprozesses wird bestimmt.

Die Wurzel ist multivalent. Beweis. Wenn nur ein Thread aktiv ist und die anderen Threads für immer inaktiv bleiben, endet in einer endlichen Anzahl von Schritten (garantiert durch die Annahme der Wartefreiheit) und entscheidet über (denn es hat nur Zugriff auf diesen Wert und dessen Entscheidung wird die Konsensgültigkeitsanforderung erfüllen). Für unsere Situation sind also , und alles mögliche Ergebnisse. X x a $X$$X$$x$$a$$b$$c$$\square$

Definition. Lasse ein kritischer Zustand ein Zustand sein, der mit der zusätzlichen Eigenschaft multivalent ist, dass ein Schritt von bestimmt , wird und eine Bewegung von bestimmt .a B $A$$a$$B$$b$

Es gibt einen kritischen Zustand. Beweis. Von oben wissen wir, dass wir in einem multivalenten Zustand beginnen. Lassen Sie keine Bewegung machen. Solange weder noch den Baum in einen einwertigen Zustand zwingen, lassen Sie ihn eine Bewegung ausführen. Die Wartefreiheit garantiert, dass der Baum endlich ist, sodass irgendwann ein kritischer Zustand angetroffen werden muss. A B $C$$A$$B$$\square$

Stellen Sie sich nun ein Szenario vor, in dem wir uns in einem kritischen Zustand befinden. Es gibt mindestens zwei Möglichkeiten:

1) bewegt sich (bestimmt dabei ) und hält an. macht dann seine Bewegung und hält an. Nächstes bis es beendet ist, und schließlich wird entschieden, dass .a B C $A$$a$$B$$C$$a$

2) bewegt sich (bestimmt dabei ) und hält an. Nächstes bis es beendet ist, und schließlich wird entschieden, . bewegt sich nicht.b C b $B$$b$$C$$b$$A$

Da atomare Lese- und Schreibvorgänge die Konsensnummer 1 haben, mussten die Bewegungen von und Test-and-Set-Anweisungen für dasselbe Register sein (wenn die Register unterschiedlich sind, kann nicht sagen, in welcher Reihenfolge und umgezogen). Aus der Perspektive von sind die Szenarien 1 und 2 also nicht zu unterscheiden, also müssen wir haben, dass sowohl als auch . Das ist unmöglich. B C A B C C a b $A$$B$$C$$A$$B$$C$$C$$a$$b$$\square$

Dass der Test-and-Set-Befehl die Konsensnummer 2 hat, folgt sowohl aus den Ansprüchen 1 als auch 2.

Der Wikipedia-Artikel enthält eine Referenz, die Ihre Fragen beantwortet, aber vielleicht möchten Sie dieses 26-seitige Papier nicht lesen. Ich werde eine vereinfachte Version des (ziemlich technischen) Beweises geben, die zeigt, dass Test-and-Set den binären Konsens für 3 Prozesse nicht lösen kann. Diese Art von Argument wird häufig zum Nachweis von Konsenszahlen verwendet.

Nehmen wir an, wir haben einen Konsensalgorithmus, der TAS-Register für 3 Prozesse verwendet.

Zu jedem Zeitpunkt hat jeder Prozess eine auszuführende Bewegung (Anweisung). Welche der drei Anweisungen ausgeführt wird, ist nicht deterministisch.

Angenommen, wir befinden uns in einem zweiwertigen Zustand (ein Zustand, in dem sowohl eine 0- als auch eine 1-Entscheidung noch möglich ist) und der nachfolgende Zustand ist einwertig, je nachdem, welcher Prozess als nächstes abläuft. Ein solcher Zustand muss schließlich wegen der wartefreien Bedingung erreicht werden.

Angenommen (wlg), wenn sich Prozess 1 bewegt, ist der Zustand 0-wertig, und wenn sich Prozess 2 bewegt, ist der Zustand 1-wertig. Bei beiden Verschiebungen muss es sich um eine TAS-Operation (oder zumindest um eine Art Schreibzugriff) für dasselbe Register handeln, da bei TAS-Operationen für verschiedene Register nicht festgestellt werden konnte, ob Prozess 1 zuerst verschoben wurde oder Prozess 2 zuerst verschoben wurde.

Betrachten wir diese beiden möglichen Ausführungen:

• Prozess 1 bewegt sich zuerst, dann Prozess 2 bewegt sich, dann läuft Prozess 3 alleine
• Prozess 2 bewegt sich zuerst, dann läuft Prozess 3 alleine

Aus Sicht von Prozess 3 sind diese Zustände nicht zu unterscheiden, da nur der von Prozess 2 geschriebene Wert angezeigt wird. Im ersten Fall sollte jedoch 0 als Ausgabe und im zweiten 1 als Ausgabe angegeben werden. Dies ist eindeutig ein Widerspruch.

Die Prozesse 1 und 2 können untereinander entscheiden, welche zuerst verschoben wurden (da sie sehen können, welcher Wert vor dem Schreiben im Register war), ein dritter Zuschauerprozess jedoch nicht.

Eine andere Möglichkeit zu beweisen, dass Test und Set nicht zur Lösung des 3-Prozessor-Konsenses verwendet werden können, besteht darin, zu zeigen, dass Test und Set unter Verwendung des 2-Prozessor-Konsenses implementiert werden können. Dann führt die Annahme, dass Test und Satz den Konsens mit 3 Prozessoren lösen können, zu einem Widerspruch: Angenommen, Test und Satz lösen den Konsens mit 3 Prozessoren. Durch Ersetzen von test-and-set durch seine Implementierung unter Verwendung von 2-Prozessor-Konsens erhält man dann eine Implementierung von 3-Prozessor-Konsens unter Verwendung von 2-Prozessor-Konsens, was unmöglich ist. Daher kann Test & Set den 3-Prozessor-Konsens nicht lösen.

Wenn Sie Test-and-Set für n-Prozessoren mithilfe eines 2-Prozessor-Konsenses implementieren möchten, lassen Sie die Prozessoren anhand eines Turniers, bei dem jedes Match mithilfe eines 2-Prozessor-Konsenses (in einem Match die Prozessoren) implementiert wird, einen Gewinner des Test-and-Set ermitteln Schlagen Sie ihre Kennung vor, und das Konsensergebnis gibt an, wer gewinnt.

Im praktischen Sinne könnte eine weniger strenge Konsensdefinition ausreichen (hier nenne ich es Lichtkonsens):

Definition . Ein leichter Konsens wird zwischen n Threads erreicht, wenn (a) jeder Thread entweder denselben Wert festlegt oder der Wert für ihn unbekannt ist, (b) mindestens ein Thread den Wert kennt und (c) dieser Wert tatsächlich von einem von vorgeschlagen wurde die Fäden.

Daher erlaubt dieser Konsens in seinem leichteren Sinne, dass ein Thread den Konsens, den Wert, der entschieden wird, nicht kennt.

Folgerung : In diesem leichteren Sinne hat Test-and-Set eine unendliche Lichtkonsenszahl.

Behauptung : Dieser leichtere Sinn ist praktisch. Um beispielsweise den Thread für den Eintritt in den kritischen Bereich auszuwählen, muss kein Konsens im engeren Sinne hergestellt werden. Das heißt: Jeder Thread muss wissen, ob er ausgewählt wurde oder nicht. Wenn er jedoch nicht ausgewählt ist, muss er nicht wissen, welcher Thread ausgewählt wurde. Mit anderen Worten, für den gegenseitigen Ausschluss ist kein strikter Konsens erforderlich, Licht ist genug.