Study notes · 10% of the exam

Locks, Semaphores, Condition Variables and Barriers

Pick the right primitive (mutex, semaphore, condition variable, reader-writer lock, barrier, once) and use it so that progress is guaranteed and nothing blocks while holding a lock it shouldn't.

Key points

1
A mutex gives exclusion and has an owner; a semaphore is an ownerless counter of permits for bounding concurrency or signalling.
2
Condition variables are stateless: always wait on a predicate, under the same lock that guards that predicate, inside a while loop.
3
Java, Python, pthreads and Go use Mesa semantics: notify is a hint, so the woken thread must re-check its condition.
4
Never block on one resource while holding a lock the provider of that resource needs (semaphore-before-mutex order, no I/O under locks).
5
Don't call foreign code (listeners, callbacks) while holding a lock; snapshot under the lock and call outside it.
6
Spin only for very short waits on multicore; adaptive mutexes spin briefly then park, and futexes make the uncontended path syscall-free.
7
Reader-writer locks: reader preference can starve writers, and read-to-write upgrades deadlock when two readers try at once.

Common traps

Using if instead of while around wait(), which breaks on stolen and spurious wakeups.
Notifying before the waiter starts waiting with no shared flag: the lost wakeup.
A plain Semaphore silently grows past its limit on an extra release; use BoundedSemaphore for pools.

Read the source

Test yourself on Locks, Semaphores, Condition Variables and Barriers

Ten questions, with the answer and explanation after each one.