نظم تشغيل 2- المحاضرة الرابعة

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 may provide: • An algorithm that examines the state of the system to determine whether a deadlock has occurred • An algorithm to recover from the deadlock.
? we note that a detection-and-recovery scheme requires overhead that includes not only the run-time costs of maintaining the necessary information and executing the detection algorithm but also the potential losses inherent in recovering from a deadlock.
1 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.
? More precisely, 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 allocatio
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 may provide: • An algorithm that examines the state of the system to determine whether a deadlock has occurred • An algorithm to recover from the deadlock.
? we note that a detection-and-recovery scheme requires overhead that includes not only the run-time costs of maintaining the necessary information and executing the detection algorithm but also the potential losses inherent in recovering from a deadlock.
1 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.
? More precisely, 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 allocatio