Process 1 Process 2 // initialisation code // initialisation code integer x; y = 1; x = y + z; z = 2; // other code ... // other code ... Shared datastructures integer y = 0; z = 0;
In the above example Process 1 is adding two integer variables while Process 2 is assigning to those variables. Variable x is local to Process 1, while variables y and z are shared between the two processes.
At the end of the program fragment, what are the possible values of x?
Answer to (a)
If x = y + z is implemented by loading a register with y, then adding z to it, then the final value of x could be 0, 1, 2, or 3. This is because we could see the initial values for y and z, their final values or some combination, depending on how far the second process has progressed. A further peculiarity of the above fragment is that the final value of x could be 2, even though y + z is not 2 in any program state. This can happen if the initial value of y is loaded into a register by Process 1, y and z are set to their final values in Process 2, the final value of z is added to the initial value of y in Process 1's register and the result stored in x.
(b) Consider the following concurrent program:
Process 1 Process 2 x = x + 1; x = x + 2; x = x + 2; y = y - x; Shared datastructures integer x = 0; y = 0;
Now we interleave 6 atomic actions in process 1 and 7 in process 2:
Not sure what the formula is for the number of interleavings of 2 processes with n and m steps, respectively. For the first 6 steps of concurrent execution, we always have 2 choices: whether the next action is from process 1 or from process 2. This gives us a perfect binary tree of depth 6, so there are 64 possible interleavings of the first 6 steps. One of those, where all 6 steps are from process 1, has only a single continuation (7 steps from process 2), but others continue branching for some time, and with 13 steps all together we have a tree of depth 13, although it is not a perfect tree after the first 6 levels (so we have much fewer that 213 interleavings).Process 1 Process 2 1. load x in r1; load x in r2; 2. add 1 to r1; add 2 to r2; 3. store r1 in x; store r2 in x; 4. load x in r1; load y in r2; 5. add 2 to r1; load x in r3; 6. store r1 in x; subtract r2 from r3 (in r3); 7. load r3 in y; Shared datastructures integer x = 0; y = 0;
Let us assume that incr(x) increments x atomically, and instead of x = x+2 we do incr(x) twice:
Process 1 Process 2 1. incr(x); incr(x); 2. incr(x); incr(x); 3. incr(x); load y in r2; 4. load x in r3; 5. subtract r2 from r3 (in r3); 6. load r3 in y; Shared datastructures integer x = 0; y = 0;
Again there are loads of interleavings (8 for only the first 3 steps) but updates to x now cannot get lost; x always ends up as 5, and y can be -2, -3, -4 and -5.