Unterschied zwischen strenger Konsistenz und sequentieller Konsistenz

8

Ich verstehe strenge und sequentielle Konsistenz unabhängig voneinander ziemlich gut.

Strict C erzwingt grundsätzlich die tatsächliche Reihenfolge, in der die Anweisungen auf der globalen Uhr ausgeführt wurden.

Sequentielle Konsistenz erzwingt die Reihenfolge grundsätzlich nur auf einem Prozessor.

Ich habe jedoch Probleme, Literatur zusammenzustellen. http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html beschreibt die sequentielle Konsistenz so, dass Speicherverzögerungen berücksichtigt werden. Es kann einige Zeit dauern, bis sich ein Schreibvorgang auf alle Prozessoren ausbreitet. Aber wenn es das tut, erreicht es alle auf einmal, was in Ordnung ist. Daher gilt Folgendes unter Sequentielle Konsistenz

P1:  W(x)1
-----------------------
P2:        R(x)0 R(x)1

Was mich jetzt beschäftigt, sind die folgenden Prozesse, die so etwas wie Dekkers Algorithmus sind.

P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0

Dies sollte unter sequentieller Konsistenz ( http://portal.acm.org/citation.cfm?id=1787234.1787255 S. 2) sicherlich NICHT möglich sein . Es gibt keine Gesamtreihenfolge, die dieses Ergebnis liefern könnte.

Aus der Idee heraus ist es jedoch sinnvoll, dass sich Schreibvorgänge durch sequentielle Konsistenz langsam ausbreiten und ein Thread möglicherweise keine Ahnung hat, was andere Prozessoren vorhaben.

Was fehlt mir hier?

pl.programming-languages dc.parallel-comp concurrency jetru
quelle
Ich denke, Sie verwechseln sequentielle Konsistenz und kausale Konsistenz. SC ist eine stärkere Bedingung als Ihre intuitive Formulierung ... wenn ich Sie richtig verstehe. Ihre zweite Ausführung ist CC (und PRAM C), aber nicht SC.
Aaron Sterling
Ja vielleicht. Meine Frage ist speziell, warum die zweite Ausführung NICHT sequentiell konsistent ist. Wenn der erste ist, was ist die besondere Argumentation, die die Ausführung 2 inkonsistent macht?
Jetru
Danke für alle Antworten. Ich las auch über kausale Konsistenz und verstand, dass ich genau darüber nachdachte.
Jetru

Antworten:

8

Ihnen fehlt nichts :)

Der Dekker-Algorithmus ist auf einem auf verteilten Shared-Memory-Hierarchien basierenden Multiprozessor nicht sequentiell konsistent, aber es ist sehr gut möglich, da sich die Speicheraktualisierungen nicht im Gleichschritt mit der Aktualisierung des lokalen Speichers (Cache), sondern asynchron über Cache-Kohärenz-Protokolle wie MESI (Weaker Memory Model) ausbreiten.

Bei einem Uniprozessor, bei dem Dekkers Algorithmus nicht der Fall ist, ist dies streng konsistent.

Sai Venkat
quelle
Wenn ich also die Weitergabe von Speicheraktualisierungen betrachte, entspanne ich tatsächlich das Speichermodell, daher ist in meinem imaginären Speichermodell Ausführung 2 möglich. In einem ordnungsgemäß sequentiell konsistenten Speicher würden sich die Schreibvorgänge sofort ausbreiten. Ist das richtig?
Jetru
1
Ja. Wenn jeder Prozess nur auf seinen lokalen Speicher schaut, ist die Ausführung 2 möglich. In einer ordnungsgemäß sequentiellen Konsistenz müssen sich die Schreibvorgänge nicht sofort ausbreiten, sondern wenn sich ein anderer Speicherort auf den geschriebenen Speicherort bezieht oder diesen aktualisiert, was normalerweise der Fall ist.
Sai Venkat
4

Sie haben bereits die richtige Antwort. Die zweite Ausführung ist nicht sequentiell konsistent, da "es keine Gesamtreihenfolge gibt, die dieses Ergebnis liefern kann".

Ich denke, Ihre Verwirrung kommt von dieser Idee:

Die Idee, dass sequentielle Konsistenz es Schreibvorgängen ermöglicht, sich langsam zu verbreiten, und ein Thread möglicherweise keine Ahnung hat, was andere Prozessoren vorhaben.

Das ist richtig. Die Ausbreitung kann langsam sein. Durch die sequentielle Konsistenz kann ein Thread nicht wissen, was andere Prozesse vorhaben (für welche Programme auch immer). Die sequentielle Konsistenz lässt jedoch nicht zu, dass jeder Thread nicht weiß, was andere Prozesse vorhaben (für einige Programme, einschließlich des Dekker-Algorithmus).

Der obige Ausdruck "für einige Programme" stammt aus dieser Überlegung: Selbst bei sequentieller Konsistenz ist kein Thread über das Verhalten eines anderen Threads informiert, wenn die Threads keinen gemeinsam genutzten Speicher verwenden.

Yhirai
quelle
3

Dieses Papier kann auch zum Verständnis beitragen, da der Titel auf den Unterschied zwischen den beiden von Ihnen erwähnten Konsistenzen hinweist. (Es geht jedoch zu einem großen Teil um die Implementierung von gemeinsam genutzten SeqCon- und StrictCon-Objekten bei der Nachrichtenübermittlung. Dies ist eine Möglichkeit, über die von Ihnen erwähnte Verzögerung nachzudenken.)

Um Ihre spezifische Frage zu beantworten: Sequentielle Konsistenz erfordert, dass alle Ereignisse in einer sequentiellen Reihenfolge stattfinden und dass das, was in einem Prozess passiert, immer mit der Zeit konsistent ist.

Also der Grund warum 

P1:  W1(x,1)  R2(y)0
-------------------
P2:  W2(y,1)  R2(x)0

ist nicht möglich, ist, dass es eine globale Sequenz geben muss, z W1(x,1) R1(y)0 W2(y,1) R2(x)?. In dieser Sequenz kann der letzte Lesevorgang eindeutig keine 0 zurückgeben. Diese Sequenz muss jedoch nicht mit Echtzeit konsistent sein. Es ist durchaus möglich (sequentielle Konsistenz), dass in Echtzeit die Abfolge der Ereignisse war W1(x,1) W2(y,1) R1(y)0 R2(x)1. Diese Sequenz ist aus Gründen der strengen Konsistenz unzulässig (da R1 (y) den Wert des vorherigen Schreibvorgangs nicht zurückgegeben hat).

Martin B.
quelle
Entschuldigung für den späten Kommentar, aber könnte es möglich sein, dass W1 (x, 1) W2 (y, 1) R1 (y) 1 R2 (x) 1 auch in einer sequentiell konsistenten Umgebung auftritt? Ist die Ausführungsreihenfolge so angeordnet, dass sie in dieser Reihenfolge erfolgt, bevor sie rechtzeitig erfolgt?
William
Die Ausführung W1 (x, 1) W2 (y, 1) R1 (y) 1 R2 (x) 1 ist sequentiell konsistent, sogar streng konsistent, wenn ich mich nicht irre (ich bin schon heute ein bisschen müde).
Martin B.
Ich bin mir nicht sicher, ob ich genau verstehe, was Sie unter "Ausführungsreihenfolge ist geplant" verstehen.
Martin B.