Can a deadlock be resolved completely?
First of all, let me illustrate, ‘What is actually a deadlock and how it happens?’. I am taking a simple example. Suppose, there is a bridge or a passage through which only one person can pass at a single time. If two persons, A and B, both busy, try to cross the bridge at the same time from both the ends, what will happen? Both of them will be struck at the middle of the bridge, waiting for the other person to get out of the bridge so that he can cross it. As long as both the persons remain thinking in the same way, neither A nor B will be able to cross the bridge or the resource – bridge will be utilized. This situation in simple terms can be said to be a deadlock.
Now, let us come to our computer terms and processes. Suppose two processes P1 and P2, each need to use CD-ROM drive and DAT drive. Suppose things happen in this order:
Process P1 requests the DAT drive from the resource manager.
Process P1 is granted exclusive use of the DAT drive.
Process P2 requests the CD-ROM drive from the resource manager.
Process P2 is granted exclusive use of the CD-ROM drive.
Process P1 requests the CD-ROM drive from the resource manager.
Process P2 requests the DAT drive from the resource manager.
The process is shown in the diagram.
Then what will happen? A deadlock occurs, since they are each waiting for a message from the other one.
Definition of Deadlock
Deadlock is a situation where two or more processes remain waiting for a resource that another process in the group holds. These processes will wait forever, since none of them can make any further advance and release its resources unless it obtain certain resources to complete its task, and those resources are held by other processes that cannot make any progress since they are waiting for some resources held by some process in the group.
Sometimes even 3 or more processes can be locked into a deadlock. Here a process is waiting for another process, which is waiting for another one, etc, until finally a process in the chain may be waiting for the original process. Hence none of them will proceed.
Necessary conditions for a deadlock to occur
The four most important conditions of deadlock are
A. If resources are not shared
B. If resources are not pre-emptable
C. Circular wait is also possible
D. A process has the permission to hold one resource and request for another
Strategies to deal with deadlock
Mainly, there are three strategies for dealing with a deadlock.
Prevention – Restrictions can be placed on resource requests so that deadlock can never occur.
Avoidance – Plan ahead so that you never get into a circumstance where deadlock cannot be avoided.
Recovery – Once a deadlock is detected, recover from it.
Let us examine above three strategies and find out what each one suggests.
Deadlock Prevention:
As noted, there are four conditions in which deadlock can occur. If we are able to prevent any one of these conditions from occurring, we can prevent deadlock.
Allowing preemption: Preemption is the act that can be done to interrupt a particular process, thus helps in freeing system resources. If we can preempt resources, then deadlock is not at all possible. It can be done, but expensive if made practical.
Avoiding hold and wait: If a process is given all of the resources it needs at one time, then a situation will never arise where it is holding one or two resources and waiting for another. This will prevent deadlock effectively. But the problem is that it can lead to inefficient use of resources. i.e. A process will hold a particular resource in advance before the actual time it needs that one. Also, another process may be waiting for that particular resource while this one is actually holding it for future purpose without any use in present time. Another problem is, this solution assumes that the process know all the resources you will need before you start, which is not always true. Some resources may be needed later, once the process is started. It again can lead to another deadlock.
Avoiding mutual exclusion: In the case of sharing a hardware device, virtualization can be used. Best example is printer spooling where, an unlimited number of virtual printers are created and data is print into a disk file and send a message to the print spooler process to print it when its turn comes up. But the drawback of this method is that it can be made useful only to share hardware devices.
Avoiding circular wait: Give each resource a unique, positive integer. Also, resources must be acquired in ascending, numerical order. It can prevent circular wait and this method is often used. But it will also lead to inefficient use of resources.
Deadlock Avoidance:
Often algorithms are used to avoid deadlock. Whenever you are going to make an allocation, run the algorithm and see if making that allocation would lead to a deadlock. But like several ideas, it also has certain drawbacks. Algorithms are slow and there is a lot of overhead in running them before every resource allocation. Also, it assumes that processes have a clear idea of all its needed resources and that all its resources are available. Both may not be true in all cases.
Deadlock Recovery:
It involves two steps – Detection and recovery. Once a deadlock is detected, a resource may be preempted. i.e. a process is cancelled and restarted again. Sometimes, a process may be killed for the benefit of others. Some approaches like hierarchical processing, serialization, advance claim and one-shot allocation are also used to deal with a deadlock problem according to the situation.
But each and every approach has some benefits and drawbacks. i.e. There is no ideal solution for a deadlock problem. In complicated systems, deadlock can occur easily and may be even difficult to detect. Only thing we can do is to use a particular method that suits that particular situation to the most.
Like it on Facebook, Tweet it or share this article on other bookmarking websites.