《上海交通大学高级数据库课件陆朝俊ed6ch15剖析》由会员分享，可在线阅读，更多相关《上海交通大学高级数据库课件陆朝俊ed6ch15剖析（54页珍藏版）》请在金锄头文库上搜索。
1、16.1 第15章 并发控制 n基于锁的协议 n死锁处理 n多粒度 n基于时间戳的协议 n基于有效性检查的协议 n多版本方案 n快照隔离 n插入,删除操作与谓词读 n实践中的弱一致性级别 16.2 基于锁的协议 n确保隔离性的一种方法: 以互斥的方式访问数据项, 即当一个事务正在访问数据 项Q时, 其他事务不能修改Q. n锁是最常用的实现互斥访问的方法: 事务只能访问它持有锁的数据项. n两种锁方式(mode): l共享(S)方式: 只能读数据项; l排它(X)方式: 数据项可读可写. n事务必须向并发控制管理器请求锁. 仅当事务被授予锁之后才能执行相应读写 操作. l数据项Q上的S-锁用 l
2、ock-S(Q)指令请求. l数据项Q上的X-锁用 lock-X(Q)指令请求. 16.3 基于锁的协议 (续) n锁相容性矩阵 n如果事务对Q的锁请求与其他事务在Q上已有的锁相容, 则可授予锁 l任意数目的事务可对同一数据持有S-锁 l若一事务对Q持有X-锁, 则其他事务不得持有Q上的任何锁. l不相容锁对应于冲突指令(ch.14) n若不能授予锁, 则发出请求的事务只能等待, 直至其他事务持有的所有不相容 锁被释放. l释放数据项Q上的锁用unlock(Q)指令 16.4 过早释放锁不能保证可串行化 T1 T2 并发控制管理器 lock-X(B) grant-X(B, T1) read(B
3、) B:=B-50 write(B) unlock(B) lock-S(A) grant-S(A, T2) read (A) unlock(A) lock-S(B) grant-S(B, T2) read (B) unlock(B) display(A+B) lock-X(A) grant-X(A, T1) read(A) A:=A+50 write(A) unlock(A) T2显示不一致的总额 ! 16.5 推迟释放锁 T3 T4 lock-X(B) lock-S(A) read(B) read (A) B:=B-50 lock-S(B) write(B) read (B) lock-X(
4、A) display(A+B) read(A) unlock(A) A:=A+50 unlock(B) write(A) unlock(B) unlock(A) T4不会显示不一致的总额 ! 16.6 死锁 n考虑调度 nT3 和T4 都不能继续 执行lock-S(B) 使T4 等待T3 释放它持有的B上的锁, 而执 行 lock-X(A) 使T3 等待T4 释放它持有的A上的锁. n这种情形称为死锁. l为处理死锁, T3 或T4 必须回滚并释放它持有的锁. 16.7 饿死 n如果并发控制管理器设计的不好还可能出现饿死. 例如: l一个事务可能在等待给数据项加X-锁, 同时一系列其他事务在请
5、 求并被授予同一数据项上的S-锁. l同一事务因死锁而被重复回滚. n并发控制管理器可设计成能够防止饿死: 当事务T请求lock-M(Q), 仅 当满足下列条件才授予 l没有事务在Q上持有与M不相容的锁; l没有比T先提出请求且正在等待Q上锁的事务 16.8 两阶段封锁协议 n要求每个事务分两个阶段来发出封锁与释放请求: l阶段1: 增长阶段 4事务可获得锁 4但不能释放锁 l阶段2: 收缩阶段 4事务可释放锁 4但不能获得新锁 n2PL协议确保冲突可串行化. l试证明: 各事务可按它们的lock point(即调度中各事务获得其最后 一个锁的地方)的次序串行化. 16.9 两阶段封锁协议 (
6、续) n两阶段锁不能确保避免死锁. n两阶段锁不能避免级联回滚. l严格(strict)两阶段封锁协议可避免级联回滚: 事务必须保持它的所 有排他锁直至提交/中止. 4所有未提交数据都不会被其他事务读取 n强(rigorous)两阶段封锁协议更加严格: 所有锁都必须保持 到事务提交/中止. l事务可按它们提交的次序串行化. 16.10 两阶段封锁协议 (续) n存在用两阶段封锁不能产生的冲突可串行化调度. n然而, 在没有关于事务的额外信息或对数据施加某种结构 或序的情况下, 两阶段封锁对冲突可串行化按如下意义是 必要的: 给定不遵守两阶段封锁的事务Ti, 总可以找到遵守两阶段封 锁的事务Tj
7、 使得存在Ti 与Tj 的非冲突可串行化调度. n在缺乏有关数据项被存取的方式的信息的情况下, 两阶段 封锁协议对确保冲突可串行化是充分必要的. 16.11 锁转换 n允许锁转换的两阶段封锁协议: 增长阶段: l可获得 lock-S l可获得 lock-X l可将 lock-S 转换为 lock-X (升级) 收缩阶段: l可释放 lock-S l可释放 lock-X l可将 lock-X 转换为 lock-S (降级) n本协议确保冲突可串行化. 16.12 锁转换调度例 16.13 封锁指令的自动生成 n事务Ti 发出标准的读/写操作, 无需使用显式的封锁调用. n对read(D) 的处理
8、如下: if Ti 在D上持有锁 then read(D) else begin lock-S(D); read(D) end 16.14 封锁指令的自动生成(续) n对write(D)的处理如下: if Ti 在D上有 lock-X then write(D) else if Ti 在D上有lock-S then upgrade(D); write(D) else lock-X(D); write(D) end; n所有锁在事务提交/中止之后释放 16.15 基于图的协议 n存在事务存取数据的额外信息时, 可以构造非两阶段封锁协议, 仍保持 冲突可串行化. n例如基于图的协议: 预先知道对数
9、据的处理次序 n在所有数据项的集合D = d1, d2 ,., dh 上施加一个偏序. l如果di dj 则同时存取di 和dj 的事务必须先存取di 后存取dj. l集合D可视为有向无圈图, 称为数据库图. n树协议是图协议的一种简单形式. 16.16 树协议 1.只允许排他锁. 2.Ti 的第一个锁可以加在任何数据项上. 其后, Ti 可对数据Q 加锁仅当Q的 父节点当前已被Ti 加锁. 3.数据项可在任意时刻释放锁. 4.已被Ti 封锁及释放过的数据项此后不能被Ti 再次封锁 16.17 树协议 (续) n树协议确保冲突可串行化且可避免死锁. n树协议中释放锁可比两阶段锁协议中更早发生.
10、 l较短等待时间, 增加并发度 l协议无死锁, 不需回滚 n缺点 l协议不能保证可恢复性或无级联回滚. 4保持排他锁到事务提交/中止. 4并发性更好的方法: 引入提交依赖. 仅确保可恢复性. l事务可能不得不对它不存取的数据项加锁. 4增加锁开销以及额外的等待时间 4潜在的并发度降低 4如果没有预先的使用数据的知识, 事务只好对根加锁 n树协议可产生两阶段锁协议不能产生的调度, 反之亦然. 16.18 死锁处理 n考虑下列两个事务: T1: write (X) T2: write(Y) write(Y) write(X) n带来死锁的调度 T1T2 lock-X on X write (X)
11、lock-X on Y write (X) 等待 lock-X on X 等待lock-X on Y 16.19 死锁处理 n如果有一个事务集合使得集合中的每个事务都在等待集合中的另一个 事务, 则系统死锁. n死锁处理的两类方法: 死锁预防vs死锁检测与恢复. l死锁预防协议确保系统永远不会进入死锁状态. l死锁检测与恢复协议允许死锁发生, 但能检测到并能从死锁恢复. n若系统死锁概率很高, 适合用死锁预防; 否则适合用死锁检测与恢复. 16.20 死锁预防策略 n两类预防方法: l确保不会发生循环等待的方法 4要求每个事务在开始执行之前为其所有数据项加锁. 缺点: 难以预测要用的数据; 数
12、据使用率低. 4在所有数据项上施加序, 并要求事务只能按序封锁数据项(如树协议). l利用抢占与回滚的方法: 使用事务时间戳来控制抢占与否. 4等待-死亡方案 非抢占式 老事务等待年轻事务释放数据项. 年轻事务永远不会等待老事务, 而是回滚( 死亡). 越老越可能等待;年轻事务可能在获得所需数据项之前死亡多次. 4伤害-等待方案 抢占式 老事务伤害 (强制回滚)年轻事务而不是等待它. 年轻事务等待老事务. 年轻事务可能比等待-死亡方案有较少的回滚. 4在上面两方案中, 回滚的事务重启动时带有原来的时间戳. 老事务因此 具有对新事务的优先级, 故避免了饿死. 16.21 基于超时的方案 n基于封
13、锁超时 l事务对一个锁只等待一个指定的时间量. 此后, 等待超时, 事务回滚. l因此即使发生死锁, 也会很快解开. l特点: 4实现简单; 适合短事务. 4可能有饿死. 4难以确定合适的超时间隔. 16.22 死锁检测 n死锁可用等待图描述, 即G = (V,E ), lV 是顶点集合 (即系统中的所有事务) lE 是边的集合; 其中每个元素是一有序对Ti Tj. n若Ti Tj 属于E, 则存在从Ti 到Tj 的有向边, 意味着Ti 等待Tj 释放数据 项. n当Ti 请求一个正被Tj 持有的数据项时, 边Ti Tj 被插入到等待图中. n当Tj 不再持有Ti 所需的数据项时, 这条边被删
14、除. n系统处于死锁状态当且仅当等待图包含圈. n死锁检测: 系统维护等待图信息, 并周期性地调用死锁检测算法来查找 等待图中的圈. l若死锁频繁, 则需更经常调用死锁检测算法; 16.23 死锁检测 (续) 无圈的等待图 有圈的等待图 16.24 死锁恢复 n当检测到死锁时: 某些事务必须回滚(作为牺牲品)来打破死锁. l选择导致最小代价的事务作为牺牲品. 4事务已计算多久, 还需计算多久; 4事务已使用多少数据, 还需使用多少; 4回滚将涉及多少事务. l回滚 决定事务回滚多远 4完全回滚: 中止事务并重启动. 4部分回滚: 只做为打破死锁所必需的回滚. l基于代价因子的系统中, 若同一事
15、务总是被选为牺牲品则发生了饿 死. 4在代价因子中包括回滚次数以避免饿死 16.25 多粒度 n同步单位: 单个数据项 vs 一组数据项 n允许数据项具有不同大小, 从而定义一个数据粒度层次, 其中细粒度嵌 在粗粒度中 n可图示为一棵树 (勿与树封锁协议混淆) n树中每个节点都可独立加锁. n当一事务对树中节点显式地加锁, 它也对该节点的所有后裔隐式地加了 同样方式的锁. n锁粒度 (封锁所在的树层次): l细粒度 (树中较低层): 高并发度, 高封锁开销 l粗粒度 (树中较高层): 低封锁开销, 低并发度 16.26 粒度层次例 从顶层开始的各个层次是: ldatabase larea lfile lrecord 16.27 意向锁方式 n多粒度情况下, 如何发现不同粒度数据上的锁冲突? n引入意向锁方式 l意向共享(IS): 表示在树的较低层有显式共享锁. l意向排他(IX): 表示在树的较低层有显式排他或共享锁 l共享及意向排他(SIX): 以该节点为根的子树加显式共享锁, 并且在 子树的某较低层加显式排他锁. n意向锁使得可对较高层节点按S或X方式加锁而无需检查其所有后裔节 点. 16.28 含意向锁方式的相容矩阵 n包括所有封锁方式的兼容性矩阵 IS
