《封锁协议》PPT课件.ppt

《《封锁协议》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《封锁协议》PPT课件.ppt（56页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2023/1/111第第1111章并发控制章并发控制讲课内容：讲课内容：事务最基本的特性之一就是隔离性。当DBMS中有多个事务并发执行时，事务的隔离性就不一定能保持。DBMS必须对并发事务之间的相互作用加以控制，这种控制是通过并发控制机制并发控制机制并发控制机制并发控制机制来实现的。所谓的并发控制机制本质上就是并发控制协议，这些协议是一组规则，用来决定冲突的事务是回滚重启还是等待执行。本章要讨论的所有协议都本章要讨论的所有协议都能保证调度是可串行化的能保证调度是可串行化的！封锁协议封锁协议有效性检查协议有效性检查协议死锁处理死锁处理树形协议树形协议多粒度机制多粒度机制插入与删除插入与删除时间戳

2、排序协议时间戳排序协议多版本机制多版本机制本章总结本章总结2023/1/11211.111.1封锁协议封锁协议加锁的理由保证调度可串行化的方法之一是对数据项的访问以互斥的方式进行：当一个事务访问某个数据项时，其他任何事务都不能修改该数据项。实现这个要求的最常用的方法就是：只有当一个事务目前在一个数据项上持有某种锁时，DBMS才允许该事务访问这个数据项；否则，就2023/1/11311.111.1封锁协议封锁协议给数据项加锁的类型共享锁：如果事务T获得了数据项Q上的共享锁(记为S)，则T可读Q但不能写Q。排他锁：如果事务T获得了数据项Q上的排他锁(记为X)，则T既可读Q又可写Q。根据操作要求事务

3、给数据项申请适当的锁该请求是发送给DBMS的并发控制管理器的；只有在并发控制管理器授予事务所需要的锁之后，事务才能继续其操作。2023/1/11411.111.1封锁协议封锁协议一个数据项上到底能加有多少个锁？锁和锁之间的关系是什么？令A与B代表任意类型的锁，已知如下条件：事务Ti正请求对数据项Q加A类型锁；而另一个事务Tj当前在数据项Q上持有B类型锁。结论：尽管数据项Q上已加有B类型锁，但如果事务Ti可以立即获得数据项Q上的A类型锁，则称A类型锁与B类型锁相容。锁相容矩阵只有其值为TRUE的两类锁才相容。2023/1/11511.111.1封锁协议封锁协议基本的封锁协议加锁：要访问一个数据项

4、，事务T必须首先申请给该数据项加锁：如果该数据项已经被另一事务加上了不相容类型的锁，则在所有不相容类型的锁被释放之前，并发控制管理器不会授予事务T申请的锁；因此T必须等待，直到所有不相容类型的锁被释放。解锁：只要事务T还在访问某数据项，它就必须拥有该数据项上的锁；除此之外，事务T可以随时释放随时释放先前它加在某个数据项上的锁。2023/1/11611.111.1封锁协议封锁协议加锁与解锁的表达假设Q代表数据项加锁指令：lock-S(Q)：申请Q上的共享锁；lock-X(Q)：申请Q上的排他锁。解锁指令：unlock(Q)：释放Q上相应的锁。2023/1/11711.111.1封锁协议封锁协议带

5、锁的调度事务T1申请锁并发控制管理器检查是否可以授予锁？如果可以，grant-X(A,T1)指令将授予锁如果不可以，则事务T1就必须等待！2023/1/11811.111.1封锁协议封锁协议基本封锁协议的问题从前面的例子可以看出，即使在调度中采用了基本的封锁协议，也还有可能导致数据库不一致。因此基本的封锁协议也有缺陷：解锁问题：在事务中过早地释放数据项上的锁，有可能导致数据库的不一致。死锁问题：所有的事务因为持有锁和申请锁而导致大家都处于等待状态，无法继续执行；饿死问题：一个事务总是不能在某个数据项上加上锁，因此该事务也就永远不能取得进展。2023/1/11911.111.1封锁协议封锁协议解

6、锁与死锁问题如果对数据项进行读写之后立即解锁，容易造成数据库的不一致，那么是否把解锁的时机往后推到事务的末尾就万事大吉了呢？解锁的时机不仅影响事务的并发度，同时还有可能造成调度的死锁！死锁比造成数据库不一致要好，因为死锁可以通过DBMS回滚某事务加以解决；而2023/1/111011.111.1封锁协议封锁协议饿死问题锁的授予：事务申请对某数据项加某种类型的锁；没有其他事务在该数据项上持有与该事务所申请的锁不相容的锁；此时，并发控制管理器才可以授予锁。当事务Ti申请对数据项Q加M型锁时，授权加锁的条件是：不存在其他事务在数据项Q上持有与M型锁冲突的锁；不存在其他事务等待对数据项Q加锁且先于Ti

7、申请加锁。2023/1/1111两阶段封锁协议为了解决事务的解锁问题，该协议要求每个事务分两个阶段提出加锁和解锁申请：增长阶段：事务可以获得锁，但不能释放锁。缩减阶段：事务可以释放锁，但不能获得锁。对于一个事务而言：11.111.1封锁协议封锁协议：解锁时机2023/1/111211.111.1封锁协议封锁协议两阶段封锁协议饿死问题：DBMS中并发控制管理器授权加锁的两个条件。解锁问题：两阶段封锁协议指出了事务释放锁的时机，使得解锁指令也不必非得出现在事务的末尾，增加了事务之间的并发度。死锁问题：在调度中可能还会有死锁发生，真正的原因是什么呢？2023/1/1113封锁点对任何一个事务而言，在

8、调度中获得其最后一个锁的时刻，称为该事务的封锁点。思考调度中多个事务可根据它们的封锁点进行排序，该顺序就是事务的一个可串行化次序。11.111.1封锁协议封锁协议2023/1/1114加强的两阶段封锁协议问题的提出：在两阶段封锁协议下，还有一个问题就是在发生故障的情况下调度中事务的级联回滚可能发生。举例：如右图所示11.111.1封锁协议封锁协议2023/1/1115加强的两阶段封锁协议严格两阶段封锁协议：除了要求封锁是两阶段之外，还要求事务持有的所有排他锁必须在事务提交之后方可释放；这个要求保证未提交事务所写的任何数据在该事务提交之前均以排他方式加锁，防止其他事务读取这些数据。强两阶段封锁协

9、议：该协议要求事务提交之前不得释放任何锁，它旨在让冲突的事务尽可能地串行执行；可重复读！这样调度中的事务可以按其提交的顺序串行化；事务提交的顺序与前面讲的封锁点顺序一致吗？11.111.1封锁协议封锁协议问题：降低了事务之间的并发度！2023/1/1116锁的转换问题的提出：如果事务一开始就申请排他锁并获得该锁，那么其他事务只能在该事务提交之后才有可能获得锁而继续执行；也就是说，加强的两阶段封锁协议虽然保证了调度不会发生级联回滚，但却降低了事务之间的并发度。举例：事务T12必须对数据项a1加排他锁，结果导致11.111.1封锁协议封锁协议2023/1/1117锁的转换问题的解决：事实上，只是在

10、T12写a1的时候才需要对a1加排他锁；因此，一开始T12只要对a1加共享锁就可以，只是在需要时再将其变为排他锁，这样T12和T13就可以真正地实现并发执行。锁的升降级：upgrade表示将共享锁升级为排他锁，只能发生在downgrade表示将排他锁降级为共享锁，只能发生在11.111.1封锁协议封锁协议2023/1/1118商用DBMS中封锁协议的实现在实际的商用DBMS中，根据加强的封锁协议实现的并发控制机制很简单且被广泛采用；这样的机制能保证并发控制管理器自动为事务产生加锁、解锁指令：当事务T进行read(Q)操作时，系统产生lock-S(Q)指令，后接read(Q)指令；当事务T进行w

11、rite(Q)操作时，系统检查T是否已在Q上持有共享锁：若有，则系统发出upgrade(Q)指令，后接write(Q)指令；否则系统发出lock-X(Q)指令，后接write(Q)指令；事务提交或回滚后，该事务持有的锁都被释放。11.111.1封锁协议封锁协议2023/1/1119树状协议。T1:DBGET2:DH11.211.2并发调度中的事务冲突并发调度中的事务冲突ABCDGHJEFI2023/1/1120事务冲突封锁协议要求事务在操作数据前，必须向并发控制管理器申请锁：如果事务没有立刻获得相关的锁，就说明系统中有冲突的事务，它必须等待。系统中并发的事务之间存在哪些冲突？这些冲突会造成哪些

12、问题(数据库不一致)？写读冲突：读未提交的数据，即脏读；读写冲突：不可重复读；写写冲突：重写未提交的数据，即丢失修改；幻影：相同的条件，前后两次查询的结果不同。11.211.2并发调度中的事务冲突并发调度中的事务冲突2023/1/1121写读冲突读未提交的数据，即脏读：事务Tj读取了已经被另一个事务Ti修改，但最终却没有提交的数据项Q。11.211.2并发调度中的事务冲突并发调度中的事务冲突2023/1/1122读写冲突不可重复的读：当事务Tj读数据对象Q并仍在运行时，事务Ti修改了Q的值。如果Tj再次读Q的值11.211.2并发调度中的事务冲突并发调度中的事务冲突2023/1/1123写写冲

13、突重写未提交的数据，即丢失修改：事务Ti和Tj读入同一数据并进行修改，Tj重复写入Q值，并且Ti先于Tj提交。这样Tj提交的结果就破坏了Ti提交的结果，导致Ti的修改丢失。11.211.2并发调度中的事务冲突并发调度中的事务冲突2023/1/1124幻影事务Tj按一定条件读取了某些数据后，事务Ti又插入(删除)了一些满足条件的数据。当Tj再次按相同的条件读取数据时，发现多(少)了一些记录。11.211.2并发调度中的事务冲突并发调度中的事务冲突仅保证它所访问的数据不被其他事务修改是不够的没有阻止其他事务插入新的满足条件的数据2023/1/1125调度中冲突事务的解决方案：封锁协议：等待执行；冲

14、突可串行化顺序：事务封锁点的顺序；按事务提交的顺序；每一对冲突事务的可串行化次序是由执行时第一个两者都申请但互相冲突的锁决定的。时间戳排序协议：回滚重启；冲突可串行化顺序：事先选定好了事务的串行顺序，即事务进入DBMS的先后顺序。11.311.3时间戳排序协议时间戳排序协议三个顺序的一致性？2023/1/1126时间戳基本概念：对于系统中的每个事务T，把一个唯一固定的时间标志和事务T联系起来，这个时间标志就是事务的时间戳时间戳是在事务T开始执行前由DBMS的并发控制管理器赋予事务的，记为TS(T)。时间戳的大小(先后)之分：如果事务Ti先于事务Tj进入系统，那么：TS(Ti)TS(Tj)实现方

15、式：使用系统时钟或逻辑计数器11.311.3时间戳排序协议时间戳排序协议2023/1/1127时间戳的特征事务的时间戳决定了调度中事务的可串行化顺序：若若TS(TTS(Ti i)TS(TTS(Tj j)，则，则DBMSDBMS保证所产生的调度等价保证所产生的调度等价于于T Ti i出现在出现在T Tj j之前的某个串行调度。之前的某个串行调度。每个数据项Q需要和以下两个重要的时间戳相关联：W-TS(Q)：当前已成功执行write(Q)的所有事务的最大时间戳R-TS(Q)：当前已成功执行read(Q)的所有事务的最大时间戳随着读写指令的成功执行，它们随时被更新。11.311.3时间戳排序协议时间

16、戳排序协议2023/1/1128协议内容时间戳排序协议保证并发调度中任何有冲突的read和write操作按时间戳顺序执行。假设事务Ti发出read(Q)操作：若TS(Ti)W-TS(Q)，则Ti需要读入的Q值已被覆盖。因此，read操作被拒绝，Ti回滚；(写读冲突)若TS(Ti)W-TS(Q)，则执行read操作，而R-TS(Q)的值被设为R-TS(Q)与TS(Ti)中的较大者。11.311.3时间戳排序协议时间戳排序协议2023/1/1129协议内容时间戳排序协议保证并发调度中任何有冲突的read和write操作按时间戳顺序执行。假设事务Ti发出write(Q)操作：若TS(Ti)R-TS(

17、Q)，则Ti产生的Q值是先前所需要的值，但系统已假定该值不会被产生。因此，write操作被拒绝，Ti回滚；(读写冲突)11.311.3时间戳排序协议时间戳排序协议2023/1/1130协议内容假设事务Ti发出write(Q)操作：若TS(Ti)W-TS(Q)，则Ti想写入的Q值已经丢失。因此，write操作被拒绝，Ti回滚；(写写冲突)其他情况下执行write(Q)操作，并将W-TS(Q)的值设为TS(Ti)。事务Ti被并发控制机制回滚之后，被赋予新的时新的时间戳间戳并重新启动，进入系统。11.311.3时间戳排序协议时间戳排序协议2023/1/1131调度举例在时间戳排序协议下：假设事务在第

18、一条指令执行前的那一刻被赋予时间戳；对事务要访问的任何数据项来说，假设它们的W-TS和R-TS的初始值都为0(最小)。11.311.3时间戳排序协议时间戳排序协议2023/1/1132Thomas(托马斯)写规则对时间戳排序协议中事务间“写/写”冲突规则的重大修改；首先从一个例子开始：如图所示，TS(T3)TS(T4)，假设T3的read(Q)和T4的write(Q)都成功执行，则W-TS(Q)=TS(T4)；当T3试图执行write(Q)时，由于TS(T3)W-TS(Q)，即TS(T4)，该操作被拒绝且事务T3回滚。虽然按照时间戳排序协 议的要求T3应该回滚，但实际上没有必要。T3 的wri

19、te(Q)操作可以 忽略，为什么？11.311.3时间戳排序协议时间戳排序协议2023/1/1133Thomas(托马斯)写规则T4已写T3要写的Q永远不会被任何事务读到：满足TS(Ti)W-TS(Q)=TS(T4)的任何事务Ti试图进行read(Q)操作时均被回滚；满足TS(Tj)W-TS(Q)=TS(T4)的任何事务Tj必须读入由T4而不是T3写入的Q值。11.311.3时间戳排序协议时间戳排序协议结论：T3的write(Q)已经过时，可以忽略！即使执行T3的write(Q)，W-TS(Q)的值仍然是TS(T4)！2023/1/1134Thomas(托马斯)写规则当事务Ti发出write(

20、Q)操作时：若TS(Ti)R-TS(Q)，规则同前面：Ti回滚；若TS(Ti)W-TS(Q)，则Ti试图要写入的Q值已经过时。因此该write(Q)操作可被忽略；其他情况下执行write(Q)操作，并将W-TS(Q)的值设为TS(Ti)。11.311.3时间戳排序协议时间戳排序协议2023/1/1135小结时间戳排序协议保证：满足该协议的任何调度冲突可串行化，为什么？满足该协议的任何调度无死锁，为什么？但该协议不保证：所产生的调度都是可恢复的：11.311.3时间戳排序协议时间戳排序协议2023/1/1136并发事务的隔离等级事务的隔离等级控制事务可暴露给其他并发执行事务的程度；通过选择隔离等

21、级，事务以把未提交的数据更新暴露给其他事务为代价，获得更高程度的并发度；一般商用DBMS的隔离等级分为以下四种：读未提交(Read Uncommitted)读已提交(Read Committed)可重复读(Repeatable Read)可串行化(Serializable)11.411.4事务的隔离等级事务的隔离等级2023/1/1137读未提交：允许事务可以读取未提交的数据；设置事务的隔离等级为“读未提交”，使得事务不必等待任何锁，也不必对所读的数据加共享锁；读未提交虽然提高了事务之间的并发度，但是以牺牲数据库的一致性为代价：读脏数据不能重复读幻影set trans isolation RE

22、AD UNCOMMITTED11.411.4事务的隔离等级事务的隔离等级2023/1/1138读已提交只允许事务读取已提交的数据，但不要求可重复读；这是一般商用DBMS的缺省隔离等级，保证事务不会读取其他未提交事务所修改的数据；读已提交要求在所访问的数据上至少加共享锁，共享锁不会防止其他事务读取数据，但会防止其他事务修改数据。这里的共享锁不必保持到事务结束；读已提交可能造成的数据库不一致性现象：不能重复读和幻影11.411.4事务的隔离等级事务的隔离等级2023/1/1139可重复读只允许事务读取已提交的数据，并要求一个事务在对同一数据的两次读取之间，其他事务不能对这些数据进行更新；为保证可重

23、复读，事务必须保持它的共享锁到事务结束(注意：排他锁总是保持到事务结束)。这样，其他事物就不能修改可重复读事务正在访问的数据；可重复读会极大地降低事务之间的并发度，同时也会造成数据库的不一致性现象：幻影11.411.4事务的隔离等级事务的隔离等级2023/1/1140可串行化并发调度的执行结果等价于一个串行调度；在可重复读的基础上，进一步要求一个事务的两次相同的查询之间，其他事务不能插入满足查询条件的数据，避免发生幻影现象；同可重复读一样，事务必须保持它的共享锁到事务结束。同时，事务不但要封锁现有的数据，还要封锁不存在的数据(插入操作)；加强的两阶段封锁协议和时间戳排序协议都能保证它们所产生的

24、并发调度是冲突可串行化的。11.411.4事务的隔离等级事务的隔离等级2023/1/1141死锁的定义如果存在一个事务集，该集合中的每个事务都在等待集合中的另外一个事务，我们就说系统处于死锁状态。例如：在集合T0,T1,Tn中，若T0在等待被T1锁住的数据项；T1在等待被T2锁住的数据项；Tn-1在等待被Tn锁住的数据项；而Tn在等待被T0锁住的数据项，则系统死锁。11.511.5死锁处理死锁处理2023/1/1142死锁的解决解决死锁问题主要有以下两种策略：死锁预防：预先防止死锁发生，保证系统永不进入死锁状态。死锁检测与恢复：允许系统进入死锁状态，但要周期性地检测系统有无死锁。如果有，则把系

25、统从死锁中恢复过来。两种策略都会引起事务回滚：如果系统进入死锁状态的概率相对较高，则通常采用死锁预防策略；否则死锁检测与恢复策略会更有效。基于锁超时的机制：申请锁的事务至多等待给定的时间。若11.511.5死锁处理死锁处理2023/1/1143死锁预防预防死锁的最有效的方法就是采用资源抢占与事务回滚技术：在这种方法里，首先赋予每个事务一个唯一的时间戳，系统利用时间戳来决定事务应当是等待，还是回滚重启；但调度的并发控制仍然使用封锁机制；若一个事务回滚，则该事务重启时保持原有的时间戳。利用时间戳的两种死锁预防机制如下：等待-死亡(wait-die)机制受伤-等待(wound-wait)机制11.5

26、11.5死锁处理死锁处理2023/1/1144等待-死亡机制这种机制基于非抢占技术；当事务Ti申请的数据项当前被Tj持有，仅当TS(Ti)TS(Tj)时，允许Ti等待。否则，Ti抢占Tj持有的数据项，而Tj回滚。例如：若事务Ti、Tj、Tk的时间戳分别为5、10、15：如果Ti申请的数据项当前被Tj持有，则Ti将从Tj抢占数据项，Tj回滚；如果Tk申请的数据项当前被Tj持有，则Tk将等待。11.511.5死锁处理死锁处理2023/1/1146等待-死亡与受伤-等待的区别等待区别：在等待-死亡机制中，较老的事务必须等待在受伤-等待机制中，较老的事务从不等待回滚区别：在等待-死亡机制中：同一事务可

27、能回滚多次！在受伤-等待机制中：相关事务只需回滚一次？11.511.5死锁处理死锁处理2023/1/1147死锁检测与恢复死锁检测与恢复机制的工作方式如下：检查系统状态的算法周期性地被激活(实际上它应当是系统中的一个进程或线程)，判断系统中有无死锁；如果发生死锁，则系统要进行恢复。这种机制的基本要求如下：维护当前已分配给事务的数据项的有关信息以及任何尚未解决的数据项请求信息；提供一个使用这些信息判断系统是否进入死锁状态的算法；提供解除死锁的策略。11.511.5死锁处理死锁处理2023/1/1148死锁检测与恢复死锁检测：死锁用称为等待图的有向图来描述；该图由两部分G=(V,E)组成，其中V是

28、顶点集，E是边集：顶点集由调度中的所有事务组成；如果事务Ti在等待Tj释放所需数据项，则存在从Ti到Tj的一条有向边TiTj。死锁检测算法就是要检查等待图中是否存在有向环，图论中有相应的深度优先搜索算法或广度优先搜索算法来完成此任务：这和前面介绍过的判断调度冲突可串行化的优先图类似。11.511.5死锁处理死锁处理2023/1/1149死锁检测与恢复死锁恢复：常用方法是回滚一个或多个事务；在选择要回滚的事务时要考虑以下情况：选择使回滚代价最小的事务作为牺牲者；决定回滚多远：彻底回滚，即中止该事务尔后重启；部分回滚，只回滚到可以解除死锁为止。避免饿死：避免同一事务总是作为回滚代价最小的事务而被选

29、中；常用的方法就是在代价因素中包含回滚次数11.511.5死锁处理死锁处理该事务已计算了多久？已使用了多少数据项？完成还需多少数据项？回滚将牵涉多少其他事务？2023/1/1150概述前面讲的read和write操作只能处理数据库中已经存在的数据；实际上，事务不仅要访问数据库中已经存在的数据项，而且还要创建新的数据项、删除旧的数据项：delete(Q)：从数据库中删除数据项Q；insert(Q)：插入一个新的数据项Q到数据库并赋予Q一个初值。事务T在Q被删除后执行read(Q)或在Q被插入前执行read(Q)都将产生逻辑错误！11.611.6插入与删除插入与删除2023/1/1151删除首先要

30、弄清楚调度中删除操作和哪些数据操作冲突？假设调度S中两个连续的操作Im和In分别属于事务Ti和Tj，其中Im=delete(Q)：若In=read(Q)：ImIn，则冲突；若In=write(Q)：ImIn，则冲突；若In=delete(Q)：则冲突；若In=insert(Q)：则冲突。分两种情况：ImIn，在Im与In之前，Q已经存在。11.611.6插入与删除插入与删除2023/1/1152删除并发控制机制中删除操作的处理：如果使用两阶段封锁协议，则在一数据项被删除之前，应该为其申请加排他锁；在时间戳排序协议下，进行类似于write操作的测试。假设事务Ti发出delete(Q)操作：如果T

31、S(Ti)R-TS(Q)，则Ti应回滚；如果TS(Ti)W-TS(Q)，则Ti应回滚；其他情况下，执行delete(Q)操作。11.611.6插入与删除插入与删除2023/1/1153插入同样，insert(Q)操作与delete(Q)、write(Q)和read(Q)操作之间存在冲突；由于insert(Q)操作创建新数据项Q并为其赋初值，因此，在并发控制中应当像处理write操作那样来处理insert操作：在两阶段封锁协议下：如果Ti要执行insert(Q)操作，则事务Ti应该为Q申请加排他锁。在时间戳排序协议下：由于在数据项Q存在之前，read(Q)和write(Q)都不可能成功执行，因此

32、，R-TS(Q)与W-TS(Q)都为0。如果Ti发出insert(Q)操作，则执行之并将R-TS(Q)与W-TS(Q)的值设为TS(Ti)。11.611.6插入与删除插入与删除2023/1/1154小结：并发冲突的解决与实质小结：并发冲突的解决与实质并发控制协议封锁协议：调度中冲突的事务必须有一个要等待，容易产生死锁。时间戳排序协议：调度中冲突的事务必须有一个要回滚，不会产生死锁。并发控制协议的实质并不是告诉DBMS如何让调度中的事务去并发执行，而是在发生冲突的情况下如何让冲突的事务尽可能地串行执行。2023/1/1155小结：并发冲突的解决与实质小结：并发冲突的解决与实质可串行化顺序的一致性

33、两阶段封锁协议(包括严格两阶段封锁协议)保证调度可根据事务的封锁点串行化；而强两阶段协议的本质是事务在提交之后才能释放锁，调度可以根据事务提交的顺序串行化；时间戳排序协议保证调度按照事务进入系统的时间(先后顺序)串行化；托马斯写规则是对时间戳排序协议的重大改进，它通过删除事务发出的过时write操作来保证调度尽可能地视图可串行化？2023/1/1156小结：并发冲突的解决与实质小结：并发冲突的解决与实质商用数据库管理系统中的并发控制协议带有锁转换的强两阶段封锁协议。调度中的事务冲突与隔离等级写读冲突/读未提交读写冲突/读已提交写写冲突/可重复读幻影/可串行化死锁处理利用事务的时间戳来处理封锁协议中容易出现的死锁现象，主要思路是回滚事务。