是数据库技术和计算机网络技术相结合的产物OracleSybase.ppt

第十六章分布式数据库系统考虑计算机网络环境下的数据库系统。如果全体数据存放在某个结点，则称该系统为集中式数据库系统。前边各章讨论的数据库系统都属于集中式数据库系统。集中式数据库系统有一些优点，例如人员易于管理、数据冗余较低、符合某种安全性，以及应用程序和数据之间有较高的独立性等。但随着数据库应用的不断发展，人们发现，在许多应用场合，如果把数据库的数据适当地分散在若干个网络结点上，用户作局部应用时存取本地结点的数据，作全局应用时存取多个结点的数据，这样安排更能提高系统能力和满足需求。这种在物理上具有分布性而在逻辑上具有整体性的数据库系统就是本章要讨论的分布式数据库系统(DDBS)。DDBS是数据库技术和计算机网络技术相结合的产物。Oracle、Sybase、Informix及DB2等关系数据库管理系统均具有一定的分布式数据库管理系统(DDBMS)的功能，可用来建立DDBS.第一节概述第二节分布式数据库设计第三节分布式数据库查询处理第四节分布式数据库系统的事务处理,P,第一节概述一计算机网络计算机网络由多个计算机通过通信网络相互连接组成。每个计算机称为一个结点。结点之间的连接方式称为拓扑结构。下图列出了常用的拓扑结构。,A,B,C,D,A,B,C,D,A,B,C,D,E,F,A,O,C,B,A,B,C,D,完全连接,部分连接,树型连接,环型连接,P1,若网络中的结点分布范围较大，例如全国，则称之为广域网。广域网一般由电话线、微波、卫星和光纤等通信媒体实现连接。若结点分布范围较小，例如大楼内，则称为局域网。局域网一般由双绞线、同轴电缆和光纤等媒体连接。相对于广域网，局域网的速度较高，可靠性较好。,星型连接,接下页,二分布式数据库和分布式数据库系统分布式数据库(DDB)是分布在计算机网络上的多个逻辑相关的数据集合。分布式数据库系统(DDBS)是建立在计算机网络基础上管理DDB的数据库系统。DDB有两特点：,P11,接下页,1)逻辑整体性分布在各结点上的数据文件具有逻辑联系和相关结构，可通过公共界面访问。支持多结点存取的全局应用。,2)分布性系统中的文件分布在多个结点上，各结点具有独立的数据库处理能力(称为结点自治或局部自治)。支持本结点局部应用,DDBS由多个局部数据库系统组成，每结点有其局部数据库系统。各结点既可处理只对本结点存取的局部事务，也可参与全局事务的处理，利用通信存取多个结点的数据。例如，由多个支行组成的银行系统，各支行可处理本地业务，但跨支行的业务则是需要访问多个支行数据的全局事务。,计算机,DB,T,T,T,计算机,DB,T,T,T,计算机,DB,T,T,T,通信网络,计算机,DB,T,T,T,结点1,结点2,结点3,结点4,分布式数据库系统DDBS有下述五个特点：1)网络透明性用户不必知道分布位置就可访问数据。2)数据冗余和冗余透明性适当的数据冗余可降低通信开销和增加系统可靠性。但数据一致性的维护由系统负责，用户不必知道冗余的细节。3)数据片段透明性关系以某种方式分割为若干个片段，分布在不同结点上。用户无须知道分割的细节。4)局部自治性各结点能独立处理本地存取的局部数据库事务。5)数据库的安全性、完整性和并行事务的可串行性不仅要保证各个局部数据库数据的安全性和完整性，还要保证全局数据库的安全性和完整性。此外还要保证并发事物的可串行性。DDBS有下述主要优点：分布式控制：常用数据存储在本地。支持本地事务和全局事务;增强数据共享性：本地共享和全局共享是数据共享的两个层次。扩充性能好：容易扩充。扩充不影响原有的用户程序。,P12,接下页,现实世界,外模式,概念模式,内模式,现实世界,外模式,全局概念模式GCS,LCS1,LCS2,LCS3,LIS1,LIS2,LIS3,局部概念模式,局部内模式,用户视图,数据视图(逻辑结构),物理结构,四层模式之间有三个映射。各层映射带来了不同的数据独立性。,三层模式间有两个映射,三分布式数据库的结构集中式数据库系统的结构是三级抽象模式结构，由外模式、概念模式和内模式组成。由于有地域映射的概念，DDBS多增加了一级抽象，即把概念模式分解为全局和局部两级概念模式。因此DDBS的结构是四级模式结构。,逻辑映射,地域映射,物理映射,P13,集中式数据库结构,分布式数据库结构,第二节分布式数据库设计DDBS的设计方法与集中式DBS在总体上是相似的。除了前边介绍过的数据库一般设计方法之外，DDBS主要考虑数据库的分布问题，即如何把数据库R的数据合理地分布在多个结点上。本节介绍三种分布方法和有关的命名问题和分片透明性问题：一重复存储分布方法：每结点存储R的一个副本；二分片存储分布方法：将R划分为多个片段，每个片段存储在一个结点；三组合存储分布方法：上述两种方法的组合。四命名和局部自治性五分布透明性,P2,数据的重复存储这种分布方法把全部或部分数据库文件重复存储在至少两个结点上。如果数据库文件R在每个结点都有一个副本，则R的这种重复存储方式称为完全重复存储方式。数据库重复存储的优点是：1.可靠性较高：当用户查询需要访问某结点存储的R，而该结点恰好出现故障，此时系统可以使用别的结点存储的R副本，继续进行用户查询。2.并发性较好：读操作是数据库的主要操作。数据库的多副本存储允许读操作以并发方式进行，从而降低读操作的时延。3.通信开销较低：当能在本地的数据库副本中读到所需要的数据时，就能避免了结点间的通信开销。加快了系统的响应速度。数据库重复存储也有如下的缺点：1.数据重复存储带来了数据一致性的维护问题。任何改变数据库的操作都必须在全体副本进行。于是增加了数据更新的开销。2.数据重复存储也增加了并发控制的复杂性。若要对一个记录加锁，则还必须对其所有副本加锁。于是增加了并发控制的开销。,P21,数据的分片存储这种分布方法把关系划分为若干个片段并把这些片段分布在不同的结点上。片段的划分必须保证数据库语义不变、信息的不重复和可重构。划分的粒度要适中，过大不利于数据分布和并发控制，过小则增加查询的复杂性。粒度的划分取决于DDBS上运行的各应用程序。划分片段有如下三种方法：1)水平划分：把关系的元组作不重叠的分组。可以用选择操作完成水平划分。例如对总行的客户关系可按所属支行作水平划分。同一支行的客户划分为同一个片段。2)垂直划分：对关系模式分解为几个子模式，每个子模式属性集含有原关系模式的键，或系统专门设置的直接检索元组的实际地址(元组标识符)。可以用投映操作完成垂直划分。由于子模式含键，故各片段通过自然连接可正确恢复原关系。3)混合划分：是上述两种方法的混合方法。例如先作垂直划分，然后作水平划分。,P22,接下页,支行帐号姓名余额北京101陈大1000北京102赵二90,支行帐号姓名余额元组标识北京101陈大10001北京102赵二902上海201张三983上海202李四804,帐号余额元组标识10110001102902201983202804,支行帐号姓名余额上海201张三98上海202李四80,支行姓名元组标识北京陈大1北京赵二2上海张三3上海李四4,垂直划分,水平划分,水平划分和垂直划分的例子,P221,接下页,数据的组合存储这种分布方法组合了重复存储和分片存储两种方法。给定一个数据库关系R，先对R作片段划分。任何片段既可以单独存放在某个结点，也可以重复存储在若干个结点上。这取决于应用的特点。例如，总行的客户关系既按所属支行作水平划分，也按子属性结构作垂直划分。右边案例把一个关系划分为四个片段。,P23,接下页,支行帐号姓名余额元组标识北京101陈大10001北京102赵二902上海201张三983上海202李四804,帐号余额元组标识201983202804,支行姓名元组标识上海张三3上海李四4,帐号余额元组标识10110001102902,支行姓名元组标识北京陈大1北京赵二2,其中片段1和片段2的副本存储在任何一个结点上。片段3和片段4有两个副本，一个存储在本地，另一个存储在总行。,1,2,3,4,命名和局部自治性数据项的唯一命名在集中式数据库系统中是很容易得到保证的。但在DDBS存在数据重复存储现象的环境下，要保证同一个数据项的不同副本有不同的名字就不是一个简单的问题。基本的命名方法是用名字服务器集中管理。各数据项的各个副本均在名字服务器注册。这样就可以避免发生名字的冲突。集中管理命名的方法有如下缺点：1.名字服务器成为一个瓶颈；2.名字服务器的任何故障将导致系统瘫痪；3.名字的集中管理降低了局部自治性。针对这些缺点，可作这样的改进：在数据项名字前加结点前缀。由于不同结点有不同的名字，所以这样改进以后就可以避免同一个数据项的不同副本发生冲突。而且不必集中控制。这种方法虽然提高了局部自治性，但降低了网络透明性，因为用户必须指明数据项副本的存放地点。,P24,分布透明性DDBS的分布透明性是指如下的三层透明性：1.分片透明性：这是分布透明性的高层。用户对全局关系进行操作，不必考虑分片划分和存储的细节。分片划分结构的任何改变，均不影响用户对关系的操作。用户看到的是一个集中式DBS。2.位置透明性：这是分布透明性的中层。用户对关系的分片进行操作，不必考虑分片的存储分布。分片存储分布的任何改变，均不影响用户对分片的操作。用户看到的是被逻辑划分的关系。3.局部数据模型透明性：这是分布透明性的低层。用户对存储在某结点的关系分片进行操作，不必考虑当地采用的数据存储结构和访问方法等物理细节以及查询语言转换细节。用户看到的是各结点上的逻辑数据。,P25,接下页,情况1：系统具有分片透明性。算法如下：scanf(%S,sno);读学号到变量snoexecsqlselectsn,ageinto:sname,:sage;fromSwheresno=:sno;printf(%s,%d,sname,sage);,学生数据库S全局关系,S_A理科片段,S_B文科片段,场地1,snosnssage,DDBS的透明层次越高，应用程序就越简单。为了说明这个道理，我们考察下边的例子。,场地2,场地3,分片透明性,位置透明性,应用程序不必考虑关系的逻辑划分和各分片的存储场地。,P251,接下页,例：设DDBS有全局关系S(sno,sn,ss,age)。它划分为两个片段：S_A和S_B.这两个片段分别有1个和2个存储场地。见下图。查询：键入学号，查找学生并在屏幕显示该学生的资料。,学生数据库S全局关系,S_A理科片段,S_B文科片段,场地1,snosnssage,场地2,场地3,分片透明性,位置透明性,应用程序需要考虑关系的逻辑划分，但不必考虑分片的存储场地。,情况2：系统具有位置透明性，不具分片透明性。算法如下：scanf(%S,sno);读学号到:snoexecsqlselectsn,ageinto:sname,:sage;fromS_A逐个分片试探wheresno=:sno;if(!found)execsqlselectsn,ageinto:sname,:sagefromS_Bwheresno=:sno;printf(%S,%d,sname,sage);,接下页,P252,学生数据库S全局关系,S_A理科片段,S_B文科片段,site1,snosnssage,site2,分片透明性,位置透明性,情况3：系统仅具局部数据模型透明性，但不具位置透明性。算法如下：scanf(%S,sno);execsqlselectsn,ageinto:sname,:sage;fromS_Aatsite1wheresno=:sno;if(!found)execsqlselectsn,ageinto:sname,:sagefromS_Batsite2wheresno=:sno;printf(%S,%d,sname,sage);,应用程序不仅要考虑关系的逻辑划分，而且要考虑分片的存储场地。,P253,第三节分布式数据库查询处理分布式数据库管理系统概述分布式数据库管理系统(DDBMS)是对分布式数据库实施建立、管理和维护的软件系统。它由全局数据库管理器和局部数据库管理器组成。全局数据库管理器的基本功能是提供用户查询界面、作全局级别的优化、将操作分配到有关结点并等待这些结点的返回结果。在执行全局用户查询的过程中，各结点的全局数据库管理器(全局查询执行器)需要互相通信；局部数据库管理器的基本功能是接受全局数据库管理器的局部查询命令、作本地存取优化、实施磁盘操作并将结果返回全局数据库管理器。,全局数据库管理器,局部数据库管理器,全局数据库管理器,局部数据库管理器,用户,结点1,结点2,通信,P3,接下页,用户界面处理器,语义数据控制器,全局查询优化器,全局查询执行器,外模式,全局概念模式,全局数据模式,用户,通信,全局数据库管理器的组成,结点1,本结点的局部数据库管理器,本地查询任务,提交本地查询结果,相关站点的全局查询执行器,接收用户命令，进行预处理，接收全局查询执行器返回的查询结果，进行后处理，返回给用户按完整性和安全性检查用户查询的合法性将全局查询转化为一组优化的局部查询，分配到有关结点协调控制全局用户查询计划的分布式执行,P31,接下页,局部查询优化器,局部系统恢复处理器,数据存取器,数据库,局部概念模式日志文件局部内模式,局部数据库管理器的组成,对全局查询优化器分配到本结点的查询进行优化，选择存取数据项的最佳路径，形成局部查询计划保证本结点的局部系统发生故障时通过恢复处理，使数据库状态仍然正确执行存取指令，负责本地的并发控制和系统恢复，查询结果回送至全局查询执行器,全局查询执行器,P32,接下页,分布式查询处理分布式的查询处理，既要考虑存取磁盘的复杂性，又要考虑通信时间开销和多结点并发执行带来的性能提高。处理的步骤是：第一步：查询变换。把全局查询的元组演算定义转换为关系代数定义。第二步：数据定位。把全局概念模式上的查询转换为局部概念模式上的低层(片段)查询。第三步：全局查询优化。考虑片段特性和通信开销，优化片段查询的操作顺序，重点是优化多结点连接操作。若系统以通信开销为主，通常采用半连接技术进行优化。这个阶段完成后，查询被分解为一组在不同结点上执行的片段查询。第四步：局部查询优化。为每个局部查询优化执行计划，完成本地局部查询的优化处理。局部查询优化的策略和方法与集中式数据库系统相同。,P33,第四节分布式数据库系统的事务处理分布式数据库系统的事务由分布在若干个结点上的子事务组成。事务的执行要保持原子性，多用户系统的事务还要保证可串行性。这跟集中式数据库系统的要求是相同的。但在分布式环境下，情况变得更为复杂。本节讨论如何通过分布式并发控制和系统恢复，保证事务的原子性和可串行性。一分布式事务处理器的结构二分布式系统恢复技术三分布式并发控制技术四分布式死锁处理技术,P4,分布式事务处理器的结构分布式事务处理器是分布在所有结点上的事务处理系统。它由各个结点的局部事务处理器组成。相关结点的局部事务处理器协作处理全局事务。每个结点的局部事务处理器包含两个子系统：1.事务处理器其功能是处理在本地运行的事务，与其它结点的事务协调器协作，保证全局事务的原子性和可串行性。其任务是：管理和维护日志文件，以备系统恢复。对本地执行的事务作并发控制。2.事务协调器协调所有在本地启动的事务。对其中的全局事务T，其任务是：分解T为多个子事务，并把子事务分布到有关结点并发运行。执行提交协议。终止处理T，保证T或在所有结点提交，或在所有结点放弃。,结点A发起全局事务,事务事务处理协调,结点C执行子事务,结点B执行子事务,事务事务处理协调,事务事务处理协调,P41,执行提交协议,子事务,子事务,二分布式系统恢复技术1故障与故障恢复DDBS必须能对特定故障范围内实现故障恢复。能处理的故障类型：内存故障、辅存故障、结点故障、连接故障、信息丢失和网络分割。对故障恢复的要求：能检测故障并调整系统，当故障修复后能使系统恢复到正确状态。下表描述了系统发现故障后的执行过程和恢复后的执行过程。,发现故障后执行的操作故障恢复后执行的操作结点故障封记故障结点。取消对它的访修改结点有关信息表，问。放弃其上的在线事务。正确反映系统的变化用备用服务器代替故障服务器通信故障任何重构策略须能保证当网络被割断的网络重新连接分割时仍可正确工作后须广播连接恢复消息,P42a,接下页,2提交协议发起全局事务的主结点把子事务分配给相关的从结点作并发执行。只要存在着某个从结点对子事务没执行、没按时完成、虽然按时完成但出现错误，虽然按时正确完成但因通信故障无法向主结点报告运行结果，那么这个全局事务将可能使数据库处于错误的状态。为了能够保证分布式系统任何时候都处于正确的状态，要求分布式事务必须具有原子性，即：任何事务要么在所有有关的结点提交，要么在所有有关的结点放弃。为此，每个结点的事务协调器必须执行一个提交协议：两段式或三段式的提交协议。前者较简单，但有一些缺点。后者克服了前者的缺点，但增加了处理的复杂性和额外开销。无论是两段式还是三段式的提交协议，其执行过程都是从发起全局事务的主结点收到各从结点的报告，确知它们已经完成其局部子事务的时刻开始。,P42b,接下页,3两段式提交协议:设主结点S启动全局事务T，S的协调器为C。当所有从结点向C报告，已完成规定的子事务，于是C执行：阶段1C在日志写记录，并向从结点发prepare,T，从结点接报后即根据自身情况决定是放弃或提交。放弃：在日志写，写盘后，回复C：abortT提交：在日志写，写盘后，回复C：readyT阶段2若C按时收到所有结点readyT，则决定提交事务：在日志写，写盘后，向从结点发commitT；否则放弃事务T：在日志写，写盘后向从结点发abortT,协调器C,从结点1,从结点2,从结点3,写并发prepare写并发ready/abort写并发commit/abort写commit/abort执行redo/undo,时间,主结点S,主结点S(C),从结点U,P42c,接下页,4使用两段式提交协议处理故障：(1)结点故障设事务T由主结点S发起，其协调器为C。运行中从结点U发生故障，当它恢复后，须按日志如下操作：若日志不含T的记录，放弃事务T；若日志含，则执行redo；若日志含，则执行undo；若日志含，则联系主结点S的协调器C.若C正常，则C通知U提交或放弃，U除了记日志外，分别只需作redo或undo；若C异常，则U广播querystatusT请求援助，每个结点收到广播后须检查日志，确定是否曾介入事务T，若曾介入，则将自身的结局情况告诉U执行。若无结点告诉U，则U只能定期作求援广播querystatusT.,P42d,接下页,主结点,S,U,U,(2)主结点S的协调器C故障T的命运由所有从结点U决定。若某正常从结点日志含，则判定为提交；若某正常从结点日志含或，则判定放弃；若某正常从结点日志既不含也不含，说明C未指示提交，但有可能已指示放弃，与其等待C恢复，还不如判定为放弃；其它情况：全体正常从结点日志的最后记录是，这些结点只能等待C恢复，继续占有系统资源，造成阻塞。(3)网络链路故障：链路L故障，等价于相关结点故障，可使用上述处理。(4)网络分割为几个子网若执行事务T的所有结点同在一个子网，则网络故障不影响提交，否则可归结为链路故障。二段式提交协议缺点：协调器C发生故障可能导致从结点等待协调器C恢复，造成阻塞于是有人提出三段式提交协议。,接下页,P42e,主结点,S,U,U,5三段式提交协议三段式提交协议在某些故障不出现的情况下，可以避免阻塞，但须满足三条假定：网络无分割；结点不全死；事务同时正常结点至少K个。设事务T由主结点S启动，S的协调器为C，当各从结点向C报告已完成子操作，于是C作如下操作：阶段1C把写入日志，向从结点发prepare,T，从结点接报后，即决定是放弃或提交。放弃：在日志写，并即答复CabortT；提交：在日志写，并答复CreadyT。阶段2若C按时收到所有结点readyT，则决定预提交，在日志写，并向从结点发precommitT，从结点将此信息写入日志并向C回送acknowledgeT；否则放弃事务T，将写入日志并向有关结点发送。阶段3仅在阶段2中C作出预提交决定的情况下，才执行以下操作：若C发precoT后预定时间内有k个结点答复acknT即决定提交，把写入日志并向有关结点发送，对方收后写入日志；否则决定abort.,P42f,接下页,阶段条件阶段1阶段2阶段3各从点按时收到否仅适于预提交情况报告完全体从点ack响应的否成操作正常响应则数目足够则协调器C先写日志preparepre_commitabortcommitabort后发送preparepre_commitabortcommitabort从结点U先写日志ready/nopre_commitabortcommitabort后发送ready/noackabortackabortDB操作redoundo,三段式提交协议操作一览表,P42g,接下页,6使用三段式提交协议处理故障(1)从结点故障从结点U从故障恢复过来后，首先检查日志，确定故障发生时未结束的事务T.设T由主结点S发起，S的协调器为C.U按日志如下操作：若日志含，则执行redo；若日志含或，则执行undo；若尾句是或，则联系主结点S的协调器C，共商T的命运，若C正常，如果C通知U提交，则U记日志并作redo；如果C通知U放弃，则U记日志并作undo；如果C通知U预交，则U记日志并回送acknowledgeT.若C超时无反应，则U执行一个谐调器故障协议。(2)协调器故障当某从结点U发现协调器C超时不答，即执行协调器故障协议，选举代理协调器。当原协调器恢复，代理协调器即退出。,P42h,接下页,(3)协调器故障协议设不发生网络分割故障.(该假设对本协议很重要)，用某种协议选举代理协调器CN，CN向全体参与者询问局部状态，每个参与者检查日志，按如下逻辑向CN报告自身状态：当日志含commitT，为提交状态；当日志含abortT，为放弃状态；当日志尾句是readyT，为准备状态；当日志尾句是pre_commitT，为预提交状态；当日志既不含readyT也不含abortT时为非准备状态.；CN根据收到的答复，按下列逻辑作出决定：当有参与者是提交状态，则决定提交；当有参与者是放弃状态，则决定放弃；当没有参与者是提交状态，也没有参与者是放弃状态，但有参与者是预提交状态，则决定重新再次运行阶段2；其它情况决定放弃。,P42i,分布式并发控制技术为了使集中式数据库系统并发控制技术(这里是指锁技术和时间印技术)能适用于分布式环境，需要对其作修改和扩充。1锁技术(1)分布式锁技术分布式锁技术要求系统无重复存储的数据。每结点设置一个局部锁管理器，接受事务对本结点数据项Q的加解锁请求。当Q无不相容锁时才接受请求，向发出请求的结点返回同意加锁的信息。否则，加锁请求被推迟。加锁请求需要两次通信，解锁请求需要一次通信，实现较简单，但对死锁的处理复杂。(2)集中式锁技术整个系统仅有一个锁管理器，设置在某个结点上。全部加解锁请求集中到该结点申请。这种方法的优点是管理和死锁处理都很简单，缺点是锁管理器成为系统的瓶颈，因而带来脆弱性。,P43a,接下页,2.时间印协议在集中式数据库系统，时间印技术的原理是：1)按进入系统的时间为每个事务分配唯一的时间印。2)在处理冲突操作中，放弃某些时间印较小的事务并令其重启获取较大的时间印。保证先进入，先执行。把这种技术推广到分布式数据库，关键是建立分布式环境下产生唯一时间印的策略。(1)产生唯一时间印有两种策略：集中式产生策略：设置一个职能结点，用逻辑计数器或局部时钟为系统的每个事务产生时间印。分布式产生策略：各结点自行为本地发起的事务产生时间印，在时间印的后边配上结点的标识符，作为系统的时间印。(2)并发控制策略适当地结合基本时间印策略和提交协议的做法，阻止事务读取未提交数据，保证调度可串行化。,P43b,四分布式死锁处理技术前边讨论过集中式系统预防死锁发生的措施，这些措施在分布式环境中可能引起不必要的等待、嵌套放弃现象以及无关结点的参与。本节讨论死锁检测和处理，问题的核心是维护等待图。局部等待图局部等待图描述的是结点内访问相同数据项的事务之间的等待解锁的关系。图中的点表示正在访问该场地某数据项的事务，有向边PQ表示事务P欲访问的本地数据项正被事务Q所持有，仅当事务Q对该数据项解锁后，事务P才能实施对该数据项的加锁访问，因此有向边PQ反映了事务P等待事务Q解锁的依赖关系。全局等待图全局等待图是对各场地局部等待图的综合。,T1,T2,T3,T5,T1,T2,T3,T5,T4,结点1局部等待图,结点2局部等待图,全局等待图,T2,T3,T4,任何场地的局部等待图若有环，则表示出现死锁，但即使所有局部等待图都无环，全局等待图仍可能有环，可有死锁发生。,A,B,C,1.A,2.B,2.C,P44a,接下页,构造和维护全局等待图的方法有集中式和分布式两种。1维护全局等待图的集中式方法：选择一个结点作为死锁检测器，全局等待图存放在这个结点上。由于通信延迟，完全实时并且完全准确的全局等待图是难以实现的，只能构造反映近似状态的全局等待图。近似的标准是：全局事务协调器在任何时候启动死锁检测算法，都能准确报告系统是否处于死锁状态之中。死锁检测器的功能是：1)存放全局等待图；2)监视各局部等待图，将其变化反映到全局等待图中；3)死锁检测算法触发时能准确报告系统是否出现死锁。分布式事务协调器利用上述机制发现死锁，并通知所有结点放弃某一事务，使系统从死锁中解脱出来。,P44b,接下页,2.维护全局等待图的分布式方法：各场地构造全局等待图的子图，与前述的局部等待图不同，这里的子图根据实际情况，增加结点TEX，反映站外情况。成为扩展等待图。子图有环是全局死锁的必要条件。图中TTEX表示事务T准备访问另一结点上由某事务占有的某数据项。TEXT表示其它站点的某事务准备访问本站由事务T占有的某数据项。当子图有环，且环中不含EX，则表明本地处于死锁之中；当子图有环，但环中含EX，则还不能决定结点是否已经陷入死锁。需要启动某种算法作进一步判断。,T1,T2,T3,T5,T1,T2,T3,T5,T2,T3,T4,ex,ex,T2,T3,T4,A,B,C,结点2局部等待图,结点2扩展等待图,结点1局部等待图,结点1扩展等待图,P44c,接下页,下边是检测死锁的一种嵌套算法：结点1发现有环(带ex)后，即将此信息告知ex相关的结点2，继续判断。结点2收到此信息即修改其等待图。若结点2的新图有环且不含ex，表示死锁已经发生；若结点2的新图有环且含有ex，则结点2必须发信息给ex相关的结点3，继续判断。如此递推下去，经有限次传递检测，必可得出结论。若系统陷入死锁，则必出现某个不含ex的环，算法停止。若系统并未陷入死锁，则到了某步，图无环，算法停止。,P44d,