分布式数据库的并发控制读书报告

1、读书报告信息学院 计算机科学与技术杨凌雯 201320602019一、并发控制中的概念和理论1.1 并发控制中的概念数据库的特点就是数据的集中管理和共享。在通常情况下它总是有若干个事务在执行，这些事务可能并发地存取相同的数据，称为事务的并发操作。并发控制是负责正确协调并发事务的执行，保证这种并发的存取操作不致破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确的运行并获得正确的结果。分布式并发控制主要解决多个分布式事务对数据并发执行的正确性。1.丢失更新问题在图5. 1(a)中，数据库中数据项x的初值是100，事务I对x的值减30,事务T2对x的值增加一倍,如果执行次序是先T1后T2,那

2、么结果x的值是140。如果是先T2后T1，那么x的值是170。这两种情况都应该是正确的，因为具体实现时只有其中一种情况.但是若按图5. 1 (a)那样的并发执行,结果x的值是200，这个值肯定是错误的。因为在时间t7丟失了事务T1对数据库的更新操作，因此这个并发操作是不正确的。2.不一致分析问题在图5. 1(b)中，事务T1对x值的值减30，而車务T2只要读出x的值。但在t5时刻，由于T1已更新了 x的值，此时T2使用的x值仍是100，因此就造成了不一致，这个问题称为不一致分析问题。3.依赖于未提交更新的问題在数据库技术中，把未提交的随后又被撤销的更新数据称为“脏数据”。这里事务T2在t4时刻

3、读的x值就是脏数据。1.2事务可串行化理论的基本概念一般来说，对一组并发的分布式事务可能存在多种正确调度，可串行化调度是分布式事务能否正确执行的基本方法。事务的可串行性是指若千个事务并发执行的结果与按希望的顺序执行的结果相同时，称诸事务是可串行的。这就是说，如果事务的并发执行能够通过以一定顺序串行执行就可使数据库处于新的一致状态，那么诸如丢失更新的问题就可能得到解决，这就是串行化理论的观点。1.分布式事务的一个调度在数据库系统中，事务访问数据库中数据的方式是通过发出读操作和写操作原语来实现的。通常，以T1表示某个事务，以Ri(x)表示该事务对数据项x的读操作，以Wi(x)表示该事务对数据项x的

4、写操作，这里不考虑数据项x的粒度。事务的一个操作序列称为一个调度（schedule，也称历史history)，一般以字母S表示。例如： S： R1(x),R2(y),W2(y),R2(x), W1(x),W2(x)S是关于两个事务的一个调度。两个同时访问同一数据项x的操作， 如果其中至少有一个是写操作，那么称这两个操作是冲突的。1）读操作不相互冲突，因此只有两种冲突：读-写冲突（或写-读冲突），及写-写冲突。2）两个操作可以属于同一事务或者两个不同的事务，在后者的情况下，称为两个事务冲突。3）如果有两个事务Ti和Tj，Ti的所有操作都先于Tj的操作，那么这两个事务为串行执行的，必定不会有冲突。

5、2.串行调度对一个串行调度来说，它总是可以正确的执行，执行它可以使数据库保持一致状态。1)如果S正确执行完成，则S中的每一个事务都被提交，由于事务的原子性保证了数据库的一致性。2)如果S在执行时发生故障，若Tk之前的事务都已提交，则夭折Tk，使数据库的状态恢复到Tk前的状态。该状态的数据库也是一致的，因力Tk之前的事务都已提交。3)如果S在执行时发生故障，若Tk之前的事务有被夭折的，则夭折Tk，重做Tk以前已被提交的事务，撤销Tk以前被夭折的事务，此时数据库也是一致的。串行调度总是可以使数据库保持一致。但是，串行调度时系统的运行效率较低。3.可串行化调度串行调度对不会引起冲突的操作要求过高，它

6、们可以进行并行操作。如果在两个操作间存在冲突，这两个操作的执行顺序就很重要；而对于两个不会引起冲突的 操作，它们的执行顺序则并不重要。事务的并发控制主要是正确处理并发执行的事务对数据库的冲突操作。可串行化调度，直观上看，是让有冲突的操作串行执行，非冲突的操作并行执行，所以可串行化调度就是事务并发控制要寻求的基本方法。通常分布式事务的可串行化调度可以转化为子事务的可串行化调度，但涉及多副本选择时,分布式事务调度要多做一个选择副本的操作，以避免冲突操作。1.3 分布式事务的可串行化理论现在给出关下分布式事务的可串行化理论的一些定义。1.事务2.冲突操作如果有两个操作P和Q对同一个数据x进行操作，其

7、中有一个是写操作Wx，则P 和Q称为冲突操作。3.并发事务的一个调度（简称并发调度）第一种情况简单地说明了调度的域是每个事务域的并集。第二种情况定义排序关系为每个事务排序关系的超集，这保证了每一事务内部的操作的顺序。最后一种情况定义了冲突操作的执行顺序。4.串行调度5.一致性调度如果执行一个调度S，使数据库从一个一致状态转变到另一个一致状态，则称调度S 为一致性调度。显然，串行调度是一致性调度，但是一致性调度不一定是串行调度。6.两个调度等价（冲突等价）7.可串行化调度与串行调度等价的调度称为可串行化调度。例1考虑两个事务，分别定义为对于这两种调度，可以产生如下五种调度：S1=R1(x),x=

8、x+10,W1(x),R1(y),y=y-15,W1(y),C1, R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2S2=R1(x),x=x+10,W1(x), R2(x),x=x-20,W2(x), R1(y),y=y-15,W1(y),C1, R2(y),y=y*2,W2(y),C2S3=R1(x),x=x+10,W1(x), R2(x), x=x-20,W2(x),R2(y),y=y*2,W2(y),C2 ,R1(y),y=y-15,W1(y),C1S4=R2(x),x=x-20,W2(x),R2(y),y=y*2,W2(y),C2 ,R1(x),x=x+1

9、0,W1(x),R1(y),y=y-15,W1(y),C1S5=R2(x),x=x-20,W2(x), R1(x),x=x+10,W1(x), R2(y),y=y*2,W2(y),C2 ,R1(y),y=y-15,W1(y),C1如果将事务提交延迟到两个事务操作完成之后执行，有：1）调度S1和S4是串行调度2）调度S2和S1的冲突操作具有相同的顺序，因此是等价调度；S2是可串行化调度，也是一致性调度3）调度S3虽是一致调度，但是它不与S1或S4等价，所以S3不是可串行化调度4）调度S5和S4等价，所以S5是一致调度，也是可串行化调度有以下推论：1）一个可串行化调度必定与某个串行调度等价，且是一

10、致性调度2）一致性调度不一定是可串行化调度3）同一事务集几个可串行化调度，他们的结果未必相同1.4 分布式事务的可串行化调度测试1.使用优先图判别可串行化调度调度 S 的优先图是一个有向图G(N,E) ，其中N: 一组节点N=T1T2,Tn, S中的事务E: 一组有向边E=e1,e2,en, Ti，Tj 是图中的一条边，当且仅当p Ti, q Tj 使得p, q 冲突，并且 p <S q。算法5.1 测试调度S的可串行化1）对于调度 S中的事务Ti，在图中创建一个节点Ti。2）对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的R(X)操作，那么在优先图中创建一条边（Ti

11、Tj ）。3）对于每一种这样的情形：如果S中的在Ti执行了R(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj ）。4）对于每一种这样的情形：如果S中的在Ti执行了W(X)操作后执行Tj的W(X)操作，那么在优先图中创建一条边（TiTj ）。5）当且仅当优先图中没有闭环时，调度S是可串行化的。一般来说，如果调度S的优先序图不存在环路,那么就可有若干个与S等价的串行调度。但如果优先图存在环路，那么不可能创建任何等价的串行调度，从而S是不可串行的。2.分布式数据库中可串行化理论的扩展可串行化理论是事务并发控制的基础，判别一个调度是否为一个一致调度，只需判别其是否可串行化就行，即

12、并发控制程序的主要功能就是为并发执行的诸事务产生一个可串行化的调度。在分布式数据库中，只涉及一个站点上的调度称为局部调度，涉及多个站点上的调度称为全局调度。很有可能局部调度都是可串行化的，而分布式数据库的相互一致性却仍不能保证。3.单副本可串行化相互一致性要求所有数据项副本的值都是相同的，能维持相互一致性的调度称作单副本可串行化(one-copy serifdizable)的调度。一个单副本可串行化的全局调度必须满足以下条件：1)每一个局部调度必须是可串行化的。2)两个冲突操作在它们同时出现的各个局部调度中，必须具有相同的相对顺序。4.读一个/写全部副本控制协议1. 5并发控制机制的常用方法及

13、其分类1.使用协议或规则保证调度是可串行化的如果任意地执行事务，然后再测试结果调度的可串行化，那么一旦它的结果是不可串行化的，就必须取消这个调度的影响。在大多数实际系统中采取的方法是确定保证可串行化的方法，而不必去测试调度本身。在大多数商业DBMS中采取的方法是去设计协议（规则的集合），如果协议被每个单独事务遵循，或者被一个DBMS并发控制子系统执行，就将确保事务参与的所有调度都是可串行化的。2.并发控制机制常用的方法及其分类并发控制机制划分为两神类型：悲观并发控制法和乐观并发控制法。悲观算法使事务的并发执行在执行生命周期的开始就同步化，而乐观算法则将同步化延迟到事务执行周期的结束。具体分类如

14、下图：二、分布式数据库系统并发控制的封锁技术2.1基于封锁的并发控制方法概述基于封锁(locking)的并发控制方法，是一种最常见的并发控制算法，其基本思想是事务访问数据项前要对该数据项封锁，如果已被其他事务锁定，就要等待，直到那个事务释放该锁为止。1.锁的粒度、类型和操作（1）锁的粒度锁的粒度(gmmilarity)是指锁定数据项的范围。所有的并发控制技术都假定，数据库是由许多命名的数据项组成。一个数据项可以是下列的任何一种：1)一个数据库记录；2)数据库记录中的一个字段值；3)一个磁盘块（页面）；4> 一个完整的文件；5)整个数据库。粒度会影响并发控制和恢复的性能，粒度小，并发度高，

15、锁开销大；粒度大，并发度低，锁开销省。数据项尺寸越大，允许的并发程度越低。数据项尺寸越小,数据库中项的数量越多。（2）.锁的类型：共享锁：Share锁，S锁或者读锁。排它锁：eXclusive锁，X锁，拒绝锁或写锁。更新锁：Update锁，U锁。数据项既可以读也可以写，则要用X锁；如果数据项只可以读，则要用 S锁。（3）. 锁的操作：Read_lock(x):读锁 Write_lock(x)：写锁 unlock(x)：解锁数据项的状态：read_locked: 读锁 Write_locked:写锁具体操作方法：1）在系统锁表中记录关于锁的信息。2）锁表中每条记录有四个字段：<数据项名称，

16、锁状态，读锁的数目，正在封锁该数据项的事务>。3）锁状态是上面两种，没有被封锁的数据项，在系统表中没有记录。2.封锁准则和锁的转换(1)封锁准则1）事务T在执行任何read_item（x）操作之前，必须先执行read_lock(x)或者write_lock(x)操作2）事务T在执行任何write_item（x）操作之前，必须先执行write_lock(x)操作3）如果事务T执行read_lock(x)操作,数据项x必须没有加锁或者已经加了读锁，否则事务T的这个操作不能进行4）如果事务T执行write_lock(x)操作,数据项x必须没有加锁，否则事务T的这个操作不能进行5）事务T在完成所

17、有read_item（x）和write_item（x）操作之后，必须执行unlock(x)操作6）如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行read_lock(x)操作7）如果事务T已经持有数据项x上的一个读锁或者一个写锁，那么它不能再执行write_lock(x)操作8）如果事务T没有持有数据项x上的一个读锁或者一个写锁，那么它不能执行unlock(x)操作（2）锁的转换1）特定条件下，一个已经在数据项x上持有锁的事务T ，允许将某种封锁状态转换为另外一种封锁状态。2）比如，一个事务先执行了read_lock（x）操作，然后他可以通过执行write_lock(x)操

18、作来升级该锁。3）同样，一个事务先执行了write_lock(x) 操作，然后他可以通过执行read_lock（x） 操作来降级该锁。（3）基本封锁算法1)简单的分布式封锁方法类似于集中式，数据更新时，要将同一数据的全部副本封锁，然后对其进行更新，更新完成后解除全部上述封锁。但这要在计算机网络的各站点之间进行相当大的消息传输。2)主站点封锁法主站点封锁法模拟集中式，选定一个站点定义为“主站点”，负责系统全部封锁管理。所有站点都向这个主站点提出封锁和解锁请求，所有封锁和解锁信息都被传送到那个主站点管理和保存，然后由主站点去处理封锁事宜。因此，这种方式是集中式封锁方案的扩展。好处就是不太复杂，便于

19、封锁管理，减少通信代价。缺点就是导致系统“瓶颈”，主站点的故障会使系统瘫痪，制约系统的可靠性和可用性。尽管所有的锁都在主站点上存取,但数据项本身仍可以在它们所在的站点上存取。3)主副本封锁法这个方法不指定主站点，而对每个数据项指定一个主副本，不同数据项的主副本放在不同的站点上。当处理程序对某个数据项进行操作时，先对这个数据项的主副本进行封锁，然后再进行操作，对主副本封锁意味着对这个数据项的所有副本都被封锁。主副本按使用情况，尽量就近分布。优点是减轻了主站点的负担，减少了站点间控制消息的传输量，缺点是对只读操作要求过高。(4)快照方法它是实际数据的暂时凝聚，是数据库数据的一种存储方式。快照方法不

20、考虑数据的复制，只考虑每一数据的“副本”和定义在这些“主副本”上的任意多个快照。快照可以定义为一个或多个“主副本”的部分拷贝，也可以定义为某个 或某些“主副本”的全拷贝。2.2两阶段封锁协议1. 两阶段封锁协议保证调度的可串行化如果一个事务所有的封锁操作（读封锁和写封锁）都放在第一个解锁操作之前，那么 就说该事务遵守两阶段封锁协议。第一阶段是扩张或称成长阶段。在这个阶段中，事务只能获得新的数据项锁，而不能释放任何已持有的锁。第二阶段是收缩或称衰退阶段，在这个阶段中，事务只能释放已经持有的锁，而不能获得任何的新锁。封锁点是指事务获得了它所要求的所有锁，并且还没有开始释放任何一个锁的时刻，因此封锁

21、点决定了一个事务生长阶段的结束和衰退阶段的开始。如果允许锁的转换，那么锁的升级（从读锁转换到写锁）必须在扩张阶段完成，而锁的降级（从写锁转换到读锁）则必须在收缩阶段完成。一个很有名的理论Eswaran et al. , 1 976是：遵循了两段锁规则的并发控制算法所产生的调度都是可串行化的，可以证明，如果调度中的每个事务都遵守两阶段封锁协议，就可以保证该调度是可串行化的，不再需要检测调度的可串行性。实施两阶段封锁规则的封锁机制，也就实施了调度的可串行性。两阶段封锁限制了一个调度中可以发生的并发事务的数量。这正是不必检测调度本身就能保证所有调度可串行性的代价。2.基本的、保守的、严格的、严酷的两

22、阶段封锁协议两阶段封锁协议（2PL）存在许多变种。上面讲过的技术称为基本2PL(Basic 2PL)另外，有一个称为保守2PL(Conservative 2PL,或静态2PL (Static 2PL)，要求事务在开始执行之前就持有所有它要访问的数据项上的锁。因此，事务要预先声明它的读集和写集。个事务的读集（Read-Set)就是该事务要读的所有数据项的集合；一个事务的写集 (Write-Set)就是该事务要写的所有数据项的集含，如果有任何事先声明需要的数据项不能被封锁，那么事务就不能封锁任何一个数据项；换句话说,事务必须一直等待，直到所有的数据项都是可封锁的。2.3两阶段封锁协议的实现方法1.

23、集中式两阶段锁协议的实现方法一种实现方法是把封锁管理程序的职责仅限定到某个单独的站点上，这就意味着只有一个 站点拥有封锁管理程序，而其他站点上的事务管理程序是同这个封锁管理程序进行通信， 而不是同它们自己站点上的封锁管理程序进行通信。这种方法也被称作主站点2PL算法。合作站点上的事务执行方式是通过图5. 8中所描述的集中式两段锁(C2PL)算法来实现的。通信发生在事务被初始化的站点上的事务管理程序（协调TM)与主站点上的封锁管理程序，以及其他参与站点上的数据处理器(DP)之间a参与站点是指操作被执行的站点。图5.8中标明了消息的顺序。C2PL算法的一个基本缺点是很容易在主站点处形成瓶颈，主站点

24、上的故障或无法访问将会导致整个系统的失败。2.主副本两阶段锁协议的实现方法主副本2PL（PC2PL）实现方法是对集中式2PL实现方法的向前扩展，以解决后者中潜在的系统性能问题。这种方法是在一些站点上实现封锁管理，每一个封锁管理程序管理所指定的一组封锁单元上的锁。事务管理程序向封锁管理程序发出对某一特定封锁单元的封锁和释放锁的请求。因此这一算法把每一个数据项的副本都作为其主要副本。3.分布式两阶段锁协议的实现方法分布式两阶段锁(D2PL)实现方法力求在每个站点实现封锁管理程序的有效性。分布式2PL事务管理算法与C2PL-TM(集中式两阶段锁事务管理算法）相似，但有两处重大的改进。在集中式两段锁事

25、务管理中，向中心站点封锁管理程序发送的信息，在分布式两段锁事务管理中，将发送给所有参与站点的封锁管理程序；另外的不同之处在于操作并不通过协调者事务管理程序传到数据处理器，而是通过参与者的封锁管理程序。这意味着协调若事务管理程序并不等候“同意封锁请求”信息。2.3多粒度封锁与意想锁1.多粒度封锁多粒度树的根节点是整个数据库，表示最大的封锁数据粒度。叶节点表示最小的封锁数据粒度。图5. 10给出了一个三级粒度树。多粒度封锁协议允许多粒度树中的每个节点被独立地封锁。对一个节点封锁意味着这个节点的所有后裔节点也被加以同样类型的锁。因此，在多粒度封锁中个数据项可能以两种方式封锁，显式封锁和隐式封锁。显式

26、封锁是因事务的要求直接对数据对象封锁；隐式封锁是该数据对象没有直接独立封锁，是由于其上级节点封锁而使该数据对象加上了锁。2.意向锁意向锁的含义是如果对一个节点加意向锁，则说明该节点的下层节点止在被封锁；对任一节点封锁时，必须先对它的上层节点加意向锁。意向锁的思想是：对于一个事务，沿着从根节点到目标节点的路径，指出将在该节点的某个后代节点上需要锁的类型(共亭或排他)，存在三种类型的意向锁：1)意向共享锁(IS)，指示在某些后代节点上将会请求共享锁，如果对一个数据对象加IS锁,表示它的后裔节点拟（意向）加S锁。2)意向排他锁(IX)，指示在某些后代节点上将会请求排他锁。如果对一个数据对象 加IX锁

27、，表示它的后裔节点拟（意向）加X锁。3)共享意向排他锁(SIX)，指示当前节点处在共享方式的封锁中，但是在它的某些后代节点上将会请求排他锁。如果对一个数据对象加SIX锁，表示对它加S锁，再加TX锁， 即SIX S十IX。例如对某个表加SIX锁，则表示该事务要读整个表(所以要对该表加S 锁），同时会更新个别元组(所以要对该表加IX锁）。图5.12(a)给出了这些锁的相容矩阵，从中可以发现这五种锁的强度如图5. 12(b)所示的偏序关系。所谓锁的强度是指它对其他锁的排斥程度。一个事务在申请封锁时以强锁代替弱锁是安全的，反之则不然。三、分布式数据库系统中的死锁处理3.1 全局死锁与等待图1.活锁、死

28、锁和全局死锁封锁技术易于理解也很实用，利用封锁技术，可以避免由于并发冲突操作引起的数据错误，但也可能产生其他一些问题。例如可能存在某个事务永远处于等待状态，得不到执行的机会，这种现象称为活锁(livdock)。在两个或多个事务的集合中，当每个事务T都在等待已经被该集合中另一个事务T' 封锁的数据项时，即该集合中的每个事务都在等待该集合中另外一个事务释放它所需要的数据项上持有的锁，它才能继续执行下去，结果任何一个事务都无法继续执行，这种现象称为死锁(deadlock )在分布式数据库中，采用封锁机制，系统有可能陷于全局死锁状态。全局死锁是指涉及两个或多个站点的死锁。由于这两个事务不在同一

29、站点，引起全局死锁。分布式数据库中的数据冗余也会增加更新数据时引起死锁的机会。因为更新时需要对全部副本加拒绝锁，有副本的每个站点上都有可能等待另一个事务释放锁，但每一事务只有在它全部完成后才能释放拒绝锁，因此造成全局死锁，如图5. 5所示。2.等待图等待图是一种用来表示事务之间相互等待关系的有向图，其中指出哪一个事务在等待其他哪个或哪些事务释放锁。3.2死锁的预防方法预防死锁的方法是一种比较保守的方法。这类方法的想法是当有发生死锁危险时，就中止并重新启动其中一个事务或让该事务等待，但如果允许有等待的话，则绝不可能发生死锁。因为在这种方法中不会发生死锁，所以不需要进行死锁的检测和恢复。死锁预防是

30、这样进行的：形成死锁的原因是多个事务并发执行，互相等待另一事务所持有的锁，且形成等待回路面引起的。如果事务T1请求一资源，而该资源被另一事务 T2所持有时，则进行一次预防性测试。若测试结果表明有死锁的危险时，或不让T1进入等待状态，并重新启动T1或中止并重新启动T2。预防死锁的方法有两种：(1)非占先权（排队在先者可能失去优先)方法也称等待-死亡(wait-die)模式。如果Ti对已被Tj锁定的一数据项请求封锁的话，则只有在Ti比Tj年老时(Ti<Tj)，才允许T1等待（失去优先）。如果Ti比Tj年轻(Ti>Tj）, 则Ti被终止并带有同一时间戳重新启动。这个方法的理论基础是：最好

31、总是重新启动较年轻的事务。所以，为了实现非占先权的方法，允许较年老的事务去等待已持有资源的较年轻的事务，但不允许较年轻的事务去等待较年老的事务。(2)占先权(排队在先者绝对优先)方法也称伤害-等待(wound-wait)模式。如果T,对已被T,锁定的一数据项请求封锁的话，则只有在Ti比Tj年轻(Ti>Tj）时，才允许Ti等待；否则（Ti<Tj)，Tj被终止并带有同一时间戳重新启动，而允许Ti得锁执行。这个方法的理论基础是：因为仍要求终止较年轻的事务，且允许年老的事务绝对优于年轻的事务，因而只有年轻的等待年老的。从不会发生死锁这一点上来说，上面的两种方法都是正确的，并且两者都是启动年

32、 轻的事务。但是,这两种技术都可能引起一些事务不必要的撒销和重新开始，即使这些啪 务在实阳中从来也不会引起死锁。这是它们的共同之处,但它们也存在一些差别，这些差 别对选择采用哪一种方法很起作用。1)在非占先权方法中，一事务只有当它请求访问一新的数据项时，才有可能被重新启动，而对已经访问了全部所需数据项的事务，在任何情况下都不会被并发控制机构所中止。这个特性对于必须执行在外部世界中，不可逆动作的事务来说是极重要的。例如，分配现金或控制一个过程。而在占先权法中，对一持有锁的事务虽然已快结束，不再要锁，但仍有可能因另一更年老的事务要求访问同一-数据项而被中止。力了避免这种可能性，可以把占先权方法做如

33、下更新：令Tj为年轻且持锁的事务，如果Tj已经不再请求锁(进入收缩阶段）时，就不终止Tj而让它等待。这样，保证了已获得全部数据项并要求结束的事务决不会被重启。因力进入收缩阶段的Tj，它不会再要求获得新锁，不再请求新锁的事务就不会引起死锁，所以就不用终止Tj。2)在非占先权方法中，有可能较年老的事务等待年轻的，所以在某种意义上来说事务变老就失去了优先性；在占先权法中，则事务变老就增加了优先性。3)在非占先权方法中，令事务Ti比已锁住一资源的Tj年轻。当Ti试图锁住该资源时，Ti被中止并重新后动。假定Ti再次试图锁住同一资源，如果Ti长期持有该资源，则 Ti将被多次重新启动，在占先权方法中则相反，

34、如果Ti持有一资源，并因一较老的事务Tj要求此同一资源而被重新启动的话，则Ti新的请求将不会被重新启动，只是等待直到Tj结束为止。因此，对占先权法来说，只有一次重新启动。3.3 死锁的检测和解决方法1.死锁检测和解决的一般方法死锁是一种潜在现象，如果在一个系统中存在死锁，那么只有在外界干预的情况下才能消除死锁。死锁检测通过对全局等待图中回路的形成进行研究来实现。如果系统处于死锁状态，就必须撤销一些引起死锁的事务，选择撤销哪些事务称为受害者选择 (victim selection)。通过选择一个或多个受害者事务，这些事务将被优先执行或撤销，以打破GWFG中的回路。但是对一组陷入死锁的事务选择最小

35、总开销来打破死锁是困难的，然而可以考虑一些会影响这一选择的因素：1）对事务已经投入了大量努力。2）撒销事务的开销。3）调度器力图避免撤销那些几乎要完成的事务。4）包含该事务的回路数目。一般地，受害者选择算法应该避免选择那些已经运行了很长时间的事务，以及已经执行了许多更新操作的事务，而应该选择那些还没有执行许多更新操作的事务。2.分布式死锁检测和解决方法检测分布式死锁有三种基本方法，通常称为集中式、层次式及分布式死锁检测法。(1)集中式死锁检测法某个站点上的锁管理器被指定为整个系统的死锁检测器。其他每个站点上的锁管理器周期性地将它的LWFG传给系统死锁检测器，然后由系统死锁检测器形成GWFG并在

36、其中查找回路。或者，其他每个站点上的锁管理器周期性地把一张记录本站点上事务开始时间、对锁的持有、请求情况变化的动态表，发送给负责处理封锁的站点。由它维护一张全局封锁动态表，形成GWFG并在其中查找回路。(2)层次式死锁检测法层次式死锁检测法以层次方式组织成员数据库管理系统中的死锁检测器。因为非本地死锁一般也只涉及到几个相互靠近的站点，在这种情况下，它们能够发现死锁而不必与一远程的中央站点进行通信。层次式死锁检测法就是利用这种可能来减少通信费用。(3)分布式死锁检测法分布式死锁检测法赋予每个站点相同的检测死锁职责。因此，正如在层次式死锁检测中一样，每个站点上的本地死锁检测器互相传送各自的LWFG

37、 (实际上只传送潜在的死锁回路）。四、分布式数据库系统并发控制的时标技术4.1 基于时标的并发控制方法1.基本概念与基于封锁的算法不同，基于时标的并发控制算法并不试图通过互斥来支持串行性，而是选择一个事先的串行次序依次执行事务。为建立这个次序，在每个事务初始化时，事务管理器将给每个事务Ti分配一个在整个系统中唯一的时标Ts（Tj）。时标是用来唯一地识别每个事务并允许排序的标识符。唯一性只是产生时标的属性之一，另外一个属性是单调性，同一事务管理程序所产生的两个时标将是单调递增的。2.全局唯一时标的形成和调整如果全局唯一时标由本地计数器值和站点标识符构成，如图5. 20所示。有两个站点，在每一站点设置一计数器，每当发生一个事务，计数器值加1，这解决了同一站点内事务的次序问题。对不同站点，在发送报文时把本站点的计数器值包