浙江大学数据库系统概念PPT第十六章.ppt

《浙江大学数据库系统概念PPT第十六章.ppt》由会员分享，可在线阅读，更多相关《浙江大学数据库系统概念PPT第十六章.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Silberschatz,Korth and Sudarshan,Bo Zhou16.1Database System Concepts 3rd EditionChapter 16:Concurrency ControlnLock-Based ProtocolsnMultiple GranularitynDeadlock HandlingnInsert and Delete OperationsnConcurrency in Index StructuresSilberschatz,Korth and Sudarshan,Bo Zhou16.2Database System Concepts

2、3rd 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 r

3、equested using lock-S instruction.nLock requests are made to concurrency-control manager.Transaction can proceed only after request is granted.Silberschatz,Korth and Sudarshan,Bo Zhou16.3Database System Concepts 3rd EditionLock-Based Protocols(Cont.)nLock-compatibility matrixnA transaction may be gr

4、anted 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,but if any transaction holds an exclusive on the item no other transaction may hold any lock on the item.nIf a lock cannot

5、 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 Sudarshan,Bo Zhou16.4Database System Concepts 3rd EditionLock-Based Protocols(Cont.)nExample of a transaction performing lo

6、cking:T2:lock-S(A);read(A);unlock(A);lock-S(B);read(B);unlock(B);display(A+B)Locking 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

7、 requesting and releasing locks.Locking protocols restrict the set of possible schedules.Basically,how to generate a correct(serializable)schedule?Silberschatz,Korth and Sudarshan,Bo Zhou16.5Database System Concepts 3rd EditionPitfalls of Lock-Based ProtocolsnConsider the partial schedulenNeither T3

8、 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.To handle a deadlock one of T3 or T4 must be rolled back and its locks released.Silberschat

9、z,Korth and Sudarshan,Bo Zhou16.6Database System Concepts 3rd 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:A transact

10、ion 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.nConcurrency control manager can be designed to prevent starvation.Silberschatz,Korth and Sudarshan,Bo

11、 Zhou16.7Database System Concepts 3rd EditionThe Two-Phase Locking ProtocolnTwo-Phase Locking is a protocol which ensures conflict-serializable schedules.Phase 1:Growing Phasetransaction may obtain locks transaction may not release locksPhase 2:Shrinking Phasetransaction may release lockstransaction

12、 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 Sudarshan,Bo Zhou16.8Database System Concepts 3rd EditionThe Two-Ph

13、ase 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

14、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 Sudarshan,Bo Zhou16.9Database System Concepts 3rd EditionThe Two-Phase Locking Protocol(Cont.)nThere may be conflict s

15、erializable schedules that cannot be obtained if two-phase locking is used.nTo obtain conflict serializable schedules though non-two-phase locking protocol,we need:Either to have additional information about the transactionsOr to impose some structure or ordering on the set of date items in the data

16、base.Silberschatz,Korth and Sudarshan,Bo Zhou16.10Database System Concepts 3rd EditionLock ConversionsnLock Conversions:Only acquire X lock when necessary.Provide a mechanism for upgrading a S lock to a X lock.nTwo-phase locking with lock conversions:First Phase:can acquire a lock-S on itemcan acqui

17、re a lock-X on itemcan convert a lock-S to a lock-X(upgrade)Second Phase:can release a lock-Scan release a lock-Xcan convert a lock-X to a lock-S (downgrade)nThis protocol assures serializability.But still relies on the programmer to insert the various locking instructions.Silberschatz,Korth and Sud

18、arshan,Bo Zhou16.11Database System Concepts 3rd EditionAutomatic Acquisition of LocksAutomatic Acquisition of Locks(Commercial DBMS Uses)(Commercial DBMS Uses)nA transaction Ti issues the standard read/write instruction,without explicit locking calls.nThe operation read(D)is processed as:if Ti has a

19、 lock on D then read(D)else begin if necessary wait until no other transaction has a lock-X on D grant Ti a lock-S on D;read(D)endSilberschatz,Korth and Sudarshan,Bo Zhou16.12Database System Concepts 3rd EditionAutomatic Acquisition of Locks(Cont.)nwrite(D)is processed as:if Ti has a lock-X on D the

20、n write(D)else begin if necessary wait until no other trans.has any lock on D,if Ti has a lock-S on D then upgrade lock on D to lock-X else grant Ti a lock-X on D write(D)end;nAll locks are released after commit or abortSilberschatz,Korth and Sudarshan,Bo Zhou16.13Database System Concepts 3rd Editio

21、nOther Concurrency Control ProtocolsnGraph-Based Locking Protocol Tree protocolMaintain partial ordering of all data items.Only X lockGuarantee conflict serializablenTimestamp-Based ProtocolnValidation-Based ProtocolSilberschatz,Korth and Sudarshan,Bo Zhou16.14Database System Concepts 3rd EditionMul

22、tiple GranularitynAllow data items to be of various sizes and define a hierarchy of data granularities,where the small granularities are nested within larger onesnCan be represented graphically as a treenWhen a transaction locks a node in the tree explicitly,it implicitly locks all the nodes descend

23、ents in the same mode.nGranularity of locking(level in tree where locking is done):fine granularity(lower in tree):high concurrency,high locking overheadcoarse granularity (higher in tree):low locking overhead,low concurrencySilberschatz,Korth and Sudarshan,Bo Zhou16.15Database System Concepts 3rd E

24、ditionExample of Granularity Hierarchy The highest level in the example hierarchy is the entire database.The levels below are of type area,file and record in that order.Silberschatz,Korth and Sudarshan,Bo Zhou16.16Database System Concepts 3rd EditionIntention Lock ModesnIn addition to S and X lock m

25、odes,there are three additional lock modes with multiple granularity:intention-shared(IS):indicates explicit locking at a lower level of the tree but only with shared locks.intention-exclusive(IX):indicates explicit locking at a lower level with exclusive or shared locksshared and intention-exclusiv

26、e(SIX):the subtree rooted by that node is locked explicitly in shared mode and explicit locking is being done at a lower level with exclusive-mode locks.nintention locks allow a higher level node to be locked in S or X mode without having to check all descendent nodes.Silberschatz,Korth and Sudarsha

27、n,Bo Zhou16.17Database System Concepts 3rd EditionCompatibility Matrix withCompatibility Matrix with Intention Lock Modes Intention Lock ModesnThe compatibility matrix for all lock modes is:ISIXSS IXX ISIXSS IXX Silberschatz,Korth and Sudarshan,Bo Zhou16.18Database System Concepts 3rd EditionMultipl

28、e Granularity Locking SchemenTransaction Ti can lock a node Q,using the following rules:1.The lock compatibility matrix must be observed.2.The root of the tree must be locked first,and may be locked in any mode.3.A node Q can be locked by Ti in S or IS mode only if the parent of Q is currently locke

29、d by Ti in either IX or IS mode.4.A node Q can be locked by Ti in X,SIX,or IX mode only if the parent of Q is currently locked by Ti in either IX or SIX mode.5.Ti can lock a node only if it has not previously unlocked any node (that is,Ti is two-phase).6.Ti can unlock a node Q only if none of the ch

30、ildren of Q are currently locked by Ti.nObserve that locks are acquired in root-to-leaf order,whereas they are released in leaf-to-root order.Silberschatz,Korth and Sudarshan,Bo Zhou16.19Database System Concepts 3rd EditionDeadlock HandlingnConsider the following two transactions:T1:write(X)T2:write

31、(Y)write(Y)write(X)nSchedule with deadlockT1T2lock-X on Xwrite(X)lock-X on Ywrite(X)wait for lock-X on Xwait for lock-X on YSilberschatz,Korth and Sudarshan,Bo Zhou16.20Database System Concepts 3rd EditionDeadlock HandlingnSystem is deadlocked if there is a set of transactions such that every transa

32、ction in the set is waiting for another transaction in the set.Deadlock preventionDeadlock detectionnDeadlock 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 executio

33、n(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(graph-based protocol).Silberschatz,Korth and Sudarshan,Bo Zhou16.21Database System Concepts 3rd EditionMore Deadlock Prevention StrategiesnF

34、ollowing schemes use transaction timestamps for the sake of deadlock prevention alone.nwait-die scheme non-preemptiveolder transaction may wait for younger one to release data item.Younger transactions never wait for older ones;they are rolled back instead.a transaction may die several times before

35、acquiring needed data itemnwound-wait scheme preemptiveolder transaction wounds(forces rollback)of younger transaction instead of waiting for it.Younger transactions may wait for older ones.may be fewer rollbacks than wait-die scheme.Silberschatz,Korth and Sudarshan,Bo Zhou16.22Database System Conce

36、pts 3rd EditionWait-die vs.Wound-waitnThree transactions:A,B,C ordered by starting time.B held a lock on data item Y.ThenWait-dieWound-waitA acquire YWaitB rollback;A granted the lock on YC acquire YC rollbackWaitSilberschatz,Korth and Sudarshan,Bo Zhou16.23Database System Concepts 3rd EditionDeadlo

37、ck prevention(Cont.)nBoth in wait-die and in wound-wait schemes,a rolled back transactions is restarted with its original timestamp.Older transactions thus have precedence over newer ones,and starvation is hence avoided.nTimeout-Based Schemes:a transaction waits for a lock only for a specified amoun

38、t of time.After that,the wait times out and the transaction is rolled back.thus deadlocks are not possiblesimple to implement;but starvation is possible.Also difficult to determine good value of the timeout interval.Silberschatz,Korth and Sudarshan,Bo Zhou16.24Database System Concepts 3rd EditionDea

39、dlock DetectionnDeadlocks can be described as a wait-for graph,which consists of a pair G=(V,E),V is a set of vertices(all the transactions in the system)E is a set of edges;each element is an ordered pair Ti Tj.nIf Ti Tj is in E,then there is a directed edge from Ti to Tj,implying that Ti is waitin

40、g for Tj to release a data item.nWhen Ti requests a data item currently being held by Tj,then the edge Ti Tj is inserted in the wait-for graph.This edge is removed only when Tj is no longer holding a data item needed by Ti.nThe system is in a deadlock state if and only if the wait-for graph has a cy

41、cle.Must invoke a deadlock-detection algorithm periodically to look for cycles.Silberschatz,Korth and Sudarshan,Bo Zhou16.25Database System Concepts 3rd EditionDeadlock Detection(Cont.)Wait-for graph without a cycleWait-for graph with a cycleSilberschatz,Korth and Sudarshan,Bo Zhou16.26Database Syst

42、em Concepts 3rd EditionDeadlock RecoverynWhen deadlock is detected:Some transaction will have to rolled back(made a victim)to break deadlock.Select that transaction as victim that will incur minimum cost.Rollback-determine how far to roll back transactionTotal rollback:Abort the transaction and then restart it.More effective to roll back transaction only as far as necessary to break deadlock.Starvation happens if same transaction is always chosen as victim.Include the number of rollbacks in the cost factor to avoid starvationEnd of Chapter