1、1第四章第四章 分布式资源管理分布式资源管理策略策略2实现资源共享的三种方法。实现资源共享的三种方法。4.1.1 数据迁移数据迁移l数据迁移的两种方法：数据迁移的两种方法： 第一种方法是将整个文件转移给场点第一种方法是将整个文件转移给场点A，尔后，所有对该，尔后，所有对该文件的存取都是局部的了。当用户不再需要访问该文件文件的存取都是局部的了。当用户不再需要访问该文件时，它的副本（如果它被修改过）被回送给场点时，它的副本（如果它被修改过）被回送给场点B。对一。对一个文件的任何微小的修改，都得将这整个文件传送回去个文件的任何微小的修改，都得将这整个文件传送回去3 另一种方法是只将该文件中实际需要的
2、部分另一种方法是只将该文件中实际需要的部分 转移给转移给A。一旦用户不再使用该文件，该文件的任何已作过修改时部一旦用户不再使用该文件，该文件的任何已作过修改时部分必须回送给场点分必须回送给场点B。 显然，如果只访问一个较大文件的一小部分，显然，如果只访问一个较大文件的一小部分，那么采用后一种方法较好；否则采用第一种方法较那么采用后一种方法较好；否则采用第一种方法较合适。不过，仅仅从一个场点向另一个场点转移数合适。不过，仅仅从一个场点向另一个场点转移数据是不够的，系统还得执行各种数据转换（如果两据是不够的，系统还得执行各种数据转换（如果两个场点不是直接兼容的话）。例如，如果它们使用个场点不是直接
3、兼容的话）。例如，如果它们使用了不同的字符代码表示。了不同的字符代码表示。 4 4.1.2 计算迁移计算迁移 在某些情形中，转移计算比转移数据更有效。例如，在某些情形中，转移计算比转移数据更有效。例如，考虑这样一个作业，它需要存取位于不同场点上的若干较考虑这样一个作业，它需要存取位于不同场点上的若干较大的文件，以获得它们的概况。一种比较有效的办法是在大的文件，以获得它们的概况。一种比较有效的办法是在它们驻留的场点上各自存取这些文件，然后分别回送所需它们驻留的场点上各自存取这些文件，然后分别回送所需要的值给初启该计算的那个场点要的值给初启该计算的那个场点 。 l计算的实现方式：计算的实现方式：可
4、用一个远程过程调用来初启。进程可用一个远程过程调用来初启。进程p引用场点引用场点A上预定义的上预定义的一个过程，该过程执行完后给一个过程，该过程执行完后给p回送回送 所需要的结果。所需要的结果。5 通过消息传递的方式通过消息传递的方式 。进程。进程p可以发送一条消息给场点可以发送一条消息给场点A，操作系统在场点操作系统在场点A创建一个新进程创建一个新进程q，q的功能是执行由的功能是执行由该消息所指定的任务，当该消息所指定的任务，当q完成其执行后，它又通过消息完成其执行后，它又通过消息系统给系统给p回送所需要的结果。回送所需要的结果。 这两种方案都可用来存取驻留在各个场点上的若干这两种方案都可用
5、来存取驻留在各个场点上的若干文件。文件。64.1.3 作业迁移作业迁移 当一个作业提交给系统后，系统可以在一特定的场点当一个作业提交给系统后，系统可以在一特定的场点上执行这整个作业，或在不同的场点上执行它的某一部分上执行这整个作业，或在不同的场点上执行它的某一部分 利用这种方案的主要原因是：利用这种方案的主要原因是： 负载均衡：作业（或子作业）可以分散到系统中以负载均衡：作业（或子作业）可以分散到系统中以 均衡系统的工作负载。均衡系统的工作负载。 计算速度的提高：如果单个作业可以分解成若干子计算速度的提高：如果单个作业可以分解成若干子 作业，这些子作业可以在不同的场点并发地执行，那么，作业，这
6、些子作业可以在不同的场点并发地执行，那么， 整个作业的周转时间将会减少。整个作业的周转时间将会减少。 7 硬件特性：该作业可能有这祥一些特性，即它硬件特性：该作业可能有这祥一些特性，即它比较适合于在某些特殊的处理机上执行。例如，矩阵比较适合于在某些特殊的处理机上执行。例如，矩阵转换就比较适合于在阵列机上执行。转换就比较适合于在阵列机上执行。 软件特性：该作业可能需要特定场点上的软件软件特性：该作业可能需要特定场点上的软件或不能移动的软件，或者移动该作业比较划算。或不能移动的软件，或者移动该作业比较划算。u显示迁移显示迁移u隐式迁移隐式迁移84.2资源管理管理策略资源管理管理策略 分布式系统对于
7、资源管理有两种基本的观点：分布式系统对于资源管理有两种基本的观点：l 单个资源管理单个资源管理单个资源与多个管理机构相互关系的角度进行分析。单个资源与多个管理机构相互关系的角度进行分析。l 多个资源管理多个资源管理多个资源与多个管理机构相互关系的角度进行分析。多个资源与多个管理机构相互关系的角度进行分析。前者是后者的基础，后者是前者的提高。前者是后者的基础，后者是前者的提高。9 单个资源管理，有四种资源管理方式：单个资源管理，有四种资源管理方式：n集中管理方式：集中管理方式：只有一个管理者对该资源的各种活动统一只有一个管理者对该资源的各种活动统一进行管理，其它管理者对该资源均不具有管理职能和责
8、任。进行管理，其它管理者对该资源均不具有管理职能和责任。该方式也称为专制（该方式也称为专制（autocratic）管理方式。）管理方式。n功能分布管理方式：功能分布管理方式：多个管理者按照不同的资源活动分担多个管理者按照不同的资源活动分担管理职能和责任，且每种活动只由一个管理者管理。该方管理职能和责任，且每种活动只由一个管理者管理。该方式也称为分担管理方式或分割（式也称为分担管理方式或分割（partitioned)管理方式。管理方式。10n浮动管理方式：浮动管理方式：多个管理者均可同等地担负管理职能和多个管理者均可同等地担负管理职能和责任，但在一段时间内，只有一个管理者行使职权，责任，但在一段
9、时间内，只有一个管理者行使职权，“任期任期”满后再由另一管理者接替，如此轮流下去。该满后再由另一管理者接替，如此轮流下去。该方式也称轮流（方式也称轮流（successive）管理方式。）管理方式。n分散管理方式：分散管理方式：多个管理者采取协商一致的原则对资源多个管理者采取协商一致的原则对资源活动进行全面管理，其中各个管理者的地位和功能是完活动进行全面管理，其中各个管理者的地位和功能是完全平等的。该方式也称民主全平等的。该方式也称民主(democratic）管理方式。）管理方式。 11从多个资源管理，可分为如下四种管理方式：从多个资源管理，可分为如下四种管理方式：n 集中：集中：每一类资源只属
10、一个管理者管理。它控制该类每一类资源只属一个管理者管理。它控制该类 全部资全部资源。源。n 分管分管（集中分布式）：每一类资源由多个管理者管理，但每（集中分布式）：每一类资源由多个管理者管理，但每一资源只属一个管理者管理。一资源只属一个管理者管理。n 合管合管（完全分布式）：不仅每一类资源存在多个管理者管理，（完全分布式）：不仅每一类资源存在多个管理者管理，而且该类中每个资源属于全部管理者共同管理。而且该类中每个资源属于全部管理者共同管理。n 部分管理部分管理：每一类资源由多个管理者管理，每一资源：每一类资源由多个管理者管理，每一资源 属于若属于若干管理者管理。干管理者管理。 如图如图4.1所
11、示。其中圆圈表示管理者，三角形表示资所示。其中圆圈表示管理者，三角形表示资源。源。1213 分布式管理方式和集中式管理方式的主要区别是对分布式管理方式和集中式管理方式的主要区别是对同类资源是采用多个管理者还是一个管理者。集中分布同类资源是采用多个管理者还是一个管理者。集中分布管理和完全分布管理的主要区别是前者让资源管理者对管理和完全分布管理的主要区别是前者让资源管理者对它管理的资源拥有全部控制权，而后者只允许资源管理它管理的资源拥有全部控制权，而后者只允许资源管理者对它管理的资源拥有部分控制权。从上述两种管理方者对它管理的资源拥有部分控制权。从上述两种管理方式的角度来考虑系统资源的划分。式的角
12、度来考虑系统资源的划分。从实用的角度讲，分从实用的角度讲，分布式系统中的资源管理方式主要有布式系统中的资源管理方式主要有局部集中式局部集中式、分散式分散式和和分级式分级式。 14 4.2.2 局部集中管理局部集中管理 每个资源由一个且仅由一个资源管理者管理，具体每个资源由一个且仅由一个资源管理者管理，具体讲就是，资源按其在各场点上的分布情况分别由其所在讲就是，资源按其在各场点上的分布情况分别由其所在的场点进行局部的集中管理，不存在全系统范围的集中的场点进行局部的集中管理，不存在全系统范围的集中管理者。管理者。 这种管理方式主要适用于这种管理方式主要适用于和处理机紧密相连的资源，和处理机紧密相连
13、的资源，如内存、键盘、显示器，如内存、键盘、显示器，当与它们紧密相连的处理机失当与它们紧密相连的处理机失效时，这些资源也就随之失效了。效时，这些资源也就随之失效了。154.2.2 分散式管理分散式管理一个资源由多个场点上的管理者在协商一致的一个资源由多个场点上的管理者在协商一致的原则下共同管理。原则下共同管理。 这类则这类则和处理机的关系不甚紧密和处理机的关系不甚紧密，例如多副本，例如多副本文件，网络打印机等。文件，网络打印机等。164.2.3 分级式管理分级式管理 分级式管理的基本原理是：分级式管理的基本原理是： 针对实际的分布式系统对其中的各种资源进行分析，然后根针对实际的分布式系统对其中
14、的各种资源进行分析，然后根据其重要性、常用性和隶属关系将资源分为两个级别：第一级是被据其重要性、常用性和隶属关系将资源分为两个级别：第一级是被多个场点经常使用的资源；第二级是仅被本场点使用的资源。多个场点经常使用的资源；第二级是仅被本场点使用的资源。 采用不同的方式管理不同级别的资源。即对第一级资源，由采用不同的方式管理不同级别的资源。即对第一级资源，由于它们被系统中的多个场点经常使用，因此，必须采用分散式管理于它们被系统中的多个场点经常使用，因此，必须采用分散式管理方式，由多个场点在协商一致的原则下共同管理。对第二级资源，方式，由多个场点在协商一致的原则下共同管理。对第二级资源，由于它们属于
15、某个场点，不被其它场点使用，可以采用集中式管理由于它们属于某个场点，不被其它场点使用，可以采用集中式管理方式，由某个场点集中管理。方式，由某个场点集中管理。 174.2.4 一个分散式资源管理算法一个分散式资源管理算法 1.基本说明基本说明 占有资源的进程，必须先释放资源，系统才能把该资源分占有资源的进程，必须先释放资源，系统才能把该资源分配给另一进程；配给另一进程； 多个进程申请同一资源时，必须按其请求的先后次序来分配；多个进程申请同一资源时，必须按其请求的先后次序来分配； 若每个分配到资源的进程都在有限时间内释放所占有的资源，若每个分配到资源的进程都在有限时间内释放所占有的资源，则每个资源
16、申者就可能在有限时间内获得该资源；则每个资源申者就可能在有限时间内获得该资源； 假定系统由假定系统由n个场点组成，每个场点运行一个进程，它们的个场点组成，每个场点运行一个进程，它们的编号依次为编号依次为p1, p2, , pn。每个进程都有一个自己管理的申请队。每个进程都有一个自己管理的申请队列用以存放请求消息。列用以存放请求消息。182.算法描述算法描述 该算法利用时间戳来标明申请资源的先后次序，以此来尽量该算法利用时间戳来标明申请资源的先后次序，以此来尽量消除对共享资源的竞争。消除对共享资源的竞争。 当系统中的任一进程当系统中的任一进程pi，申请资源，申请资源rj时，向系统中的其它时，向系
17、统中的其它每一进程发一每一进程发一Request(Ti, pi, rj)消息，（其中消息，（其中Ti为此时的时间戳）为此时的时间戳）并把它存入自己的请求队列；并把它存入自己的请求队列； 进程进程pk，接收到这一消息后，将其存入自己的请求队列，接收到这一消息后，将其存入自己的请求队列，若若pk当前未请求该资源，则它马上给当前未请求该资源，则它马上给Pi发送一个带有时间戳的认发送一个带有时间戳的认可消息；若可消息；若pk也正在请求使用该资源，且其时间戳也正在请求使用该资源，且其时间戳Tk先于先于Ti，则，则它暂不给它暂不给Pi发送认可消息；发送认可消息； 19 仅当下列条件成立时，仅当下列条件成立
18、时，Pi才可以分配该资源才可以分配该资源; 在其请求队列中，它的在其请求队列中，它的Request(Ti, pi, rj)消消 息中的息中的Ti比所有其它请求消息中的时间戳都要小；比所有其它请求消息中的时间戳都要小； pi已接收到所有其它进程发来的时间戳迟于已接收到所有其它进程发来的时间戳迟于Ti的认可的认可 消息。消息。 在释放资源时，在释放资源时，pi从自己的请求队列中去掉从自己的请求队列中去掉Request(Ti, pi, ri)消息，并向系统中每个正等待请求使用该资源的进程发一消息，并向系统中每个正等待请求使用该资源的进程发一条条Release(Ti, pi, ri)消息和一条带时间戳
19、的认可消息。消息和一条带时间戳的认可消息。 当进程当进程pj收到收到pi发来的发来的Release(Ti, pi, ri)消息后，从其请消息后，从其请求队列中去掉求队列中去掉Request(Ti, pi, ri)消息。消息。201.算法描述算法描述当一资源管理者打算向其它场点的资源管理者申请资源时，先当一资源管理者打算向其它场点的资源管理者申请资源时，先将招标消息广播出去；将招标消息广播出去； 当一资源管理者接收到这一招标消息后，若该场点有所需资源，当一资源管理者接收到这一招标消息后，若该场点有所需资源，则它根据一定方法计算出则它根据一定方法计算出”标数标数”。然后，给申请者发一条投标。然后，
20、给申请者发一条投标消息，否则回复一条拒绝投标的消息；消息，否则回复一条拒绝投标的消息； 4.2.5招标算法招标算法21 当申请者接收到所有的投标消息后，根据一定的策略选择一个当申请者接收到所有的投标消息后，根据一定的策略选择一个投标者，并直接向它发送一条申请资源的消息；投标者，并直接向它发送一条申请资源的消息； 接收到此申请资源消息的资源管理者，将申请者的名字排入其接收到此申请资源消息的资源管理者，将申请者的名字排入其等待队列，并在可以分配所指资源时再发消息通知申请者；等待队列，并在可以分配所指资源时再发消息通知申请者； 申请者在使用完所需资源后，通知分配资源者回收资源。申请者在使用完所需资源
21、后，通知分配资源者回收资源。22 投标与选标策略可视具体情况而定，例如，可用等待队列中排队投标与选标策略可视具体情况而定，例如，可用等待队列中排队等待的申请者的个数作为标数来投标，选标时则选择标数最小的投标等待的申请者的个数作为标数来投标，选标时则选择标数最小的投标者中标，或者不仅考虑有多个资源申请者，还考虑到投标者与招标者者中标，或者不仅考虑有多个资源申请者，还考虑到投标者与招标者之间的距离，如，可规定标数为：之间的距离，如，可规定标数为： xc1 ac2 b 选取最小的选取最小的x中标，其中中标，其中a为等待的申请者的个数，为等待的申请者的个数，b为投标者与招标者为投标者与招标者之间的距离
22、之间的距离c1和和c2为两个常数。采用这种投标与选标策略考虑到了资源为两个常数。采用这种投标与选标策略考虑到了资源使用的均衡性和有效性。使用的均衡性和有效性。23若考虑场点故障而仍使该算法有效，则可增加如下措若考虑场点故障而仍使该算法有效，则可增加如下措施：施： 若资源申请者发出申请消息后久末获得所需资源，则向中标若资源申请者发出申请消息后久末获得所需资源，则向中标者发一询问消息，若中标者末故障就立即予以回复；若发出询问者发一询问消息，若中标者末故障就立即予以回复；若发出询问消息后仍无回复，则申请者重新广播招标消息。消息后仍无回复，则申请者重新广播招标消息。 此时，修改为：此时，修改为：“当申
23、请者接收到所有的投标消息后，或当申请者接收到所有的投标消息后，或等待时间超过预定时间值等待时间超过预定时间值T后，根据一定的策略选择一个投标者，后，根据一定的策略选择一个投标者，并直接向它发送一条申请资源的消息并直接向它发送一条申请资源的消息”。n容易看出，该算法有如下特点：容易看出，该算法有如下特点： 不会出现饥饿现象，因为只要系统中有所申请的不会出现饥饿现象，因为只要系统中有所申请的资源就必有一个中标者，只要每个资源占有者在有限资源就必有一个中标者，只要每个资源占有者在有限长时间内归还所占资源，申请者总能从中标者处获得长时间内归还所占资源，申请者总能从中标者处获得所需资源。所需资源。 在无
24、场点故障情况下，从广播招标消息到接到获在无场点故障情况下，从广播招标消息到接到获得资源的通知，一共交换了得资源的通知，一共交换了2 (n - 1) 22n条消息。条消息。24252.适用于环形结构的招标算法适用于环形结构的招标算法 对于具有环形结构的分布式计算机系统，相应的招标对于具有环形结构的分布式计算机系统，相应的招标算法为：算法为： 申请资源者向其邻近场点发一招标消息；申请资源者向其邻近场点发一招标消息； 接收到招标消息后，若本场点上无所指资源，则它将招标消息接收到招标消息后，若本场点上无所指资源，则它将招标消息沿环转移给下一邻近场点，否则沿环转移给下一邻近场点，否则: 若此消息中未附投
25、标信息，则它将本场点的投标信息附上，并若此消息中未附投标信息，则它将本场点的投标信息附上，并将这一新形成的消息转移给下一邻近场点；将这一新形成的消息转移给下一邻近场点； 若此消息中已附有投标消息，则它就将本场点的投标消息同此若此消息中已附有投标消息，则它就将本场点的投标消息同此消息进行比较，优选一个附上转移给下一邻近场点；消息进行比较，优选一个附上转移给下一邻近场点； 26 某场点接收到自己发出的招标消息后，从其中所附的某场点接收到自己发出的招标消息后，从其中所附的投标信息可知中标者是谁，直接向中标的资源管理者发一申投标信息可知中标者是谁，直接向中标的资源管理者发一申请资源的消息；请资源的消息
26、； 中标者接收到申请消息后，将申请者的名字排入其等待中标者接收到申请消息后，将申请者的名字排入其等待队列，并在可以分配所需资源时向申请者发通知；队列，并在可以分配所需资源时向申请者发通知； 当资源使用完后，申请者通知分配资源者回收资源。当资源使用完后，申请者通知分配资源者回收资源。 对于非环结构的分布式计算机系统，也可采用对于非环结构的分布式计算机系统，也可采用上述算法，只要规定消息统一按上述算法，只要规定消息统一按“逻辑环逻辑环”转移即转移即可。可。 27 4.3 分布式系统中的死锁处理分布式系统中的死锁处理 分布式系统中用于解决死锁问题的方法。分布式系统中用于解决死锁问题的方法。l基于死锁
27、预防基于死锁预防l基于死锁检测。基于死锁检测。 引入资源分配图和进程等待图的概念。引入资源分配图和进程等待图的概念。 284.3.1 资源分配图资源分配图 考虑如图考虑如图4.2所示的资源分配图所示的资源分配图G。其中，其中，V = P R， P = p1, p2, p3，R = r1, r2, r3, r4，E = (p1, r1), (p2, r3), (r1, p2), (r2, p1), (r2, p2), (r3, p3) 资源类资源类该类例示个数该类例示个数r11r22r31r4229可以证明，对于给定的资源分配图可以证明，对于给定的资源分配图G，若，若G中不含环路，则表明系统中不
28、含环路，则表明系统未发生死锁，反之，若未发生死锁，反之，若G中含有环路，则表明系统可能存在死锁。例中含有环路，则表明系统可能存在死锁。例如，若在图如，若在图4.2中插入边中插入边(p3, r2)（如虚线所示），则在这种情形，系（如虚线所示），则在这种情形，系统可能出现死锁。统可能出现死锁。304.3.2 进程等待图进程等待图 从资源分配图中去掉表示资源类的方形并且合并相关的有向边便可得从资源分配图中去掉表示资源类的方形并且合并相关的有向边便可得到对应的进程等待图到对应的进程等待图(process waiting graph)。例如，与图。例如，与图4.3中资源分配图中资源分配图对应的进程等待图
29、如图对应的进程等待图如图4.5所示。所示。 进程等待图中从进程等待图中从pi到到pj的有向边的有向边(pi, pj)意指：意指：pi等待等待pj释被它所需要的释被它所需要的资源。资源。而有向边而有向边(pi, pj)在进程等待图中存在，当且仅当对应的资源分配图在进程等待图中存在，当且仅当对应的资源分配图中，对某个资源类中，对某个资源类rk存在两条边，存在两条边，(pi, rk)和和(rk, pj)。l 若系统中的每一资源类仅含一个例示，则若系统中的每一资源类仅含一个例示，则系统发生死锁的充要条件系统发生死锁的充要条件是进程等待图中存在环路。是进程等待图中存在环路。 进程等待图常简称为等待图。进
30、程等待图常简称为等待图。 314.3.3 利用时间戳预防死锁方法利用时间戳预防死锁方法 预防死锁即破坏导致死锁成立的四个必要条件之一入手。预防死锁即破坏导致死锁成立的四个必要条件之一入手。l 四个必要条件：四个必要条件：互斥互斥请求与保持请求与保持不剥夺不剥夺环路等待环路等待n我们可以通过抢占资源（如果必要）来破坏循环等待条件。我们可以通过抢占资源（如果必要）来破坏循环等待条件。q为了控制抢占，我们给每个进程赋一个唯一的优先数，这些优先为了控制抢占，我们给每个进程赋一个唯一的优先数，这些优先数用以决定进程数用以决定进程pi是否等待进程是否等待进程pj。例如，如果。例如，如果pi的优先数高于的优
31、先数高于pj的优先数，我们可以让的优先数，我们可以让pi等待等待pj，否则，否则pi被撤离。这种方法能防止被撤离。这种方法能防止死锁，因为对于等待图中的每一条边死锁，因为对于等待图中的每一条边(pi, pj)，pi的优先数高于的优先数高于pj的的优先数，因此也就不存在循环等待现象。优先数，因此也就不存在循环等待现象。n可能会发生饥饿现象？可能会发生饥饿现象？n提出了使用时间戳作为优先数的方法。提出了使用时间戳作为优先数的方法。q对系统中的每一进程，当创建它时，就赋给它一个时间戳，对系统中的每一进程，当创建它时，就赋给它一个时间戳，3233 等死（等死（wait-die）方法）方法：是一种基于非
32、抢占性技术的方：是一种基于非抢占性技术的方法。当进程申请当前己由法。当进程申请当前己由pj占有的资源时，仅当占有的资源时，仅当pi的时间戳的时间戳小于小于pj的时间戳（即的时间戳（即pi比比pj年长）时，让年长）时，让pi等待等待,否则否则pi被撤被撤离（死去）。例如，假定进程离（死去）。例如，假定进程p1，p2和和p3分别有时间戳分别有时间戳5，10和和15，若，若p1申请已由申请已由p2占有的资源，占有的资源，p1就等待；如果就等待；如果p3申申请已由请已由p2占有的资源，占有的资源，p3就被撤离。就被撤离。 利用时间戳预防死锁的两种方法是利用时间戳预防死锁的两种方法是34 因伤等待因伤等
33、待(wound-wait)：是一种基于抢占性技术的方法。：是一种基于抢占性技术的方法。而且与上述方法对应。当而且与上述方法对应。当pi申请当前已由申请当前已由pj占有的资源时，占有的资源时，如果如果pi的时间戳大于的时间戳大于pj的时间戳（即的时间戳（即pi比比pj年轻）时让年轻）时让pi等等待，否则待，否则pj被撤离（即被撤离（即pj被被pi致伤），致伤），pi占有资源。再考虑前占有资源。再考虑前面的例子，如果面的例子，如果p1申请已由申请已由p2占有的资源，那么该资源从占有的资源，那么该资源从p2手中抢占，而且手中抢占，而且p2被撤离；如果被撤离；如果p3申请已由申请已由p2占有的资源，占
34、有的资源，则则p3就等待。就等待。35 这两种方案都可以避免饥饿现象发生，只要对被撤离这两种方案都可以避免饥饿现象发生，只要对被撤离的进程不再赋以新的时间戳，因为时间戳总是递增的，因的进程不再赋以新的时间戳，因为时间戳总是递增的，因此，被撤离的进程最终将具有最小的时间戳，因此它将不此，被撤离的进程最终将具有最小的时间戳，因此它将不会再次被撤离。但这两种方案是有差别的：会再次被撤离。但这两种方案是有差别的： 在在“等死等死”方案中，年长的进程必须等待年轻的进程释放它方案中，年长的进程必须等待年轻的进程释放它的资源，因此进程越的资源，因此进程越“年长年长”，它就越容易引起等待。与此相反，在，它就越
35、容易引起等待。与此相反，在“因伤等待因伤等待”方案中，年长的进程决不会等待年轻的进程。方案中，年长的进程决不会等待年轻的进程。 36 在在“等死等死”方案中，如果进程方案中，如果进程pi因为申请已由进程因为申请已由进程pj占领占领的资源而被撤离和死掉，那么当它再次激活时，它又可能再次发的资源而被撤离和死掉，那么当它再次激活时，它又可能再次发出相同的申请，此时，若资源仍由出相同的申请，此时，若资源仍由pj占有，那么，占有，那么，pi将再次将再次“死死掉。因此在得到所需要的资源之前。掉。因此在得到所需要的资源之前。pi可能被撤离若干次。但在可能被撤离若干次。但在“因伤等待因伤等待”方案中，进程方案
36、中，进程pi因为因为pj申请已由它所占有的资源而被申请已由它所占有的资源而被撤离和致伤，当撤离和致伤，当pi再次激话并申请正由再次激话并申请正由pj占有的资源时，占有的资源时，pi就等待。就等待。因此，在因此，在“因伤等待因伤等待”方案中撤离的次数较少。方案中撤离的次数较少。37 死锁预防算法甚至在不发生死锁时也可能抢占资源。死锁预防算法甚至在不发生死锁时也可能抢占资源。l死锁检测算法死锁检测算法构造一等待图来描述资源分配状态。因为我们假定每类资源只构造一等待图来描述资源分配状态。因为我们假定每类资源只有单个例示，因此，等待图中的环路就表示死锁发生。有单个例示，因此，等待图中的环路就表示死锁发
37、生。l如何管理等待图？如何管理等待图？要求每一场点管理一个局部等待图。图中的结点对应所有这样要求每一场点管理一个局部等待图。图中的结点对应所有这样的进程（本地及远程的），这些进程当前正占有或者正在申请的进程（本地及远程的），这些进程当前正占有或者正在申请局部于该场点的任何资源。例如，图局部于该场点的任何资源。例如，图4.6中的系统由两个场点组中的系统由两个场点组成，每个场点都管理它的局部等待图。注意进程成，每个场点都管理它的局部等待图。注意进程p2和和p3出现在出现在两个图中，表示它们在两个场点中申请资源。两个图中，表示它们在两个场点中申请资源。4.3.4 死锁检测方法死锁检测方法3839 显
38、然，如果任何局部等待图中存在环路，则表明发生了显然，如果任何局部等待图中存在环路，则表明发生了死锁。但任何局部等待图中不出现环路并不意味不存在死死锁。但任何局部等待图中不出现环路并不意味不存在死锁锁。例如，考虑图例如，考虑图4.6中的情况，其中每个局部等待图中均无中的情况，其中每个局部等待图中均无环路，但该系统却存在死锁，因为在它的所有局部等待环路，但该系统却存在死锁，因为在它的所有局部等待图之并图中存在环路。图图之并图中存在环路。图4.7中的等待图就是图中的等待图就是图4.6中两个中两个（局部）等待图之并，它的确含有环路，这隐含该系统（局部）等待图之并，它的确含有环路，这隐含该系统存在死锁。
39、存在死锁。 有许多不同的方法构造分布式系统中的等待图，几个常有许多不同的方法构造分布式系统中的等待图，几个常用的方法介绍如下：用的方法介绍如下：404.3.5 集中式死锁检测方式集中式死锁检测方式 采用集中式方式，全局等待图是取所有局部等待图采用集中式方式，全局等待图是取所有局部等待图之并构造而成的，它是由单一进程管理的，这个特殊的之并构造而成的，它是由单一进程管理的，这个特殊的进程称为进程称为”死锁检测协调者（死锁检测协调者（coordinator）”进程，等进程，等待图可以在不同时刻构造：待图可以在不同时刻构造： 每当从局部等待图中去掉一条边或向局部等待图插入一条每当从局部等待图中去掉一条
40、边或向局部等待图插入一条新的边时；新的边时； 周期性地当等待图中已经发生了若干改变时；周期性地当等待图中已经发生了若干改变时； 每当协调者需要引用环路检测算法时。每当协调者需要引用环路检测算法时。 41 当引用该死锁检测算法时，协调者搜索它的全局图，当引用该死锁检测算法时，协调者搜索它的全局图，如果发现一环路，则挑选一个进程作为牺牲者予以撤离，如果发现一环路，则挑选一个进程作为牺牲者予以撤离，从而破坏环路。事后协调者必须通知所有的场点从而破坏环路。事后协调者必须通知所有的场点“此时此时某一进程已经选作为牺牲者某一进程已经选作为牺牲者”。接到通知的场点也应作。接到通知的场点也应作相应的处理。相应
41、的处理。 42这种方案可能导致不必要的撤离，因为存在下述几种这种方案可能导致不必要的撤离，因为存在下述几种现象：现象： 在全局等待图中可能存在假环路。例如，考虑图在全局等待图中可能存在假环路。例如，考虑图4.7中的系中的系统。假定统。假定p2释放了它在场点释放了它在场点A中占有的资源，从而导致场点中占有的资源，从而导致场点A中中删除边删除边(p1, p2)，然后进程，然后进程p2申请场点申请场点B中已由中已由p3占有的资源，于占有的资源，于是导致场点是导致场点B中插入边中插入边(p2, p3)。如果来自场点。如果来自场点B的消息的消息insert(p2, p3)在来自场点在来自场点A的的del
42、ete(p1, p2)消息之前到达，那么，在消息之前到达，那么，在“插入插入”之后之后“删去删去”之前的这段时间隔，协调者可能发现假环路之前的这段时间隔，协调者可能发现假环路p1，p2，p3，我们称这种情况为假死锁（，我们称这种情况为假死锁（falsedeadlock）。这时就得调用）。这时就得调用死锁解除算法，尽管实际上并没有发生死锁。死锁解除算法，尽管实际上并没有发生死锁。43当死锁的确发生而且已选定了一个牺牲者，但在同时某进程当死锁的确发生而且已选定了一个牺牲者，但在同时某进程由于与死锁毫不相干的原因被暂时夭折（如进程的执行时间超由于与死锁毫不相干的原因被暂时夭折（如进程的执行时间超过了
43、分配给它的时间片）时，也可能导致不必要的撤离。过了分配给它的时间片）时，也可能导致不必要的撤离。例如，假定图例如，假定图4.6中的场点中的场点A决定让决定让p2夭折，但在同时协调者已夭折，但在同时协调者已发现一个环路并选定发现一个环路并选定p3作为牺牲者。于是作为牺牲者。于是p2和和p3现在都得撤离，现在都得撤离，尽管此时实际上仅尽管此时实际上仅p2需要撤离。需要撤离。44为了避免报告假死锁，它要求来自不为了避免报告假死锁，它要求来自不同场点的请求消息附上唯一的标识同场点的请求消息附上唯一的标识（时间戳）。当场点（时间戳）。当场点A上的进程上的进程pi申申请位于场点请位于场点B的进程的进程pj
44、占有的资源时，占有的资源时，应发送一条带有时间戳应发送一条带有时间戳n的申请消息。的申请消息。于是，边于是，边(pi, pj, n)被插入到被插入到A的局部的局部等待图中，如果等待图中，如果pj已经接收到这一请已经接收到这一请求消息但不能马上释放所请求的资源求消息但不能马上释放所请求的资源时，边时，边(pi, pj, n)也插入场点也插入场点B的局部的局部等待图中；等待图中；45 如果同一场点中的进程如果同一场点中的进程pi向向pj提出申请，则相应提出申请，则相应的请求消息中不必附上时间戳。该检测算法的执行的请求消息中不必附上时间戳。该检测算法的执行过程如下：过程如下： 协调者向系统中每一场点
45、发送一条初始消息；协调者向系统中每一场点发送一条初始消息； 当接收到这一消息后，各场点将它的局部等待图发送给当接收到这一消息后，各场点将它的局部等待图发送给协调者。注意，每一个等待图包含该场点的所有局部信息。这协调者。注意，每一个等待图包含该场点的所有局部信息。这种等待图反映了相应场点瞬时的状态，但它并不与反映任何其种等待图反映了相应场点瞬时的状态，但它并不与反映任何其它场点的等待图同步。它场点的等待图同步。 46 当协调者接收到来自每一场点的回复消息后，它就按如下方法当协调者接收到来自每一场点的回复消息后，它就按如下方法构造等待图：构造等待图： 系统中的每一进程作为图中一个结点；系统中的每一
46、进程作为图中一个结点； 当且仅当这些等待图之一中有边当且仅当这些等待图之一中有边(pi, pj)或者边或者边(pi, pj, n)(对某对某个个n)出现在一个以上的等待图中时，则在全局等待图中就加上边出现在一个以上的等待图中时，则在全局等待图中就加上边(pi, pj)。 可以断言，如果按此方法所构造的等待图中出现环路，可以断言，如果按此方法所构造的等待图中出现环路，那么该系统处于死锁状态。如果所构造的图中不存在环路，那么该系统处于死锁状态。如果所构造的图中不存在环路，那么在开始执行该算法时，该系统不是处于死锁状态。那么在开始执行该算法时，该系统不是处于死锁状态。474.3.6 层次式死锁检测方
47、法层次式死锁检测方法 集中式死锁检测算法要求所有的信息部驻留在一个进集中式死锁检测算法要求所有的信息部驻留在一个进程中，并且由该进程管理。层次式死锁检测算法则是将这程中，并且由该进程管理。层次式死锁检测算法则是将这些信息分散给多个进程来管理。因而它是一种分布式算法。些信息分散给多个进程来管理。因而它是一种分布式算法。 同集中式方法类似，每个场点管理它自己的局部等待同集中式方法类似，每个场点管理它自己的局部等待图，但与集中式方式不同的是全局等待图被分散给若干不图，但与集中式方式不同的是全局等待图被分散给若干不同的控制者（同的控制者（controller）管理，这些控制者组织成树形结）管理，这些控
48、制者组织成树形结构。其中每片叶子包含单个场点的局那等待图。每个非叶构。其中每片叶子包含单个场点的局那等待图。每个非叶子控制者管理着它下面子树的控制者管理的等待图。子控制者管理着它下面子树的控制者管理的等待图。48 控制者控制者c的局部等待图；的局部等待图； 从从C到到A的路径中每一控制者的局部等待图；的路径中每一控制者的局部等待图； 从从C到到B的路径中每一控制者的局部等待图。的路径中每一控制者的局部等待图。 此外，如果此外，如果pi和和pj出现在控制者出现在控制者D的等待图中，而的等待图中，而且且D的孩子之一的等待图中存在从的孩子之一的等待图中存在从pi到到pj的路径，那么的路径，那么边边(
49、pi, pj)也必须出现在也必须出现在D的等待图中。的等待图中。令令A、B和和C是控制者，是控制者，C是是A和和B的父亲（注意，的父亲（注意，C必须唯一，因为我们讨论的是树形结构）。如果必须唯一，因为我们讨论的是树形结构）。如果结点结点pi出现在控制者出现在控制者A和和B的局部等待图中，那么，的局部等待图中，那么，pi也必须出现在下面的局部等待图中：也必须出现在下面的局部等待图中：49 如果这些等待图中的任何一个出现环路，那么，该系统如果这些等待图中的任何一个出现环路，那么，该系统处于死锁状态，必须引用相应的死锁解除算法。处于死锁状态，必须引用相应的死锁解除算法。 例如，考虑图例如，考虑图4.6所示的系统，该系统的树形结构如所示的系统，该系统的树形结构如图图4.8所示。由于所示。由于p2和和p3都在都在A和和B中出现，所以它们也中出现，所以它们也出现在出现在C中。由于在中。由于在A中存在从中存在从p2到到p3的路径，因此的路径，因此C中中包含包含(p2, p3)。类似地，由于。类似地，由于B中存在从认中存在从认p3到到p2的路径，的路径，所以，所以，C中也包含边中也包含边(p3, p2)。注意。注意C的等待图中出现了的等待图中出现了环路，这表明该系统已出现死锁。环路，这表明该系统已出现死锁。 5051Thanks !
