3.3Semaphores
The idea
A semaphore is an integer with two atomic operations: P (wait) decrements or blocks, V (signal) increments and wakes a waiter.
Think of it like this: A coat-check with a fixed number of hangers: P takes a hanger or makes you wait, V returns one.
Why it exists
It is the standard building block for mutual exclusion and for making one process wait for another.
How it works
- Initialise: 1 for a lock, n for n identical resources, 0 for "wait for an event".
- P(S): wait until S > 0, then S = S − 1.
- V(S): S = S + 1.
- Always pair them, and take multiple semaphores in the same order everywhere.
Worked example: Semaphore initialised to 2 used as a mutex
Two processes pass P together and both enter the critical section: mutual exclusion is lost. A mutex semaphore must start at 1.
Now play with it
- →In the lab, run T1 P(mutex), then T2 P(mutex): T2 is blocked.
- →Pick the "initial value 2" scenario and let both threads in.
With mutex = 1 only one thread can pass P. Remove it (set to 2) to see both inside. P(s) waits until s > 0 then decrements; V(s) increments.
| Semaphore start value | Use |
|---|---|
| 1 (binary) | mutual exclusion lock |
| n (counting) | n identical resources, e.g. n buffer slots |
| 0 | make one process wait for an event or an order of execution |
P (wait): if S > 0 then S = S − 1, otherwise block. V (signal): S = S + 1 and wake one waiter. Both must be atomic.
Check yourself
A semaphore S initialised to 0 is typically used to
Exam notes (the dense version)
A semaphore is an integer with two atomic operations: P (wait): wait until S > 0, then S = S − 1; V (signal): S = S + 1 (waking one waiter). A binary semaphore (initial 1) acts as a mutex lock; a counting semaphore (initial n) controls n identical resources. A semaphore initialised to 0 enforces an order (A must run before B). Typical bugs: P and V swapped, P(S) twice in a row, P on two semaphores in opposite orders (deadlock).
Previous year questions: Synchronization & Concurrency (10)
PYQs are grouped by topic, so this is the full set for Synchronization & Concurrency; try the ones that match this subtopic. Open all 10 on the topic page.