Deadlock Detection/Algorithm/Example in Operating System:
If the system does not use any of the preventive or avoidance methods, there is a possibility of deadlock occurrence. If a deadlock occurs in the system, it must be detected and recovered. The system needs to provide some methods of deadlock detection and recovery. These methods are overhead for the system.
1 Single Instance of Each Resource Type:
If each resource type has only one instance (There is only 1 printer, 1 hard drive, 1 tape drive, etc.), we can use a variant of the resource-allocation graph called a wait-for graph. It is done by removing the nodes of type resource and collapsing the appropriate edges.
In this graph, processes are not waiting for resources. They are waiting for other processes that hold these resources. A cycle in the graph indicates the occurrence of a deadlock in the system.
This approach requires that a cycle detection algorithm runs from time to time to detect deadlock. Algorithms that detect cycles are O(N2). N is the number of vertices in the graph.
2. Detection-Algorithm Usage:
Detection algorithms need to be executed to detect a deadlock. The frequency and time when we run such algorithm is dependent on how often we assume deadlocks occur and how. many processes they may effect.
If deadlocks may happen often, we run the detection often. If it affects many processes, we may decide to run it often so that less processes are affected by the deadlock.
We could run the algorithm on every resource request. The deadlocks are rare so it is not very efficient use of resources. We could run the algorithm from time to time like every hour or at random times during the system execution lifetime.
