System Software & Operating System Deadlock Detection PDF

Document Details

Uploaded by Deleted User

Tags

deadlock detection operating systems computer science system software

Summary

This document explains deadlock detection and recovery techniques in operating systems. It discusses algorithms for handling deadlocks, focusing on situations where resources have a single instance and multiple instances. The document is relevant to computer science undergraduate courses.

Full Transcript

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

Use Quizgecko on...
Browser
Browser