Deadlocks in Operating Systems

A deadlock is a situation where a group of processes are each waiting for a resource held by another process in the same group, so none of them can ever proceed. A deadlock can only occur when four conditions hold at once: mutual exclusion, hold and wait, no preemption and circular wait, and every handling strategy breaks at least one.

3 min read

A deadlock is a situation where two or more processes are stuck waiting on each other forever. Each process holds a resource another process needs, and each is waiting for a resource that a different process in the same cycle is holding. Since nobody releases anything, nobody can move forward, and the system stays frozen in that state indefinitely.

The four conditions that must all hold

A deadlock cannot happen unless all four of these are true at once. This is the standard checklist taught in every OS course, and it matters because every deadlock-handling strategy works by breaking at least one of them.

  1. Mutual exclusion. At least one resource must be held in a non-shareable way, only one process can use it at a time.
  2. Hold and wait. A process is holding at least one resource while waiting to acquire additional resources currently held by other processes.
  3. No preemption. A resource can only be released voluntarily by the process holding it, the OS cannot forcibly take it away.
  4. Circular wait. There's a cycle of processes, each waiting for a resource held by the next process in the cycle.

A worked example

Say two processes, P1 and P2, and two resources, R1 (a printer) and R2 (a scanner).

  1. P1 requests and is granted R1.
  2. P2 requests and is granted R2.
  3. P1 now requests R2, but P2 is holding it, so P1 blocks and waits.
  4. P2 now requests R1, but P1 is holding it, so P2 blocks and waits.

P1 is waiting for R2, held by P2. P2 is waiting for R1, held by P1. Neither can proceed, neither will release what it's holding, because releasing only happens after a process finishes using a resource, and neither can finish. This is a deadlock, and it can be represented as a cycle in a resource allocation graph: P1 to R2 to P2 to R1 to P1.

Why this matters beyond a toy example

Real deadlocks in production systems usually involve database locks, not printers. Two transactions that each lock a row the other one needs next produce exactly this same cycle, and most production databases (PostgreSQL, MySQL, SQL Server) run a background deadlock detector specifically to catch and break this pattern automatically, usually by picking one transaction as the "victim" and rolling it back so the other can proceed.

What interviewers actually ask about deadlocks

  • "What are the four necessary conditions for a deadlock?" Mutual exclusion, hold and wait, no preemption, circular wait, all four must hold simultaneously.
  • "If I remove one of the four conditions, is a deadlock still possible?" No. All four are necessary; removing any single one makes a deadlock impossible, which is exactly the basis for prevention strategies.
  • "How is a deadlock different from starvation?" A deadlock is a permanent standstill with no possible resolution without intervention; starvation is a process being repeatedly denied a resource but still theoretically able to eventually get it.
  • "How would you detect a deadlock has occurred?" By building a resource allocation graph or wait-for graph from current process/resource states and checking for a cycle.

Key takeaways

  • A deadlock is a set of processes each waiting on a resource the next process in a cycle is holding.
  • All four conditions (mutual exclusion, hold and wait, no preemption, circular wait) must hold at once.
  • A resource allocation graph with a cycle is the formal signature of a deadlock.
  • Real databases run background deadlock detectors and resolve deadlocks by rolling back one transaction.
All 205 OS interview questions

Browse all Operating Systems topics

Log in to save which topics you've read across every subject.

Frequently asked questions

What are the four necessary conditions for a deadlock?

Mutual exclusion, hold and wait, no preemption, circular wait, all four must hold simultaneously.

If I remove one of the four conditions, is a deadlock still possible?

No. All four are necessary; removing any single one makes a deadlock impossible, which is exactly the basis for prevention strategies.

How is a deadlock different from starvation?

A deadlock is a permanent standstill with no possible resolution without intervention; starvation is a process being repeatedly denied a resource but still theoretically able to eventually get it.

How would you detect a deadlock has occurred?

By building a resource allocation graph or wait-for graph from current process/resource states and checking for a cycle.