Unterschied zwischen der Konsensummer N und der Konsensummer unendlich
-
29-09-2020 - |
Frage
in buch gleichzeitige Programmierung: Algorithmen, Prinzipien und Fundamente von Michel Raynal, in Abschnitt 16.5.1, SAUDE 75 sagt
Compare & Swap-Objekte haben unendliche Konsensummer.
und in Abschnitt 16.5.2 sagt Lemma 40
Der MEM-to-MEM-Swap-Objekttyp hat eine Konsensummer n in einem System von N-Prozessen.
dann in § 16.1 Autor in Tabelle sowohl Compare & Swap als auch Men-to-MEM-Swap als Objekte mit der Konsensummer unendlich.
Also, was ist der Unterschied zwischen Objekten mit Konsensummer N und Objekten mit Konsensummer unendlich?
Lösung
Die Konsensummer eines Objekts ist die maximale Anzahl von gleichzeitigen Prozessen, die Sie mit einem solchen Objekt auf eine wartefreie Weise synchronisieren können (ich werde hier nicht in das Warten-freie Mittel eingehen). Beispielsweise hilft ein Register mit nur Lese- und Schreibvorgängen nicht bei der wartungsfreien Synchronisierung, sodass es eine Konsens-Nummer 1 hat. Ein Register mit einem Test- und Set-Betrieb kann verwendet werden, um zwei Prozesse in einer Wartezeit zu synchronisieren -Fokus, aber nicht drei oder mehr, also ist die Konsensummer des Test- und Satzes 2.
$ N $ -Register-Zuordnung, bei dem ein Prozess atomar in mehrere Register schreiben kann, ermöglicht den
Ein einzelnes Register mit einem Compare-and-Swap-Betrieb reicht aus, um eine beliebige Anzahl von Prozessen zu synchronisieren. Wartenfrei. Daher ist die Konsensanzahl von Compare-and-Swap unendlich.
lemma 40 besagt, dass ein MEM-und-Swap-Objekt die wartenfreie Synchronisation aller Prozesse in einem System von $ n $ gleichzeitige Prozesse für jeden ermöglicht Nummer $ n $ . Dies bedeutet, dass für eine beliebige Anzahl
Wenn Sie eine andere Quelle als Raynals-Buch bevorzugen, können Sie das Original lesen Papier von Maurice Herlihy .