Chapter 3: The Core Hazards: Race Conditions, Deadlock, Livelock, Starvation

Why this matters

These four hazards account for nearly every concurrency bug that will ever land on your desk. Each has a precise definition, a minimal reproducible example, and a standard fix — and being able to correctly name which one you're looking at is what turns a confusing, intermittent production bug into a targeted, fixable diagnosis instead of a mystery.

Race condition

[BEGINNER] A race condition occurs when the correctness of a result depends on the relative timing or interleaving of concurrent operations — Chapter 1's counter += 1 example is the canonical case. The specific, most common shape is a check-then-act race: checking a condition, then acting on it, with another thread able to invalidate the condition in between.

import threading

balance = 100

def withdraw(amount):
    global balance
    if balance >= amount:          # CHECK
        # <-- another thread can run its own withdraw() HERE, in this exact gap -->
        balance -= amount          # ACT
        print(f"Withdrew {amount}, balance now {balance}")
    else:
        print(f"Insufficient funds for {amount}")

t1 = threading.Thread(target=withdraw, args=(80,))
t2 = threading.Thread(target=withdraw, args=(80,))
t1.start(); t2.start()
t1.join(); t2.join()
# Both threads can see balance=100, both pass the check, both withdraw --
# balance ends at -60, even though a single withdrawal of 80 should have
# left the OTHER one correctly rejected.

The fix — a lock, closing the gap between check and act:

import threading

balance = 100
lock = threading.Lock()

def withdraw(amount):
    global balance
    with lock:  # only ONE thread can be inside this block at a time
        if balance >= amount:
            balance -= amount
            print(f"Withdrew {amount}, balance now {balance}")
        else:
            print(f"Insufficient funds for {amount}")

Deadlock

[BEGINNER] A deadlock occurs when two or more threads are each waiting for a resource the other holds, with neither able to proceed — the thread-level instance of the same four conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) covered at the OS/process level in the companion Operating System book's Chapter 10.

import threading

lock_a = threading.Lock()
lock_b = threading.Lock()

def thread_1():
    with lock_a:
        print("Thread 1 acquired lock A")
        threading.Event().wait(0.1)  # simulate some work, widening the race window
        with lock_b:                  # waits for lock_b, held by thread_2
            print("Thread 1 acquired lock B")

def thread_2():
    with lock_b:
        print("Thread 2 acquired lock B")
        threading.Event().wait(0.1)
        with lock_a:                  # waits for lock_a, held by thread_1
            print("Thread 2 acquired lock A")

t1 = threading.Thread(target=thread_1)
t2 = threading.Thread(target=thread_2)
t1.start(); t2.start()
t1.join(); t2.join()
# Thread 1 holds A, waiting for B. Thread 2 holds B, waiting for A. Neither
# ever proceeds. The program hangs forever -- no crash, no error, just silence.

The fix — consistent lock ordering, breaking the circular wait:

def thread_1():
    with lock_a:      # BOTH threads now acquire A before B, consistently
        with lock_b:
            print("Thread 1 acquired both locks")

def thread_2():
    with lock_a:      # same order as thread_1 -- no circular wait is possible
        with lock_b:
            print("Thread 2 acquired both locks")

Livelock

[BEGINNER] A livelock occurs when threads are actively responding to each other — not blocked, genuinely executing — but still make no real progress, because each one keeps changing state specifically to avoid a conflict, and that avoidance itself keeps recreating the conflict.

import threading
import time

class Resource:
    def __init__(self):
        self.in_use_by = None

resource = Resource()

def polite_worker(name, other_name):
    for _ in range(5):
        if resource.in_use_by is None:
            resource.in_use_by = name
            time.sleep(0.01)
            if resource.in_use_by == other_name:
                # "Oh, someone else wants it too -- let me back off politely."
                print(f"{name} backs off for {other_name}")
                resource.in_use_by = None
                time.sleep(0.01)
                continue
            print(f"{name} successfully used the resource")
            resource.in_use_by = None
            return
    print(f"{name} gave up after repeated polite backing-off -- LIVELOCK")

t1 = threading.Thread(target=polite_worker, args=("A", "B"))
t2 = threading.Thread(target=polite_worker, args=("B", "A"))
t1.start(); t2.start()
t1.join(); t2.join()
# Both threads are constantly active (never blocked/waiting) -- but if their
# timing stays synchronized, both keep politely backing off for each other,
# and NEITHER makes real progress. Unlike deadlock, this is visible as high
# CPU activity with zero forward progress, not silence.

The fix — break the symmetry, so both sides don't back off identically:

import random

def less_polite_worker(name, other_name):
    for _ in range(5):
        if resource.in_use_by is None:
            resource.in_use_by = name
            time.sleep(random.uniform(0.005, 0.02))  # RANDOM delay breaks the synchronized pattern
            if resource.in_use_by == other_name:
                if random.random() < 0.5:  # only back off SOMETIMES, not every time
                    resource.in_use_by = None
                    continue
            print(f"{name} successfully used the resource")
            resource.in_use_by = None
            return

Starvation

[BEGINNER] Starvation occurs when a thread is perpetually denied the resources it needs to proceed, not because of a cycle (as in deadlock), but because other threads are repeatedly, unfairly favored ahead of it — directly connected to the companion OS book's Chapter 4 scheduling-fairness discussion.

import threading
import time

lock = threading.RLock()
low_priority_starved = True

def high_priority_worker():
    for _ in range(20):
        with lock:
            time.sleep(0.01)  # does its work while holding the lock frequently and briefly

def low_priority_worker():
    global low_priority_starved
    # In an UNFAIR lock implementation, this thread might keep losing the race
    # to acquire the lock against a much more frequent competitor, indefinitely.
    with lock:
        low_priority_starved = False
        print("Low priority worker finally got the lock")

The fix — fairness mechanisms: a fair lock implementation (one that grants access in request order, FIFO, rather than allowing arbitrary or priority-based reordering) prevents indefinite starvation by guaranteeing every waiter is eventually served; alternatively, priority aging (the same OS book Chapter 4 mechanism — gradually increasing a waiting thread's effective priority the longer it waits) guarantees eventual progress even in a priority-based system. Python's standard threading.Lock does not guarantee strict FIFO fairness, which is worth knowing explicitly rather than assuming.

Common mistakes

1. Confusing deadlock (silent, no CPU activity, threads genuinely blocked) with livelock (visible CPU activity, threads genuinely busy, but no real progress) — the diagnostic signature is different, and confusing the two sends debugging effort in the wrong direction.
2. Fixing a check-then-act race condition by adding a lock only around the "act" step, not the "check" step — the entire check-then-act sequence must be inside the same critical section, or the race persists exactly as before.
3. Assuming Python's GIL prevents race conditions entirely — it prevents certain low-level memory-corruption bugs but does NOT prevent logical race conditions like check-then-act, as Chapter 1 and this chapter's examples both demonstrate concretely.
4. Treating starvation as "just bad luck" rather than investigating lock fairness or priority configuration — persistent, one-sided resource denial is a diagnosable, fixable pattern, not an unavoidable fact of concurrent systems.

Checklist: recognizing and fixing each hazard

1. Race condition: look for a check-then-act sequence (or any read-modify-write) on shared state without a lock spanning the entire sequence — fix by locking the whole sequence, not just part of it.
2. Deadlock: look for multiple locks acquired in inconsistent orders across different code paths — fix with a consistent, global lock-acquisition order.
3. Livelock: look for threads that are CPU-active but reporting no progress, especially involving "polite" retry/backoff logic that might stay synchronized — fix by introducing randomness or asymmetry to break the synchronization.
4. Starvation: look for a thread/task that's persistently denied a resource despite not being in any cycle — fix with a fair (FIFO) lock/scheduling mechanism, or explicit priority aging.

Discussion / interview questions

1. "What's the difference between a deadlock and a livelock?" Strong answer: Deadlock: threads are blocked, waiting on each other in a cycle, with zero activity — visible as a silent hang. Livelock: threads are actively executing, responding to each other, but their mutual responses keep preventing real progress — visible as busy CPU activity with no forward progress.

2. "How would you fix the specific deadlock caused by two threads acquiring the same two locks in opposite orders?" Strong answer: Enforce a single, consistent global lock-acquisition order across every code path that needs both locks — breaking the circular wait condition structurally, so no cycle can ever form.

3. "Does Python's Global Interpreter Lock (GIL) prevent race conditions?" Strong answer: No — the GIL ensures only one thread executes Python bytecode at a literal instant, but a logical race condition (like check-then-act on shared state, or even counter += 1, which is multiple bytecode operations) can still occur because the GIL can switch between threads mid-sequence, exactly as shown in this chapter's examples.

4. "What is starvation, and how does it differ from deadlock?" Strong answer: Starvation is a thread being perpetually denied a needed resource due to unfavorable, repeated prioritization of other threads — no cycle is involved, unlike deadlock; fixed via fairness mechanisms (FIFO locks) or priority aging, rather than lock-ordering discipline.

Chapter summary / cheat sheet

Hazard	Signature	Root cause	Standard fix
Race condition	Wrong/inconsistent results, no hang	Unsynchronized access to shared mutable state (often check-then-act)	Lock the ENTIRE check-then-act sequence
Deadlock	Silent hang, zero CPU activity	Circular wait on multiple locks	Consistent global lock-acquisition order
Livelock	Busy CPU, zero progress	Symmetric, synchronized mutual avoidance	Break symmetry (randomness, asymmetric backoff)
Starvation	One thread perpetually denied, others proceed fine	Unfair scheduling/lock granting	Fair (FIFO) locks, or priority aging

• All four hazards are recognizable, nameable, and have standard fixes — the diagnostic skill is matching the observed symptom (hang vs. busy-no-progress vs. wrong result vs. one-sided denial) to the correct hazard before applying a fix.

---