順序一致性

Question

是以下順序一致性

P1：W（x）1 R（x）1 ----------------------- R （x）的1

P2：W（X）2 ------------- R（X）2 R（x）的1

P3：W（X）3 R （x）3 ---------------------- R（x）1

我相信這是順序一致的，因爲程序順序是由個人處理器

Answer 1

否，th是不是一個順序一致的蹤跡。

爲了順序一致，應該存在一個等效的合法的跟蹤，其中每個進程的操作按其程序順序執行。跟蹤是合法當它是連續的，每個讀取寄存器X返回最後寫入的值。

我們可以構造一個法律痕跡，但在它P2和P3的操作就不是他們的節目順序一致（讀取返回1必須寫入前將重新排列）：

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 

試圖滿足這兩個屬性我們發現這是不可能的：

// 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!