数据库系统第十一章.ppt

1、1,第十一章 并发控制,11.1并发控制概述 11.2封锁 11.3封锁协议 11.4活锁和死锁 11.5并发调度的可串行性 11.6两段锁协议 11.7封锁的粒度,2,11.1并发控制概述,事务的并行,交叉并发方式(单处理机系统) 同时并发方式(多处理机系统),交叉并发方式,同时并发方式,3,并发控制机制,为了保证事务的隔离性和数据库的一致性，数据库管理系统具有的对并发操作进行正确调度的功能。,例子1：飞机订票系统的两个事务：,(1)事务甲:读机票余额A；卖出一张机票A=A-1；写回A；,(2)事务乙:读机票余额A；卖出一张机票A=A-1；写回A；,(1)丢失修改 (2)不可重复读 (3)读

2、“脏”数据,数据库的不一致性:,4,例子2:,不可重复读,不可重复读: (1)T1再次读取数据, 得值不相同; (2) T1再次读取数据, 某些数据消失; (3) T1再次读取数据, 多余数据出现;,5,例子3:,读“脏”数据,6,11.2封锁,封锁:事务T在对某个数据对象操作之前,先向系统发出请 求,对其加锁.加锁后事务T就对该 数据对象有了一定 的控制,在事务T释放它的锁之前,其它的事务不能更 新此数据对象.,封锁的类型:,排它锁 (Xlock) 共享锁 (Slock),排它锁 (Xlock):若事务T对数据对象A加上X锁,则允许T 读取和修改A,其他任何事务都不能再对A 加任何类型的锁,

3、直到T释放A上的X锁.,共享锁 (Slock):若事务T对数据对象A加上S锁,则允许T 读取A,其他事务只能再对A加S锁,不能加X 锁,直到T释放A上的S锁.,7,X锁与S锁的相容矩阵:,N,N,Y,N,Y,Y,Y,Y,Y,11.3封锁协议,封锁协议:在对数据对象加锁时,约定的规则（如何时申请 X锁或S锁、持锁时间、何时释放等）。,常用的封锁协议: 一级封锁协议 二级封锁协议 三级封锁协议,8,1.一级封锁协议,一级封锁协议:事务T在修改数据R之前必须先对其加X锁, 直到事务结束才释放.,丢失修改,Xlock A 获得 读A=16,Xlock A 等待,A=16-1 写回A=15 commit

4、 unlock A,获得 Xlock A 读A=15 A=15-1 写回A=14 Commit unlock A,没有丢失修改,9,读A=50 读B=100 求和=150,Xlock B 获得 读B=100 B=2*B 写回B=200 commit unlock B,读A=50 读B=200 求和=250,不可重复读,不可重复读,10,Xlock C 获得 读C=100 C=2*C 写回C=200,读C=200,rollback C恢复为100 unlock C,读“脏”数据,读“脏”数据,11,2.二级封锁协议,二级封锁协议:一级封锁协议加上事务T在读取数据R之前必须先对 其加S锁，读完后即

5、可释放S锁.,读“脏”数据,Xlock C 获得 读C=100 C=2*C 写回C=200,Slock C 等待,rollback C恢复为100 unlock C,获得Slock C 读 C=100 commit unlock C,不读“脏”数据,12,Slock A Slock B 获得 读A=50 读B=100 求和=150 unlock A unlock B,Xlock B 获得 读B=100 B=2*B 写回B=200 commit unlock B,Slock A Slock B 获得 读A=50 读B=200 求和=250 unlock A unlock B,不可重复读,13,3

6、.三级封锁协议,三级封锁协议:一级封锁协议加上事务T在读取数据R之前 必须先对其加S锁，直到事务结束才释放。,14,Slock A Slock B 获得 读A=50 读B=100 求和=150,Xlock B 等待,读A=50 读B=100 求和=150 commit unlock A unlock B, 获得 读B=100 B=2*B 写回B=200 commit unlock B,可重复读,15,封锁协议,总结:,什么操作需要申请封锁 何时释放锁,16,11.4 活锁和死锁,一、活锁,永远等待,解决活锁的方法:,先来先服务策略,17,二、死锁,解决死锁的方法:,1.死锁的预防 2.死锁的诊

7、断与解除,18,1.死锁的预防,(1) 一次封锁法,-要求每个事务必须一次将所要使用的数 据全部加锁,否则就不能继续执行.,19,(2)顺序封锁法,顺序封锁法:预先对数据对象规定一个封锁顺序,所有事务都按这个 顺序实行封锁.,对数据的封锁顺序：R1、R2,20,2.死锁的诊断与解除,(1)超时诊断法,如果一个事务的等待时间超过了规定的时限,就认为发生了死锁.,(2)等待图诊断法,并发控制子系统周期性地检测事务等待图,如果发现图中存在回路,则认为发生死锁.,(3)撤销解除法,选择一个处理死锁代价最小的事务,将其撤销,释放此事务持有的所有的锁,使其它事务得以继续运行下去.,21,11.5 并发调度

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

9、 获得 B=A+1=4 写回B=4 Unlock B,Slock A 获得 读A=2 Unlock A Xlock B 获得 B=A+1=3 写回B=3 Unlock B,Slock B 获得 读B=3 Unlock B Xlock A 获得 A=B+1=4 写回A=4 Unlock A,解：可能的串行执行结果：,A=3 B=4 A=4 B=3,24,不正确的调度,正确的调度,25,11.6 两段锁协议,两段锁协议:是指所有事务必须分两个阶段对数据项加锁 和解锁。,第一阶段是获得封锁，也称为扩展阶段,在此阶段,事务可以申请获 得任何数据项上的任何类型的锁,但不能释放任何锁; 第二阶段是释放封锁

10、,也称为收缩阶段,在此阶段,事务可以释放任何 数据项上的任何类型的锁,但不能再申请任何锁;,例子:,事务T1的封锁序列:,Slock A Slock B Xlock C Unlock B Unlock A Unlock C;,事务T2的封锁序列:,Slock A Unlock A Slock B Xlock C Unlock C Unlock B;,扩展阶段,收缩阶段,26,不遵守两段锁协议,可串行化,遵守两段锁协议,充分,27,两段锁协议和一次封锁法的异同之处:,一次封锁法要求每个事务必须一次将所要使用的数据全部加锁,否 则就不能继续执行.,两段锁协议是指所有事务必须分两个阶段对数据项加锁和

11、解锁。,遵守两段锁协议,发生死锁,一次封锁,28,11.7封锁的粒度,封锁粒度:是指封锁对象的大小.,封锁粒度与系统的并发度和开销密切相关:,例:,(1)封锁粒度为页,T1需要修改元组L1,则必须对包含L1的页A加锁;如果T1对A加后,T2需要修改元组L2,则T2被迫等待.,系统并发度低,(2)封锁粒度为元组,T3需要读取整个页A,则T3必须对页A中的每个元组加锁.,系统开销大,29,11.7.1 多粒度封锁,多粒度封锁：在一个系统中同时支持多种封锁粒度供不同 的事务选择。,1.定义多粒度树,根结点是整个数据库,表示最大的数据粒度.叶结点表示最小的数据粒度.,2.多粒度封锁协议,允许多粒度树中

12、的每个结点被独立地加锁.,30,例:,显式封锁:某个事务直接加到数据对象上的封锁.,隐式封锁:不是事务直接加上的封锁,而是由于上级结点加 锁而使该数据对象加上的锁.,T1获得对数据库加Slock,则同时它获得对关系R1Rn,元组11元组nm的Slock.,显式封锁(Slock),隐式封锁(Slock),31,多粒度封锁方法中,事务要对某个数据对象加锁,系统需要 检查: (1)待加的锁是否与该数据对象上原有的显式封锁冲突. (2)待加的锁是否与该数据对象上原有的隐式封锁冲突. (3)待加的锁是否与该数据对象的所有下级结点的原有的 显式、隐式封锁冲突.,例子:,T1对数据库加了Slock , 若此

13、时T2 要求对关系R1加Xlock,系统如何处理?,T1对关系R1加了Slock,若此时T2要求对数据库加Slock ,系统如何处理?,拒绝,允许,Xlock？,32,11.7.2 意向锁,33,思考题：比较单粒度封锁、多粒度封锁、具有意向锁多粒度封锁三者的联系与区别（可举例说明）。,例子：T1对关系R1加了Slock,若此时T2要求对关系Rn加Xlock ,系统如何处理?,（1）单粒度封锁,系统只检查X锁与关系Rn上原有的锁是否相容。,允许,（2）多粒度封锁,系统要检查： X锁与关系Rn上原有的显式锁是否相容 X锁与关系Rn上原有的隐式锁是否相容 X锁与关系Rn的下层结点元组n1元组nm上原 有的锁是否相容,允许,（3）具有意向锁多粒度封锁 系统要检查：.,34,1.在单粒度系统中，事务要使用某数据时，首先要申请对该数据加锁，系统要判定该锁是否和该数据原有的锁相容，如相容则可使用该数据，否则等待。 特点：系统判定简单，但是可能会降低系统并发度或增加系统开销。,2.在多粒度系统中，事务要使用某数据时，首先要申请对该数据加锁，系统要判定（1）该锁是否和该数据原有的显式锁相容。 （2）该锁是否和该数据原有的隐式锁相容。 （3）