Sequenzielle Konsistenz

Question

Ist die folgende fortlaufende Übereinstimmung

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

P2: W (x) 2 ------------- R (x) 2 R (x) 1

P3: W (x) R 3 (x) 3 ---------------------- R (x) 1

Ich glaube, dass dies sequenziell konsistent ist, da die Programmreihenfolge vom Individuum erfüllt wird Prozessoren

Answer 1

Nein, th is ist keine sequentiell konsistente Spur.

Damit es sequentiell konsistent ist, sollte es einen entsprechenden legalen Trace geben, in dem Operationen jedes Prozesses in seiner Programmreihenfolge ausgeführt werden. Und eine Spur ist legal, wenn es sequentiell ist und jedes gelesen, um Register X gibt den letzten geschriebenen Wert zurück.

Wir können eine rechtliche Spur konstruieren, sondern Operationen von P2 und P3 in es wäre nicht ihr Programm übereinstimmen, um (liest, die Rückkehr 1 hatte vor schreibt neu geordnet werden):

P1: W(X, 1) 
P1: R(X) → 1 
P1: R(X) → 1 
P2: R(X) → 1 
P3: R(X) → 1 
P2: W(X, 2) 
P2: R(X) → 2 
P3: W(X, 3) 
P3: R(X) → 3 

Der Versuch, zu befriedigen beide Eigenschaften finden wir, dass es nicht möglich ist:

// it doesn't matter where we start really: P1, P2 or P3 
// (but with P2 and P3 the seq. consistent part of the trace would be even shorter) 
// let's go with P1 
P1: W(X, 1) 

// now the next read has to see X=1 so the trace remains legal 
P1: R(X) → 1 
// and again 
P1: R(X) → 1 

// no more P1's operations, 
// have to chose first op in either P1's or P2's program order 
// let's go with P2 
P2: W(X, 2) 

// now the next read has to see X=2 so the trace remains legal 
P2: R(X) → 2 // great! 

// at this point there's no operation that would keep the trace legal 
// except P3's W(X, 3) 
P3: W(X, 3) 

// there's only three reads left and the next one should see X=3 
P3: R(X) → 3 // yay! 

// but the last two reads ruin everything 
P2: R(X) → 1 // not seq. consistent! (because isn't legal) 
P3: R(X) → 1 // again, not seq. consistent!