数据库系统概论王珊chp学习教案.pptx

《数据库系统概论王珊chp学习教案.pptx》由会员分享，可在线阅读，更多相关《数据库系统概论王珊chp学习教案.pptx（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据库系统概论数据库系统概论(giln)王珊王珊chp第一页，共100页。问题问题(wnt)的产生的产生n n多用户(yngh)数据库系统的存在n n 允许多个用户(yngh)同时使用的数据库系统n n飞机定票数据库系统n n银行数据库系统 n n特点：在同一时刻并发运行的事务数可达数百个 第1页/共100页第二页，共100页。问题问题(wnt)的产生（续）的产生（续）n n不同的多事务不同的多事务(shw)(shw)执行方式执行方式 n n (1)(1)事务事务(shw)(shw)串行执行串行执行n n每每个个时时刻刻只只有有一一个个事事务务(shw)(shw)运运行行，其其他他事事

2、务务(shw)(shw)必必须须等等到到这这个个事事务务(shw)(shw)结结束束以以后方能运行后方能运行n n不不能能充充分分利利用用系系统统资资源源，发发挥挥数数据据库库共共享享资资源的特点源的特点T1T2T3事务的串行执行(zhxng)方式第2页/共100页第三页，共100页。问题问题(wnt)的产生（续）的产生（续）(2)(2)交叉并发方式（交叉并发方式（Interleaved ConcurrencyInterleaved Concurrency）在在单单处处理理机机系系统统中中，事事务务的的并并行行执执行行是是这这些些(zhxi)(zhxi)并并行行事事务务的的并并行行操操作作轮轮

3、流流交交叉叉运行运行单单处处理理机机系系统统中中的的并并行行事事务务并并没没有有真真正正地地并并行行运运行行，但但能能够够减减少少处处理理机机的的空空闲闲时时间，提高系统的效率间，提高系统的效率第3页/共100页第四页，共100页。问题问题(wnt)的产生（续）的产生（续）事务的交叉并发(bngf)执行方式第4页/共100页第五页，共100页。问题问题(wnt)的产生（续）的产生（续）(3)同时并发方式（simultaneous concurrency）多处理机系统中，每个处理机可以运行一个事务，多个处理机可以同时运行多个事务，实现多个事务真正(zhnzhng)的并行运行第5页/共100页第六

4、页，共100页。问题问题(wnt)的产生（续）的产生（续）n n事务并发执行带来的问题(wnt)n n会产生多个事务同时存取同一数据的情况 n n可能会存取和存储不正确的数据，破坏事务一致性和数据库的一致性第6页/共100页第七页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发控制概述并发控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并发调度的可串行性并发调度的可串行性11.5 两段锁协议两段锁协议(xiy)11.6 封锁的粒度封锁的粒度11.7 小结小结第7页/共100页第八页，共100页。11.1 并发并发(bngf)控制概述控制概述n n并发

5、控制机制的任务n n对并发操作进行正确调度(diod)n n保证事务的隔离性n n保证数据库的一致性第8页/共100页第九页，共100页。T1T1的修改的修改的修改的修改(xig(xig i)i)被被被被T2T2覆盖了！覆盖了！覆盖了！覆盖了！并发(bngf)控制概述（续）并发操作并发操作并发操作并发操作(cozu)(cozu)带来数据的不一致性实例带来数据的不一致性实例带来数据的不一致性实例带来数据的不一致性实例 例例例例11飞机订票系统中的一个活动序列飞机订票系统中的一个活动序列飞机订票系统中的一个活动序列飞机订票系统中的一个活动序列 甲售票点甲售票点甲售票点甲售票点(甲事务甲事务甲事务甲

6、事务)读出某航班的机票余额读出某航班的机票余额读出某航班的机票余额读出某航班的机票余额A A，设，设，设，设A=16A=16；乙售票点乙售票点乙售票点乙售票点(乙事务乙事务乙事务乙事务)读出同一航班的机票余额读出同一航班的机票余额读出同一航班的机票余额读出同一航班的机票余额A A，也为，也为，也为，也为1616；甲售票点卖出一张机票，修改余额甲售票点卖出一张机票，修改余额甲售票点卖出一张机票，修改余额甲售票点卖出一张机票，修改余额AA-1AA-1，所以，所以，所以，所以A A为为为为1515，把，把，把，把A A写回数据库；写回数据库；写回数据库；写回数据库；乙售票点也卖出一张机票，修改余额乙

7、售票点也卖出一张机票，修改余额乙售票点也卖出一张机票，修改余额乙售票点也卖出一张机票，修改余额AA-1AA-1，所以，所以，所以，所以A A为为为为1515，把，把，把，把A A写回数据库写回数据库写回数据库写回数据库 结果明明卖出两张机票，数据库中机票余额只减少结果明明卖出两张机票，数据库中机票余额只减少结果明明卖出两张机票，数据库中机票余额只减少结果明明卖出两张机票，数据库中机票余额只减少1 1 第9页/共100页第十页，共100页。并发控制并发控制(kngzh)概述（续）概述（续）n n这种情况称为数据库的不一致性，是由并发操作引起这种情况称为数据库的不一致性，是由并发操作引起(y(y

8、nqnq)的。的。n n在并发操作情况下，对甲、乙两个事务的操作序列的调度是随机的。在并发操作情况下，对甲、乙两个事务的操作序列的调度是随机的。n n若按上面的调度序列执行，甲事务的修改就被丢失。若按上面的调度序列执行，甲事务的修改就被丢失。n n原因：第原因：第4 4步中乙事务修改步中乙事务修改A A并写回后覆盖了甲事务的修改并写回后覆盖了甲事务的修改第10页/共100页第十一页，共100页。并发控制并发控制(kngzh)概述（续）概述（续）n n并发操作并发操作(cozu)(cozu)带来的数据不一致性带来的数据不一致性n n丢失修改（丢失修改（Lost UpdateLost Update

9、）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的 提 交(tjio)结 果 破 坏 了 T1提 交(tjio)的结果，导致T1的修改被丢失。n n上面飞机订票例子就属此类 第12页/共100页第十三页，共100页。丢失丢失(dis)修改（续

10、）修改（续）T1T2 R(A)=16R(A)=16 AA-1 W(A)=15WAA-1W(A)=15丢失(dis)修改第13页/共100页第十四页，共100页。2.不可不可(bk)重复读重复读n n不可重复读是指事务(shw)T1读取数据后，事务(shw)T2n n 执行更新操作，使T1无法再现前一次读取结果。第14页/共100页第十五页，共100页。不可不可(bk)重复读（续）重复读（续）n n不可重复读包括三种(sn zhn)情况：n n(1)事务T1读取某一数据后，事务T2对其做了修改，当事务T1再次读该数据时，得到与前一次不同的值 第15页/共100页第十六页，共100页。不可不可(b

11、k)重复读（续）重复读（续）n nT1T1读取读取B=100B=100进行运算进行运算n nT2T2读取同一数据读取同一数据B B，对其进行修，对其进行修改后将改后将B=200B=200写回数据库。写回数据库。n nT1T1为了对读取值校对重读为了对读取值校对重读(zhngd)B(zhngd)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)

12、重复读（续）重复读（续）(2)(2)事务事务T1T1按一定按一定(ydng)(ydng)条件从数据库中读取了某些数据记录条件从数据库中读取了某些数据记录后，事务后，事务T2T2删除了其中部分记录，当删除了其中部分记录，当T1T1再次按相同条件读再次按相同条件读取数据时，发现某些记录消失了取数据时，发现某些记录消失了 (3)(3)事务事务T1T1按一定按一定(ydng)(ydng)条件从数据库中读取某些数据记录后，条件从数据库中读取某些数据记录后，事务事务T2T2插入了一些记录，当插入了一些记录，当T1T1再次按相同条件读取数据时，再次按相同条件读取数据时，发现多了一些记录。发现多了一些记录。后

13、两种不可重复读有时也称为幻影现象（后两种不可重复读有时也称为幻影现象（Phantom RowPhantom Row）第17页/共100页第十八页，共100页。3.读读“脏脏”数据数据(shj)读“脏”数据是指：事务T1修改(xigi)某一数据，并将其写回磁盘事务T2读取同一数据后，T1由于某种原因被撤销这时T1已修改(xigi)过的数据恢复原值，T2读到的数据就与数据库中的数据不一致T2读到的数据就为“脏”数据，即不正确的数据 第18页/共100页第十九页，共100页。读读“脏脏”数据数据(shj)（续）（续）T1T2 R(C)=100 CC*2 W(C)=200R(C)=200ROLLBAC

14、K C恢复为100例如(lr)读“脏”数据(shj)nT1将C值修改为200，T2读到C为200nT1由于某种原因撤销，其修改作废，C恢复原值100n这时T2读到的C为200，与数据库内容不一致，就是“脏”数据 第19页/共100页第二十页，共100页。并发控制并发控制(kngzh)概述（续）概述（续）n n数据不一致性：由于并发操作破坏了事务的隔离性n n并发控制就是要用正确的方式调度并发操作，使一个(y)用户事务的执行不受其他事务的干扰，从而避免造成数据的不一致性 第20页/共100页第二十一页，共100页。并发并发(bngf)控制概述（续）控制概述（续）n n并发控制的主要技术(jsh)

15、n n有封锁(Locking)n n时间戳(Timestamp)n n乐观控制法n n商用的DBMS一般都采用封锁方法 第21页/共100页第二十二页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发并发(bngf)控制概述控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并并发发(bngf)调调度度的的可可串串行行性性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度11.7 小结小结第22页/共100页第二十三页，共100页。11.2 封锁封锁(fn su)n n什么是封锁(fn su)n n基本封锁(fn su)类型n n锁的相容矩阵第2

16、3页/共100页第二十四页，共100页。什么什么(shn me)是封锁是封锁n n封锁(fn su)就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁n n加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。第24页/共100页第二十五页，共100页。基本封锁基本封锁(fn su)类型类型n n一个事务对某个数据对象加锁后究竟拥有一个事务对某个数据对象加锁后究竟拥有(yngy(yngy u)u)什么样的控制由封锁的类什么样的控制由封锁的类型决定。型决定。n n基本封锁类型基本封锁类型n n排它锁（排它锁（Exclusiv

17、e LocksExclusive Locks，简记为，简记为X X锁）锁）n n共享锁（共享锁（Share LocksShare Locks，简记为，简记为S S锁）锁）第25页/共100页第二十六页，共100页。排它锁排它锁n n排它锁又称为写锁n n若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型(lixng)的锁，直到T释放A上的锁n n保证其他事务在T释放A上的锁之前不能再读取和修改A 第26页/共100页第二十七页，共100页。共享锁共享锁n n共享锁又称为读锁n n若事务T对数据对象A加上S锁，则其它事务只能再对A加S锁，而不能加X锁，直到(

18、zhdo)T释放A上的S锁n n保证其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改 第27页/共100页第二十八页，共100页。锁的相容锁的相容(xin rn)矩阵矩阵Y=Yes，相容的请求N=No，不相容的请求T1T2XS-XNNYSNYY-YYY第28页/共100页第二十九页，共100页。锁的相容锁的相容(xin rn)矩阵（续）矩阵（续）在锁的相容矩阵中：在锁的相容矩阵中：最左边一列表示事务最左边一列表示事务T1T1已经获得的数据对象上的锁的类型，其中横线表示没有已经获得的数据对象上的锁的类型，其中横线表示没有(mi y(mi y u)u)加锁。加锁。最上面一行表示另一事务

19、最上面一行表示另一事务T2T2对同一数据对象发出的封锁请求。对同一数据对象发出的封锁请求。T2T2的封锁请求能否被满足用矩阵中的的封锁请求能否被满足用矩阵中的Y Y和和NN表示表示Y Y表示事务表示事务T2T2的封锁要求与的封锁要求与T1T1已持有的锁相容，封锁请求可以满足已持有的锁相容，封锁请求可以满足NN表示表示T2T2的封锁请求与的封锁请求与T1T1已持有的锁冲突，已持有的锁冲突，T2T2的请求被拒绝的请求被拒绝第29页/共100页第三十页，共100页。使用封锁机制使用封锁机制(jzh)解决丢失解决丢失修改问题修改问题T1T2 Xlock A R(A)=16Xlock A AA-1等待

20、W(A)=15等待 Commit等待 Unlock A等待获得Xlock AR(A)=15AA-1W(A)=14CommitUnlock A例：n事务T1在读A进行(jnxng)修改之前先对A加X锁n当T2再请求对A加X锁时被拒绝nT2只能等待T1释放A上的锁后T2获得对A的X锁n这时T2读到的A已经是T1更新过的值15nT2按此新的A值进行(jnxng)运算，并将结果值A=14送回到磁盘。避免了丢失T1的更新。没有丢失(dis)修改第30页/共100页第三十一页，共100页。使用封锁机制使用封锁机制(jzh)解决不可重复读问题解决不可重复读问题T1T2 Slock ASlock BR(A)=

21、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在读A，B之前，先对A，B加S锁n其他事务只能再对A，B加S锁，而不能加X锁，即其他事务只能读A，B，而不能修改(xigi)n当T2为修改(xigi)B而申请对B的X锁时被拒绝只能等待T1释放B上的锁nT1为验算再读A，B，这时读出的B仍是100，求和结果仍为150，即可重复读nT1结束才释放A，B上的S锁。T2才获得对B的X锁 可重复(

22、chngf)读第31页/共100页第三十二页，共100页。使用封锁机制解决使用封锁机制解决(jiju)读读“脏脏”数据问题数据问题T1T2 Xlock CR(C)=100CC*2W(C)=200Slock C等待 ROLLBACK等待(C恢复为100)等待Unlock C等待获得Slock CR(C)=100Commit CUnlock C例n事务T1在对C进行(jnxng)修改之前，先对C加X锁，修改其值后写回磁盘nT2请求在C上加S锁，因T1已在C上加了X锁，T2只能等待nT1因某种原因被撤销，C恢复为原值100nT1释放C上的X锁后T2获得C上的S锁，读C=100。避免了T2读“脏”数据

23、不读“脏”数据(shj)第32页/共100页第三十三页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发控制并发控制(kngzh)概述概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并发调度的可串行性并发调度的可串行性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度11.7 小结小结第33页/共100页第三十四页，共100页。11.3 活锁和死锁活锁和死锁n n封锁技术(jsh)可以有效地解决并行操作的一致性问题，但也带来一些新的问题n n死锁n n活锁第34页/共100页第三十五页，共100页。活锁活锁n n事务事务T1T1封锁了数据封锁了数

24、据R Rn n事务事务T2T2又请求封锁又请求封锁R R，于是，于是T2T2等待。等待。n nT3T3也请求封锁也请求封锁R R，当，当T1T1释放了释放了R R上的封锁之后系统首先批准上的封锁之后系统首先批准(p zh(p zh n)n)了了T3T3的请的请求，求，T2T2仍然等待。仍然等待。n nT4T4又请求封锁又请求封锁R R，当，当T3T3释放了释放了R R上的封锁之后系统又批准上的封锁之后系统又批准(p zh(p zh n)n)了了T4T4的请求的请求n nT2T2有可能永远等待，这就是活锁的情形有可能永远等待，这就是活锁的情形 第35页/共100页第三十六页，共100页。活锁（续

25、）活锁（续）活 锁第36页/共100页第三十七页，共100页。活锁（续）活锁（续）n n避免活锁：采用先来先服务的策略避免活锁：采用先来先服务的策略n n当多个事务请求封锁当多个事务请求封锁(fn(fn su su)同一数据对象时同一数据对象时n n按请求封锁按请求封锁(fn(fn su su)的先后次序对这些事务排队的先后次序对这些事务排队n n该该数数据据对对象象上上的的锁锁一一旦旦释释放放，首首先先批批准准申申请请队队列列中中第第一一个个事事务务获获得锁得锁第37页/共100页第三十八页，共100页。死锁死锁n n事务事务T1T1封锁封锁(fn(fn su su)了数据了数据R1R1n

26、nT2T2封锁封锁(fn(fn su su)了数据了数据R2R2n nT1T1又请求封锁又请求封锁(fn(fn su su)R2)R2，因，因T2T2已封锁已封锁(fn(fn su su)了了R2R2，于是，于是T1T1等待等待T2T2释放释放R2R2上上的锁的锁n n接着接着T2T2又申请封锁又申请封锁(fn(fn su su)R1)R1，因，因T1T1已封锁已封锁(fn(fn su su)了了R1R1，T2T2也只能等待也只能等待T1T1释释放放R1R1上的锁上的锁n n这样这样T1T1在等待在等待T2T2，而，而T2T2又在等待又在等待T1T1，T1T1和和T2T2两个事务永远不能结束，

27、形成死锁两个事务永远不能结束，形成死锁 第38页/共100页第三十九页，共100页。死锁（续）死锁（续）T1T2lock R1Lock R2Lock R2.等待等待Lock R1等待等待等待等待死 锁第39页/共100页第四十页，共100页。解决解决(jiju)死锁的方法死锁的方法两类方法两类方法1.1.预防死锁预防死锁2.2.死锁的诊断死锁的诊断(zhndun)(zhndun)与解除与解除第40页/共100页第四十一页，共100页。1.死锁的预防死锁的预防(yfng)n n产生产生(ch(ch nshng)nshng)死锁的原因是两个或多个事务都已封锁了一些数据对象，然后又都请求对死锁的原因

28、是两个或多个事务都已封锁了一些数据对象，然后又都请求对已为其他事务封锁的数据对象加锁，从而出现死等待。已为其他事务封锁的数据对象加锁，从而出现死等待。n n预防死锁的发生就是要破坏产生预防死锁的发生就是要破坏产生(ch(ch nshng)nshng)死锁的条件死锁的条件第41页/共100页第四十二页，共100页。死锁的预防死锁的预防(yfng)（续）（续）预防(yfng)死锁的方法 一次封锁法 顺序封锁法第42页/共100页第四十三页，共100页。(1)一次封锁一次封锁(fn su)法法n n要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行n n存在的问题n n降低系统并发度

29、n n难于事先精确确定封锁(fn su)对象第43页/共100页第四十四页，共100页。(2)顺序顺序(shnx)封锁法封锁法n n顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实顺序封锁法是预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。行封锁。n n顺序封锁法存在的问题顺序封锁法存在的问题n n维护成本维护成本n n 数据库系统中封锁的数据对象极多，并且数据库系统中封锁的数据对象极多，并且(bngqi)(bngqi)在不断地变化。在不断地变化。n n难以实现：很难事先确定每一个事务要封锁哪些对象难以实现：很难事先确定每一个事务要封锁哪些对象n n 第44页/

30、共100页第四十五页，共100页。死锁的预防死锁的预防(yfng)（续）（续）n n结论n n在操作系统中广为采用的预防死锁的策略并不很适合数据库的特点n nDBMS在解决死锁的问题上更普遍采用的是诊断并解除(jich)死锁的方法第45页/共100页第四十六页，共100页。2.死锁的诊断死锁的诊断(zhndun)与解除与解除n n死锁的诊断(zhndun)n n超时法n n事务等待图法 第46页/共100页第四十七页，共100页。(1)超时法超时法n n如果一个事务的等待时间超过了规定如果一个事务的等待时间超过了规定(gudng)(gudng)的时的时限，就认为发生了死锁限，就认为发生了死锁n

31、 n优点：实现简单优点：实现简单n n缺点缺点n n有可能误判死锁有可能误判死锁n n时限若设置得太长，死锁发生后不能及时发现时限若设置得太长，死锁发生后不能及时发现第47页/共100页第四十八页，共100页。(2)等待等待(dngdi)图法图法n n用事务等待图动态反映所有事务的等待情况用事务等待图动态反映所有事务的等待情况n n事务等待图是一个有向图事务等待图是一个有向图G=(TG=(T，U)U)n nT T为结点的集合，每个结点表示正运行为结点的集合，每个结点表示正运行(ynxng)(ynxng)的事务的事务n nU U为边的集合，每条边表示事务等待的情况为边的集合，每条边表示事务等待的

32、情况n n若若T1T1等待等待T2T2，则，则T1T1，T2T2之间划一条有向边，从之间划一条有向边，从T1T1指向指向T2T2第48页/共100页第四十九页，共100页。等待等待(dngdi)图法（续）图法（续）事务等待图n图(a)中，事务T1等待T2，T2等待T1，产生(chnshng)了死锁n图(b)中，事务T1等待T2，T2等待T3，T3等待T4，T4又等待T1，产生(chnshng)了死锁 n图(b)中，事务T3可能还等待T2，在大回路中又有小的回路 第49页/共100页第五十页，共100页。等待等待(dngdi)图法（续）图法（续）n n并发控制子系统(xtng)周期性地（比如每隔

33、数秒）生成事务等待图，检测事务。如果发现图中存在回路，则表示系统(xtng)中出现了死锁。第50页/共100页第五十一页，共100页。死锁的诊断死锁的诊断(zhndun)与解除与解除（续）（续）n n解除死锁解除死锁n n选择一个处理死锁代价最小的事务，将其撤消选择一个处理死锁代价最小的事务，将其撤消n n释放释放(shfng)(shfng)此事务持有的所有的锁，使其它事务能继续此事务持有的所有的锁，使其它事务能继续运行下去运行下去第51页/共100页第五十二页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发控制概述并发控制概述11.2 封锁封锁(fn su)11.3

34、 活锁和死锁活锁和死锁11.4 并发调度的可串行性并发调度的可串行性11.5 两段锁协议两段锁协议11.6 封锁封锁(fn su)的粒度的粒度11.7 小结小结第52页/共100页第五十三页，共100页。11.4 并发并发(bngf)调度的可串行调度的可串行性性n nDBMS对并发事务(shw)不同的调度可能会产生不同的结果n n什么样的调度是正确的？n n 第53页/共100页第五十四页，共100页。可串行化调度可串行化调度(diod)n n可串行化(Serializable)调度n n多个事务(shw)的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务(shw)时的结果相同n

35、 n可串行性(Serializability)n n是并发事务(shw)正确调度的准则n n一个给定的并发调度，当且仅当它是可串行化的，才认为是正确调度 第54页/共100页第五十五页，共100页。可串行化调度可串行化调度(diod)（续）（续）例现在有两个事务，分别包含下列操作：事务T1：读B；A=B+1；写回A事务T2：读A；B=A+1；写回B现给出对这两个事务不同的调度(diod)策略 第55页/共100页第五十六页，共100页。串行化调度串行化调度(diod),正确的调正确的调度度(diod)T1T2Slock BY=R(B)=2Unlock BXlock AA=Y+1=3W(A)Un

36、lock ASlock AX=R(A)=3Unlock AXlock BB=X+1=4W(B)Unlock B串行调度(diod)(a)n假设A、B的初值均为2。n按T1T2次序执行(zhxng)结果为A=3，B=4 n串行调度策略,正确的调度 第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的

37、初值均为2。nT2T1次序执行结果为B=3，A=4 n串行调度(diod)策略,正确的调度(diod)第57页/共100页第五十八页，共100页。不可串行化调度不可串行化调度(diod)，错误，错误的调度的调度(diod)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页。可串行化调度可串行化调

38、度(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执行结果与串行调度(a)的执行结果相同(xin tn)n是正确的调度 第59页/共100页第六十页，共100页。冲突冲突(chngt)可串行化调度可串行化调度n n可串行化调度的充分条件n n一个调度Sc在保证冲突操作(cozu)的次序不变的情况下，通过交换两个事务不冲突操作(cozu)的次序得到另一个调

39、度Sc，如果Sc是串行的，称调度Sc为冲突可串行化的调度n n一个调度是冲突可串行化，一定是可串行化的调度第60页/共100页第六十一页，共100页。冲突冲突(chngt)可串行化调度可串行化调度（续）（续）冲突操作冲突操作冲突操作冲突操作冲突操作是指不同的事务对同一个数据的读写操作和写写操作冲突操作是指不同的事务对同一个数据的读写操作和写写操作冲突操作是指不同的事务对同一个数据的读写操作和写写操作冲突操作是指不同的事务对同一个数据的读写操作和写写操作Ri(x)Ri(x)与与与与Wj(x)Wj(x)/*/*事务事务事务事务TiTi读读读读x x，TjTj写写写写x*/x*/Wi(x)Wi(x)

40、与与与与Wj(x)Wj(x)/*/*事务事务事务事务TiTi写写写写x x，TjTj写写写写x*/x*/其他操作是不冲突操作其他操作是不冲突操作其他操作是不冲突操作其他操作是不冲突操作不同事务的冲突操作和同一事务的两个不同事务的冲突操作和同一事务的两个不同事务的冲突操作和同一事务的两个不同事务的冲突操作和同一事务的两个(li(li n n )操作不能交换操作不能交换操作不能交换操作不能交换(Swap)(Swap)第61页/共100页第六十二页，共100页。冲突冲突(chngt)可串行化调度可串行化调度（续）（续）例今有调度例今有调度(diod)Sc1=r1(A)w1(A)r2(A)w2(A)r

41、1(B)w1(B)r2(B)w2(B)(diod)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)w

42、1(B)r2(A)w2(A)r2(B)w2(B)Sc2Sc2等价于一个串行调度等价于一个串行调度(diod)T1(diod)T1，T2T2，Sc1Sc1冲突可串行化的调度冲突可串行化的调度(diod)(diod)第62页/共100页第六十三页，共100页。冲突冲突(chngt)可串行化调度可串行化调度（续）（续）n n冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足冲突可串行化调度是可串行化调度的充分条件，不是必要条件。还有不满足(m(m nz)nz)冲冲突可串行化条件的可串行化调度。突可串行化条件的可串行化调度。n n 例例 有有3 3个事务个事务n n T1=W1(Y)W

43、1(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)不满足不满足(m(m nz)nz)冲突可串行化。但是调度冲突可串行化。但是调度L2L2是可是可串行化的，因为串行化的，因为L2L2执行的结果与调度执行的结果与调度L1L1相同，相同，Y Y的值都

44、等于的值都等于T2T2的值，的值，X X的值都等于的值都等于T3T3的的值值 第63页/共100页第六十四页，共100页。第十一章第十一章 并发并发(bngf)控制控制11.1 并发并发(bngf)控制概述控制概述11.2 封锁封锁11.3 活锁和死锁活锁和死锁11.4 并并发发(bngf)调调度度的的可可串串行行性性11.5 两段锁协议两段锁协议11.6 封锁的粒度封锁的粒度11.7 小结小结第64页/共100页第六十五页，共100页。11.5 两段锁协议两段锁协议(xiy)n n封锁协议封锁协议n n 运用运用(ynyng)(ynyng)封锁方法时，对数据对象加锁时需要约定一些规则封锁方法

45、时，对数据对象加锁时需要约定一些规则 n n何时申请封锁何时申请封锁n n持锁时间持锁时间n n何时释放封锁等何时释放封锁等n n两段封锁协议两段封锁协议(Two-Phase Locking(Two-Phase Locking，简称，简称2PL)2PL)是最常用的一种封锁协议，理论上证明是最常用的一种封锁协议，理论上证明使用两段封锁协议产生的是可串行化调度使用两段封锁协议产生的是可串行化调度第65页/共100页第六十六页，共100页。两段锁协议两段锁协议(xiy)（续）（续）n n两段锁协议n n 指所有事务必须分两个阶段(jidun)对数据项加锁和解锁 n n在对任何数据进行读、写操作之前，

46、事务首先要获得对该数据的封锁n n 在释放一个封锁之后，事务不再申请和获得任何其他封锁第66页/共100页第六十七页，共100页。两段锁协议两段锁协议(xiy)（续）（续）n n“两段两段”锁的含义锁的含义n n事务分为两个阶段事务分为两个阶段n n 第一阶段是获得封锁，也称为第一阶段是获得封锁，也称为(chn(chn wi)wi)扩展阶段扩展阶段n n事务可以申请获得任何数据项上的任何类型的锁，但是事务可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁不能释放任何锁 n n 第二阶段是释放封锁，也称为第二阶段是释放封锁，也称为(chn(chn wi)wi)收缩阶段收缩阶段n n事务可

47、以释放任何数据项上的任何类型的锁，但是不能事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁再申请任何锁 第67页/共100页第六十八页，共100页。两段锁协议两段锁协议(xiy)（续）（续）例例事务事务TiTi遵守两段锁协议，其封锁序列是遵守两段锁协议，其封锁序列是 ：Slock A Slock B Xlock C Unlock B Unlock A Unlock CSlock A Slock B Xlock C Unlock B Unlock A Unlock C；|扩展阶段扩展阶段(jidun)(jidun)|收缩阶段收缩阶段(jidun)|(jidun)|事务事务TjTj不遵

48、守两段锁协议，其封锁序列是：不遵守两段锁协议，其封锁序列是：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)等待Unlo

49、ck(A)等待R(A=160)Xlock(A)Unlock(B)W(A=210)Unlock(C)遵守两段锁协议(xiy)的可串行化调度n左图的调度是遵守两段锁协议的，因此(ync)一定是一个可串行化调度。第69页/共100页第七十页，共100页。两段锁协议两段锁协议(xiy)（续）（续）n n事务遵守两段锁协议是可串行化调度事务遵守两段锁协议是可串行化调度(diod)(diod)的充分条件，而不是必要条件。的充分条件，而不是必要条件。n n若并发事务都遵守两段锁协议，则对这些事务的任何并发调度若并发事务都遵守两段锁协议，则对这些事务的任何并发调度(diod)(diod)策略都是可串行化的策略

50、都是可串行化的n n若并发事务的一个调度若并发事务的一个调度(diod)(diod)是可串行化的，不一定所有事务都符合两段锁协议是可串行化的，不一定所有事务都符合两段锁协议 第70页/共100页第七十一页，共100页。两段锁协议两段锁协议(xiy)（续）（续）n n两段锁协议与防止死锁的一次封锁法n n一次封锁法要求(yoqi)每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行，因此一次封锁法遵守两段锁协议n n但是两段锁协议并不要求(yoqi)事务必须一次将所有要使用的数据全部加锁，因此遵守两段锁协议的事务可能发生死锁第71页/共100页第七十二页，共100页。两段锁协议两段锁协