5.3分布式数据库中的死锁处理

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,5.3分布式数据库中的死锁处理,1,.全局死锁与等待图,活锁，死锁和全局死锁,活锁：某个事务处于永远等待状态，得不到执行的机会,解决方法：“先来者先执行”就是简单的排队方式,2,死锁：该集合中的每个事务都在等待该集合中另外一个事务释放它所需要的数据项上持有的锁，它才能继续执行下去，结果任何一个事务都无法继续执行,在分布式数据库中，采用封锁机制，系统有可能发生全局死锁全局死锁涉及两个或多个站点的死锁,3,图.,4,分布式数据库中的数据冗余也会增加更新数据时引起死锁的机会因为更新时需要对全部副本加拒绝锁，有副本的每个站点上都有可能等待另一个事务释放锁，但每个事务只有它全部完成后才能释放拒绝锁，因此造成全局死锁,5,图.,6,等待图（WFC）,等待图是一种用来表示事务之间相互等待关系的有向图，其中指出哪一个事务在等待其他哪个或哪些事务释放锁,图中节点表示事务，边表示等待关系，箭头方向就是等待方向,如下图是.的等待图,7,图.,8,全局等待图（GWFC）：,图.,9,.死锁的预防方法,思想：当有发生死锁危险时，就终止并重新启动其中一个事务或让该事务等待，但如果允许有等待的话，则决不可能发生死锁,因为这种方法不会发生死锁，所以不需要进行死锁的检测和恢复,10,死锁预防是这样进行的：形成死锁的原因是多个事务并发执行，互相等待另一事务所持有的锁，且形成等待回路引起的如果事务T1请求一资源，而该资源被另一事务T2所持有时，则进行一次预防性测试若测试结果有死锁的危险时，或不让T1进入等待状态，并重新启动T1或终止并重新启动T2,11,预防性测试的一般方法是把事务排序,如按它们标识符的词典顺序排序，或按它们的开始时间排序等,预防死锁的方法有两种（按事务开始时间）,非占先权（排队在先者可能失去优先）方法，也叫等待死亡模式,非占先权的理论基础是：最好总是重新启动较年轻的事务允许年老的事务等待已持有资源的年轻事务，但不允许年轻的事务去等待年老的事务,12,占先权（排队在先者绝对优先）方法，也叫伤害等待模式,占先权的理论基础是：因为仍要求终止较年轻的事务，但不允许年老的事务绝对优于年轻的事务，因而只有年轻的等待年老的,这两种方法都不会发生死锁,13,.死锁的检测和解决方法,.死锁的检测和解决的一般方法,检测是通过对全局等待图中的回路的形成进行研究来实现的,如果系统处于死锁状态，就必须撤消一些引起死锁的事务选择撤消哪个事务称为受害者选择通过选择一个或多个受害者事务，这些事务或者被优先执行或被撤消，以打破GWFG中的回路,14,选择最小总开销来打破死锁很困难，以下是可以影响这一选择的因素：,:对事务已经投入了大量努力,:撤消事务的开销,:调度器力图避免撤消那些几乎要完成的事务,:包含该事务的回路数目,15,.分布式死锁检测和解决办法,检测有三种基本方法：集中式，层次式及分布式死锁检测法,（）集中式死锁检测法：某个站点上的锁管理器被指定为整个系统的死锁检测器，其他每个站点上的锁管理器周期性的将它的LWFG传给系统的死锁检测器，然后由系统的死锁检测器形成GWFG并在其中查找回路或者，每个站点上的锁管理器周期性把一张记录本站点上事务开始时间，对锁的持有，请求情况变化的动态表，发给负责处理封锁的站点由它维护一张全局封锁动态表，形成GWFG并在其中查找回路如果GWFG中至少有一个回路，它将选择一个或多个事务，把它们撤消并恢复，释放被占资源，使其他事务继续进行,这种方法很简单，但是传输开销较高,16,（）层次式死锁检测法：以层次方式组织成员数据库管理系统中的死锁检测器按下述步骤进行死锁检测：,:树叶是各站点的死锁局部检测器，它们在本站点建立局部等待图,:本站点的死锁检测器找出本站点的LWFG中的任何回路，并把有关潜在全局回路的信息发送给层次结构中的紧挨的上一层死锁检测器,:每个非本地死锁检测器只对它所涉及的下层进行死锁检测器，合并这些接收到的有关潜在全局回路信息，并找出任何回路,:如果还有上层死锁检测器，将经过简化的有关潜在全局回路信息发给它的上一层死锁检测器，由上一层死锁检测器再进行合并，找出任何全局回路这样逐层进行检查，直到最高层,17,图.,18,（）及分布式死锁检测法：赋予每个站点相同的检测死锁职责简单介绍一下System R系统中使用的方法，它对每一站点的LWFG的形成更新如下：,:由于每一站点接收从其他站点传来的可能的死锁回路，因此向自己的局部WFG增加一些边,:在站点的LWFG中，被增加的用于表示本地事务正在等待其他站点事务的边，同用于表示远程事务正在等待本站点事务的边相连接，该节点称为外部节点（EX）.,向谁传送信息：不知道被涉及的哪些站点时，可以向系统中所有站点传输如果知道死锁回路的头还是尾就可以沿着回路中的站点向前或后传送接收到信息的站点随即根据前面讨论的方法更新其LWFG，并检查死锁,19,.时标技术,.基于时标的并发控制方法,基本概念,基于时标的并发控制方法选择一个事先的串行次序依次执行事务为建立次序，在每个事务初始化时，事务管理器将给每个事务分配一个在整个系统中唯一的时标,时标：是用来唯一识别每个事务并允许排序的标识符特性：唯一性和单调性,时标由两部分组成：,本地计数器值，站点标识符,20,采用时标方法的思想是：给每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行如果发生冲突，是通过撤消并重新启动一个事务来解决的事务重新启动时，则赋予新的时标这个方法的优点是无死锁，不必设置锁封锁和死锁检测所引起的通信开锁也避免了但这个方法要求时标在全系统中是唯一的,21,全局唯一时标的形成和调整,图.,22,.基本时标法,基本时标法使用下述规则：,）每个事务在本站点开始赋予一个全局唯一时标,）在事务结束之前，不对数据库进行物理更新,）事务的每个读操作或写操作都具有该事务的时标,）对于数据库中的每个数据X，记录对其进行读操作和写操作的最大时标，分配记为RTM(X)和WTM(X),）如果事务被重新启动，则被赋予新的时标,23,基本时标法的执行过程,）设read_TS是对数据X进行读操作的时标，如果read_TSWTM(X),则拒绝该操作，并使发出该操作的事务用新时标重新启动；否则执行该操作，并把RTM(X)置为max(RTM(x),read_TS),2)设write_TS是对数据X进行写操作的时标，如果write_TS RTM(X)或TSWTM(X),则拒绝这个写操作，并使发出该操作的事务用新时标重新启动；否则执行这个写操作，并把WTM(X)置为max(WTM(x),write_TS),基本时标法的特点是不会发生死锁，任何一个事务都不会阻塞，如果某一操作不能执行就重新启动，而不是等待高的重启动次数是这个方法的缺点,24,.保守时标法,保守时标法是一种消除重启动的方法，通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝对不被重启动,保守时标法的规则,）每个事务只在一个站点执行，它不激活远程的程序，仅仅能向远程站点发出读或写请求,）每个站点必须按时标时间的顺序发送读写数据的请求，在传输中也不会改变这个顺序，以保证各站点能够按时标顺序接收来自不同站点的全部读写请求,）每个站点都为其他各个站点发来的读写操作开辟一个缓冲区，把接收到的读写操作分别保存在相应的缓冲区中,25,保守时标法的执行步骤,站点站点站点站点n,R11 R21 R31 . Rn1,R12 R22 R32,R13 R23,R24,W11 W21 W31 . Wn1,W22 W32 . Wn2,W23,26,此时按如下步骤执行：,）设RT=min(Rij),WT=min(Wij),）按下法处理在缓冲区队列里的Rij和Wij,:扫描R队列，若各队列中存在(Rij)WT的Rij,按顺序执行它们，执行完成从队列中把它们去掉,:扫描W队列，若各队列中存在(Wij)TS(T)，那么撤消并回滚T；否则创建X的一个新版本Xj，并且令read_TS(Xj)=write_TS(Xj)=TS(T).,）如果事务T发布一个read_item(X)操作，并且X的版本i具有X所有版本中最高的write_TS(Xi)，同时write_TS(Xi)TS(T) 那么,把Xi的值返回给事务T，并且将read_TS(Xi)的值置为TS(T) 和当前read_TS(Xi)中较大的一个,31,.采用验证锁的多版本两阶段封锁,在这种封锁模式中，每个数据项有三种锁：读，写和验证因此对于一个数据项X，LOCK(X)的状态可以是以下四种：读封锁，写封锁，验证封锁，未封锁,在只有读和写的封锁模式图.（a）所示锁的相容性.,采用验证锁的多版本两阶段封锁模式图.（b）所示锁的相容性.,32,读 写 读 写 验证,读 是 否 读 是 是 否,写 否 否 写 是 否 否,验证 否 否 否,33,5.6并发控制的乐观方法,基本思想：对于冲突操作不像悲观方法那样采取挂起或拒绝的方法，而是让一个事务执行直到完成,乐观方法基于如下假设：冲突的事务是少数（），大多数事务是可以不受干扰的执行完毕因此在事务执行过程中，事务都是先对欲操作的数据项的本地局部副本进行操作，执行完毕后再进行检验当不曾发生过冲突时，就把该本地局部副本全局化；若发生过冲突，则回退该事务并作为新事务重新启动,34,35,）读计算阶段：事务从数据库中读数据，进行计算，并为写集合中的数据项确定新值，但这些值暂不写入数据库,读阶段末产生一个更新表包括读集的数据项，带有自身时标；写集数据项的新值该事务自身的时标,）验证阶段：检测事务对数据库的更新是否失去相容性，确定如果将事务的更新应用于数据库，不会违反可串行性,表决规则：更新表读集中的每个数据项的时标和它的本地数据库中存在的对应数据项的时标进行比较，如果它们全部相等，则该站点投肯定票，否则投否定票,36,这里没有考虑更新表挂起的情况即一个更新表从已经表决的时刻算起，到它收到来自源站点的最后决定为止，这段时间称为该更新表在这个站点上未表决（挂起）。如果同一站点上的两个更新表U和U，且两个更新表都更新同一数据项。当U表到达时，U表还未处理或仍处于未表决在状态，而且U和U有冲突，即U的执行结果会引起与U表读集相对应的数据项时标的改变。这时就需要对上述表决规则进行扩充。,37,扩充后的表决规则如下：,:比较U表的读集中的数据项的时标与数据库中对应数据,项的时标；,:如果不等投否定票,:如果相等，若存在一个与U表有冲突操作的未决更新表,U，且U的时标大于U的时标，则投否定票,:如果相等，若存在一个与U表有冲突操作的未决更新表,U，且U的时标小于U的时标，则推迟表决,:如果相等，但不存在未决的更新表，则投肯定票,38,）写阶段如验证阶段获得肯定结果，则把数据更新应用于数据库，对数据库进行更新，否则，忽略所有更新，并重新开始该事务,39,谢谢！,40,