数据库原理并发控制.pptx

《数据库原理并发控制.pptx》由会员分享，可在线阅读，更多相关《数据库原理并发控制.pptx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第11章 并发控制第1节并发控制概述第2节封锁（Locking）第3节活锁和死锁第4节并发调度的可串行性第5节两阶段锁协议第6节封锁的粒度第1页/共43页1 并发控制概述多用户数据库系统允许多个用户同时使用的数据库系统。多事务执行方式串行执行：每个时刻只有一个事务运行，其他事务必须等到这个事务结束以后方能运行。（不能充分利用系统资源如I/O,CPU等，不能发挥数据库共享资源的特点）交叉并发：单处理机，操作轮流交叉执行。虽然并行事务并没有真正地并行运行，但减少了处理机的空闲时间，提高了系统效率。同时并发：多处理机，多个处理机同时运行多个事务，实现多个事务真正的并行运行。第2页/共43页事务的串行

2、执行与交叉并发执行T1T2T3事务串行执行事务交叉并发执行第3页/共43页事务并发执行带来的问题多个事务同时存取同一数据。可能会存取和存储不正确的数据，从而破坏事务的一致性和数据库的一致性。并发控制DBMS必须提供并发控制机制，以保证事务的隔离性，保证数据库的一致性。并发控制机制是衡量一个DBMS系统性能的重要标志之一。并发控制子系统，通过对并发事务的并发操作进行正确调度，来保证事务的隔离性和一致性的。第4页/共43页并发操作对数据库一致性影响的实例飞机订票系统中两个售票事务的并发执行甲售票点（甲事务）读出某航班的机票余额A,设A=16;乙售票点（乙事务）读出同一航班的机票余额A,也为16;甲

3、售票点卖出一张机票，AA-1，把A=15写回数据库。乙售票点也卖出一张机票，A A-1，把A=15写回数据库。售票结果卖出两张机票，数据库中却只减少了一张。原因在事务并发执行时，DBMS对事务的并发操作序列进行了随机调度。使得甲事务对数据库的修改被乙事务的修改结果所覆盖。这种情况称丢失修改。第5页/共43页并发操作会引起哪些数据不一致性呢？数据不一致性丢失修改（Lost Update）不可重复读（Non-repeatable Read）读“脏”数据（Dirty Read）记号R(x):读数据xW(x):写数据x 第6页/共43页三种数据不一致性R(A)=16 A=A-1 W(A)=15R(A)

4、=16A=A-1W(A)=15R(A)=50 R(B)=100求和=150 R(A)=50 R(B)=200求和=250(验算不对)R(B)=100 B=B*2W(B)=200R(C)=100R(C)=C*2W(C)=200 RollbackC恢复为100R(C)=200T1T2T1T2T1T2（a）丢失修改（b）不可重复读（c）读“脏”数据第7页/共43页三类数据不一致性丢失修改两个事务T1和T2读入同一数据并修改，T2 提交的结果破坏了T1提交的结果，导致T1的修改丢失。不可重复读事务T1读取数据后，事务T2执行更新操作，使T1无法再现前一次读取结果。不可重复读的三种情况事务T1读取某一数

5、据后，事务T2对其做了修改，当事务T1再次读取该数据时，得到与前一次不同的值。事务T1按条件读，事务T2删除其中记录，T1再读，发现数据丢失。事务T1按一定条件从数据库中读取数据，事务T2插入记录，T1再读，发现多了一些记录。读“脏”数据事务T1修改某一数据，并将其写回磁盘，事务T2读取同一数据后，T1由于某种原因被撤销，这时T1已经修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，则T2读到的数据就是脏数据（不正确的数据）。第8页/共43页产生数据不一致的原因原因对并发事务的并发操作进行随机调度破坏了事务间的隔离性，引起了数据的不一致。并发控制的任务用正确的方式调度并发操作，使一

6、个用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性。并发控制的主要技术有封锁(Locking)：商用的DBMS一般都采用封锁方法时间戳(Timestamp)乐观控制法第9页/共43页2 封锁什么是封锁？封锁就是事务T在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务T对该数据对象就有了一定的控制，在事务T释放它的锁之前，其它事务不能更新此数据对象。封锁是实现并发控制的一个非常重要的技术。两种基本锁排它锁（Exclusive Locks,简称X锁）也称写锁，若事务T对数据对象A加上X锁，则事务T可以对A读和修改，其他任何事务都不能对A再加任何锁，直到T释放

7、A上的锁。共享锁（Share Locks,简称S锁）也称读锁，若事务T对数据对象A加上S锁，则事务T可以读A但不能修改，其他事务只能对A再加S锁，不能加X锁，直到T释放A上的S锁。第10页/共43页排它锁与共享锁的相容矩阵 X S -X N N Y S N Y Y -Y Y YT1T2第11页/共43页利用封锁解决丢失修改问题Xlock A获得读A=16 A=A-1写回A=15CommitUnlock AXlock A等待等待等待等待获得Xlock A读A=15A=A-1写回A=14CommitUnlock AT1T2（a）没有丢失修改事务T在修改数据之前，必须先对其加X锁，直到事务结束才释放

8、。第12页/共43页利用封锁解决读赃数据问题Xlock C读C=100读C=C*2写回C=200 Rollback（C恢复为100）Unlock CSlock C等待等待等待等待获得Slock C读C=100Commit CUnlock CT1T2（c）不读“脏”数据1、事务T在修改数据之前，必须先对其加X锁，直到事务结束才释放。2、事务T在读取数据R前必须先对其加S锁，读完后即可释放S锁。第13页/共43页利用封锁解决不可重复读问题Slock ASlock B读A=50读B=100求和=150读A=50读B=100求和=150CommitUnlock AUnlock BXlock B等待等待

9、等待等待等待等待等待获得Xlock B读B=100B=B*2写回B=200CommitUnlock BT1T2（b）可重复读1、事务T在修改数据之前，必须先对其加X锁，直到事务结束才释放。2、事务T在读取数据R前必须先对其加S锁，直到事务结束才释放S锁。第14页/共43页3 活锁和死锁T1T2T3T4T1T2Lock RLock R1Lock R2Lock R等待Lock RUnlock R等待等待Lock RLock R2等待Lock R等待等待等待等待等待等待Unlock R等待等待Lock R1等待Lock R等待等待等待等待等待（a）活锁（b）死锁第15页/共43页活锁活锁发生的情况如

10、果事务T1封锁了数据R，事务T2又请求封锁R，于是T2等待。事务T3也请求封锁R，当T1释放以后首先批准T3的请求，T2仍然等待。然后事务T4也请求封锁R，当T3释放以后首先批准T4的请求这样，T2可能永远等待。避免方法避免活锁的简单方法是采用先来先服务的策略。当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批准申请队列中第1个事务获得锁。第16页/共43页死锁死锁发生的情况如果事务T1封锁了数据R1，T2封锁了数据R2，然后T1又请求封锁R2，由于T2封锁了R2，故T1等待T2释放R2上的锁。接着T2又请求封锁R1，由于T1封锁了R1，故T

11、2等待T1释放R1上的锁。这样就出现了循环等待，结果两个事务都不可能结束。解决死锁问题的两种方法死锁预防提出一定措施来预防死锁的发生。死锁诊断与解除允许发生死锁，但采用一定手段定期诊断是否发生了死锁。若有，则立即解除。第17页/共43页死锁的预防产生死锁的原因两个或多个事务都已经封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。要预防死锁就必须破坏产生死锁的条件。两种常用的预防死锁的方法一次封锁法要求每个事务必须一次将所要使用的数据全部加锁，否则不能继续执行。优点：一次封锁法能够有效防止死锁的发生。缺点：降低了系统的并发度。顺序封锁法预先对数据对象规定一个封锁次

12、序，所有事务都按这个顺序实行封锁。特点：有效防止死锁的发生；封锁对象太多，维护成本高；事务的封锁请求是动态的，难以确定一个较好的顺序实行封锁。第18页/共43页死锁的诊断与解除死锁的诊断超时法如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。特点实现简单如果设置的等待时限太短，可能误判死锁。如果设置的等待时限太长，死锁发生后将不能及时发现。等待图法事务等待图一是个有向图G=(T,E)其中：T:顶点集合，每个顶点表示当前系统内正在运行的事务E:边的集合，每条边表示事务等待的情况。TiTj，指事务Ti等待事务Tj释放它所需要的数据项资源如果等待图中存在回路，表示系统中出现了死锁。死锁解除当

13、检测到系统中存在死锁时，必须设法解除。通常解除死锁的方法是选择一个处理死锁代价最小的事务，将其撤销，释放该事务所持有的所有锁，使其它事务得以继续进行下去。第19页/共43页T1T4T3T2无环等待图T1T4T3T2有环等待图第20页/共43页？问题对并发执行的事务，如何执行才能保证事务间的隔离性？保证事务执行的一致性？对并发事务如何调度才能获得正确的执行结果呢？第21页/共43页4 并发调度的可串行性概述如果一个事务运行过程中没有其它事务同时运行，那么就可以认为该事务的运行结果是正常的。因此将所有的事务串行起来调度的策略一定是正确的调度策略。虽然调度顺序不同得到的结果不同，但不会破坏数据库的一

14、致性状态。可串行化调度定义多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行执行时的结果相同。这种调度策略称为可串行化（Serializable）调度。正确调度准则可串行化是并发事务正确调度的准则。当且仅当一个并发调度是可串行化时才是正确调度。第22页/共43页并发调度示例事务的操作事务T1:读B;A=B+1;写回A事务T2:读A;B=A+1;写回B 假定A,B的初值为2。串行调度T1T2，执行结果：A=3，B=4T2T1，执行结果：B=3，A=4第23页/共43页T1T2T1T2T1T2T1T2Slock BSlock ASlock BSlock BY=R(B)=2X=R(A)=2Y

15、=R(B)=2Y=R(B)=2Unlock BUnlock ASlock AUnlock BXlock AXlock BX=R(A)=2Xlock AA=Y+1=3B=X+1=3Unlock BSlock AW(A)=3W(B)=3Unlock AA=Y+1=3等待Unlock AUnlock BXlock AW(A)=3等待Slock ASlock BA=Y+1=3Unlock A等待X=R(A)=3Y=R(B)=3W(A)=3X=R(A)=3Unlock AUnlock BXlock BUnlock AXlock BXlock AB=X+1=3Xlock BB=X+1=4A=Y+1=4W(

16、B)=3B=X+1=4W(B)=4W(A)=4Unlock AW(B)=4Unlock BUnlock AUnlock BUnlock B串行调度串行调度不可串行化调度可串行化调度第24页/共43页冲突可串行化调度冲突操作冲突操作是指不同的事务对同一个数据的读写操作和写写操作Ri(x)与Wj(x)/*事务Ti读x，Tj写x*/Wi(x)与Wj(x)/*事务Ti写x，Tj写x*/其他操作是不冲突操作不同事务的冲突操作和同一事务的两个操作不能交换(Swap)可串行化调度的充分条件一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到另一个调度Sc，如果Sc是串行的，称调

17、度Sc为冲突可串行化的调度。一个调度是冲突可串行化的，一定是可串行化的调度。冲突可串行化调度是可串行化调度的充分条件。第25页/共43页冲突可串行化调度实例如下调度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)交换处理把w2(A)与r1(B)w1(B)交换，得到：r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)再把r2(A)与r1(B)w1(B)交换：Sc2r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)Sc2等价于一个串行调度T1，T2，Sc1冲突可串行化的调度第26页/共43页不满足冲

18、突可串行化的可串行化调度充分非必要条件冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度。示例有3个事务：T1=W1(Y)W1(X)，T2=W2(Y)W2(X)，T3=W3(X)调度L1=W1(Y)W1(X)W2(Y)W2(X)W3(X)是一个串行调度。调度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不满足冲突可串行化。但是调度L2是可串行化的，因为L2执行的结果与调度L1相同，Y的值都等于T2的值，X的值都等于T3的值 第27页/共43页冲突可串行化的判定优先图设S是一个调度。构造一个优先图。（有向图）G=（V，E）,V事务顶点，E有

19、向边。若满足下列条件，则存在边TiTj在Tj执行read(Q)前，Ti执行write(Q);在Tj执行write(Q)前，Ti执行read(Q);在Tj执行write(Q)前，Ti执行write(Q);若存在TiTj，则表示在任何调度S中，Ti都必须出现在Tj之前。判断优先图存在环路非冲突可串行化；优先图无环路冲突可串行化。第28页/共43页实例T1T2Read(A)Write(A)Read(A)Write(A)Read(B)Write(B)Read(B)Write(B)T1T2第29页/共43页串行化顺序TiTmTjTkTmTiTjTkTmTiTkTjOR第30页/共43页5 两段锁协议封锁

20、协议在运用封锁方法时，对数据对象加锁时所约定的一些规则称封锁协议。封锁协议规定了何时申请封锁、持锁时间以及何时释放封锁等内容。不同的约定内容，形成了不同的封锁协议。两段锁协议是最常用的一种封锁协议。两段锁协议的概念所有的事务必须分两个阶段对数据项加锁和解锁。在任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁；在释放一个封锁之后，事务不再申请和获得任何其它封锁。“两段”的含义将事务分为两个阶段：扩展阶段和收缩阶段。扩展阶段：获得锁。事务可以申请获得任何数据项上的任何类型的锁，但不能释放任何锁。收缩阶段：释放锁。事务可以释放任何数据项上的任何类型的锁，但不能再申请任何锁。第31页/共43

21、页两段锁协议与可串行化事务T1遵守两段锁协议Slock A Slock B Xlock C Unlock B Unlock A Unlock C 扩展阶段 收缩阶段 事务T2不遵守两段锁协议Slock A Unlock A Slock B Xlock C Unlock C Unlock B两段锁协议与可串行化可以证明，若并发执行的所有事务均遵守两段锁协议，则对这些事务的任何并发调度策略都是可串行化的。事务遵守两段锁协议是可串行化调度的充分条件，但不是必要条件。也就是说：如果并发事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议。示例：T1和T2都不满足两段锁协议，但至少存在一个可串行化

22、的调度。第32页/共43页两段锁协议示例T1T2T1T2Slock BSlock BY=R(B)=2Y=R(B)=2Xlock AUnlock BSlock AXlock A等待Slock AA=Y+1=3等待等待W(A)=3等待A=Y+1=3等待Unlock B等待W(A)=3等待Unlock A等待Unlock A等待Slock ASlock AX=R(A)=3X=R(A)=3Xlock BUnlock AB=X+1=4Xlock BW(B)=4B=X+1=4Unlock BW(B)=4Unlock AUnlock B遵守两段锁协议可串行化调度不遵守两段锁协议可串行化调度第33页/共43页

23、两段锁协议与一次封锁法一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。因此，一次封锁法遵守两段锁协议。一次封锁法是预防死锁的一种方法，采用了一次封锁法，不会发生死锁；但是并发度不高。两段锁协议不要求事务必须一次将所有要使用的数据全部加锁，只是将其申请锁和释放锁分成两个阶段，所以遵守两段锁协议的事务不一定符合一次封锁条件，因而可能发生死锁。第34页/共43页遵守两段锁协议的事务发生死锁T1T2Slock BR(B)=2Slock AR(A)=2Xlock A等待等待Xlock B等待第35页/共43页6 封锁粒度封锁粒度(Granularity)封锁对象的大小称为封

24、锁粒度。两类封锁对象逻辑单元：如数据库中的元组、属性值、索引、关系、数据库物理单元：如页（数据页和索引页）、数据块等多粒度封锁一个系统同时提供多种封锁粒度供不同的事务选择，这种方法称多粒度封锁（Multiple Granularity Locking）。封锁粒度与并发度和系统开销的关系封锁的粒度越大，能够封锁的数据单元就越少，并发度就越小，系统开销也越小；封锁的粒度越小，并发度较高，但系统开销也就越大。选择封锁粒度时，应该考虑两个因素：封锁开销、并发度，适当选择封锁粒度以求的最优的效果。第36页/共43页多粒度封锁多粒度树多粒度树的根节点是整个数据库，表示最大的数据粒度。叶结点表示最小的数据粒

25、度。下图给出了一个三级粒度树的示例。数据库关系R1关系Rn元组元组元组元组三级粒度树第37页/共43页多粒度封锁协议多粒度封锁协议允许多粒度树中的每个节点被独立地加锁。对一个节点加锁意味着这个节点的所有后裔节点被加以同样类型的锁。因此，在多粒度封锁中一个数据对象可能以两种方式封锁，显式封锁和隐式封锁。显式封锁应事务的要求直接加到数据对象上的封锁。隐式封锁由于数据对象的上级节点加锁而使该数据对象加上的锁。锁冲突检查在多粒度封锁方法中，显式封锁和隐式封锁的效果是一样的，因此系统检查封锁冲突时，不仅要检查显式封锁，还要检查隐式封锁。一般地，对某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲

26、突；又要检查所有上级节点，看是否有该对象上的隐式封锁与之冲突；还要检查所有的下级节点，看是否有显式封锁与本事务将加到下级节点的隐式封锁冲突。这样检查的效率显然非常低。为此，人们引进了一种新型锁，称为意向锁。第38页/共43页意向锁概念如果对一个节点加意向锁，则说明该节点的下层节点正在被加锁；对任意节点加锁时，必须先对它的上层节点加意向锁。三种常用意向锁意向共享锁(Intent Share Lock,IS锁)：对一个数据对象加IS锁，表示它的后裔节点拟加S锁。意向排他锁(Intent Exclusive Lock,IX锁)：对一个数据对象加IX锁，表示它的后裔节点拟加X锁。共享意向排他锁(Sha

27、re Intent Exclusive Lock,SIX锁)：对一个数据对象加SIX锁，表示对它本身加S锁，再加IX锁。锁的强度指它对其它锁的排斥程度。一个事务在申请锁时以强锁代替弱锁是安全的。反之则不然。具有意向锁的多粒度封锁方法中任意事务T要对一个数据对象加锁，必须先对它的上层节点加意向锁。申请封锁时应该按自上而下的次序进行；释放封锁时则应该自下而上的次序进行。第39页/共43页SXISIXSIX-SYNYNNYXNNNNNYISYNYYYYIXNNYYNYSIXNNYNNY-YYYYYYT1数据封锁相容矩阵T2XSIXSIXIS锁强度的偏序关系数据锁的相容矩阵第40页/共43页多粒度封锁示例：事务T1要对关系R1加S锁要首先对数据库加IS锁检查数据库和R1是否已加了不相容的锁(X或IX)不再需要搜索和检查R1中的元组是否加了不相容的锁(X锁)作用提高了系统的并发度减少了加锁和解锁的开销第41页/共43页作业第4版P305：9、11、12、15第42页/共43页感谢您的观看！第43页/共43页