Semaphores

Semaphores were designed by E. W. Dijkstra in 1965. At first glance, they provide a surprisingly simple solution to all kinds of interprocess communication problems — but their use calls for experience, intuition, and caution.

Basically, semaphores are simply specially protected variables that can represent both positive and negative integers; their initial value is 1.

Two standard operations are defined to manipulate semaphores — up and down. 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 the down function. 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, the up function 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:

1. When a second process tries to enter the critical code section, it too must first perform a down 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 the down operation that it is handled as an elementary step from 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.

2. When a process exits the critical code section, it performs the up operation. 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 completing its down operation 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 the down operation will not be interrupted. Before describing the implementation of the corresponding functions, it is first necessary 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.

Continue reading here: Kernel Locking Mechanisms

Was this article helpful?

0 0