More Deadlock Prevention Strategies Following schemes use transaction timestamps for the sake of deadlock prevention alone. wait-die scheme-non-preemptive older transaction may wait for younger one to release data item. (older means smaller timestamp)Younger transactions never Younger transactions never wait for older ones;they are rolled back instead. a transaction may die several times before acquiring needed data item wound-wait scheme-preemptive older transaction wounds(forces rollback)of younger transaction instead of waiting for it.Younger transactions may wait for older ones. may be fewer rollbacks than wait-die scheme. Database System Concepts-6th Edition 15.17 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 15.17 ©Silberschatz, Korth and Sudarshan th Edition More Deadlock Prevention Strategies Following schemes use transaction timestamps for the sake of deadlock prevention alone. wait-die scheme — non-preemptive older transaction may wait for younger one to release data item. (older means smaller timestamp) Younger transactions never Younger transactions never wait for older ones; they are rolled back instead. a transaction may die several times before acquiring needed data item wound-wait scheme — preemptive older transaction wounds (forces rollback) of younger transaction instead of waiting for it. Younger transactions may wait for older ones. may be fewer rollbacks than wait-die scheme
Deadlock prevention (Cont.) Both in wait-die and in wound-wait schemes,a rolled back transactions is restarted with its original timestamp.Older transactions thus have precedence over newer ones,and starvation is hence avoided. Timeout-Based Schemes: a transaction waits for a lock only for a specified amount of time.If the lock has not been granted within that time,the transaction is rolled back and restarted. Thus,deadlocks are not possible simple to implement;but starvation is possible.Also difficult to determine good value of the timeout interval. Database System Concepts-6th Edition 15.18 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 15.18 ©Silberschatz, Korth and Sudarshan th Edition Deadlock prevention (Cont.) Both in wait-die and in wound-wait schemes, a rolled back transactions is restarted with its original timestamp. Older transactions thus have precedence over newer ones, and starvation is hence avoided. Timeout-Based Schemes: a transaction waits for a lock only for a specified amount of time. If the lock has not been granted within that time, the transaction is rolled back and restarted, Thus, deadlocks are not possible simple to implement; but starvation is possible. Also difficult to determine good value of the timeout interval
Deadlock Detection Deadlocks can be described as a wait-for graph,which consists of a pair G=(V,目， V is a set of vertices (all the transactions in the system) E is a set of edges;each element is an ordered pair T->T If T>T;is in E,then there is a directed edge from Ti to Ti,implying that T;is waiting for T;to release a data item. When T;requests a data item currently being held by Ti,then the edge T;>T;is inserted in the wait-for graph.This edge is removed only when T;is no longer holding a data item needed by Ti. The system is in a deadlock state if and only if the wait-for graph has a cycle.Must invoke a deadlock-detection algorithm periodically to look for cycles. Database System Concepts-6th Edition 15.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 15.19 ©Silberschatz, Korth and Sudarshan th Edition Deadlock Detection Deadlocks can be described as a wait-for graph, which consists of a pair G = (V,E), V is a set of vertices (all the transactions in the system) E is a set of edges; each element is an ordered pair Ti →Tj . If Ti → Tj is in E, then there is a directed edge from Ti to Tj , implying that Ti is waiting for Tj to release a data item. When Ti requests a data item currently being held by Tj , then the edge Ti → Tj is inserted in the wait-for graph. This edge is removed only when Tj is no longer holding a data item needed by Ti . The system is in a deadlock state if and only if the wait-for graph has a cycle. Must invoke a deadlock-detection algorithm periodically to look for cycles
Deadlock Detection (Cont.) 8 四 不西 不四 下M 人9 个9 Wait-for graph without a cycle Wait-for graph with a cycle Database System Concepts-6th Edition 15.20 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 15.20 ©Silberschatz, Korth and Sudarshan th Edition Deadlock Detection (Cont.) Wait-for graph without a cycle Wait-for graph with a cycle
Deadlock Recovery When deadlock is detected Some transaction will have to rolled back(made a victim)to break deadlock.Select that transaction as victim that will incur minimum cost. Rollback--determine how far to roll back transaction Total rollback:Abort the transaction and then restart it. More effective to roll back transaction only as far as necessary to break deadlock. Starvation happens if same transaction is always chosen as victim.Include the number of rollbacks in the cost factor to avoid starvation Database System Concepts-6th Edition 15.21 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 15.21 ©Silberschatz, Korth and Sudarshan th Edition Deadlock Recovery When deadlock is detected : Some transaction will have to rolled back (made a victim) to break deadlock. Select that transaction as victim that will incur minimum cost. Rollback -- determine how far to roll back transaction Total rollback: Abort the transaction and then restart it. More effective to roll back transaction only as far as necessary to break deadlock. Starvation happens if same transaction is always chosen as victim. Include the number of rollbacks in the cost factor to avoid starvation