数据库课件08-第八章并发控制-new幻灯片.ppt

死锁的检测/诊断与恢复 等待图法: 是一有向图G=(T, U). 节点表示正在执行的事务, 边表示等待情况。T1?T2: T1等待T2 死锁诊断: 如果图中存在回路, 系统中发生死锁 T2等待T3 T2→T3 T3等待T1 T3→T1 T1 T2 T3 若 T1等待T2 T1→T2 死锁的检测/诊断与恢复 死锁恢复 选择一个处理死锁代价最小的事务, 将其撤销, 释放锁 该事务计算的时间、使用多少数据项、完成事务还需多少数据项、撤销该事务需要牵涉多少其他事务 决定rollback多远 彻底撤销，或 rollback到可以解决死锁为止 避免饥饿 避免由于某个事务rollback的代价最小，而总是rollback该事务。 常用的方法：在代价因素中包括rollback的次数 并发调度的可串行性 对并发事务的调度是随机的 ?结果可能不同 ？哪个结果是正确的 合法的数据库状态?正确的结果 串行的事务?合法的数据库状态 事务的串行执行: 串行执行一定是正确的 并发事务的不同调度 T1 T2 T1 T2 T1 T2 Slock B Y=B=2 Unlock B Xlock A A=Y+1 写回A=3 Unlock A Slock A X=A=3 Unlock A Xlock B B =X+1 写回B=4 Unlock B Slock B Y=B=2 Unlock B Xlock A A=Y+1 写回A=3 Unlock A Slock A X=A=2 Unlock A Xlock B B =X+1 写回B=3 Unlock B 不可串行化调度 可串行化调度 Slock B Y=B=2 Unlock B Xlock A A=Y+1 写回A=3 Unlock A Slock A 等待 等待 等待 X=A=3 Unlock A Xlock B B =X+1 写回B=4 Unlock B 串行化调度 设初始值A=2, B=2 并发调度的可串行性 可串行化: 多个事务的并发执行是串行的, 当且仅当其结果和这些事务的某一次串行执行的结果相同的 可串行性: 是并发事务正确性准则 正确调度: 给定的一个并发调度, 当且仅当它是可串行化的, 才认为是正确的 确保并发事务执行可串行化的方法: 2PL, 时间戳等 2 Phase Lock 两阶段封锁协议 两阶段封锁协议: 所有事务必须分两个阶段对所要存取的数据项加锁和解锁 （Eswaran等人1976年提出的） 在对任何数据进行读写操作之前, 首先申请并获得对该数据项的封锁 在释放一个封锁之后, 事务不再申请和获得任何其他的封锁 可以证明, 若并发执行的所有事务都遵循两段封锁协议, 则对这些事务的任何并发调度策略都是正确的 事务遵守两段封锁协议是可串行化调度的充分条件 遵守两段封锁协议的事务可能发生死锁, 与防止死锁的一次封锁法不同 两阶段封锁协议 阶段1：加锁阶段 ?事务在读写一个数据项之前，必须对其加锁； ?如果该数据项被其它使用者已加上不相容的锁，则必须等待。 阶段2：解锁阶段 ?事务在释放锁之后，不允许再申请其它锁； 锁 的 个 数 时间 事务开始执行 事务结束执行 操作 表示解锁 表示加锁 阶段1 阶段2 两段封锁协议(2PL)的加锁、解锁示意图 避免丢失修改错误 当事务T1、T2申请写锁时，均申请不到，必等待，直到另一事务释放对数据项x的锁为止。如：T2废弃，释放读锁；则T1得到写锁，完成写操作。事务T2重启动后，读取x(事务T1执行的结果)，直至完成操作。因此，不会出现丢失修改错误。 T1 T2 读锁 Slock(x) 读锁 Slock(x) 写锁 Xlock(x) 写锁 Xlock(x) 等待 abort (释放锁) T2重启 读锁Slock(x) 死锁 两阶段封锁协议 时间 获得写锁 (x=90) 提交 T1: x = x-10; T2: x = x-20; x 100 90 避免不可重复读错误 当事务T2申请写锁时，不能申请成功，必等待，当事务T1再次读数据项x时，读取的x值与第一次读到的值相同，不会出现重复读错误。 T1 T2 读锁 Slock(x) 写锁 Xlock(x) 读锁 Slock(x) 等待 冲突 时间 两阶段封锁协议 100 x T1: r(x) r(x) T2: x = x-20; 100 避免读脏数据错误 事务T1申请写锁后，写x=80。此时，事务T2申请读锁失败，必须等待。当事务T1产生故障中断时，废弃事务T1的执行，即执行反做，使x恢复为原值100，并释放对x的写锁。此时事务T2等待读锁，读取x值，x值为原值100，而不是事务T1的脏数据80。 T1 T2 写锁 Xl