If we have two different processes with shared variable x, what are the possible values of x when both processes have completed?

Process A is running the following for-loop:

for (i = 0; i < 5; i++)
    x++

Process B is running:

for (j = 0; j < 5; j++)
    x--

I want to say x can be anywhere from -5 to 5, assuming x is initialized to 0. Is this true? Please include an explanation.

有帮助吗?

解决方案

Assuming the compiler will generate a single instruction that will increment x++ or decrement x--, it will have the same value it had before the for loops were executed after both threads are done, which is 0.

Otherwise, let's take the following example:

x++:
1. MOV R1, x     //register R1 receives x
2. INC R1        //register R1 is incremented
3. MOV x, R1     //store decremented x back to the memory

and

x--:
1. MOV R1, x     //register R1 receives x
2. DEC R1        //register R1 is decremented
3. MOV x, R1     //store decremented x back to the memory

It is quite obvious now that if one thread looses the CPU after executing line 1, it will have a value which is not updated, which will lead to a race condition and the variable will then have any value beetwen -5 and +5 after both threads are done with their execution, as you pointed out, depending on the different order of execution that both threads can have.

其他提示

You are correct. Imagine this scenario:

Both process A and process B (let's call them thread for clarity), get to the first iteration of the loop. Both threads retrieve the value of x (0), keep a local copy of that, compute their increment/decrement, and then race each other to update the register/memory containing x. Let's say A stores first, and B stores second. The resulting value of x is now -1.

Repeat this four more times and x ends up as -5.

Reverse the race above, and x ends up as 5.

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top