Lesson 2 · Synchronization and deadlocks

Mutexes, Semaphores, and Monitors

The mutex, semaphore and monitor operating system primitives solve overlapping problems and are constantly confused. The distinction is simple once stated: a mutex has an owner, a semaphore has a count, and a monitor bundles a lock with the ability to wait for a condition.

Mutex: Ownership Is the Point

A mutex (mutual exclusion lock) has exactly two states, locked and unlocked, and — crucially — an owner. The thread that locks it is the only thread permitted to unlock it. Attempting to unlock a mutex you do not hold is an error, not a clever trick.

That ownership is not bookkeeping pedantry; it enables things a plain counter cannot do. Because the system knows who holds the lock, it can implement priority inheritance, temporarily boosting the holder's priority when a higher-priority thread blocks on it, which is the standard defence against priority inversion.

Ownership also enables recursive (reentrant) mutexes, where the owner may lock again without deadlocking itself, and it makes error detection possible — a runtime can tell you that you double-locked or unlocked something you never held.

Use a mutex when the answer to 'may this thread proceed' is 'only if nobody else is inside'. Keep the critical section small, always release on every path including exceptions, and prefer scoped wrappers — std::lock_guard, synchronized, with lock: — so an early return cannot leak the lock.

Two states plus an owner; only the owner unlocks
Ownership enables priority inheritance and recursion
Unlocking a mutex you do not hold is an error
Always use a scoped wrapper so early returns cannot leak it

Semaphore: A Counter With No Owner

A semaphore is an integer with two atomic operations: wait (P, down) decrements and blocks if the result would be negative, and signal (V, up) increments and wakes a waiter. Dijkstra introduced it in 1965 and the model has not needed changing.

A counting semaphore models a pool of N interchangeable resources — five database connections, three printers, a bounded buffer of size 10. Initialise to N, and the count is precisely the number still available. A mutex cannot express this at all.

A binary semaphore is initialised to 1 and looks like a mutex, but the difference is real: it has no owner, so any thread may signal it, including one that never waited. That is a bug when you meant mutual exclusion, and the entire point when you mean signalling — thread A waits for something thread B will finish, and B signals when done.

So the choice is by intent. Protecting shared state that must be entered and left by the same thread: mutex. Counting available resources, or one thread notifying another that an event occurred: semaphore. Using a binary semaphore as a mutex works right up until someone signals it from the wrong thread and mutual exclusion silently evaporates.

wait/P decrements and may block; signal/V increments and wakes
Counting semaphores model N interchangeable resources
Binary semaphores have no owner — that is the difference
Mutex for exclusion, semaphore for counting and signalling

Key reference

Terms, operations, and practical uses

Mutex

OwnershipOnly the locking thread may unlock it.
Priority inheritanceBoosts the holder when a higher-priority thread blocks.
Recursive mutexThe owner may lock again without self-deadlock.
Scoped lockinglock_guard, synchronized, with — an early return cannot leak.

Semaphore

wait (P)Decrements, blocking if the count would go negative.
signal (V)Increments and wakes one waiter.
CountingModels N interchangeable resources; a mutex cannot.
BinaryLooks like a mutex but has no owner — anyone may signal.

Condition variables

waitAtomically releases the lock and sleeps — that atomicity is the point.
Lost wakeupWhat happens if release and sleep are not atomic.
Spurious wakeupPermitted by POSIX and Java — hence always a while loop.
Thundering herdBroadcasting when signal would do wakes everyone pointlessly.

Code example

Bounded buffer with counting semaphores

# Bounded-buffer producer/consumer with counting semaphores.
# empty counts free slots, full counts items -- the mutex only guards the list.
# A producer that finds no empty slot blocks; here the consumer runs instead,
# which is why some items are consumed while production is still going.
CAPACITY = 3
empty, full = CAPACITY, 0
buffer, high, consumed = [], 0, 0

def consume():
    global empty, full, consumed
    if full == 0:
        return None
    full -= 1                      # wait(full): claim an item
    item = buffer.pop(0)
    empty += 1                     # signal(empty): free the slot again
    consumed += 1
    return item

def produce(item):
    global empty, full, high
    if empty == 0:                 # wait(empty) blocks -- the consumer drains one
        consume()
    empty -= 1                     # take a free slot
    buffer.append(item)            # critical section, guarded by the mutex
    high = max(high, len(buffer))
    full += 1                      # signal(full): one more item available

produced = 0
for i in range(5):
    produce(i)
    produced += 1
while full:                        # drain whatever is still buffered
    consume()

print(f"buffer max {high} | produced {produced} | consumed {consumed} "
      f"| permits back to {empty}")

#include <algorithm>
#include <deque>
#include <iostream>
using namespace std;
// Bounded-buffer producer/consumer with counting semaphores.
// empty counts free slots, full counts items -- the mutex only guards the list.
// A producer that finds no empty slot blocks; here the consumer runs instead,
// which is why some items are consumed while production is still going.
const int CAPACITY = 3;
int emptySlots = CAPACITY, fullSlots = 0, high = 0, consumed = 0;
deque<int> buffer;
int consume() {
    if (fullSlots == 0) return -1;
    fullSlots--; // wait(full): claim an item
    int item = buffer.front();
    buffer.pop_front();
    emptySlots++; // signal(empty): free the slot again
    consumed++;
    return item;
}
void produce(int item) {
    if (emptySlots == 0) consume(); // wait(empty) blocks -- consumer drains one
    emptySlots--; // take a free slot
    buffer.push_back(item); // critical section, guarded by the mutex
    high = max(high, (int)buffer.size());
    fullSlots++; // signal(full): one more item available
}
int main() {
    int produced = 0;
    for (int i = 0; i < 5; i++) {
        produce(i);
        produced++;
    }
    while (fullSlots) consume(); // drain whatever is still buffered
    cout << "buffer max " << high << " | produced " << produced
    << " | consumed " << consumed << " | permits back to " << emptySlots << "\n";
}

import java.util.ArrayDeque;
import java.util.Deque;
class Main {
    // Bounded-buffer producer/consumer with counting semaphores.
    // empty counts free slots, full counts items -- the mutex guards the list.
    // A producer that finds no empty slot blocks; here the consumer runs
    // instead, so some items are consumed while production is still going.
    static final int CAPACITY = 3;
    static int emptySlots = CAPACITY, fullSlots = 0, high = 0, consumed = 0;
    static Deque<Integer> buffer = new ArrayDeque<>();
    static int consume() {
        if (fullSlots == 0) return -1;
        fullSlots--; // wait(full): claim an item
        int item = buffer.poll();
        emptySlots++; // signal(empty): free the slot again
        consumed++;
        return item;
    }
    static void produce(int item) {
        if (emptySlots == 0) consume(); // wait(empty) blocks -- consumer drains
        emptySlots--; // take a free slot
        buffer.add(item); // critical section under the mutex
        high = Math.max(high, buffer.size());
        fullSlots++; // signal(full): one more item
    }
    public static void main(String[] args) {
        int produced = 0;
        for (int i = 0; i < 5; i++) {
            produce(i);
            produced++;
        }
        while (fullSlots > 0) consume(); // drain whatever is still buffered
        System.out.println("buffer max " + high + " | produced " + produced
        + " | consumed " + consumed + " | permits back to " + emptySlots);
    }
}

Inputcapacity 3, five items produced

Outputbuffer max 3 | produced 5 | consumed 5 | permits back to 3

Example

Run the example step by step

Output

Condition Variables and the Loop That Is Not Optional

Locks answer 'may I touch this'. They cannot answer 'has this become true yet'. A condition variable fills that gap: a thread holding a lock can wait, which atomically releases the lock and sleeps, then reacquires the lock when woken.

That atomic release-and-sleep is the whole reason condition variables exist. Checking a condition, releasing a lock, and sleeping as three separate steps has a race — the state can change in the gap, the signal fires with nobody waiting, and the thread sleeps forever waiting for something that already happened. This is the lost wakeup.

Waiting must always be inside a while loop testing the predicate, never an if. Three reasons, each sufficient: spurious wakeups are permitted by POSIX and Java and do occur; notifyAll wakes every waiter but only one may proceed; and another thread may consume the condition between the signal and your reacquiring the lock.

signal wakes one waiter, broadcast/notifyAll wakes all. Signal when any single waiter can handle it and all waiters are equivalent; broadcast when waiters are waiting on different predicates sharing one condition variable. Broadcasting when signal would do causes a thundering herd — every thread wakes, contends for the lock, and all but one goes back to sleep.

wait atomically releases the lock and sleeps
Without that atomicity you get lost wakeups
Always while, never if — spurious wakeups are real
Signal for equivalent waiters, broadcast for differing predicates

Monitors and the Classic Problems

The mutex semaphore monitor operating system comparison is completed by the third primitive. A monitor bundles shared data, the lock protecting it, and the condition variables for waiting, with the language guaranteeing that only one thread executes inside at a time. Java's synchronized methods with wait/notify are monitors; so are Python's threading.Condition and C#'s lock.

The advantage is that the lock cannot be forgotten. With raw mutexes, one code path that touches shared state without acquiring first breaks everything and is invisible in review. A monitor makes the association structural rather than a convention people have to remember.

The producer-consumer problem is the standard exercise: producers add to a bounded buffer, consumers remove, and neither may proceed when the buffer is full or empty respectively. The semaphore solution is elegant — an empty semaphore initialised to N, a full semaphore initialised to 0, and a mutex for the buffer itself. Acquire in the wrong order (mutex before the counting semaphore) and it deadlocks, which is the lesson.

The readers-writers problem asks that many readers may share access while a writer needs exclusivity. The naive solution starves writers under continuous reads; the writer-preference variant starves readers instead. Real read-write locks pick a policy explicitly, and only pay off when reads genuinely dominate — under mixed load a plain mutex is often faster, because the read-write lock's own bookkeeping costs more than the contention it avoids.

Mutex vs semaphore vs monitor — the classic compare-and-contrast answer
	Mutex	Semaphore	Monitor
What it holds	A lock, held or free	An integer count	A lock plus condition variables
Has an owner	Yes	No	Yes, the thread inside
Who may release	Only the owner	Any thread	The thread inside
Counts resources	One	N interchangeable	One
Priority inheritance	Possible	Not possible	Possible
Enforced by	The programmer	The programmer	The language
Use it for	Mutual exclusion	Counting and signalling	Exclusion plus waiting on a condition

A monitor makes the lock structural, not a convention
Producer-consumer: empty and full semaphores plus a mutex
Acquiring the mutex before the counting semaphore deadlocks
Read-write locks only pay off when reads clearly dominate