Последовательная консистенция

Question

Является следующим последовательным последовательным

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

Р2: W (X) 2 ------------- Р (х) 2 Р (х) 1

Р3: W (х) 3 R (x) 3 ---------------------- R (x) 1

Я считаю, что это последовательное согласование, поскольку заказ программы встречается индивидуальным процессоры

Answer 1

Нет, th не является последовательным последовательным следом.

Для последовательного согласования должен существовать эквивалент legal trace, в котором операции каждого процесса выполняются в его программном порядке. И след закончен, когда он является последовательным, и каждый считывает регистр 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!