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) {
/*...*/
}
An Implicit Binary Semaphore Prevents Another Race Condition.
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 MyObject.java lets us write P(S) instead of S.P() for a semaphore S.
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?
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.
Bounded buffers can be used to communicate information from one thread to another in a pipeline.
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.
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).
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.
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.
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.
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.
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?
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.
A screen snapshot of the dining philosophers:
Last modified 30 December 1997.
© 1997 Stephen J. Hartley
SJH shartley@mcs.drexel.edu
