ch 2 - DISTRIBUTED DEADLOCK DETECTION.pptx

operating system

1. DISTRIBUTED DEADLOCK DETECTION BY Dr. T.R.SRINIVASAN, B.E., M.E., Ph.D., Assistant Professor, School of Electrical and Computer Engineering, Jimma Institute of Technology, Jimma University, Jimma 1

2. THE SYSTEM MODEL In chapter 1: Deadlock under centralized system Methods to handle deadlock Deadlock in DS under following model System have only reusable resources Process are allowed only exclusive access to resources Only one copy of resources States of Process Running Blocked Deadlock Resource Deadlock Communication Deadlock Resource Allocation Graph Wait-For Graph(WFG) Transaction-Wait-For Graph(TWF Graph) 2

3. DEADLOCK HANDLING STRATEGIES IN DISTRIBUTED SYSTEM (DS) DEADLOCK PREVENTION Process acquire needed resources before execution Inefficient as it decreases system concurrency Set of process can become deadlocked while resource acquiring Future resource requirements are unpredictable Preempting a process that holds needed resource DEADLOCK AVOIDANCE Resource is granted if the resulting global state is safe Every site to maintain global state of the system – huge storage requirement and communication cost Process of checking the global state must be mutually exclusive – several site concurrently checks for safe global state but the net global state may not be true Large No. of Processes and Resources – Computationally Expensive DEADLOCK DETECTION Once cycle is formed in WFG – it persists until detected and broken Cycle detection can proceed concurrently with the normal activity 3

4. ISSUES IN DEADLOCK DETECTION AND RESOLUTION Detection of Existing Deadlocks In DS, cycle involves several sites – search for cycle depends how WFG is represented Centralized Algorithms Distributed Algorithms Hierarchical Algorithms Correct deadlock Detection Algorithm must satisfy Progress – No Undetected Deadlocks Detect all deadlocks in finite time After all wait-for dependencies are formed – algorithm should not wait for more to detect the deadlock Safety – No False Deadlocks Not report deadlocks that are non-existent (PHANTOM DEADLOCKS) Resolution of detected Deadlocks Breaking wait-for dependencies to resolve deadlocks Rolling back one or more processes that are deadlocked Algorithms propagate regarding wait-for along the edges When edge is broken, it should be updated to all sites Not updated in time will result in Phantom Deadlocks 4

5. CONTROL ORGANIZATIONS FOR DDD CETRALIZED CONTROL Control site responsible for constructing the WFG Searches for cycles Maintains WFG or built it whenever DD to be carried out Simple and easy to implement Single point of failure Congested near the control site because of msgs from all other sites DISTRIBUTED CONTROL Responsibility is shared equally among all sites Global state graph is spread over many sites Several site participate I detecting deadlock Detection is initiated by a waiting process suspected to be part of a cycle difficult to design due to lack of globally shared memory Several sites may initiate detection for the same deadlock Proof of correctness is difficult for these algorithms Resolution is cumbersome – several sites detect same deadlock and not aware of other sites involved HIERARCHICAL CONTROL Sites are arranged in hierarchical fashion Sites detects deadlock involving only its descendant sites Get the best of both CETRALIZED and DISTRIBUTED CONTROL Requires special care while arranging the sites in hierarchical order Objective is defeated if deadlocks span several clusters 5

6. CENTRALIZED DEADLOCK DETECTION ALGORITHMS THE COMPLETELY CENTRALIZED ALGORITHM Simplest Centralized Deadlock Detection Algorithm Control Site(CS) maintain WFG Msgs to control site by all other sites Request resource Release resource Control site receives msg updates WFG Whenever adds edge to WFG checks for deadlocks Simple and easy to implement Inefficient since all request will be thru CS even for a local resource Large delays, communication and congestion overheads Reliability is poor – control site failure Solution for above issues Local WFG maintained by each site and sends to CS whenever global WFG is constructed But due to comm. Delay and inconsistent view of the system detects false deadlocks Example – Resource R1 and R2 at site S1 and S2, Transaction T1 and T2 started simultaneously at site S3 and S4. T1 T2 Lock R1 Lock R1 Unlock R1 unlock R1 Lock R2 Lock R2 Unlock R2 unlock R2 THE HO-RAMAMOORTHY ALGORITHMS Two-phase Algorithm One-phase Algorithm 6

7. Cont… Two-phase Algorithm Each site maintains a status table – contains status of processes of that site Status of process – resources locked and resources being waited for Periodically, control site requests for status table from all other sites and constructs WFG and searches for deadlocks If no cycles, system is free from deadlock Otherwise, control site ask for status table again Constructs WFG with transactions common to both reports By selecting the common transaction gets the consistent view of the system In deadlock, same wait-for condition must exist in both report May result in false deadlock reports By getting two reports, reduces the probability of getting an inconsistent view, but does not eliminate the possibility 7

8. One-phase Algorithm Requires only one status report from each site Each site maintains two tables Resource status table Transactions that locked or waiting for resources of that site Process status table Resources locked and being waited by processes Periodically, control site requests for both tables from all sites and constructs WFG using transactions common to both tables Now searches the WFG for cycles Consistent and faster when compared with two-phase Requires fewer msgs than two-phase Requires more storage since maintains two tables Msg size is bigger since transfers both tables 8 Cont…

9. All sites collectively cooperate to detect deadlock Initiated when a process is forced to wait Initiated by the site where the process waits or by the local site Classes of algorithm Path-pushing Edge-chasing Diffusion computation Global state detection 9 DISTRIBUTED DEADLOCK DETECTION ALGORITHMS

10. Information about wait-for dependencies is propagated as paths Obermarch’s algorithm is used to demonstrate which uses distributed database system Process are referred to transactions denoted by T 1 ,T 2 ,T 3 ,…, T n Transactions have multiple subtransactions that executes in different sites Atmost one subtransaction within a transaction can be executing at the same time Execution passes sequentially from one to the other Subtransactions communicate using msgs Algorithm features Nonlocal portion of WFG is abstracted( realeted) by a node(External or Ex) Transactions are ordered which reduces the msgs and reduces deadlock detection overheads Ensures exactly one transaction in each cycle detects deadlock 10 A PATH-PUSHING ALGORITHM

11. 11

12. Uses a special message called PROBE Probe is triplet( I,j,k ) Deadlock detection initiated for process P i Sent by home site of P j To the home site of P k Probe travels along the edges of TWF graph Deadlock detected when returns to initiaing process Terms and data structures used in this algorithm P j is said to depend on P k if exists a sequence like P j ,P i1 ,P i2 ,P i3 ,…, P im ,P k Each process is blocked except P k All process holds a resource for which the previous process is waiting except P j System maintains a boolean array: Dependen ti Dependent i (j) is true, if P i knows P j is dependent on it Initially Dependent i (j) is false for all i and j 12 AN EDGE-CHASING ALGORITHM

13. 13

14. 14

15. Deadlock detection computation is diffused through WFG Msgs used: query( i,j,k ) and reply( i,j,k ) Diffusion computation initiated by P i , Sent from P j , Sent to P k Blocked process sends the query msg to all processes Active process discards both query and reply msg When a blocked process receives a query, it takes the following action If first query msg (called engaging query) by P k , then propagates to all dependents, sets NUM k ( i ) to the no. of query messages sent Not an engaging query, P k returns a reply msg immediately, provided P k is blocked else discards it Local boolean variablenWAIT k ( i ) at P k denotes it’s blocked since the engaging msg from P i When blocked process receives a reply msg decrements NUM k ( i ) and holds WAIT k ( i ) 15 A DIFFUSION COMPUTATION BASED ALGORITHM

16. 16

17. Three Algorithms Bracha and Toueg Algorithm Two Phases First Phase: Records the snapshot of WFG Second Phase: simulates the request grand for deadlocks Second phase is nested inside first phase Wang Algorithm Two Phases First Phase: Records the snapshot of WFG Second Phase: WFG recorded is reduced to detect deadlocks first phase and Second phase occur serially Kshemkalyani-Singhal Algorithm Single Phase and Both sweeps are done concurrently Fan-out sweep msgs outward from the initiator process Fan-in sweep msgs inward to the initiator process Sweep of WFG is a traversal of the WFG Fan-out: msg will traverse along the edges in edge direction Fan-in: msg will traverse along the edges in opposite edge direction In the inward sweep, recorded WFG is reduced to determine whether initiator is deadlocked or not 17 A GLOBAL STATE DETECTION BASED ALGORITHM

18. 18 SYSTEM MODEL 1. System has N nodes 2. Nodes connected to other by a logical channel 3. Event in a computation – Internal, msg sent, msg receive 4. Events are assigned timestamp as per Lamport’s clock 5. Event occurred at time t on node i is given by t i 6. Computation msg can be REQUEST, REPLY or CANCEL 7. A node sends REQUEST to other nodes when it blocks 8. when node I blocks on node j, node j becomes successor of node i in WFG 9. A reply msg denotes the granting of request 10. A node i unblocks when P i out of its Q i request are granted 11. When node unblocks, sends CANCEL msg to withdraw the remaining requests it had sent

19. 19

20. Sites are arranged in Hierarchical fashion Site is responsible for detecting deadlocks involving only its children sites Localized to a cluster of sites Two different algorithms The Menasce-Muntz Algorithm Controllers are arranged in tree fashion Controllers manage resources and detects deadlocks Controllers at the bottom most(leaf controllers) manages the resources Non leaf controllers are responsible for deadlock detection A leaf controller maintains part of global WFG concerned with the resources allocated by it A non leaf controller maintains all TWF graph spanning its children and responsible for detecting deadlocks involving all its children If change occurs in TWF due to allocation, wait or release – it propagates to its parent controller Parent controller updates TWF and checks for cycles, propagates up if necessary 20 HIERARCHICAL DEADLOCK DETECTION ALGORITHMS

21. The Ho- Ramamoorthy Algorithm Sites are grouped into several disjoint clusters A site is chosen as central control site, which dynamically chooses control site for clusters Central CS requests each cluster CS for transaction status and wait-for relations Central CS after collecting status table from all clusters applies one-phase deadlock detection algorithm for intracluster deadlocks Central CS send intercluster information to cluster CS Cluster CS splices the information constructs the WFG and checks for cycles 21

22. Cont… 22