Semaphores · CAP366

A semaphore S is an integer accessed only through atomic wait(S) (decrement; block if it becomes negative) and signal(S) (increment; wake a waiter if S <= 0). A binary semaphore (0/1) works as a mutex; a counting semaphore tracks a number of resource instances.

Trace: S = 2; A, B, C call wait: S = 1, 0, -1 and C blocks. A signal then wakes C and S returns to 0.

Bounded buffer: mutex = 1, empty = N, full = 0. Producer: wait(empty), wait(mutex), add, signal(mutex), signal(full). Consumer mirrors it.

Mistake	Consequence
wait(mutex) before wait(empty) in the producer when full	Deadlock (holds mutex while blocked)
signal(mutex) ... wait(mutex) swapped	Mutual exclusion lost
P1: A then B, P2: B then A	Possible deadlock

Exam pitfall: the order of the two waits matters; waiting on mutex first can deadlock, whereas the order of the two signals does not.

Try two questions

Question 1 · Tier 2, Understand

A spinlock is a lock in which:

The lock is released automatically by the kernel after a fixed time-out
A waiting process sleeps on a queue and is woken when the lock is released
A waiting process loops (busy-waits) until the lock becomes available
The lock may be held by several processes at once, so none of them has to wait

Show the answer

C. Spinlocks avoid context-switch cost but waste CPU cycles; useful for very short critical sections.

Question 2 · Tier 1, Recall

Which pair of operations is defined on a semaphore?

fork (F) and join (J)
wait (P) and signal (V)
request (Q) and grant (G)
open (O) and close (C)

Show the answer

B. wait(S) decrements S (blocks if S would become negative); signal(S) increments S.

Key points

Try two questions