数据库系统概论第11章并发控制.ppt

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

1、第第第第1111章章章章 并发控制并发控制并发控制并发控制 11.1并发控制概述并发控制概述11.2封锁封锁 11.3封锁协议封锁协议 11.4活锁和死锁活锁和死锁 11.5并发调度的可串行性并发调度的可串行性 11.6两段锁协议两段锁协议 11.7封锁的粒度封锁的粒度18.1并发控制概述并发控制概述事务的并行事务的并行交叉并发方式交叉并发方式(单处理机系统单处理机系统)同时并发方式同时并发方式(多处理机系统多处理机系统)时时间间T1T2T1(1)T2(1)T2(2)T1(2)T1(3)T2(3)例如例如:时间时间T1(1)T2(1)T2(2)T1(2)T1(3)T2(3)T1T2串行方式串行

2、方式时时间间T1T2T1(1)T2(1)T2(2)T1(2)T1(3)T2(3)交叉并发方式交叉并发方式同时并发方式同时并发方式2并发控制机制并发控制机制为了保证事务的隔离性和数据库的为了保证事务的隔离性和数据库的一致性，数据库管理系统具有的对一致性，数据库管理系统具有的对并发操作进行正确调度的功能。并发操作进行正确调度的功能。例子例子1：飞机订票系统的两个事务：飞机订票系统的两个事务：(1)事务甲事务甲:读机票余额读机票余额A；卖出一张机票；卖出一张机票A=A-1；写回；写回A；(2)事务乙事务乙:读机票余额读机票余额A；卖出一张机票；卖出一张机票A=A-1；写回；写回A；事务甲事务甲事务乙

3、事务乙时时间间读读A=16读读A=16A=16-1写回写回A=15A=16-1写回写回A=15(1)丢失修改丢失修改(2)不可重复读不可重复读(3)读读“脏脏”数据数据数据库的不一致性数据库的不一致性:3例子例子2:时时间间T1T2读读A=50 读读B=100 求和求和=150读读B=100 B=2*B 写回写回B=200读读A=50 读读B=200 求和求和=250不可重复读不可重复读不可重复读不可重复读:(1)T1再次读取数据再次读取数据,得值不相同得值不相同;(2)T1再次读取数据再次读取数据,某些数据消失某些数据消失;(3)T1再次读取数据再次读取数据,多余数据出现多余数据出现;4例子

4、例子3:时时间间T1T2读读C=100 C=2*C 写回写回C=200读读C=200 rollback C恢复为恢复为100读读“脏脏”数据数据58.2封锁封锁封锁封锁:事务事务T在对某个数据对象操作之前在对某个数据对象操作之前,先向系统发出请先向系统发出请 求求,对其加锁对其加锁.加锁后事务加锁后事务T就对该就对该 数据对象有了一定数据对象有了一定 的控制的控制,在事务在事务T释放它的锁之前释放它的锁之前,其它的事务不能更其它的事务不能更 新此数据对象新此数据对象.封锁的类型封锁的类型:排它锁排它锁(Xlock)共享锁共享锁(Slock)排它锁排它锁(Xlock):若事务若事务T对数据对象对

5、数据对象A加上加上X锁锁,则允许则允许T 读取读取和和修改修改A,其他任何事务都其他任何事务都不能不能再对再对A 加任何类型的锁加任何类型的锁,直到直到T释放释放A上的上的X锁锁.共享锁共享锁(Slock):若事务若事务T对数据对象对数据对象A加上加上S锁锁,则允许则允许T 读取读取A,其他事务只其他事务只能能再对再对A加加S锁锁,不能不能加加X 锁锁,直到直到T释放释放A上的上的S锁锁.6X锁与锁与S锁的相容矩阵锁的相容矩阵:T1T2Xlock Slock -XlockSlock -NNYNYYYYY8.3封锁协议封锁协议封锁协议封锁协议:在对数据对象加锁时在对数据对象加锁时,约定的规则（如

6、何时申请约定的规则（如何时申请 X锁或锁或S锁、持锁时间、何时释放等）。锁、持锁时间、何时释放等）。常用的封锁协议常用的封锁协议:一级封锁协议一级封锁协议 二级封锁协议二级封锁协议 三级封锁协议三级封锁协议71.一级封锁协议一级封锁协议一级封锁协议一级封锁协议:事务事务T在修改数据在修改数据R之前必须先对其加之前必须先对其加X锁锁,直到事务结束才释放直到事务结束才释放.事务甲事务甲事务乙事务乙时时间间读读A=16读读A=16A=16-1写回写回A=15A=16-1写回写回A=15丢失修改丢失修改Xlock A 获得获得 读读A=16Xlock A 等待等待A=16-1写回写回A=15 comm

7、it unlock A事务甲事务甲事务乙事务乙时时间间获得获得 Xlock A 读读A=15A=15-1写回写回A=14 Commit unlock A没有丢失修改没有丢失修改8时时间间T1T2读读A=50 读读B=100 求和求和=150Xlock B 获得获得 读读B=100 B=2*B 写回写回B=200 commit unlock B读读A=50 读读B=200 求和求和=250不可重复读不可重复读时时间间T1T2读读A=50 读读B=100 求和求和=150读读B=100 B=2*B 写回写回B=200读读A=50 读读B=200 求和求和=250不可重复读不可重复读9时时间间T1T

8、2Xlock C 获得获得 读读C=100 C=2*C 写回写回C=200读读C=200 rollback C恢复为恢复为100 unlock C读读“脏脏”数据数据时时间间T1T2读读C=100 C=2*C 写回写回C=200读读C=200 rollback C恢复为恢复为100读读“脏脏”数据数据102.二级封锁协议二级封锁协议二级封锁协议二级封锁协议:一级封锁协议加上事务一级封锁协议加上事务T在读取数据在读取数据R之前必须先对之前必须先对 其加其加S锁，读完后即可释放锁，读完后即可释放S锁锁.时时间间T1T2Xlock C 获得获得 读读C=100 C=2*C 写回写回C=200读读C=

9、200 rollback C恢复为恢复为100 unlock C读读“脏脏”数据数据时时间间T1T2Xlock C 获得获得 读读C=100 C=2*C 写回写回C=200Slock C 等待等待 rollback C恢复为恢复为100 unlock C获得获得Slock C 读读 C=100 commit unlock C不读不读“脏脏”数据数据11时时间间T1T2读读A=50 读读B=100 求和求和=150Xlock B 获得获得 读读B=100 B=2*B 写回写回B=200 commit unlock B读读A=50 读读B=200 求和求和=250不可重复读不可重复读时时间间T1T

10、2Slock A Slock B 获得获得 读读A=50 读读B=100 求和求和=150 unlock A unlock B Xlock B 获得获得 读读B=100 B=2*B 写回写回B=200 commit unlock BSlock A Slock B 获得获得 读读A=50 读读B=200 求和求和=250 unlock A unlock B 不可重复读不可重复读123.三级封锁协议三级封锁协议三级封锁协议三级封锁协议:一级封锁协议加上事务一级封锁协议加上事务T在读取数据在读取数据R之前之前 必须先对其加必须先对其加S锁，直到事务结束才释放。锁，直到事务结束才释放。13时时间间T1

11、T2Slock A Slock B 获得获得 读读A=50 读读B=100 求和求和=150 unlock A unlock B Xlock B 获得获得 读读B=100 B=2*B 写回写回B=200 commit unlock BSlock A Slock B 获得获得 读读A=50 读读B=200 求和求和=250 unlock A unlock B 不可重复读不可重复读时时间间T1T2Slock A Slock B 获得获得 读读A=50 读读B=100 求和求和=150Xlock B 等待等待读读A=50 读读B=100 求和求和=150 commit unlock A unlock

12、 B 获得获得 读读B=100 B=2*B 写回写回B=200 commit unlock B可重复读可重复读14封锁协议封锁协议总结总结:什么操作需要申请封锁什么操作需要申请封锁何时释放锁何时释放锁X锁锁S锁锁一致性保证一致性保证操作操作结束结束释放释放操作操作结束结束释放释放事务事务结束结束释放释放事务事务结束结束释放释放一级封锁协议一级封锁协议二级封锁协议二级封锁协议三级封锁协议三级封锁协议不丢失不丢失 修修 改改不读脏不读脏数数 据据可重可重复读复读158.4 活锁和死锁活锁和死锁一、活锁一、活锁时时间间T1T2T3T4Lock R 获得获得 Lock R 等待等待Lock R 等待等

13、待Unlock R获得获得Unlock RLock R 等待等待获得获得永远等待永远等待解决活锁的方法解决活锁的方法:先来先服务策略先来先服务策略16二、死锁二、死锁时时间间T1T2Lock R1 获得获得Lock R2 获得获得Lock R2 等待等待Lock R1 等待等待解决死锁的方法解决死锁的方法:1.死锁的预防死锁的预防2.死锁的诊断与解除死锁的诊断与解除171.死锁的预防死锁的预防(1)一次封锁法一次封锁法-要求每个事务必须一次将所要使用的要求每个事务必须一次将所要使用的数数 据全部加锁据全部加锁,否则就不能继续执行否则就不能继续执行.时时间间T1T2Lock R1 获得获得Loc

14、k R2 获得获得Lock R2 等待等待Lock R1 等待等待Unlock R1Unlock R2获得获得 R1 R2 18(2)顺序封锁法顺序封锁法顺序封锁法顺序封锁法:预先对数据对象规定一个封锁顺序预先对数据对象规定一个封锁顺序,所有事务都按这所有事务都按这个个 顺序实行封锁顺序实行封锁.时时间间T1T2Lock R1 获得获得 Unlock R1Lock R2 获得获得 Lock R1 等待等待 获得获得 Lock R2 等待等待 .Unlock R2 获得获得 Unlock R1,R2对数据的封对数据的封锁顺序：锁顺序：R1、R2192.死锁的诊断与解除死锁的诊断与解除(1)超时诊

15、断法超时诊断法如果一个事务的等待时间超过了规定的时限如果一个事务的等待时间超过了规定的时限,就认为发就认为发生了死锁生了死锁.(2)等待图诊断法等待图诊断法并发控制子系统周期性地检测事务等待图并发控制子系统周期性地检测事务等待图,如果发现图如果发现图中存在回路中存在回路,则认为发生死锁则认为发生死锁.(3)撤销解除法撤销解除法选择一个处理死锁代价最小的事务选择一个处理死锁代价最小的事务,将其撤销将其撤销,释放此释放此事务持有的所有的锁事务持有的所有的锁,使其它事务得以继续运行下去使其它事务得以继续运行下去.208.5 并发调度的可串行性并发调度的可串行性定义定义:多个事务的并发执行是正确的多个

16、事务的并发执行是正确的,当且仅当其结果与当且仅当其结果与 按某一次序串行地执行它们时的结果相同按某一次序串行地执行它们时的结果相同,我们称我们称 这种调度策略为这种调度策略为可串行化可串行化的调度的调度.定理定理:一个给定的并发调度一个给定的并发调度,当且仅当它是可串行化的当且仅当它是可串行化的,才才 认为是认为是正确调度正确调度.例子例子:有两个事务有两个事务:T1:读读B;A=B+1;写回写回A;T2:读读A;B=A+1;写回写回B;请分析以下请分析以下2种对这两个事务的调度策略哪些是正确的种对这两个事务的调度策略哪些是正确的,哪些是不正确的哪些是不正确的.(设设A、B的初值都为的初值都为

17、2）21Xlock A获得获得A=B+1=3写回写回A=3Xlock B获得获得B=A+1=3写回写回B=3T1T2T1T2Slock A等待等待Slock B获得获得读读B=2Unlock BXlock A获得获得Slock A获得获得读读A=2Slock B获得获得读读B=2Unlock BUnlock AUnlock AUnlock BA=B+1=3写回写回A=3Unlock A获得获得读读A=3Unlock AXlock B获得获得B=A+1=4写回写回B=4Unlock B22Slock B获得获得读读B=2Unlock BXlock A获得获得A=B+1=3写回写回A=3Unloc

18、k ASlock A获得获得读读A=3Unlock AXlock B获得获得B=A+1=4写回写回B=4Unlock BSlock A获得获得读读A=2Unlock AXlock B获得获得B=A+1=3写回写回B=3Unlock BSlock B获得获得读读B=3Unlock BXlock A获得获得A=B+1=4写回写回A=4Unlock AT1T2T1T2解解：可能的串行执行结果：可能的串行执行结果：A=3 B=4A=4 B=323Xlock A获得获得A=B+1=3写回写回A=3Xlock B获得获得B=A+1=3写回写回B=3T1T2T1T2Slock A等待等待Slock B获得获

19、得读读B=2Unlock BXlock A获得获得Slock A获得获得读读A=2Slock B获得获得读读B=2Unlock BUnlock AUnlock AUnlock BA=B+1=3写回写回A=3Unlock A获得获得读读A=3Unlock AXlock B获得获得B=A+1=4写回写回B=4Unlock B不不正正确确的的调调度度正正确确的的调调度度248.6 两段锁协议两段锁协议两段锁协议两段锁协议:是指所有事务必须分两个阶段对数据项加锁是指所有事务必须分两个阶段对数据项加锁 和解锁。和解锁。第一阶段第一阶段是获得封锁，也称为扩展阶段是获得封锁，也称为扩展阶段,在此阶段在此阶段

20、,事务可以申请获事务可以申请获 得任何数据项上的任何类型的锁得任何数据项上的任何类型的锁,但不能释放任何锁但不能释放任何锁;第二阶段第二阶段是释放封锁是释放封锁,也称为收缩阶段也称为收缩阶段,在此阶段在此阶段,事务可以释放任事务可以释放任何何 数据项上的任何类型的锁数据项上的任何类型的锁,但不能再申请任何锁但不能再申请任何锁;例子例子:事务事务T1的封锁序列的封锁序列:Slock A Slock B Xlock C Unlock B Unlock A Unlock C;事务事务T2的封锁序列的封锁序列:Slock A Unlock A Slock B Xlock C Unlock C Unlo

21、ck B;扩展阶段扩展阶段收缩阶段收缩阶段25不遵守两段锁协议不遵守两段锁协议可串行化可串行化T1T2T1T2Slock B获得获得读读B=2Xlock ASlock A等待等待A=B+1=3写回写回A=3Unlock BUnlock A获得获得读读A=3Xlock B获得获得B=A+1=4写回写回B=4Unlock BUnlock ASlock B获得获得读读B=2Unlock BXlock ASlock A等待等待A=B+1=3写回写回A=3Unlock A获得获得读读A=3Unlock AXlock B获得获得B=A+1=4写回写回B=4Unlock B遵守两段锁协议遵守两段锁协议充分充

22、分26两段锁协议和一次封锁法的异同之处两段锁协议和一次封锁法的异同之处:一次封锁法一次封锁法要求每个事务必须一次将所要使用的数据全部加锁要求每个事务必须一次将所要使用的数据全部加锁,否否 则就不能继续执行则就不能继续执行.两段锁协议两段锁协议是指所有事务必须分两个阶段对数据项加锁和解锁。是指所有事务必须分两个阶段对数据项加锁和解锁。时时间间T1T2SLock R1 获得获得XLock R2 获得获得SLock R2 等待等待XLock R1 等待等待Unlock R1Unlock R2获得获得 R1 R2 时时间间T1T2SLock R1 获得获得XLock R2 获得获得SLock R2 等

23、待等待XLock R1 等待等待遵守两段锁协议遵守两段锁协议,发生死锁发生死锁一次封锁一次封锁278.7封锁的粒度封锁的粒度封锁粒度封锁粒度:是指封锁对象的大小是指封锁对象的大小.封锁粒度与系统的并发度和开销密切相关封锁粒度与系统的并发度和开销密切相关:例例:(1)封锁粒度为页封锁粒度为页 T1需要修改元组需要修改元组L1,则必须对包则必须对包含含L1的页的页A加锁加锁;如果如果T1对对A加后加后,T2需要修改元组需要修改元组L2,则则T2被迫等待被迫等待.系统并发度低系统并发度低(2)封锁粒度为元组封锁粒度为元组 T3需要读取整个页需要读取整个页A,则则T3必须必须对页对页A中的每个元组加锁

24、中的每个元组加锁.系统开销大系统开销大L1L2页页A288.7.1 多粒度封锁多粒度封锁多粒度封锁：在一个系统中同时支持多种封锁粒度供不同多粒度封锁：在一个系统中同时支持多种封锁粒度供不同 的事务选择。的事务选择。1.定义多粒度树定义多粒度树根结点是整个数据库根结点是整个数据库,表示最大的数据粒表示最大的数据粒度度.叶结点表示最小的数据粒度叶结点表示最小的数据粒度.数据库数据库关系关系R1关系关系Rn元组元组11元组元组1m元组元组n1元组元组nm2.多粒度封锁协议多粒度封锁协议允许多粒度树中的每个结点被允许多粒度树中的每个结点被独立地加锁独立地加锁.29例例:数据库数据库关系关系R1关系关系

25、Rn元组元组11元组元组1n元组元组n1元组元组nm显式封锁显式封锁:某个事务直接加到数据对象上的封锁某个事务直接加到数据对象上的封锁.隐式封锁隐式封锁:不是事务直接加上的封锁不是事务直接加上的封锁,而是由于上级结点加而是由于上级结点加 锁而使该数据对象加上的锁锁而使该数据对象加上的锁.T1获得对数据库加获得对数据库加Slock,则同时它获得对关系则同时它获得对关系R1Rn,元元组组11元组元组nm的的Slock.显式封锁显式封锁(Slock)隐式封锁隐式封锁(Slock)30多粒度封锁方法中多粒度封锁方法中,事务要对某个数据对象加锁事务要对某个数据对象加锁,系统需要系统需要检查检查:(1)待

26、加的锁是否与该数据对象上原有的待加的锁是否与该数据对象上原有的显式封锁显式封锁冲突冲突.(2)待加的锁是否与该数据对象上原有的待加的锁是否与该数据对象上原有的隐式封锁隐式封锁冲突冲突.(3)待加的锁是否与该数据对象的所有待加的锁是否与该数据对象的所有下级结点下级结点的原有的的原有的 显式封锁冲突显式封锁冲突.例子例子:数据库数据库关系关系R1关系关系Rn元组元组11元组元组1n元组元组n1元组元组nmT1对数据库加了对数据库加了Slock,若此时若此时T2 要求对关系要求对关系R1加加Xlock,系统如何处理系统如何处理?T1对关系对关系R1加了加了Slock,若此时若此时T2要求对数据库加要

27、求对数据库加Slock,系统如何处理系统如何处理?拒绝拒绝允许允许Xlock？318.7.2 意向锁意向锁32思考题：比较思考题：比较单粒度封锁单粒度封锁、多粒度封锁多粒度封锁、具有意向锁多粒具有意向锁多粒度封锁度封锁三者的联系与区别（可举例说明）。三者的联系与区别（可举例说明）。例子：例子：T1对关系对关系R1加了加了Slock,若此时若此时T2要求对关系要求对关系Rn加加Xlock,系统如何处理系统如何处理?（1）单粒度封锁）单粒度封锁系统只检查系统只检查X锁与关系锁与关系Rn上原有的锁是否相容。上原有的锁是否相容。允许允许（2）多粒度封锁）多粒度封锁系统要检查：系统要检查：X锁与关系锁与

28、关系Rn上原有的显式锁是否相容上原有的显式锁是否相容 X锁与关系锁与关系Rn上原有的隐式锁是否相容上原有的隐式锁是否相容 X锁与关系锁与关系Rn的下层结点元组的下层结点元组n1元组元组nm上原上原 有的锁是否相容有的锁是否相容允许允许（3）具有意向锁多粒度封锁）具有意向锁多粒度封锁 系统要检查：系统要检查：.331.在单粒度系统中，事务要使用某数据时，首先要申请对该数据加锁，系统要判在单粒度系统中，事务要使用某数据时，首先要申请对该数据加锁，系统要判定该锁是否和该数据原有的锁相容，如相容则可使用该数据，否则等待。定该锁是否和该数据原有的锁相容，如相容则可使用该数据，否则等待。特点：系统判定简单

29、，但是可能会降低系统并发度或增加系统开销。特点：系统判定简单，但是可能会降低系统并发度或增加系统开销。2.在多粒度系统中，事务要使用某数据时，首先要申请对该数据加锁，系统要判在多粒度系统中，事务要使用某数据时，首先要申请对该数据加锁，系统要判定（定（1）该锁是否和该数据原有的显式锁相容。）该锁是否和该数据原有的显式锁相容。（2）该锁是否和该数据原有的隐式锁相容。）该锁是否和该数据原有的隐式锁相容。（3）该锁是否和该数据的下层结点原有的锁相容）该锁是否和该数据的下层结点原有的锁相容 如都相容则可使用该数据，否则等待。如都相容则可使用该数据，否则等待。特点：系统判定复杂，但可以提高系统并发度或减少

30、系统开销。特点：系统判定复杂，但可以提高系统并发度或减少系统开销。3.在具有意向锁的多粒度系统中，事务要使用某数据时，首先要申请对该数据的在具有意向锁的多粒度系统中，事务要使用某数据时，首先要申请对该数据的上层结点加意向锁，再对该数据加锁，系统要判定上层结点加意向锁，再对该数据加锁，系统要判定 （1）该意向锁是否和上层结点原有锁相容。）该意向锁是否和上层结点原有锁相容。（2）该锁是否和该数据原有的锁相容。）该锁是否和该数据原有的锁相容。如都相容则可使用该数据，否则等待。如都相容则可使用该数据，否则等待。特点：系统判定不是很复杂，但可以提高系统并发度或减少系统开销。特点：系统判定不是很复杂，但可以提高系统并发度或减少系统开销。34