Deadlock
Operating Systems · 10 interview questions
Deadlock is a set of processes each holding a resource and waiting for one held by another, so none can proceed. It requires four conditions simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait. Break any one and deadlock is impossible.
There are four strategies. Prevention attacks one of the conditions structurally — for example, requiring all resources be requested at once, or imposing a global ordering to make circular wait impossible. Avoidance allows requests but only grants those that leave the system in a safe state, which is what the Banker's algorithm computes. Detection lets deadlock happen, finds cycles in a wait-for graph, and recovers by aborting a victim. Ignoring it is the strategy most general-purpose operating systems actually choose.
Interviewers ask about this because the same theory explains database deadlocks and application-level lock ordering bugs, which are things you will genuinely meet.
Deadlock interview questions
- What are the four necessary conditions for deadlock?
- Mutual exclusion, hold and wait, no preemption, and circular wait. All four must hold at once, so eliminating any single one prevents deadlock.
- Why can't you usually eliminate mutual exclusion?
- Because some resources are inherently non-shareable — a printer or a write lock can't be used by two processes at once. It's the condition least available to attack.
- How do you eliminate hold and wait?
- Require a process to request every resource it needs at once, and to hold none while waiting. It works but wastes resources held long before use, and can starve processes needing popular combinations.
- What's the practical way to eliminate circular wait?
- Impose a global ordering on resources and require they be acquired in that order. It's the most usable prevention technique, and it's the same advice as 'always take locks in a consistent order'.
- Why they ask: The one that transfers directly into real code.
- What is a safe state?
- One where some ordering of processes exists in which each can obtain its maximum remaining need and finish. A safe state is never deadlocked; an unsafe state may or may not deadlock.
- What does the Banker's algorithm do?
- Before granting a request, it simulates the allocation and checks whether a safe sequence still exists. If not, the request waits. It requires each process to declare its maximum need in advance, which is why it's rarely used in practice.
- How does deadlock detection work?
- Build a wait-for graph of who is blocked on whom and look for a cycle. With one instance per resource type a cycle means deadlock; with multiple instances a cycle is necessary but not sufficient.
- Why they ask: The multiple-instance caveat is the detail that separates a memorised answer.
- How does a system recover once deadlock is detected?
- Abort processes — all of them, or one at a time until the cycle breaks — or preempt resources and roll back. Victim selection weighs work done so far, priority, and how many resources would be freed.
- Why do general-purpose operating systems often ignore deadlock?
- Because it's rare and the alternatives are expensive. Prevention constrains legitimate programs, avoidance needs maximum-need declarations, and detection costs cycles continuously. Rebooting occasionally is cheaper — the ostrich algorithm.
- How is deadlock different from starvation?
- Deadlocked processes will never proceed — the situation is permanent without intervention. A starving process could proceed at any moment; the scheduler simply keeps choosing others.
You'll forget most of this by next week
That's not a discipline problem, it's how memory works. In the app these come back on an expanding schedule — right before you'd lose them.
Start free for 7 days