OS-Deadlock Detection and Recovery

Deadlock Detection is the process of actually determining that a deadlock exists and of identifying the processes and resources involved in the deadlock


To detect deadlocks a popular notation is used in which a directed graph indicates resource allocation and requests. Squares represent processes and large circles represent classes of identical devices. Small circles drawn inside large circles indicate the number of identical devices of each class. Diagram:


One technique useful for detecting deadlocks involves graph reductions in which the processes that may complete their execution and the processes that will remain deadlocked are determined. If a process’s resource requests may be granted, then we say that a graph may be reduced by that process. The reduction of a graph by a process is shown by removing the arrows to that process from resources and by removing arrows from that process to resource. If a graph can be reduced by all its processes, then there is no deadlock. If a graph cannot be reduced by all its processes then the irreducible processes constitute the set of deadlocked processes in the graph.


Once a system has become deadlocked, the deadlock must be broken by removing one or more of the necessary conditions. Several processes will lose some or all of the work they have accomplished.

Recovery is done by forcibly removing a process from the system and reclaiming its resources. The removed process is ordinarily lost, but the remaining processes may now be able to complete. Sometimes it is necessary to remove several processes until sufficient resources have been reclaimed to allow the remaining process to finish. Processes may be removed according to some priority order.
OS-Deadlock Detection and Recovery Reviewed by 1000sourcecodes on 22:46 Rating: 5
Powered by Blogger.