G52CON 2008-9: Informal Exercise 1, Interference

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

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?

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

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

1. 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.