Chapter 5: Locking and Interprocess Communication
advantages and disadvantages. Some solutions are of an academic nature, and some have found their
way into practice in various operating systems — one solution has been adopted in most systems and is
therefore worth discussing in detail.
Semaphores
Semaphoreswere designed by E. W. Dijkstra in 1965. At first glance, they provide a surprisingly sim-
ple solution to all kinds of interprocess communication problems — but their use calls for experience,
intuition, and caution.
Basically,semaphoresare simply specially protected variables that can represent both positive and nega-
tive integers; their initial value is 1.
Two standard operations are defined to manipulate semaphores —upanddown. They are used to control
entry to and exit from critical code areas, where it is assumed that competing processes have equal access
to the semaphores.
When a process wants to enter critical code, it invokes thedownfunction. This decrements the value of the
semaphore by 1; that is, it sets it to 0 and executes the dangerous section of code. Once it has performed
the programmed actions, theupfunction is invoked to increment the value of the semaphore by 1 — thus
resetting it to its original value. Semaphores are characterized by two special features:
- When a second process tries to enter the critical code section, it too must first perform adown
operation on the semaphore. Because a first process has already entered the code section, the
value of the semaphore is 0. This causes the second process to ‘‘sleep‘‘on the semaphore. In
other words, it waits until the first process has exited the relevant code.
It is of particular importance in the implementation of thedownoperation that it is handled
asan elementary stepfrom the perspective of the application. It cannot then be interrupted by
a scheduler call, and this means that race conditions cannot occur. In the view of the kernel,
querying the variable and modifying its value are two different actions but are seen by the
user as an atomic unit.
When a process sleeps on a semaphore, the kernel puts it in the blocked state and also places
it on a wait list with all other processes waiting on the semaphore.
- When a process exits the critical code section, it performs theupoperation. This not only
increments the value of the semaphore (to 1), but also selects a process sleeping on it. This
process is now able to safely begin execution of the critical code after resuming and complet-
ing itsdownoperation to decrement the semaphore value to 0.
This procedure would not be possible without the special support of the kernel because a userspace
library cannot guarantee that thedownoperation will not be interrupted. Before describing the imple-
mentation of the corresponding functions, it is firstnecessary to discuss the mechanisms that the kernel
itself uses to protect critical code sections. These mechanisms are the basis for the protection facilities
exported to user programs.
Semaphores work well in userland, and could in principle also be used to solve all kinds of in-kernel
locking problems. But they are not: Performance is one of the foremost goals of the kernel, and despite
the fact that semaphores might seem simple to implement at a first glance, their overhead is usually too
large for the kernel. This is why a plethora of different locking and synchronization mechanisms are
available for use in the kernel, which I discuss in the following.
