Concurrency Primitives: Locks, Conditions and Semaphores

Almost every design problem ends with "what if two threads call this at once?" A few problems make concurrency the whole task, like a bounded blocking queue where producers must wait when it is full and consumers must wait when it is empty. Both come down to a small toolkit: a lock to make a check and an update one atomic step, and a condition variable or semaphore to sleep until the state you need appears.

The idea#

A condition variable lets a thread sleep until another thread signals that the state has changed. The recipe fits in four steps:

1. Create a threading.Lock.
2. Build a threading.Condition on that lock.
3. Inside with condition:, wait() in a while loop until the state you need holds.
4. Change the state, then notify() the threads waiting for the opposite state.

Why while and not if: a thread woken from wait() must re-acquire the lock before it runs, and another thread may get there first and take the item. Wakeups can also happen spuriously, with no notify() at all. Re-checking the condition after every wakeup is the only safe rule.

Why two conditions: with one shared condition, notify() might wake another producer when you meant to wake a consumer, and everyone keeps waiting. One shared condition works if you use notify_all(), at the cost of waking threads that go straight back to sleep. Two conditions on the same lock (not_full, not_empty) let each side wake only the other side.

Put together, the lock makes "check the state, then change it" one atomic step, so no other thread can slip in between. The while loop guarantees that a thread only acts when the state it needs holds right now.

How to spot it#

These cues point to a lock plus a condition or semaphore.

• "blocks until", "wait if the queue is full / empty"
• "multiple producer and consumer threads"
• "print in order", "alternate between two threads"
• in any design follow-up: a read, a decision, then a write on shared state (check-then-act)

Template#

Here is the bounded blocking queue from the opening, built with two conditions on one lock. Each operation follows the same four lines: lock, wait in a while, change the state, notify the other side.

init(capacity):
    items = empty deque
    lock = one Lock
    not_full, not_empty = two Conditions on lock
enqueue(x):
    with not_full:
        while the queue is full: not_full.wait()   # re-check after waking
        append x
        not_empty.notify()                         # wake one consumer
dequeue():
    with not_empty:
        while the queue is empty: not_empty.wait()
        remove the front item
        not_full.notify()                          # wake one producer
        return the item
size():
    with the same lock: return the length          # consistent read

The semaphore version#

A semaphore is a counter that blocks on acquire at zero, so it can count free and filled slots directly. empty_slots starts at capacity and full_slots at 0. A producer takes an empty slot (blocking at zero), appends under a mutex, then releases a full slot. A consumer does the mirror image.

init(capacity):
    empty_slots = Semaphore(capacity)    # room for producers
    full_slots = Semaphore(0)            # items for consumers
    lock = Lock                          # guards the deque
enqueue(x):
    empty_slots.acquire()                # blocks while full
    with lock: append x
    full_slots.release()                 # wakes one consumer
dequeue():
    full_slots.acquire()                 # blocks while empty
    with lock: remove the front item
    empty_slots.release()                # wakes one producer
    return the item

Acquire the semaphore before the mutex. If a producer held the mutex while blocked on a full queue, no consumer could get in to make room: a deadlock. The theory behind this design is in the Producer-Consumer Problem note.

Check-then-act races in design follow-ups#

Locks matter well beyond pure concurrency problems. Most "make it thread-safe" follow-ups in other designs are the same bug: two threads read the same state, both decide, both write.

The last row is the alternative to locking: if data is never modified in place (only appended, with deletes recorded separately), readers can't see a half-done change.

Pitfalls#

Check your code against these before you call it thread-safe.

• if instead of while around wait(). A woken thread may find the state already changed.
• notify() on one shared condition. It can wake the wrong side; use two conditions or notify_all().
• Mutex before semaphore. Holding the lock while blocked on a semaphore deadlocks the queue.
• Calling wait() or notify() without holding the lock. Python raises RuntimeError.
• Reading shared state without the lock. len(deque) happens to be safe in CPython, but holding the lock makes the intent clear and keeps it safe on other runtimes.
• A local lock for a multi-server system. It only protects one process; across servers use an atomic operation in a shared store.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the bounded blocking queue.

• 1603. Design Parking System
• 1114. Print in Order
• 1188. Design Bounded Blocking Queue
• 1115. Print FooBar Alternately

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Lock, condition on the lock, wait() in a while, change state, notify() the other side.
• Two conditions on one lock avoid waking the wrong side; one condition needs notify_all().
• Semaphores count free slots and filled slots; take the semaphore before the mutex.
• Most design races are check-then-act: make the check and the write one atomic step.
• Append-only data plus tombstones lets readers skip locks entirely.