next up previous
Next: Issues to Consider When Up: The Essence of Concurrency Previous: A Simple Example

Another Simple Example

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:

tex2html_wrap_inline223

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 tex2html_wrap_inline231 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, tex2html_wrap_inline243 , each executing n statements what is the number of sequences of interleaved statements possible?



Norman Papernick
Thu Mar 21 14:23:15 EST 1996