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 (the operating system removes the thread from the CPU scheduling or ``ready'' queue) if it must wait to enter its critical section or if the resource it wants is not available.

Mutual exclusion pseudocode:
semaphore S = 1; ... P(S); N=N+1; V(S);

Condition synchronization pseudocode (resource availability):
semaphore tapeDrives = 7; ... P(tapeDrives); useTapeDrive(); V(tapeDrives);

Java has implicit binary semaphores of the form

    Object mutex = new Object();
    synchronized (mutex) {
that can be used for mutual exclusion. Only one thread at a time can be executing inside the synchronized block.

    An Implicit Binary Semaphore Prevents the Race Condition.

    An Implicit Binary Semaphore Prevents Another Race Condition.

      Why is the semaphore mutex also used in the Auditor thread? Isn't it enough just to make the moving of money from one account to another in the ATM thread into a single atomic action?

Java does not have explicit binary and counting semaphores, so they are provided as classes in the Synchronization subdirectory of the lib directory. Their implementation is shown later. Two explicit binary semaphores, one initialized to zero (impossible with an implicit binary semaphore), and one explicit counting semaphore are used to synchronized three threads so they obey the ``rules.'' The ``syntactic sugar'' in lets us write P(S) instead of S.P() for a semaphore S.

    Explicit Binary and Counting Semaphores Synchronize Three Threads.

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 implementation shown uses a circular array and can be used only with a single producer thread and a single consumer thread. Do you see why?

    The Bounded Buffer for a Producer and Consumer.

    The Producer and Consumer Driver.

A linked list can be used to implement a first-in-first-out buffer that is not bounded and can be used by multiple producer threads and multiple consumer threads.

    The Unbounded Buffer for the Producers and Consumers.

    The Producers and Consumers Driver.

Bounded buffers can be used to communicate information from one thread to another in a pipeline.

    A Pipeline Using Bounded Buffers.

Semaphores 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.

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 Sleeping Barber.

Five philosophers sit around a table and think until hungry. Interspersed between the philosophers are five forks. A hungry philosopher must have exclusive access to both its left and right forks in order to eat. If they are not both free, the philosopher waits. The following algorithm does not deadlock (it never happens that all philosophers are hungry, each holding one fork and waiting for the other), 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 neighbor), an advantage, but also allows starvation (a philosopher's two neighbors can collaborate and alternate their eating so the one in the middle never can use the forks).

    The Server for the Dining Philosophers.

    The Dining Philosophers Driver.

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

    The Dining Philosophers Server Where Each Fork is a Semaphore.

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.

    The Dining Philosophers Server Where One is ``Odd''.

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. The solution here allows writers to starve if enough readers keep coming along to read the database that the number of current readers is always above zero.

    The Database for the Readers and Writers.

    The Readers and Writers Driver.

This sequence of attempts to implement counting semaphores with binary semaphores illustrates some of the subtleties of pure binary semaphores and thread scheduling. The first two attempts have a problem if a context switch occurs at point A since then V's on the binary semaphore blocked may get lost. The third solves that problem but introduces more context switching overhead. The last two are good solutions, with the latter being somewhat simpler.

    Attempt 1.

    Attempt 2.

    Attempt 3.

    Attempt 4.

    Attempt 5.

Jurassic Park consists of a safari area, a number of single-passenger safari cars, some number of people, and a museum. Each person in the park visits the museum for a random amount of time, then line up to take a safari ride, waiting for an empty car. Each car waits for a passenger, then goes out on safari for a random amount of time. The following solution has a major flaw. What is it? How can the flaw be fixed?

    Jurassic Park.

Lest you think the use of mutual exclusion locks (binary semaphores) always removes race conditions, read this account of a recent real-life race condition involving the Pathfinder mission to the planet Mars in 1997.

The XtangoAnimator class in the XtangoAnimation subdirectory of the lib directory can be used to animate the dining philosophers.

    Animated Dining Philosophers.

    A screen snapshot of the dining philosophers:

Laboratory Exercises

  1. Examine the bounded buffer for race conditions if there are multiple producer and/or consumer threads. Fix any race conditions you find.
  2. Printing W, X, Y, and Z
  3. Look in some operating systems books for semaphore exercises and write the solutions in Java. Examples are classical problems like the cigarette smokers and the bakery.
  4. Bumper Cars
  5. Multirider Bumper Cars
  6. Baboons
  7. Baboons without Starvation
  8. Building Elevator
  9. Modify the sleeping barber program so there are multiple barbers.
  10. Modify the dining philosophers server so that two philosophers cannot collaborate to starve the one between them.
  11. Modify the readers and writers database so that readers cannot starve writers.
  12. Unidirectional TSP
  13. Animate one or more of these programs.

Last modified 30 December 1997.

© 1997 Stephen J. Hartley