Deadlock and how to avoid it

Key points

• Deadlock: thread A holds lock 1 and wants 2, thread B holds 2 and wants 1. Neither ever moves again.
• Every deadlock needs a cycle in the wait-for graph. Break the cycle and deadlock cannot happen.
• Cheapest fix: global lock ordering. Everyone acquires locks in the same order, sorted by id, hash or name.
• Second option: tryLock with a timeout, then release what you hold, back off and retry.
• Best of all: hold one lock at a time, and never call code you do not control while holding a lock.
• To diagnose a hang, run jstack <pid>. The JVM prints "Found one Java-level deadlock" and both stacks.

Example

import java.util.concurrent.locks.ReentrantLock;

public class Main {
    static class Account {
        final int id;
        final ReentrantLock lock = new ReentrantLock();
        int balance;
        Account(int id, int balance) { this.id = id; this.balance = balance; }
    }

    // Deadlock needs a cycle. Always lock the lower id first and no cycle can form.
    static void transfer(Account from, Account to, int amount) {
        Account first  = from.id < to.id ? from : to;
        Account second = from.id < to.id ? to : from;
        first.lock.lock();
        try {
            second.lock.lock();
            try {
                if (from.balance >= amount) { from.balance -= amount; to.balance += amount; }
            } finally { second.lock.unlock(); }
        } finally { first.lock.unlock(); }
    }

    public static void main(String[] args) throws InterruptedException {
        Account a = new Account(1, 1000);
        Account b = new Account(2, 1000);

        Thread t1 = new Thread(() -> { for (int i = 0; i < 1000; i++) transfer(a, b, 1); });
        Thread t2 = new Thread(() -> { for (int i = 0; i < 1000; i++) transfer(b, a, 1); });
        t1.start(); t2.start();
        t1.join();  t2.join();

        System.out.println("a       : " + a.balance);
        System.out.println("b       : " + b.balance);
        System.out.println("total   : " + (a.balance + b.balance) + " (no deadlock, nothing lost)");
    }
}

Same locks, same order, every single time.