Deadlock in Operating Systems: Causes, Conditions, and Prevention Techniques

In any system, physical or digital, every process/task needs resources for its implementation and completion. Once the process completes, the resources used are released. This is a normal process. However, sometimes, when there are multiple processes involved, they compete for resources. As you know, resources are limited. Hence, when processes compete for resources, there arises a situation where two processes competing for the resource cannot complete because each process is waiting for the other to release the resource. This situation is called a Deadlock.

This article explores the concept of deadlock in operating systems, the necessary conditions that lead to deadlocks, the common causes, and the various prevention techniques used to avoid them.

What is a Deadlock?

A deadlock in an operating system is a state in which a set of processes is stuck because each holds a resource that another process wants.

In simple words, processes in deadlock are trapped in a circular chain of dependencies. In a deadlocked state, one process is holding a resource that is required by another process to complete its execution. At the same time, the first process is also waiting for a resource to complete its execution, and that resource is held by the second process. In this way, none of the processes can proceed towards completion.

Deadlock usually occurs in systems where multiple processes compete for limited resources such as CPU time, memory, or input or output devices.

Example of Deadlock

To demonstrate deadlock, consider a system with two processes, Process P1 and Process P2. There are also two resources, Resource R1 and Resource R2.

The situation here is depicted in the following diagram:

As seen in the above diagram, process P1 has resource R1, and resource R2 is held by process P2. Now, P1 is waiting to acquire R2, and P2 is waiting for R1. Thus, both processes are waiting for resources held by the other. Since neither process can complete, the system is in a deadlock state.

This circular waiting creates a permanent block unless the operating system intervenes.

Necessary Conditions for Deadlock

There are four necessary conditions for a deadlock to occur. These are often called Deadlock Conditions or Coffman Conditions (named after computer scientist Edward G. Coffman).

Here are the necessary conditions for deadlock:

1. Mutual Exclusion

In this condition, at least one resource is non-shareable, meaning only one process can use it at a time and cannot be accessed or modified by multiple processes.

• A printer cannot print two documents simultaneously.
• A file lock prevents multiple processes from writing to the same file.

In this situation, a deadlock will occur when more than one process tries to access this non-shareable resource.

2. Hold and Wait

Under this condition, a process is holding at least one resource and is waiting to acquire additional resources currently held by other processes.

An example of this condition is shown in the previous section, where Process P1 holds Resource R1. P1 requests Resource R2 but must wait because it is held by P2.

During this waiting period, P1 continues holding R1, preventing others from using it.

The Hold and Wait condition can lead to a situation in which processes hold resources and wait indefinitely for others.

3. No Preemption

In the OS, resources can only be released voluntarily by the process holding them.

They cannot be preempted or relinquished forcibly.

• If a process is printing, the OS cannot interrupt and remove the printer resource until the process finishes.

Since resources cannot be preempted, processes must wait until resources are released naturally.

Hence, if a process is holding a resource and cannot complete its task because it is waiting for another resource, it will not release its current resource, potentially contributing to a deadlock.

4. Circular Wait

A circular wait condition exists in which each process waits for a resource held by the next process in the chain.

Consider the situation shown in the diagram below:

Here, P1 is waiting for the resource held by P2, P2 is waiting for the resource held by P3, P3 is waiting for the resource held by P4, and P4, in turn, is waiting for the resource held by P1.

This has created a circular dependency, leading to a loop in which no process can move forward.

The circular wait pattern means that no process in the cycle can make progress because another process blocks it.

What are the Causes of Deadlock?

We have already discussed the four necessary conditions that can result in a deadlock. Apart from those conditions, there are several other causes of deadlock that center around resources and their allocation.

• Resource Contention: When multiple processes compete for a finite number of resources, the possibility of deadlock increases. For example, processes may wait endlessly for resources like printers, disk drives, or memory segments, which are usually limited.
• Improper Resource Allocation: When resources are allocated inconsistently, deadlocks can occur. For example, the condition of circular wait happens because the resources are requested in a different sequence.
• Lack of Resource Scheduling: Multiple processes may request and hold resources indefinitely that may lead to a deadlock situation. The OS should implement proper scheduling techniques to allocate resources.
• Programming Errors: Poor programming practices such as failing to release locks, incorrect synchronization mechanisms, or improper thread management, especially in concurrent programming, result in deadlocks.
• Nested Locks: A process acquiring multiple resources or locks in sequence increases the complexity of resource management. Deadlocks may occur if multiple processes acquire nested locks (lock inside a lock) in different orders.

If the operating system does not manage resource allocation efficiently, multiple processes may request and hold resources in ways that lead to deadlock.

Deadlocks in a system usually lead to performance degradation, starvation, and the inability of processes to complete.

Deadlock Prevention Techniques

Deadlock prevention techniques in operating systems ensure that at least one of the four necessary Coffman conditions (Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait) never occurs. By eliminating one or more of these conditions, the system prevents deadlocks from forming. Here are the deadlock prevention techniques:

1. Eliminate Mutual Exclusion

One technique to prevent deadlocks from mutual exclusion is to make resources sharable whenever possible.

For example, instead of allowing only one process to read a file, multiple processes can read it simultaneously. Multiple processes reading a file do not lead to deadlocks.

However, this approach is not always practical because many resources, like printers and memory segments, must remain exclusive.

2. Eliminate Hold and Wait

To prevent the hold-and-wait condition, processes must be prevented from holding one or more resources for an extended period of time or when they are simultaneously waiting for other resources.

• Processes must request all required resources at once before execution begins. This might be wasteful if a process requires only one resource at the beginning and all other resources towards the end.
• Processes holding resources must relinquish them before requesting new resources. They can then acquire released resources along with the new ones in a single request. However, if a process has been completed partially using a resource and then fails to get it reallocated after releasing it, an unexpected situation may arise.

This technique prevents processes from holding resources while waiting for other resources. However, there is a low resource utilization in this case. Process may hold resources unnecessarily for long periods of time.

3. Allow Resource Preemption

• If a process is forced to wait when requesting a new resource, then all other resources held by this process are released or preempted.
  For example, if Process P1 holds Resource R1 but requests R2, and R2 is unavailable, the system may release R1 and return it to the pool. The process must restart later when all required resources become available.
• When a resource is requested and not available, then the system looks to see what other processes currently have those resources, and these processes are themselves blocked waiting for some other resource. If such a process is found, then some of their resources are preempted and added to the list of resources for which the process is waiting.

These approaches may be applicable for resources that use registers and memory, as their states are easily saved and restored. However, they are generally not applicable to other devices such as tape drives and printers.

4. Eliminate Circular Wait

Deadlocks can also be prevented by eliminating circular wait. One way to do this is to number all resources and then make processes request resources only in a specific order, strictly increasing or decreasing.

Thus, in order to request resource Rj, a process first needs to release all Ris such that i>=j.

In general, a process cannot request a lower-numbered resource after holding a higher-numbered resource.

However, determining the relative ordering of the different resources is one big challenge in this scheme.

Real-World Examples of Deadlock

Deadlocks occur not only in operating systems but also in real-life scenarios.

Traffic Deadlock

A traffic intersection where cars block each other from all directions, creating chaos, is a classic example of deadlock.

Each driver waits for another to move, creating a circular wait condition. This deadlock is not lifted until someone reverses or moves out of the way.

Database Deadlock

When transactions lock resources in conflicting orders, a deadlock occurs in database systems.

• Transaction T1 locks Table A and requests Table B.
• Transaction T2 locks Table B and requests Table A.

Both transactions are stuck waiting for each other.

Importance of Deadlock Handling

It is always crucial to maintain system reliability and efficiency for better results. One of the methods to ensure this is to handle deadlocks effectively.

• Preventing system crashes
• Improving resource utilization
• Ensuring smooth multitasking
• Maintaining system stability

Modern operating systems employ combinations of prevention, avoidance, detection, and recovery techniques to manage deadlocks effectively.

Methods of Handling Deadlock

• Deadlock Prevention: Deadlock prevention techniques focus on removing the possibility of deadlocks by making sure that one of the necessary conditions for deadlock is always avoided. This is done by managing resource distribution and enforcing protocols to prevent circular wait, hold, and wait, and no preemption.
• Deadlock Detection and Recovery: In this approach, the system regularly monitors for deadlocks. If a deadlock exists, the system can resolve it by eliminating the deadlock loop and enabling other processes to proceed.
• Deadlock Avoidance: In this method, the system makes real-time resource allocation decisions to maintain its safety. The banker’s algorithm is used in this approach, which assesses resource requests and only approves them if they do not result in possible deadlocks.
• Wound-wait Schemes: Wound-wait schemes give preference to process execution according to the length of time waiting. If a younger process is holding a resource and an older process requests it, the younger process is interrupted to allow the older one to continue.
• Limit Resource Utilization: Here, the chances of deadlock are reduced by limiting the total resources a process can ask for. With this technique, stricter restrictions are placed on resource allocation, and the likelihood of processes reaching a state where they can hinder each other is reduced.

Differences Between Deadlock and Starvation

A deadlock occurs when processes are unable to proceed toward completion because they are holding resources and waiting for more. Starvation occurs when low-priority processes wait indefinitely because higher-priority processes continuously monopolize resources. Deadlock involves a circular wait, while starvation is a scheduling issue.

Although there is often confusion between deadlocks and starvation in the OS, these two concepts are actually quite different as described above. The following table summarizes the key differences between deadlock and starvation:

Conclusion

Deadlocks are among the most challenging problems in operating systems, especially in environments where multiple processes compete for limited resources. A deadlock occurs when processes are blocked from executing while waiting for resources held by other processes. To prevent deadlocks, you need to first understand the causes and conditions of deadlock.

The four necessary conditions, mutual exclusion, hold and wait, no preemption, and circular wait, must all be present for deadlock to occur. By eliminating or controlling these conditions, operating systems can prevent deadlocks from arising.

Deadlocks can be effectively managed using various strategies, such as deadlock prevention, avoidance algorithms like the Banker’s Algorithm, and detection and recovery mechanisms. With careful system design and resource management, the occurrence can be significantly reduced, if not completely eliminated.

Additional Resources

• User Mode vs Kernel Mode: Understanding Privilege Levels in OS
• What Are System Calls? How Operating Systems Communicate with Applications
• What are the Different Types of Code Smells?
• What is Software Architecture?
• Cohesion vs Coupling

Frequently Asked Questions (FAQs)

1. What is the difference between deadlock prevention and deadlock avoidance?
   • Deadlock Prevention eliminates one of the necessary conditions for deadlock, so that deadlocks cannot occur.
   • Deadlock Avoidance dynamically checks resource allocation to ensure the system stays in a safe state, preventing potential deadlocks.
2. Can deadlocks occur in real-world systems?
   Yes. Deadlocks occur in many real-world systems, such as:
   • Database transactions waiting for locked tables
   • Multithreaded programs using locks improperly
   • Traffic intersections where vehicles block each other.
3. Why is deadlock management important in operating systems?
   Deadlock management is important because it:
   • Prevents system freezing
   • Improves resource utilization
   • Maintains system stability
   • Ensures smooth multitasking and process execution.

Shilpa Prabhudesai