RightSignal

Operating systems · 7 of 91 / 3

Deadlocks

The concept

Why two bank transfers can freeze each other forever

A deadlock happens when a group of threads each hold a lock and each wait for a lock another one in the group holds, so none of them can ever move. Nothing crashes. The threads just stop, forever.

Two transfers run at once. Alice→Bob locks Alice's account, then asks for Bob's. Bob→Alice has locked Bob's and asks for Alice's. Each waits for the other to let go, and neither will until it finishes.

Deadlock needs all four Coffman conditions: mutual exclusion (one holder per lock), hold and wait (keep locks while waiting), no preemption (nobody takes a lock away) and circular wait (waits form a loop). Remove one and it can't happen.

What it’s forTells you whether a set of threads is deadlocked, by drawing who waits for whom.

deadlock ⇔ the wait-for graph has a cycle T₁ → T₂ → … → T₁

Tᵢ: a thread (or a database transaction)
Tᵢ → Tⱼ: an arrow: Tᵢ is waiting for a lock that Tⱼ holds
cycle: a path of arrows that comes back to where it started

What it givesYes or no: the threads on a cycle are stuck forever, and nobody else will free them.

T1 holds Alice, wants Bob → arrow T1 → T2
T2 holds Bob, wants Alice → arrow T2 → T1
T1 → T2 → T1 is a cycle, so both are deadlocked

Operating systems · 7 of 92 / 3

Deadlocks

Real-life use case

PostgreSQL stops your query with "deadlock detected"

Databases lock rows during transactions, so two transactions that update the same rows in opposite orders can deadlock exactly like the bank transfers. PostgreSQL and MySQL watch for this instead of letting both hang.

After a transaction waits on a lock for deadlock_timeout (1 second by default), PostgreSQL searches the wait-for graph for a cycle. If it finds one, it aborts one transaction with "ERROR: deadlock detected", freeing its locks.

MySQL's InnoDB does the same, saying "Deadlock found when trying to get lock; try restarting transaction". App code should catch the error and rerun the transaction.

Operating systems · 7 of 93 / 3

Deadlocks

How it helps

Grab locks in the same order and the loop can't close

The most common fix in ordinary code is to break circular wait: give every lock a fixed rank and always take locks in rising order. For the transfers, both lock the account with the smaller ID first, whatever the direction of the money.

Why it works: a waiting thread holds only locks ranked below the one it wants, so every wait arrow points upward. A cycle would need ranks to keep rising yet return to the start, which is impossible.

In the transfers, both now want Alice's account first; one gets it, the other waits holding nothing. Other fixes: try-lock with a timeout breaks hold and wait; databases abort a victim (forced preemption).

Your RightSignal

Topics in News

Why two bank transfers can freeze each other forever

PostgreSQL stops your query with "deadlock detected"

Grab locks in the same order and the loop can't close

Got it?