G52CON 2008-2009: Solution to Exercise 1, Interference

(a)

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.

Assume that:

• values are manipulated by loading them into registers, operating on them there and storing the results back into memory;
• the usual load, store and arithmetic operations are available;
• each process has its own set of registers; and
• any intermediate results that occur when a complex expression is evaluated are stored in registers or in memory private to the process.

Question:

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;

Questions:

1. Suppose each assignment statement is implemented by a single atomic action. How many possible traces are there? What are the possible final values for x and y?

   Answer

   • trace 1: P1.1 (x=1) P1.2 (x=3) P2.1 (x=5) P2.2 (y=-5)
   • trace 2: P1.1 (x=1) P2.1 (x=3) P1.2 (x=5) P2.2 (y=-5)
   • trace 3: P1.1 (x=1) P2.1 (x=3) P2.2 (y = -3) P1.2 (x=5)
   • trace 4: P2.1 (x=2) P1.1 (x=3) P1.2 (x=5) P2.2 (y=-5)
   • trace 5: P2.1 (x=2) P1.1 (x=3) P2.2 (y=-3) P1.2 (x=5)
   • trace 6: P2.1 (x=2) P2.2 (y=-2) P1.1 (x=3) P1.2 (x=5)

2. Suppose each assignment statement is implemented by three atomic actions (load, add and store). How many possible traces are there now? What are the possible final values for x and y?

   Answer

   Now we interleave 6 atomic actions in process 1 and 7 in process 2:

   
   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;
   
   

   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 2¹³ interleavings).
   In addition to the interleavings from before, we may get new interesting ones which involve loss of increment, for example P2.1 (r2=0) followed by P1.1-P1.6 (x=3) followed by P2.2-P2.7 (x=2,y=-2) (loss of 2 updates by process 1). In general, updates to x which can get lost are: the first one by process 1, which leaves x as 4 and y as either -2 or -4; the first and the second by process 1, as above; or the first one by process 2, which leaves x as 3 and y as either -2, -1, or -3.

3. Suppose each assignment statement is implemented by three atomic actions (load, add and store), but that in addition we have an atomic increment instruction as defined in lecture 4. How many possible traces are there now? What are the possible final values for x and y?

   Answer

   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.