Deadlock (Cont.) The potential for deadlock exists in most locking protocols.Deadlocks are a necessary evil. Starvation is also possible if 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-7th Edition 18.8 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 18.8 ©Silberschatz, Korth and Sudarshan th Edition Deadlock (Cont.) ▪ The potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil. ▪ Starvation is also possible if 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
The Two-Phase Locking Protocol A protocol which ensures conflict- serializable schedules. Phase 1:Growing Phase Transaction may obtain locks Transaction may not release locks Phase 2:Shrinking Phase Transaction may release locks Transaction may not obtain locks Time The protocol assures serializability.It can be proved that the transactions can be serialized in the order of their lock points (i.e.,the point where a transaction acquired its final lock). Database System Concepts-7th Edition 18.9 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 18.9 ©Silberschatz, Korth and Sudarshan th Edition The Two-Phase Locking Protocol ▪ A protocol which ensures conflictserializable schedules. ▪ Phase 1: Growing Phase • Transaction may obtain locks • Transaction may not release locks ▪ Phase 2: Shrinking Phase • Transaction may release locks • Transaction may not obtain locks ▪ The protocol assures serializability. It can be proved that the transactions can be serialized in the order of their lock points (i.e., the point where a transaction acquired its final lock). Time Locks
The Two-Phase Locking Protocol (Cont.) Two-phase locking does not ensure freedom from deadlocks Extensions to basic two-phase locking needed to ensure recoverability of freedom from cascading roll-back Strict two-phase locking:a transaction must hold all its exclusive locks till it commits/aborts. Ensures recoverability and avoids cascading roll-backs Rigorous two-phase locking:a transaction must hold al/locks till commit/abort. Transactions can be serialized in the order in which they commit. Most databases implement rigorous two-phase locking,but refer to it as simply two-phase locking Database System Concepts-7th Edition 18.10 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 18.10 ©Silberschatz, Korth and Sudarshan th Edition The Two-Phase Locking Protocol (Cont.) ▪ Two-phase locking does not ensure freedom from deadlocks ▪ Extensions to basic two-phase locking needed to ensure recoverability of freedom from cascading roll-back • Strict two-phase locking: a transaction must hold all its exclusive locks till it commits/aborts. ▪ Ensures recoverability and avoids cascading roll-backs • Rigorous two-phase locking: a transaction must hold all locks till commit/abort. ▪ Transactions can be serialized in the order in which they commit. ▪ Most databases implement rigorous two-phase locking, but refer to it as simply two-phase locking
The Two-Phase Locking Protocol (Cont.) T T Two-phase locking is not a necessary condition for serializability lock-X(B) There are conflict serializable read(B) schedules that cannot be obtained B:=B-50 if the two-phase locking protocol is write(B) used. unlock(B) In the absence of extra information lock-S(4) (e.g.,ordering of access to data),two- read() phase locking is necessary for conflict unlock() serializability in the following sense: lock-S(B) Given a transaction Ti that does not follow two-phase locking,we read(B) can find a transaction T;that uses unlock(B) two-phase locking,and a schedule display(A +B) for Ti and Ti that is not conflict lock-X(4) serializable. read() A:=A+50 write() unlock() Database System Concepts-7th Edition 18.11 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 18.11 ©Silberschatz, Korth and Sudarshan th Edition The Two-Phase Locking Protocol (Cont.) ▪ Two-phase locking is not a necessary condition for serializability • There are conflict serializable schedules that cannot be obtained if the two-phase locking protocol is used. ▪ In the absence of extra information (e.g., ordering of access to data), twophase locking is necessary for conflict serializability in the following sense: • Given a transaction Ti that does not follow two-phase locking, we can find a transaction Tj that uses two-phase locking, and a schedule for Ti and Tj that is not conflict serializable
Locking Protocols Given a locking protocol (such as 2PL) A schedule S is legal under a locking protocol if it can be generated by a set of transactions that follow the protocol A protocol ensures serializability if all legal schedules under that protocol are serializable Database System Concepts-7th Edition 18.12 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 18.12 ©Silberschatz, Korth and Sudarshan th Edition Locking Protocols ▪ Given a locking protocol (such as 2PL) • A schedule S is legal under a locking protocol if it can be generated by a set of transactions that follow the protocol • A protocol ensures serializability if all legal schedules under that protocol are serializable