Semaphore

operating-systems concurrency

Definition

Semaphore

A semaphore is a synchronisation construct provided by the operating system that allows processes or threads to coordinate access to shared resources without using busy waiting.

A semaphore $S$ is an integer-valued variable that, after initialisation, can only be accessed through two atomic operations: wait (also called $P$) and signal (also called $V$).

Data Structure

A semaphore is typically implemented as a record consisting of an integer value and a queue of processes waiting for the semaphore:

type semaphore = record
    value: integer;
    queue: list of process;
end;

Operations

The operations must be executed atomically by the OS kernel to ensure data consistency.

Initialisation

A semaphore must be initialised with a non-negative integer value and an empty process queue.

procedure init(S, val):
begin
    S.value := val;
    S.queue := empty list;
end;

Wait (P)

The wait operation (also known as $P$ for proberen) decrements the semaphore value. If the resulting value is negative, the calling process is added to the semaphore’s queue and blocked.

procedure wait(S):
begin
    S.value := S.value - 1;
    if S.value < 0 then
    begin
        add this process to S.queue;
        block it;
    end;
end;

Signal (V)

The signal operation (also known as $V$ for vrijgave) increments the semaphore value. If the value is still less than or equal to zero, it indicates that there are processes waiting; one process is removed from the queue and moved to the Ready state.

procedure signal(S):
begin
    S.value := S.value + 1;
    if S.value <= 0 then
    begin
        remove a process P from S.queue;
        place P on ready queue;
    end;
end;

Atomicity of Operations

For semaphores to correctly manage concurrency, the wait and signal operations themselves must be atomic. If the underlying hardware does not provide direct support for atomic increment/decrement with queue management, the OS kernel must protect these procedures using low-level mechanisms such as:

• Disabling interrupts: Ensuring the kernel cannot be preempted while updating the semaphore.
• Spinlocks: Using test-and-set or exchange instructions to protect the semaphore’s internal state.

While this may reintroduce a very brief period of busy waiting, it is only for the duration of the semaphore operation itself, which is significantly more efficient than spinning for an entire critical section.

Types

• Binary Semaphore: The value can only be 0 or 1.
• Counting Semaphore: The value can be any non-negative integer, representing the number of available resource instances.

M-Semaphores

M-Semaphores (Multiple Semaphores) extend the concept by allowing a process to wait on multiple semaphores simultaneously in an atomic manner.

• wait(S1, S2, ..., Sn): The process only proceeds if all semaphores $S_i$ are available (greater than 0). If any semaphore is unavailable, the process blocks on all of them without decrementing any values. This prevents partial resource acquisition and helps avoid deadlocks.