\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage[unicode=true]{hyperref}
\hypersetup{
            pdftitle={Engr 664: Theory of Concurrent Programming Concurrent Programming Introduction, Fall 2016},
            pdfauthor={H. Conrad Cunningham, D.Sc. Department of Computer and Information Science The University of Mississippi},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{Engr 664: Theory of Concurrent Programming\\
Concurrent Programming Introduction, Fall 2016}
\author{\href{/~hcc/HOME_hcc.html}{H. Conrad Cunningham, D.Sc.}\\
\href{http://www.cs.olemiss.edu}{Department of Computer and Information
Science}\\
\href{http://www.olemiss.edu}{The University of Mississippi}}
\date{22 August 2016}

\begin{document}
\maketitle

\section{Concurrent Programming
Introduction}\label{concurrent-programming-introduction}

\subsection{Motivation}\label{motivation}

We can model the execution of a (sequential) program as a sequence of
\emph{atomic operations} from the program. Each operation atomically
changes the \emph{state} (i.e., the values of the variables) of the
program.

We can model the set of possible \emph{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
\emph{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):

\begin{verbatim}
        /* P1 */  x := y + z    ||    /* P2 */  y := z + x
\end{verbatim}

Assume that the two assignments are executed asynchronously on two
different processors. Also assume that the variables \texttt{x},
\texttt{y}, and \texttt{z} are shared between the processors.

On a typical machine, execution of \texttt{x\ :=\ y\ +\ z} would
correspond to execution of a sequence of atomic ``instructions'' such
as:

\begin{verbatim}
        /* P1 */  reg1 := y ;  reg1 := reg1 + z ;  x := reg1
\end{verbatim}

Similarly, execution of \texttt{y\ :=\ z\ +\ x} would correspond to
execution of the sequence:

\begin{verbatim}
        /* P2 */  reg2 := z ;  reg2 := reg2 + x ;  y := reg2
\end{verbatim}

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 \texttt{x}, \texttt{y}, and
\texttt{z} are 1, 2, and 3, respectively.

\begin{verbatim}
        /* 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
\end{verbatim}

Note that interleaving \#1 leaves shared variable \texttt{y} with the
value 4 and interleaving \#2 leaves \texttt{y} with the value 8. The
result depends upon the relative ordering of the assignment to
\texttt{x} in P1 and the reference to \texttt{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.

\subsection{Terminology}\label{terminology}

The following ``definitions'' are abstractions; in a specific situation
the terms may be used to denote slightly different concepts. Much of the
following is adapted from the book Concurrency in Programming and
Database Systems by Arthur J. Bernstein and Philip M. Lewis (Jones and
Bartlett, 1992) or other sources.

\subsubsection{Hardware}\label{hardware}

This section gives definitions for hardware concepts from the
perspective of programmers. These are not necessarily the definitions
that would be given in a computer architecture class.

A \emph{processor} is a physical device that executes operations
sequentially, atomically, and deterministically.

Note: Here we use the terms \emph{operation} and \emph{execute} in a
general sense. An example of a processor is a cpu that can execute
instructions.

\emph{Sequential} means that the processor executes no more than one
operation at any one time.

\emph{Atomic} means that, once the processor selects an operation for
execution, it executes the operation completely; the processor does not
interrupt an operation at an intermediate stage to execute another
operation.

In this context, \emph{deterministic} means that:

\begin{itemize}
\tightlist
\item
  each of the processor's operations performs a well-defined action that
  always produces the same result when operating on the same input data,
\item
  upon completion of the execution of an operation, the next operation
  to be executed is determined (except in the case of operations that
  halt the processor).
\end{itemize}

That is, if an operation execution is deterministic, its results are
predictable.

A \emph{control unit} for a processor controls the sequencing of
operations.

A \emph{control point} (or \emph{point of execution}) refers to each
operation in a ``program'' for the processor.

If an operation is eligible for execution, the associated control point
is \emph{enabled}.

When the processor executes an operation, the associated control point
is \emph{serviced}.

The control unit is usually driven by a \emph{clock}; the clock
generates a sequence of timing pulses that activates the portions of the
processor needed to carry out the operation being executed.

Primitive computers are constructed from a single processor with a
single control unit.

A computer is \emph{sequential} if no more than one control point can be
serviced at time.

A computer made up of only one processor is sometimes called a
\emph{uniprocessor}.

A common way to increase the power of a computer is to provide multiple
processors, each with its own control unit.

A computer is \emph{parallel} if multiple control points can be serviced
at the same time.

A shared memory multiprocessor (sometimes called a \emph{tightly coupled
multiprocessor}) is a parallel computer consisting of several processors
sharing a common memory. (The processors communicate by exchanging
information through the shared memory. Interprocessor communication is
fast, but contention for access to the shared memory can be costly. As a
result, this approach limits computers to a small number of processors.)

A \emph{multicore} computer is a shared memory multiprocessor in which
all processors are on the same electronic chip.

A \emph{multicomputer} (sometimes called a \emph{loosely coupled
multiprocessor} or an \emph{ensemble} computer) is a parallel computer
consisting of several processing nodes connected by high-speed message
switching hardware. (The processors communicate by sending messages
through the switching hardware. Communication among processors is more
costly than with shared memory, but memory contention is avoided.)

A \emph{distributed computer system} is a geographically dispersed group
of computers connected by a communication network. (The processors
communicate by sending messages through the network. Communication among
processors is usually more costly than with a multicomputer.)

Two processors are \emph{synchronous} if their operations are driven by
a common clock. Otherwise, they are \emph{asynchronous}.

Asynchronous processors can explicitly synchronize their execution from
time to time.

\subsubsection{Software}\label{software}

A \emph{program} is a finite description of a task in some programming
language.

An \emph{address space} is the collection of all the variables that a
program references.

The \emph{program state} is the mapping of the variables in an address
space to their values.

A program is \emph{concurrent} if during its execution multiple control
points can be enabled at the same time.

A program is \emph{sequential} if during its execution no more than one
control point can be enabled at a time.

In essence, sequential programs form a special class of concurrent
programs.

Note: Concurrent programs are sometimes called \emph{parallel programs}.
Here we tend to use the term \emph{concurrent} to describe logically or
potentially simultaneous activities and \emph{parallel} to describe
physically simultaneous activities.

A \emph{process} is an agent that

\begin{itemize}
\tightlist
\item
  executes operations on a processor in an address space,
\item
  has a unique associated control point that designates the next
  operation it will execute.
\end{itemize}

Note: A processor is a physical device; a process is a logical
processor.

The above definition is for what some writers call a \emph{sequential
process}; they use the term \emph{process} to describe a more general
concept.

A program is \emph{determinate} if it always produces the same result
when executed from the same initial state. (In this definition we
consider just the external effects of the execution---the relationship
between ``inputs'' and ``outputs''.)

A program is \emph{indeterminate} if it can produce an unpredictable
result when executed from some initial state.

A program is \emph{deterministic} if its control points are always
serviced in the same sequence when execution is started from the same
initial state. (In this definition we consider the internal effects of
the execution---the order in which operations are executed.)

A program is \emph{nondeterministic} if its control points are serviced
in an unpredictable sequence when execution is started from some initial
state.

Note: A program may be nondeterministic but still determinate. In such a
case, each of the alternative execution sequences produce the same
result.

Note: Nondeterministic is not the same as random. Nondeterministic means
that something is unpredictable; in general, probabilities cannot be
assigned to the alternatives.

In a context where a system must repeatedly choose among alternatives,
\emph{fairness} means that no alternative will be postponed forever. For
example, a fair execution of a concurrent program may mean that any
continuously enabled control point will eventually be serviced.

A concurrent program is \emph{asynchronous} if, given the identity of
one enabled control point, we cannot infer the identities of the others.
That is, the concurrent processes are not executed in lock-step; they
can be executed on separately clocked processors.

A concurrent program is \emph{synchronous} if, given the identity of one
enabled control point, we can always infer the identity of the remaining
enabled control points.

We sometimes distinguish between a program and its
\emph{environment}---the other agents (i.e., programs, devices, and
people) with which the program interacts during its execution.

A \emph{transformational program} interacts with its environment only at
initiation and termination. It can be specified in terms of its initial
and final states.

A \emph{reactive program} interacts with its environment throughout
execution. For some reactive programs (e.g., operating systems)
termination may be considered an abnormal occurrence. Thus reactive
program cannot be specified purely in terms of initial and final states.

In essence, a transformational program is a special case of a reactive
program.

A system (e.g., a program) is \emph{open} if it can interact with
(perhaps unknown) agents in its environment; otherwise, the system is
\emph{closed}.

A \emph{concurrent programming language} consists of two components
(often integrated into a single language):

\begin{itemize}
\tightlist
\item
  a \emph{computation language} to compute values and manipulate local
  data objects,
\item
  a \emph{composition} (or \emph{coordination}) \emph{language} to
  combine programs into more complex programs.
\end{itemize}

Why develop concurrent programs?

\begin{itemize}
\tightlist
\item
  to get results faster---concurrent programs can be executed in
  parallel iIn particular, to better take advantage of the processor
  ``cores'' available)
\item
  to express programs more naturally---the universe is naturally
  parallel place
\item
  to have fun!? :-)
\end{itemize}

\end{document}