Deadlock Detection

Overview
• Allow system to enter a deadlock state
• Detection algorithm: examine the system state to determine whether a deadlock has occurred
• Recovery scheme: recover from the deadlock

Single Instance of Each Resource Type
• Maintain wait-for graph
– Nodes are processes.
– This graph is obtained from the resource-allocation graph by removing the nodes of type resource and collapsing the appropriate edges
– Pi  Pj if Pi is waiting for Pj.
• Periodically invoke an algorithm that searches for a cycle in the graph.
• An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.

Resource-Allocation Graph And Wait-for Graph


Several Instances of a Resource Type
• 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] = k, then process Pi is requesting k more instances of resource type Rj

Combined Approach to Deadlock Handling
• Combine the three basic approaches
– Prevention
– Avoidance
– Detection
• Allowing the use of the optimal approach for each of resources in the system
• Partition resources into hierarchically ordered classes.
• Use most appropriate technique for handling deadlocks within each class
• Group resources into a number of different resource classes
• Use the linear ordering strategy defined previously for the prevention of circular wait to prevent deadlocks between resource classes
• Within a resource class, use the algorithm that is most appropriate for that class
• Swappable space
Hold-and-Wait prevention strategy + avoidance
• Process resources: Assignable devices such as tape drives, files…
Avoidance + Resource ordering
• Main memory: assignable in pages or segments
Preemption
• Internal resources: PCB, I/O channels…
Resource ordering