Deadlock: when locks block everything

"With locks everywhere, we're safe, right?" Actually, no: locks can block everything.

The example: two crossed transfers

Alice sends money to Bob, and Bob sends money to Alice, at the same time. Each transfer first locks one account, then asks for the other:

1. Alice locks account A.
2. Bob locks account B.
3. Then each asks for the other's account.

Nobody lets go: Alice holds A and waits for B, Bob holds B and waits for A. Both wait, forever. That is a deadlock. What creates it is not a crossing: it is a cycle, where each one holds a resource while asking for the other's.

The fix: the same order for everyone

Everyone locks in the same order: account A, then B. Alice takes A. Bob, who also wants A, waits empty-handed. Alice takes B, finishes, releases A and B. Then Bob goes.

Remember

Same order for everyone: no cycle, so no deadlock. Bob may still wait a while, but never forever.

Good to know: databases like PostgreSQL detect this kind of cycle and cancel one of the transactions, which must then be replayed.