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

《数据库系统概念16并发控制》由会员分享，可在线阅读，更多相关《数据库系统概念16并发控制（71页珍藏版）》请在金锄头文库上搜索。

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

2、并发控制*并发操作带来的数据不一致性l丢失修改（lost update）l不可重复读（non-repeatable read）l读“脏”数据（dirty read）7数据库系统概念-并发控制*丢失修改丢失修改是指事务1与事务2从数据库中读入同一数据并修改事务2的提交结果破坏了事务1提交的结果，导致事务1的修改被丢失。8数据库系统概念-并发控制*丢失数据T1T2 读A=16 AA-1写回 A=15读A=16AA-1 写回A=159数据库系统概念-并发控制*不可重复读不可重复读是指事务1读取数据后，事务2执行更新操作，使事务1无法再现前一次读取结果。10数据库系统概念-并发控制*不可重复读读B=1

3、00BB*2 写回B=200 读A=50读B=100求和=150 读A=50读B=200求和=250(验算不对) T2T111数据库系统概念-并发控制*三类不可重复读事务1读取某一数据后： 1.事务2对其做了修改，当事务1再次读该数据 时，得到与前一次不同的值。2. 事务2删除了其中部分记录，当事务1再次读 取数据时，发现某些记录神密地消失了。 3. 事务2插入了一些记录，当事务1再次按相同 条件读取数据时，发现多了一些记录。 后两种不可重复读有时也称为幻影现象（phantom row ）12数据库系统概念-并发控制*读“脏”数据事务1修改某一数据，并将其写回磁盘事务2读取同一数据后事务1由于

4、某种原因被撤消，这时事务1已修改过的数据恢复原值事务2读到的数据就与数据库中的数据不一致，是不正确的数据，又称为“脏”数据。13数据库系统概念-并发控制*读“脏”数据读C=200 读C=100CC*2写回C ROLLBACKC恢复为100T2T114数据库系统概念-并发控制*提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理15数据库系统概念-并发控制*基于锁的协议l确保可串行化的方法之一是要求对数据项的访问以互斥的方式进行l封锁就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁l加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其

5、它的事务不能更新此数据对象。l封锁是实现并发控制的一个非常重要的技术16数据库系统概念-并发控制*锁lDBMS通常提供了多种类型的封锁。一个事务对某个 数据对象加锁后究竟拥有什么样的控制是由封锁的类 型决定的。l基本封锁类型 排它锁（eXclusive lock，简记为X锁） 共享锁（Share lock，简记为S锁）17数据库系统概念-并发控制*共享锁l共享锁又称为读锁l若事务T对数据对象Q加上S锁，事务T可读但 不能写Q，其它事务只能再对Q加S锁，而不能 加X锁，直到T释放Q上的S锁18数据库系统概念-并发控制*排它锁l排它锁又称为写锁l若事务T对数据对象Q加上X锁，则事务T既可 以读又可

6、以写Q，其它任何事务都不能再对Q加 任何类型的锁，直到T释放Q上的锁19数据库系统概念-并发控制*锁的相容矩阵Y=Yes，相容的请求 N=No，不相容的请求T1 T2XS-XNNYSNYY-YYY20数据库系统概念-并发控制*锁21数据库系统概念-并发控制*锁22数据库系统概念-并发控制*锁A=100￥ B=200￥A=100￥ B=150￥A=100￥ B=150￥A=150￥ B=150￥23数据库系统概念-并发控制*锁在适当的调度下，上一页中出 现的显示不正确的现象将不再 存在24数据库系统概念-并发控制*死锁25数据库系统概念-并发控制*封锁协议l在运用X锁和S锁对数据对象加锁时，需要

7、约定一些规则：封锁协议（Locking Protocol） 何时申请X锁或S锁持锁时间、何时释放l 不同的封锁协议，在不同的程度上为并发操作的正确调度提供一定的保证26数据库系统概念-并发控制*活锁（饿死）27数据库系统概念-并发控制*避免饿死l当事务Ti申请对数据项Q加M型锁时：-不存在数据项Q上持有与M型锁冲突的锁 的其他事务-不存在等待对数据项Q加锁且先于Ti申请 加锁的事务28数据库系统概念-并发控制*两阶段封锁协议l保证可串行性的封锁协议l每个事务分两个阶段提出加锁和解锁申请-增长阶段：事务可以获得锁，但不能释放 锁-缩减阶段：事务可以释放锁，但不能获得 新锁29数据库系统概念-并发

8、控制*两阶段封锁协议l并行执行的所有事务均遵守两段锁协议，则对这 些事务的所有并行调度策略都是可串行化的。所有遵守两段锁协议的事务，其并行执行的结果 一定是正确的l事务遵守两段锁协议是可串行化调度的充分条件 ，而不是必要条件l可串行化的调度中，不一定所有事务都必须符合 两段锁协议。30数据库系统概念-并发控制*两阶段封锁协议T1 Lock-S B 读B=2 Lock-X AA=B+1 写回A=3 Unlock B Unlock AT2Lock-S A等待等待等待等待等待 Lock-S A 读A=3Lock-X B B=A+1 写回B=4 Unlock B Unlock A T1 Lock-S

9、B 读B=2 Y=B Unlock B Lock-X AA=Y+1 写回A=3 Unlock AT2Lock-S A 等待 等待 等待 等待 Lock-S A 读A=3 X=A Unlock A Lock-X B B=X+1 写回B=4 Unlock B (a) 遵守两段锁协议 (b) 不遵守两段锁协议 T1Lock-S B 读B=2 Unlock BLock-X A A=B+1 写回A=3 Unlock AT2Lock-S A 读A=2Unlock ALock-X B 等待 Xlock B B=A+1 写回B=3 Unlock B (c) 不遵守两段锁协议 31数据库系统概念-并发控制*两阶

10、段封锁协议l两阶段封锁协议不保证不会发生死锁32数据库系统概念-并发控制*两阶段封锁协议l两阶段封锁协议下，级联回滚可能发生33数据库系统概念-并发控制*严格两阶段封锁协议l严格两阶段封锁协议除了要求封锁是两阶段 之外，还要求事务持有的所有排他锁必须在 事务结束后，方可释放。34数据库系统概念-并发控制*强两阶段封锁协议l事务提交之前，不得释放任何锁l在强两阶段封锁协议下，事务可以按其结束 的顺序串行化35数据库系统概念-并发控制*锁转换lUpgrade：从共享锁提升为排他锁lDowngrade：从排他锁降级为共享锁l锁升级只能发生在增长阶段，锁降级只能发 生在缩减阶段36数据库系统概念-并发

11、控制*基于图的协议l树形协议中，可用的加锁指令只有lock-X。 每个事务Ti对一个数据项最多只能加一次锁 ，并且遵循以下规则：- Ti首次加锁可以对任何数据项进行-此后， Ti对数据项Q加锁的前提是Ti持有 Q的父项上的锁-对数据项的解锁可以随时进行-数据项被Ti加锁并解锁后， Ti不能再对该 数据项加锁37数据库系统概念-并发控制*提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理38数据库系统概念-并发控制*基于时间戳的协议l另一种解决事务可串行化的次序的方法是事 先选定事务的次序39数据库系统概念-并发控制*时间戳l对于系统中的每一个事务Ti，将唯一的时间 戳与它相联系

12、，记为TS(Ti)。l时间戳的两种简单方法：-系统时钟-逻辑计数器 事务的时间戳决定了串行化顺序40数据库系统概念-并发控制*数据项时间戳lW-timestamp(Q)：表示成功执行write(Q)的 所有事务的最大的时间戳lR- timestamp(Q)：表示成功执行read(Q)的 所有事务的最大的时间戳41数据库系统概念-并发控制*时间戳排序协议l保证任何有冲突的read或write操作按照时 间戳顺序执行l1、假设事务Ti发出read(Q)-如果TS(Ti)= W-timestamp(Q)，则执行 read操作，R-timestamp(Q)被设为R- timestamp(Q)和TS(T

13、i)两者的最大值42数据库系统概念-并发控制*时间戳排序协议l2、假设事务Ti发出write(Q)-如果TS(Ti)，每个版本Qi包括三部分内容 ：Content：版本Qi的值；W-timestamp(Qi)：创建版本Qi的事务的时 间戳R-timestamp(Qi)：所有成功读取Qi版本的 事务的最大的时间戳52数据库系统概念-并发控制*多版本机制l多版本时间戳排序机制：假设事务Ti发出 read(Q)或者write(Q)操作，令Qk表示Q的版 本，它具有小于或等于TS(Ti)的最大的写时 间戳-如果事务发出read(Q)，则返回版本Qk的 内容-如果事务Ti发出write(Q)，且TS（T

14、i） R- timestamp(Qk)，则系统回滚Ti；若TS(Ti)= W-timestamp(Qk)，则系统覆盖Qk的内容； 否则创建一个Q的新版本53数据库系统概念-并发控制*多版本机制l多版本两阶段封锁：希望将多版本并发控制 的优点与两阶段封锁的优点结合起来。54数据库系统概念-并发控制*提纲l并发控制概述l封锁l时间戳l封锁的粒度l多版本机制l死锁处理55数据库系统概念-并发控制*死锁处理两类方法1. 预防死锁2. 死锁的诊断与解除56数据库系统概念-并发控制*死锁预防l产生死锁的原因是两个或多个事务都已封锁 了一些数据对象，然后又都请求对已为其他 事务封锁的数据对象加锁，从而出现死

15、等待 。l预防死锁的发生就是要破坏产生死锁的条件57数据库系统概念-并发控制*死锁预防预防死锁的方法l 一次封锁法和顺序封锁法l抢占与事务回滚58数据库系统概念-并发控制*一次封锁法l要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行l一次封锁法存在的问题：降低并发度 扩大封锁范围 将以后要用到的全部数据加锁，势必扩大了封锁的范围，从而降低了系统的并发度59数据库系统概念-并发控制*一次封锁法l难于事先精确确定封锁对象 数据库中数据是不断变化的，原来不要求封 锁的数据，在执行过程中可能会变成封锁对 象，所以很难事先精确地确定每个事务所要 封锁的数据对象 解决方法：将事务在执行过程中可能要封锁 的数据对象全部加锁，这就进一步降低了并 发度。60数据库系统概念-并发控制*顺序封锁法l顺序封锁法是预先对数据对象规定一个封锁顺序 ，所有事务都按这个顺序实行封锁。l顺序封锁法存在的问题 维护成本高 数据库系统中可封锁的数据对象极其众多， 并且随数据的插入、删除等操作而不断地变 化，要维护这样极多而且变化的资源的封锁 顺序非常困难，成本很高61数据库系统概念-并发控制*顺序封锁法 难于实现 事务的封锁请求可以随着事务的执行而动态地 决定，很难事先确定每一个事务要封锁哪些对 象，因此也就很难按规定的顺序去施加封锁。例：规定数据对象的封锁顺序为A,B,C,D,E。事务T3起 初