We yesterday learned about some techniques to prevent deadlocks from occuring and there are ways to avoid deadlocks too but we will discuss about them some other day but for today we will be learning about some ways on how to detect deadlocks in the first place.
Deadlock detection is the first step in avoiding deadlocks from happening. If a deadlock appears in the system it must be detected and recovered. The system must provide some ways of detecting deadlocks.
Single Instance of Each Resource Type
Suppose that each resource type has onyl one instance and there is only one printer and harddrive etc. A variant of the Resource-Allocation Graph called a wait-for graph can be used by removing the nodes of the type resource and collapsing the appropriate edges.
In this graph, processes are not waiting for the resources. They are waiting for other porcesses that are holding these resources so a cycle in this graph can tell us that there is a deadlock in the processes. But this approach requires that the cycle detection algorithm must run from time to time in order to detect deadlocks in the system. Algorithms that detect cycles are of complxity O(n^2) where n is the number of vertices in the graph.
Detection-Algorithm Usage
In order to detect deadlocks we need some detection algorithm to run after every unit time has passed. This time unit is dependent on out assumption of how often deadlocks appear and how much processes they effect in the systems.
If deadlocks appear often we may run it often. We can also run the detection algorithm on every resource request but since we know that deadlocks are rare it may not be a very efficient use of resources amd it will effect resources.
We can run these algorithms from time to time at random or after some hour or minutes to detect deadlocks.
zainsci