Question

Consider the following program:

 

Note that the scheduler in a uniprocessor system would implement pseudo parallel execution of these two concurrent processes by interleaving their instructions, without restriction on the order of the interleaving.

a. Show a sequence (i.e., trace the sequence of inter-leavings of statements) such that the statement “x is 10” is printed.

b. Show a sequence such that the statement “x is 8” is printed. You should remember that the increment/decrements at the source language level are not done atomically, that is, the assembly language code:

 

Implements the single C increment instruction (x = x + 1).

Answer 1

a.

For "x is 10", the interleaving producing the required behavior is easy to find since it requires only an interleaving at the source language statement level. The essential fact here is that the test for the value of x is interleaved with the increment of x by the other process. Thus, x was not equal to 10 when the test was performed, but was equal to 10 by the time the value of x was read from memory for printing.

 

P1: x = x - 1;	M(x)
	9
P1: x = x + 1;	10
P2: x = x - 1;	9
P1: if(x != 10)	9
P2: x = x + 1;	10
P1: printf("x is %d", x);	10

 

"x is 10" is printed.

 

 

b.

For "x is 8" we need to be more inventive, since we need to use inter-leavings of the machine instructions to find a way for the value of x to be established as 9 so it can then be evaluated as 8 in a later cycle. Notice how the first two blocks of statements correspond to C source lines, but how later blocks of machine language statements interleave portions of a source language statement. 

Notice how the first two blocks of statements correspond to C source lines, but how later blocks of machine language statements interleave portions of a source language statement.