Concurrency Control - WBUTHELP.COM

1 CHAPTER 16 ConcurrencyControlThis chapter describes how to Control concurrent execution in a database, in order toensure the isolation properties of transactions. A variety of protocols are describedfor this purpose. If time is short, some of the protocols may be omitted. We recom-mend covering, at the least, two-phase locking (Sections ), through , dead-lock detection and recovery (Section , omitting Section ), the phantom phe-nomenon (Section ), and the concepts behind index Concurrency Control (theintroductory part of Section ). The most widely used techniques would therebybe is worthwhile pointing out how the graph-based locking protocols generalizesimple protocols, such as ordered acquisition of locks, which students may have stud-ied in an operating system course.

2 Although the timestamp protocols by themselvesare not widely used, multiversion two-phase locking (Section ) is of increas-ing importance since it allows long read-only transactions to run concurrently phantom phenomenon is often misunderstood by students as showing thattwo-phase locking is incorrect. It is worth stressing that transactions that scan a rela-tion must read some data tofind out what tuples are in the relation; as long as thisdata is itself locked in a two-phase manner, the phantom phenomenon will not from 3rdedition:This chapter has been reorganized from the previous edition. Some of the materialfrom the Concurrency Control chapter of the second edition (Chapter 11), such asschedules and testing for serializability have been moved into Chapter 15 of the thirdedition.

3 The sections on deadlock handling (Section ) and Concurrency in indexstructures (Section ) have been moved in from Chapter 12 of the second edition(Transaction Processing). The section on multiversion two-phase locking is that the two-phase locking protocol ensures conflict serializability, andthat transactions can be serialized according to their lock the following two transactions:T31:read(A);read(B);ifA=0th enB:=B+1;write(B).T32:read(B);read(A);if B=0thenA:=A+1;write(A).Add lock and unlock instructions to transactionsT31andT32,so that they ob-serve the two-phase locking protocol. Can the execution of these transactionsresult in a deadlock? and unlock instructions:T31:lock-S(A)read(A)lock-X( B)read(B)ifA=0thenB:=B+1write(B)unlock(A )unlock(B)T32:lock-S(B)read(B)lock-X(A)r ead(A)ifB=0thenA:=A+1write(A)unlock(B)un lock(A) of these transactions can result in deadlock.

4 For example, con-sider the following partial (A)lock-S(B)read(B)read(A)lock-X(B)lock- X(A)The transactions are now benefit does strict two-phase locking provide? What disadvantages re-sult?Answer:Because it produces only cascadeless schedules, recovery is very the set of schedules obtainable is a subset of those obtainable from plaintwo phase locking, thus Concurrency is benefit does rigorous two-phase locking provide? How does it comparewith other forms of two-phase locking?Answer:Rigorous two-phase locking has the advantages of strict 2PL. In addi-tion it has the property that for two conflicting transactions, their commit orderis their serializability order. In some systems users might expect this implementations of database systems use strict two-phase locking. Sug-gest three reasons for the popularity of this :It is relatively simple to implement, imposes low rollback overheadbecause of cascadeless schedules, and usually allows an acceptable level a database organized in the form of a rooted tree.

5 Suppose that weinsert a dummy vertex between each pair of vertices. Show that, if we followthe tree protocol on the new tree, we get better Concurrency than if we followthe tree protocol on the original :The proof is in Buckley and Silberschatz, Concurrency Control inGraph Protocols by Using Edge Locks, Proc. ACM SIGACT-SIGMOD Sym-posium on the Principles of Database Systems, by example that there are schedules possible under the tree protocol thatare not possible under the two-phase locking protocol, and vice :Consider the tree-structured database graph given possible under tree protocol but not under 2 (A)lock(B)unlock(A)lock(A)lock(C)unlock( B)lock(B)unlock(A)unlock(B)unlock(C)Sche dule possible under 2PL but not under tree protocol:T1T2lock(A)lock(B)lock(C)unlock (B)unlock(A)unlock(C) the following extension to the tree-locking protocol, which allowsboth shared and exclusive locks: A transaction can be either a read-only transaction, in which case it canrequest only shared locks, or an update transaction, in which case it canrequest only exclusive locks.

6 Each transaction must follow the rules of the tree protocol. Read-only trans-actions may lock any data itemfirst, whereas update transactions mustlock the that the protocol ensures serializability and deadlock :The proof is in Kedem and Silberschatz, Locking Protocols: FromExclusive to Shared Locks, JACM Vol. 30, 4, the following graph-based locking protocol, which allows only ex-clusive lock modes, and which operates on data graphs that are in the form ofa rooted directed acyclic graph. A transaction can lock any vertexfirst. To lock any other vertex, the transaction must be holding a lock on themajority of the parents of that that the protocol ensures serializability and deadlock :The proof is in Kedem and Silberschatz, Controlling ConcurrencyUsing Locking Protocols, Proc.

7 Annual IEEE Symposium on Foundations ofComputer Science, the following graph-based locking protocol that allows only exclu-sive lock modes, and that operates on data graphs that are in the form of arooted directed acyclic Atransaction can lock any vertexfirst. To lock any other vertex, the transaction must have visited all the parentsof that vertex, and must be holding a lock on one of the parents of that the protocol ensures serializability and deadlock :The proof is in Kedem and Silberschatz, Controlling ConcurrencyUsing Locking Protocols, Proc. Annual IEEE Symposium on Foundations ofComputer Science, a variant of the tree protocol called theforestprotocol. The databaseis organized as a forest of rooted trees. Each transactionTimustfollow thefollowing rules: Thefirst lock in each tree may be on any data item.

8 The second, and all subsequent, locks in a tree may be requested only ifthe parent of the requested node is currently locked. Data items may be unlocked at any time. A data item may not be relocked byTiafterit has been unlocked that the forest protocol doesnotensure :Take a system with 2 trees:n11n12n6n2n5n10n8n9n4n7n3n1We have 2 transactions, the following legal (n1)lock(n3)write(n3)unlock(n3)lock(n2)l ock(n5)write(n5)unlock(n5)lock(n5)read(n 5)unlock(n5)unlock(n1)lock(n3)read(n3)un lock(n3)unlock(n2)This schedule is not is not done explicitly in persistent programming languages. Rather,objects (or the corresponding pages) must be locked when the objects are ac-cessed. Most modern operating systems allow the user to set access protections(no access, read, write) on pages, and memory access that violate the accessprotections result in a protection violation (see the Unixmprotectcommand,for example).

9 Describe how the access-protection mechanism can be used forpage-level locking in a persistent programming language. (Hint: The techniqueis similar to that used for hardware swizzling in Section ).Answer:The access protection mechanism can be used to implement pagelevel locking. Consider readsfirst. A process is allowed to read a page only af-ter it read-locks the page. This is implemented by usingmprotectto initiallyturn off read permissions to all pages, for the process. When the process triesto access an address in a page, a protection violation occurs. The handler as-sociated with protection violation then requests a read lock on the page, andafter the lock is acquired, it usesmprotectto allow read access to the page bythe process, andfinally allows the process to continue.

10 Write access is a database system that includes an atomicincrementoperation, inaddition to thereadandwriteoperations. LetVbe the value of data operationincrement(X)byCsets the value ofXtoV+Cin an atomic step. The value ofXis not available tothe transaction unless the latter executes aread(X). Figure shows a lock-compatibility matrix for three lock modes: share mode, exclusive mode, andincrementation Lock-compatibility that, if all transactions lock the data that they access in the corre-sponding mode, then two-phase locking ensures that the inclusion ofincrementmode locks allows for increased con-currency. (Hint: Consider check-clearing transactions in our bank exam-ple.)Answer:The proof is in Korth, Locking Primitives in a Database System, JACM Vol. 30, timestamp ordering,W-timestamp(Q)denotes the largest timestamp of anytransaction that executedwrite(Q)successfully.