What is Deadlock?

Blog / What is Deadlock?
So what actually is deadlock?
TL;DR Summary
  • Deadlock is a situation in an operating system where two or more processes are unable to proceed because each is waiting for one of the others to release a resource.
  • 4 Conditions Required for Deadlock to Occur:
    • Mutual Exclusion
    • Hold and Wait
    • No Preemption
    • Circular Wait

Don't let one question ruin your next technical interview...

Concurrency•20

Operating Systems•58

Deadlock is a situation in an operating system where two or more processes are unable to proceed because each is waiting for one of the others to release a resource (memory, files, printers etc.).
Deadlock visual representation
Process 1 is waiting for resource 1, held by Process 2, while Process 2 is waiting for resource 2, held by Process 1, causing a deadlock.A deadlock occurs only if these four conditions are met simultaneously:
  • Mutual exclusion: Only one process can use a resource at any one time.
  • Hold and wait: A process is holding at least one resource and is waiting to acquire more resources that are currently being held by other processes.
  • No Preemption: A resource cannot be forcibly taken from a process.
  • Four Circular: wait which means there is a set (circle) of processes each waiting for a resource that the next process in the circle holds.
Deadlock Prevention Prevention focus on structurally eliminating the possibility of deadlock by negating at least one of the four necessary conditions (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait).Example: Lock ordering (Breaking circular wait)
  • What It Is: This involves imposing a total ordering of all resource types and requiring that each process requests resources in an increasing order of enumeration.
  • How It's Done: For example, if there are resources labeled R1, R2, R3, ... Rn, then a process must request these resources in order (R1 before R2, R2 before R3, and so on). This ordering prevents circular waits.
  • Real-World Use: This is widely used in databases and file systems. Developers often implement this by ensuring that locks are always acquired in a predefined global order.
Deadlock Avoidance Avoidance dynamically examines the state of resource allocation and ensures that the system can always reach a state where all processes can complete their tasks. Example: Bankers algorithm
  • What It Is: This is a strategy used to avoid deadlock by simulating resource allocation for all possible sequences and determining if a safe sequence exists.
  • How It's Done: Before granting a resource, the system checks if doing so will leave the system in a safe state, where all processes can still complete with the resources available.
  • Real-World Use: The Banker’s Algorithm is more theoretical because its overhead can be high in systems with many processes and resources. It's not commonly used in most operating systems due to its complexity but might be seen in systems with highly critical and predictable processes.
In reality, while theoretical models of deadlock prevention and avoidance are well-defined, the actual implementation tends to prefer practicality and efficiency. Techniques like lock ordering, monitoring, and judicious use of timeouts form the backbone of handling deadlocks in most real-world applications.