Reguläre Semantik - Regular semantics

Reguläre Semantik ist ein Computerbegriff, der eine Art von Garantie beschreibt, die von einem Datenregister bereitgestellt wird, das von mehreren Prozessoren in einer parallelen Maschine oder in einem Netzwerk von zusammenarbeitenden Computern geteilt wird. Reguläre Semantik wird für eine Variable mit einem einzelnen Writer, aber mehreren Readern definiert. Diese Semantik ist stärker als die sichere Semantik, aber schwächer als die atomare Semantik : Sie garantieren, dass die Schreiboperationen in Echtzeit geordnet sind und dass Leseoperationen entweder den Wert des letzten abgeschlossenen Schreibvorgangs vor Beginn des Lesevorgangs, oder die eines der Schreibvorgänge, die gleichzeitig mit dem Lesen erfolgen.

Beispiel

Reguläre Semantik ist schwächer als Linearisierbarkeit. Betrachten Sie das unten gezeigte Beispiel, in dem die horizontale Achse die Zeit darstellt und die Pfeile das Intervall darstellen, in dem ein Lese- oder Schreibvorgang stattfindet. Gemäß der Definition eines regulären Registers sollte der dritte Lesevorgang 3 zurückgeben, da der Lesevorgang nicht gleichzeitig mit einem Schreibvorgang erfolgt. Andererseits kann der zweite Lesevorgang 2 oder 3 und der erste Lesevorgang entweder 5 oder 2 zurückgeben. Der erste Lesevorgang könnte 3 und der zweite Lesevorgang 2 zurückgeben. Dieses Verhalten würde der atomaren Semantik nicht genügen. Daher ist die reguläre Semantik eine schwächere Eigenschaft als eine atomare Semantik. Andererseits bewies Leslie Lamport , dass ein linearisierbares Register aus Registern mit sicherer Semantik implementiert werden kann , die schwächer als reguläre Register sind.

Sicher registrieren

Ein Satz von der Regularität zur Atomizität

Eine atomare Semantik eines Single-Writer-Multi-Reader (SWMR) ist ein reguläres SWMR-Register, wenn eine seiner Ausführungshistorien H die folgende Eigenschaft erfüllt: r1 und r2 sind zwei beliebige Leseaufrufe: (r1 → H r2) ⇒ ¬π(r2) →H π(r1)

Bevor wir in den Beweis einsteigen, sollten wir zuerst wissen, was die neue/alte Inversion bedeutet. Wie in der Abbildung unten gezeigt, können wir beim Betrachten der Ausführung sehen, dass der einzige Unterschied zwischen einer regulären Ausführung und einer atomaren Ausführung darin besteht, wenn a = 0 und b = 1. In dieser Ausführung betrachten wir die beiden Leseaufrufe R .read() → a gefolgt von R.read() → b, unser erster Wert (neuer Wert) ist a = 0, während der zweite Wert (alter Wert) b=1 ist. Dies ist eigentlich der Hauptunterschied zwischen Atomizität und Regularität.

Abbildung 1

Das obige Theorem besagt, dass ein reguläres Register mit einem einzelnen Schreiber und mehreren Lesern ohne neue oder alte Inversion ein atomares Register ist. Wenn wir das Bild betrachten, können wir sagen, dass es für R.read() → a →H R.read() → b und R.write(1) →H R.write(0) nicht möglich ist ( R.read() → b) =R.write(1) und π (R.read() → a) = R.write(0) wenn die Ausführung atomar ist. Um den obigen Satz zu beweisen, sollten wir zuerst beweisen, dass das Register sicher ist, als nächstes sollten wir zeigen, dass das Register regulär ist, und dann am Ende zeigen, dass das Register keine Neu/Alt-Inversion zulässt, was die Atomizität beweist. Durch die Definition des atomaren Registers wissen wir, dass ein atomares Register mit einem einzelnen Schreiber und mehreren Lesern regulär ist und die Eigenschaft no new/old Inversion erfüllt. Wir müssen also nur zeigen, dass ein reguläres Register ohne Neu/Alt-Inversion atomar ist.

Wir wissen, dass für zwei beliebige Leseaufrufe (r1 und r2), wenn das Register regulär ist und es keine neue/alte Inversion gibt (r1 → H r2) ⇒sn(π(r1)) ≤ sn(π(r2)). Für jede Ausführung (M) gibt es einen Gesamtauftrag (S), der die gleichen Operationsaufrufe enthält. Wir können sagen, dass S wie folgt aufgebaut ist: Wir beginnen mit der Gesamtreihenfolge der Schreiboperationen und fügen die Leseoperation wie folgt ein: zuerst: Die Leseoperation (r) wird nach der zugehörigen Schreiboperation (π(r)) eingefügt. .Zweitens: Wenn zwei Leseoperationen (r1,r2) gleich sind (sn(r1)=sn(r2)), dann füge zuerst die Operation ein, die zuerst in die Ausführung startet. S umfasst alle Operationsaufrufe von M, woraus folgt, dass S und M äquivalent sind. Da alle Operationen auf der Grundlage ihrer Sequenznummern geordnet sind, handelt es sich geringfügig um eine Gesamtordnung. Darüber hinaus ist diese Gesamtreihenfolge eine Ausführung von M fügt nur eine Reihenfolge für Operationen hinzu, die sich in M ​​überlappen. Wenn es keine Überlappung zwischen Lese- und Schreiboperationen gibt, gibt es keinen Unterschied zwischen der Regularität und der Atomarität. Schließlich können wir sagen, dass S zulässig ist, da jede Leseoperation den letzten geschriebenen Wert erhält, der in der Gesamtreihenfolge vor ihr liegt. Daher ist die entsprechende Historie linearisierbar. Da diese Argumentation nicht auf einer bestimmten Geschichte H beruht, bedeutet dies, dass das Register atomar ist. Da Atomizität (Linearisierbarkeit) eine lokale Eigenschaft ist, können wir feststellen, dass sich ein Satz regulärer SWMR-Register atomar verhält, sobald jedes von ihnen die Eigenschaft no new/old Inversion erfüllt.

Verweise