Deadlock Detection Algorithm

Deadlock Detection Algorithm

• 2.
  Introduction What are Deadlocks? ‘ Any blocked process which cannot be resolved unless there is some outside intervention’. In operating system deadlocks can be visualized where processes have some resources held by them and are waiting for some resources to fulfill their completion which are instead being held by some other blocked process. A very simple real-world example is of the two cars halted on both sides of a bridge which has only width for one car to pass. As both cars are holding each end of the bridge so neither can pass unless and until one car backs up and clears the road so that the other car pass and vice versa.
• 3.
  Deadlock Classification Mutual Exclusion: If one process is holding a resource required by other processes that resource must wait until it is released by the process. Hold and Wait : Processes are allowed to hold one or more resources and waiting for additional resources held by other processes. No Pre-Emption : Resources are released voluntarily, neither another process nor the OS can force a process to release a resource. Circular Wait : There may exist a set of waiting processes such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2,… Pn- 1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.
• 4.
  Resource Allocation Graph Wecan model deadlock conditions using a directed graph called a Resource Allocation Graph (RAG). Lets understand some basics: Two Kinds of Nodes : Boxes : Represent Resources Circles : Represent Processes Two Kinds of (Directed) Edges: Request Edge : from thread to resource, indicates that the thread has requested the resource and is waiting to acquire it. Assignment Edge : from resource instance to thread, indicates the thread is holding the resource instance. When a request is made, a request edge is added On fulfillment the request edge is transformed into and assignment edge. When a resource is released by a process, the assignment edge is deleted.
• 5.
  RAG with SingleResource Instance R1 R2 R1 R2 P1 P2 P3 R3 R4 P1 P2 P3 R3 R4 A closed cycle in RAG with single resource instance is mandatory for deadlock.
• 6.
  RAG with MultipleResource Instances R1 R2 R1 R2 P1 P2 P3 R3 R4 P1 P2 P3 R3 R4 A Knot is mandatory for a deadlock. (Knot is created when strongly connected subgraphs with no outgoing edges are formed).
• 7.
  Prevention and Avoidance Preventionby eliminating one of the four conditions Acquire all resources before proceeding (No wait while Hold) Allow Preemption (Eliminate 3d Condition) Prioritize Processes and Assign Resources in order of Priorities (No Circular Wait) Avoidance can be done by allowing resource requests only if they don’t lead to deadlock condition. In other words, Safe state : An order to entertain resource requests so that all processes can be completed. Drawbacks: Resource requirements for all processes must be known in advance. Resource request set is known and fixed, Complex Analysis for every request.
• 8.
  Deadlock Detection Detection : Issues Maintenanceof WFG (Wait for Graphs) Search of WFG for deadlocks Requirements Progress No undetected deadlocks Safety No false(phantom) deadlocks Resolution Roll Back one or more processes to break dependencies in WFG to resolve the situation.
• 9.
  Single Instance forEach Resource Type Maintain wait-for Graph Nodes are processes Pi-> Pj if Pi is waiting for Pj Periodically invoke an algorithm that searches for a cycle in the graph. If there is a cycle then there is or will be a deadlock. An algorithm to detect a cycle in graph requires an order of n2 Operations, where n is the number of vertices in the graph.
• 10.
  RAG& WFG R1 R4 P1P2 P3 P5 R3 P4 R5 R2 P1 P2 P3 P5 P4 Corresponding Wait for Graph Resource Allocation Graph
• 11.
  Several Instances ofa 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[ij]=k, then process Pi is requesting k more instances of resource type Rj.
• 12.
  Detection Algorithm 1. LetWork and Finish be vectors of length m and n, respectively Initialize : (a) Work=Available (b) For i=1,2,…,n 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≤ Work 3. Work = Work +Allocationi Finish[i]=true go to step 2. 4. If Finish[i]==false, for some i, 1 ≤i ≤n, then the system is in the deadlock state. Moreover, if Finish[i]==false, then Piis deadlocked. Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked state.
• 13.
  Example of DetectionAlgorithm Five processes Po through P4; three resource types A(7 instances), B(2 instances), and C(6 instances). Snapshot at time T0: Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Sequence <P0,P1,P2,P3,P4>will result in Finish[i]=true for all i.
• 14.
  P2 request anadditional instance of type C. Request A B C P0 0 0 0 P1 2 0 1 P2 0 0 1 P3 1 0 0 P4 0 0 2 State of System? Can reclaim resources held by process P0, but insufficient resources to fulfill other processes; requests. Deadlock exists, consisting of processes P1,P2,P3 and P4.
• 15.
  Detection-Algorithm Usage When, andhow often, to invoke depends on: How often a deadlock is likely to occur? How many processes will need to be rolled back? One for each disjoint cycle. If detection algorithm is invoked arbitrarily, there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes “caused” the deadlock.
• 16.
  Thank You