Races, deadlocks and starvation

How to detect a data race, the four conditions a deadlock needs, lock ordering and timeouts as the practical fixes, and the difference between live-lock and starvation.

Finding a race

A data race is two threads accessing the same memory with at least one write and no synchronisation. The behaviour is undefined, so the symptom may be a wrong value, a crash or nothing at all on your machine.

# ThreadSanitizer: compile and run with instrumentation
gcc -fsanitize=thread -g -O1 program.c -o program && ./program
# WARNING: ThreadSanitizer: data race
#   Write of size 4 at 0x... by thread T2:
#     #0 increment counter.c:12

# Helgrind, part of Valgrind, for binaries you cannot rebuild
valgrind --tool=helgrind ./program

# Go has it built in
go test -race ./...
go run -race main.go

A race can be harmless in practice for years and then manifest under different load, a new CPU or a compiler change.
Guard shared state with a lock, or make the access atomic; choosing neither is the bug.
Read-only data needs no lock as long as nothing mutates it after publication.
Sanitizers are the only practical way to find these before production; add them to CI.

The four conditions and the fixes

Condition	Meaning	Break it by
Mutual exclusion	A resource is held exclusively	Use lock-free structures where feasible
Hold and wait	A thread holds one resource and waits for another	Acquire everything at once, or release before waiting
No preemption	A held resource cannot be taken away	Use timeouts and retry from scratch
Circular wait	A cycle of threads each waiting on the next	Impose a global lock order
All four together	Necessary for deadlock	Removing any one prevents it

# deadlock: thread A locks account 1 then 2, thread B locks 2 then 1
def transfer(a, b, amount):
    with locks[a.id], locks[b.id]:       # order depends on argument order
        a.balance -= amount
        b.balance += amount

# fixed: always acquire by a stable key, never by call order
def transfer_safe(a, b, amount):
    first, second = sorted([a, b], key=lambda x: x.id)
    with locks[first.id], locks[second.id]:
        a.balance -= amount
        b.balance += amount

# second line of defence: try-lock with a timeout, then back off
def with_timeout(lock, seconds=1.0):
    if not lock.acquire(timeout=seconds):
        raise TimeoutError("could not acquire; back off and retry")

A consistent lock order is the single most effective fix. Document the order next to the locks, and review any code that acquires two of them.

Live-lock, starvation and priority inversion

Starvation — a thread never gets the resource because others keep winning. Unfair locks and unbounded priority differences cause it.
Live-lock — threads keep acting but make no progress, typically two threads repeatedly backing off and retrying in step.
Priority inversion — a high-priority thread waits on a lock held by a low-priority thread that cannot be scheduled. A priority-inheritance or priority-ceiling protocol fixes it.
Convoying — one slow holder forces the whole group to queue behind each lock acquisition in the same order.

# find threads stuck waiting on a lock
gdb -p 12345 -batch -ex "thread apply all bt" 2>/dev/null | grep -B2 -A5 "pthread_mutex_lock\|__lll_lock_wait"

# the kernel reports hung tasks after a timeout
dmesg | grep -i "hung_task\|blocked for more than"
cat /proc/sys/kernel/hung_task_timeout_secs

💡

Add jitter to any retry and backoff loop. Two threads that back off for exactly the same interval retry at the same moment, collide again, and can stay in lockstep indefinitely — the classic live-lock.

FAQ

Is a deadlock always deterministic?

No. It depends on timing, so it may appear only under load or only on a machine with a different core count. That is why lock ordering and timeouts are preferred to reproducing the deadlock in a test.

Can a deadlock happen with a single lock?

Not on itself unless it is non-recursive and the same thread locks twice. It can happen with one lock plus a resource that is never released, or between the lock and a blocking operation inside the critical section.

Synchronisation: locks, mutexes and semaphores Concurrency models: threads, async and processes

Last refreshed 2026-09-18.

Races, deadlocks and starvation

Finding a race

The four conditions and the fixes

Live-lock, starvation and priority inversion

FAQ

Related