Low-level designCore7 min

Deadlock, livelock and starvation

Threads that each hold one lock and wait for another's can wait forever: a deadlock. Take locks in one fixed order everywhere and the circle can't form. Its cousins are livelock, where threads stay busy undoing each other's moves, and starvation, where one thread never gets its turn.

Watch it evolve1 / 7
The problem

Two movers, two stockrooms

Each move locks both rooms: the one it takes from, then the one it moves to.

80
Start
Stage 1
Stage 2
Final

1 · The situation

Moving stock between two stockrooms

A hardware chain has two stockrooms, Northside and Southside, with 100 units each. Movers shift stock between them, and each move must change both rooms together, so a mover locks both before touching either. The natural way to write it: lock the room you take from, then the room you move to.

Mover A takes from Northside to Southside while Mover B takes from Southside to Northside, on two threads at the same moment. As on the earlier concurrency pages, the first program replays one order of steps that real threads can run in, using a stand-in lock that records its owner.

A mover, and the lock it takesJava
class Mover {
    private final String name;
    private final Stockroom from;
    private final Stockroom to;
    private final List<Stockroom> held = new ArrayList<>();

    Mover(String name, Stockroom from, Stockroom to) {
        this.name = name;
        this.from = from;
        this.to = to;
    }

    void take(Stockroom room) {
        if (room.lock().tryTake(name)) {
            held.add(room);
            System.out.println(name + " locks " + room.name());
        } else {
            String holder = room.lock().owner();
            System.out.println(name + " waits for " + room.name() + ", held by " + holder);
        }
    }

    void move(int n) {
        from.add(-n);
        to.add(n);
        System.out.println(name + " moves " + n + " from " + from.name() + " to " + to.name());
    }

    void releaseAll() {
        for (Stockroom room : held) room.lock().release();
        held.clear();
        System.out.println(name + " releases both");
    }
}

2 · The failure

Each holds what the other needs

Mover A locks Northside
Mover B locks Southside
Mover A waits for Southside, held by Mover B
Mover B waits for Northside, held by Mover A
Each holds what the other needs: deadlock

With real locks, both threads would wait here forever. Nothing fails; the program just stops moving.

A circle of waiting: A waits for B, and B waits for A.

Mover ANorthsidelockMover BSouthsidelockheld bywaits forheld bywaits forMover ANorthsidelockMover BSouthsidelockheld bywaits forheld bywaits for

The wait-for graph: follow the arrows and you come back where you started. A cycle in this graph is a deadlock.

This is a deadlock: two or more threads blocked forever, each waiting for something another one holds. It needs four conditions at once, and breaking any one of them prevents it:

Condition

Here

Broken by

Mutual exclusion

A room's lock has one owner

Data that needs no lock, such as immutable snapshots

Hold and wait

Each mover holds one room while asking for the other

Taking both locks in one step, all or none

No preemption

Nobody can take a lock away from its holder

Trying with a timeout, and letting go of everything on failure

Circular wait

A waits for B, and B waits for A

Taking locks in one fixed order everywhere

3 · The fix

One order for every lock

Give the rooms an order, Northside first, and make every mover lock in that order whichever way its stock goes. Then a circle can't form: whoever gets Northside first gets Southside too, and the other waits at the first lock while holding nothing.

Both movers start by taking Northside. Mover B finds it held and waits, holding nothing; Mover A takes Southside, moves, and releases both, and then B goes ahead.

Java
class Mover {
    private final String name;
    private final Stockroom from;
    private final Stockroom to;
    private final List<Stockroom> held = new ArrayList<>();

    Mover(String name, Stockroom from, Stockroom to) {
        this.name = name;
        this.from = from;
        this.to = to;
    }

    void take(Stockroom room) {
        if (room.lock().tryTake(name)) {
            held.add(room);
            System.out.println(name + " locks " + room.name());
        } else {
            String holder = room.lock().owner();
            System.out.println(name + " waits for " + room.name() + ", held by " + holder);
        }
    }

    void move(int n) {
        from.add(-n);
        to.add(n);
        System.out.println(name + " moves " + n + " from " + from.name() + " to " + to.name());
    }

    void releaseAll() {
        for (Stockroom room : held) room.lock().release();
        held.clear();
        System.out.println(name + " releases both");
    }
}
1*RoomLock− owner: String~ tryTake(String): boolean~ release()~ owner(): StringStockroom− name: String− lock: RoomLock− units: int~ name(): String~ lock(): RoomLock~ units(): int~ add(int)Mover− name: String− from: Stockroom− to: Stockroom− held: List<Stockroom>~ take(Stockroom)~ move(int)~ releaseAll()
Mover A locks Northside
Mover B waits for Northside, held by Mover A
Mover A locks Southside
Mover A moves 5 from Northside to Southside
Mover A releases both
Mover B locks Northside
Mover B locks Southside
Mover B moves 5 from Southside to Northside
Mover B releases both
Northside: 100, Southside: 100

With real threads, each mover makes 10,000 moves in opposite directions. Every run finishes, and the stock adds up:

Both movers finished 10000 moves
Northside: 100, Southside: 100

4 · The cousins

Livelock and starvation

Deadlock is the best known of three ways threads stop making progress:

  • Deadlock: threads are blocked, each waiting for another, forever.
  • Livelock: threads aren't blocked, but each keeps reacting to the others and none gets anywhere. Two movers who each try both locks, back off when the second is busy, and retry at the same instant can do this indefinitely.
  • Starvation: some threads progress, but one can't get the resource it needs for long periods because others keep taking it first, such as a writer behind an endless stream of readers on a read-write lock.

Problem

Are the threads running?

Is anything progressing?

Typical fix

Deadlock

No, all blocked

No

Lock ordering, or taking all locks at once

Livelock

Yes, busily

No

Random or growing back-off before a retry

Starvation

Yes

Yes, except the starved thread

Fair locks or queues that serve in arrival order

Race condition

Yes

Yes, with wrong results

Synchronization or confinement

5 · What it costs

Rules everyone must follow

Every fix has a price:

  • Lock ordering is a rule the whole codebase must follow. One new method that locks in the other order brings the deadlock back, and nothing warns you until it happens.
  • Timeouts and back-off break the hold-and-wait, but add retries, and with bad timing they turn a deadlock into a livelock unless the back-off is randomized.
  • One big lock for both rooms can't deadlock, but every move waits for every other move, even ones between unrelated rooms.

Approach

Can it deadlock?

Cost

Lock order: from, then to

Yes

None, until it hangs

Lock order: lower id first

No

A rule every lock taker must follow

All locks at once (C++ std::scoped_lock)

No

Only for locks known at the same moment

Try with a timeout, release all, retry

No, but can livelock

Retries, and a back-off to tune

One lock for everything

No

No moves in parallel at all

6 · Getting it right

Hold few locks, briefly, in order

  • Write the order down, next to the locks: "rooms are locked in id order". A rule nobody can find isn't followed.
  • Don't call unknown code while holding a lock. A callback or a listener may take locks of its own, in an order you don't control.
  • Hold locks briefly. The shorter the critical section, the smaller the window for a circle to form.
  • Prefer designs without nested locks. Move both values into one object under one lock, or hand the work to a single thread that owns both rooms.

When a program hangs, a thread dump lists each thread and the lock it's waiting for; follow the waits, and a circle in that list is a deadlock. Debuggers in all four languages can pause a hung program and show the same.

7 · Look-alikes

The same problem outside your code

Anything with exclusive locks can deadlock, not only threads in one program. Databases lock rows, and two transactions that update the same two rows in opposite orders deadlock exactly like the movers.

Where

The locks

What happens

Threads in one program

Mutexes and monitors

The threads hang until the program is restarted

Database transactions

Row and table locks

The database detects the circle and aborts one transaction, which the application should retry

Services calling each other

Requests waiting on responses

Each waits for the other until a timeout fires

8 · In practice

What the databases advise

PostgreSQL's documentation shows the movers' deadlock with two bank transactions updating two accounts in opposite orders. It detects such deadlocks and aborts one of the transactions, and it names the best defense: make every application lock multiple objects in a consistent order.

The advice carries straight back to code: one order, taken everywhere, beats every way of detecting and recovering from a deadlock after the fact.

Check yourself

4 questions

1. A new method moves stock from Southside to Northside by locking Southside first. What's the risk?
2. Two movers each grab one lock, find the other busy, release, and retry at the same moment, over and over. What is this?
3. Why can't the ordered movers deadlock?
4. Which change prevents deadlock by removing hold-and-wait?

Takeaways

Remember this

  • A deadlock is threads blocked forever, each waiting for a lock another holds.
  • It needs mutual exclusion, hold and wait, no preemption and circular wait; break any one to prevent it.
  • Taking locks in one fixed order everywhere prevents the circle; C++'s std::scoped_lock takes several at once safely.
  • Livelock is busy threads making no progress; starvation is one thread never getting its turn.
  • Hold few locks, briefly, and never call unknown code while holding one.