The article An Introduction to Programming with Threads by Andrew D. Birrell (1989) motivates concurrent programming with threads:

• shared memory multiprocessors are cheaper and more common so each thread can be allocated a CPU;
• it is less expensive and more efficient to create several threads in one process that share data than to create several processes that share data;
• IO on slow devices like networks, terminals, and disks can be done in one thread while another thread does useful computation in parallel;
• multiple threads can handle the events (e.g., mouse clicks) in multiple windows in the windowing system on a workstation;
• in a LAN cluster of workstations or in a distributed operating system environment, a server running on one machine can spawn a thread to handle an incoming request in parallel with the main thread continuing to accept additional incoming requests.

The MyObject class contains some methods useful for multithreaded simulations:

nap(milliseconds),
age(),
random(), and
seed(number).

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

• two or more threads share data,
• they are reading and writing the shared data concurrently,
• and the final result depends on who does what 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

• that prevent two threads from being in their critical sections at the same time,
• that have the desirable safety and liveness properties,
• and that allow critical sections to be executed atomically.

• a load/store register architecture,
• multiple concurrently executing threads are sharing data,
• single or multiple CPUs where we cannot make relative speed assumptions,
• accesses to shared variables can be interleaved if two threads are in their critical sections at the same time,
• threads may not halt in their pre- or post-protocols,
• threads may not halt in their critical sections,
• threads may halt outside their critical sections.

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

while (true) {
   outsideCS();
   wantToEnterCS(i);   // pre-protocol
   insideCS();
   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.

   Nancy G. Leveson and Clark S. Turner, ``An Investigation of the Therac-25 Accidents,'' IEEE Computer, Vol. 26, No. 7, July 1993.

   Summarize the poor concurrent programming practices described in the article.

Last modified 30 December 1997.

© 1997 Stephen J. Hartley