2015 第九篇并发控制技术.ppt

* * * * 基于封锁和基于时标两种并发控制比较 空间 成熟度 特点 封锁 小 成熟 推迟事务 时标 大 不成熟 回滚事务 提高系统吞吐量 提高CPU和磁盘的利用率 减少事务的平均响应时间 总 结 并发控制的优点 并发执行可能产生的问题 基于锁的并发控制 封锁协议 饥饿、活锁：预防 死锁 丢失修改 不可重复读 读脏数据 一级封锁协议 二级封锁协议 三级封锁协议 一次封锁法 顺序封锁法 基于时标法 预防 检测 恢复 超时法 等待图法 撤销代价最小的事务 Rollback的代价最小 避免出现饥饿现象 封锁概念 封锁类型 锁升级 多粒度锁 事务的概念 ACID特性(原子性、一致性、隔离性、持久性) 总 结 可串行化调度 基于 时标 并发 控制 级联撤销问题 严格的两阶段封锁协议 加强的两阶段封锁协议 两段 封锁 协议 基本的两阶段封锁协议 * * * * * * * * * * * * * * * * * * * * * * * * * * * * 死锁的预防 基于时标的死锁预防技术 无论是等待-死亡，还是受伤-等待, 回滚( rollback)的事务重启动时 保留其原来的时标(timestamp) 年长的事务(Older transactions) 优先新的事务，可以避免饥饿现象. 封锁与时标的区别 事务 T4 T2 T3 T1 T5 T7 T6 封锁协议 用于管理被访问的数据对象资源 时标 用于管理访问资源的事务 死锁的预防 数据对象 死锁的检测/诊断与恢复 死锁的诊断和恢复 DBMS常用方法, 有超时法和事务等待图法 超时法: 如果一个事务等待的时间超过了规定的时间, 就认为发生了死锁 缺点: 可能误诊, 规定时间不好设 优点: 简单 死锁的检测/诊断与恢复 等待图法: 是一有向图G=(T, U). 节点表示正在执行的事务, 边表示等待情况。 死锁诊断: 如果图中存在回路, 系统中发生死锁 T2等待T3 T2→T3 T3等待T1 T3→T1 T1 T2 T3 例如: T1等待T2 T1→T2 存在回路! 如何恢复死锁 ？ 死锁 死锁的检测/诊断与恢复 死锁恢复 因素1：选择一个处理死锁代价最小的事务, 将其撤销, 释放锁 该事务计算的时间、使用多少数据项、完成事务还需多少数据项、撤销该事务需要牵涉多少其他事务 死锁的检测/诊断与恢复 死锁恢复 因素2：决定rollback多远 彻底撤销，或 rollback到可以解决死锁为止 死锁的检测/诊断与恢复 死锁恢复 因素3：避免饥饿 避免由于某个事务rollback的代价最小，而总是rollback该事务。 常用的方法：在代价因素中包括rollback的次数 可串行化调度 T1 T2 1：Xlock A Read(A) A=A-50 Write(A) Unlock A 2： 3：Xlock B Read(B) B=B+50 Write(B) Unlock B 4： Xlock A Read(A) A=A*2 Write(A) Unlock A Xlock B Read(B) B=B*2 Write(B) Unlock B 哪个结果正确？ 假设：A=B=100 T1 T2 Xlock A Read(A) A=A*2 Write(A) Unlock A Xlock B Read(B) B=B*2 Write(B) Unlock B 1：Xlock A Read(A) A=A-50 Write(A) Unlock A 2： 3：Xlock B Read(B) B=B+50 Write(B) Unlock B 结果： A=100 B=300 结果： A=100 B=250 A=50 A=100 B=150 B=300 A=50 A=100 B=200 B=250 可串行化调度 对并发事务的调度是随机的 ?结果可能不同 ？哪个结果是正确的 合法的数据库状态 串行的事务 事务的串行执行: ?正确的结果 ?合法的数据库状态 串行执行一定是正确的 T1 T2 1：Xlock A Read(A) A=A-50 Write(A) Unloc