Chapter 18 — Locks, semaphores, and deadlock

In one sentence

A lock lets you turn a multi-step operation into something that behaves as if it were ONE uninterruptible step, at the cost of real risk: two locks taken in inconsistent order can leave everyone waiting on each other, forever.

Why this matters

Locks are the standard fix for Chapter 17's race conditions — and getting them wrong (holding them too long, acquiring them in inconsistent order) creates a different, equally real class of production incident: the deadlock.

How it actually works

   A MUTEX (mutual exclusion lock) is the simplest form: only ONE
   thread/process can HOLD it at a time. Anyone else trying to acquire
   it BLOCKS (waits) until the holder releases it.

     lock(mutex)
       counter += 1     // now genuinely safe: nobody else can be in
                        // here at the same time
     unlock(mutex)

   A SEMAPHORE generalises this: it allows up to N holders at once
   (a mutex is just a semaphore with N=1) -- useful for things like
   "allow at most 5 concurrent connections to this resource."

   DEADLOCK is the classic failure mode of locking: two (or more) threads
   each hold a lock the OTHER one needs, and neither will ever release
   what it has:

     Thread A:  locks Resource1, then tries to lock Resource2 (blocked --
                B has it)
     Thread B:  locks Resource2, then tries to lock Resource1 (blocked --
                A has it)
     -> both wait FOREVER. Nothing will ever unblock either of them.

   FOUR CONDITIONS must ALL be true for deadlock to occur (the classic
   formulation, from Coffman et al., 1971) -- and breaking ANY ONE of
   them prevents it:
     1. MUTUAL EXCLUSION       resources can't be shared (inherent to
                              locks)
     2. HOLD AND WAIT          a thread holds one resource while waiting
                              for another
     3. NO PREEMPTION          a resource can't be forcibly taken away
     4. CIRCULAR WAIT          a cycle of threads each waiting on the
                              next

   THE MOST COMMON REAL-WORLD FIX: always acquire multiple locks in the
   SAME, CONSISTENT ORDER, everywhere in your codebase (e.g. always lock
   "lower resource ID before higher resource ID") -- this breaks
   condition 4, circular wait, and is simple enough to actually follow
   as a team-wide convention.

Real-world example

   NASA's Mars Pathfinder rover, after landing successfully in July
   1997, began experiencing unexplained total system resets days into
   its mission -- a serious, publicly documented problem for an
   irreplaceable spacecraft millions of miles from Earth. The cause,
   diagnosed and famously explained afterward by the mission's lead
   developer Glenn Reeves, was a PRIORITY INVERSION bug, a close
   relative of this chapter's deadlock family: a LOW-PRIORITY task
   would occasionally acquire a mutex protecting a shared information
   bus, then get PREEMPTED by MEDIUM-priority tasks (which had nothing
   to do with that mutex at all) before it could finish and release the
   lock. Meanwhile, a HIGH-priority task that actually NEEDED that same
   mutex sat blocked, waiting -- and because the medium-priority tasks
   kept the LOW-priority lock-holder from ever running long enough to
   finish, the high-priority task could be starved long enough to trip
   a watchdog timer, causing the whole system to reset.
   Engineers on Earth DIAGNOSED and FIXED this remotely by enabling
   "priority inheritance" (a real-time-scheduling technique where a
   low-priority task temporarily BORROWS the priority of whoever is
   waiting on its lock, so it can finish and release quickly) --
   uploaded to the rover as a patch, resolving the resets. It remains
   one of the most famous, well-documented real demonstrations that
   locking bugs are not merely academic: they took down a Mars rover,
   and the fix is a named, standard technique specifically because this
   class of problem recurs.

Try it yourself

# Fix the race condition from Chapter 17 with a proper lock, and see
# the difference
cat > lockfix.py << 'EOF'
import threading

counter = 0
lock = threading.Lock()

def increment():
    global counter
    for _ in range(100000):
        with lock:            # now the read-modify-write IS atomic
            counter += 1

threads = [threading.Thread(target=increment) for _ in range(4)]
for t in threads: t.start()
for t in threads: t.join()
print(f"expected 400000, got {counter}")   # now always correct
EOF
python3 lockfix.py   # run it several times -- always 400000 now

Common mistakes

Holding a lock longer than necessary. Do the minimum work inside the locked section — slow I/O or expensive computation inside a lock turns a small critical section into a bottleneck for every other thread waiting on it.
Acquiring locks in inconsistent order across different code paths. This is THE most common real-world cause of production deadlocks — establish and enforce a consistent lock-ordering convention.
"My code doesn't have explicit locks, so it can't deadlock." Database row locks, distributed locks (Redis, ZooKeeper), and other implicit locking mechanisms can deadlock exactly the same way — this isn't unique to hand-written mutexes.

Check yourself

What does a mutex guarantee, and what's the difference between a mutex and a semaphore?
List the four conditions required for deadlock, and name one way to break the cycle.
In the Mars Pathfinder case, what specifically caused the high-priority task to be starved, and how was it fixed?