What is Deadlock in OS: Handling, Prevention, Avoidance

What is Deadlock in OS

A deadlock is a situation in which two or more processes are unable to continue executing because each is waiting for one or more of the others to do something. Deadlocks can occur in operating systems when multiple processes compete for the same system resources, such as memory, CPU time, or input/output devices, and become deadlocked when each process is holding resources that are needed by the other processes.

There are four necessary conditions for a deadlock to occur in an operating system:

1. Mutual exclusion: At least one resource must be held in a non-shareable mode. This means that only one process at a time can use the resource.
2. Hold and wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No preemption: Resources cannot be forcibly taken away from a process that is holding them. Only the process holding the resources can release them voluntarily.
4. Circular wait: A circular chain of two or more processes each holding a resource that is requested by the next process in the chain.

Once these conditions are met, a deadlock can occur. Deadlocks can be difficult to detect, and resolve and can cause significant problems for operating systems and the applications running on them.

To prevent deadlocks, operating systems typically use a variety of techniques, including resource allocation graphs, deadlock detection algorithms, and resource scheduling algorithms. These techniques can help prevent deadlocks by identifying potential deadlocks and taking action to avoid them, or by resolving deadlocks that have already occurred

Resource Allocation Graph (RAG)

A Resource Allocation Graph (RAG) is a graphical representation of a system’s resource allocation state. It is used in computer science and engineering to depict how resources are allocated among processes or tasks in a system.

In a RAG, processes are represented by circles, and resources are represented by rectangles. A directed edge is drawn from a resource to a process if the process is currently holding the resource. A directed edge is drawn from a process to a resource if the process is currently waiting for the resource.

Also Check: Problems in Handling Multiple Processes in OS

The following conventions are used in the RAG:

• A process can request a resource by attempting to acquire it. If the resource is available, the process acquires it, and a directed edge is drawn from the resource to the process.
• If a process is holding a resource, it can release it by completing its work and releasing resources. In this case, the directed edge from the resource to the process is removed.
• If a process is waiting for a resource, it can only proceed once it acquires the resource. In this case, a directed edge is drawn from the process to the resource.
• If a resource is available, a process can acquire it. In this case, a directed edge is drawn from the resource to the process.

The RAG is a useful tool for identifying deadlocks and resource contention issues in a system. A deadlock occurs when two or more processes are waiting for resources that are currently held by other processes, forming a cycle in the RAG. A resource contention issue occurs when multiple processes are competing for the same resource, which can lead to performance issues and inefficiencies. By analyzing the RAG, it is possible to identify these issues and take corrective measures.

Methods for Handling Deadlocks

Deadlocks occur when two or more processes are unable to proceed because each is waiting for the other to complete some action. This can cause a system to become unresponsive and may require intervention to resolve.

Common methods for handling deadlocks

Here are some common methods for handling deadlocks:

Prevention:

The best way to handle deadlocks is to prevent them from occurring in the first place. This can be achieved by using one or more of the following techniques:

• Resource allocation: Ensure that resources are allocated in a way that prevents deadlock from occurring, such as using a banker’s algorithm to determine safe resource allocation.
• Resource ordering: Require processes to request resources in a specific order to prevent deadlock.
• Timeout: Set a timeout period for processes, after which they will release their resources if they are unable to complete their tasks.

Avoidance:

Deadlock avoidance involves dynamically checking the state of the system and predicting whether a particular allocation of resources could lead to deadlock. If a potential deadlock is detected, the system will avoid the allocation that would lead to it.

• Banker’s algorithm: This algorithm is used to avoid deadlock by determining if a system is in a safe state or not. It considers the available resources, the maximum demand of each process, and the resources currently allocated to each process.
• Detection and Recovery: If deadlocks cannot be prevented or avoided, then detection and recovery is the next best option.

Resource allocation graph:

This is a visual representation of the resource allocation and request for each process. If the graph contains a cycle, then a deadlock has occurred.

• Kill a process: If a deadlock is detected, one of the processes involved in the deadlock can be terminated, freeing up its resources and allowing the other processes to proceed.
• Rollback: If a deadlock is detected, the system can roll back the progress made by the processes involved in the deadlock to a previous checkpoint, freeing up resources and allowing the processes to restart.
• Resource preemption: If a deadlock is detected, the system can preempt resources from one or more processes to allow the others to proceed. The preempted process can then restart once the necessary resources become available again.

Each of these methods has its advantages and disadvantages, and the best approach will depend on the specific system and its requirements

Deadlock Prevention

Deadlock prevention is a technique used to avoid the occurrence of deadlocks in a computer system. Deadlock is a situation where two or more processes are unable to proceed because each is waiting for the other to release a resource. Deadlocks can occur in multi-process systems where processes share resources such as CPU, memory, and I/O devices.

Techniques to prevent deadlocks:

1. Mutual exclusion: Processes should be prevented from entering into a critical section simultaneously. Only one process should be allowed to access a resource at any given time.
2. Hold and Wait: Processes should not hold a resource while waiting for another resource. If a process requires multiple resources, it should request all of them at once, instead of acquiring them one by one.
3. No preemption: Resources should not be preempted from a process. A process should release all its resources before it can be preempted.
4. Circular wait: A circular wait should not exist in the system. A process should not wait for a resource that is being held by another process that is waiting for a resource that the first process holds.

By applying these techniques, deadlocks can be prevented in a computer system. However, these techniques may lead to reduced system performance or resource utilization. Therefore, a trade-off must be made between deadlock prevention and system performance.

Deadlock Avoidance

Deadlock avoidance is a strategy for preventing deadlocks from occurring in a computer system. Unlike deadlock detection and recovery, which identify and resolve deadlocks after they have occurred, deadlock avoidance aims to prevent deadlocks from happening in the first place.

One approach to deadlock avoidance is to use resource allocation algorithms that ensure that resources are allocated in a way that prevents deadlock. One such algorithm is the banker’s algorithm, which is used to ensure that a system’s resources are allocated in a way that avoids deadlock. The banker’s algorithm is based on the idea of resource allocation graphs, which are used to represent the allocation of resources to processes.

In the banker’s algorithm, each process is required to declare the maximum amount of each resource it may need. The system then determines if the allocation of resources to the processes can lead to a deadlock. If a deadlock is possible, the system will not grant the resources, thus avoiding the deadlock. Otherwise, the system will grant the resources, and the process can continue.

Another approach to deadlock avoidance is to use synchronization mechanisms such as semaphores and monitors. These mechanisms can be used to ensure that processes do not enter a deadlock state by preventing them from accessing resources that are currently being used by other processes. For example, semaphores can be used to control access to shared resources such as files or network connections.

Overall, deadlock avoidance is an important technique for ensuring the reliable operation of computer systems, especially those that rely heavily on concurrent processing and resource sharing. By preventing deadlocks from occurring, these systems can operate more efficiently and with less risk of failure

So, in this article, we learned about Deadlocks and the necessary conditions for Deadlocks. Also, we learned Deadlock Handling Methods.