Java as a Concurrent Programming Language for Operating Systems and Related Courses

Abstract. One of the important features of the Java language is support for multithreaded (also called concurrent) programming. To avoid race conditions and corruption of shared data, threads in a concurrent program must be synchronized. This tutorial introduces the programmer to the proper use of multiple threads in a Java program, using sample programs to illustrate these concepts. This tutorial assumes a prior general knowledge of Java programming; the context and level of knowledge used in this tutorial is the equivalent of an undergraduate operating systems course.

Table of Contents.

  1. Introduction
  2. Starting Java Threads
  3. Thread States, Methods, Priorities
  4. volatile Modifier
  5. Race Conditions
  6. Synchronized Blocks
  7. Java 2 Platform Standard Edition 5.0
  8. Locks
  9. Monitors
  10. Condition Variables
  11. Semaphores
  12. Blocking Queues
  13. Java's Memory Model
  14. Before Java 2 Platform Standard Edition 5.0
  15. Message Passing
  16. Rendezvous
  17. Remote Method Invocation (RMI)
  18. References and Related Material
  19. Background Information

Introduction

One of the important features of the Java language is support for multithreaded (also called concurrent) programming.

This tutorial is an introduction to the use of multiple threads in a Java program and will appeal to systems or application programmers who want to learn about multithreaded Java programming.

A multithreaded program can take advantage of the additional CPUs in a shared-memory multiprocessor architecture in order to execute more quickly. The use of multiple threads can also simplify the design of a program. As an example, consider a server program in which each incoming client request is handled by a dedicated thread.

However, to avoid race conditions and corruption of shared data, the threads in a concurrent program must be properly synchronized. Many example programs are used in this tutorial to illustrate these concepts.

This tutorial assumes a prior general knowledge of Java programming; the context and level of knowledge used in this tutorial is the equivalent of an undergraduate operating systems course. For a more explicit explanation of the experience needed to get the most out of this tutorial, see Assumptions and Context below.

The two goals of this tutorial are to:

Assumptions and Context

Before we move into the nuts and bolts of concurrent programming, let's elaborate on the knowledge and experience necessary to effectively wring the most use from this tutorial.

To use this tutorial, we assume a general knowledge of concurrency issues, at a level that would be obtained in an undergraduate computer science operating systems course.

We also assume a familiarity with the following terms and concepts: multiple threads, shared data, race conditions, critical sections, mutual exclusion, monitors, and semaphores. Finally, you should have knowledge of object-oriented programming and sequential Java: classes, objects, interfaces, inheritance, polymorphism, packages, and exceptions.

For further reference, the section References and Related Material at the end of the tutorial includes online and print references on operating systems, concurrent programming, and the Java language.

All example Java programs in this tutorial have been executed on a PC running Knoppix version 3.7-2004-12-08-EN (kernel 2.4.27) of Linux (see www.knopper.net/knoppix/index-en.html), using Sun Microsystem's Java 2 Platform Standard Edition 5.0 for Linux build 1.5.0_04-b05 (available from http://java.sun.com/j2se/1.5.0/). This version uses native threads and therefore time slices them automatically. The programs have also been tested on a Sun Ultra Enterprise 450 Server running Solaris 8 using Java 2 Platform Standard Edition 5.0.

The examples are compiled and executed with the just-in-time compiler (JIT) disabled (command java -Xint) to facilitate the manifestation of race conditions in programs raceCondition.java and bankAccountsAuditor.java.

Download all the files (jar file) with one click: javaconcprog.jar.

Single text file listing of all program source code in alphabetical order of program file name, single text file of all program sample runs in alphabetical order of file name (for printing, for example).

Entire contents © 2002 Stephen J. Hartley. All rights reserved.

Stephen J. Hartley
Computer Science Department
Rowan University
Glassboro, NJ 08028
telephone: +1-856-256-4500, ext. 3895
e-mail: hartley@elvis.rowan.edu
home page: http://elvis.rowan.edu/~hartley/index.html

Starting Java Threads

There are two ways to start Java threads. One way is to subclass the Thread class.

class A extends Thread {
   public void run() {
      ... // code for the new thread to execute
   }
}
...
   A a = new A(); // create the thread object
   a.start();     // start the new thread executing
...

The second way is to implement the Runnable interface.

class B extends ... implements Runnable {
   public void run() {
      ... // code for the new thread to execute
   }
}
...
   B b = new B();            // create the Runnable object
   Thread t = new Thread(b); // create a thread object
   t.start();                // start the new thread
...

Program threadedPrimes.java demonstrates multithreaded prime number generation with one thread per number checked. Sample run threadedPrimes.txt shows the results. The Prime class is used. Sample run unitTestPrime.txt demonstrates unit testing of this class.

Program bigIntegerPrimes.java uses Java's BigInteger class to compute successive prime numbers from a given starting number using ``infinite precision'' (unlimited number of digits) arithmetic. At any time after executing this program, the user can hit the enter key to see how far the program has progressed passed its starting number. The prime numbers are computed in one thread while another thread waits for the user to hit the enter key. Using two threads results in a much simpler and cleaner design than using a single thread for both activities. Sample run bigIntegerPrimes.txt demonstrates unit testing of this class.

More information on threads is available in the last section.

Thread States, Methods, Priorities

Thread states are defined as:

Thread priorities (class variables) are:

Priority get and set instance methods include:

The JVM scheduler usually ensures that the highest priority thread is running on the CPU, pre-empting the currently running thread when necessary, but this is not a guarantee. (See page 415 of The Java Language Specification, found in the references section.)

A Java thread is interrupted when its interrupt() method is called by another thread. This call sets a flag in the interrupted thread that the latter can check periodically, allowing one thread to tell another thread to stop itself or return allocated resources if it is not in the middle of some critical operation. A thread should check its interrupt flag before or after such operations and take appropriate action when interrupted.

Time slicing of threads, done by the JVM, is also known as round robin scheduling. Most modern JVMs perform time slicing; those JVMs that use ``green'' threads do not. A green thread retains the CPU until it yields, terminates, suspends itself, or performs IO.

The javaconcprog.PseudoTimeSlicing class implements ``pseudo'' time slicing for green threads. Using this class does not guarantee time slicing, but it works in practice.

The following methods are static in class Thread and apply to the calling thread.

The public void run() method in a Thread or Runnable object can be invoked by any thread that has a reference to the Thread or Runnable object. So we prevent that at the beginning of the run() method with if (Thread.currentThread() != me) return;.

The following are instance methods (for example, t.start() in which t is a reference variable to a Thread object).

Examples

The following example programs demonstrate what we've just been covering.

Class javaconcprog.AgeRandom is statically imported and provides some utility class methods: age(), which returns the number of milliseconds since the program started, and random(range).

Program testTimeSlicing.java allows you to test a platform for green threads and automatic timeslicing. Sample run testTimeSlicing.txt shows the results on an automatic-timeslicing platform. With green threads, the output of the beeper threads would not be interleaved.

The program also tests the effectiveness of the javaconcprog.PseudoTimeSlicing class on a JVM using green threads. A command line argument to the testTimeSlicing.java program can be used to activate pseudo-timeslicing on a green thread JVM. When activated, the output of the beeper threads is interleaved.

If you are using a green thread JVM, then uncomment the calls to

PseudoTimeSlicing.activate();
in programs boundedBufferDriver.java, noRaceCondition.java, parallelPrimes.java, parallelSievePrimes.java, threadedPrimes.java, bigIntegerPrimes.java, quickSort.java, matrixMultiplication.java, adaptiveQuadrature.java, bankAccountsAuditor.java, and raceCondition.java since the points they illustrate depend on timeslicing of threads.

Program matrixMultiplication.java implements matrix multiplication with multiple threads and uses join() for synchronization to print the result only after all threads have finished. Sample run matrixMultiplication.txt illustrates using the program. Having a different thread compute each entry of the product matrix is not efficient; more efficient is dividing the matrices to be multiplied into blocks and creating threads to multiply the blocks (see the Exercise).

Program adaptiveQuadrature.java implements adaptive quadrature numerical integration with multiple threads and uses join() for synchronization. If the sum of the areas of the two sub-trapezoids shown in the figure below is not close enough to the area of the trapezoid containing them, two threads are spawned to repeat the calculation for each sub-trapezoid. The spawning thread cannot continue until each of the two spawned threads finishes. Sample run adaptiveQuadrature.txt shows the results.

adaptive quadrature graph

Exercise: Modify the matrix multiplication program matrixMultiplication.java so that the matrices to be multiplied are divided into blocks and threads are created to multiply the blocks.

volatile Modifier

The volatile modifier tells the compiler that the variable is accessed by more than one thread at a time and inhibits inappropriate code optimizations by the compiler, such as caching the value of the variable in a CPU register instead of updating main memory with each assignment to the variable. It also inhibits caching the value in a CPU cache in a shared-memory multiprocessor architecture. These imply that a write to a volatile variable is written directly to main memory and a read comes directly from main memory, bypassing CPU registers and CPU caches.

For example, suppose two threads share a flag variable whose initial value is true. One thread keeps computing stuff until the other thread sets the flag to false. This will not work correctly unless the flag is declared volatile. The value of the flag variable must not be cached in a CPU register or cache.

boolean flag = true;  // shared
...
public void run() {   // one thread
   while (flag) {
      ...;  // compute stuff
   }
}
...
public void run() {   // other thread
   ...
   flag = false;
   ...
}

The Java Language Specification guarantees that updates to any one shared variable by a particular thread are seen by other threads in the order performed by that particular thread. However, the JLS does not require other threads to see updates to different shared variables in the order performed by the updating thread unless the variables are declared volatile (see JLS, first edition, page 147).

Class BoundedBuffer in boundedBufferBusyWaiting.java implements a busy waiting bounded buffer for a producer and consumer. The producer thread deposits items; it busy waits for an empty slot if the bounded buffer fills up. The consumer thread fetches items; it busy waits for an item if the bounded buffer is empty. The following figure illustrates this interaction.

bounded buffer

The consumer thread must ``see'' the value and occupied fields updated by the producer thread in the exact order performed by the producer thread. If not, the consumer might read again an item from a buffer slot it has already read or read an invalid value from the buffer slot. This might happen if the consumer sees the occupied field as true while the value field still has an old or invalid value because the producer's write of `true' to the occupied field is seen by the consumer before the updated value field is seen by the consumer. Therefore, the value and occupied fields are declared volatile and are not cached in CPU registers or caches.

Program boundedBufferDriver.java creates the producer and consumer threads. Sample run boundedBufferBusyWaiting.txt shows the results of executing the program with the busy waiting bounded buffer class.

Race Conditions

Recall that if two threads execute n=n+1 on a shared variable n at about the same time, their load and store instructions might interleave so that one thread overwrites the update of the other.

This lost update, when it occurs, leads to an erroneous result and is an example of a race condition. Race conditions are possible when two or more threads share data, they are reading and writing the shared data concurrently, and the final result of the computation can vary, depending on which thread does what when. Some of the possible final results are correct and some are incorrect.

For example, two threads share the variable a whose initial value is 0. One thread performs the assignment a=1 and another thread performs at about the same time the assignment a=2. The final result, 1 or 2, is a race condition. Depending on the application, both might be correct.

However, suppose one thread performs the update a=a+1 and another thread performs at about the same time the update a=a+2. The final result is a race condition and could be 1, 2, or 3, only one of which is correct.

Program raceCondition.java demonstrates a lost update in which sum=fn(sum,m) plays the role of n=n+1. Sample run raceCondition.txt illustrates the results. Notice that the final resulting sum is incorrect.

In program bankAccountsAuditor.java, a race condition between an ATM thread and an Auditor thread in a bank exists. Sample run bankAccountsAuditor.txt shows the results. Notice that the total sum of money counted by the auditor is sometimes incorrect.

Class BoundedBuffer in boundedBufferSuspendResume.java shows we should not synchronize threads with suspend() and resume() because a race condition is possible. If we try to replace busy waiting with blocking in the bounded-buffer producer and consumer by having a thread suspend itself until resumed by the other thread, we run the risk of both the producer thread and the consumer thread becoming suspended, each waiting for the other to resume it.

This is called deadlock and can happen like this. Suppose the buffer is empty and the consumer tries to fetch an item from the buffer. Under round robin thread scheduling, it is possible for the consumer thread to lose the CPU after finding the buffer empty but before suspending itself. Suppose this happens. When the producer thread puts an item into the empty buffer, it resumes the consumer. However, the consumer has not yet suspended itself, so the resume has no effect. When the consumer next gets the CPU, it suspends itself, having ``missed'' the resume operation by the producer. If the producer fills up the buffer and then tries to deposit an item into the full buffer, it will suspend itself and remain blocked until resumed by the consumer fetching an item from the buffer. This will never happen since the consumer is suspended. Both threads remained suspended forever and we have a deadlock situation.

Since context switching (the result of one thread losing the CPU and and another thread getting it) is not controllable or predictable by the user, we can encourage context switching with Thread.yield() or, better, Thread.sleep(ms), as shown in the version of BoundedBuffer in boundedBufferForceDeadlock.java.

Program boundedBufferDriver.java creates the producer and consumer threads. Sample run boundedBufferSuspendResume.txt uses the suspend-resume version of BoundedBuffer in boundedBufferSuspendResume.java having no yield or sleep and shows no deadlock. Sample run boundedBufferForceDeadlock.txt, on the other hand, demonstrates a deadlock occurring when context switching is forced with sleep in the alternate version of BoundedBuffer in boundedBufferForceDeadlock.java.

Synchronized Blocks

Every Java object has a lock. A synchronized block uses an object's lock to act like a binary semaphore having initial value one. It solves the mutual exclusion critical section problem:

Object obj = new Object();
   ...
synchronized (obj) {  // in a method
   ... // any code, e.g., critical section
}

The synchronized method construct

   ... synchronized method(...) {
      ...  // body of method
   }
is an abbreviation for
   ... method(...) {
      synchronized (this) {
         ...  // body of method
      }
   }
that is, the entire body of the instance method is a synchronized block on the object (keyword this) the method is in.

The JLS does not guarantee that the thread that has waited the longest to lock an object will be the next to obtain the lock when the object is unlocked.

Program noRaceCondition.java uses a synchronized block so that only one thread at a time is allowed to execute sum=fn(sum,m). A thread executing this function must first obtain the lock on the `this' object, instantiated from the Racer class by the main program and shared by both threads. Sample run noRaceCondition.txt illustrates the results. Notice that the final resulting sum is correct.

Multithreaded program parallelPrimes.java generates prime numbers with a fixed number of threads (using class Prime). Sample run parallelPrimes.txt shows the results.

Besides solving the mutual exclusion problem, the use of a shared lock by threads sharing data ensures that changes to shared data by one thread become visible to other threads. When a thread obtains the shared lock, all values cached in its CPU registers or CPU cache are invalidated and refreshed from main memory. When the thread releases the shared lock, all values cached in its CPU registers or CPU cache are flushed (written) to main memory. Therefore, use of the volatile keyword is not necessary for variables shared by multiple threads when a shared lock is used properly.

Use synchronization whenever a thread

Exercise: Use a synchronized block to eliminate the race condition in the ATM/Auditor program bankAccountsAuditor.java.

Java 2 Platform Standard Edition 5.0

Java 2 Platform Standard Edition 5.0 contains a package, java.util.concurrent, derived from Doug Lea's collection of concurrent programming classes, gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html. This package contains a rich set of classes (locks, condition variables, semaphores, blocking queues, etc.) that has been thoroughly tested and is suitable for concurrent programming in a ``production'' environment (meaning in ``the real world''). See java.sun.com/j2se/1.5.0/docs/api for the concurrent API and java.sun.com/docs/books/tutorial/essential/threads/index.html for a tutorial on threads.

This package was developed by Doug Lea to address the concurrent programming deficiencies of the Java language prior to Java 2 Platform Standard Edition 5.0. See the discussion below under ``Before Java 2 Platform Standard Edition 5.0.''

Locks

Package java.util.concurrent.locks contains an interface Lock and a class ReentrantLock that implements the Lock interface. Locks can be used in place of synchronized blocks and to implement synchronized methods, that is, use

class ... {
   Lock mutex = new ReentrantLock();
   ...
   ... method(...) {
      mutex.lock();
      try {
         ...  // code that might return or throw an exception
      } finally {
         mutex.unlock();
      }
   }
}
in place of
class ... {
   Object mutex = new Object();
   ...
   ... method(...) {
      synchronized (mutex) {
         ...  // code that might return or throw an exception
      }
   }
}
or
class ... {
   ...
   ... method(...) {
      synchronized (this) {
         ...  // code that might return or throw an exception
      }
   }
}

Locks offer more flexibility than synchronized blocks in that a thread can unlock multiple locks it holds in a different order than the locks were obtained. This cannot be done with the implied locks of synchronized blocks because synchronized blocks must be lexically nested.

Program noRaceLock.java uses a lock so that only one thread at a time is allowed to execute sum=fn(sum,m). Sample run noRaceLock.txt shows the correct summing result.

Monitors

As the following examples show, monitors can be used to synchronize threads that request resources from and return resources to a server. This is called a client-server relationship.

In a client-server relationship, the clients interact with the server but not with each other. The server monitor is a passive object in the sense that no independent thread executes inside it; the code in the monitor is executed only when a monitor method is invoked by a client thread.

A thread invoking a synchronized method must acquire the lock in the monitor object containing the method before executing the method's code. The thread blocks if the lock is currently held by another thread.

Monitors can be awkward to use if the threads have a relationship other than a client-server one, such as a peer-to-peer one in which there is no central server and client threads interact directly with each other.

Condition Variables

Monitors studied in operating systems texts have condition variables that are used to block threads until conditions are right for them to continue executing inside the monitor. Locks and the Condition interface provide this capability. Blocked threads are said to wait in a wait set.

Each condition variable (wait set) has a specific condition associated with it. If a thread enters the monitor and finds the condition false, the thread waits in the condition variable's wait set until the condition is true. Some other thread later enters the monitor, changes the condition to true, and signals the condition variable, releasing one thread (or all threads) from the wait set.

Condition variables and their associated wait sets are chosen after analyzing the problem to determine how many distinct conditions there are on which threads need to block until the condition is true. When a thread changes a condition associated with a wait set from false to true, the thread signals one (or all) threads in the wait set with signal (or signalAll). Released threads reenter the monitor, one at a time, after reacquiring the monitor's lock. An efficiency goal of the problem analysis is to devise condition variables so that signal instead of signalAll is used.

A Java monitor has the following structure or pattern:

class Monitor extends ... {
   private ...  // data fields (state variables)
   private Lock mutex = new ReentrantLock();
   private Condition ... = mutex.newCondition();
   private Condition ... = mutex.newCondition();
   Monitor(...) {...}  // constructor
   public type method1(...) throws InterruptedException {
      mutex.lock();
      try {
         ...
         ....signal(); // or signalAll() if any await conditions altered
         while (!condition1) ....await();
         ...
         ....signal(); // or signalAll() if any await conditions altered
      } finally { mutex.unlock(); }
   }
   public type method2(...) throws InterruptedException {
      mutex.lock();
      try {
         ...
         ....signal(); // or signalAll() if any await conditions altered
         while (!condition2) ....await();
         ...
         ....signal(); // or signalAll() if any await conditions altered
      } finally { mutex.unlock(); }
   }
   ...
}

It is usually wrong to Thread.sleep(ms) while inside a monitor synchronized method holding the lock.

mutex.lock();
try {
   ...
   Thread.sleep(ms);  // NO!
   ...
} finally { mutex.unlock(); }
Other threads wanting to enter the monitor will block to acquire the lock and they cannot be interrupted from this state. It is better to set a flag, leave the monitor, release the lock, and sleep outside the monitor. After sleeping, reenter the monitor to unset the flag. Other threads can then await() on a condition variable for the flag to change. No thread holds the monitor's lock for any longer than to set or check this flag.
Lock mutex = new ReentrantLock();
Condition waiting = mutex.newCondition();
...
public void wantToCross() {
   mutex.lock();
   try {
      while (crossing) waiting.await();
      crossing = true;
   } finally { mutex.unlock(); }
}
...
Thread.sleep(ms);
...
public void doneCrossing() {
   mutex.lock();
   try {
      crossing = false;
      waiting.signal();
   } finally { mutex.unlock(); }
}

If a thread that is blocked inside a call to sleep(ms), join(), or condition variable await() is interrupted, then these methods clear the thread's interrupt flag and throw an InterruptedException instead of returning normally. Note that no exception is thrown if a thread is interrupted while blocked waiting to acquire a monitor's lock to execute a synchronized method. The thread remains blocked until it acquires the lock, as the test program testInterrupt.java and its output testInterrupt.txt show.

The Java 2 Platform Standard Edition 5.0 documentation states that, by default, for a condition variable created from a ReentrantLock, waiting threads are signaled in first-in-first-out order, but that the thread waiting the longest to reacquire the lock after being signaled will not necessarily be the next one to reacquire the lock.

The data fields in a monitor need not be declared volatile because all writes to shared variables by a thread are completed before obtaining and before releasing the monitor lock (see JLS, first edition, page 400).

Ignoring InterruptedException, as in

while (!condition) try { ....await(); }
   catch (InterruptedException e) { }
is undesirable. The enclosing method should throw the exception back to the caller.

The following code

if (!condition) try { ....await(); }
   catch (InterruptedException e) { }
is incorrect because a thread interrupted out of its wait() then re-enters the monitor without being properly signaled.

Examples

Class BoundedBuffer in boundedBufferMonitor.java is a bounded buffer monitor solving the producers and consumers problem. Multiple producer threads and multiple consumer threads are handled. A producer thread deposits items and blocks if the bounded buffer fills up. A consumer thread fetches items and blocks if the bounded buffer is empty. The monitor is implemented with a lock and two condition variables. Note that Condition's signal() is used instead of signalAll() because of the two disjoint wait sets being used for consumers and producers from which one thread can continue.

Program boundedBufferDriver.java creates the producer and consumer threads and sample run boundedBufferMonitor.txt shows the properly synchronized producers and consumers.

Class DiningServer in diningPhilosophersServer.java and DiningServerImpl in diningPhilosophersMonitor.java implement a monitor that solves the dining philosophers problem. Five philosophers sit around a table and think until hungry. Between each pair of adjacent philosophers is one fork, as shown in the figure below. A hungry philosopher must have exclusive simultaneous access to both its left and right forks in order to eat. If they are not both free, the philosopher waits. Each philosopher has its own dedicated condition variable (and wait set).

dining philosophers

Program diningPhilosophersDriver.java creates the philosopher threads and sample run diningPhilosophersMonitor.txt shows the dining philosophers eating according to the rules.

Class Intersection in carIntersectionMonitor.java is a monitor for a simulation of cars crossing at an intersection of two one-way streets so that

Each of the two streets has its own condition variable.

traffic intersection

Program carIntersectionDriver.java creates the car threads and sample run carIntersectionMonitor.txt shows the cars properly traversing the intersection.

More information on monitors is available in the last section.

Exercises

Write a monitor for the database readers and writers problem. Multiple reader threads can read the database simultaneously but writer threads must have exclusive access with respect to other reader and writer threads.

Write a barrier monitor. Threads wait until all threads arrive at the barrier, then they are all released.

When a signal() or signalAll() is done inside a Java monitor, the next thread to get inside the monitor (acquire the lock) is arbitrary. Therefore, the cars in the intersection simulation going in the same direction do not necessarily go through the intersection in the order they arrived at it (it is not FCFS). Fix this.

Semaphores

Program noRaceSemaphore.java uses a java.util.concurrent.Semaphore with initial value one (binary semaphore) for mutual exclusion to fix the race condition in raceCondition.java. Sample run noRaceSemaphore.txt shows the properly computed shared sum.

Class BoundedBuffer in boundedBufferSemaphore.java is a bounded buffer for a single producer and a single consumer, implemented using java.util.concurrent.Semaphore. Program boundedBufferDriver.java creates the producer thread and the consumer thread. Sample run boundedBufferSemaphore.txt shows the properly synchronized producer and consumer.

Class DiningServer in diningPhilosophersServer.java and DiningServerImpl in diningPhilosophersSemaphore.java solve the dining philosophers problem with semaphores. Program diningPhilosophersDriver.java creates the philosopher threads and sample run diningPhilosophersSemaphore.txt shows the dining philosophers eating according to the rules.

Program tokenRing.java uses an array of binary semaphores for event (condition) synchronization to coordinate a bunch of threads incrementing and passing a token value around a ring. Sample run tokenRing.txt shows the token ring in operation.

The Java 2 Platform Standard Edition 5.0 documentation states that, by default, semaphores are not fair. The thread waiting the longest in a call to acquire will not necessarily be the one to return after a release. In fact, barging is possible: a thread that calls acquire after some other thread has called release might return from acquire instead of a thread that was already waiting in acquire before the release.

More information on semaphores is available in the last section.

Blocking Queues

Bounded buffers are a part of java.util.concurrent in the form of interface BlockingQueue and class ArrayBlockingQueue that implements BlockingQueue. Class BoundedBuffer in boundedBufferQueue.java is a bounded buffer implemented with ArrayBlockingQueue. Program boundedBufferDriver.java creates the producer and consumer threads and sample run boundedBufferQueue.txt shows the properly synchronized producers and consumers.

Exercises

Is it possible for a call to the printState method in boundedBufferSemaphore.java (bounded buffer implemented with semaphores) to print inconsistent values of putIn and/or takeOut and/or count? If so, show how this can happen and modify the class to prevent it from happening.

Explain why class BoundedBuffer in boundedBufferSemaphore.java does not work correctly for multiple producer and multiple consumer threads. Modify the class so that it correctly handles them.

Write a semaphore solution for the database readers and writers problem.

Write a semaphore solution for the cars at an intersection problem.

Java's Memory Model

Java's memory model is a complicated subject. It was designed with a particular parallel computer architecture in mind (shared-memory multiprocessor with CPU caches) so that unrealistic hardware constraints would not be placed on this architecture by the memory model.

Three surprising (to say the least!) implications of the memory model for multithreaded programs are:

An example of the second concern, exposing this in constructors to other threads, is starting a thread in the constructor of an object.
class ThreadedObject implements Runnable {
   public ThreadedObject(...) {
      ...
      Thread me = new Thread(this);  // No! exposes `this'
      me.start();
   }
   ...
   public void run() { ... }
}
We are giving a reference, this, of an incompletely constructed object to another thread, the one started in object me.

These problems are described in detail in the articles by William Pugh, Brian Goetz, and Peter Haggar in the memory model section of the references at the end. To be correct, your multithreaded Java programs must not use double locking and must not expose this in constructors to other threads.

These problems have led computer scientists to conclude that Java's memory model is flawed and broken. Eventually, the model will be changed to fix some of the problems, such as String objects not really being immutable. (This was done in the third edition of the JLS; see Chapter 17).

In the meantime, following one rule (that has two parts) will keep your multithreaded Java programs from having problems related to the current memory model. The rule is: in a Java program having multiple threads that share data, obtain a shared lock or semaphore or enter a synchronized block

For example,
... a, ...;                 // shared data
...
Object lock = new ...;      // shared lock
...
public void run() {         // one thread
   synchronized (lock) {    // obey rule's first part
      ...
      x = ... a ...;        // read shared data
      ...
   }
}
...
public void run() {         // another thread
   synchronized (lock) {    // obey rule's second part
      ...
      a = ... y ...;        // write shared data
      ...
   }
}

This rule ensures that when a thread enters a synchronized block or synchronized method

and when a thread leaves a synchronized block or synchronized method

See the online articles and papers about Java's memory model in the references for more detailed descriptions of these problems.

Before Java 2 Platform Standard Edition 5.0

Older versions of Java were difficult and error-prone to use correctly for concurrent programming (monitors and semaphores). The following discussion describes the problems.

Monitors

Every Java object possesses a lock and these methods: wait(), notify(), and notifyAll().

A thread invoking a synchronized method must acquire the lock of the object containing the method before executing the method's code. The thread blocks if the object is already locked.

A monitor had the following structure or pattern:

class Monitor extends ... {
   private ...  // data fields (state variables)
   Monitor(...) {...}  // constructor
   public synchronized type method1(...)
         throws InterruptedException {
      ...
      notifyAll(); // if any wait conditions altered
      while (!condition1) wait();
      ...
      notifyAll(); // if any wait conditions altered
   }
   public synchronized type method2(...)
         throws InterruptedException {
      ...
      notifyAll(); // if any wait conditions altered
      while (!condition2) wait();
      ...
      notifyAll(); // if any wait conditions altered
   }
   ...
}

Note the following important points:

Semaphores

Versions of the Java language prior to Java 2 Platform Standard Edition 5.0 do not include a built-in semaphore class. The following semaphore classes are user-defined Java monitors:

Pitfalls

The above semaphore classes are not efficient because V() is implemented with a notifyAll(), unblocking all threads waiting inside P(), instead of a notify() that unblocks just one waiting thread. Trying to implement a semaphore with notify() instead of notifyAll() is tricky, as the following discussion shows.

This version of a counting semaphore, class BadCountingSemaphore1 is not correct because of barging, as shown in the following figure.

an incorrect semaphore

Suppose the semaphore's current value is 0. Three threads invoke the semaphore's P() method and wait. Then another thread calls V(), which moves one of the three waiting threads to the runnable set.

Now suppose a couple of other threads barge ahead of the signaled thread and perform two more V() operations on the semaphore. Because the semaphore's value is positive, notify() is not called and none of the waiting threads is moved to the runnable set.

Finally, the thread signaled by the first V() re-enters the semaphore monitor, decrements the semaphore value from 3 to 2, and leaves the monitor. The monitor has two waiting threads and a positive value. This is an inconsistent state for a counting semaphore.

To fix this problem, we could try changing the semantics of the semaphore value field, as in class BadCountingSemaphore2. The value is allowed to go negative, in which case its absolute value equals the number of waiting threads.

This fixes the barging problems but introduces an interrupt() problem. Suppose the semaphore value is -1 due to one thread blocked in wait() inside P(). Then suppose that thread is interrupted. The value is left at -1 even though no threads are blocked in P(). The next V() will increment the value to 0 whereas it should now be 1.

Another, more insidious problem is present: a race condition between interrupt() and notify(). Suppose several threads are blocked inside wait() and then one of them is notified and then interrupted before it reacquires the monitor lock. The notify() gets ``lost'' in that one of the other waiting threads should now proceed. So we need to catch the exception when a thread is interrupted out of wait() and regenerate the notify().

For the complete sequence of attempts and the final version, EfficientCountingSemaphore, see the paper ``Alfonse, Wait Here for My Signal!'' in the references.

Examples

Program noRaceSemaphore.java uses a binary semaphore for mutual exclusion to fix the race condition in raceCondition.java.

Program tokenRing.java uses an array of binary semaphores for event (condition) synchronization to coordinate a bunch of threads incrementing and passing a token value around a ring.

Class BoundedBuffer in boundedBufferSemaphore.java is a bounded buffer implemented with semaphores for a single producer and a single consumer. Program boundedBufferDriver.java creates the producer thread and the consumer thread.

Class DiningServer in diningPhilosophersServer.java and DiningServerImpl in diningPhilosophersSemaphore.java solve the dining philosophers problem with semaphores. Program diningPhilosophersDriver.java creates the philosopher threads.

Security Issues

An object's lock is accessible to any thread that has a reference to the object. This can upset the operation of a monitor if some rogue thread decides to do something like the following.

synchronized (monitor) {
   Thread.sleep(veryLongTime);
   // or
   invert(veryLargeMatrix);
}
The following executed by some rogue thread is not so bad because of the while (!condition) loop that a wait() is done in. But is does add overhead.
synchronized (monitor) {
   monitor.notifyAll();
}

To protect our code from this rogue thread mischief, we should code a monitor as follows, using a counting semaphore as an example. We use a wrapper class and delegate P() and V() to a private counting semaphore inside the wrapper class.

class SecureCountingSemaphore {
   private CountingSemaphore S = null;
   SecureCountingSemaphore(int initial)
      { S = new CountingSemaphore(initial); }
   void P() throws InterruptedException { S.P(); }
   void V() { S.V(); }
}

Another way is to use a private lock object inside the semaphore class and change synchronized methods to use the private lock.

class SecureCountingSemaphore {
   private int value = 0;
   private Object mutex = new Object();
   SecureCountingSemaphore(int initial)
      { value = initial; }
   void P() throws InterruptedException {
      synchronized (mutex)
         { while (value == 0) mutex.wait();  value--; }
   }
   void V() {
      synchronized (mutex)
         { value++;  mutex.notifyAll(); }
   }
}

Message Passing

Object-oriented programming blurs the distinction between invoking a method and sending a message. It also blurs the distinction between shared and distributed memory computer architectures.

The following figure shows the difference between invoking a method and sending a message.

sending message versus calling method

It is important to note that multiple threads invoking methods in an object might lead to race conditions unless synchronization is properly done by making the object a monitor. With message passing, the sending and receiving objects have just one thread executing inside each of them, leading to ``safer'' concurrent programming.

If the threads have a relationship other than client-server, monitors can be awkward to use. Using message passing between the threads is easier in these situations. If the threads communicate with each other, they are called peers or filters. In the filter situation, the threads form a pipeline in which each thread gets its input from its predecessor in the pipeline and sends it output to its successor in the pipeline.

There are two kinds of message passing: asynchronous (non-blocking send) and synchronous (blocking send). Note that a receive always blocks. The one-way flow of information from sender to receiver in synchronous message passing is sometimes called a simple rendezvous.

Class javaconcprog.MessagePassing implements both synchronous and asynchronous varieties. The asynchronous version can be capacity-controlled or not. Capacity-controlled asynchronous message passing is implemented with a java.util.concurrent.ArrayBlockingQueue (a bounded buffer); non-capacity-controlled is implemented with a java.util.concurrent.LinkedBlockingQueue (actually, capacity is limited by RAM and/or swap space). Synchronous message passing is implemented with a java.util.concurrent.SynchronousQueue.

There are two possibilities for a class implementing either synchronous or asynchronous message passing:

  1. Send object references from one thread to another thread, both within the same JVM.
  2. Send serialized objects through connected sockets from a thread in one JVM to a thread in another JVM. The other JVM might be on the same or a different physical machine.

Class javaconcprog.MessagePassing implements the first option: the communicating threads are all executing in the same JVM. Remote Method Invocation (RMI), described later, can be used to implement message passing between threads in different JVMs (that might also be on different physical machines).

Each object instantiated from a message passing class, whether synchronous or asynchronous or intra-JVM or inter-JVM, represents a mailbox or channel shared by a collection of threads.

The following is skeleton code for message passing between threads in the same JVM.

shared type:
class Message { ... }
shared mailbox:
   // blocking sends (synchronous):
MessagePassing mailbox = new MessagePassing(-1);
   // non-blocking sends (asynchronous) with no capacity control:
MessagePassing mailbox = new MessagePassing();  // or pass 0
   // capacity controlled non-blocking sends:
MessagePassing mailbox = new MessagePassing(capacity);
one thread executes:
Message ms = new Message(...);
mailbox.send(ms);
another thread executes:
Message mr;
mr = mailbox.receive();

The capacity-controlled constructor creates a message passing mailbox with a finite capacity. Once the mailbox fills up with messages to be received, threads trying to send another message to the mailbox must wait.

Values like int and double can be sent using auto boxing and unboxing with the wrapper classes Integer and Double.

Class javaconcprog.MessagePassing sends object references synchronously or asynchronously within one JVM.

Examples

The first example contains worker threads and a bag of tasks, the second example contains filter threads, and the third example contains peer threads.

  1. Program quickSort.java: Quicksort (worker threads); quickSort.txt is a sample run.
  2. Program parallelSievePrimes.java: Parallel Sieve of Eratosthenes (filter threads); parallelSievePrimes.txt is a sample run.
  3. Program radixSort.java: Parallel Radix Sort (peer threads); radixSort.txt is a sample run.

Class BoundedBuffer in boundedBufferMP.java is a (un)bounded buffer implemented with message passing. The (un)bounded buffer can operate synchronously (a producer blocks until its deposit is fetched) or asynchronously with or without a maximum capacity. Program boundedBufferDriver.java creates the producer and consumer threads and sample run boundedBufferMP.txt shows the properly synchronized producers and consumers communicating with synchronous message passing.

For the curious, previous to the release of Java 2 Platform Standard Edition 5.0, asynchronous message passing was implemented with this version of class MessagePassing.

More information on message passing is available in the last section.

Exercise: Use program boundedBufferDriver.java with various command line arguments to drive the BoundedBuffer in boundedBufferMP.java to test all combinations of the following.

There are 12 possibilities in all! Explain the output of running the program in each case.

Rendezvous

In general, client-server programming involves a client thread interacting with the server thread by sending a request message followed immediately by a receive that blocks the client until the server sends a reply message containing the results of the request. This is called a rendezvous. It is also sometimes called an extended rendezvous to distinguish its two-way flow of information from the one-way flow of information in the simple rendezvous (synchronous message passing).

A monitor is a passive object that can be used to implement a server; a client calls a method in the server to request a service (the return value of the method is the server's reply). An active object, in which an independent thread executes, can also act as a server by using the rendezvous style of message passing. The following is skeleton code.

mailbox shared by the client and server:
MessagePassing mailbox = new MessagePassing();
client thread executes:
mailbox.send(request);
reply = mailbox.receive();
server thread executes:
request = mailbox.receive();
  compute reply;
mailbox.send(reply);

The above message passing will be encapsulated into two classes: a Transaction class and a Rendezvous class. A Transaction object is used to contain the client request and the server reply. A Rendezvous object is used by the client to contact or address the server; it is also used by the server to get the next client request it wants to handle. A very useful feature of the Rendezvous class is that the server can specify a condition or guard on client requests it is willing to handle at the current time. For example, a server representing a bank might be willing to grant loans of $10,000 or less Monday through Thursday; larger loans are processed only on Fridays.

A transaction occurs when two threads exchange information synchronously. Class javaconcprog.Transaction is used for one such exchange. Skeleton code follows.

A transaction object, containing the client request, is shared by the client and server:
Transaction t;
The client thread executes:
Object request = ...;  // create request
t = new Transaction(request);
Object reply = t.clientAwaitReply();
The server thread executes:
Object request = t.serverGetRequest();
Object reply = ...;  // compute reply
t.serverMakeReply(reply);

A rendezvous (also called a conditional or guarded rendezvous) builds on the idea of a transaction. Transaction objects are used once and then discarded. Many clients share a single Rendezvous object with one or more servers and use it repeatedly for requests. A Rendezvous object also allows the server to specify criteria of which thread to rendezvous with next. The following figure illustrates this idea.

conditional rendezvous

The server's rendezvous criteria are specified with an object instantiated from a class that implements the javaconcprog.RendezvousCondition interface. An instance of the javaconcprog.Rendezvous class is then used for the communication. The Transaction objects are used internally by the Rendezvous object and are not seen by the clients. Skeleton code follows.

Rendezvous object shared by the client and server:
Rendezvous r = new Rendezvous();
Client thread executes:
Object request = ...; // create request
Object reply = r.clientTransactServer(request);
Server thread executes:
RendezvousCondition c = new ServerCriteria(...);
Transaction t = r.serverGetClient(c);
Object request = t.serverGetRequest();
Object reply = ...;  // compute reply to request
t.serverMakeReply(reply);

Multiple servers can share a single Rendezvous object. For example, loan officers (servers) at a bank can share a single Rendezvous object and extract loan applications (clients) from it. Each loan officer can have different conditions, such as a trainee handling only loans less than $1000 and a senior officer handling loans of any size.

A server can call serverGetClient(c) again (a ``nested'' call) while in the middle of a transaction with a client, that is, after calling serverGetClient to get a client's request but before calling serverMakeReply to reply to that client. For example, a senior loan officer can extract a $1,000,000 loan application from the queue. While processing it (a time-consuming job), the queue of small quickly processable loan applications might increase to the point that the trainees cannot keep up. The senior officer can put the large loan application aside and process queued loan applications for a while.

Remote Method Invocation (RMI), described later, can be used to implement rendezvous between threads in different JVMs that might also be on different physical machines.

The javaconcprog.Rendezvous class also supports peer-to-peer programming. The class has four additional methods,

that can be used for asynchronous and synchronous conditional and unconditional message passing among a collection of peer threads.

A receiving peer can specify a condition for messages it is willing to receive, just as can be specified by a server for a rendezvous.

If a sender wants to block until its message is received, it should use call(m) instead of send(m).

Class DiningServer in diningPhilosophersServer.java and DiningServerImpl in diningPhilosophersRendezvous.java show an example of clients and a server. This example synchronizes the dining philosopher clients using rendezvous. Program diningPhilosophersDriver.java creates the philosopher threads and diningPhilosophersRendezvous.txt is a sample run.

Because the philosophers only need to block until their request is conditionally received by the server and since they are not interested in the reply message, the philosophers use call instead of clientTransactServer. Similarly, the server uses receive instead of serverGetClient.

Program producersConsumersRendezvous.java is an example of some producer and consumer peers in which a consumer thread specifies that it receive the message with the smallest value among the yet unreceived messages. A producer can act asynchronously by using send; the consumer uses receive. To find out which consumer got its message, a producer can act synchronously by using clientTransactServer; the consumer uses serverGetClient, serverGetRequest, and serverMakeReply in this case.

Eight sample runs follow, illustrating various ratios of producers to consumers along with synchronous and asynchronous acting producers.

Exercise: Consider a bank that makes loans and accepts loan repayments from its customers. Use nested serverGetClient(c) calls by the bank server thread to prevent starvation of a customer needing a particularly large loan: the bank accepts only repayments until it has enough funds to make the large loan. Try implementing the same bank server as a passive monitor object. Which is easier?

More information on rendezvous is available in the last section.

Remote Method Invocation (RMI)

RMI refers to a Java package java.rmi used to make remote procedure calls.

RMI allows a thread in one JVM to invoke a method in an object in another JVM that is perhaps on a different computer. A new thread is created in the remote object to execute the called method's code.

Object serialization is used to send an object from one JVM to another as an argument of a remote method invocation. This converts an object into a byte stream that is sent through a socket and converted into a copy of the object on the other end.

Program Compute.java shows several clients accessing a remote server executing in a different JVM, which might be on a different physical machine. Server output in a sample run is shown in computeLocalServer.txt; client output in the same sample run is shown in computeLocalClients.txt.

Notice that the sample output shows the clients' remote method invocations are interleaved, that is overlapping executions by new threads created in the server for each RMI. There are no race conditions or synchronization problems because the clients are independent and do not share any data.

In the sample run, the clients all execute in one JVM and the server in another JVM; both JVMs are on the same physical machine. If the clients are on a different physical machine, pass the name of the machine on which the server runs as a command line argument when starting the clients. Server output in a multiple-machine sample run is shown in computeMultiServer.txt; client output in the same sample run is shown in computeMultiClients.txt.

RMI can be used by a thread in one JVM to send a message to or rendezvous with a thread in another JVM. A thread willing to receive or rendezvous registers an interface that other threads can use and implements the interface using a message passing or rendezvous object.

The following classes use RMI to implement rendezvous and message passing for threads executing in different JVMs that are perhaps on different machines.

Program Transact.java shows several clients using rendezvous to access a remote server executing in a different JVM, which can be on a different physical machine. Server output in a sample run is shown in transactLocalServer.txt; client output in the same sample run is shown in transactLocalClients.txt.

In the program, multiple clients transact (read and write operations) with a database on a remote server. The transactions are serialized, that is, done sequentially in some nonoverlapping order, to avoid race conditions on the shared database maintained by the server. Also, the server uses conditional rendezvous to give client number zero highest priority by always handling its transaction first among those waiting to be performed. There is no reason for giving client number zero priority except to show that it can be done and how to do it.

In the sample run, the clients all execute in one JVM and the server in another JVM. Both JVMs are on the same physical machine. If the clients are on a different physical machine, pass the name of the machine on which the server runs as a command line argument when starting the clients. Server output in a multiple-machine sample run is shown in transactMultiServer.txt; client output in the same sample run is shown in transactMultiClients.txt.

Program Ring.java shows several peers arranged in a circular ring. Each ring member uses message passing to communicate with its left and right neighbors. Each ring member executes in its own JVM and the ring members need not all be on the same physical machine. A single token object is passed around the ring from each member to its successor. The outputs of the members in a sample run of a three-member ring are shown in ringMembersLocal.txt.

In the sample run, the three ring members execute in different JVMs, all on the same physical machine. If the JVMs are on different physical machines, give each ring member on its command line the machine name of its successor. Each physical machine running one or more ring member JVMs needs to be executing one instance of the rmiregistry program (part of the J2SE). The outputs of the members in a multiple-machine sample run of a four-member ring are shown in ringMembersMulti.txt.

More information on remote method invocation is available in the last section.

See also java.sun.com/jdc/JDCTechTips/2001/tt0227.html.

References and Related Material

Web Sites

Andrew D. Birrell, ``An Introduction to Programming with Threads'', DEC research report (January 1989)

Doug Lea's Java concurrent programming package, gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html

Doug Lea's concurrency API (JSR-166) will be incorporated into a future version of Java: gee.cs.oswego.edu/dl/concurrency-interest/index.html.

Bill Pugh's Java Memory Model Page: www.cs.umd.edu/~pugh/java/memoryModel.

JCSP web page at the University of Kent, Canterbury, UK, www.cs.ukc.ac.uk/projects/ofa/jcsp

JavaPP Web page at the University of Bristol, UK, www.cs.bris.ac.uk/~alan/javapp.html

JavaPP Web page at the University of Twente, Netherlands, www.ce.utwente.nl/javapp

Sun Microsystems, Inc., J2SE downloads, www.javasoft.com/products/index.html

Java 2 Platform Standard Edition 5.0 API, java.sun.com/j2se/1.5.0/docs/api

Sun Microsystems tutorial on threads, java.sun.com/docs/books/tutorial/essential/threads/index.html

Online IBM developerWorks Articles

Alex Roetter, ``Writing multithreaded Java applications'' (February 2001)

Brian Goetz, Threading lightly series: ``Part 1: Synchronization is not the enemy'' (July 2001), ``Part 2: Reducing contention'' (September 2001), ``Part 3: Sometimes it's best not to share'' (October 2001)

Brian Goetz, ``Java theory and practice: Concurrency made simple (sort of)'' (November 2002)

Brian Goetz, ``Java theory and practice: Concurrent collections classes'' (July 2003)

Neel V. Kumar, ``Writing efficient thread-safe classes'' (April 2000)

See the archives for more recent articles.

Online JavaWorld Articles

Introduction to Java threads (April 1996)

Synchronizing threads in Java, Part 1 (April 1996)

Using threads in Java, Part 2 (May 1996)

How the Java virtual machine performs thread synchronization (July 1997)

Using threads with collections, Part 1 (March 1998)

Using threads with collections, Part 2 (June 1998)

Design for thread safety (August 1998)

Programming Java threads in the real world, Part 1 (September 1998)

Programming Java threads in the real world, Part 2 (October 1998)

Programming Java threads in the real world, Part 3 (November 1998)

Programming Java threads in the real world, Part 4 (December 1998)

Programming Java threads in the real world, Part 5 (February 1999)

Programming Java threads in the real world, Part 6 (March 1999)

Programming Java threads in the real world, Part 7 (April 1999)

Programming Java threads in the real world, Part 8 (May 1999)

Programming Java threads in the real world, Part 9 (June 1999)

Does Java support the semaphore mechanism? (November 1999)

There are many more recent articles in the by-year archives.

Online Articles and Papers About Java's Memory Model

William Pugh, et. al., ``The `Double-Checked Locking is Broken' Declaration''

William Pugh, ``The Java Memory Model Is Fatally Flawed''

For the proposed changes in the Java Memory Model resulting from JSR 133, see the PDF file: Jeremy Manson and William Pugh, ``Semantics of Multithreaded Java'' (January 2002).

Brian Goetz, ``Java theory and practice: Safe construction techniques'' (June 2002)

Brian Goetz, ``Double-checked locking: Clever, but broken'' (February 2001)

Brian Goetz, ``Can double-checked locking be fixed?'' (May 2001)

Brian Goetz, `` Can ThreadLocal solve the double-checked locking problem?'' (November 2001)

Peter Haggar, ``Double-checked locking and the Singleton pattern'' (May 2002)

Operating Systems Books

Abraham Silberschatz and Peter Galvin, Operating System Concepts, fifth edition, Addison Wesley, 1998.

William Stallings, Operating Systems, fourth edition, Prentice Hall, 2001.

Andrew Tanenbaum, Modern Operating Systems, second edition, Prentice Hall, 2001.

Java Books

Ken Arnold, James Gosling, and David Holmes, The Java Programming Language, third edition, Addison Wesley, 2000.

James Gosling, Bill Joy, and Guy Steele, The Java Language Specification, Addison-Wesley, 1996.

Cay Horstmann and Gary Cornell, Core Java. Volume I Fundamentals, sixth edition, Prentice Hall, 2003. Volume II Advanced Features, fifth edition, Prentice Hall, 2002.

Concurrent Programming Books

Gregory R. Andrews, Concurrent Programming: Principles and Practice, Benjamin/Cummings, 1991.

Gregory R. Andrews, Foundations of Multithreaded, Parallel, and Distributed Programming, Addison Wesley, 2000.

Allen B. Downey, The Little Book of Semaphores, second edition, June 2005, greenteapress.com/semaphores.

Stephen J. Hartley, Concurrent Programming: The Java Programming Language, Oxford University Press, March 1998.

Paul Hyde, Java Thread Programming, Sams, 1999.

Doug Lea, Concurrent Programming in Java: Design Principles and Patterns, second edition, Addison Wesley, 2000.

Jeff Magee and Jeff Kramer, Concurrency: State Models and Java Programs, John Wiley, 1999.

A. W. Roscoe, The Theory and Practice of Concurrency, Prentice Hall, 1998.

Concurrent Programming Papers

Peter A. Buhr, Michel Fortier, and Michael H. Coffin, ``Monitor Classification,'' ACM Computing Surveys, Vol. 27, No. 1, March 1995.

Stephen J. Hartley, ``Alfonse, Your Java Is Ready!'' Presented at the Twenty-Ninth SIGCSE Technical Symposium, Association for Computing Machinery, Atlanta, Georgia, February 26-March 1, 1998. Published in ACM SIGCSE Bulletin, Vol. 30, No. 1, March 1998, pp. 247-251.

Stephen J. Hartley, ``Alfonse, Wait Here for My Signal!'' Presented at the Thirtieth SIGCSE Technical Symposium, Association for Computing Machinery, New Orleans, LA, March 24-28, 1999. Published in ACM SIGCSE Bulletin, Vol. 31, No. 1, March 1999, pp. 58-62.

Stephen J. Hartley, ``Alfonse, You Have a Message!'' Presented at the Thirty-First SIGCSE Technical Symposium, Association for Computing Machinery, Austin, TX, March 8-12, 2000. Published in ACM SIGCSE Bulletin, Vol. 32, No. 1, March 2000, pp. 60-64.

Stephen J. Hartley, ``Alfonse, Give Me a Call!'' Presented at the Thirty-Second SIGCSE Technical Symposium, Association for Computing Machinery, Charlotte, NC, February 21-25, 2001. Published in ACM SIGCSE Bulletin, Vol. 33, No. 1, March 2001, pp. 229-232.

Background Information

Background Material on Threads

The following subsection is a quick refresher on threading.

A process is an executing program. It has been allocated memory by the operating system. A thread is an execution or flow of control in the address space of a process; the program counter register points to the next instruction to be executed.

A process is a program with one thread. A process can have more than one thread. All the threads in a process have their own program counter and their own stack for local (also called automatic) variables and return addresses of invoked procedures.

In the Java language, a thread in the run-time interpreter calls the main() method of the class on the java command line. Each object created can have one or more threads, all sharing access to the data fields of the object.

The article, ``An Introduction to Programming with Threads''," by Andrew D. Birrell (January 1989 DEC research report) offers the following motivations for concurrent programming with threads:

Handling windowing events in separate threads will lead to a more responsive user interface because long-running tasks will not prevent other events from being handled. Doing I/O on a slow device in a separate thread while another thread computes will increase the throughput and efficiency of an application. It will also simplify the modeling and design of the application. Spawning off a new thread to handle a client request will increase the throughput and simplify the design of a server.

If two threads execute n=n+1 on a shared variable n at about the same time, their load and store instructions might interleave so that one thread overwrites the update of the other. This lost update leads to an erroneous result and is an example of a race condition.

Race conditions are possible when

Concurrently executing threads that share data need to synchronize their operations and processing in order to avoid race conditions on shared data. Thread synchronization can be done with flag variables and busy waiting. Since it uses a lot of CPU cycles, busy waiting is inefficient. Blocking would be better.

A critical section is a block of code in a thread that accesses one or more shared variables in a read-update-write fashion. In such a situation we want mutual exclusion in which only one thread at a time can access (read-update-write) a shared variable at a time.

The mutual exclusion problem is how to keep two or more threads from being in their critical sections at the same time, where we make no assumptions about the number of CPUs or their relative speeds.

A thread outside its critical section should not keep other threads outside their critical sections from entering. This is called a safety property (or absence of unnecessary delay).

Also, no thread should have to wait forever to enter its critical section. This is called a liveness property (or eventual entry).

An atomic action ``makes an indivisible state transition: any intermediate state that might exist in the implementation of the action must not be visible to other threads.'' (From page 60 of Andrews' Concurrent Programming: Principles and Practice book in the references). This means that nothing from another thread can be interleaved in the implementation of the action for it to be atomic.

Critical sections need to be defined as if they were one atomic action to avoid race conditions.

Here are the basic issues to keep in mind to solve the mutual exclusion problem when devising a pre-protocol and a post-protocol based on either hardware or software. The protocols must:

The system's ground rules are as follows:

Thread Ti, i = 1, 2, 3, ...

   while (true) {
      outsideCS();
      wantToEnterCS(i);   // pre-protocol
      insideCS();
      finishedInCS(i);    // post-protocol
   }

Background Material on Monitors

Semaphores are like goto's and pointers. They work okay but are error prone and lack structure and ``discipline''.

For example, this disastrous typo is easy to do and allows multiple threads into the critical section at the same time.

V(S); criticalSection(); V(S)

This typo blocks one process inside the critical section forever.

P(S); criticalSection(); P(S)

Nested critical sections can lead to deadlock.

P1: P(Q); P(S); ... V(S); V(Q);

P2: P(S); P(Q); ... V(Q); V(S);

A monitor is an object with some built-in mutual exclusion and thread-synchronization capabilities. Monitors are an integral part of the programming language so the compiler can generate the correct code to implement the monitor. Only one thread can be active at a time in the monitor, where ``active'' means executing a method of the monitor.

Monitors also have condition variables on which a thread can wait if conditions are not right for it to continue executing in the monitor. Some other thread can then get in the monitor and perhaps change the state of the monitor. If conditions are now right, that thread can signal a waiting thread, moving the latter to the ready queue to get back into the monitor when it becomes free.

Monitors can use either signal-and-exit or signal-and-continue signaling discipline. In signal-and-exit, a signaling thread must leave the monitor immediately, at which point it is guaranteed that the signaled thread is the next one in the monitor.

In signal-and-continue, the signaled thread is not guaranteed to be the next one in the monitor. In fact, barging can take place: some thread that has called a monitor method and is blocked until the monitor is free can get into the monitor before a signaled thread.

Semaphores and monitors can be used to solve the so-called ``classical'' synchronization problems found in many operating systems books: the sleeping barber, the five dining philosophers, and the database readers and writers.

The sleeping barber. A barber waits to cut hair. Customers enter the waiting room and take a seat if one is available. If the waiting room is full, they try again later. Otherwise, they wait until their turn for a hair cut.

The dining philosophers. Five philosophers sit around a table and think until hungry. Interspersed between the philosophers are five forks. To eat, a hungry philosopher must have exclusive access to both the fork on its left and the fork on its right. If both forks are not free, the philosopher waits.

The algorithm in class DiningServerImpl in diningPhilosophersMonitor.java does not deadlock: it never happens that all philosophers are hungry, each holding one fork and waiting for the other fork to become available. The algorithm allows maximal parallelism: a philosopher never picks up and holds a fork while waiting for the other fork to become available when the fork it is holding could be used for eating by its hungry neighbor. However, the algorithm allows starvation: a philosopher's two neighbors can collaborate and alternate their eating so the one in the middle never can use the forks.

If an algorithm for synchronizing the philosophers allows a philosopher to hold a fork while waiting for the other fork, deadlock is possible, an extreme case of not having maximal parallelism. Each fork is represented by a semaphore and each hungry philosopher does a ``P'' on its left fork and then its right fork. However, starvation is not possible.

We can fix the deadlock problem and retain no starvation, but we still do not have maximal parallelism: all philosophers pick up left then right except one designated philosopher who picks up right then left.

Philosopher starvation can be prevented in class DiningServerImpl in diningPhilosophersMonitor.java by introducing a new state: very hungry. A philosopher is put into this state if it is hungry, one of its neighbors puts down its forks, and it cannot eat because the other fork is in use. A new rule is added: a hungry philosopher cannot eat if it has a very hungry neighbor. These changes prevent a collaboration of two philosophers trying to starve the philosopher between them.

The readers and writers. A database can be accessed concurrently by threads that only want to read, but a writer thread must have exclusive access with respect to other readers and writers.

A solution might allow writers to starve if enough readers keep coming along to read the database that the number of current readers is always above zero.

Writer starvation is prevented by requiring readers that come along to read the database to wait if there is a waiting writer even if other readers are currently reading the database. When the current readers finish, the waiting writer writes the database and then signals into the database a waiting reader. Each entering reader signals another waiting reader into the database.

Background Material on Semaphores

Semaphores can be used for mutual exclusion and thread synchronization. Instead of busy waiting and wasting CPU cycles, a thread can block on a semaphore if it must wait to enter its critical section or if the resource it wants is not available. The operating system removes the thread from the CPU scheduling or ``ready'' queue.

Semaphores can be used to enforce mutual exclusion.

semaphore S = 1; ... P(S); N=N+1; V(S);

Semaphores can be used for condition synchronization (resource usage tracking)

semaphore tapeDrives = 7; ... P(tapeDrives); useTapeDrive(); V(tapeDrives);

Before Java 2 Platform Standard Edition 5.0, Java did not have explicit binary and counting semaphores, so they had to be implemented by the user. Nowadays, the package java.util.concurrent includes semaphores.

Background Material on Message Passing

Sometimes the phrase ``send a message to an object'' is used to describe a thread in one object calling a method in another object. Here, that phrase is used to describe a thread in one object sending a message to a thread in another object, where the message is itself an object.

This technique is used for thread communication and synchronization in a computing environment where the threads do not have shared memory (since the threads reside in different virtual or physical machines). Hence the threads cannot share semaphores or monitors and cannot use shared variables to communicate. Message passing can still be used, of course, in a shared memory platform.

Messages are sent through a port or channel with an operation like channel.send(message) and received from a port or channel with an operation like message = channel.receive(). Messages can be passed synchronously, meaning the sender blocks until the receiver does a receive and the receiver blocks until the sender does a send.

Since the sender and receiver are at specific known points in their code at a known specific instant of time, synchronous message passing is also called a simple rendezvous with a one-way flow of information from the sender to the receiver.

In asynchronous message passing, the sender does not block. If there is not a receiver waiting to receive the message, the message is queued or buffered. The receiver still blocks if there is no queued or buffered message when a receive is executed.

In conditional message passing, the message remains queued until some condition, specified by the receiver, becomes true. At that time, the message is passed to the receiver, unblocking it.

A two-way flow of information, perhaps over the network, is called an extended rendezvous and can be implemented with a pair of sends and receives. Typically a client thread uses this technique to communicate with a server thread and request a service to be performed on its behalf.

A similar situation exists when a worker thread contacts a master thread, asking for more work to do. The client or worker sends a request and blocks, waiting to receive a reply. The server or master receives the client request, performs the requested service, and sends the reply, unblocking the client.

The quick sort algorithm can be parallelized for a shared-memory multiple-CPU machine by dedicating each CPU to a worker thread and using a message passing channel as a bag of tasks. See program quickSort.java.

The main() method puts the whole array to be sorted into the bag. A worker extracts a task, chooses a pivot point, and partitions the array. Each of the two partitions is then put back into the bag as a task for one of the workers to perform.

Even though message passing is being used for the bag of tasks, shared memory is still required because the array is being sorted ``in place'' and the work requests being put into the bag are array index pairs and not pieces of the array itself.

A bag of tasks communication channel, object task, is shared by the quicksort worker threads.

MessagePassing task = new MessagePassing();

The quicksort worker threads get tasks from the task bag inside a while loop.

while (true) {
   m = task.receive();
   quickSort(id, m.left, m.right);
}

The quicksort worker threads create tasks and put them into the task bag.

if (right-(l+1) > 0) task.send(new Task(l+1, right));
if ((l-1)-left > 0) task.send(new Task(left, l-1));

Background Material on Rendezvous

An extended rendezvous is also called a remote procedure call from a client to a server (or a worker to the master) because it resembles a call to a procedure on a remote machine that is executed on the remote machine.

Typically the call represents a request for service, such as reading a file that resides on the remote machine, accessing a database that resides on the remote machine, or performing a computation on the remote machine using specialized hardware on it. The client sends a request object (rendezvous view) or some parameters (remote procedure call view) to the server and waits. The server computes a reply and sends the reply object (rendezvous view) or return value (remote procedure call view) to the waiting client.

The server may handle the request in its main thread or the server may spawn a new thread to handle the request while the server's main thread handles additional requests for service from other clients. The latter gives greater throughput and efficiency because a lengthy request would otherwise delay the handling of additional requests from other clients.

Clients and servers need a ``place'' (a shared object) in which they can congregate so that clients can contact an appropriate server to carry out a conversation (a transaction). A transaction consists of a client sending a request to a server and waiting for a reply; and a server accepting a request, computing a reply, and sending the reply to the waiting client.

In the local case (everything in the same JVM), a shared object created from class javaconcprog.Rendezvous is used as the place for the client and server to ``meet'' and establish a rendezvous. The server calls a method in the object and blocks until the client calls a method. At this point in time, both methods return a newly created object from class javaconcprog.Transaction that the client and server subsequently use for the two-way flow of information (request and reply). This transaction object is used just once for the two-way flow and then discarded.

In the remote case (client and server in different JVMs that are possibly on different physical machines), the client uses the server's host (machine) name, a TCP/IP port number, and the service name to address the server; the server ''listens'' on the TCP/IP port. Since they are in different JVMs, the client and server need their own rendezvous objects, created from classes javaconcprog.RemoteRendezvousClient and javaconcprog.RemoteRendezvousServer respectively (both of these implement the javaconcprog.RemoteRendezvous interface). A client creates its rendezvous object using the server's host name, port number, and service name in the object's constructor. The server creates its rendezvous object using the port number and service name.

When the rendezvous occurs in the local case (within the same JVM), a transaction object is created by the shared rendezvous object and returned to both the client and server. The client and server share this transaction object and use it to communicate request and reply. In the remote case (between JVMs that might be on different physical machines), Java's RMI (object serialization over the network) is used to send the transaction object containing the client's request to the server and to send the transaction object back to the client, now containing the server's reply.

Background Material on Remote Method Invocation

Sun Microsystems has added a remote method invocation capability to Java, the ability to make remote procedure calls. Sun's RMI allows a thread in one JVM to invoke (call) a method in an object in another JVM that is perhaps on a different physical machine. A new thread is created in the other (remote) JVM to execute the called method.

We have used the term ``remote procedure call'' to describe an extended rendezvous between two threads in different JVMs, perhaps on different physical machines. The technical difference between a remote procedure call (RMI) and an extended rendezvous is that when an RMI operation is performed, a new thread is created in the remote JVM to execute the called method. When that method terminates, the thread dies. In the case of an extended rendezvous, the interaction occurs between two existing threads (client and server) that continue to exist after the interaction is complete.

The program Compute.java shows how to use RMI. The ComputeServer remote object implements a Compute interface containing a compute() method that a local Client can call, passing a Work object whose doWork() method the server calls. The client is using the remote server to have work performed on its behalf (adding vectors). Presumably the server is running on a computer architecture that can perform the work more efficiently. Parameters to the remote method and the method's return result, if any, are passed from one JVM to the other using object serialization over the network.