The idea: two locks, taken in opposite order

A bank moves money between accounts. Each account has its own mutex, and a transfer locks both accounts so nobody sees the money half moved. Thread T1 runs transfer(A, B, 10) and thread T2 runs transfer(B, A, 10) at the same time. Each locks the source account first, then the target. So T1 takes A then B, and T2 takes B then A. If T1 gets A and T2 gets B before either asks for its second lock, T1 holds A and wants B, T2 holds B and wants A. Neither can go on, and neither will let go: a deadlock. This is the "ABBA" lock-order inversion, the deadlock programmers actually hit.

Left: time goes down. 1, T1 lock(A) gets A. 2, T2 lock(B) gets B. 3, T1 lock(B) waits because T2 has B. 4, T2 lock(A) waits because T1 has A. Right: mutex A is held by T1, mutex B is held by T2, T1 wants B and T2 wants A, a cycle T1, B, T2, A, T1.
Four steps are enough: each thread holds one lock and waits for the other's, and the wait-for graph is a cycle.
void transfer(Account *from, Account *to, int amount) {
    pthread_mutex_lock(&from->m);     // T1: A    T2: B
    pthread_mutex_lock(&to->m);       // T1: B    T2: A   <- both may block here
    from->balance -= amount;
    to->balance   += amount;
    pthread_mutex_unlock(&to->m);
    pthread_mutex_unlock(&from->m);
}

How to use the animation

Each thread runs its listing in a loop, one line per step, and every line is atomic. A coloured marker shows the line a thread runs next. Pick a thread and press Step Thread to choose the interleaving yourself, or let the round-robin or random scheduler pick, or run a demo. A thread that blocks moves under the mutex it waits for and its name turns red; the label under its home spot says what it holds and what it waits for. The three tabs are three versions of the same transfer. Under the accounts, three lines check the money (A + B = 200), the wait-for graph and the work done.

Why it hides in tests

The deadlock needs one exact interleaving: both threads must take their first lock before either takes its second. If T1 runs its whole transfer first, nothing goes wrong (Opposite order tab, Demo: lucky schedule). A transfer holds its locks for a few microseconds, so in a test the window is tiny. Under real load, with many threads and preemption at any instruction, it opens sooner or later, and the program hangs with no error message: the threads simply sleep forever (Demo: deadlock).

Deadlock needs all four Coffman conditions at once: mutual exclusion (a mutex has one owner), hold and wait (T1 keeps A while it asks for B), no preemption (nobody can take A away from T1) and circular wait (T1 waits for T2, which waits for T1). Breaking any one of them prevents it. The two practical fixes below each break one. Dining Philosophers shows the same cycle with five threads.

Fix 1: one global lock order

Decide an order for all locks and always take them in that order. For accounts, lock the lower account id first (or the lower address). Now T2, which moves money from B to A, still locks A first. If T1 holds A, T2 waits before it takes any lock, so it blocks nobody (Global lock order tab, Demo: same schedule). A thread holding B already holds A, so nobody holding B ever waits for A: the circular wait is impossible, whatever the scheduler does (Demo: scheduler run).

void transfer(Account *from, Account *to, int amount) {
    Account *first  = from->id < to->id ? from : to;
    Account *second = from->id < to->id ? to : from;
    pthread_mutex_lock(&first->m);
    pthread_mutex_lock(&second->m);
    ...
}

C++ does this for you: std::scoped_lock lk(a.m, b.m); (or std::lock(a.m, b.m)) takes several mutexes with a deadlock-avoiding algorithm, whatever order you name them in. In large programs the order is a documented rule: the Linux kernel lists the order of its locks in comments, and lockdep checks it at run time.

Left, fix 1: both T1 and T2 run lock(A) first. T2 waits on A while holding nothing and gets A later. Everyone takes A before B, so no cycle can form. Right, fix 2: T1 locks A, T2 locks B, T2's trylock(A) fails, T2 unlocks B, T1 locks B and T2 retries. If both back off in lockstep every time, the result is livelock.
A lock order makes the cycle impossible; trylock breaks it after it starts to form, at the risk of livelock.

Fix 2: trylock, then back off

Sometimes the order cannot be known in advance (the second lock depends on what the first one protects). Then take the second lock with pthread_mutex_trylock, which never sleeps: it returns EBUSY at once if the mutex is held. On failure, release the first lock and start over. This breaks hold and wait: a thread never sleeps while it holds a lock (trylock + back off tab, Demo: back off: T2 gives B back and T1 finishes).

The risk is livelock. If both threads run in perfect lockstep, each takes its first lock, fails the trylock and backs off, forever. They are busy, but no transfer finishes (Demo: livelock). Real code sleeps for a random time before retrying, so the two threads soon fall out of step. Java's ReentrantLock.tryLock(timeout) and pthread_mutex_timedlock are the same idea with a wait limit.

fixbreakscost
Global lock ordercircular waitevery code path must follow the rule; the order must be known before locking
trylock + back offhold and waitwasted work on retry; livelock without random back-off
One big lock(only one lock: no cycle)no parallelism between transfers

Finding lock-order bugs

A deadlocked process uses no CPU and prints nothing. A thread dump shows it: gdb's thread apply all bt or Java's jstack (which reports "Found one Java-level deadlock") shows each thread stuck in a lock call, holding the lock another one wants. Tools catch the inversion before it hangs: ThreadSanitizer reports "lock-order-inversion (potential deadlock)" when it has seen A-then-B on one path and B-then-A on another, even if the run did not deadlock, and the kernel's lockdep does the same for kernel locks. Databases detect the cycle at run time and roll back a victim instead; see Two-Phase Locking and Deadlock Detection.

See also Mutex with a Futex for what lock() does while a thread sleeps, and the Banker's algorithm for deadlock avoidance when every thread declares its needs in advance.

How an operating system finds a deadlock in a resource-allocation graph and recovers, see Deadlock Detection.

What the page leaves out

Each line is one atomic step on a single CPU, and a woken waiter must retry its lock. The page leaves out timed locks, random back-off times, recursive (reentrant) mutexes that deadlock a thread with itself, reader-writer locks, deadlocks with three or more threads and locks, deadlocks that mix locks with condition variables or with joins, and the resource-allocation-graph detection an operating system can run.