Semaphores: wait, signal, counting and binary semaphores

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What does a TSL lock fail to guarantee? from Lesson 3.1.3
2. What is busy waiting? from Lesson 3.1.2
3. Which state does a process enter while waiting for an event? from Lesson 1.1.1

1 · The Hook

A library has 3 copies of a popular book. A counter on the desk shows how many are left: borrowing subtracts 1, returning adds 1, and if it shows 0 you wait in a queue. That counter is a semaphore, invented by Dijkstra. It can act as a lock (1 copy), count resources (k copies), or make one thing happen before another (0 copies at the start). GATE asks both semaphore arithmetic and "which outputs are possible" puzzles.

3 · Core Concept

Predict First — the answer

3 get through, 2 wait (block).

In plain words

A semaphore is a shared integer you may touch only with two operations. wait (also called P or down): take one unit; if none is left, sleep until one is available. signal (V or up): give one unit back and wake a sleeper if there is one. Both operations are atomic.

1. Definition

Simple (busy-waiting) version:

wait(S)   { while (S <= 0) ;  S--; }
signal(S) { S++; }

Blocking version (no spinning; each semaphore keeps a queue of sleeping processes):

wait(S)   { S--;  if (S < 0)  { add this process to S's queue; block(); } }
signal(S) { S++;  if (S <= 0) { remove a process from S's queue; wake it up; } }

In the blocking version a negative value −k means k processes are waiting.

2. Two kinds

• Binary semaphore (value 0 or 1): a lock, often called a mutex.
• Counting semaphore (any value): k identical resources.

3. Three uses

4. Semaphore arithmetic

For the blocking definition: final value = initial − (number of waits) + (number of signals). Initial 10, then 6 waits and 4 signals → 10 − 6 + 4 = 8.

5. Mistakes with semaphores

• Two processes taking two semaphores in opposite orders can block each other for ever: P1 wait(S); wait(Q); and P2 wait(Q); wait(S); → each holds one and waits for the other (deadlock).
• Forgetting signal (the lock is never released), or using signal before wait by mistake.
• If the queue is LIFO, some process may wait for ever (starvation).

6. "Which outputs are possible?" puzzles

Simulate: keep the semaphore values, and at each moment only allow a process to pass wait(s) if s > 0. Example (s = 0, t = 1):

P1: print "A"; signal(s); wait(t); print "C";
P2: wait(s); print "B"; signal(t);

A must come first (P2 is blocked on s = 0). Then P1 can pass wait(t) at once (t = 1), so C can come before or after B: ABC or ACB.

4 · Visual

Counting semaphore S = 3, five processes call wait

call:     wait  wait  wait  wait  wait
S after:   2     1     0    -1    -2
result:   go    go    go   sleep sleep     (-2 = two sleepers)

signal(S): S = -1, one sleeper wakes and goes

5 · Worked Examples

Example 1 Easy

A counting semaphore starts at 10; then 6 wait and 4 signal operations are done. Final value?

Solution

10 − 6 + 4 = 8.

Example 2 Medium

We want statement B in process P2 to run only after statement A in process P1. Write the code.

Solution

Semaphore s = 0. P1: A; signal(s); P2: wait(s); B;

Example 3 GATE

A counting semaphore is initialised to 7. Then 20 wait and 15 signal operations are performed. What is its final value?

Solution

7 − 20 + 15 = 2.

6 · GATE Traps

• The final-value formula uses the blocking definition (values may go negative).
• Mutex starts at 1; an ordering semaphore starts at 0.
• Every process using the shared data must use the semaphore; one process skipping it brings the race back.
• wait/signal themselves must be atomic (the OS implements them with a short lock).

7 · Memory Hook

"wait takes one or sleeps; signal gives one and wakes; −k = k sleepers."

8 · Connect the Dots

With semaphores we can now solve the famous synchronization puzzles: a bounded buffer, readers and writers, and the dining philosophers.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Arithmetic

A semaphore is initialised to 10. Then 6 wait and 4 signal operations complete. Final value?

Numerical answer: ________

Q2 · NAT · 1 mark(s) — Negative value

In the blocking implementation, a semaphore's value is −3. How many processes are waiting on it?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Ordering

To make statement B (in P2) run only after statement A (in P1), the semaphore used should start at:

1. (A) 0
2. (B) the number of processes
3. (C) 1
4. (D) −1

Q4 · NAT · 1 mark(s) — Counting

A counting semaphore starts at 3 and every process runs wait(S); CS; signal(S);. At most how many processes can be inside CS at the same time?

Numerical answer: ________

Q5 · NAT · 2 mark(s) — Outputs

s = 0, t = 1. P1: print "A"; signal(s); wait(t); print "C"; P2: wait(s); print "B"; signal(t); How many different output strings are possible?

Numerical answer: ________

10 · Rule Card

• wait/P: S--; if S < 0 block. signal/V: S++; if S ≤ 0 wake one. Atomic.
• Negative value −k = k processes waiting. Final value = initial − waits + signals.
• Binary (mutex, starts 1) vs counting (starts k). Ordering semaphore starts 0.
• Opposite orders of waits can deadlock; LIFO queues can starve.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

semaphorewait (P) and signal (V)busy-waiting and blocking implementationsnegative value meaningbinary semaphore (mutex)counting semaphoreordering with a semaphoresemaphore arithmeticpossible-output puzzles