Concurrency

Liveness Hazards: Deadlock & Friends

Safety failures compute wrong answers; liveness failures compute nothing forever. Deadlock (cyclic lock waits) is the star hazard; livelock and starvation are its cousins. The cure is design: consistent lock ordering and open calls.

Deadlock recipe: two threads acquiring the same two locks in opposite orders
Prevention #1: a global lock ordering, applied everywhere (tie-break by System.identityHashCode)
Prevention #2: open calls — never call alien methods while holding a lock
Prevention #3: tryLock with timeout turns deadlock into recoverable failure
Diagnose with thread dumps (jstack/jcmd Thread.print) — the JVM prints found deadlocks
Resource deadlocks count too: pools, bounded queues, JDBC connections

The classic: transferMoney (JCiP 10.1)

// Thread A: transfer(checking, savings)  → locks checking, wants savings
// Thread B: transfer(savings, checking)  → locks savings, wants checking → DEADLOCK
public void transfer(Account from, Account to, long amount) {
    synchronized (from) {
        synchronized (to) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}

The fix: induce a total order on locks

public void transfer(Account from, Account to, long amount) {
    Account first = from, second = to;
    if (System.identityHashCode(from) > System.identityHashCode(to)) {
        first = to; second = from;              // always lock in canonical order
    }
    synchronized (first) {
        synchronized (second) {
            from.debit(amount);
            to.credit(amount);
        }
    }
}   // (equal hashes: add a global tie-breaker lock — rare but required for correctness)

Deadlocks are probabilistic bombs: they need the unlucky interleaving, so they pass tests and detonate under production load (JCiP's phrasing). The lock-ordering discipline removes the possibility. Alien-method calls while holding locks (EJ 79) reintroduce it invisibly — you can't know what locks the callee takes. An open call (no locks held) restores composability.

Starvation: a thread never gets CPU or a lock (priority abuse, unfair locks under pathological contention). Livelock: threads actively retry and perpetually collide — two-polite-people-in-a-corridor; randomized backoff breaks the symmetry. Missed signals: waiting without a condition loop. All three are rarer than deadlock and share the same medicine: simple, well-ordered coordination.