Concurrent Programming

Keywords and phrases Pipelines, parallel processes, message passing, monitors, concurrent programming, safety, liveness, deadlock, live-lock, fairness, communication, synchronization producer-consumer, dining philosophers.

There are several reasons for a programmer to be interested in concurrency:

1. To better understand computer architecture  (it has a great deal of concurrency with pipelining (multiple steps) and super-scalar (multiple instructions)) and
2. compiler design,
3. some problems are most naturally solved by using a set of co-operating processes,
4. A sequential solution constitutes over specification, and
5. to reduce the execution time.

Sequential operations:

   --O-O-O-O--> 

      -O-O-
   --|     |-->  
      -O-O-

Aside. The terms, concurrent, distributed and parallel have a been used at various times to describe various types of concurrent programming. Multiple processors and disjoint or shared store are implementation concepts and are not important from the programming language point of view. What matters is the notation used to indicate concurrent execution, communication and synchronization.

Functional and logic programming languages do not necessarily need explicit specification of concurrency and, with a parallelizing compiler, may be executed on parallel hardware. It is important to note that the notion of processes is orthogonal to that of inference, functions and assignments.

Aside. Processes which share an address space are called threads or light-weight processes. For some programming languages (C, C++) there are threads packages to permit concurrent programming. In other cases, the operating system (Microsoft Windows NT, Sun Solaris) provides system calls for threads. Processes which do not share an address space are called heavy-weight processes. The Unix family of operating systems provide a system call to allow programmers to create heavy-weight processes.

The Concurrent Nature of Systems

Co-operation

The Secretary. scheduling, priority, co-operative multitasking, interrupts, competitive multitasking, pre-emptive multitasking

The Secretarial Pool parallel tasking

Geoffrey Fox's wall. the construction of a brick wall by a number of workers.

Questions:

• How do we break down the task to extract maximum parallelism?
• Wow do we get the task done in the shortest possible time with a given number of workers.
• What is the minimum amount of supervision needed?
• Can all workers be kept equally busy?
• Does the task demand specialized workers?
• Can we maintain efficiency as either the size of the problem or the number of workers grows?

The Nature of Concurrent Systems

Abstraction

Performance

Communication

Behavior

Synchronization and Communication

Live-lock may result if there are more than one waiting process and when the signal is received access is not granted fairly.

Starvation: (live-lock) multiple processes waiting for access but access is not provided in a fair manner

Coroutines.

Real-time Programming language issues

When message passing is asynchronous, synchronization can be obtained by requiring a reply to a synchronizing message. In the examples that follow, synchronized message passing is assumed.

Communication commands in the guards. Most communication based programming languages permit input commands in the guards but not output commands. The asymmetry is due to the resulting complexity required to implement output commands in the guards.

process Q;
const qsize = 10;
var head, tail : integer;
   queue : array[0..qsize-1] of integer;

begin                        
    head,tail := 0,0;
    *[ head != tail, C?X --> C!queue[head]; head := (head + 1) mod qsize 
      [] head != (tail+1) mod qsize, P?X --> queue[tail],tail := X, (tail + 1) mod qsize]
end;

process P;
begin
   *[ true --> produce(X); Q!X]
end;

process C;
begin
   *[ true --> Q!X, Q?X; consume(X)]
end;


begin
[ P || C || Q ]
end.

Nondeterminism

A program is nondeterministic if it has more than one allowable evaluation strategy and different evaluation strategies lead to different results.

A concept related to nondeterminism is parallel evaluation Parallel evaluation that does not involve interaction on the part of its subparts is called noninterfering parallelism. Processes which have disjoint address spaces cannot interfere with each other and thus can operate without fear of corrupting each other. For example, the two processes in

Another example of non-interfering processes is found in matrix multiplication. When two matrices are multiplied, each entry in the product matrix is the result of multiplying a row times a column and summing the products. This is called an inner product. Each inner produce can be computed independently of the others. Figure~\ref{cp:mm}

# multiply n by n matrices a and b in parallel 
# place result in matrix c 
# all matrices are global to multiply 
process multiply( i := 1 to n, := 1 to n) 
   var inner_prod := 0 
   fa k := 1 to n -> 
      inner_prod := inner_prod + a[i,k]*b[k,j] 
   af
   c[i,j] := inner_prod 
end

In interfering parallelism, there is interaction and the relative speeds of the subparts can affect the final result.

Processes that access a common address space may interfere with each other. In this program,

A language is concurrent if it uses interfering parallelism.

Sequential programs are nearly always deterministic. A deterministic program follows a sequence of step that can be predicted in advance. Its behavior is reproducible and thus, deterministic programs are testable. Concurrent programs are likely to be nondeterministic because the order and speed of execution of the processes is unpredictable. This makes testing of concurrent programs a difficult task.

The requirement for disjoint address space may be too severe a requirement. What is required is that shared resources may need to be protected so that only one process is permitted access to the resourse at a time. This permits processes to cooperate, sharing the resource but maintaining the integrity of the resource.

Mutual Exclusion

• At most one process has access
• If there are multiple requests for a resource, it must be granted to one of the processes in finite time.
• When a process has exclusive access to a shared resource it release it in finite time.
• When a process requests a resource it must obtain the resource in finite time.
• A process should not consume processing time while waiting for a resource.

Deadlock

Deadlock can occur in a system of processes and resources if, and only if, the following conditions all hold together.

• Mutual exclusion: processes have exclusive access to the resources.
• Wait and hold: processes continue to hold a resource while waiting for a new resource request to be granted.
• No preemption: resources cannot be removed from a process.
• Circular wait: there is a cycle of processes, each is awaiting a resource held by the next process in the cycle.

A second approach is to allow deadlocks to occur but detect and recover automatically. Once deadlock is detected, processes are selectively aborted or one or more processes are rolled back to an earlier state and temporarily suspended until the danger point is passed. This might not an acceptable solution in real-time systems.

A third approach is to prevent deadlock by weakening one or more of the conditions. The wait-and-hold condition may be modified to require a process to request all needed resources at one time. The circular-wait condition may be modified by imposing a total ordering on resources and insisting that they be requested in that order.

Another example of a liveness problem is live-lock (or lockout or starvation). Live-lock occurs when a process is prevented from making progress (other processes are running). This is an issue of fairness.

Scheduling

Semantics

Concurrency in Programming Languages

 From the programmer's point of view, concurrent programming notations allow programs to be structured as a set of possibly interactive processes. Such an organization is particularly useful for operating systems, real-time control systems, simulation studies, and combinatorial search applications.

To permit the effective use of multiple processes, concurrent programming languages must provide notations for:

1. Concurrent execution: A notation that denotes operations that could be, but need not be, executed in parallel.

PCN                   Occam
[|| P1, P2, ..., Pn]    PAR
                          P1
                          ...
                          Pn

2. Communication: A notation that permits processes to exchange information either through shared variables (visible to each process) or a message passing mechanism.

Shared Memory

Assignment: X := E

Message Passing

Synchronous P_i!E, P_j?X

Asynchronous P_i!E, P_j?X

Remote procedure call

3. Synchronization: A notation to require a process to wait for a signal from another process. In general processes are not independent. Often a process depends on data produced by another process. If the data is not available the process must wait until the data is available.
wait(P_i), signal(P_j)

A process can change its state to Blocked (waiting for some condition to change) and can signal Blocked processes so that they can continue.

In this case, the OS must provide the system calls BLOCK and WAKEUP. cking version of a semaphore

type semaphore = record
                     value : integer;
                     L : list of processes; // or queue blocked waiting for 
                 end;                       // the signal

down(S): S.value := S.value - 1;  // wait
         if S.value < 0 then
            add this process to S.L;
            block;
         end;

up(S): S.value := S.value + 1;    // signal
       if S.value <= 0 then
          remove a process P from S.L;
          wakeup(P);
       end;

Implementation
• Single processor: The normal way is to implement the semaphore operations (up and down) as system calls with the OS disabling the interrupts while executing the code.
• Multiprocessor: Each semaphore should be protected by a lock variable, with the TSL instruction used to be sure that only one CPU at a time examines the semaphore. Using the TSL instruction to prevent several CPUs from accessing the semaphore at the same time is different from busy waiting.
In many applications it is necessary to order the actions of a set of processes as well as interleave their access to shared resources. common address space, critical section protected by a monitor, synchronization provided through wait and signal.

Some alternative synchronization primitives are

• Semaphores
• Critical Regions
• Monitors
• Synchronized Message Passing
4. Mutual exclusion: A notation to synchronize access to shared resources.

semaphores

Monitors: One approach is to protect the critical section by a monitor. The monitor approach requires that only one process at a time may execute in the monitor.

monitor Queue_ADT
const qsize = 10;
var head, tail : integer;
   queue : array[0..qsize-1] of integer;
   notempty, notfull : condition;
procedure enqueue (x : integer);
   begin
      [ head=(tail+1) mod qsize --> wait(notfull)
      [] head!=(tail+1) mod qsize --> skip];
      queue[tail],tail := x, (tail + 1) mod qsize
      signal(notempty)
   end;
procedure dequeue (var x : integer);
   begin
      [ head=tail --> wait(notempty)
      [] head!=tail --> skip];
      x,head := queue[head],(head + 1) mod qsize;
      signal(notfull)
   end;
begin                        
    head,tail := 0,0;
end;
begin                        
 [ produce(x); enqueue(x) || dequeue(y); consume(y) || dequeue(y); consume(y)] 
end.

• Correctness (safety and liveness)
• Performance
• Architecture
• Implementation

Aside.

concurrency: Fork (P) & Join (P)

Producer-Consumer

const qsize = 10;
var count:integer;
   queue : array[0..qsize-1] of integer;
procedure enqueue (x : integer);
   begin
       *[ head=(tail+1) mod qsize --> skip]; 
      queue[tail],tail := x, (tail + 1) mod qsize
   end;
procedure dequeue (var x : integer);
   begin
       *[ head=tail --> skip]; 
      x,head := queue[head],(head + 1) mod qsize
   end;
begin                        
 head,tail := 0,0;
 [ *[produce(x); enqueue(x)] || *[dequeue(y); consume(y)]] 
end.

Shared Memory Model

• Static
• Dynamic

• Named
• Anonymous

• Semaphore
• Monitor

Some alternative synchronization primitives are

• Semaphores
• Critical Regions
• Monitors
• Synchronized Message Passing

monitor Queue_ADT
   const qsize = 10;
   var count:integer;
      queue : array[0..qsize-1] of integer;
   procedure enqueue (x : integer);
      begin
          *[ head=(tail+1) mod qsize -> skip]; 
         queue[tail],tail := x, (tail + 1) mod qsize
      end;
   procedure dequeue (var x : integer);
      beg\=in
          *[ head=tail -> skip]; 
         x,head := queue[head],(head + 1) mod qsize
      end;
   begin                        
       head,tail := 0,0;
   end;
begin                        
    [ produce(x); enqueue(x) $\parallel$ dequeue(y); consume(y) $\parallel$ dequeue(y); consume(y)] 
end.

Message Passing Model

• Static
• Dynamic

• Named
• Anonymous

• Synchronous
• Asynchronous

• Unidirectional
• Bidirectional

Hardware

• Process: single flow of control through a set of instructions
• Processor: hardware device for executing
• Parallel computer: two or more processors connected through an interconnection network.

System classification by number of instruction and data streams.

• SISD: classical sequential von Neumann machine.  Inherently sequential.  Parallelism may be simulated by interleaving instructions & multiprogramming.
• Pipelining and vector architectures
• SIMD: synchronous since there is a single instruction stream, each processor has its own data stream.  Matrix operations are a good example.  Thinking Machines - CM, Maspar Computer Corp -- MP (single sequencing units)
• MISD: does not seem to be useful
• MIMD/SPMD: asynchronous processes but with occasional pauses to synchronize; Intel iPSC, nCUBE, Sequent Symmetry, SGI Onyx, SUN MP system
• shared-memory (sometimes called multiprocessors) locking and protection mechanism
• distributed-memory (sometimes called multicomputers) message passing

• Bus-based architectures
• Cache coherence -- for bus based systems use the snoopy protocol
• Switch-based architectures, crossbar switch
• NUMA - nonuniform memory access

• Dynamic interconnection networks
• Static interconnection networks
• linear array, 2D mesh, 3D mesh
• ring, torus
• hypercube
• bus

• routing
• store-and-forward

cut-through

The Engineering of Concurrent Programs

• Programming Behavior of processes and their interconnection
• Network description Processors and their interconnection
• Configuration Mapping of software onto hardware

Programming

The way to design parallel software is to begin with the most parallel algorithm possible and then gradually render it more sequential ... until it suits the machine on which it is to run.
East (1995)

• Shared definition variables (single assignment) -- X=Exp,
• Parallel composition -- [||P₀,...,P_n],
• Choice composition -- [? G₀ -> P₀,..., G_n -> P_n],
• Sequential composition -- [; S₀,...,S_n], and
• Recursion -- name(parameters) composition expression

If a program that uses only parallel and choice composition and definition variables does not have adequate efficiency, ...
We use the following steps in the introduction of mutables and sequencing into a parallel block.

1. We order the statements in a parallel block so that all variables that appear on the right-hand sides of definition statements reduce to ground values or tuples, and all guards reduce to the ground values true or false, give only the definitions established by statements earlier in the ordering. In other words, we order statements in the direction of data flow; statements that write a variable appear earlier than statements that read that variable. Then we convert the parallel block into a sequential block by replacing "||" by ";" retaining the data-flow order of statements.
2. Next, we introduce mutables, add assignment statements to our program, and show that the mutable m has the same value as the definition variable x it is to replace, at every point in the program in which x is read - i.e., where x appears on the right-hand side of a definition statement or assignment or guard.
3. Finally, we remove the definition variables that are replaced by mutables, secure in the knowledge that the mutables have the same value as the definition variables in the statements in which they are read. We must, of course, be sure that mutables shared by constituent blocks of a parallel block are not modified within the parallel block.

Chandy and Taylor (1992)

Decomposition

Function decomposition

Advantages
Disadvantages

• Fewer tasks than workers
• Some tasks are easier than others

Domain decomposition

• Horizontal domain decomposition: group is responsible for the entire project.
• Vertical domain decomposition: Assembly line, pipelining

Communication and Synchronization

Alternation and Competition

• Scheduling
• Co-operative multitasking: multi-person game, using the copy machine
• Priority: telephone vs email
• Competitive multitasking: time slice
• Client-server: bakery
• Busy waiting
• Fairness

Correctness

Chandy & Taylor (1992) require

1. Shared mutable variables remain constant during parallel composition.
2. Mutable variables to copied when used in definitions.
3. When defined, definition variables act as constants in assignment.

1. it must be defined before it is referenced,
2. it must be referenced before it is updated, and
3. only one process at a time may (re)define it.

Correctness issues in the design of concurrent programs fall in one of two categories: safety and liveness.

• Safety: nothing bad will happen. For example, access to a shared resource like a printer requires that the user process have exclusive access to the resource. So there must be a mechanism to provide mutual exclusion.
• Liveness: something good will happen. On the other hand, no process should prevent other processes from eventual access to the printer. Thus any process which wants the printer must eventually have access to the printer.

Network description

Configuration

Implementation

Historical Perspectives and Further Reading

Concurrency occurs in hardware when two or more operations overlap in time. Concurrency in hardware dates back to the 1950s when special-purpose processors were developed for controlling input/output devices. This permitted the overlapping of CPU instructions with I/O actions. For example, the execution of an I/O instruction no longer delayed the execution of the next instruction. The programmer was insulated from this concurrency by the operating system. The problems presented to the operating systems by this concurrency and the resulting solutions form the basis for constructs supporting concurrency in programming languages. Hardware signals called interrupts provided the synchronization between the CPU and the I/O devices.

Other advances in hardware have lead to the the development of alternative architectures. Pipeline processors which fetch the next instruction while the first instruction is being decoded. Super scalar processors combine multiple pipelines to provide an even greater level of concurrency. Array processors provide a large number of identical processors that operate simultaneously on different parts of the same data structure. Data flow computers aim at extracting maximum concurrency from a computation by performing as much of the computation in parallel as possible. Connectionism based hardware models provide concurrency by modeling computation after the neural networks found in the brain.

Interrupts together with a hardware clock made it possible to implement multiprogramming systems which are designed to maximize the utilization of the the computer systems resources (CPU, store, I/O devices) by running two or more jobs concurrently. When one job was performing I/O another job could be executing using the CPU.

Interrupts and the hardware clock also made possible the development of interactive systems where multiple users have simultaneous access to the system resources. Such a system must provide for a large number of jobs whose combined demands on the system may exceed the system resources. Various techniques of swapping and paging meet this need by moving jobs in and out of the store to the larger capacity of backing store devices. With the increase of jobs comes the need to increase the capacity of the CPU. The solution was to develop multiprocessor systems in which several CPUs are available and simultaneously operate on separate jobs in the shared store.

An alternate solution is to develop distributed systems consisting of several complete computers (each containing both CPU and an associated store) that can operate independently but also communicate efficiently. Such systems of local area networks permit the efficient use of shared resources (such as printers and large backing store via file servers) and increase the computational throughput of the system.

Andrews, Gregory R. and Olsson, Ronald A. (1993)

 The SR Programming Language, Benjamin/Cummings, Redwood City, CA.

Ben-Ari, M. (1990)

 Principles of Concurrent and Distributed Programming, Prentice Hall International, Hemel Hempstead, Hertfordshire.

Chandy, K. Mani and Taylor, Stephen (1992)

An Introduction to Parallel Programming Jones and Bartlett, Boston.

East, Ian. (1995)

Parallel Processing with Communicating Process Architecture, UCL Press, London, England.

Foster, I. (1996)

Compositional Parallel Programming Languages TOPLAS Vol 18 No. 4 (July 1996): pp. 454-476.

Hehner, Eric C. R. (1993)

A Practical Theory of Programming Springer-Verlag, New York.

Lewis, Ted G. (1993)

Foundations of Parallel Programming: A Machine Independent Approach IEEE Computer Society Press, Los Alamitos, CA.

Pacheco, Peter S. (1997)

Parallel Programming with MPI Morgan Kaufmann Publishers Inc., San Francisco, CA.

Watt, David A. (1990)

Programming Language Concepts and Paradigms, Prentice-Hall International, Hemel Hempstead, Hertfordshire.

Exercises

• Producer-Consumer/Bounded Buffer (Models race conditions) Producers create data elements which are placed in a buffer. The consumers remove data elements from the buffer and perform some internal computation. The problem is to keep the producer from overwriting full buffers and the consumer from rereading empty buffers.
• Readers and Writers (Models access to a database) A data object is shared among several concurrent processes. Some of which only want to read the content of the shared object, whereas others want to update (read and write) the shared object. The problem is insure that only one writer at a time has access to the object. Readers are processes which are not required to exclude one another. Writers are required to exclude every other process, readers and writers alike.
• The Dining Philosophers. (Models exclusive access to limited resources) N philosophers spend their lives seated around a circular table thinking and eating. Each philosopher has a plate of spaghetti and, on each side, shares a fork his/her neighbor. To eat, a philosopher must first acquire the forks to its immediate left and right. After eating, a philosopher places the forks back on the table. The problem is to write a program that lets each philosopher eat and think.

The philosophers correspond to processes and the forks correspond to resources.

A safety property for this problem is that a fork is held by one and only one philosopher at a time. A desireable liveness property is that whenever a philosopher wants to eat, eventually the philosopher will get to eat.

1. Solve the dining philosophers problem using a central fork manager (centralized).
2. Solve the dining philosophers problem where there is a manager for each fork(distributed).
3. Solve the dining philosophers problem where the philosophers handle their own forks (decentralized).
4. Solve the dining philosophers problem if the philosophers must acquire all the forks in order to eat (distributed mutual exclusion).
• Sleeping Barber The barber shop has one barber, a barber chair, and n chairs for waiting customers. The problem is to construct an appropriate simulation.
• Searching
1. Find the largest element in an unordered list
• Sorting
1. Merge sort: Your program should break the list into two halves and sort each half concurrently. While sorting, the two halves should be concurrently merged.
2. Parallel merge of sorted lists -- if X[i] should just precede Y[j], then X[i] should appear at Z[i+j-1].
3. Rank sort: X[i] has rank k if X has exactly k items less than X[i] i.e., X[i] should be placed in position k.
4. Insertion sort: value is placed into its place in the sorted list.
5. Exchange/Bubble sort: small values flow left and large values flow right.
6. Quicksort
7. Bitonic sort
• The N-body problem. The N-body problem is used in astrophysics to calculate the dynamics of the solar system and galaxies. Each mass in this problem experiences a gravitational attraction by every other mass, in proportion to the inverse square of the distance between the objects.
• The sieve of Eratosthenes. The sieve of Eratosthenes is a method of generating prime numbers by deleting composite numbers. This is done by the following beginning with two as the first prime:
1. Delete all multiples of the prime number other than the prime number.
2. Iterate with the next remaining number which is prime.
• Polynomial Multiplication -- initialize, form cross-product, sort by power, combine like powers
• The quadrature problem. The quadrature problem is to approximate the area under a curve, i.e., to approximate the integral of a function. Given a continuous, non-negative function f(x) and two endpoints l and r, the problem is to compute the area of the region bounded by f(x) the x axis, and the vertical lines through l and r. The typical way to solve the problem is to subdivide the regions into a number of smaller ones, using something like a trapezoid to approximate the area of each smaller region, and them sum the areas of the smaller regions.
• Matrix Operations.
1. Multiplication: AB = C where A is a p \times q matrix, B a q \times r matrix, C a p \times r matrix and C[i,j] = \sum_{k=1}^m A[i,k]B[k,j]
2. Triangularization: Triangularization is a method for reducing a real matrix to upper-triangular form. It involves iterating across the columns and zeroing out the elements in the column below the diagonal element. This is done by performing the following step for each column.
1. For each row r below the diagonal row d, subtract a multiple of row d from row r. The multiple is m[r,d]/m[d,d]; subtracting this multiple of row d has the effect of setting m[r,d] to zero.
3. Backsubstitution:
4. Gaussian elimination: Gaussian elimination with partial pivoting is a method for reducing a real matrix to upper-triangular form. It involves iterating across the columns and zeroing out the elements in the column below the diagonal element. This is done by performing the following three steps for each column.
1. Select a pivot element, which is the element in column d having the largest absolute value.
2. Swap row d and the row containing the pivot element.
3. For each row r below the new diagonal row, subtract a multiple of row d from row r. The multiple is m[r,d]/m[d,d]; subtracting this multiple of row d has the effect of setting m[r,d] to zero.
Assume the matrix is non-singular (the divisor is non-zero).
• Shortest Path between two vertices of a graph (edges are weighted).
• Traveling salesman problem. Find the shortest tour that visits each city exactly once.
• Dutch national flag. A collection of colored balls is distributed among N processes. There are at most N different colors of balls. The goal is for the processes to exchange balls so that eventually, for all i, process i holds all balls of color i. The number of balls in the collection is unknown to the processes.
• Distributed Synchronization
1. Write a program that polls N processes for yes or no votes and terminates when at least N/2 responses have been received. Assume N is even.
2. Repeat the previous exercise, but terminate when a majority of identical responses have been received. Assume N is even.
3. Random election of a leader amongst n processes. Create n processes. %Let each process flip a coin to decide whether the process wants to %contest the "elections". %Broadcast this to all other processes. Now, each process generates a random number to decide its "vote", and sends the "vote" to the process it is voting for. Each process counts its votes, and broadcasts the results to all other processes. Now everyone knows the leader. (May have to think of starting the process over again in case of a tie, or simply deciding that the process with the larger Id is the leader, or some such thing.) This is a rather silly problem, but it will help your to learn about broadcasts and synchronizing processes, both of which are extremely important for any kind of parallel programming.
• The eight-queens problem. The eight-queens problem is concerned with placing eight queens on a chess board in such a way that none can attack another. One queen can attack another if they are in the same row or column or are on the same diagonal.
• Miscellaneous
1. Sum a set of numbers
2. (Conway) Read 80-character records, write 125 character records. Add an extra blank after each input record. Replace every pair of asterisks (**) with an exclamation point (!).
3. (Manna and Pnueli) Compute (n k) = n(n-1)...(n-k+1)/k!
4. (Roussel) Compare the structure of two binary trees
5. (Dijkstra) Let S and T be two disjoint sets of numbers with s and t the number of elements respectively. Modify S and T so that S contains the s smallest members of S union T and t the t largest members of S union T.
6. (Conway) The game of life
7. (Hoare) Write a disk server that minimizes amount of seek time
8. Show that Lewis' flow-correctness rules are safety or liveness rules.
9. PCN is a single assignment language (in a single assignment language, the assignment of a value to a variable may occur just once within a program). In addition, when a program must reference an undefined variable, it waits until the variable becomes defined. Show that PCN programs satisfy Lewis' flow-correctness rules.