What is a Semaphore?

A semaphore is an integer variable manipulated only through two atomic operations:

wait(S): while (S <= 0); S = S - 1; signal(S): S = S + 1;

Originally proposed by Edsger Dijkstra. wait is also called P (Dutch proberen — to test); signal is V (verhogen — to increment).

Two Flavors

1. Binary semaphore (mutex) — value 0 or 1, equivalent to a lock.
2. Counting semaphore — value can range over an integer; used to control access to a pool of N identical resources.

Solving the Critical Section with a Semaphore

Initialize mutex = 1 and write each process as:

wait(mutex); / critical section / signal(mutex);

Any process attempting wait(mutex) while another is in the CS finds the value 0 and is queued.

Producer–Consumer with Bounded Buffer

Use three semaphores:

• mutex = 1 — protects buffer.
• empty = N — number of empty slots.
• full = 0 — number of filled slots.

Producer:

wait(empty); wait(mutex); add item; signal(mutex); signal(full);

Consumer:

wait(full); wait(mutex); remove item; signal(mutex); signal(empty);

Reader–Writer Problem

Multiple readers may hold the resource simultaneously, but a writer needs exclusive access. Implemented with a counter readcount, a mutex over the counter, and a semaphore that the first reader takes and the last reader releases.

Implementation Notes

A naive busy-wait wait wastes CPU. Real OS semaphores block the calling process (move it to a wait queue) and the kernel wakes it on signal.

Pitfalls

• Forgetting signal() — process that exits without releasing causes permanent block.
• Wrong order — wait(mutex); wait(empty); (instead of empty first) deadlocks if buffer is full.
• Counting semaphore underflow — calling signal more times than wait.

Comparison: Mutex vs Semaphore

Summary

• Semaphores generalize locks to N units of a resource.
• Two atomic operations (wait, signal) prevent race conditions when used correctly.
• Wrong ordering or missing signals cause classic concurrency bugs.