Deadlock in Operating System
Subject: Computer Science Fundamentals · Language: Operating System · Level: intermediate · 9 min read
Understand deadlock with resources, four necessary conditions, resource allocation graph, prevention, avoidance, detection, recovery, and starvation difference.
Deadlock is a situation where two or more processes are blocked forever because each process is waiting for a resource held by another process. In this condition, none of the processes can continue execution, and the system cannot make progress for those processes. For beginners, deadlock can be understood with a simple example. Suppose person A has a pen and needs a notebook. Person B has the notebook and needs the pen. Both are waiting for each other, and neither gives up their resource. This waiting cycle is similar to deadlock in an operating system.
Deadlock is important because operating systems manage many shared resources such as printers, files, memory, devices, locks, and database connections. If resources are not allocated carefully, processes may get stuck permanently.
Resource and Process
A resource is anything a process needs to complete its work. Examples include CPU time, memory, files, printers, scanners, locks, semaphores, and input-output devices. Some resources can be shared by many processes at the same time, while some resources cannot. For example, a read-only file may be shared safely by many processes. But a printer usually prints one job at a time, so it behaves like a non-shareable resource. A process may request a resource, use it, and release it after work is complete. Deadlock happens when processes hold some resources and wait for other resources in a way that creates a cycle.
Simple Deadlock Example
Suppose process P1 holds resource R1 and requests resource R2. At the same time, process P2 holds resource R2 and requests resource R1. P1 cannot continue without R2, and P2 cannot continue without R1. Now P1 waits for P2, and P2 waits for P1. Since neither process releases its current resource, both remain blocked. This is deadlock. This example is small, but real systems can have many processes and many resources. Detecting and handling deadlock becomes more complex when the system is large.
Necessary Conditions for Deadlock
Deadlock can occur only when four necessary conditions hold at the same time. These conditions are mutual exclusion, hold and wait, no preemption, and circular wait. If any one of these conditions is prevented, deadlock cannot occur.
Mutual Exclusion
Mutual exclusion means at least one resource must be non-shareable. Only one process can use that resource at a time. If another process wants it, that process must wait. For example, a printer is usually a mutually exclusive resource. If one process is printing a document, another process cannot print at the exact same time on the same printer. Mutual exclusion is often necessary because some resources cannot be safely shared. Therefore, it is not always possible to remove this condition completely.
Hold and Wait
Hold and wait means a process is holding at least one resource while waiting for another resource. This condition is dangerous because a process does not release what it already has while waiting for something else. For example, P1 may hold a file lock and wait for a printer. P2 may hold the printer and wait for the file lock. Since both are holding one resource and waiting for another, deadlock may happen.
No Preemption
No preemption means a resource cannot be forcibly taken away from a process. The process must release the resource voluntarily after completing its work. For some resources, preemption may be possible. For example, CPU can be taken away from a process during scheduling. But for other resources, such as a printer or file write operation, forcibly taking the resource may cause problems. No preemption contributes to deadlock because a waiting process cannot simply take the needed resource from another process.
Circular Wait
Circular wait means there is a cycle of processes where each process waits for a resource held by the next process in the cycle. For example, P1 waits for a resource held by P2, P2 waits for a resource held by P3, and P3 waits for a resource held by P1. This forms a circular chain of waiting. Circular wait is the condition that makes the waiting permanent. If there is no cycle, processes may eventually continue when resources are released.
Resource Allocation Graph
A resource allocation graph is a diagram used to understand deadlock. It contains process nodes and resource nodes. An arrow from a process to a resource means the process is requesting that resource. An arrow from a resource to a process means the resource is allocated to that process.
If the graph has a cycle, deadlock may exist. If each resource has only one instance, a cycle means deadlock definitely exists. If resources have multiple instances, a cycle may indicate possible deadlock but does not always guarantee it. Resource allocation graphs are useful for visualizing which process holds which resource and which process is waiting.
Deadlock Prevention
Deadlock prevention means designing the system so that at least one necessary condition for deadlock never holds. If one of the four conditions is broken, deadlock cannot occur. Preventing mutual exclusion is difficult because some resources are naturally non-shareable. Preventing hold and wait can be done by requiring a process to request all resources at once, but this may waste resources.
Preventing no preemption means allowing resources to be taken away from processes when needed. This works for some resources but not all. Preventing circular wait can be done by assigning an order to resources and requiring processes to request resources in that order. Deadlock prevention is safe, but it can reduce system efficiency because it may be too strict.
Deadlock Avoidance
Deadlock avoidance means the OS checks resource allocation before granting a request. It grants the request only if the system remains in a safe state. A safe state means there is at least one order in which all processes can finish without deadlock. An unsafe state does not always mean deadlock has happened, but it means deadlock may happen later.
Banker's Algorithm is a famous deadlock avoidance algorithm. It checks available resources, maximum needs, allocated resources, and remaining needs before granting requests. Deadlock avoidance needs advance information about maximum resource needs. This may not always be practical in real systems.
Deadlock Detection
Deadlock detection allows deadlock to occur and then checks whether it has happened. The OS may periodically examine process and resource information to find cycles or blocked process groups. Detection is useful in systems where preventing or avoiding deadlock is too costly. Instead of being strict all the time, the OS detects deadlock when it occurs. The challenge is deciding how often detection should run. Running it too frequently wastes CPU time. Running it too rarely may allow deadlocked processes to remain stuck for too long.
Deadlock Recovery
After detecting deadlock, the OS must recover from it. Recovery can be done by terminating processes or preempting resources. One method is to terminate all deadlocked processes. This is simple but may lose a lot of work. Another method is to terminate one process at a time until the deadlock is removed.
Resource preemption means taking a resource from one process and giving it to another. This must be done carefully because it may leave the victim process in an inconsistent state. When choosing a process to terminate or preempt, the OS may consider priority, work completed, resources held, and how much work will be lost.
Starvation vs Deadlock
Deadlock and starvation are related but different. In deadlock, processes are stuck because they are waiting for each other in a cycle. In starvation, a process waits for a long time because other processes keep getting resources first. A starving process is not necessarily part of a waiting cycle. It may simply be ignored repeatedly by the scheduling or resource allocation policy. Aging can help reduce starvation by gradually increasing the priority of waiting processes. Deadlock needs different handling such as prevention, avoidance, detection, or recovery.
Real-Life Examples of Deadlock
A traffic deadlock can happen when cars enter an intersection from all sides and each car blocks another car. No one can move because everyone is waiting for someone else to move first. In computers, deadlock can happen with file locks, database locks, printer access, memory allocation, or thread locks. For example, two threads may acquire locks in opposite order and wait forever.
Summary
Deadlock is a permanent waiting situation where processes are blocked because each process waits for a resource held by another. The four necessary conditions are mutual exclusion, hold and wait, no preemption, and circular wait. The main ways to handle deadlock are prevention, avoidance, detection, and recovery. A beginner should clearly understand the four conditions, resource allocation graph, safe and unsafe state, Banker's Algorithm idea, and the difference between deadlock and starvation.
More Operating System Lessons
- Introduction to Operating System
- Types of Operating System
- Operating System Functions and Services
- System Calls in Operating System
- Process Management in Operating System
- Process Scheduling in Operating System
- CPU Scheduling Algorithms
- Threads and Multithreading in Operating System
- Process Synchronization in Operating System
- Memory Management in Operating System
- Virtual Memory in Operating System
- File System in Operating System