What is a deadlock and how can you prevent it?
A deadlock is when two or more processes wait for each other forever, each holding something the other needs. It needs four conditions together; breaking any one of them, for example always taking locks in the same order, prevents it.
Explain it simply
Two people meet on a narrow bridge from opposite sides. Each refuses to step back until the other moves. Nobody can cross, forever. In a computer, two threads each hold one lock and wait for the lock the other holds. Neither can continue, so both are stuck.
Example
- Thread 1 locks the
Accountstable, then tries to lock theOrderstable. - Thread 2 locks
Orders, then tries to lockAccounts. - Thread 1 waits for Orders, Thread 2 waits for Accounts: deadlock.
The simple fix: decide a global order (always Accounts first, then Orders) and make every thread follow it. Then the circular wait cannot happen.
How it works
A deadlock can only happen when all four Coffman conditions hold at the same time:
- Mutual exclusion: a resource can be used by one process at a time.
- Hold and wait: a process holds one resource while waiting for another.
- No preemption: resources cannot be taken away by force.
- Circular wait: there is a cycle of processes, each waiting for the next.
Operating systems handle deadlocks in three ways: prevention (design so one condition can never hold), avoidance (check each request is safe before granting it, as in the Banker's algorithm), and detection and recovery (let it happen, find the cycle in a wait-for graph, then kill or roll back a process). Many systems simply ignore rare deadlocks and rely on restarts.
Real-world use
- Databases detect deadlocks between transactions and abort one of them with an error; your code should retry.
- Application code prevents them with a fixed lock order, timeouts (
tryLock) and holding locks for as short a time as possible.
Common mistakes
- Confusing deadlock with starvation (a process waits a very long time because others keep getting priority) or livelock (processes keep reacting to each other and make no progress).
- Calling unknown code while holding a lock.
- Taking locks in different orders in different parts of the code.
What to say in the interview
"A deadlock is a state where a set of processes are all blocked, each waiting for a resource held by another. It requires mutual exclusion, hold and wait, no preemption and circular wait. To prevent it I break one of those, most practically circular wait by always acquiring locks in a fixed global order, and I use timeouts and keep critical sections short. Systems can also avoid deadlocks with the Banker's algorithm or detect them with a wait-for graph and recover."
Follow-up questions
- Explain the Banker's algorithm at a high level.
- What is the difference between deadlock, livelock and starvation?
- How do databases resolve deadlocks between transactions?