顺序一致性

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!