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.
|
