(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:
Questions:
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.
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:
Answer
Answer
Now we interleave 6 atomic actions in process 1 and 7 in process 2:
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 213 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.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;
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.
(c) Consider the following concurrent program:
Process 1 Process 2 while (x != y) while (x != y) x = x + 1; y = y - 1; Shared datastructures integer x = 0; y = 10;
Questions:
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