% Engr 664: Theory of Concurrent Programming \
  Motivation, Fall 2016  
% [H. Conrad Cunningham, D.Sc.](/~hcc/HOME_hcc.html) \
  [Department of Computer and Information Science](http://www.cs.olemiss.edu) \
  [The University of Mississippi](http://www.olemiss.edu)  
% 22 August 2016 


# 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.