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 Java, 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 (1989) motivates concurrent programming with threads:

The MyObject class contains some methods useful for multithreaded simulations:

    random(), and
A program can sleep for some number of milliseconds. The age() method returns, in milliseconds, the elapsed time since the program started. The random number generator can be seeded and returns a double in the range zero to one. It also contains some ``syntactic sugar'' for use with semaphores, described later.

    Utility methods in Class MyObject.

This is a skeleton (model or template) for a multithreaded simulation.

    A Multiple Thread Simulation.

In JDK 1.0.2 and 1.1 for Solaris 2.x, Java threads are not time sliced, as the following test program, Beeping, shows. Java threads are time sliced on Windows 95/NT, though. The first two sample runs show the difference. Use a Scheduler object to get pseudo time slicing of threads on Sun's Solaris 2.x. The third sample run of Beeping shows it working on Solaris.

    A Class for Time Slicing Threads.

    Testing for Time Sliced Threads.

This program creates two windows, each a subclass of Frame, with some buttons to control the thread in each window that computes Fibonacci numbers. There is another thread in the Java virtual machine that is blocked, waiting for events like button clicks in the windows. When a button is clicked, the action() method is called by this thread to process the click. Meanwhile, the other two threads can be computing concurrently and displaying the Fibonacci numbers in their windows. Try coding this as a purely sequential program with only one thread or flow of control!

    Fibonacci Numbers and Stop Button.

A screen snapshot:

This example shows how to send the output of each thread to a different file. This technique may be useful for debugging.

    Sending Each Thread Output to a Different File.

Two threads doing N=N+1 at about the same time is called a race condition since one of the updates can get lost. In general, race conditions are possible when

Three different kinds of race conditions are illustrated with Java programs.

Multiple threads doing sum=fn(sum,m) to the shared variable sum is a race condition like N=N+1. Note that one Racer object is created; then two threads are created in that object and the two threads share the sum variable. The Windows 95 sample runs show that if M is large enough, the threads run in pseudo parallel due to time slicing; the Solaris sample runs show there is no time slicing.

    A Race Condition.

There is a fixed $10 million in this bank (10,000 accounts that each start out with $1000) but the auditor sometimes sees more, sometimes less. If the bank auditor is adding up the account balances while some funds are being moved from one account to another, an inaccurate total can be calculated. Can you explain how more money than is really there shows up sometimes in the sample output?

    A Different Kind of Race Condition.

If two threads try to manipulate a queue at the same time, a node can get lost. Remember that the two threads may be executing in round-robin fashion on a shared CPU and that context switches can occur at any time.

    A Queue Race Condition.

The following sequence of queue snapshots shows node 4 not in the queue even though thread A appended it.

These examples show that 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, as this example shows. Since it uses a lot of CPU cycles, busy waiting is inefficient. Blocking somehow would be better.

    Busy Waiting Bounded Buffer for a Producer and Consumer.

    Producer and Consumer Driver.

We can try to remove busy waiting from the bounded buffer by using the thead suspend() and resume() methods, but we end up introducing race conditions. It is possible, if a context switch occurs at just the ``right'' time, for both the producer and the consumer to become suspended: the producer because the bounded buffer is full and the consumer waiting for a resume() that never happens. Do you see how?

    Suspend/Resume Bounded Buffer for a Producer and Consumer.

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: 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, also called a ``safety'' property (absence of unnecessary delay). And no thread should have to wait forever to enter its critical section, also called a ``liveness'' property (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'' (p. 60 Andrews' Concurrent Programming book). 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 done as if they were one atomic action to avoid race conditions.

The mutual exclusion problem is to devise a pre-protocol and a post-protocol based on either hardware or software

The ground rules are

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

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

This sequence of examples shows successful and unsuccessful attempts to solve the mutual exclusion problem in software without specialized hardware instructions like test-and-set.

    Testing the Attempts.

    First Attempt: Strict Alternation.

    Second Attempt: Check Other's Flag Variable, Then Set Own.

    Third Attempt: Set Own Flag Variable, Then Check Other's.

    Fourth Attempt: Back Off.

    Dekker's Solution: Take Turns Backing Off.

    Peterson's Shorter Solution.

    Lamport's Bakery Algorithm: Two Threads Only.

    Lamport's Bakery Algorithm: Arbitrary Number of Threads.

Laboratory Exercises

  1. Use the ``beep'' program to determine if your platform time slices threads.
  2. Try some other values for the -M command line argument of the ``race'' program to determine the approximate time slice size on your system.
  3. What can go wrong (race condition) in the busy waiting bounded buffer if there is more than one producer thread and/or more than one consumer thread?
  4. Race Conditions
  5. More Race Conditions
  6. Multithreaded Adaptive Quadrature
  7. Unidirectional TSP
  8. ``Game of Life''
  9. Read the following article. Summarize the poor concurrent programming practices described in the article.

Last modified 30 December 1997.

© 1997 Stephen J. Hartley