Unterschied zwischen der Konsensummer N und der Konsensummer unendlich

Question

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?

Answer 1

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 $ 2N- 2 $ Prozesse zum Synchronisieren von wartenfrei, wenn es $ N $ registriert ist. Weitere Prozesse erfordern weitere Register. Daher besteht die Konsensummer eines Objet, der aus $ N $ Register besteht, die atomisch zugewiesen werden können, ist $ 2N-2 $ .

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 $ N $ , die Konsensummer von MEM-und-Swap zumindest $ N $ . (Angabe, dass die Konsensummer ist $ N $ in einem System von $ n $ -Prozesse ist ein Bit eines Misnomers, da die Definition der Konsensnummer nicht eigentlich von der Gesamtzahl der Prozesse abhängt.) Da die Konsensanzahl der MEM-und-Swap mindestens $ n $ für jeden $ n $ , ist es unendlich.

Wenn Sie eine andere Quelle als Raynals-Buch bevorzugen, können Sie das Original lesen Papier von Maurice Herlihy .