Deadlock Detection In the centralized deadlock-detection approach,a global wait-for graph is constructed and maintained in a single site;the deadlock-detection coordinator Real graph:Real,but unknown,state of the system. Constructed graph:Approximation generated by the controller during the execution of its algorithm. the global wait-for graph can be constructed when: a new edge is inserted in or removed from one of the local wait-for graphs. a number of changes have occurred in a local wait-for graph the coordinator needs to invoke cycle-detection. If the coordinator finds a cycle,it selects a victim and notifies all sites.The sites roll back the victim transaction. Database System Concepts-7th Edition 23.27 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 23.27 ©Silberschatz, Korth and Sudarshan th Edition Deadlock Detection ▪ In the centralized deadlock-detection approach, a global wait-for graph is constructed and maintained in a single site; the deadlock-detection coordinator • Real graph: Real, but unknown, state of the system. • Constructed graph: Approximation generated by the controller during the execution of its algorithm . ▪ the global wait-for graph can be constructed when: • a new edge is inserted in or removed from one of the local wait-for graphs. • a number of changes have occurred in a local wait-for graph. • the coordinator needs to invoke cycle-detection. ▪ If the coordinator finds a cycle, it selects a victim and notifies all sites. The sites roll back the victim transaction
Local and Global Wait-For Graphs T2 T2 T4 Local 3 3 site S1 site S2 T T2 T5 Global Database System Concepts-7th Edition 23.28 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 23.28 ©Silberschatz, Korth and Sudarshan th Edition Local and Global Wait-For Graphs Local Global
Example Wait-For Graph for False Cycles Initial state: T 3 T2 T3 S1 S2 T2 coordinator Database System Concepts-7th Edition 23.29 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 23.29 ©Silberschatz, Korth and Sudarshan th Edition Example Wait-For Graph for False Cycles Initial state:
False Cycles (Cont.) Suppose that starting from the state shown in figure, 1.T2 releases resources at Si resulting in a message remove T1->T2 message from the Transaction Manager at site S1 to the coordinator) 2.And then T2 requests a resource held by T3 at site S2 resulting in a message insert 72->T3 from S2 to the coordinator ■ Suppose further that the insert message reaches before the delete message this can happen due to network delays The coordinator would then find a false cycle T1→T2→T3→T1 The false cycle above never existed in reality. False cycles cannot occur if two-phase locking is used. Database System Concepts-7th Edition 23.30 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 23.30 ©Silberschatz, Korth and Sudarshan th Edition False Cycles (Cont.) ▪ Suppose that starting from the state shown in figure, 1. T2 releases resources at S1 ▪ resulting in a message remove T1 → T2 message from the Transaction Manager at site S1 to the coordinator) 2. And then T2 requests a resource held by T3 at site S2 ▪ resulting in a message insert T2 → T3 from S2 to the coordinator ▪ Suppose further that the insert message reaches before the delete message • this can happen due to network delays ▪ The coordinator would then find a false cycle T1 → T2 → T3 → T1 ▪ The false cycle above never existed in reality. ▪ False cycles cannot occur if two-phase locking is used
Distributed Deadlocks Unnecessary rollbacks may result When deadlock has indeed occurred and a victim has been picked, and meanwhile one of the transactions was aborted for reasons unrelated to the deadlock. Due to false cycles in the global wait-for graph;however,likelihood of false cycles is low. In the distributed deadlock-detection approach,sites exchange wait-for information and check for deadlocks Expensive and not used in practice Database System Concepts-7th Edition 23.31 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 23.31 ©Silberschatz, Korth and Sudarshan th Edition Distributed Deadlocks ▪ Unnecessary rollbacks may result • When deadlock has indeed occurred and a victim has been picked, and meanwhile one of the transactions was aborted for reasons unrelated to the deadlock. • Due to false cycles in the global wait-for graph; however, likelihood of false cycles is low. ▪ In the distributed deadlock-detection approach, sites exchange wait-for information and check for deadlocks • Expensive and not used in practice