CODEWITHSUNDEEP
loopsconcurrencyprocessrace-condition
Sakshi
Sakshi

Reputation: 33

loops in a race condition

2 processes P0 and P1 are running concurrently with race condition. I want to calculate maximum and minimum values that x could have taken on during the execution. Initial value of x is 0

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

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

The maximum value should be 4000 and minimum should be -2999. But even after having tried many times, i couldn't figure this out. Any kind of help would be greatly appreciated! Thanks in advance.

Upvotes: 2

Views: 530

Answers (2)

Sankalp
Sankalp

Reputation: 75

I think the minimum value should be -2999 itself. I'll try to show how.

I am assuming the steps are running in the order 1,2,3,a,b (the names which Mr. Devarsh gave in one of the answers). Now notice that there has to be an increment operation at the end of every loop. For all but the last iteration, step 2 or step a can dirty read and destroy the increments done by (step b + step 1) or step b respectively. But in the last iteration, the decrement operation cannot destroy the value of increment which is going to happen next. And hence the answer -2999 and not -3000. I hope the answer is clear. Let me know if any clarification is required.

Upvotes: 1

Devarsh Desai
Devarsh Desai

Reputation: 6112

code247,

The key to understanding this problem lies in seeing the assembly code that's generated with each increment and decrement.

Each post-increment will generate the following code:

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

Each post-decrement will generate the following code:

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

Now what you're learning with concurrency is that the above assembly instructions can actually execute in a non-deterministic manner if you choose not to use mutex locks and other concurrency control techniques.

Now here is how we get a value of 4000 for the maximum value.

This is how the code is going to execute:

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
 }

Your code will execute in the following way to achieve the maximum:

step 1
step a
step b
step 2
step 3

Now the key here, is in recognizing that your reads and writes are going to be dirty. What this means is that in the above assembly code, the loaded value will not always reflect the correct value. Here's how this is going to play out:

 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)

From the above execution, you can see that the assembly is going to become intertwined, and that you aren't going to be persisting the correct value of 'x' onto your stack without the proper use of concurrency. This is how you're going to get 4000, because in some permutation of your assembly, you are going to consistently process 4 increment operators in series while the result of your decrement operators are not going to be properly saved. In this same manner, you are going to get the -2999 value, by executing your decrement operators in series while not properly persisting the value of x after your increment operator.

Please let me know if you have any questions!

Upvotes: 2

Related Questions