Deadlocks (Cont.) Two-phase locking does not ensure freedom from deadlocks. In addition to deadlocks,there is a possibility of starvation. Starvation occurs if the concurrency control manager is badly designed.For example: A transaction may be waiting for an X-lock on an item, while a sequence of other transactions request and are granted an S-lock on the same item. The same transaction is repeatedly rolled back due to deadlocks. Concurrency control manager can be designed to prevent starvation. Database System Concepts-6th Edition 15.12 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 15.12 ©Silberschatz, Korth and Sudarshan th Edition Deadlocks (Cont.) Two-phase locking does not ensure freedom from deadlocks. In addition to deadlocks, there is a possibility of starvation. Starvation occurs if the concurrency control manager is badly designed. For example: A transaction may be waiting for an X-lock on an item, while a sequence of other transactions request and are granted an S-lock on the same item. The same transaction is repeatedly rolled back due to deadlocks. Concurrency control manager can be designed to prevent starvation
Deadlocks (Cont.) The potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil. When a deadlock occurs there is a possibility of cascading roll- backs. Cascading roll-back is possible under two-phase locking.To avoid this,follow a modified protocol called strict two-phase locking--a transaction must hold all its exclusive locks till it commits/aborts. Rigorous two-phase locking is even stricter.Here,al/locks are held till commit/abort.In this protocol transactions can be serialized in the order in which they commit Database System Concepts-6th Edition 15.13 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 15.13 ©Silberschatz, Korth and Sudarshan th Edition Deadlocks (Cont.) The potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil. When a deadlock occurs there is a possibility of cascading rollbacks. Cascading roll-back is possible under two-phase locking. To avoid this, follow a modified protocol called strict two-phase locking -- a transaction must hold all its exclusive locks till it commits/aborts. Rigorous two-phase locking is even stricter. Here, all locks are held till commit/abort. In this protocol transactions can be serialized in the order in which they commit
Implementation of Locking A lock manager can be implemented as a separate process to which transactions send lock and unlock requests The lock manager replies to a lock request by sending a lock grant messages (or a message asking the transaction to roll back,in case of a deadlock) The requesting transaction waits until its request is answered The lock manager maintains a data-structure called a lock table to record granted locks and pending requests The lock table is usually implemented as an in-memory hash table indexed on the name of the data item being locked Database System Concepts-6th Edition 15.14 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 15.14 ©Silberschatz, Korth and Sudarshan th Edition Implementation of Locking A lock manager can be implemented as a separate process to which transactions send lock and unlock requests The lock manager replies to a lock request by sending a lock grant messages (or a message asking the transaction to roll back, in case of a deadlock) The requesting transaction waits until its request is answered The lock manager maintains a data-structure called a lock table to record granted locks and pending requests The lock table is usually implemented as an in-memory hash table indexed on the name of the data item being locked
Lock Table T23 Dark blue rectangles indicate granted locks;light blue indicate waiting requests Lock table also records the type of lock T23 T8 T2 granted or requested New request is added to the end of the 1912 queue of requests for the data item,and granted if it is compatible with all earlier locks T23 Unlock requests result in the request being deleted,and later requests are checked to see if they can now be granted T23 If transaction aborts,all waiting or granted requests of the transaction are deleted lock manager may keep a list of locks granted held by each transaction,to implement this efficiently waiting Database System Concepts-6th Edition 15.15 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 15.15 ©Silberschatz, Korth and Sudarshan th Edition Lock Table Dark blue rectangles indicate granted locks; light blue indicate waiting requests Lock table also records the type of lock granted or requested New request is added to the end of the queue of requests for the data item, and granted if it is compatible with all earlier locks Unlock requests result in the request being deleted, and later requests are checked to see if they can now be granted If transaction aborts, all waiting or granted requests of the transaction are deleted lock manager may keep a list of locks held by each transaction, to implement this efficiently
Deadlock Handling System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set. Deadlock prevention protocols ensure that the system will never enter into a deadlock state.Some prevention strategies Require that each transaction locks all its data items before it begins execution (predeclaration). Impose partial ordering of all data items and require that a transaction can lock data items only in the order specified by the partial order. Database System Concepts-6th Edition 15.16 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 15.16 ©Silberschatz, Korth and Sudarshan th Edition Deadlock Handling System is deadlocked if there is a set of transactions such that every transaction in the set is waiting for another transaction in the set. Deadlock prevention protocols ensure that the system will never enter into a deadlock state. Some prevention strategies : Require that each transaction locks all its data items before it begins execution (predeclaration). Impose partial ordering of all data items and require that a transaction can lock data items only in the order specified by the partial order