数据库系统概念16并发控制.ppt

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

1、2数据库系统概念-并发控制08 一月 2023提纲提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理3数据库系统概念-并发控制08 一月 2023事务并发执行带来的问题事务并发执行带来的问题l可能会存取和存储不正确的数据，破坏事务的隔离性和数据库的一致性lDBMS必须提供并发控制机制l并发控制机制是衡量一个DBMS性能的重要标志之一4数据库系统概念-并发控制08 一月 2023并发控制概述并发控制概述l并发控制机制的任务对并发操作进行正确调度保证事务的隔离性保证数据库的一致性5数据库系统概念-并发控制08 一月 2023T1的修改被的修改被T2覆盖了！覆盖了！读读A=16AA-

2、3写回写回A=13读读A=16AA-1写回写回A=15事务事务T2事务事务T1数据不一致实例：飞机订票系统数据不一致实例：飞机订票系统6数据库系统概念-并发控制08 一月 2023并发操作带来的数据不一致性并发操作带来的数据不一致性l丢失修改（lost update）l不可重复读（non-repeatable read）l读“脏”数据（dirty read）7数据库系统概念-并发控制08 一月 2023丢失修改丢失修改丢失修改是指事务1与事务2从数据库中读入同一数据并修改事务2的提交结果破坏了事务1提交的结果，导致事务1的修改被丢失。8数据库系统概念-并发控制08 一月 2023丢失数据丢失数

3、据T1T2读读A=16AA-1写回写回A=15读读A=16AA-1写回写回A=159数据库系统概念-并发控制08 一月 2023不可重复读不可重复读不可重复读是指事务1读取数据后，事务2执行更新操作，使事务1无法再现前一次读取结果。10数据库系统概念-并发控制08 一月 2023不可重复读不可重复读读读B=100BB*2写回写回B=200读读A=50读读B=100求和求和=150读读A=50读读B=200求和求和=250(验算不对验算不对)T2T111数据库系统概念-并发控制08 一月 2023三类不可重复读三类不可重复读事务1读取某一数据后：1.事务2对其做了修改，当事务1再次读该数据时，得

4、到与前一次不同的值。2.事务2删除了其中部分记录，当事务1再次读取数据时，发现某些记录神密地消失了。3.事务2插入了一些记录，当事务1再次按相同条件读取数据时，发现多了一些记录。后两种不可重复读有时也称为幻影现象（phantom row）12数据库系统概念-并发控制08 一月 2023读读“脏脏”数据数据事务1修改某一数据，并将其写回磁盘事务2读取同一数据后事务1由于某种原因被撤消，这时事务1已修改过的数据恢复原值事务2读到的数据就与数据库中的数据不一致，是不正确的数据，又称为“脏”数据。13数据库系统概念-并发控制08 一月 2023读读“脏脏”数据数据读读C=200读读C=100CC*2写

5、回写回CROLLBACKC恢复为恢复为100T2T114数据库系统概念-并发控制08 一月 2023提纲提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理15数据库系统概念-并发控制08 一月 2023基于锁的协议基于锁的协议l确保可串行化的方法之一是要求对数据项的访问以互斥的方式进行l封锁就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁l加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。l封锁是实现并发控制的一个非常重要的技术16数据库系统概念-并发控制08 一月 2023锁锁lDBMS通常提供了多

6、种类型的封锁。一个事务对某个数据对象加锁后究竟拥有什么样的控制是由封锁的类型决定的。l基本封锁类型排它锁（eXclusive lock，简记为X锁）共享锁（Share lock，简记为S锁）17数据库系统概念-并发控制08 一月 2023共享锁共享锁l共享锁又称为读锁l若事务T对数据对象Q加上S锁，事务T可读但不能写Q，其它事务只能再对Q加S锁，而不能加X锁，直到T释放Q上的S锁18数据库系统概念-并发控制08 一月 2023排它锁排它锁l排它锁又称为写锁l若事务T对数据对象Q加上X锁，则事务T既可以读又可以写Q，其它任何事务都不能再对Q加任何类型的锁，直到T释放Q上的锁19数据库系统概念-并

7、发控制08 一月 2023锁的相容矩阵锁的相容矩阵Y=Yes，相容的请求，相容的请求N=No，不相容的请求，不相容的请求T1T2XS-XNNYSNYY-YYY20数据库系统概念-并发控制08 一月 2023锁锁21数据库系统概念-并发控制08 一月 2023锁锁22数据库系统概念-并发控制08 一月 2023锁锁A=100￥B=200￥A=100￥B=150￥A=100￥B=150￥A=150￥B=150￥23数据库系统概念-并发控制08 一月 2023锁锁在适当的调度下，上一页中出现的显示不正确的现象将不再存在24数据库系统概念-并发控制08 一月 2023死锁死锁25数据库系统概念-并发控

8、制08 一月 2023封锁协议封锁协议l在运用X锁和S锁对数据对象加锁时，需要约定一些规则：封锁协议（Locking Protocol）何时申请X锁或S锁持锁时间、何时释放l 不同的封锁协议，在不同的程度上为并发操 作的正确调度提供一定的保证26数据库系统概念-并发控制08 一月 2023活锁（饿死）活锁（饿死）27数据库系统概念-并发控制08 一月 2023避免饿死避免饿死l当事务Ti申请对数据项Q加M型锁时：-不存在数据项Q上持有与M型锁冲突的锁的其他事务 -不存在等待对数据项Q加锁且先于Ti申请加锁的事务28数据库系统概念-并发控制08 一月 2023两阶段封锁协议两阶段封锁协议l保证可

9、串行性的封锁协议l每个事务分两个阶段提出加锁和解锁申请 -增长阶段：事务可以获得锁，但不能释放锁 -缩减阶段：事务可以释放锁，但不能获得新锁29数据库系统概念-并发控制08 一月 2023两阶段封锁协议两阶段封锁协议l并行执行的所有事务均遵守两段锁协议，则对这些事务的所有并行调度策略都是可串行化的。所有遵守两段锁协议的事务，其并行执行的结果一定是正确的l事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件l可串行化的调度中，不一定所有事务都必须符合两段锁协议。30数据库系统概念-并发控制08 一月 2023两阶段封锁协议两阶段封锁协议T1Lock-SB读读B=2Lock-XAA=B+1写

10、回写回A=3UnlockBUnlockAT2Lock-SA等待等待等待等待等待等待等待等待等待等待Lock-SA读读A=3Lock-XBB=A+1写回写回B=4UnlockBUnlockAT1Lock-SB读读B=2Y=BUnlockBLock-XAA=Y+1写回写回A=3UnlockAT2Lock-SA等待等待等待等待等待等待等待等待Lock-SA读读A=3X=AUnlockALock-XBB=X+1写回写回B=4UnlockB(a)遵守两段锁协议遵守两段锁协议(b)不遵守两段锁协议不遵守两段锁协议T1Lock-SB读读B=2UnlockBLock-XAA=B+1写回写回A=3UnlockA

11、T2Lock-SA读读A=2UnlockALock-XB等待等待XlockBB=A+1写回写回B=3UnlockB(c)不遵守两段锁协议不遵守两段锁协议31数据库系统概念-并发控制08 一月 2023两阶段封锁协议两阶段封锁协议l两阶段封锁协议不保证不会发生死锁32数据库系统概念-并发控制08 一月 2023两阶段封锁协议两阶段封锁协议l两阶段封锁协议下，级联回滚可能发生33数据库系统概念-并发控制08 一月 2023严格两阶段封锁协议严格两阶段封锁协议l严格两阶段封锁协议除了要求封锁是两阶段之外，还要求事务持有的所有排他锁必须在事务结束后，方可释放。34数据库系统概念-并发控制08 一月 2

12、023强两阶段封锁协议强两阶段封锁协议l事务提交之前，不得释放任何锁l在强两阶段封锁协议下，事务可以按其结束的顺序串行化35数据库系统概念-并发控制08 一月 2023锁转换锁转换lUpgrade：从共享锁提升为排他锁lDowngrade：从排他锁降级为共享锁l锁升级只能发生在增长阶段，锁降级只能发生在缩减阶段36数据库系统概念-并发控制08 一月 2023基于图的协议基于图的协议l树形协议中，可用的加锁指令只有lock-X。每个事务Ti对一个数据项最多只能加一次锁，并且遵循以下规则：-Ti首次加锁可以对任何数据项进行 -此后，Ti对数据项Q加锁的前提是Ti持有Q的父项上的锁 -对数据项的解锁

13、可以随时进行 -数据项被Ti加锁并解锁后，Ti不能再对该数据项加锁37数据库系统概念-并发控制08 一月 2023提纲提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理38数据库系统概念-并发控制08 一月 2023基于时间戳的协议基于时间戳的协议l另一种解决事务可串行化的次序的方法是事先选定事务的次序39数据库系统概念-并发控制08 一月 2023时间戳时间戳l对于系统中的每一个事务Ti，将唯一的时间戳与它相联系，记为TS(Ti)。l时间戳的两种简单方法：-系统时钟 -逻辑计数器事务的时间戳决定了串行化顺序40数据库系统概念-并发控制08 一月 2023数据项时间戳数据项时间

14、戳lW-timestamp(Q)：表示成功执行write(Q)的所有事务的最大的时间戳lR-timestamp(Q)：表示成功执行read(Q)的所有事务的最大的时间戳41数据库系统概念-并发控制08 一月 2023时间戳排序协议时间戳排序协议l保证任何有冲突的read或write操作按照时间戳顺序执行l1、假设事务Ti发出read(Q)-如果TS(Ti)=W-timestamp(Q)，则执行read操作，R-timestamp(Q)被设为R-timestamp(Q)和TS(Ti)两者的最大值42数据库系统概念-并发控制08 一月 2023时间戳排序协议时间戳排序协议l2、假设事务Ti发出wr

15、ite(Q)-如果TS(Ti)R-timestamp(Q)，则Ti产生的Q值是先前所需要的值，且系统已假定该值不会被产生。因此，write操作被拒绝，Ti回滚 -如果TS(Ti)W-timestamp(Q)，则Ti试图写入的Q值已过时。因此，write操作被拒绝，Ti回滚 -否则，执行write操作，将W-timestamp(Q)设为TS(Ti)43数据库系统概念-并发控制08 一月 2023时间戳排序协议时间戳排序协议44数据库系统概念-并发控制08 一月 2023时间戳排序协议时间戳排序协议l调度可恢复方法：-所有的写操作都在事务末尾执行，在写操作正在执行时，任何事务都不允许访问已写好的任

16、何数据项 -对未提交数据项的读操作，被推迟到更新该数据项的事务提交之后 -事务Ti读取了其他事务所写的数据，只有在其他事务提交之后，Ti才能提交45数据库系统概念-并发控制08 一月 2023Thomas写规则写规则T16将因为将因为write(Q)write(Q)而回滚而回滚46数据库系统概念-并发控制08 一月 2023Thomas写规则写规则l假如事务Ti发出write(Q)-如果TS(Ti)R-timestamp(Q)，则Ti产生的Q值是先前所需要的值，且系统已假定该值不会被产生，因此，write操作被拒绝，Ti回滚。-如果TS(Ti)W-timestamp(Q)，则T1试图写入的值已

17、过时，因此，忽略这个写操作 -否则，执行write操作，将W-timestamp(Q)设为TS（Ti）47数据库系统概念-并发控制08 一月 2023提纲提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理48数据库系统概念-并发控制08 一月 2023多粒度多粒度l意向锁：如果一个节点加上了意向锁，则意味着要在树的较低层进行显示加锁l共享意向锁/排他意向锁/共享排他意向锁49数据库系统概念-并发控制08 一月 2023多粒度封锁协议多粒度封锁协议l遵从图16-17的锁相容函数l根结点必须首先加锁，可以加任何类型的锁l仅当Ti对Q的父结点持有IX或IS锁时，Ti对于结点Q加S或者

18、Is锁l仅当Ti对Q的父结点持有IX或SIX锁时，Ti对于结点Q加X、SIX、IX锁l仅当Ti未曾对任何结点解锁时，Ti可以对结点加锁l仅当Ti当前不持有Q的子节点的锁时，Ti可以对节点Q解锁50数据库系统概念-并发控制08 一月 2023提纲提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理51数据库系统概念-并发控制08 一月 2023多版本机制多版本机制l多版本时间戳排序 -对于每个数据项Q，有一个版本序列，每个版本Qi包括三部分内容：Content：版本Qi的值；W-timestamp(Qi)：创建版本Qi的事务的时间戳 R-timestamp(Qi)：所有成功读取Qi

19、版本的事务的最大的时间戳52数据库系统概念-并发控制08 一月 2023多版本机制多版本机制l多版本时间戳排序机制：假设事务Ti发出read(Q)或者write(Q)操作，令Qk表示Q的版本，它具有小于或等于TS(Ti)的最大的写时间戳 -如果事务发出read(Q)，则返回版本Qk的内容 -如果事务Ti发出write(Q)，且TS（Ti）R-timestamp(Qk)，则系统回滚Ti；若TS(Ti)=W-timestamp(Qk)，则系统覆盖Qk的内容；否则创建一个Q的新版本53数据库系统概念-并发控制08 一月 2023多版本机制多版本机制l多版本两阶段封锁：希望将多版本并发控制的优点与两阶

20、段封锁的优点结合起来。54数据库系统概念-并发控制08 一月 2023提纲提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理55数据库系统概念-并发控制08 一月 2023死锁处理死锁处理两类方法1.预防死锁2.死锁的诊断与解除56数据库系统概念-并发控制08 一月 2023死锁预防死锁预防l产生死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。l预防死锁的发生就是要破坏产生死锁的条件57数据库系统概念-并发控制08 一月 2023死锁预防死锁预防预防死锁的方法l 一次封锁法和顺序封锁法l抢占与事务回滚58数据库系统

21、概念-并发控制08 一月 2023一次封锁法一次封锁法l要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行l一次封锁法存在的问题：降低并发度 扩大封锁范围将以后要用到的全部数据加锁，势必扩大了封锁的范围，从而降低了系统的并发度59数据库系统概念-并发控制08 一月 2023一次封锁法一次封锁法l难于事先精确确定封锁对象数据库中数据是不断变化的，原来不要求封锁的数据，在执行过程中可能会变成封锁对象，所以很难事先精确地确定每个事务所要封锁的数据对象解决方法：将事务在执行过程中可能要封锁的数据对象全部加锁，这就进一步降低了并发度。60数据库系统概念-并发控制08 一月 2023顺序封

22、锁法顺序封锁法l顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。l顺序封锁法存在的问题 维护成本高数据库系统中可封锁的数据对象极其众多，并且随数据的插入、删除等操作而不断地变化，要维护这样极多而且变化的资源的封锁顺序非常困难，成本很高61数据库系统概念-并发控制08 一月 2023顺序封锁法顺序封锁法难于实现事务的封锁请求可以随着事务的执行而动态地决定，很难事先确定每一个事务要封锁哪些对象，因此也就很难按规定的顺序去施加封锁。例：规定数据对象的封锁顺序为A,B,C,D,E。事务T3起初要求封锁数据对象B,C,E，但当它封锁了B,C后，才发现还需要封锁A，这样就破坏了封

23、锁顺序.62数据库系统概念-并发控制08 一月 2023抢占与事务回滚抢占与事务回滚lWait-die：当事务Ti申请的数据项当前被事务Tj持有时，仅当Ti的时间戳小于Tj的时间戳时，允许Ti等待，否则Ti回滚lWound-die：当事务Ti申请的数据项当前被事务Tj持有时，仅当Ti的时间戳大于Tj的时间戳时，允许Ti等待，否则Ti回滚63数据库系统概念-并发控制08 一月 2023死锁的预防死锁的预防l结论在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点DBMS在解决死锁的问题上更普遍采用的是诊断并解除死锁的方法64数据库系统概念-并发控制08 一月 2023死锁检测死锁检测l允许

24、死锁发生l解除死锁由DBMS的并发控制子系统定期检测系统中是否存在死锁一旦检测到死锁，就要设法解除65数据库系统概念-并发控制08 一月 2023检测死锁：检测死锁：超时法超时法l如果一个事务的等待时间超过了规定的时限，就认为发生了死锁l优点：实现简单l缺点有可能误判死锁时限若设置得太长，死锁发生后不能及时发现66数据库系统概念-并发控制08 一月 2023等待图法等待图法l用事务等待图动态反映所有事务的等待情况事务等待图是一个有向图G=(V，E)V为结点的集合，每个结点表示正运行的事务E为边的集合，每条边表示事务等待的情况若T1等待T2，则T1，T2之间划一条有向边，从T1指向T2l并发控制

25、子系统周期性地（比如每隔1 min）检测事务等待图，如果发现图中存在回路，则表示系统中出现了死锁。67数据库系统概念-并发控制08 一月 2023从死锁中恢复从死锁中恢复l解除死锁选择一个处理死锁代价最小的事务，将其撤消，释放此事务持有的所有的锁，使其它事务能继续运行下去。68数据库系统概念-并发控制08 一月 2023小结小结l数据共享与数据一致性是一对矛盾l数据库的价值在很大程度上取决于它所能提供的数据共享度。l数据共享在很大程度上取决于系统允许对数据并发操作的程度。l数据并发程度又取决于数据库中的并发控制机制l另一方面，数据的一致性也取决于并发控制的程度。施加的并发控制愈多，数据的一致性往往愈好。69数据库系统概念-并发控制08 一月 2023小结小结l数据库的并发控制以事务为单位l数据库的并发控制通常使用封锁机制两类最常用的封锁70数据库系统概念-并发控制08 一月 2023小结小结l并发控制机制调度并发事务操作是否正确的判别准则是可串行性并发操作的正确性则通常由两段锁协议来保证。两段锁协议是可串行化调度的充分条件，但不是必要条件71数据库系统概念-并发控制08 一月 2023小结小结l对数据对象施加封锁，带来问题l活锁：先来先服务l 死锁：预防方法l一次封锁法顺序封锁法l抢占与回滚 死锁的诊断与解除l超时法l等待图法