封锁协议课件.ppt
56页
第第1111章 并发控制章 并发控制讲课内容：讲课内容：事务最基本的特性之一就是隔离性当DBMS中有多个事务并发执行时，事务的隔离性就不一定能保持DBMS必须对并发事务之间的相互作用加以控制，这种控制是通过并发控制机制并发控制机制并发控制机制并发控制机制来实现的所谓的并发控制机制本质上就是并发控制协议，这些协议是一组规则，用来决定冲突的事务是回滚重启还是等待执行本章要讨论的所有协议都本章要讨论的所有协议都能保证调度是可串行化的能保证调度是可串行化的！■■封锁协议封锁协议 ■■有效性检查协议 有效性检查协议 ■■死锁处理死锁处理■■树形协议 树形协议 ■■多粒度机制 多粒度机制 ■■插入与删除插入与删除■■时间戳排序协议时间戳排序协议 ■■多版本机制 多版本机制 ■■本章总结本章总结2024/9/231封锁协议 §11.1§11.1封锁协议封锁协议Ø加锁的理由ü保证调度可串行化的方法之一是对数据项的访问以互斥的方式进行：•当一个事务访问某个数据项时，其他任何事务都不能修改该数据项ü实现这个要求的最常用的方法就是：•只有当一个事务目前在一个数据项上持有某种锁时，DBMS才允许该事务访问这个数据项；•否则，就……2024/9/232封锁协议 §11.1§11.1封锁协议封锁协议Ø给数据项加锁的类型ü共享锁：•如果事务T获得了数据项Q上的共享锁(记为S)，则T可读Q但不能写Q。
ü排他锁：•如果事务T获得了数据项Q上的排他锁(记为X)，则T既可读Q又可写QØ根据操作要求事务给数据项申请适当的锁ü该请求是发送给DBMS的并发控制管理器的；ü只有在并发控制管理器授予事务所需要的锁之后，事务才能继续其操作2024/9/233封锁协议 §11.1§11.1封锁协议封锁协议Ø一个数据项上到底能加有多少个锁？Ø锁和锁之间的关系是什么？ü令A与B代表任意类型的锁，已知如下条件：•事务Ti正请求对数据项Q加A类型锁；•而另一个事务Tj当前在数据项Q上持有B类型锁ü结论：•尽管数据项Q上已加有B类型锁，但如果事务Ti可以立即获得数据项Q上的A类型锁，则称A类型锁与B类型锁相容Ø锁相容矩阵ü只有其值为TRUE的两类锁才相容2024/9/234封锁协议 §11.1§11.1封锁协议封锁协议Ø基本的封锁协议ü加锁：•要访问一个数据项，事务T必须首先申请给该数据项加锁：如果该数据项已经被另一事务加上了不相容类型的锁，则在所有不相容类型的锁被释放之前，并发控制管理器不会授予事务T申请的锁；因此T必须等待，直到所有不相容类型的锁被释放ü解锁：•只要事务T还在访问某数据项，它就必须拥有该数据项上的锁；•除此之外，事务T可以随时释放随时释放先前它加在某个数据项上的锁。
2024/9/235封锁协议 §11.1§11.1封锁协议封锁协议Ø加锁与解锁的表达假设Q代表数据项ü加锁指令：•lock-S(Q)：申请Q上的共享锁；•lock-X(Q)：申请Q上的排他锁ü解锁指令：•unlock(Q)：释放Q上相应的锁2024/9/236封锁协议 §11.1§11.1封锁协议封锁协议Ø带锁的调度ü事务T1申请锁ü并发控制管理器检查是否可以授予锁？ü如果可以，grant-X(A,T1)指令将授予锁ü如果不可以，则事务T1就必须等待！2024/9/237封锁协议 §11.1§11.1封锁协议封锁协议Ø基本封锁协议的问题ü从前面的例子可以看出，即使在调度中采用了基本的封锁协议，也还有可能导致数据库不一致因此基本的封锁协议也有缺陷：•解锁问题：在事务中过早地释放数据项上的锁，有可能导致数据库的不一致•死锁问题：所有的事务因为持有锁和申请锁而导致大家都处于等待状态，无法继续执行；•饿死问题：一个事务总是不能在某个数据项上加上锁，因此该事务也就永远不能取得进展2024/9/238封锁协议 §11.1§11.1封锁协议封锁协议Ø解锁与死锁问题ü如果对数据项进行读写之后立即解锁，容易造成数据库的不一致，那么是否把解锁的时机往后推到事务的末尾就万事大吉了呢？ü解锁的时机不仅影响事务的并发度，同时还有可能造成调度的死锁！•死锁比造成数据库不一致要好，因为死锁可以通过DBMS回滚某事务加以解决；而…2024/9/239封锁协议 §11.1§11.1封锁协议封锁协议Ø饿死问题ü锁的授予：•事务申请对某数据项加某种类型的锁；•没有其他事务在该数据项上持有与该事务所申请的锁不相容的锁；•此时，并发控制管理器才可以授予锁。
当事务Ti申请对数据项Q加M型锁时，授权加锁的条件是：①不存在其他事务在数据项Q上持有与M型锁冲突的锁；②不存在其他事务等待对数据项Q加锁且先于Ti申请加锁2024/9/2310封锁协议 Ø两阶段封锁协议ü为了解决事务的解锁问题，该协议要求每个事务分两个阶段提出加锁和解锁申请：•增长阶段：事务可以获得锁，但不能释放锁•缩减阶段：事务可以释放锁，但不能获得锁ü对于一个事务而言：§11.1§11.1封锁协议封锁协议：解锁时机2024/9/2311封锁协议 §11.1§11.1封锁协议封锁协议Ø两阶段封锁协议ü饿死问题：•DBMS中并发控制管理器授权加锁的两个条件ü解锁问题：•两阶段封锁协议指出了事务释放锁的时机，使得解锁指令也不必非得出现在事务的末尾，增加了事务之间的并发度û死锁问题：•在调度中可能还会有死锁发生，真正的原因是什么呢？2024/9/2312封锁协议 Ø封锁点ü对任何一个事务而言，在调度中获得其最后一个锁的时刻，称为该事务的封锁点Ø思考ü调度中多个事务可根据它们的封锁点进行排序，该顺序就是事务的一个可串行化次序§11.1§11.1封锁协议封锁协议2024/9/2313封锁协议 Ø加强的两阶段封锁协议ü问题的提出：•在两阶段封锁协议下，还有一个问题就是在发生故障的情况下调度中事务的级联回滚可能发生。
ü举例：•如右图所示§11.1§11.1封锁协议封锁协议2024/9/2314封锁协议 Ø加强的两阶段封锁协议ü严格两阶段封锁协议：•除了要求封锁是两阶段之外，还要求事务持有的所有排他锁必须在事务提交之后方可释放；•这个要求保证未提交事务所写的任何数据在该事务提交之前均以排他方式加锁，防止其他事务读取这些数据ü强两阶段封锁协议：•该协议要求事务提交之前不得释放任何锁，它旨在让冲突的事务尽可能地串行执行；可重复读！•这样调度中的事务可以按其提交的顺序串行化；•事务提交的顺序与前面讲的封锁点顺序一致吗？§11.1§11.1封锁协议封锁协议问题：降低了事务之间的并发度！2024/9/2315封锁协议 Ø锁的转换ü问题的提出：•如果事务一开始就申请排他锁并获得该锁，那么其他事务只能在该事务提交之后才有可能获得锁而继续执行；•也就是说，加强的两阶段封锁协议虽然保证了调度不会发生级联回滚，但却降低了事务之间的并发度ü举例：•事务T12必须对数据项a1加排他锁，结果导致……§11.1§11.1封锁协议封锁协议2024/9/2316封锁协议 Ø锁的转换ü问题的解决：•事实上，只是在T12写a1的时候才需要对a1加排他锁；•因此，一开始T12只要对a1加共享锁就可以，只是在需要时再将其变为排他锁，这样T12和T13就可以真正地实现并发执行。
ü锁的升降级：•upgrade表示将共享锁升级为排他锁，只能发生在……•downgrade表示将排他锁降级为共享锁，只能发生在……§11.1§11.1封锁协议封锁协议2024/9/2317封锁协议 Ø商用DBMS中封锁协议的实现ü在实际的商用DBMS中，根据加强的封锁协议实现的并发控制机制很简单且被广泛采用；ü这样的机制能保证并发控制管理器自动为事务产生加锁、解锁指令：•当事务T进行read(Q)操作时，系统产生lock-S(Q)指令，后接read(Q)指令；•当事务T进行write(Q)操作时，系统检查T是否已在Q上持有共享锁：若有，则系统发出upgrade(Q)指令，后接write(Q)指令；否则系统发出lock-X(Q)指令，后接write(Q)指令；•事务提交或回滚后，该事务持有的锁都被释放§11.1§11.1封锁协议封锁协议2024/9/2318封锁协议 2024/9/2319Ø树状协议ØT1:DBGEØT2:DH§11.2§11.2并发调度中的事务冲突并发调度中的事务冲突ABCDGHJEFI封锁协议 Ø事务冲突ü封锁协议要求事务在操作数据前，必须向并发控制管理器申请锁：•如果事务没有立刻获得相关的锁，就说明系统中有冲突的事务，它必须等待。
ü系统中并发的事务之间存在哪些冲突？这些冲突会造成哪些问题(数据库不一致)？•写读冲突：读未提交的数据，即脏读；•读写冲突：不可重复读；•写写冲突：重写未提交的数据，即丢失修改；•幻影：相同的条件，前后两次查询的结果不同§11.2§11.2并发调度中的事务冲突并发调度中的事务冲突2024/9/2320封锁协议 Ø写读冲突ü读未提交的数据，即脏读：•事务Tj读取了已经被另一个事务Ti修改，但最终却没有提交的数据项Q§11.2§11.2并发调度中的事务冲突并发调度中的事务冲突2024/9/2321封锁协议 Ø读写冲突ü不可重复的读：•当事务Tj读数据对象Q并仍在运行时，事务Ti修改了Q的值如果Tj再次读Q的值……§11.2§11.2并发调度中的事务冲突并发调度中的事务冲突2024/9/2322封锁协议 Ø写写冲突ü重写未提交的数据，即丢失修改：•事务Ti和Tj读入同一数据并进行修改，Tj重复写入Q值，并且Ti先于Tj提交这样Tj提交的结果就破坏了Ti提交的结果，导致Ti的修改丢失§11.2§11.2并发调度中的事务冲突并发调度中的事务冲突2024/9/2323封锁协议 Ø幻影ü事务Tj按一定条件读取了某些数据后，事务Ti又插入(删除)了一些满足条件的数据。
当Tj再次按相同的条件读取数据时，发现多(少)了一些记录§11.2§11.2并发调度中的事务冲突并发调度中的事务冲突仅保证它所访问的数据不被其他事务修改是不够的没有阻止其他事务插入新的满足条件的数据2024/9/2324封锁协议 Ø调度中冲突事务的解决方案：ü封锁协议：•等待执行；•冲突可串行化顺序：事务封锁点的顺序；按事务提交的顺序；每一对冲突事务的可串行化次序是由执行时第一个两者都申请但互相冲突的锁决定的ü时间戳排序协议：•回滚重启；•冲突可串行化顺序：事先选定好了事务的串行顺序，即事务进入DBMS的先后顺序§11.3§11.3时间戳排序协议时间戳排序协议三个顺序的一致性？2024/9/2325封锁协议 Ø时间戳ü基本概念：•对于系统中的每个事务T，把一个唯一固定的时间标志和事务T联系起来，这个时间标志就是事务的时间戳•时间戳是在事务T开始执行前由DBMS的并发控制管理器赋予事务的，记为TS(T)ü时间戳的大小(先后)之分：•如果事务Ti先于事务Tj进入系统，那么：TS(Ti) < TS(Tj)ü实现方式：•使用系统时钟或逻辑计数器§11.3§11.3时间戳排序协议时间戳排序协议2024/9/2326封锁协议 Ø时间戳的特征ü事务的时间戳决定了调度中事务的可串行化顺序：•若若TS(TTS(Ti i)<) 之前的某个串行调度ü每个数据项Q需要和以下两个重要的时间戳相关联：•W-TS(Q)：当前已成功执行write(Q)的所有事务的最大时间戳•R-TS(Q)：当前已成功执行read(Q)的所有事务的最大时间戳•随着读写指令的成功执行，它们随时被更新§11.3§11.3时间戳排序协议时间戳排序协议2024/9/2327封锁协议 Ø协议内容ü时间戳排序协议保证并发调度中任何有冲突的read和write操作按时间戳顺序执行•假设事务Ti发出read(Q)操作：若TS(Ti) 因此，write操作被拒绝，Ti回滚；(写写冲突)其他情况下执行write(Q)操作，并将W-TS(Q)的值设为TS(Ti)•事务Ti被并发控制机制回滚之后，被赋予新的时新的时间戳间戳并重新启动，进入系统§11.3§11.3时间戳排序协议时间戳排序协议 §11.3§11.3时间戳排序协议时间戳排序协议结论：T3的write(Q)已经过时，可以忽略！即使执行T3的write(Q)，W-TS(Q)的值仍然是TS(T4)！2024/9/2333封锁协议 ØThomas(托马斯)写规则ü当事务Ti发出write(Q)操作时：•若TS(Ti) 这里的共享锁不必保持到事务结束；ü读已提交可能造成的数据库不一致性现象：•不能重复读和幻影§11.4§11.4事务的隔离等级事务的隔离等级2024/9/2338封锁协议 Ø可重复读ü只允许事务读取已提交的数据，并要求一个事务在对同一数据的两次读取之间，其他事务不能对这些数据进行更新；ü为保证可重复读，事务必须保持它的共享锁到事务结束(注意：排他锁总是保持到事务结束)这样，其他事物就不能修改可重复读事务正在访问的数据；ü可重复读会极大地降低事务之间的并发度，同时也会造成数据库的不一致性现象：•幻影§11.4§11.4事务的隔离等级事务的隔离等级2024/9/2339封锁协议 Ø可串行化ü并发调度的执行结果等价于一个串行调度；ü在可重复读的基础上，进一步要求一个事务的两次相同的查询之间，其他事务不能插入满足查询条件的数据，避免发生幻影现象；ü同可重复读一样，事务必须保持它的共享锁到事务结束同时，事务不但要封锁现有的数据，还要封锁不存在的数据(插入操作)；ü加强的两阶段封锁协议和时间戳排序协议都能保证它们所产生的并发调度是冲突可串行化的§11.4§11.4事务的隔离等级事务的隔离等级2024/9/2340封锁协议 Ø死锁的定义ü如果存在一个事务集，该集合中的每个事务都在等待集合中的另外一个事务，我们就说系统处于死锁状态。 例如：•在集合{T0,T1,…,Tn}中，若T0在等待被T1锁住的数据项；T1在等待被T2锁住的数据项；……；Tn-1在等待被Tn锁住的数据项；而Tn在等待被T0锁住的数据项，则系统死锁§11.5§11.5死锁处理死锁处理2024/9/2341封锁协议 Ø死锁的解决ü解决死锁问题主要有以下两种策略：•死锁预防：预先防止死锁发生，保证系统永不进入死锁状态•死锁检测与恢复：允许系统进入死锁状态，但要周期性地检测系统有无死锁如果有，则把系统从死锁中恢复过来ü两种策略都会引起事务回滚：•如果系统进入死锁状态的概率相对较高，则通常采用死锁预防策略；•否则死锁检测与恢复策略会更有效ü基于锁超时的机制：•申请锁的事务至多等待给定的时间若……§11.5§11.5死锁处理死锁处理2024/9/2342封锁协议 Ø死锁预防ü预防死锁的最有效的方法就是采用资源抢占与事务回滚技术：•在这种方法里，首先赋予每个事务一个唯一的时间戳，系统利用时间戳来决定事务应当是等待，还是回滚重启；•但调度的并发控制仍然使用封锁机制；•若一个事务回滚，则该事务重启时保持原有的时间戳ü利用时间戳的两种死锁预防机制如下：•等待-死亡(wait-die)机制•受伤-等待(wound-wait)机制§11.5§11.5死锁处理死锁处理2024/9/2343封锁协议 Ø等待-死亡机制ü这种机制基于非抢占技术；ü当事务Ti申请的数据项当前被Tj持有，仅当TS(Ti) 否则，事务Ti回滚例如：•若事务Ti、Tj、Tk的时间戳分别为5、10、15：如果Ti申请的数据项当前被Tj持有，则Ti将等待；如果Tk申请的数据项当前被Tj持有，则Tk将回滚§11.5§11.5死锁处理死锁处理2024/9/2344封锁协议 Ø受伤-等待机制ü该机制基于资源抢占技术，是wait-die的相反机制；ü当事务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.5§11.5死锁处理死锁处理2024/9/2345封锁协议 Ø等待-死亡与受伤-等待的区别ü等待区别：•在等待-死亡机制中，较老的事务必须等待……•在受伤-等待机制中，较老的事务从不等待……ü回滚区别：•在等待-死亡机制中：同一事务可能回滚多次！•在受伤-等待机制中：相关事务只需回滚一次？§11.5§11.5死锁处理死锁处理2024/9/2346封锁协议 Ø死锁检测与恢复ü死锁检测与恢复机制的工作方式如下：•检查系统状态的算法周期性地被激活(实际上它应当是系统中的一个进程或线程)，判断系统中有无死锁；•如果发生死锁，则系统要进行恢复。 ü这种机制的基本要求如下：•维护当前已分配给事务的数据项的有关信息以及任何尚未解决的数据项请求信息；•提供一个使用这些信息判断系统是否进入死锁状态的算法；•提供解除死锁的策略§11.5§11.5死锁处理死锁处理2024/9/2347封锁协议 Ø死锁检测与恢复ü死锁检测：•死锁用称为等待图的有向图来描述；•该图由两部分G=(V, E)组成，其中V是顶点集，E是边集：顶点集由调度中的所有事务组成；如果事务Ti在等待Tj释放所需数据项，则存在从Ti到Tj的一条有向边TiTj•死锁检测算法就是要检查等待图中是否存在有向环，图论中有相应的深度优先搜索算法或广度优先搜索算法来完成此任务：这和前面介绍过的判断调度冲突可串行化的优先图类似§11.5§11.5死锁处理死锁处理2024/9/2348封锁协议 Ø死锁检测与恢复ü死锁恢复：•常用方法是回滚一个或多个事务；•在选择要回滚的事务时要考虑以下情况：选择使回滚代价最小的事务作为牺牲者；决定回滚多远：彻底回滚，即中止该事务尔后重启；部分回滚，只回滚到可以解除死锁为止避免饿死：避免同一事务总是作为回滚代价最小的事务而被选中；常用的方法就是在代价因素中包含回滚次数§11.5§11.5死锁处理死锁处理该事务已计算了多久？已使用了多少数据项？完成还需多少数据项？回滚将牵涉多少其他事务？2024/9/2349封锁协议 Ø概述ü前面讲的read和write操作只能处理数据库中已经存在的数据；ü实际上，事务不仅要访问数据库中已经存在的数据项，而且还要创建新的数据项、删除旧的数据项：•delete(Q)：从数据库中删除数据项Q；•insert(Q)：插入一个新的数据项Q到数据库并赋予Q一个初值。 ü事务T在Q被删除后执行read(Q)或在Q被插入前执行read(Q)都将产生逻辑错误！§11.6§11.6插入与删除插入与删除2024/9/2350封锁协议 Ø删除ü首先要弄清楚调度中删除操作和哪些数据操作冲突？ü假设调度S中两个连续的操作Im和In分别属于事务Ti和Tj，其中Im=delete(Q)：•若In=read(Q)：Im •在时间戳排序协议下：由于在数据项Q存在之前，read(Q)和write(Q)都不可能成功执行，因此，R-TS(Q)与W-TS(Q)都为0如果Ti发出insert(Q)操作，则执行之并将R-TS(Q)与W-TS(Q)的值设为TS(Ti)§11.6§11.6插入与删除插入与删除2024/9/2353封锁协议 小结：并发冲突的解决与实质小结：并发冲突的解决与实质Ø并发控制协议ü封锁协议：•调度中冲突的事务必须有一个要等待，容易产生死锁ü时间戳排序协议：•调度中冲突的事务必须有一个要回滚，不会产生死锁Ø并发控制协议的实质ü并不是告诉DBMS如何让调度中的事务去并发执行，而是在发生冲突的情况下如何让冲突的事务尽可能地串行执行2024/9/2354封锁协议 小结：并发冲突的解决与实质小结：并发冲突的解决与实质Ø可串行化顺序的一致性ü两阶段封锁协议(包括严格两阶段封锁协议)保证调度可根据事务的封锁点串行化；ü而强两阶段协议的本质是事务在提交之后才能释放锁，调度可以根据事务提交的顺序串行化；ü时间戳排序协议保证调度按照事务进入系统的时间(先后顺序)串行化；ü托马斯写规则是对时间戳排序协议的重大改进，它通过删除事务发出的过时write操作来保证调度尽可能地视图可串行化？2024/9/2355封锁协议 小结：并发冲突的解决与实质小结：并发冲突的解决与实质Ø商用数据库管理系统中的并发控制协议ü带有锁转换的强两阶段封锁协议。 Ø调度中的事务冲突与隔离等级ü写读冲突/读未提交ü读写冲突/读已提交ü写写冲突/可重复读ü幻 影/可串行化Ø死锁处理ü利用事务的时间戳来处理封锁协议中容易出现的死锁现象，主要思路是回滚事务2024/9/2356封锁协议 。
