Pitfalls of Lock-Based Protocols (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-5th Edition,Oct 5,2006 16.7 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 16.7 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Pitfalls of Lock-Based Protocols (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 This is 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 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-5th Edition,Oct 5,2006 16.8 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 16.8 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 The Two-Phase Locking Protocol This is 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 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)
The Two-Phase Locking Protocol (Cont.) Two-phase locking does not ensure freedom from deadlocks Cascading roll-back is possible under two-phase locking.To avoid this, follow a modified protocol called strict two-phase locking.Here 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. Database System Concepts-5th Edition,Oct 5,2006 16.9 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 16.9 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 The Two-Phase Locking Protocol (Cont.) Two-phase locking does not ensure freedom from deadlocks Cascading roll-back is possible under two-phase locking. To avoid this, follow a modified protocol called strict two-phase locking. Here 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
The Two-Phase Locking Protocol (Cont.) There can be conflict serializable schedules that cannot be obtained if two-phase locking is used. However,in the absence of extra information(e.g.,ordering of access to data),two-phase locking is needed for conflict serializability in the following sense: Given a transaction T that does not follow two-phase locking,we can find a transaction T that uses two-phase locking,and a schedule for T; and T that is not conflict serializable. Database System Concepts-5th Edition,Oct 5,2006 16.10 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 16.10 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 The Two-Phase Locking Protocol (Cont.) There can be conflict serializable schedules that cannot be obtained if two-phase locking is used. However, in the absence of extra information (e.g., ordering of access to data), two-phase locking is needed 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
Lock Conversions Two-phase locking with lock conversions: First Phase: can acquire a lock-S on item can acquire a lock-X on item can convert a lock-S to a lock-X(upgrade) Second Phase: can release a lock-S can release a lock-X can convert a lock-X to a lock-S (downgrade) This protocol assures serializability.But still relies on the programmer to insert the various locking instructions. Database System Concepts-5th Edition,Oct 5,2006 16.11 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 16.11 ©Silberschatz, Korth and Sudarshan th Edition, Oct 5, 2006 Lock Conversions Two-phase locking with lock conversions: – First Phase: can acquire a lock-S on item can acquire a lock-X on item can convert a lock-S to a lock-X (upgrade) – Second Phase: can release a lock-S can release a lock-X can convert a lock-X to a lock-S (downgrade) This protocol assures serializability. But still relies on the programmer to insert the various locking instructions