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?