Thursday, August 20, 2009
at
4:07 AM
|
- Allow system to enter deadlock state
- Detection algorithm
- Recovery scheme
Single Instance of Each Resource Type
• Maintain wait-for graph
-Nodes are processes.
– Pi → Pj if Pi is waiting for Pj.
• Periodically invoke an algorithm that searches for acycle in thegraph.
• An algorithm to detect a cycle in a graph requires an order of n2operations, where n is the number of vertices in the graph.
Detection Algorithm
1. Let Work and Finish be vectors of length m and n, respectiveInitialize:
(a) Work :- Available
(b) For i = 1,2, …, n, if Allocationi ≠ 0, thenFinish[i] := false;otherwise, Finish[i] := true.
2. Find an index i such that both:
(a) Finish[i] = false
(b) Requesti ≤ WorkIf no such i exists, go to step 4.
3.Work := Work + Allocation
Finish[i] := true
go to step 2.
4. If Finish[i] = false, for some i, 1 ≤ i ≤ n, then the system is indeadlock state. Moreover, if Finish[i] = false, then Pi isdeadlocked.
Algorithm requires an order of m x n2 operations to detect whetherthe system is in deadlocked state.
Posted by
Roger
Labels:
os 8
0 comments:
Post a Comment