Semaphore

operating-systems concurrency

Definition

Semaphore

A semaphore is a synchronisation construct allowing processes to coordinate access to shared resources without busy waiting. An integer-valued variable $S$ accessed only through two atomic operations: wait ($P$) and signal ($V$).

Data Structure

Implementation

typedef struct {
    int value;
    queue process_queue;
} semaphore;

Operations

Initialisation

void init(semaphore *S, int val) {
    S->value = val;
    S->queue = empty;
}

Wait (P)

Decrements value. If negative, process is blocked and added to queue.

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->queue;
        block();
    }
}

Signal (V)

Increments value. If still $\le 0$, unblocks a waiting process.

void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove process P from S->queue;
        wakeup(P);
    }
}

Atomicity

Atomic Operations

wait and signal must be atomic. Hardware mechanisms:

• Disabling interrupts: Kernel cannot be preempted during update
• Spinlocks: Using test-and-set or exchange

Brief busy waiting during semaphore operations is acceptable — much more efficient than spinning for an entire critical section.

Types

Binary Semaphore

Value can only be 0 or 1. See Binary Semaphore.

Counting Semaphore

Value can be any non-negative integer, representing available resource instances. See Counting Semaphore.

M-Semaphores

Allow atomic waiting on multiple semaphores simultaneously. Process proceeds only if all $S_i>0$, preventing partial resource acquisition and helping avoid deadlocks.