Database System Concepts, 6th Ed.Silberschatz, Korth and SudarshanSee www.db- for conditions on re-use Chapter 15 : Concurrency Control Silberschatz, Korth and Sudarshan15.2Database System Concepts - 6th EditionChapter 15: Concurrency ControlnLock-Based ProtocolsnTimestamp-Based ProtocolsnValidation-Based ProtocolsnMultiple GranularitynMultiversion SchemesnInsert and Delete OperationsnConcurrency in Index StructuresSilberschatz, Korth and Sudarshan15.3Database System Concepts - 6th EditionLock-Based ProtocolsnA lock is a mechanism to control concurrent access to a data itemnData items can be locked in two modes : 1. exclusive (X) mode. Data item can be both read as well as written. X-lock is requested using lock-X instruction. 2. shared (S) mode. Data item can only be read. S-lock is requested using lock-S instruction.nLock requests are made to concurrency-control manager. Transaction can proceed only after request is granted.Silberschatz, Korth and Sudarshan15.4Database System Concepts - 6th EditionLock-Based Protocols (Cont.)nLock-compatibility matrixnA transaction may be granted a lock on an item if the requested lock is compatible with locks already held on the item by other transactionsnAny number of transactions can hold shared locks on an item, lbut if any transaction holds an exclusive on the item no other transaction may hold any lock on the item.nIf a lock cannot be granted, the requesting transaction is made to wait till all incompatible locks held by other transactions have been released. The lock is then granted.Silberschatz, Korth and Sudarshan15.5Database System Concepts - 6th EditionLock-Based Protocols (Cont.)nExample of a transaction performing locking: T2: lock-S(A); read (A); unlock(A); lock-S(B); read (B); unlock(B); display(A+B)nLocking as above is not sufficient to guarantee serializability if A and B get updated in-between the read of A and B, the displayed sum would be wrong.nA locking protocol is a set of rules followed by all transactions while requesting and releasing locks. Locking protocols restrict the set of possible schedules.Silberschatz, Korth and Sudarshan15.6Database System Concepts - 6th EditionPitfalls of Lock-Based ProtocolsnConsider the partial schedulenNeither T3 nor T4 can make progress executing lock-S(B) causes T4 to wait for T3 to release its lock on B, while executing lock-X(A) causes T3 to wait for T4 to release its lock on A.nSuch a situation is called a deadlock. lTo handle a deadlock one of T3 or T4 must be rolled back and its locks released.Silberschatz, Korth and Sudarshan15.7Database System Concepts - 6th EditionPitfalls of Lock-Based Protocols (Cont.)nThe potential for deadlock exists in most locking protocols. Deadlocks are a necessary evil.nStarvation is also possible if concurrency control manager is badly designed. For example:lA 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. lThe same transaction is repeatedly rolled back due to deadlocks.nConcurrency control manager can be designed to prevent starvation.Silberschatz, Korth and Sudarshan15.8Database System Concepts - 6th EditionThe Two-Phase Locking ProtocolnThis is a protocol which ensures conflict-serializable schedules.nPhase 1: Growing Phaseltransaction may obtain locks ltransaction may not release locksnPhase 2: Shrinking Phaseltransaction may release locksltransaction may not obtain locksnThe 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). Silberschatz, Korth and Sudarshan15.9Database System Concepts - 6th EditionThe Two-Phase Locking Protocol (Cont.)nTwo-phase locking does not ensure freedom from deadlocksnCascading 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.nRigorous 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.Silberschatz, Korth and Sudarshan15.10Database System Concepts - 6th EditionThe Two-Phase Locking Protocol (Cont.)nThere can be conflict serializable schedules that cannot be obtained if two-phase locking is used. nHowever, 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.Silberschatz, Korth and Sudarshan15.11Database System Concepts - 6th EditionLock ConversionsnTwo-phase locking with lock conversions: First Phase: lcan acquire a lock-S on itemlcan acquire a lock-X on itemlcan convert a lock-S to a lock