分布式进程管理讲稿.ppt

《分布式进程管理讲稿.ppt》由会员分享，可在线阅读，更多相关《分布式进程管理讲稿.ppt（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、分布式进程管理分布式进程管理1第一页，讲稿共七十页哦10.1 进程迁移进程迁移 进程迁移就是将一个进程的状态，从一台机器(源机)转移到另一台机器(目标机)上，从而使该进程能在目标机上执行。这个概念主要来自于对大量互连系统间负载平衡方法的研究，但其应用已超出了这个领域。2第二页，讲稿共七十页哦10.1.1 进程迁移的动机进程迁移的动机进程迁移在分布式操作系统中很重要，主要有以下几个原因：负载共享。通过将进程从负载较重的节点迁移到负载较轻的节点，使系统负载达到平衡，从而提高整体执行效率。减少通信开销。可以将相互间紧密作用的进程迁移到同一节点，以减少它们相互作用期间的通信耗费。可获得性。运行时间较长

2、的进程在出现错误时可能需要迁移。那么，一个想继续的进程既可以迁移到另外的系统，也可以推迟运行，待错误恢复后在当前系统中重新开始。利用特定资源。3第三页，讲稿共七十页哦10.1.2 进程迁移机制进程迁移机制在设计一个进程迁移机制时要考虑许多问题，其中包括：由谁来激发迁移？进程的哪一部分被迁移?如何进行迁移？如何处理未完成的消息和信号？4第四页，讲稿共七十页哦10.1.2 进程迁移机制进程迁移机制1.迁移激发由谁激发迁移取决于迁移机制的目的。若其目的在于负载平衡，那么，通常由操作系统中掌管系统负载的组件决定什么时候进行迁移；若其目的在于获得特定资源，那么，可由需要资源的进程自行决定何时进行迁移，这

3、种迁移也称为自迁移（Self-migration）。对前一种情况，整个迁移作用以及多系统的存在，对进程都可以是透明的；对后一种情况，进程必须了解分布式系统的分布情况。5第五页，讲稿共七十页哦10.1.2 进程迁移机制进程迁移机制2.迁移什么 当迁移一个进程时，必须在源系统上破坏该进程，并在目标系统上建立它。这才是进程的移动，而不是复制进程。因此，进程映像，至少包括进程控制块，必须移动。另外，这个进程与其他进程间的任何链接也必须更新。6第六页，讲稿共七十页哦10.1.2 进程迁移机制进程迁移机制进程迁移举例：内核P1P2P3P4P5abcdfe3ab45b1c2机器S内核P1P2P3d1机器Dc

4、2a2内核P1P2P4P5abcdfe3ab45b1c2机器S内核P1P2P3P4d1机器Dc2a2(a)(b)7第七页，讲稿共七十页哦10.1.2 进程迁移机制进程迁移机制从执行的角度看,进程控制块移动的困难之处在于进程地址空间的传送和进程打开文件的传送。考虑第一个问题进程地址空间的传送，假设用虚拟存储策略(分段或分页)，有两种方法：迁移时传送整个地址空间。仅传送那些在主存中的地址空间部分，在需要时再传送虚拟地址空间中的段。8第八页，讲稿共七十页哦10.1.2 进程迁移机制进程迁移机制3.消息和信号处理对于那些未完成的消息和信号，可通过一种机制进行处理：在迁移进行时，暂时存储那些完成的消息和

5、信号，然后将它们直接送到新的目的地，有必要在迁移出发的位置将正在发出的信息维持一段时间，以确保所有的未完成消息和信号都被传送到目的地。9第九页，讲稿共七十页哦10.1.3.一种迁移方案一种迁移方案 下面讨论在IBM的AIX操作系统上的一种迁移机制，它是自我迁移的典型代表。AIX操作系统是一种分布式的UNIX操作系统，在LOCUS操作系统上可得到类似的机制。实际上，AIX系统是对LOCUS的改进。10第十页，讲稿共七十页哦10.1.3.一种迁移方案一种迁移方案迁移按以下事件序列进行：当进程决定迁移自身时，它选择一个目标机，发送一个远程消息，该消息带有进程的部分映像及打开文件信息。在接收端，内核服

6、务进程生成一个后代，将这个信息交给它。这个新进程收集完成其操作所需的数据、环境、自变量及栈信息。如果程序文本是不纯的，那么它是被拷贝过来的；如果是纯的，那么它就是全局文件系统所要求的页面。迁移完成时通知源进程，源进程就发送一个最后完成消息给新进程，然后破坏自己。11第十一页，讲稿共七十页哦10.1.4 进程迁移的协商进程迁移的协商 进程迁移涉及到进程迁移的决定，在某些情况下，由单个实体作决定。但是，有些系统允许指定的目标系统参与作决定，主要是为了保持对用户的响应时间。Charlotte采用的是迁移协商（Negotiation of Migration）机制，是由若干个Starter进程负责迁移

7、策略(什么时候将哪个进程迁移到什么地方)，及作业调度和内存分配。因此，Starter可以在这3方面进行协调，每个Starter进程可以控制一簇机器，Starter从它控制的每台机器的内核获取当时的详细负载统计信息。12第十二页，讲稿共七十页哦10.1.4 进程迁移的协商进程迁移的协商必须由两个Starter进程联合来决定迁移，按以下步骤进行：由控制源系统S的Starter决定将进程P迁移到特定的目标系统D，它发送一个消息给D的Starter,要求传送。如果D的Starter准备接受进程P，就回复一个肯定的确认。S的Starter通过服务请求的方式将这个决定传给S的内核，或者将消息传给S机上的K

8、ernJob(KJ)进程，将来自远程进程的消息转换成服务请求。S的内核将进程P传给D。如果D资源不足，它可以拒绝接受，否则，D的内核就把来自S的信息传给它的控制Starter。Starer通过一个迁入（MigrateIn）请求与D协商决定迁移策略。D保留必要的资源以避免死锁和流控问题，然后给S返回一个接收信息。13第十三页，讲稿共七十页哦10.1.4 进程迁移的协商进程迁移的协商进程迁移的协商：S tarterAK J0PK J1SBK J2PK J3DK J4 迁 移 进 P 迁 移 出 P 提 供 PS tarter 是 的，迁 移 到 机 器 3 需 要 P 吗？提 供 P 接 收14第

9、十四页，讲稿共七十页哦10.1.4 进程迁移的协商进程迁移的协商Charlotte进程迁移功能有三个重要的特征：它把决策机制从嵌入内核的迁移机制中分离出来。迁移对迁移进程和与其相连的进程是透明的。迁移进程可以在任何时候被抢先，被中断的进程可以移到另一个节点中。15第十五页，讲稿共七十页哦10.1.5 进程驱逐进程驱逐 协商进程允许一个系统将迁移到其上的进程驱逐出去。Sprite提供了这种驱逐能力。在Sprite中，每个进程在其生存期内都好像仅在一个主机上运行。这台主机是该进程的“家节点”(Home Node)，如果某进程被迁移，它就成为目标机上的“外来进程”(Foreign Process)。

10、目标机任何时候都可驱逐外来进程，于是外来进程有可能被迫迁移回其“家节点”。16第十六页，讲稿共七十页哦10.1.5 进程驱逐进程驱逐Sprite的驱逐机制包含如下部分：每个节点都有一个根据当前的负载来决定什么时候接受新的外来进程的监管进程。如果一个进程被驱逐，它就迁移回其家节点，在其他节点可以使用时该进程又可进行迁移。尽管驱逐所有进程需要一段时间，但被标记驱逐的所有进程可以被立即挂起。将被驱逐进程的整个地址空间传送回家节点，通过在以前的主机恢复迁移进程的内存映像，可以减少迁移进程的时间。17第十七页，讲稿共七十页哦10.1.6 抢占及非抢占进程的迁移抢占及非抢占进程的迁移 抢占进程的迁移，包括

11、传送一个部分运行的进程，或者是已生成但还未运行的进程。非抢占进程的迁移在负载平衡中很有用。其优点是可以避免频繁的进程迁移，其不足在于对负载分配的突变反应不灵敏。迁移非抢占进程的方法较简单，仅传送那些尚未运行的进程，因此，不要求传送进程的状态。这两种迁移，都必须将进程运行的环境信息传给远程节点，这包括用户当前的工作目录和进程继承的权限。18第十八页，讲稿共七十页哦10.2 分布式全局状态分布式全局状态10.2.1 全局状态及分布式快照 在紧耦合系统中存在的所有同步问题，如互斥、死锁、饥饿，在分布式系统中同样存在。由于系统没有全局状态，故这方面的设计策略更复杂。由于分布式系统结构中的时间滞后不可避

12、免，因而其与同步相关问题的解决更加复杂，因此，用进程/事件图来解释这个问题。19第十九页，讲稿共七十页哦10.2.1 全局状态及分布式快照全局状态及分布式快照确定全局状态的例子：m sg=传 送$100”到 支 行 B m sg=传 送$100”到 支 行 B 3:00SA=$100.00SB =$0.00支 行 A支 行 B(a)3:00SA=$0.00支 行 A支 行 B(b)2:59SB =$0.003:013:00SA=$100.00支 行 A支 行 B(c)2:59SB =$100.003:012:59ttt20第二十页，讲稿共七十页哦10.2.1 全局状态及分布式快照全局状态及分布

13、式快照不一致和一致的全局状态：SBSA进程 A进程 B(a)M2M1M3M4SCSBSA进程 A进程 B(b)M2M1M3M4SC进程 C进程 Ctt21第二十一页，讲稿共七十页哦10.2.1 全局状态及分布式快照全局状态及分布式快照为了寻求一个合适的解决方案，首先对下面术语给出定义：通道。如果两个进程交换信息，那么它们之间就有一个通道。为了方便，通道只是单向的。状态。一个进程的状态就是该进程所带通道发送和接收的消息序列。快照。一张快照记录一个进程的状态，每张快照包括上次快照后所有通道上发送和接收的所有消息的记录。全局状态。所有进程的联合状态。分布式快照。快照集，一个进程一个。22第二十二页，

14、讲稿共七十页哦10.2.1 全局状态及分布式快照全局状态及分布式快照 面对的问题是，由于消息传送的时间滞后，不能决定真正的全局状态。我们希望通过从所有进程收集快照来决定全局状态。我们希望分布式快照记录一个一致的全局状态：如果每个接收消息进程状态中的接收记录都与该消息在发送消息进程状态中的发送记录相对应，那么全局状态是一致的。如果一个进程记录了一条消息的接收，但相应的发送消息进程没有记录消息已发送的信息，就会发生不一致的全局状态。23第二十三页，讲稿共七十页哦10.2.2 分布式快照算法分布式快照算法 在记录一致的全局状态的分布式快照算法中，假设消息按序发送并且没有丢失，算法用到一个专门的控制消

15、息，叫做marker。一些进程在发送更多消息前，记录其状态并通过所有输出的通道发送给marker，从而激发该算法。每个进程P都按如下步骤进行。第一次收到marker(来自进程q)，接收进程p执行如下步骤：记录其当前局部状态Sp。将从q到p的输入通道记录为空状态。将marker沿所有输出通道传送给其所有邻居。24第二十四页，讲稿共七十页哦10.2.2 分布式快照算法分布式快照算法 在记录了状态后，当p从另外的输入通道(来自进程r)收到一个marker时，接受进程p就执行下面的步骤：将从r到p的状态记为：从p记录其状态Sp到它接收来自r的marker这段时间内，p从r收到的消息序列。一旦所有输入通

16、道都收到marker，算法在这个进程上中止。25第二十五页，讲稿共七十页哦10.2.2 分布式快照算法分布式快照算法现对算法讨论如下：通过发送一个marker，使任何进程都可开始该算法。实际上，几个节点各自独立地记录状态，算法仍有效。若每个消息(包括marker)都在有限时间内传送，则算法将在有限时间内终止。这是一个分布式算法，每个进程都记录自己的状态和所有输入通道的状态。一旦所有状态都记录了(算法在所有进程都中止了)，算法就得到一致的全局状态。算法不受影响，也不被进程采用的任何其他的分布式算法影响。26第二十六页，讲稿共七十页哦10.2.2 分布式快照算法分布式快照算法进程和通道图：1243

17、27第二十七页，讲稿共七十页哦10.2.2 分布式快照算法分布式快照算法快照举例：进程1 进程3 输出通道 输出通道 2发送1，2，3，4，5，6 2发送1，2，3，4，5，6，7，8 3发送1，2，3，4，5，6 进入通道 进入通道 1接收1，2，3存储4，5，6进程2 2接收1，2，3存储4 输出通道 4接收1，2，3 3发送1，2，3，4 进程4 4发送1，2，3，4 输出通道 进入通道 3发送1，2，3 1接收1，2，3，4存储5，6 进入通道 2接收1，2，3，4，5，6，7，8 2接收1，2存储3，428第二十八页，讲稿共七十页哦10.3 分布式进程管理分布式进程管理互斥互斥 在第

18、3章和第4章中曾提到的并发进程执行的相关问题，其中两个主要问题就是互斥和死锁。这两章主要讨论在单机系统中只有一个主存而有多个进程的环境下解决这个问题的方法。为解决分布式操作系统和没有共享主存的多处理器中发生的相关问题，就需要新的解决方法。互斥和死锁算法必须依靠消息的交换，而不能依靠对主存的访问。本小节和10.4节分别讨论分布式操作系统中的互斥和死锁问题。29第二十九页，讲稿共七十页哦10.3.1 分布式互斥问题分布式互斥问题 当两个或多个进程竞争系统资源时，有必要利用互斥机制，假设两个或更多的进程都要使用单一非共享资源，如打印机。把这样的资源看做是临界资源，程序中使用这类资源的部分看做是程序的

19、临界段。在某一时刻仅允许一个程序位于其临界段。30第三十页，讲稿共七十页哦10.3.1 分布式互斥问题分布式互斥问题进程的并发运行要求能够定义临界段和实行互斥，要支持互斥必须满足以下要求：在某一时刻，仅允许若干拥有同一资源或共享临界段的进程中的一个进入临界段。在非临界段运行结束的进程，不能影响其他进程。访问临界段的进程，不能无限期地被延迟，即无死锁和饥饿发生。没有进程在临界段时，应允许任何要求进入临界段的进程进入。对进程执行速度或进程数无任何假定。一个进程在其临界段中只逗留有限时间。31第三十一页，讲稿共七十页哦10.3.1 分布式互斥问题分布式互斥问题分布式进程管理中互斥问题模型:系 统 i

20、P11,P12,P1kR P1R P11,RP12,R P1m系 统 jPj1,Pj2,PjkR P3Rj1,Rj2,Rjm系 统 nPN1,PN2,PNkR P2RN1,RN2,RNm R Pj为 系 统 j 中 资 源 控 制 进 程 Pji为 系 统 j 中 用 户 进 程 i Rji为 系 统 j 中 资 源 i32第三十二页，讲稿共七十页哦10.3.1 分布式互斥问题分布式互斥问题互斥算法可以是集中式的，也可以是分布式的。在集中式算法中，将有一个节点作为控制节点，控制对所有共享对象的访问。当任一进程要求访问临界段时，它就发送一个Request消息给本地资源控制进程，资源控制进程就发送

21、一个Request消息给控制节点。当其共享对象可用时，控制节点就返回一个Reply(允许)消息；当进程使用完资源后，就发送一个Release消息给控制节点。这个集中式算法有两个特点：只有控制节点才能分配资源。所有必要信息都集中在控制节点，包括所有资源的性质和位置，以及每个资源的分配状态。33第三十三页，讲稿共七十页哦10.3.1 分布式互斥问题分布式互斥问题分布式算法应有如下特性：所有节点差不多有同等的信息量。每个节点只有整个系统的部分信息，必须根据这些信息作决定。所有节点共同负责作最后决定。所有节点对最后决定所起的作用相同。一般，一个节点失效，不会引起整个系统的失效。没有调整事件计时的统一的

22、系统共同时钟。34第三十四页，讲稿共七十页哦10.3.1 分布式互斥问题分布式互斥问题需要对第点和第点作进一步说明：对第点，一些分布式算法允许节点之间相互交流信息。即使这样，在某一时刻，仍有一些信息可能被滞留在传递中，未能及时到达其他节点。因此，由于消息传递的滞后性，当前节点的信息可能不是最新的。对第点，由于系统通信的延迟，要求所有系统有一个统一的时钟是不可能的；使所有本地时钟都与中央时钟完全同步也很困难，经过一段时间后，有些本地时钟可能偏移。35第三十五页，讲稿共七十页哦10.3.2 分布式系统的事件定序分布式系统的事件定序时时戳方法戳方法 大多数互斥和死锁的分布式算法的基本操作是对事件进行

23、定序（Event Ordering）。没有统一时钟或没有同步的局部时钟是主要问题。为了解决这个问题，用“时戳”对分布式系统中的事件定序，而不需要物理时钟。36第三十六页，讲稿共七十页哦10.3.2 分布式系统的事件定序分布式系统的事件定序时戳方法时戳方法首先对事件下一定义。讨论一个系统的行为、一个事件，如一个进程进入或离开临界段。时戳方法就是对由消息传送的事件定序。网络中的每个系统i都有一个本地计数器Ci，它相当于一个时钟。每次系统传送一条消息就将其计数器加1，消息按(m，Ti，i)形式传送，其中，m为消息的内容；Ti为消息的时戳；i为该站点的编号。当该消息达到时，接收系统j将它的时钟置为Cj

24、=1+maxCj，Ti在每个站点，事件的顺序按下面的规则决定。对i处的消息x和j处消息y，如果满足下面一个条件，就称x先于y：TiTj Ti=Tj并且ij37第三十七页，讲稿共七十页哦10.3.2 分布式系统的事件定序分布式系统的事件定序时时戳方法戳方法时戳算法运行示例1：时戳算法运行示例2：tP10(a,1,1)1456P2012 3(x,3,2)6P30264(j,5,3)7(b,5,1)5tP10(a,1,1)1P202P30P4021(q,1,4)322338第三十八页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法1.Lamport算法最早提出的分布式互斥方法是Lampor

25、t算法，它基于分布式队列的概念，该算法基于以下假设：分布式系统由N个站点组成，每个站点有惟一编号，从1到N。每个站点都仅有一个进程负责进行互斥访问资源，也负责处理那些同时到达的请求。按发送的顺序接收从一个进程到另一个进程的消息。每条消息都在有限时间内正确地送到目的地。网络是全互连的，进程间可以两两直接发送信息。假设和可通过一个可靠传输协议来实现。为了简便，假设每个站点仅控制一个资源。39第三十九页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法 算法所用的数据结构可以是一个队列，也可以是一个数组，若是数组，则每个站点占其中一个数据项：项qj表示来自Pj的消息。数组初始化为qj=(Re

26、lease，0，j)j=1，N 本算法中用到以下3种消息。(Request，Ti，i)：Pi请求访问资源。(Reply，Tj，j)：Pj允许对它所控制的资源进行访问。(Release，Tk，k)：Pk释放以前分配给它的一个资源。40第四十页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法Lamport算法如下：当Pi请求访问资源时，它发送一个请求(Request，Ti，i)，时戳是当前本地时钟值。它将此消息放入自身数组的qi中，然后，将这个消息传给所有其他进程。Pj收到请求(Request，Ti，i)后，将这个消息放入自身数组的qi中，并传送(Reply，Tj，j)给所有其他进程（并

27、且将这个消息也放置在自身数组中）。这一步就是为了满足上述规则，以确保在作决定时没有更早的消息在传送。注意：若Pj 在收到Request消息前也已提出过对同一资源的访问请求，那么其Reply消息上的时戳就应比（Ti，i）小。41第四十一页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法 Pi满足下面两个条件就可访问一个资源(进入其临界段)：数组q中Pi的请求消息是数组中最早的请求消息。由于消息在所有站点的顺序一致，这个规则允许在任一时刻仅有一个进程访问资源。Pi 确定已收到其它所有进程的其时戳都比（Ti，i）小的响应消息。这个规则确保Pi已知道所有在它当前请求前面的请求。Pi通过发送(

28、Release,Ti,i)消息来释放所占用的资源。该消息也置入其自身的数组项中，并传递给所有其他进程。当Pi接收到(Release,Tj,j)消息，它用该消息替换q(j)的当前内容。当Pi接收到(Reply,Tj,j)消息，它用该消息替换q(j)的当前内容。很容易证明此算法满足互斥要求,且公平，不死锁，不饥饿。42第四十二页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法2.Ricart算法 Ricart对Lamport算法进行了一些简化，希望将Release消息删去以优化原始算法。Ricart算法的假设与Lamport算法的假设基本点相同。同前，每个站点都有一个进程负责控制资源的分

29、配。该进程有一个数组q并遵循以下规则。当Pi请求访问资源时，它发出一个请求(Request，Ti，i)。时戳为当前本地时钟之值。它将这条消息放入自身数组qi中，然后，将消息发送给所有其他进程。43第四十三页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法 当Pj收到请求(Request，Ti，i)后，按如下规则处理：如果Pj正处于临界段中，就延迟发送Reply消息(见规则4)；如果Pj并不等待进入临界段，就发送(Reply，Tj，j)给所有其他进程；如果Pj等待进入其临界段，并且到来的消息在Pj的Request后，则将到来的消息放入其数组的qi中，并延迟发送Reply消息；如果Pj等

30、待进入其临界段，但是到来的消息在Pj的Request前，就将到来的消息放入其数组的qi中，并发送(Reply，Tj，j)给Pi。如果Pi从所有其他进程都收到了Reply消息，它就可以访问资源。当Pi离开临界段时，它给每个挂起的Request发送一个Reply消息，从而释放资源。44第四十四页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法 Ricart算法的状态图：请求互斥激活其他进程等待临界段计算互斥请求发送一个 Request 给其他所有进程收到所有Reply离开临界段45第四十五页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法 简单小结：当一个进程想要进入临界段时，

31、它就给所有其他进程发送一条带时戳的Request消息，当它从所有其他进程收到Reply后，它就可以进入临界段。当一个进程收到另一个进程的Request时，它必须酌情发送一个Reply：如果该进程不想进入临界段，它就马上发送Reply。若它想要进入临界段，它就将自己的Request的时戳与收到的Request的时戳进行比较，如果后者较迟，它就延迟发送Reply；否则马上发送Reply。这里，Reply消息实际上起到了Lamport算法中Release消息所起到的释放资源的作用。46第四十六页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法本算法主要存在以下的问题：所有进程都必需知道系统

32、中每个进程的名字。当有新进程加入时，会造成大量开销。若一进程意外失效，则会导致发出Request的进程收不到全部响应。因此，系统必需提供某种机制，当某进程失效时，将其名字通知其它进程。47第四十七页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法3.令牌方法下面讨论一种有效的令牌方法。这个算法需要2个数据结构：令牌从一进程传到另一个进程，它实际上是一个数组token，其第k个元素记录上一次令牌传到进程Pk的时戳；每个进程也有一个数组Request，其第j个元素记录上次从Pj收到Request的时戳。48第四十八页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法算法过程如下：

33、最初，将令牌随机分配给一个进程，即将该进程的token present置为true，表示进程此时拥有令牌。当一个进程要进入临界段时，如果它拥有令牌就可进入；否则，它向所有其他进程广播带时戳的Request请求消息，等待直到它得到令牌。当进程Pi离开临界段时，它必须将令牌传给其他进程，它按i+1，i+2，1，2，i1的顺序搜索Request数组，找到第一个满足Pj最新要求的、时戳比其token中记录的Pj上一次拥有令牌的时间值要大的进程Pj，也就是满足：Requestjtokenj的Pj。这一规则就是为了确保令牌不会被重复发放给已经使用过令牌获得了资源，而且没有更新需求产生的进程。49第四十九页

34、，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法令牌传递算法令牌传递算法(进程进程Pi)：if not token-present then begin clock:=clock+1;Prelude broadcast(request,clock,i);wait(access,token);token-present:=True end;endif;token-held:=True;token(i):=clock;Postludetoken-held:=false;for j:=i+1 to n,1 to i1 do if(request(j)token(j)token-presen

35、t then begin token-present:=False;send(j,access,token)end endif;(a)接左图：接左图：When received(request,t,j)do request(j):=max(request(j),t);if token-presentnot token-held then endifenddo;(b)记号说明：send(j,access,token)将access消息和令牌token传给进程j broadcast(request,clock,i)将进程i的请求消息和时戳clock传给所有其他进程 received(request

36、,t,j)从进程j收到请求消息及时戳t50第五十页，讲稿共七十页哦10.3.3 分布式互斥算法分布式互斥算法该算法满足下面两种情况之一：如果请求进程没有令牌，则需要N条消息(N1条广播请求，1条传送令牌)。如果进程已拥有令牌就不需要消息。51第五十一页，讲稿共七十页哦10.4 分布式死锁分布式死锁 在第4章中，将死锁定义为一个进程集的永久阻塞，这些进程或者竞争系统资源或者相互通信。这个定义对分布式系统和单个系统同样有效。与互斥一样，死锁在分布式系统中会引起比共享内存系统更为复杂的问题。由于没有一个站点能精确地知道整个系统的当前状态，并且两个进程的消息可能遇到不可预测的延迟，因此，死锁处理在分布

37、式系统中相当复杂。有两种类型的死锁：资源分配引起的死锁和消息通信引起的死锁。52第五十二页，讲稿共七十页哦10.4.1 资源分配中的死锁资源分配中的死锁 只有满足以下所有条件时，才会出现资源分配的死锁：互斥。占有并等待。非抢占。循环等待。分布式死锁处理遇到的困难在于“死锁幻象”(Phantom Deadlock)。53第五十三页，讲稿共七十页哦10.4.1 资源分配中的死锁资源分配中的死锁死锁幻象：P1P2P3释放 RaP1P2P3请求 RbP1P2P3P1P2P3请求 RbP1P2P3释放 Ra54第五十四页，讲稿共七十页哦10.4.2 死锁预防死锁预防 第4章讨论的死锁预防方法中有两种可以

38、用在分布式环境中：对网络中所有可共享资源进行线性排序。其缺点在于，由于资源并不是按它们使用的顺序请求。因此，资源可能比需要占有的时间要长。一个进程一次请求它所需要的全部资源，通过阻塞该进程直到所有请求同时被满足为止，这可破坏占有并等待的条件。55第五十五页，讲稿共七十页哦10.4.2 死锁预防死锁预防 这两种方法都需要进程事先就知道它所需要的资源，这并不总是可能的。下面讨论两个不需要这种预见知识的算法，由于我们是围绕数据库讨论，所以只对事务而不是对进程来讨论。这里介绍的方法利用了时戳。每个事务在生存期内都带有其产生的时戳，从而使事务有了严格的顺序。如果资源R已在事务T1中用过而被另一个事务T2

39、请求，就可以通过比较两者的时戳来解决冲突，这个比较可避免循环等待条件的形成。对这个基本方法作两种变化，就得到了wait-die方法和wound-wait方法。56第五十六页，讲稿共七十页哦10.4.2 死锁预防死锁预防(a)wait-die方法(b)wound-wait方法57第五十七页，讲稿共七十页哦10.4.2 死锁预防死锁预防wait-die 算法演示：T1 T1 T2 T2 T1 Ra Ra Rb Ra Rb Ra Rb 58第五十八页，讲稿共七十页哦10.4.3 死锁避免死锁避免死锁避免就是动态确定如果满足一个资源分配请求，是否会引起死锁。由于以下原因分布式死锁避免并不实际可行：每个

40、节点必须记录系统的全局状态，这就需要大量的存储和通信耗费。检测安全全局状态的进程必须是互斥的，否则，两个节点各自考虑一个不同进程的资源请求，可能得出满足请求是安全的结论，但实际上同时满足这两个请求会发生死锁。对有大量进程和资源的分布式系统而言，检查安全状态，需要相当大的开销。59第五十九页，讲稿共七十页哦10.4.4 死锁检测死锁检测1.分布式死锁检测策略 分布式死锁检测的困难在于，每个站点仅知道自己的资源，而死锁可能涉及分布式资源。根据系统控制是集中的、分层的还是分布式的，相应有几种策略：集中式策略，由一个站点来负责死锁检测。分布式，需要所有进程合作来检测死锁。60第六十页，讲稿共七十页哦1

41、0.4.4 死锁检测死锁检测2.分布式死锁检测算法 现在讨论一种分布式死锁检测算法。该算法用于一个分布式数据库系统，其中每个站点只有部分数据库信息，并且事务可在每处初始化。一个站点中的所有数据对象都有两个参数：惟一标号Di和变量Lock-by(Di)，后面这个变量在数据对象没有任何事务加锁时为空；否则，其值就是加锁事务的标号。61第六十一页，讲稿共七十页哦10.4.4 死锁检测死锁检测一个站点中的所有事务j都有4个参数：惟一标号Tj。变量Held-by(Tj)，如果事务Tj在运行或者处于就绪态，就置为空；否则，其值就等于另外某个事务的标号，这个事务占有了事务Tj所请求的数据对象。变量Wait-

42、by(Tj)，如果事务Tj不等待其他事务，就置为空；否则，其值就等于处于阻塞事务序列头的事务标号。队列Request Q(Tj)，它包括对Tj占有的数据对象的所有尚未满足的请求。队列的每个元素都形如(Tk，Dk)，其中Dk是Tj占有的数据对象，Tk是请求Dk的事务。62第六十二页，讲稿共七十页哦10.4.4 死锁检测死锁检测事务Tj收到更新的消息begin if Wait-for(Tj)Wait-for(Ti)then Wait-for(Tj):=Wait-for(Ti);if Wait-for(Tj)Request-Q(Tj)=nil then update(Wait-for(Ti),Req

43、uest-Q(Tj)else begin DECLARE DEADLOCK;initiate deadlock resolution as follows Tj被选择作为夭折的事务 Tj释放它所占用的全部数据对象 send-clear(Tj,Held-by(Tj);allocate each data object Di held-by Tj to the first requester Tk in Request-Q(Tj);for every transaction Tn in Request-Q(Tj)requesting data object Di held-by Tj do Enq

44、ueue(Tn,Request-Q(Tk)；endend.事务Tk收到clear(Tj,Tk)消息begin purge the tuple having Tj as the requesting transaction from Request-Q(Tk)end.分布式死锁检测算法：数据对象Dj收到lock-request(Ti)begin if Locked-by(Dj)=nil then send granted else begin send not granted to Ti;send Locked-by(Dj)to Ti endend事务Ti对数据对象Dj发出加锁请求begin s

45、end lock-request(Ti)to Dj；wait for granted/not granted;if granted then begin Locked-by(Dj):=Ti;Held-by(Ti):=;end else假定Dj已被事务Tj使用 begin Held-by(Ti):=Tj;Enqueue(Ti,Request-Q(Tj);if Wait-for(Tj)=nil then Wait-for(Ti):=Tj else Wait-for(Ti):=Wait-for(Tj);update(Wait-for(Ti),Request-Q(Ti)endend.63第六十三页，讲

46、稿共七十页哦10.4.4 死锁检测死锁检测 分布式死锁检测算法举例：T0向T3提出请求前的系统状态 T0向T3提出请求后的系统状态 64第六十四页，讲稿共七十页哦10.4.5 消息通信中的死锁消息通信中的死锁 1.互相等待 当一组进程中的每一个成员都在等待组内另一个成员的消息，又没有任何消息在传送时，就会发生消息通信死锁。为了更详细地解释这种情况，需定义一个进程的依赖集(DS)：进程Pi 在因等待某个进程发出的消息而停止的同时，也期待着其它一些进程所发出的消息，所有这些进程的集合就是DS(Pi)。如果任何期望消息到达，Pi就可以运行。65第六十五页，讲稿共七十页哦10.4.5 消息通信中的死锁

47、消息通信中的死锁有了前面的定义，进程集S的死锁可定义如下：S中所有进程都停止，正等待消息。S中所有的进程的独立集都包含在S中。S中的成员间没有传送消息。S中的所有进程都被死锁。66第六十六页，讲稿共七十页哦10.4.5 消息通信中的死锁消息通信中的死锁 消息通信中的死锁：不死锁 死锁 67第六十七页，讲稿共七十页哦10.4.5 消息通信中的死锁消息通信中的死锁2.消息缓冲分配不合理 对正在传送消息的存储缓冲的分配不合理也会引起消息传送系统的死锁。这种死锁在包交换网中居多：数据网中最简单的死锁形式是直接的存储转发死锁，如果一个包交换节点用公共缓冲池来缓冲包，就可能产生死锁。直接的存储转发死锁是可避免的，只要不将全部缓冲区都分配给一条链就可以了。可以将缓冲区分成大小固定的块，每块对应一条链，就可以预防死锁。另一种是间接的存储转发死锁。68第六十八页，讲稿共七十页哦10.4.5 消息通信中的死锁消息通信中的死锁 直接的存储转发死锁 存储转发死锁举例 缓冲池满AB缓冲池满给B的 包E给A的 包DC给E的 包给D的 包B给C的 包A直接的存储转发死锁 间接的存储转发死锁 69第六十九页，讲稿共七十页哦The end.Thanks!70第七十页，讲稿共七十页哦