Suppose again P and Q share the variable x, initialized to 0. Suppose P executes the code (as before):
x := 1
x := x +1
and Q executes just the statement:
x := 59
You should convince yourself that the strongest assertion about the value of x you can make at the end of P || Q is:
Each possible final value corresponds to one of the possible interleavings of the statements executed by P and Q. Note that each process executes its code sequentially; hence, it's impossible for x to be 1 at the end, which could occur if all statement interleavings were allowed. (We're also assuming each process terminates so So as the number of statements increase, the number of possible interleavings (and hence the number of possible final values) increase.
Exercise 1: Given that P executes m statements and Q executes n statements, what is the number of sequences of interleaved statements possible? (Don't worry about distinguishing between interleavings that might lead to the same final values of any shared variables.)
Exercise 2: Given that there are i processes, , each executing n statements what is the number of sequences of interleaved statements possible?