We can model the execution of a (sequential) program as a sequence of atomic operations from the program. Each operation atomically changes the state (i.e., the values of the variables) of the program.
We can model the set of possible asynchronous parallel executions of two programs as the set of all interleavings of the sequences of atomic operations from the two programs. A particular parallel execution corresponds to one of the interleavings, the choice of which is nondeterministic (i.e., unpredictable by the programmer). The nondeterministic interleaving models the nondeterministic relative speeds of the executions of the two programs.
Note: By interleaving, we mean a merge of the two sequences in which the relative order of elements in each sequence is preserved. Picture the shuffling of two decks of cards into one.
Consider the parallel execution of the following two assignment statements (identified as programs P1 and P2, respectively):
/* P1 */ x := y + z || /* P2 */ y := z + x
Assume that the two assignments are executed asynchronously on two
different processors. Also assume that the variables x,
y, and z are shared between the processors.
On a typical machine, execution of x := y + z would
correspond to execution of a sequence of atomic "instructions" such
as:
/* P1 */ reg1 := y ; reg1 := reg1 + z ; x := reg1
Similarly, execution of y := z + x would correspond to
execution of the sequence:
/* P2 */ reg2 := z ; reg2 := reg2 + x ; y := reg2
There are 20 different ways that these two sequences might be interleaved. A parallel execution of the two sequences might correspond to any of the possible interleavings. The final values of the shared variables will be different depending upon which interleaving models the execution.
For example, consider the following interleavings of programs P1
and P2 where the initial values of the variables x,
y, and z are 1, 2, and 3, respectively.
/* P1 */ reg1 := y ; reg1 := reg1 + z ; x := reg1
/* P2 */ reg2 := z ; reg2 := reg2 + x ; y := reg2
Interleaving #1 Interleaving #2
/* P1 */ reg1 := y ; /* P1 */ reg1 := y ;
/* P2 */ reg2 := z ; /* P1 */ reg1 := reg1 + z ;
/* P1 */ reg1 := reg1 + z ; /* P2 */ reg2 := z ;
/* P2 */ reg2 := reg2 + x ; /* P1 */ x := reg1 ;
/* P1 */ x := reg1 ; /* P2 */ reg2 := reg2 + x ;
/* P2 */ y := reg2 /* P2 */ y := reg2
Note that interleaving #1 leaves shared variable y
with the value 4 and interleaving #2 leaves y with the
value 8. The result depends upon the relative ordering of the
assignment to x in P1 and the reference to
x in P2. The result is time dependent and outside of the
programmer's control: the relative execution speeds of P1 and P2
affect the final values of the variables.
As the above example illustrates, the result of parallel execution of statements is, in general, indeterminate because of the nondeterministic order of operations on shared data. A key problem in concurrent programming is thus finding a way to tame the nondeterminism without sacrificing the benefits of parallel execution.
UP to Lecture Notes menu?