数据库原理第十一章并发控制学习教案.pptx

会计学1数据库原理数据库原理(yunl)第十一章并发控制第十一章并发控制第一页，共100页。问题问题(wnt)的产生的产生n n多用户数据库系统的存在n n 允许多个用户同时使用的数据库系统n n飞机定票数据库系统n n银行数据库系统 n n特点：在同一时刻(shk)并发运行的事务数可达数百个 第1页/共100页第二页，共100页。问题问题(wnt)的产生（续）的产生（续）n n不同的多事务执行方式不同的多事务执行方式 n n (1)(1)事务串行执行事务串行执行n n每每个个时时刻刻只只有有一一个个事事务务运运行行，其其他他事事务务必必须须等到这个事务结束以后方能运行等到这个事务结束以后方能运行n n不不能能充充分分利利用用系系统统资资源源，发发挥挥(fhu)(fhu)数数据据库库共享资源的特点共享资源的特点T1T2T3事务的串行执行(zhxng)方式第2页/共100页第三页，共100页。问题问题(wnt)的产生（续）的产生（续）(2)(2)交叉并发方式（交叉并发方式（Interleaved ConcurrencyInterleaved Concurrency）在单处理机系统中，事务的并行执行是这些并行事务的并行操作轮流交叉运行在单处理机系统中，事务的并行执行是这些并行事务的并行操作轮流交叉运行单单处处理理机机系系统统中中的的并并行行事事务务并并没没有有真真正正地地并并行行运运行行，但但能能够够(nnggu)(nnggu)减减少少处处理理机机的的空空闲时间，提高系统的效率闲时间，提高系统的效率第3页/共100页第四页，共100页。问题问题(wnt)的产生（续）的产生（续）事务(shw)的交叉并发执行方式第4页/共100页第五页，共100页。问题问题(wnt)的产生（续）的产生（续）(3)同时并发方式（simultaneous concurrency）多处理机系统中，每个处理机可以运行一个事务(shw)，多个处理机可以同时运行多个事务(shw)，实现多个事务(shw)真正的并行运行第5页/共100页第六页，共100页。问题问题(wnt)的产生（续）的产生（续）n n事务并发执行带来的问题n n会产生(chnshng)多个事务同时存取同一数据的情况 n n可能会存取和存储不正确的数据，破坏事务一致性和数据库的一致性第6页/共100页第七页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发并发(bngf)控制概述控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并并发发(bngf)调调度度的的可可串串行行性性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度11.7 小结小结第7页/共100页第八页，共100页。11.1 并发控制并发控制(kngzh)概述概述n n并发控制机制的任务n n对并发操作进行正确(zhngqu)调度n n保证事务的隔离性n n保证数据库的一致性第8页/共100页第九页，共100页。T1T1的修改的修改的修改的修改(xig(xig i)i)被被被被T2T2覆盖了！覆盖了！覆盖了！覆盖了！并发控制(kngzh)概述（续）并发操作并发操作并发操作并发操作(cozu)(cozu)带来数据的不一致性实例带来数据的不一致性实例带来数据的不一致性实例带来数据的不一致性实例 例例例例11飞机订票系统中的一个活动序列飞机订票系统中的一个活动序列飞机订票系统中的一个活动序列飞机订票系统中的一个活动序列 甲售票点甲售票点甲售票点甲售票点(甲事务甲事务甲事务甲事务)读出某航班的机票余额读出某航班的机票余额读出某航班的机票余额读出某航班的机票余额A A，设，设，设，设A=16A=16；乙售票点乙售票点乙售票点乙售票点(乙事务乙事务乙事务乙事务)读出同一航班的机票余额读出同一航班的机票余额读出同一航班的机票余额读出同一航班的机票余额A A，也为，也为，也为，也为1616；甲售票点卖出一张机票，修改余额甲售票点卖出一张机票，修改余额甲售票点卖出一张机票，修改余额甲售票点卖出一张机票，修改余额AA-1AA-1，所以，所以，所以，所以A A为为为为1515，把，把，把，把A A写回数写回数写回数写回数据库；据库；据库；据库；乙售票点也卖出一张机票，修改余额乙售票点也卖出一张机票，修改余额乙售票点也卖出一张机票，修改余额乙售票点也卖出一张机票，修改余额AA-1AA-1，所以，所以，所以，所以A A为为为为1515，把，把，把，把A A写回写回写回写回数据库数据库数据库数据库 结果明明卖出两张机票，数据库中机票余额只减少结果明明卖出两张机票，数据库中机票余额只减少结果明明卖出两张机票，数据库中机票余额只减少结果明明卖出两张机票，数据库中机票余额只减少1 1 第9页/共100页第十页，共100页。并发控制并发控制(kngzh)概述（续）概述（续）n n这种情况称为数据库的不一致性，是由并发操作引起的。这种情况称为数据库的不一致性，是由并发操作引起的。n n在并发操作情况下，对甲、乙两个事务的操作序列的调度是随机的。在并发操作情况下，对甲、乙两个事务的操作序列的调度是随机的。n n若按上面的调度序列执行，甲事务的修改就被丢失若按上面的调度序列执行，甲事务的修改就被丢失(dis)(dis)。n n原因：第原因：第4 4步中乙事务修改步中乙事务修改A A并写回后覆盖了甲事务的修改并写回后覆盖了甲事务的修改第10页/共100页第十一页，共100页。并发并发(bngf)控制概述（续）控制概述（续）n n并发操作带来的数据不一致性并发操作带来的数据不一致性n n丢失修改丢失修改(xig(xig i)i)（Lost UpdateLost Update）n n不可重复读（不可重复读（Non-repeatable ReadNon-repeatable Read）n n读读“脏脏”数据（数据（Dirty ReadDirty Read）n n记号记号n nR(x):R(x):读数据读数据x xn nW(x):W(x):写数据写数据x x 第11页/共100页第十二页，共100页。1.丢失丢失(dis)修改修改n n两个事务T1和T2读入同一数据并修改，T2的提交结果破坏了T1提交的结果，导致T1的修改被丢失。n n上面(shng min)飞机订票例子就属此类 第12页/共100页第十三页，共100页。丢失丢失(dis)修改（续）修改（续）T1T2 R(A)=16R(A)=16 AA-1 W(A)=15WAA-1W(A)=15丢失(dis)修改第13页/共100页第十四页，共100页。2.不可不可(bk)重复读重复读n n不可(bk)重复读是指事务T1读取数据后，事务T2n n 执行更新操作，使T1无法再现前一次读取结果。第14页/共100页第十五页，共100页。不可不可(bk)重复读（续）重复读（续）n n不可(bk)重复读包括三种情况：n n(1)事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读该数据时，得到与前一次不同的值 第15页/共100页第十六页，共100页。不可不可(bk)重复读（续）重复读（续）n nT1T1读取读取B=100B=100进行进行(jnxng)(jnxng)运算运算n nT2T2读取同一数据读取同一数据B B，对其进行，对其进行(jnxng)(jnxng)修改后将修改后将B=200B=200写回数据写回数据库。库。n nT1T1为了对读取值校对重读为了对读取值校对重读B B，B B已已为为200200，与第一次读取值不一致，与第一次读取值不一致 T1T2 R(A)=50 R(B)=100求和=150R(B)=100BB*2(B)=200 R(A)=50R(B)=200和=250(验算不对)不可(bk)重复读 例如：第16页/共100页第十七页，共100页。不可不可(bk)重复读（续）重复读（续）(2)(2)事务事务T1T1按一定条件从数据库中读取了某些数据记录后，事按一定条件从数据库中读取了某些数据记录后，事务务T2T2删除了其中部分记录，当删除了其中部分记录，当T1T1再次按相同条件读取数再次按相同条件读取数据时，发现某些记录消失了据时，发现某些记录消失了 (3)(3)事务事务T1T1按一定条件从数据库中读取某些数据记录后，事务按一定条件从数据库中读取某些数据记录后，事务T2T2插入了一些插入了一些(yxi)(yxi)记录，当记录，当T1T1再次按相同条件读取数据再次按相同条件读取数据时，发现多了一些时，发现多了一些(yxi)(yxi)记录。记录。后两种不可重复读有时也称为幻影现象（后两种不可重复读有时也称为幻影现象（Phantom RowPhantom Row）第17页/共100页第十八页，共100页。3.读读“脏脏”数据数据(shj)读“脏”数据是指：事务T1修改某一数据，并将其写回磁盘(c pn)事务T2读取同一数据后，T1由于某种原因被撤销这时T1已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致T2读到的数据就为“脏”数据，即不正确的数据 第18页/共100页第十九页，共100页。读读“脏脏”数据数据(shj)（续）（续）T1T2 R(C)=100 CC*2 W(C)=200R(C)=200ROLLBACK C恢复为100例如(lr)读“脏”数据(shj)nT1将C值修改为200，T2读到C为200nT1由于某种原因撤销，其修改作废，C恢复原值100n这时T2读到的C为200，与数据库内容不一致，就是“脏”数据 第19页/共100页第二十页，共100页。并发控制并发控制(kngzh)概述（续）概述（续）n n数据不一致性：由于并发操作破坏了事务的隔离性n n并发控制就是要用正确的方式调度并发操作，使一个用户事务的执行不受其他事务的干扰，从而避免(bmin)造成数据的不一致性 第20页/共100页第二十一页，共100页。并发并发(bngf)控制概述（续）控制概述（续）n n并发(bngf)控制的主要技术n n有封锁(Locking)n n时间戳(Timestamp)n n乐观控制法n n商用的DBMS一般都采用封锁方法 第21页/共100页第二十二页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发控制概述并发控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并并发发调调度度(diod)的的可可串串行行性性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度11.7 小结小结第22页/共100页第二十三页，共100页。11.2 封锁封锁(fn su)n n什么是封锁n n基本封锁类型n n锁的相容(xin rn)矩阵第23页/共100页第二十四页，共100页。什么什么(shn me)是封锁是封锁n n封锁就是事务T在对某个数据对象(duxing)（例如表、记录等）操作之前，先向系统发出请求，对其加锁n n加锁后事务T就对该数据对象(duxing)有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象(duxing)。第24页/共100页第二十五页，共100页。基本基本(jbn)封锁类型封锁类型n n一个事务一个事务(shw)(shw)对某个数据对象加锁后究竟拥有什么样的控制由封锁的类型决定。对某个数据对象加锁后究竟拥有什么样的控制由封锁的类型决定。n n基本封锁类型基本封锁类型n n排它锁（排它锁（Exclusive LocksExclusive Locks，简记为，简记为X X锁）锁）n n共享锁（共享锁（Share LocksShare Locks，简记为，简记为S S锁）锁）第25页/共100页第二十六页，共100页。排它锁排它锁n n排它锁又称为写锁n n若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它(qt)任何事务都不能再对A加任何类型的锁，直到T释放A上的锁n n保证其他事务在T释放A上的锁之前不能再读取和修改A 第26页/共100页第二十七页，共100页。共享锁共享锁n n共享锁又称为读锁n n若事务T对数据对象A加上S锁，则其它事务只能再对A加S锁，而不能加X锁，直到T释放(shfng)A上的S锁n n保证其他事务可以读A，但在T释放(shfng)A上的S锁之前不能对A做任何修改 第27页/共100页第二十八页，共100页。锁的相容锁的相容(xin rn)矩阵矩阵Y=Yes，相容的请求N=No，不相容的请求T1T2XS-XNNYSNYY-YYY第28页/共100页第二十九页，共100页。锁的相容锁的相容(xin rn)矩阵（续）矩阵（续）在锁的相容矩阵中：在锁的相容矩阵中：最左边最左边(zu(zu bian)bian)一列表示事务一列表示事务T1T1已经获得的数据对象上的锁的类型，其中横线已经获得的数据对象上的锁的类型，其中横线表示没有加锁。表示没有加锁。最上面一行表示另一事务最上面一行表示另一事务T2T2对同一数据对象发出的封锁请求。对同一数据对象发出的封锁请求。T2T2的封锁请求能否被满足用矩阵中的的封锁请求能否被满足用矩阵中的Y Y和和NN表示表示Y Y表示事务表示事务T2T2的封锁要求与的封锁要求与T1T1已持有的锁相容，封锁请求可以满足已持有的锁相容，封锁请求可以满足NN表示表示T2T2的封锁请求与的封锁请求与T1T1已持有的锁冲突，已持有的锁冲突，T2T2的请求被拒绝的请求被拒绝第29页/共100页第三十页，共100页。使用封锁机制解决丢失使用封锁机制解决丢失(dis)修改问题修改问题T1T2 Xlock A R(A)=16Xlock A AA-1等待 W(A)=15等待 Commit等待 Unlock A等待获得Xlock AR(A)=15AA-1W(A)=14CommitUnlock A例：n事务T1在读(zi d)A进行修改之前先对A加X锁n当T2再请求对A加X锁时被拒绝nT2只能等待T1释放A上的锁后T2获得对A的X锁n这时T2读到的A已经是T1更新过的值15nT2按此新的A值进行运算，并将结果值A=14送回到磁盘。避免了丢失T1的更新。没有丢失(dis)修改第30页/共100页第三十一页，共100页。使用封锁机制使用封锁机制(jzh)解决不可重复读问题解决不可重复读问题T1T2 Slock ASlock BR(A)=50R(B)=100求和=150Xlock B等待等待 R(A)=50等待R(B)=100等待求和=150等待Commit等待Unlock A等待Unlock B等待获得XlockBR(B)=100BB*2W(B)=200CommitUnlock Bn事务T1在读(zi d)A，B之前，先对A，B加S锁n其他事务只能再对A，B加S锁，而不能加X锁，即其他事务只能读A，B，而不能修改n当T2为修改B而申请对B的X锁时被拒绝只能等待T1释放B上的锁nT1为验算再读A，B，这时读出的B仍是100，求和结果仍为150，即可重复读nT1结束才释放A，B上的S锁。T2才获得对B的X锁 可重复(chngf)读第31页/共100页第三十二页，共100页。使用封锁机制使用封锁机制(jzh)解决读解决读“脏脏”数据问题数据问题T1T2 Xlock CR(C)=100CC*2W(C)=200Slock C等待 ROLLBACK等待(C恢复为100)等待Unlock C等待获得Slock CR(C)=100Commit CUnlock C例n事务T1在对C进行修改之前，先对C加X锁，修改其值后写回磁盘nT2请求在C上加S锁，因T1已在C上加了X锁，T2只能等待nT1因某种原因被撤销，C恢复(huf)为原值100nT1释放C上的X锁后T2获得C上的S锁，读C=100。避免了T2读“脏”数据不读“脏”数据(shj)第32页/共100页第三十三页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发并发(bngf)控制概述控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并并发发(bngf)调调度度的的可可串串行行性性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度11.7 小结小结第33页/共100页第三十四页，共100页。11.3 活锁和死锁活锁和死锁n n封锁(fn su)技术可以有效地解决并行操作的一致性问题，但也带来一些新的问题n n死锁n n活锁第34页/共100页第三十五页，共100页。活锁活锁n n事务事务T1T1封锁了数据封锁了数据R Rn n事务事务T2T2又请求又请求(q(q ngqi)ngqi)封锁封锁R R，于是，于是T2T2等待。等待。n nT3T3也请求也请求(q(q ngqi)ngqi)封锁封锁R R，当，当T1T1释放了释放了R R上的封锁之后系统首先批准了上的封锁之后系统首先批准了T3T3的请求的请求(q(q ngqi)ngqi)，T2T2仍然等待。仍然等待。n nT4T4又请求又请求(q(q ngqi)ngqi)封锁封锁R R，当，当T3T3释放了释放了R R上的封锁之后系统又批准了上的封锁之后系统又批准了T4T4的请求的请求(q(q ngqi)ngqi)n nT2T2有可能永远等待，这就是活锁的情形有可能永远等待，这就是活锁的情形 第35页/共100页第三十六页，共100页。活锁（续）活锁（续）活 锁第36页/共100页第三十七页，共100页。活锁（续）活锁（续）n n避免活锁：采用先来先服务的策略避免活锁：采用先来先服务的策略n n当多个事务请求封锁同一数据对象当多个事务请求封锁同一数据对象(duxing)(duxing)时时n n按请求封锁的先后次序对这些事务排队按请求封锁的先后次序对这些事务排队n n该该数数据据对对象象(duxing)(duxing)上上的的锁锁一一旦旦释释放放，首首先先批批准准申申请请队队列列中第一个事务获得锁中第一个事务获得锁第37页/共100页第三十八页，共100页。死锁死锁n n事务事务T1T1封锁了数据封锁了数据R1R1n nT2T2封锁了数据封锁了数据R2R2n nT1T1又请求封锁又请求封锁R2R2，因，因T2T2已封锁了已封锁了R2R2，于是，于是T1T1等待等待(dngdi)T2(dngdi)T2释放释放R2R2上的锁上的锁n n接着接着T2T2又申请封锁又申请封锁R1R1，因，因T1T1已封锁了已封锁了R1R1，T2T2也只能等待也只能等待(dngdi)T1(dngdi)T1释放释放R1R1上的锁上的锁n n这样这样T1T1在等待在等待(dngdi)T2(dngdi)T2，而，而T2T2又在等待又在等待(dngdi)T1(dngdi)T1，T1T1和和T2T2两个事务永远不能结两个事务永远不能结束，形成死锁束，形成死锁 第38页/共100页第三十九页，共100页。死锁（续）死锁（续）T1T2lock R1Lock R2Lock R2.等待等待Lock R1等待等待等待等待死 锁第39页/共100页第四十页，共100页。解决解决(jiju)死锁的方法死锁的方法两类方法两类方法1.1.预防预防(yfng)(yfng)死锁死锁2.2.死锁的诊断与解除死锁的诊断与解除第40页/共100页第四十一页，共100页。1.死锁的预防死锁的预防(yfng)n n产生死锁的原因是两个或多个事务都已封锁产生死锁的原因是两个或多个事务都已封锁(fn(fn su su)了一些数据对象，然后又都请求对已了一些数据对象，然后又都请求对已为其他事务封锁为其他事务封锁(fn(fn su su)的数据对象加锁，从而出现死等待。的数据对象加锁，从而出现死等待。n n预防死锁的发生就是要破坏产生死锁的条件预防死锁的发生就是要破坏产生死锁的条件第41页/共100页第四十二页，共100页。死锁的预防死锁的预防(yfng)（续）（续）预防死锁的方法 一次封锁(fn su)法 顺序封锁(fn su)法第42页/共100页第四十三页，共100页。(1)一次封锁一次封锁(fn su)法法n n要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行n n存在的问题n n降低系统并发(bngf)度n n难于事先精确确定封锁对象第43页/共100页第四十四页，共100页。(2)顺序顺序(shnx)封锁法封锁法n n顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。n n顺序封锁法存在的问题顺序封锁法存在的问题(wnt)(wnt)n n维护成本维护成本n n 数据库系统中封锁的数据对象极多，并且在不断地变化。数据库系统中封锁的数据对象极多，并且在不断地变化。n n难以实现：很难事先确定每一个事务要封锁哪些对象难以实现：很难事先确定每一个事务要封锁哪些对象n n 第44页/共100页第四十五页，共100页。死锁的预防死锁的预防(yfng)（续）（续）n n结论n n在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点n nDBMS在解决死锁的问题上更普遍采用的是诊断并解除(jich)死锁的方法第45页/共100页第四十六页，共100页。2.死锁的诊断死锁的诊断(zhndun)与解除与解除n n死锁的诊断n n超时法n n事务等待(dngdi)图法 第46页/共100页第四十七页，共100页。(1)超时法超时法n n如果一个事务的等待时间超过了规定的时限，就认为发生如果一个事务的等待时间超过了规定的时限，就认为发生(fshng)(fshng)了死锁了死锁n n优点：实现简单优点：实现简单n n缺点缺点n n有可能误判死锁有可能误判死锁n n时限若设置得太长，死锁发生时限若设置得太长，死锁发生(fshng)(fshng)后不能及时发现后不能及时发现第47页/共100页第四十八页，共100页。(2)等待等待(dngdi)图法图法n n用事务等待图动态反映所有事务的等待情况用事务等待图动态反映所有事务的等待情况(qngkung)(qngkung)n n事务等待图是一个有向图事务等待图是一个有向图G=(TG=(T，U)U)n nT T为结点的集合，每个结点表示正运行的事务为结点的集合，每个结点表示正运行的事务n nU U为边的集合，每条边表示事务等待的情况为边的集合，每条边表示事务等待的情况(qngkung)(qngkung)n n若若T1T1等待等待T2T2，则，则T1T1，T2T2之间划一条有向边，从之间划一条有向边，从T1T1指向指向T2T2第48页/共100页第四十九页，共100页。等待等待(dngdi)图法（续）图法（续）事务等待图n图(a)中，事务T1等待(dngdi)T2，T2等待(dngdi)T1，产生了死锁n图(b)中，事务T1等待(dngdi)T2，T2等待(dngdi)T3，T3等待(dngdi)T4，T4又等待(dngdi)T1，产生了死锁 n图(b)中，事务T3可能还等待(dngdi)T2，在大回路中又有小的回路 第49页/共100页第五十页，共100页。等待等待(dngdi)图法（续）图法（续）n n并发控制子系统周期性地（比如(br)每隔数秒）生成事务等待图，检测事务。如果发现图中存在回路，则表示系统中出现了死锁。第50页/共100页第五十一页，共100页。死锁的诊断死锁的诊断(zhndun)与解除与解除（续）（续）n n解除死锁解除死锁n n选择一个处理死锁代价最小的事务，将其撤消选择一个处理死锁代价最小的事务，将其撤消n n释放释放(shfng)(shfng)此事务持有的所有的锁，使其它事务能继此事务持有的所有的锁，使其它事务能继续运行下去续运行下去第51页/共100页第五十二页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发并发(bngf)控制概述控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并并发发(bngf)调调度度的的可可串串行行性性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度11.7 小结小结第52页/共100页第五十三页，共100页。11.4 并发并发(bngf)调度的可串行调度的可串行性性n nDBMS对并发事务不同(b tn)的调度可能会产生不同(b tn)的结果n n什么样的调度是正确的？n n 第53页/共100页第五十四页，共100页。可串行化调度可串行化调度(diod)n n可串行化(Serializable)调度n n多个事务(shw)的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务(shw)时的结果相同n n可串行性(Serializability)n n是并发事务(shw)正确调度的准则n n一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度 第54页/共100页第五十五页，共100页。可串行化调度可串行化调度(diod)（续）（续）例现在有两个事务，分别包含下列操作：事务T1：读B；A=B+1；写回A事务T2：读A；B=A+1；写回B现给出对这两个事务不同(b tn)的调度策略 第55页/共100页第五十六页，共100页。串行化调度串行化调度(diod),正确的调正确的调度度(diod)T1T2Slock BY=R(B)=2Unlock BXlock AA=Y+1=3W(A)Unlock ASlock AX=R(A)=3Unlock AXlock BB=X+1=4W(B)Unlock B串行调度(diod)(a)n假设A、B的初值均为2。n按T1T2次序执行结果为A=3，B=4 n串行调度(diod)策略,正确的调度(diod)第56页/共100页第五十七页，共100页。串行化调度串行化调度(diod),正确的调正确的调度度(diod)T1T2Slock AX=R(A)=2Unlock AXlock BB=X+1=3W(B)Unlock BSlock BY=R(B)=3Unlock BXlock AA=Y+1=4W(A)Unlock A串行调度(diod)(b)n假设A、B的初值均为2。nT2T1次序执行结果(ji gu)为B=3，A=4 n串行调度策略,正确的调度 第57页/共100页第五十八页，共100页。不可不可(bk)串行化调度，错误的串行化调度，错误的调度调度T1T2Slock BY=R(B)=2Slock AX=R(A)=2Unlock BUnlock AXlock AA=Y+1=3W(A)Xlock BB=X+1=3W(B)Unlock AUnlock B不可(bk)串行化的调度 n执行结果(ji gu)与(a)、(b)的结果(ji gu)都不同n是错误的调度 第58页/共100页第五十九页，共100页。可串行化调度可串行化调度(diod)，正确的，正确的调度调度(diod)T1T2Slock BY=R(B)=2Unlock BXlock ASlock AA=Y+1=3等待W(A)等待Unlock A等待X=R(A)=3Unlock AXlock BB=X+1=4W(B)Unlock B可串行化的调度(diod)n执行结果与串行调度(diod)(a)的执行结果相同n是正确的调度(diod)第59页/共100页第六十页，共100页。冲突冲突(chngt)可串行化调度可串行化调度n n可串行化调度的充分条件n n一个调度Sc在保证冲突操作的次序不变的情况下，通过交换两个事务不冲突操作的次序得到(d do)另一个调度Sc，如果Sc是串行的，称调度Sc为冲突可串行化的调度n n一个调度是冲突可串行化，一定是可串行化的调度第60页/共100页第六十一页，共100页。冲突冲突(chngt)可串行化调度可串行化调度（续）（续）冲突操作冲突操作冲突操作冲突操作冲突操作是指不同的事务对同一个数据冲突操作是指不同的事务对同一个数据冲突操作是指不同的事务对同一个数据冲突操作是指不同的事务对同一个数据(shj)(shj)的读写操作和写写操作的读写操作和写写操作的读写操作和写写操作的读写操作和写写操作Ri(x)Ri(x)与与与与Wj(x)Wj(x)/*/*事务事务事务事务TiTi读读读读x x，TjTj写写写写x*/x*/Wi(x)Wi(x)与与与与Wj(x)Wj(x)/*/*事务事务事务事务TiTi写写写写x x，TjTj写写写写x*/x*/其他操作是不冲突操作其他操作是不冲突操作其他操作是不冲突操作其他操作是不冲突操作不同事务的冲突操作和同一事务的两个操作不能交换不同事务的冲突操作和同一事务的两个操作不能交换不同事务的冲突操作和同一事务的两个操作不能交换不同事务的冲突操作和同一事务的两个操作不能交换(Swap)(Swap)第61页/共100页第六十二页，共100页。冲突冲突(chngt)可串行化调度可串行化调度（续）（续）例今有调度例今有调度Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)把把w2(A)w2(A)与与r1(B)w1(B)r1(B)w1(B)交换，得到：交换，得到：r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)再把再把r2(A)r2(A)与与r1(B)w1(B)r1(B)w1(B)交换：交换：Sc2 Sc2r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)Sc2Sc2等价等价(dngji)(dngji)于一个串行调度于一个串行调度T1T1，T2T2，Sc1Sc1冲突可串行化冲突可串行化的调度的调度第62页/共100页第六十三页，共100页。冲突冲突(chngt)可串行化调度可串行化调度（续）（续）n n冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化条件的可串行化调度。件的可串行化调度。n n 例例 有有3 3个事务个事务(shw)(shw)n n T1=W1(Y)W1(X)T1=W1(Y)W1(X)，T2=W2(Y)W2(X)T2=W2(Y)W2(X)，T3=W3(X)T3=W3(X)n n调度调度L1=W1(Y)W1(X)W2(Y)W2(X)W3(X)L1=W1(Y)W1(X)W2(Y)W2(X)W3(X)是一个串行调度。是一个串行调度。n n调度调度L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)L2=W1(Y)W2(Y)W2(X)W1(X)W3(X)不满足冲突可串行化。但是调度不满足冲突可串行化。但是调度L2L2是可串行化的，因是可串行化的，因为为L2L2执行的结果与调度执行的结果与调度L1L1相同，相同，Y Y的值都等于的值都等于T2T2的值，的值，X X的值都等于的值都等于T3T3的值的值 第63页/共100页第六十四页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发控制概述并发控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并发调度的可串行性并发调度的可串行性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度(l d)11.7 小结小结第64页/共100页第六十五页，共100页。11.5 两段锁协议两段锁协议(xiy)n n封锁协议封锁协议n n 运用封锁方法时，对数据运用封锁方法时，对数据(shj)(shj)对象加锁时需要约定一些规则对象加锁时需要约定一些规则 n n何时申请封锁何时申请封锁n n持锁时间持锁时间n n何时释放封锁等何时释放封锁等n n两段封锁协议两段封锁协议(Two-Phase Locking(Two-Phase Locking，简称，简称2PL)2PL)是最常用的一种封锁协议，理论上证明使用两段封锁协议是最常用的一种封锁协议，理论上证明使用两段封锁协议产生的是可串行化调度产生的是可串行化调度第65页/共100页第六十六页，共100页。两段锁协议两段锁协议(xiy)（续）（续）n n两段锁协议n n 指所有事务必须分两个阶段对数据项加锁和解锁 n n在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁n n 在释放一个封锁之后，事务不再(b zi)申请和获得任何其他封锁第66页/共100页第六十七页，共100页。两段锁协议两段锁协议(xiy)（续）（续）n n“两段两段”锁的含义锁的含义n n事务分为两个事务分为两个(li(li n n )阶段阶段n n 第一阶段是获得封锁，也称为扩展阶段第一阶段是获得封锁，也称为扩展阶段n n事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁何锁 n n 第二阶段是释放封锁，也称为收缩阶段第二阶段是释放封锁，也称为收缩阶段n n事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁锁 第67页/共100页第六十八页，共100页。两段锁协议两段锁协议(xiy)（续）（续）例例事务事务TiTi遵守两段锁协议，其封锁遵守两段锁协议，其封锁(fn(fn su su)序列是序列是 ：Slock A Slock B Xlock C Unlock B Unlock A Unlock CSlock A Slock B Xlock C Unlock B Unlock A Unlock C；|扩展阶段扩展阶段|收缩阶段收缩阶段|事务事务TjTj不遵守两段锁协议，其封锁不遵守两段锁协议，其封锁(fn(fn su su)序列是：序列是：Slock A Unlock A Slock B Xlock C Unlock C Unlock BSlock A Unlock A Slock B Xlock C Unlock C Unlock B；第68页/共100页第六十九页，共100页。两段锁协议两段锁协议(xiy)（续）（续）事务T1事务T2Slock(A)R(A=260)Slock(C)R(C=300)Xlock(A)W(A=160)Xlock(C)W(C=250)Slock(A)Slock(B)等待R(B=1000)等待Xlock(B)等待W(B=1100)等待Unlock(A)等待R(A=160)Xlock(A)Unlock(B)W(A=210)Unlock(C)遵守两段锁协议(xiy)的可串行化调度n左图的调度是遵守两段锁协议的，因此(ync)一定是一个可串行化调度。第69页/共100页第七十页，共100页。两段锁协议两段锁协议(xiy)（续）（续）n n事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。n n若并发若并发(bngf)(bngf)事务都遵守两段锁协议，则对这些事务的任何并发事务都遵守两段锁协议，则对这些事务的任何并发(bngf)(bngf)调度策略都是可串行化的调度策略都是可串行化的n n若并发若并发(bngf)(bngf)事务的一个调度是可串行化的，不一定所有事务都符合两段事务的一个调度是可串行化的，不一定所有事务都符合两段锁协议锁协议 第70页/共100页第七十一页，共100页。两段锁协议两段锁协议(xiy)（续）（续）n n两段锁协议与防止死锁的一次封锁法n n一次封锁法要求每个事务(shw)必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议n n但是两段锁协议并不要求事务(shw)必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务(shw)可能发生死锁第71页/共100页第七十二页，共100页。两段锁协议两段锁协议(xiy)（续）（续）例例 遵守两段锁协议遵守两段锁协议(xiy)(xiy