Deadlocks in Databases

Two or more transactions are waiting for each other to release locks — and none of them ever will.

The 4 Coffman Conditions

Deadlock occurs only when ALL 4 conditions hold simultaneously. Break any ONE → deadlock impossible.

1. Mutual Exclusion — A resource can only be held by ONE transaction at a time.
2. Hold and Wait — T1 is HOLDING Lock(A) while WAITING for Lock(B).
3. No Preemption — Locks cannot be forcibly taken away.
4. Circular Wait — T1 waits for T2, T2 waits for T3, T3 waits for T1 → Circular dependency.

Deadlock Detection — Wait-For Graph

• Nodes → Transactions
• Edge → T1 → T2 means T1 is waiting for T2
• If CYCLE exists → Deadlock detected → abort one transaction (usually youngest)

Deadlock Prevention

Approach 1 — Wait-Die (Non-preemptive)

• Older transaction → allowed to WAIT
• Younger transaction → DIES (aborted and restarted)

Approach 2 — Wound-Wait (Preemptive)

• Older transaction → WOUNDS younger (forces abort)
• Younger transaction → allowed to WAIT

Approach 3 — Conservative 2PL

• Transaction locks ALL resources it needs upfront
• Either gets everything or nothing
• No Hold and Wait → no deadlock, but very low concurrency

Deadlock vs Livelock vs Starvation

Type	Description
Deadlock	Transactions stuck, NO progress at all. T1 waits T2, T2 waits T1 → frozen.
Livelock	Transactions keep changing state but NO progress. T1 retries → T2 retries → loop.
Starvation	One transaction NEVER gets resources. Always loses to higher priority transactions.

Deadlock Strategy by Database

Database	Strategy
PostgreSQL	Wait-For Graph detection → abort youngest
MySQL InnoDB	Detection + timeout fallback
Oracle	Detection → abort statement (not whole TX)
SQL Server	Detection → abort lowest cost victim