Mutexes, semaphores and the bathroom key

The fix for a race is to allow one thread into the critical section at a time. Three tools, in order of how much they can express.

Mutex

A lock with two states and one owner. The thread that locks it is the only one that may unlock it.

pthread_mutex_lock(&m);
counter++;                 // critical section
pthread_mutex_unlock(&m);

This is the bathroom key on a fob: one key, whoever holds it is inside, everyone else waits.

Semaphore

A counter, not a lock, and nobody owns it. wait decrements and blocks at zero; signal increments.

A semaphore starting at 1 behaves like a mutex, which is why they get confused. A semaphore starting at 5 lets five threads through, which a mutex cannot do: five parking spaces, not one bathroom.

Because nobody owns it, one thread may signal a semaphore another thread waited on. That is what makes it right for signalling rather than protecting: producer and consumer, where one thread announces that work exists.

Monitor

A language-level construct: the lock is attached to the data, so you cannot touch the data without holding it. Java's synchronized is one. It removes the commonest bug, which is forgetting to lock at all.

The three requirements

Any correct solution needs all three:

1. 1Mutual exclusion. One thread inside at a time.
2. 2Progress. If nobody is inside, somebody waiting gets in. No stalemate.
3. 3Bounded waiting. A thread cannot be skipped over forever.