循環處於競態條件

Question

2進程P0和P1與競態條件同時運行。 我想計算x在執行過程中可能採取的最大值和最小值。 x的初始值是0

P0: 
for(int i=0; i<1000; i++){ 
    x++; 
    x-- ; 
    x++; 
} 

P1: 
for(int j=0; j<2000; j++){ 
    x-- ; 
    x++; 
} 

的最大值應4000和最小應爲-2999。但即使經過多次嘗試，我也弄不明白。 任何形式的幫助將不勝感激！提前致謝。

Answer 1

code247，

理解這個問題的關鍵在於看到一個與每個增量和減量生成的彙編代碼。

每個增量後會生成以下代碼：

ld [%fp-4], %l0 
add %l0, 1, %l0 
st %l0, [%fp-4] 

每個減量後會生成以下代碼：

ld [%fp-4], %l0 
sub %l0, 1, %l0 
st %l0, [%fp-4] 

現在你和併發性學習的是什麼，上述如果您選擇不使用mutex locks和其他concurrency control techniques，裝配說明實際上可以以非確定性方式執行。

現在這裏是我們如何獲得最大值爲4000的值。

這是代碼將如何執行：

P0: 
for(int i=0; i<1000; i++){ 
    x++; //lets call this step 1 
    x-- ; //step 2 
    x++; //step 3 
} 

P1: 
for(int j=0; j<2000; j++){ 
    x-- ; //step a (using letters to denote difference in processes) 
    x++; //step b 
} 

您的代碼將通過以下方式執行，以獲得最大：

step 1 
step a 
step b 
step 2 
step 3 

現在這裏的關鍵，是在認識到你的reads and writes are going to be dirty。這意味着在上面的彙編代碼中，加載的值不會總是反映正確的值。下面是這是怎麼回事發揮出來：

ld [%fp-4], %l0 //read current value of 'x' for step 1 
add %l0, 1, %l0 //performs increments 
st %l0, [%fp-4] //stores value from step 1 
ld [%fp-4], %l0 //begins read for step a 
sub %l0, 1, %l0 //performs decrement 
ld [%fp-4], %l0 //performs a DIRTY-READ for step b (notice step a hasn't finished executing) 
add %l0, 1, %l0 //performs increment 
st %l0, [%fp-4] //stores value from increment (value from decrement is now outdated and lost) (this is a dirty write) 
st %l0, [%fp-4] //stores value from decrement (this value is actually lost)(this is a dirty write) 

從上面的執行，你可以看到，組件將成爲交織在一起，那你是不是將要堅持的正確值「X」到沒有proper use of concurrency的堆棧上。這就是你將如何獲得4000，因爲在你的程序集的一些排列中，你將連續處理4個增量運算符，而你的遞減運算符的結果不會被正確保存。以同樣的方式，你將獲得-2999的值，通過串行執行你的遞減運算符，而在你的遞增運算符之後沒有適當地保持x的值。

如果您有任何問題，請讓我知道！

Answer 2

我認爲最小值應該是-2999本身。我會盡力展示如何。

我假定這些步驟按1,2,3，a，b（Devarsh先生在其中一個答案中給出的名稱）的順序運行。 現在請注意，每個循環結尾處都必須有一個增量操作。對於除最後一次迭代以外的所有操作，步驟2或步驟a可能會髒讀並分別破壞（步驟b +步驟1）或步驟b完成的增量。但在最後一次迭代中，遞減操作不能破壞接下來將要發生的增量值。因此答案-2999而不是-3000。 我希望答案很清楚。如果需要澄清，請告知我。