循环处于竞态条件

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。 我希望答案很清楚。如果需要澄清，请告知我。