Mutexes, Semaphores and Monitors
How threads safely share data. Race conditions, critical sections, the difference between a mutex and a semaphore, and a bounded buffer built on a condition variable, with code that was run.
A mutex lets one thread into a critical section at a time and only its owner unlocks it, while a semaphore is a counter that admits up to N threads and any thread can signal. A monitor pairs a lock with condition variables for waiting on state. Interviewers expect wait() inside a while loop because of spurious wakeups.
A race condition happens when the result depends on the timing of threads touching shared data. A mutex lets only one thread into a critical section at a time, a semaphore is a counter that allows up to N threads in, and a monitor bundles a lock with condition variables so threads can wait for a state change.
- A race condition is a bug where the result depends on thread timing; count += 1 is three steps (read, add, write), so two threads can lose an increment.
- A correct critical-section solution must guarantee mutual exclusion, progress and bounded waiting.
- With a lock around count += 1, four Python threads doing 100,000 increments each always produced a total of 400000.
- A mutex has an owner and only that thread may unlock it, while a semaphore is a counter any thread can release; a binary semaphore has no ownership.
- In a test of threading.Semaphore(2), eight threads ran but never more than two held the semaphore at the same time.
- A condition variable wait() must be called inside a while loop, because spurious wakeups happen and another thread may change the state before the waiter runs.
01The problem: a race condition
count += 1 looks like one step. It is three: read the value, add one, write it back. If two threads each read 10 before either writes, both write 11. One increment is lost. The outcome depends on the exact timing, which changes from run to run, so the bug may appear one time in a thousand and vanish when you add a print statement to debug it.
The stretch of code that touches shared data, here the read-add-write, is called a critical section. A correct solution must guarantee mutual exclusion (only one thread inside at a time), progress (if no one is inside, someone waiting can enter), and bounded waiting (no thread waits forever).
02Mutex: one thread at a time
import threading
count = 0
lock = threading.Lock()
def work(n):
global count
for _ in range(n):
with lock: # acquire ... release
count += 1
threads = [threading.Thread(target=work, args=(100000,)) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print(count) # 400000With the lock the total is always 400000. Without it, the total can come out lower, and differently each run (how often depends on the Python version and machine).
A mutex has an owner. The thread that locked it must be the one to unlock it. (Python's threading.Lock does not enforce this and any thread may release it; threading.RLock and pthread error-checking mutexes do.) Use with lock: (or try/finally) so the lock is released even if the code inside raises an exception. Forgetting to unlock on an error path is a classic way to freeze a program.
03Semaphore: a counter with wait and signal
A semaphore holds a non-negative integer. acquire (also called wait or P) decrements it, and blocks if it is zero. release (signal or V) increments it and wakes a waiter. Dijkstra introduced it in the 1960s.
A semaphore initialised to 1 acts like a mutex (a binary semaphore), with one difference: any thread can release it, not just the one that acquired it. A semaphore initialised to N limits concurrency, such as at most 2 database connections in use.
import threading, time
sem = threading.Semaphore(2)
active = peak = 0
guard = threading.Lock()
def job():
global active, peak
with sem:
with guard:
active += 1
peak = max(peak, active)
time.sleep(0.05)
with guard:
active -= 1
threads = [threading.Thread(target=job) for _ in range(8)]
for t in threads: t.start()
for t in threads: t.join()
print(peak) # 2Eight threads ran, but never more than two at the same time.
04Monitors and condition variables
Sometimes mutual exclusion is not enough. A consumer thread must wait until a producer has put something in a buffer. Spinning in a loop wastes CPU. A monitor solves this: it is a lock together with one or more condition variables. A thread holding the lock can call wait, which atomically releases the lock and sleeps, and another thread calls notify after changing the state to wake it.
Java builds this into every object (synchronized, wait(), notify()). In Python it is threading.Condition.
import threading
from collections import deque
class BoundedBuffer:
def __init__(self, size):
self.items = deque()
self.size = size
self.cond = threading.Condition()
def put(self, x):
with self.cond:
while len(self.items) == self.size: # while, not if
self.cond.wait()
self.items.append(x)
self.cond.notify_all()
def get(self):
with self.cond:
while not self.items:
self.cond.wait()
x = self.items.popleft()
self.cond.notify_all()
return x
buf, out = BoundedBuffer(3), []
prod = threading.Thread(target=lambda: [buf.put(i) for i in range(10)])
cons = threading.Thread(target=lambda: [out.append(buf.get()) for _ in range(10)])
prod.start(); cons.start(); prod.join(); cons.join()
print(out) # [0, 1, 2, ..., 9]With a producer putting 0 to 9 into a buffer of size 3 and a consumer taking 10 items, the consumer gets [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] in order. The producer blocks when the buffer is full and the consumer blocks when it is empty.
05Why `while` and not `if` around wait
This is the most common mistake with condition variables. After wait returns, the condition may no longer be true. Another thread may have taken the item in between, or the OS may wake a thread spuriously, which is permitted and does happen. So the check must be in a loop: wait until the condition holds, every time.
A related point: signalling before anyone is waiting is lost. A condition variable is not a counter. If you need the memory of a signal, use a semaphore, or keep the state in a variable that the condition checks.
06Choosing the right tool
Use a mutex to protect a data structure. Use a semaphore to cap how many threads use a resource, or to signal between threads when you want the signal counted. Use a monitor with condition variables for producer-consumer and anything else that involves waiting for a state.
Also keep critical sections small. A lock held during a slow operation, such as a network call, serialises every thread behind it. And take locks in a consistent order if you need more than one, or you invite a deadlock, which is the next topic in this path.
Where you can, avoid shared mutable state. Message passing and thread-safe queues such as Python's queue.Queue do the locking inside, so your code cannot get it wrong.
07Common interview questions
Q: Difference between a mutex and a semaphore?
A: A mutex has an owner and only that thread may unlock it. A semaphore is a counter any thread can signal. A binary semaphore looks like a mutex but has no ownership.
Q: What is a race condition?
A: A bug where the result depends on the relative timing of threads accessing shared data.
Q: What are the requirements for a critical-section solution?
A: Mutual exclusion, progress, and bounded waiting.
Q: Why is wait() called in a while loop?
A: Because of spurious wakeups and because another thread may change the state first, the condition must be re-checked.
Q: What is a spinlock and when is it used?
A: A lock where the thread busy-waits in a loop. It makes sense only when the wait is very short, usually inside the kernel on multi-core machines.
Q: Solve the producer-consumer problem.
A: A bounded buffer with a lock and two conditions (not full, not empty), or two counting semaphores for empty and full slots plus a mutex.