Semaphore (programming) - Semantics and Implementation

Semantics and Implementation

One important property of these semaphore variables is that their value cannot be changed except by using the wait and signal functions.

Counting semaphores are equipped with two operations, historically denoted as V (also known as signal) and P (or wait)(see below). Operation V increments the semaphore S, and operation P decrements it. The semantics of these operations are shown below. Square brackets are used to indicate atomic operations, i.e., operations which appear indivisible from the perspective of other processes.

The value of the semaphore S is the number of units of the resource that are currently available. The P operation wastes time or sleeps until a resource protected by the semaphore becomes available, at which time the resource is immediately claimed. The V operation is the inverse: it makes a resource available again after the process has finished using it.

A simple way to understand wait and signal operations is:

• wait: Decrements the value of semaphore variable by 1. If the value becomes negative, the process executing wait is blocked, i.e., added to the semaphore's queue.
• signal: Increments the value of semaphore variable by 1. After the increment, if the pre-increment value was negative (meaning there are processes waiting for a resource), it transfers a blocked process from the semaphore's waiting queue to the ready queue.

Many operating systems provide efficient semaphore primitives that unblock a waiting process when the semaphore is incremented. This means that processes do not waste time checking the semaphore value unnecessarily.

The counting semaphore concept can be extended with the ability to claim or return more than one "unit" from the semaphore, a technique implemented in UNIX. The modified V and P operations are as follows:

function V(semaphore S, integer I): function P(semaphore S, integer I): repeat: [if S >= I: S ← S - I break]

To avoid starvation, a semaphore has an associated queue of processes (usually a first-in, first out). If a process performs a P operation on a semaphore that has the value zero, the process is added to the semaphore's queue. When another process increments the semaphore by performing a V operation, and there are processes on the queue, one of them is removed from the queue and resumes execution. When processes have different priorities the queue may be ordered by priority, so that the highest priority process is taken from the queue first.

If the implementation does not ensure atomicity of the increment, decrement and comparison operations, then there is a risk of increments or decrements being forgotten, or of the semaphore value becoming negative. Atomicity may be achieved by using a machine instruction that is able to read, modify and write the semaphore in a single operation. In the absence of such a hardware instruction, an atomic operation may be synthesized through the use of a software mutual exclusion algorithm. On uniprocessor systems, atomic operations can be ensured by temporarily suspending preemption or disabling hardware interrupts. This approach does not work on multiprocessor systems where it is possible for two programs sharing a semaphore to run on different processors at the same time. To solve this problem in a multiprocessor system a locking variable can be used to control access to the semaphore. The locking variable is manipulated using a test-and-set-lock (TSL) command.