Semaphores

An integer counter with atomic wait and signal that threads use to coordinate access to shared data.

A semaphore is an integer counter with two atomic operations, used to coordinate threads that share data. wait() (also called P) tries to take a permit: it decrements the counter, and if no permit is free the thread blocks until one is. signal() (V) returns a permit: it increments the counter and wakes a waiting thread. The letters P and V come from Dutch — Edsger Dijkstra introduced semaphores in the 1960s.

wait and signal

wait(S):              // P
  S = S - 1
  if S < 0:
    block this thread and add it to S's queue

signal(S):            // V
  S = S + 1
  if S <= 0:
    wake one thread from S's queue

wait and signal must be atomic

If two threads run wait at the same instant and the decrement isn't atomic, both can read the same value and both think a permit was free — re-creating the very race the semaphore exists to prevent. The OS guarantees these operations are indivisible.

Binary vs counting

1Binary semaphore (mutex) — the count starts at 1, so exactly one thread can be inside the critical section at a time. It's used as a lock.
2Counting semaphore — the count starts at N, admitting up to N threads at once — useful for N identical copies of a resource, such as N database connections in a pool.

Worked example — protecting a shared counter

semaphore mutex = 1;   // binary semaphore, used as a lock

// every thread runs:
wait(mutex);           // enter the critical section
balance = balance + 1; // shared update, now safe
signal(mutex);         // leave the critical section

Without the mutex, two threads could both read balance as 5, both compute 6, and both write 6 — losing one update, a classic race condition. The binary semaphore forces the read-modify-write to happen one thread at a time, restoring mutual exclusion.

Counting as a resource pool

Initialize a counting semaphore to the number of available copies — say connections = 5. Each wait checks one out and each signal returns one; the 6th thread simply blocks until someone calls signal. No explicit count-keeping needed.

OperationTimeSpace

wait / signal · blocks rather than busy-waitsO(1)O(1) + wait queue

Check yourself

A binary semaphore is initialized to 1. How many threads can be inside the critical section at the same time?