Consider the simultaneous execution of the following three programs on three processors:

Processor 1 a. A:=1 b. Print B, C

Processor 2 c. B:=1 d. Print A, C

Processor 3 e. C:=1 f. Print A,B

Assume A, B, C, are shared writable variables in memory (initially A=B=C=0 )

Assume atomic memory access operations. Answer the following with reasoning or supported by computer simulation results:

a) List the 90 execution interleaving orders of the six instructions {a,b,c,d,e,f} which will preserve the individual program orders. The corresponding output patterns (6-tuples) should be listed accordingly.

b) Can all 6-tuple combinations be generated out of the 720 non-program-order interleavings? Justify the answer with reasoning and examples.

c) We have assumed atomic memory access in this exercise. Explain how the output 011001 for the above is not possible in an atomic memory multiprocessor system if individual orders are preserved.