Engr 664: Theory of Concurrent Programming
Fall Semester 1999
Lecture Notes


Motivation

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?


Copyright © 1999, H. Conrad Cunningham
Last modified: Wed Aug 18 20:43:50 1999