G52CON: Solution to Exercise 1, Interference

(a) In general, statements in a high-level programming language are not atomic---they expand into fine grained actions which are.


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.

Questions:

At the end of the program fragment, what are the possible values of x?
Answer
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.
Can any of the 'special' machine instructions described in Lecture 4 (exchange, test-and-set, increment) be used to ensure mutual exclusion?
Answer
The special instructions found on uniprocessor machines discussed in lecture 4 (exchange, test-and-set and increment) can't be used to ensure mutual exclusion in this case. The increment instruction simply adds 1 to the value of a memory location and loads the result into a register: it can't be used to implement general addition of the form y + z. However it may be possible to perform the addition as an atomic operation on a machine with a memory lock instruction, if this can be prefixed to addition.

(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:

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)
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;
```
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 there are fewer than 2¹³ interleavings). In addition there are interleavings that 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.
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;
```
There are many 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.


Process 1				Process 2

while (x != y)				while (x != y)
x = x + 1;				y = y - 1;

	      Shared datastructures
	      integer x = 0; y = 10;

Questions:

Suppose loop tests are performed by loading values into registers whose values are then compared and assignment statements are implemented by three atomic actions (load, add and store). Will the program terminate? Explain your answer.
Answer
The program may or may not terminate. The main cases where it will fail to terminate are executions in which the following interleaving occurs (for any value of x < 10 and y = x + 1: we'll take 4 and 5 as specific examples):
```
x  y  Process 1                     Process 2
4  5  1. read x (4), read y (5)     1. read x (4), read y (5)
      4 != 5 returns true           4 != 5 returns true
      read x (4), add 1, (5)        read y (5), subtract 1, (4)
      write x (5)                   write y (4)
      after P2.1 & before P2.2      after P1.1 & before P1.2
5  4  2. read x (5), read y (4      2. read x (5), read y (4)
      ...                           ...
```

This file is maintained by Brian Logan

Last modified: 5-Feb-2014, 18:52