数据库第11章并发控制.ppt

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

1、2022/12/30兰彬制作1第十一章第十一章 并发控制并发控制11.1并发控制概述并发控制概述11.2封锁封锁11.3封锁协议封锁协议11.4活锁和死锁活锁和死锁11.5并发调度的可串行性并发调度的可串行性11.6两段锁协议两段锁协议2022/12/30兰彬制作2并发控制概述并发控制概述多个事务执行方式主要有多个事务执行方式主要有2种：种：（1）事务串行执行）事务串行执行每每个个时时刻刻只只有有一一个个事事务务运运行行，其其他他事事务务必须等到这个事务结束以后方能运行必须等到这个事务结束以后方能运行不不能能充充分分利利用用系系统统资资源源，不不能能发发挥挥数数据据库共享资源的特点库共享资源的

2、特点2022/12/30兰彬制作3并发控制（续）并发控制（续）（2）事务并行（并发）执行）事务并行（并发）执行l单处理机系统中：单处理机系统中：交叉并发方式交叉并发方式所有并行事务的并行操作所有并行事务的并行操作轮流交叉运行轮流交叉运行能能够够减减少少处处理理机机的的空空闲闲时时间间，提提高高系系统统的的效率效率2022/12/30兰彬制作4并发控制（续）并发控制（续）（2）事务并行（并发）执行）事务并行（并发）执行l多处理机系统中：多处理机系统中：同时并发方式同时并发方式每每个个处处理理机机都都可可以以运运行行一一个个事事务务，多多个个处处理理机机可可以以同同时时运运行行多多个个事事务务，实

3、实现现多多个个事事务真正的并行运行务真正的并行运行最理想的并发方式，但受制于硬件环境最理想的并发方式，但受制于硬件环境2022/12/30兰彬制作5事务并发执行带来的问题事务并发执行带来的问题l可可能能会会存存取取和和存存储储不不正正确确的的数数据据，破破坏坏事事务务的隔离性和数据库的一致性的隔离性和数据库的一致性lDBMS必须提供并发控制机制必须提供并发控制机制l并并发发控控制制机机制制是是衡衡量量一一个个DBMS性性能能的的重重要要标志之一标志之一2022/12/30兰彬制作611.1 11.1 并发控制概述并发控制概述l并发控制机制的任务并发控制机制的任务对多个事务的并发操作进行正确调度

4、对多个事务的并发操作进行正确调度保证事务的隔离性保证事务的隔离性保证数据库的一致性保证数据库的一致性2022/12/30兰彬制作7T1的修改被的修改被T2覆盖了，数据库覆盖了，数据库中数据出现错误中数据出现错误读读A=20AA-1写回写回A=19读读A=20AA-1写回写回A=19事务事务T2事务事务T1数据不一致实例：飞机订票系统数据不一致实例：飞机订票系统2022/12/30兰彬制作8并发操作带来的数据不一致性并发操作带来的数据不一致性l丢失修改（丢失修改（lostupdate）l不可重复读（不可重复读（non-repeatableread）l读读“脏脏”数据（数据（dirtyread）数

5、据库的并发操作通常会带来数据库的并发操作通常会带来3个问题：个问题：2022/12/30兰彬制作91.丢失修改丢失修改l事务事务1与事务与事务2从数据库中读出同一数据从数据库中读出同一数据并修改，事务并修改，事务2的提交结果破坏了事务的提交结果破坏了事务1提交的结果，导致事务提交的结果，导致事务1的修改被丢失。的修改被丢失。2022/12/30兰彬制作10读读A=20AA-1写回写回A=19读读A=20AA-1写回写回A=19事务事务T2事务事务T1(a)丢失修改丢失修改图图11.1三种数据不一致性三种数据不一致性2022/12/30兰彬制作112.不可重复读不可重复读l事务事务1读取数据后，

6、事务读取数据后，事务2执行更新操作，执行更新操作，使事务使事务1无法再现前一次读取结果。无法再现前一次读取结果。2022/12/30兰彬制作12图图11.1三种数据不一致性三种数据不一致性(续续)读读B=100BB*2写回写回B=200读读A=50读读B=100求求和和=150读读A=50读读B=200求求和和=250(验算不对验算不对)T2T1(b)不可重复读不可重复读2022/12/30兰彬制作13不可重复读的不可重复读的3种情况种情况1.事务事务1读取某些数据后，读取某些数据后，事务事务2对其做了修改对其做了修改，当事务当事务1再次读该数据时，得到与前一次不同再次读该数据时，得到与前一次

7、不同的值的值2.事务事务1按照一定的条件，从数据库中读取了某按照一定的条件，从数据库中读取了某些数据记录后，些数据记录后，事务事务2删除了其中部分记录删除了其中部分记录，当事务当事务1再次读取数据时，发现某些记录神密再次读取数据时，发现某些记录神密地消失了。地消失了。2022/12/30兰彬制作14不可重复读的不可重复读的3种情况种情况3.事务事务1按照一定的条件，从数据库中读取了某按照一定的条件，从数据库中读取了某些数据记录后，些数据记录后，事务事务2插入了一些记录插入了一些记录，当事，当事务务1再次按相同条件读取数据时，发现多了一再次按相同条件读取数据时，发现多了一些记录。些记录。后两种不

8、可重复读有时也称为后两种不可重复读有时也称为幻影现象幻影现象2022/12/30兰彬制作153.读读“脏脏”数据数据l事务事务1修改修改某一数据，并将其某一数据，并将其写回写回磁盘上的磁盘上的数数据库据库中。中。l这样，事务这样，事务2读到的数据就与数据库中的数据读到的数据就与数据库中的数据不一致，是不正确的数据，又称为不一致，是不正确的数据，又称为“脏脏”数据数据。l事务事务2读取读取同一数据同一数据（被事务被事务1修改后的数据修改后的数据）后，后，事务事务1由于某种原因由于某种原因被撤消被撤消，这时事务，这时事务1已已修改过的数据恢复原值修改过的数据恢复原值2022/12/30兰彬制作16

9、图图11.1三种数据不一致性三种数据不一致性(续续)读读C=200读读C=100CC*2写回写回C=200ROLLBACKC恢复为恢复为100T2T1(c)读读“脏脏”数据数据2022/12/30兰彬制作1711.2封锁封锁l什么是封锁什么是封锁l封锁封锁是实现是实现并发控制并发控制的一个非常重要的技术。的一个非常重要的技术。封锁就是：事务封锁就是：事务T在对某个数据对象（例如在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，表、记录等）操作之前，先向系统发出请求，对其加锁；对其加锁；加锁后事务加锁后事务T就对该数据对象有了一定的控就对该数据对象有了一定的控制，在制，在事务事务T释

10、放它的锁之前释放它的锁之前，其它的事务其它的事务不能更新此数据对象不能更新此数据对象。2022/12/30兰彬制作18基本的封锁类型基本的封锁类型lDBMS通常提供了多种类型的封锁。一个事务通常提供了多种类型的封锁。一个事务对某个数据对象加锁后究竟拥有什么样的控制对某个数据对象加锁后究竟拥有什么样的控制是由封锁的类型决定的。是由封锁的类型决定的。l基本封锁类型基本封锁类型排它锁排它锁（eXclusivelock，简记为，简记为X锁锁）共享锁共享锁（Sharelock，简记为，简记为S锁锁）2022/12/30兰彬制作19封锁的封锁的2种类型种类型l排它锁排它锁写锁，写锁，X锁锁若事务若事务T对

11、数据对象对数据对象A加上加上S锁，则其它事锁，则其它事务务只能再对只能再对A加加S锁锁，而，而不能加不能加X锁锁，直到，直到T释放释放A上的上的S锁。锁。若事务若事务T对数据对象对数据对象A加上加上X锁，则只允许锁，则只允许T读取读取和和修改修改A，其它，其它任何事务都不能再对任何事务都不能再对A加加任何类型任何类型的锁的锁，直到，直到T释放释放A上的锁。上的锁。l共享锁共享锁读锁，读锁，S锁锁2022/12/30兰彬制作20封锁的相容矩阵封锁的相容矩阵Y=Yes，相容的请求，相容的请求N=No，不相容的请求，不相容的请求T2T1XS-XNNYSNYY-YYY2022/12/30兰彬制作211

12、1.3封锁协议封锁协议l在运用在运用X锁和锁和S锁对数据对象加锁时，需要约定锁对数据对象加锁时，需要约定一些规则：一些规则：封锁协议（封锁协议（LockingProtocol）l常用的封锁协议：常用的封锁协议：三级封锁协议三级封锁协议何时申请何时申请X锁或锁或S锁锁持锁时间持锁时间何时释放何时释放X锁或锁或S锁锁2022/12/30兰彬制作221.一级封锁协议一级封锁协议l事务事务T在在修改修改数据数据R之前必须先对其之前必须先对其加加X锁锁，直，直到该到该事务结束事务结束才释放才释放正常结束正常结束（COMMIT）非正常结束非正常结束（ROLLBACK）l一级封锁协议可一级封锁协议可防止丢失

13、修改防止丢失修改l在一级封锁协议中，如果只是读数据，不需要在一级封锁协议中，如果只是读数据，不需要加锁的，所以它加锁的，所以它不能保证不能保证可重复读可重复读和和不读不读“脏脏”数据数据。2022/12/30兰彬制作23T1T2XlockA获得获得读读A=16AA-1，写回写回A=15Commit,UnlockAXlockA等待等待等待等待获得获得XlockA读读A=15AA-1，写回，写回A=14Commit，UnlockA一级封锁协议：一级封锁协议：没有丢失修改没有丢失修改 2022/12/30兰彬制作24一级封锁协议：一级封锁协议：读读“脏脏”数据数据T1T2XlockA获得获得读读A=

14、16AA-1写回写回A=15RollbackUnlockA读读A=152022/12/30兰彬制作25一级封锁协议：一级封锁协议：不可重复读不可重复读T1T2读读A=50，读读B=100求和求和=150读读A=50，读读B=200求和求和=250（验算不对）（验算不对）XlockB，获得获得读读B=100BB*2，写回写回B=200Commit，UnlockB2022/12/30兰彬制作262.二级封锁协议二级封锁协议l二级封锁协议：二级封锁协议：l二级封锁协议可以二级封锁协议可以防止防止丢失修改丢失修改和和读读“脏脏”数据数据。一级封锁协议一级封锁协议+事务事务T在在读取读取数据数据R前必须

15、前必须先先加加S锁锁，读完后即可释放读完后即可释放S锁锁l在二级封锁协议中，由于读完数据后即可释放在二级封锁协议中，由于读完数据后即可释放S锁，所以它锁，所以它不能保证不能保证可重复读可重复读。2022/12/30兰彬制作27二级封锁协议：二级封锁协议：不读不读“脏脏”数据数据T1T2XlockC，读，读C=100CC*2，写回，写回C=200ROLLBACK(C恢复为恢复为100)UnlockCSlockC，等待等待等待等待等待等待等待等待获得获得SlockC，读，读C=100CommitC，UnlockC2022/12/30兰彬制作283.三级封锁协议三级封锁协议l三级封锁协议：三级封锁协

16、议：l三级封锁协议可三级封锁协议可防止防止丢失修改丢失修改、读脏数据读脏数据和和不不可重复读可重复读。一级封锁协议一级封锁协议+事务事务T在在读取读取数据数据R之前必须之前必须先对其先对其加加S锁锁，直到，直到事务结束事务结束才释放才释放S锁锁2022/12/30兰彬制作29三级封锁协议：三级封锁协议：可重复读可重复读T1T2SlockA，读，读A=50SlockB，读，读B=100，求和，求和=150读读A=50,读读B=100,求和求和=150CommitUnlockA，UnlockBXlockB等待等待等待等待等待等待等待等待获得获得XlockB读读B=100，BB*2写回写回B=200

17、Commit，UnlockB2022/12/30兰彬制作30表表11.1不同级别的封锁协议不同级别的封锁协议X锁锁S锁锁一致性保证一致性保证操作操作结束结束释放释放事务事务结束结束释放释放操作操作结束结束释放释放事务事务结束结束释放释放不丢失不丢失修修改改不读脏不读脏数数据据可重可重复读复读一级封一级封锁协议锁协议 二级封二级封锁协议锁协议 三级封三级封锁协议锁协议 2022/12/30兰彬制作3111.4活锁和死锁活锁和死锁l封锁技术可以有效地解决并发操作的一封锁技术可以有效地解决并发操作的一致性问题，但可能带来一些新的问题致性问题，但可能带来一些新的问题死锁死锁活锁活锁2022/12/30

18、兰彬制作3211.4.1活锁活锁如果事务如果事务T1封锁了数据封锁了数据R后，事务后，事务T2又请求又请求封锁封锁R，则，则T2等待。然后等待。然后T3也请求封锁也请求封锁R；l活锁活锁系统可能使某个事务系统可能使某个事务永远处于等待状永远处于等待状态态，得不到封锁的机会，得不到封锁的机会等等T1释放了释放了R后，系统首先批准了后，系统首先批准了T3的请求，的请求，T2仍然等待；接着仍然等待；接着T4又请求封锁又请求封锁R；T3释放释放R后，系统又批准了后，系统又批准了T4的请求的请求这样，这样，T2有可能永远处于等待状态。有可能永远处于等待状态。2022/12/30兰彬制作33避免活锁的方法

19、避免活锁的方法采用采用“先来先服务先来先服务”的策略的策略当多个事务请求封锁同一数据对象时，当多个事务请求封锁同一数据对象时，按请求封锁的按请求封锁的先后次序先后次序对这些事务排队对这些事务排队该该数数据据对对象象上上的的锁锁一一旦旦释释放放，首首先先批批准准申申请请队列中队列中第一个事务第一个事务获得锁。获得锁。2022/12/30兰彬制作3411.4.2死锁死锁l死锁死锁系统中有多个事务都处于等待状态，系统中有多个事务都处于等待状态，并且每个事务都在等待另外一个事务释放封锁并且每个事务都在等待另外一个事务释放封锁后才能继续执行下去，结果造成任何一个事务后才能继续执行下去，结果造成任何一个事

20、务都无法继续执行。都无法继续执行。T1封锁了数据封锁了数据R1，T2封锁了数据封锁了数据R2；这样，这样，T1在等待在等待T2释放释放R2上的锁，而上的锁，而T2也也在等待在等待T1释放释放R1上的锁，因此上的锁，因此T1和和T2永远永远都不能结束，形成死锁。都不能结束，形成死锁。然后然后T1又请求封锁数据又请求封锁数据R2，由于，由于R2被被T2封封锁，锁，T1只能等待；接着，只能等待；接着，T2又请求封锁又请求封锁R1，由于由于R1被被T1封锁，封锁，T2也只能等待；也只能等待；2022/12/30兰彬制作35解决死锁的方法解决死锁的方法解决死锁有两类方法解决死锁有两类方法1.预防死锁预防

21、死锁2.死锁的诊断与解除死锁的诊断与解除2022/12/30兰彬制作361.死锁的预防死锁的预防l预防死锁的发生就是要预防死锁的发生就是要破坏产生死锁的条件破坏产生死锁的条件。l预防死锁的方法有预防死锁的方法有2种：种：一次封锁法一次封锁法顺序封锁法顺序封锁法2022/12/30兰彬制作37（1）一次封锁法）一次封锁法l一次封锁法：要求每个事务必须一次封锁法：要求每个事务必须一次一次将所有要将所有要使用的数据使用的数据全部加锁全部加锁，否则就不能继续执行，否则就不能继续执行l一次封锁法存在的问题：一次封锁法存在的问题：（1）将以后要用到的全部数据加锁，势必）将以后要用到的全部数据加锁，势必扩大

22、扩大封锁范围封锁范围，从而，从而降低系统的并发度降低系统的并发度（2）很难事先精确地确定每个事务所要封锁的）很难事先精确地确定每个事务所要封锁的数据对象，但是又要求把该事务将要用到的数据对象，但是又要求把该事务将要用到的数据全部封锁，这样就有可能数据全部封锁，这样就有可能进一步扩大封进一步扩大封锁范围，降低系统效率锁范围，降低系统效率。2022/12/30兰彬制作38（2）顺序封锁法）顺序封锁法l顺序封锁法是：预先对数据对象规定一个封锁顺序封锁法是：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实行封锁。顺序，所有事务都按这个顺序实行封锁。l顺序封锁法存在的问题：顺序封锁法存在的问题：（

23、1）维护成本高）维护成本高数据库系统中可封锁的数据库系统中可封锁的数据对象很多，并且随数据的插入、删除等数据对象很多，并且随数据的插入、删除等操作而不断地变化，要维护如此多而且在不操作而不断地变化，要维护如此多而且在不断变化的数据的封锁顺序是非常困难，维护断变化的数据的封锁顺序是非常困难，维护的成本很高的成本很高2022/12/30兰彬制作39顺序封锁法（续）顺序封锁法（续）例如：例如：l顺序封锁法存在的问题：顺序封锁法存在的问题：（2）难于实现）难于实现事务的封锁请求可以随着事务的封锁请求可以随着事务的执行而动态地决定，很难事先确定每事务的执行而动态地决定，很难事先确定每一个事务要封锁哪些对

24、象，因此也就很难按一个事务要封锁哪些对象，因此也就很难按规定的顺序去施加封锁。规定的顺序去施加封锁。规定数据对象的封锁顺序为规定数据对象的封锁顺序为A,B,C,D,E。事务事务T3起初要求封锁数据对象起初要求封锁数据对象B,C,E，但当，但当它封锁了它封锁了B，C后，才发现还需要封锁后，才发现还需要封锁A，这样就破坏了封锁顺序。这样就破坏了封锁顺序。2022/12/30兰彬制作40死锁的预防（续）死锁的预防（续）l结论结论在操作系统中广泛采用的在操作系统中广泛采用的预防死锁预防死锁的策略并的策略并不很适合数据库的特点不很适合数据库的特点DBMS在解决死锁的问题上更普遍采用的是在解决死锁的问题上

25、更普遍采用的是诊断并解除死锁的方法诊断并解除死锁的方法2022/12/30兰彬制作412.死锁的诊断与解除死锁的诊断与解除l基本思想：基本思想：l由由DBMS的的并发控制子系统并发控制子系统定期定期检测系统中是检测系统中是否存在死锁，一旦检测到死锁，就要否存在死锁，一旦检测到死锁，就要设法解除设法解除允许允许死锁发生，当死锁发生后，再采取一定死锁发生，当死锁发生后，再采取一定的措施来的措施来诊断和解除诊断和解除死锁死锁l诊断死锁的诊断死锁的2种常用方法：种常用方法：1）超时法）超时法2）事务等待图法）事务等待图法2022/12/30兰彬制作42检测死锁：检测死锁：超时法超时法l超时法的基本思想

26、：超时法的基本思想：l优点：优点：l缺点：缺点：如果一个事务的如果一个事务的等待时间等待时间超过超过了了规定的时限规定的时限，就认为发生了死锁就认为发生了死锁实现简单实现简单有可能有可能误判误判死锁死锁时限时限若设置得若设置得太长太长，死锁发生后，死锁发生后不能及时发不能及时发现现2022/12/30兰彬制作43检测死锁：检测死锁：事务等待图法事务等待图法l用事务等待图用事务等待图动态动态反映所有事务的等待情况：反映所有事务的等待情况：事务等待图是一个事务等待图是一个有向图有向图G=(T，U)T为结点的集合，每个结点表示正运行的事务为结点的集合，每个结点表示正运行的事务U为边的集合，每条边表示

27、事务等待的情况为边的集合，每条边表示事务等待的情况若若T1等待等待T2，则，则T1、T2之间划一条有向边，从之间划一条有向边，从T1指向指向T2并发控制子系统周期性地（比如每隔并发控制子系统周期性地（比如每隔1min）检测事务等待图，如果发现图中检测事务等待图，如果发现图中存在回路存在回路，则，则表示系统中出现了死锁。表示系统中出现了死锁。2022/12/30兰彬制作44解除死锁的方法解除死锁的方法l当使用超时法或者事务等待图法检测出系统中当使用超时法或者事务等待图法检测出系统中存在死锁后，就要设法解除死锁，通常采用的存在死锁后，就要设法解除死锁，通常采用的方法是：方法是：选择一个处理死锁选择

28、一个处理死锁代价最小代价最小的事务，将其的事务，将其撤撤消消，释放此事务持有的所有的锁，使其它事，释放此事务持有的所有的锁，使其它事务能继续运行下去。务能继续运行下去。2022/12/30兰彬制作4511.5并发调度的可串行性并发调度的可串行性一、什么样的并发操作调度是正确的一、什么样的并发操作调度是正确的二、如何保证并发操作的调度是正确的二、如何保证并发操作的调度是正确的2022/12/30兰彬制作46一、什么样的并发操作调度是正确的一、什么样的并发操作调度是正确的l例：现在有例：现在有2个事务，分别包括不同的操作：个事务，分别包括不同的操作：事务事务T1：读：读B；AB1；写回；写回A。事

29、务事务T2：读读A；BA1；写回；写回B。假设假设A，B的初值都为的初值都为2。l可能有以下几种执行顺序（调度策略）：可能有以下几种执行顺序（调度策略）：1）T1T2的顺序执行（串行调度策略的顺序执行（串行调度策略1）2）T2T1的顺序执行（串行调度策略的顺序执行（串行调度策略2）3）T1和和T2交叉交叉执行（交叉调度策略）执行（交叉调度策略）2022/12/30兰彬制作471）T1T2的顺序执行的顺序执行T1T2SlockB，Y=B=2UnlockBXlockA，A=B+1写回写回A=3UnlockASlockA，X=A=3UnlockAXlockB，B=A+1写回写回B=4UnlockA先

30、执行先执行T1，再，再执行执行T2，而且，而且T1和和T2的执的执行互不干扰行互不干扰执行结果是：执行结果是：A=3B=42022/12/30兰彬制作482）T2T1的顺序执行的顺序执行T1T2SlockB，Y=B=3UnlockBXlockA，A=B+1写回写回A=4UnlockASlockA，X=A=2UnlockAXlockB，B=A+1写回写回B=3UnlockA先执行先执行T2，再，再执行执行T1，而且，而且T2和和T1的执的执行互不干扰行互不干扰执行结果是：执行结果是：A=4B=32022/12/30兰彬制作49一、什么样的并发操作调度是正确的一、什么样的并发操作调度是正确的l将所

31、有事务将所有事务串行起来串行起来的调度策略一定是正确的的调度策略一定是正确的调度策略。即：调度策略。即：如果一个事务运行过程中没有其他事务在同如果一个事务运行过程中没有其他事务在同时运行，也就是说它没有受到其他事务的干时运行，也就是说它没有受到其他事务的干扰，那么就可以认为该事务的运行结果是正扰，那么就可以认为该事务的运行结果是正常的或者预想的常的或者预想的l以以不同的顺序不同的顺序串行串行执行事务也有可能会执行事务也有可能会产生不产生不同的结果同的结果，但由于不会将数据库置于不一致状，但由于不会将数据库置于不一致状态，所以都可以认为是态，所以都可以认为是正确正确的。的。2022/12/30兰

32、彬制作503）T1、T2交叉执行交叉执行T1T2SlockB，Y=B=2UnlockBXlockA，A=B+1写回写回A=3UnlockASlockA，X=A=2UnlockAXlockB，B=A+1写回写回B=3UnlockBT1和和T2在执在执行过程中行过程中相互相互交叉（相互干交叉（相互干扰），扰），其结果其结果和和1）、）、2）都）都不同，因此是不同，因此是错误的。错误的。执行结果是：执行结果是：A=3B=32022/12/30兰彬制作51什么样的并发操作调度是正确的（续）什么样的并发操作调度是正确的（续）l可串行化的调度：可串行化的调度：l可串行性是并发事务正确性的准则。即：可串行性

33、是并发事务正确性的准则。即：一个给定的并发调度，当且仅当它是一个给定的并发调度，当且仅当它是可串行可串行化化的，才认为是的，才认为是正确调度正确调度。几个事务的并行执行是正确的，几个事务的并行执行是正确的，当且仅当当且仅当其其结果与按某一次序结果与按某一次序串行地执行串行地执行它们时的结果它们时的结果相同。相同。这种并行调度策略称为可串行化这种并行调度策略称为可串行化（Serializable）的调度。）的调度。2022/12/30兰彬制作52一、什么样的并发操作调度是正确的一、什么样的并发操作调度是正确的l例：现在有例：现在有2个事务，分别包括不同的操作：个事务，分别包括不同的操作：事务事务

34、T1：读：读B；AB1；写回；写回A。事务事务T2：读读A；BA1；写回；写回B。假设假设A，B的初值都为的初值都为2。l可能有以下几种执行顺序（调度策略）：可能有以下几种执行顺序（调度策略）：1）T1T2的顺序执行（串行调度策略的顺序执行（串行调度策略1）2）T2T1的顺序执行（串行调度策略的顺序执行（串行调度策略2）3）T1和和T2交叉交叉执行（交叉调度策略）执行（交叉调度策略）4）可串行化的交叉调度策略）可串行化的交叉调度策略2022/12/30兰彬制作534）可串行化的交叉调度可串行化的交叉调度T1T2SlockB，Y=B=2UnlockBXlockAA=B+1,写回写回A=3Unlo

35、ckASlockA等待等待等待等待X=A=3UnlockAXlockB，B=A+1写回写回B=4UnlockB可串行化的调可串行化的调度，其结果与度，其结果与某一种串行调某一种串行调度结果相同。度结果相同。因此是正确的因此是正确的执行结果是：执行结果是：A=3B=42022/12/30兰彬制作54事务调度l l事务执行示例事务执行示例事务执行示例事务执行示例T1read(A);A:=A50;write(A);read(B);B:=B+50;write(B);T2read(A);temp:=A0.1A:=Atemp;write(A);read(B);B:=B+temp;write(B);从A过户

36、50￥到B从A过户存款的10%到B开始状态：A=1000￥B=2000￥A+B=3000￥2022/12/30兰彬制作55事务调度read(A);A:=A50;write(A);read(B);B:=B+50;write(B);read(A);temp:=A0.1A:=Atemp;write(A);read(B);B:=B+temp;write(B);T1T2A=950￥B=2050￥结束状态：A=855￥B=2145￥A+B=3000￥串串行行调调度度1 12022/12/30兰彬制作56事务调度read(A);A:=A50;write(A);read(B);B:=B+50;write(B)

37、;read(A);temp:=A0.1A:=Atemp;write(A);read(B);B:=B+temp;write(B);T1T2A=900￥B=2100￥结束状态：A=850￥B=2150￥A+B=3000￥串串行行调调度度2 22022/12/30兰彬制作57事务调度read(A);A:=A50;write(A);read(B);B:=B+temp;write(B);T1T2A=950￥B=2000￥结束状态：A=855￥B=2145￥A+B=3000￥read(B);B:=B+50;write(B);read(A);temp:=A0.1A:=Atemp;write(A);A=855

38、￥B=2000￥A=855￥B=2050￥并并行行调调度度32022/12/30兰彬制作58事务调度：丢失修改read(A);A:=A50;B:=B+temp;write(B);T1T2A=1000￥B=2000￥结束状态：A=950￥B=2100￥A+B=3050￥write(A);read(B);B:=B+50;write(B);read(A);temp:=A0.1A:=Atemp;write(A);read(B);A=900￥B=2000￥A=950￥B=2000￥A=950￥B=2050￥并并行行调调度度42022/12/30兰彬制作59事务调度：读脏数据read(A);A1:=A;r

39、ead(B);B1:=B;A1+B1=2950;read(B);B:=B+50;write(B);T1T2A=1000￥B=2000￥read(A);A:=A50;write(A);并并行行调调度度52022/12/30兰彬制作60事务调度：不能重复读read(A);A1:=AT1T2A=1000￥B=2000￥read(A);A:=A50;write(A);read(B);B:=B+50;write(B);read(B);B1:=BA1+B1=3050A=950￥B=2050￥并并行行调调度度62022/12/30兰彬制作61可串行化l l指令的顺序指令的顺序指令的顺序指令的顺序考虑一个调度

40、考虑一个调度S中的两条连续指令（仅限于中的两条连续指令（仅限于read与与write操作）操作）Ii与与Ij，分别属于事务，分别属于事务Ti与与TjIi=read(Q),Ij=read(Q);Ii=read(Q),Ij=write(Q);Ii=write(Q),Ij=read(Q);Ii=write(Q),Ij=write(Q);在在情况下，情况下，Ii与与Ij的次序无关紧要。其余的次序无关紧要。其余情况下，情况下，Ii与与Ij的次序不同，其执行结果也不的次序不同，其执行结果也不同，数据库最终状态也不同同，数据库最终状态也不同2022/12/30兰彬制作62可串行化l l冲突指令冲突指令冲突指

41、令冲突指令当两条指令是不同事务在当两条指令是不同事务在相同数据项相同数据项上的操上的操作，并且其中至少有一个是作，并且其中至少有一个是write指令时，则指令时，则称这两条指令是冲突的称这两条指令是冲突的如在如在、情况下，情况下，I Ii i与与I Ij j 是冲突的是冲突的非冲突指令交换次序不会影响调度的最终结非冲突指令交换次序不会影响调度的最终结果果l l冲突等价冲突等价冲突等价冲突等价如果调度如果调度S可以经过一系列非冲突指令交换转可以经过一系列非冲突指令交换转换成调度换成调度S，则称调度，则称调度S与与S是冲突等价的是冲突等价的2022/12/30兰彬制作63可串行化read(A);w

42、rite(A);read(B);write(B);T1T2read(B);write(B);并并行行调调度度3read(A);write(A);read(A);write(A);read(B);write(B);T1T2write(B);read(A);write(A);read(B);read(A);write(A);read(B);write(B);write(B);read(A);write(A);read(B);交换1交换2交换3read(A);write(A);read(B);write(B);read(B);write(B);read(A);write(A);2022/12/30兰

43、彬制作64可串行化l l冲突可串行化冲突可串行化冲突可串行化冲突可串行化当一个调度当一个调度S与一个串行调度与一个串行调度冲突等价冲突等价时，则时，则称该调度是冲突可串行化的称该调度是冲突可串行化的如并行调度如并行调度3是冲突可串行化的是冲突可串行化的read(A);T1T2write(A);write(A);非冲突串行化的例子：存在结果相同，但非冲突等价的调度2022/12/30兰彬制作65可串行化read(A);A:=A-50write(A);T1T2冲突指令冲突指令T1T2read(B);B:=B-10write(B);read(B);B:=B+50write(B);read(A);A:

44、=A+10write(A);read(A);A:=A-50write(A);read(B);B:=B+50write(B);read(B);B:=B-10write(B);read(A);A:=A+10write(A);A=950￥B=2000￥A=950￥B=1990￥A=950￥B=2040￥A=960￥B=2040￥A=960￥B=2040￥A=950￥B=2050￥存在非冲突等价但仍可串行化的调度2022/12/30兰彬制作66可串行化l l冲突可串行化判定冲突可串行化判定冲突可串行化判定冲突可串行化判定优先图优先图(precedencegraph)一个调度一个调度S的优先图是这样构造

45、的：它是一个的优先图是这样构造的：它是一个有向图有向图G=（V，E），），V是顶点集，是顶点集，E是边集。是边集。顶点集由所有参与调度的事务组成，边集由顶点集由所有参与调度的事务组成，边集由满足下述条件之一的边满足下述条件之一的边TiTj组成：组成：在在Tj执行执行read(Q)read(Q)之前，之前，Ti执行执行write(Q)write(Q)在在Tj执行执行write(Q)write(Q)之前，之前，Ti执行执行read(Q)read(Q)在在Tj执行执行write(Q)write(Q)之前，之前，Ti执行执行write(Q)write(Q)2022/12/30兰彬制作67可串行化T1T

46、2并并行行调调度度3 3T1T2read(A);write(B);T1T2write(A);read(B);write(B);并并行行调调度度4read(A);write(A);read(B);T1T2read(A);write(A);read(B);write(B);read(B);write(B);read(A);write(A);2022/12/30兰彬制作68可串行化如果优先图中存在边如果优先图中存在边TiTj ，则在任何等价，则在任何等价于于S S的串行调度的串行调度S S中，中，Ti都必须出现在都必须出现在Tj之前之前冲突可串行化判定准则冲突可串行化判定准则如果调度如果调度S的优先

47、图中有环，则调度的优先图中有环，则调度S是非冲是非冲突可串行化的。如果图中无环，则调度突可串行化的。如果图中无环，则调度S是冲是冲突可串行化的突可串行化的T1T2T1T2并行调度并行调度3 3是冲是冲突可串行化的突可串行化的并行调度并行调度4 4是非是非冲突可串行化的冲突可串行化的2022/12/30兰彬制作69可串行化与冲突可串行化等价的串行顺序与冲突可串行化等价的串行顺序串行顺序可由拓扑排序得到，求出与优先图串行顺序可由拓扑排序得到，求出与优先图的偏序相一致的线序的偏序相一致的线序T1T3T2T4T1T2T3T4T1T3T2T42022/12/30兰彬制作7011.5并发调度的可串行性并发

48、调度的可串行性一、什么样的并发操作调度是正确的一、什么样的并发操作调度是正确的二、如何保证并发操作的调度是正确的二、如何保证并发操作的调度是正确的2022/12/30兰彬制作71二、如何保证并发操作的调度是正确的二、如何保证并发操作的调度是正确的l为了保证并行操作的正确性，为了保证并行操作的正确性，DBMS的的并发并发控制机制控制机制必须提供一定的手段来保证必须提供一定的手段来保证调度是调度是可串行化可串行化的。的。l保证并发操作调度正确性的方法：保证并发操作调度正确性的方法：在某一事务执行时禁止其他事务执行（在某一事务执行时禁止其他事务执行（实际实际不可行不可行）封锁方法封锁方法两段锁协议两

49、段锁协议时标方法时标方法乐观方法乐观方法2022/12/30兰彬制作7211.6两段锁协议两段锁协议l两段锁协议的内容：两段锁协议的内容：1.在对任何数据进行读、写操作之前，事务首在对任何数据进行读、写操作之前，事务首先要先要申请并获得申请并获得对该数据的对该数据的封锁封锁2.在在释放释放一个封锁之一个封锁之后后，事务不再获得任何其，事务不再获得任何其他封锁。他封锁。事务分为两个阶段：事务分为两个阶段：第一阶段是第一阶段是获得封锁获得封锁，也称为，也称为扩展阶段扩展阶段；第二阶段是第二阶段是释放封锁释放封锁，也称为，也称为收缩阶段收缩阶段。l两段锁协议的含义：两段锁协议的含义：2022/12/

50、30兰彬制作73两段锁协议两段锁协议举例举例事务事务1的封锁序列：的封锁序列：扩展阶段扩展阶段收缩阶段收缩阶段事务事务2的封锁序列：的封锁序列：SlockA；SlockB；XlockC；UnlockB；UnlockA；UnlockC；SlockA；UnlockA；SlockB；XlockC；UnlockC；UnlockB；事务事务1遵守两段锁协议，而事务遵守两段锁协议，而事务2不遵守两段协议。不遵守两段协议。2022/12/30兰彬制作74两段锁协议（续）两段锁协议（续）l注意：注意：如果并发执行的所有事务均如果并发执行的所有事务均遵守两段锁协议遵守两段锁协议，则对这些事务的则对这些事务的所有