SS & OS Module 4 PART 5.pdf

System Software and Operating System Module 4 (Part 5) Deadlock Detection and Recovery Deadlock Detection If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm then a deadlock situation may occur. In this environment, the system mu...

System Software and Operating System Module 4 (Part 5) Deadlock Detection and Recovery Deadlock Detection If a system does not employ either a deadlock-prevention or a deadlock avoidance algorithm then a deadlock situation may occur. In this environment, the system must provide: An algorithm that examines the state of the system to determine whether a deadlock has occurred An algorithm to recover from the deadlock Single Instance of Each Resource Type If all resources have only a single instance, then we can define a deadlock detection algorithm that uses a variant of the resource-allocation graph, called a wait for graph. We obtain this graph from the resource- allocation graph by removing the resource nodes and collapsing the appropriate edges. An edge from Pi to Pj in a wait-for graph implies that process Pi is waiting for process Pj to release a resource that Pi needs. An edge Pi -> Pj exists in a wait-for graph if and only if the corresponding resource allocation graph contains two edges Pi -> Rq and Rq -> Pj for some resource Rq. A deadlock exists in the system if and only if the wait-for graph contains a cycle. To detect deadlocks, the system needs to maintain the wait-for graph and periodically invoke an algorithm that searches for a cycle in the graph. Several Instances of a Resource Type The algorithm employs several time-varying data structures that are similar to those used in the banker's algorithm. Available. A vector of length m indicates the number of available resources of each type. Allocation. An n x m matrix defines the number of resources of each type currently allocated to each process. Request. An n x m matrix indicates the current request of each process. If Request[i][j] equals k, then process Pi is requesting k more instances of resource type Rj. The algorithm is 1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available. For I = 0, 1..., n-1, if Allocationi != 0, then Finish[i] = false; otherwise, Finish[i] = true. 2. Find an index i such that both a. Finish[i] = false b. Requesti