3.2 What is Concurrent Programming?

Until now, we have been exclusively concerned with sequential programs that execute a single stream of operations. Even the GUI programming in the previous section avoided concurrent execution by terminating the controller as soon as it finished setting up the model and view. Concurrent computation makes programming much more complex. In this section, we will explore the extra problems posed by concurrency and outline some strategies for managing them.

In a concurrent program, several streams of operations may execute concurrently. Each stream of operations executes as it would in a sequential program except for the fact that streams can communicate and interfere with one another. Each such sequence of instructions is called a thread. For this reason, sequential programs are often called single-threaded programs. When a multi-threaded program executes, the operations in its various threads are interleaved in an unpredictable order subject to the constraints imposed by explicit synchronization operations that may be embedded in the code. The operations for each stream are strictly ordered, but the interleaving of operations from a collection of streams is undetermined and depends on the vagaries of a particular execution of the program. One stream may run very fast while another does not run at all. In the absence of fairness guarantees (discussed below), a given thread can starve unless it is the only ``runnable'' thread.

A thread is runnable unless it executes a special operation requiring synchronization that waits until a particular condition occurs. If more than one thread is runnable, all but one thread may starve (make no progress because none of its operations are being executed) unless the language makes a fairness guarantee. A fairness guarantee states that the next operation in a runnable thread eventually will execute. The Java language specification currently makes no fairness guarantees but most Java Virtual Machines guarantee fairness.

Threads can communicate with each other in a variety of ways that we will discuss in detail later in this section. The Java programming language relies primarily on shared variables to support communication between processes, but it also supports an explicit signaling mechanism.

In general, writing concurrent programs is extremely difficult because the multiplicity of possible interleavings of operations among threads means that program execution is non-deterministic. For this reason, program bugs may be difficult to reproduce. Furthermore, the complexity introduced by multiple threads and their potential interactions makes programs much more difficult to analyze and reason about. Fortunately, many concurrent programs including most GUI applications follow stylized design patterns that control the underlying complexity.

To demonstrate some of the subtle problems that arise with this sort of programming, consider the following example. We have two threads, A and B, that both have access to a variable ct. Suppose that, initially, ct is 0, but there are places in both A and B where ct is incremented.

A	B
...	...
ct++;	ct++;

To increment a variable x, (i) the value v of x must be fetched from memory, (ii) a new value v' based on v, and (iii) v' must be stored in the memory location allocated to variable x. These are three separate actions, and there is no guarantee that no other thread will access the variable until all three are done. So it's possible, for instance, that the order of operations from these two threads occurs as follows:

fetches ct = 0
B fetches ct = 0
A computes the value ct++ = 1
A stores the value 1 in ct
B computes new value ct++ = 1
B stores the value 1 in ct

With this order of the operations, the final value for ct is 1. But in other possible orderings (e.g., if A performs all of its actions first), the final value would be 2.

A simple strategy for preventing this form of interference (often called a race condition) is to make the entire access/modify/store cycle for updating shared variables atomic, despite the fact that the cycle is performed using several machine instructions. Atomic operations appear to execute as a single machine instruction because all other threads are forced to pause executing while the atomic operation executes. As a result, it is impossible for another thread to observe the value of the updated variables while the operation is in progress. A block of code that requires atomic execution is called a critical section. Some programming languages that support concurrency include begin/end brackets for enclosing critical sections.

The critical section mechanism works well in the context of running multi-threaded programs on a computer with a single processor (a uniprocessor) since it reduces to ensuring that a critical section is not interruptible (permitting another thread to run). But it is clumsy and inefficient on a multiprocessor because it forces all processors but one to stop execution for the duration of a critical section. (Existing virtual machines treat new operations that force garbage collection as critical sections.

A much better mechanism for preventing interference in concurrent programs that may be executed on multiprocessors is locking data objects. When a data object is locked by a thread, no other thread can access or modify the data object until the locking thread releases it. In essence, locking relaxes the concept of atomic execution so that it is relative to a particular object. Threads can continue executing until they try to access a locked object.

Java relies on object locking to prevent interference. An object can be locked for the duration of a method invocation simply by prefixing the method declaration with the work synchronized. For instance, to define a synchronized increment method, we would write:

synchronized void inc() { ct++; }

We can also declare static methods to be synchronized, which locks the class object (which contain all of the static variables of the class) rather than an instance object.

An unusual feature of Java's lock mechanism is the fact that locking an object only inhibits the execution of operations that are declared as synchronized. Methods that are not declared as synchronized will be executed even when an object is locked! There is a strong argument for this capability: it supports the definition of classes that partition operations in two groups: those that require synchronization and those that do not. But it also invites subtle synchronization bugs if the synchronized modifier is inadvertently omitted from one method definition.

Of course, concurrency only arises in Java when a program uses more than one thread. To support the explicit creation of new threads, Java includes a built-in abstract class Thread, that has an abstract method run(). We can make a new thread by (i) defining a class extending Thread that defines the method run(), (ii) constructing a new instance of this class, and (iii) calling the start() method on this new instance. The start() method actually creates a new thread corresponding to the receiver object (a Thread) and invokes the run() method of that thread, much as the main() method is invoked in the root class when you run a Java Virtual Machine. For example,

class Foo extends Thread {
  // must have
  public void run() { 
  ... 
  }
}

When a constructor for Foo is called, all of computation for the object allocation and constructor invocation is performed in the current thread; a new thread is not created until the start() method is invoked for a Thread() object. To create and start a new Foo thread, the current thread can simply execute the code

Thread t = new Foo();
t.start();

Alternatively, the current thread can execute the run() method of the Thread object t simply by performing the operation

t.run()

instead of

t.start()

Assume that a new Foo thread t has been created and started. At some point in the execution of the original thread (now running concurrently with thread t) can wait for thread t to terminate by executing the method invocation:

t.join();
// waits for the thread object to terminate.

So we can view the relationship of the two threads of control as follows:

main
  |
t.start
  |\
  | \
  | |
  | /
  |/
t.join
  |
  |

Synchronizing multiple threads does incur some overhead. For example, consider the following Java code:

class PCount extends Thread {

  // ** fields ***
  static int sharedCtr = 0;
  static final int cntPerIteration = 100000;
  static final int noOfIterations = 10;
  
  int id; 

  // ** constructors **
  PCount(int i) { id = i; }

  // ** methods **
  void inc() {
    sharedCtr++;
  }
  public void run() {
    for (int i = 0; i < cntPerIteration; i++) inc();
    System.out.println("Iteration #" + id + 
      " has completed; sharedCtr = " + sharedCtr);
  }

  public static void main(String[] args) 
      throws InterruptedException {
    Thread[] tPool = new Thread[noOfIterations];
    for (int j = 0; j < noOfIterations; j++) {
      tPool[j] = new PCount(j);
    }
    for (int j = 0; j < noOfIterations; j++) {
      tPool[j].start();
    }
    for (int j = 0; j < noOfIterations; j++) {
      tPool[j].join();
    }
    System.out.println("Computation complete.  sharedCtr = " 
      + sharedCtr);
  }
}

In each iteration, main creates a new thread. Afterwards, all are synchronized and a final value is determined.

The counter is not locked in this example, and so updates may be lost because of the problems described above. The likelihood with which update losses may occur varies depending on the number of threads. For example, in a test that I ran a few months ago

• for 1 million iterations, the program 65
• for 100,000 iterations, the program lost none.

Apparently, even with 100,000 threads, each iteration occurred within a single time slice.

Synchronizing the threads fixes the problem of lost updates, but it really slows the program down; even for 100,000 iterations.

In modern event-handling models such as those in Java and DrScheme, we have a single event handler that executes events serially. This protocol saves the overhead of synchronization and eliminates potential deadlocks (which we will discuss later).