高级操作系统课件-第三章分布式进程管理.ppt

《高级操作系统课件-第三章分布式进程管理.ppt》由会员分享，可在线阅读，更多相关《高级操作系统课件-第三章分布式进程管理.ppt（79页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第三章第三章 分布式进程管理分布式进程管理线程线程 代码迁移代码迁移处理器任务分配处理器任务分配软件代理软件代理进进 程程定义定义：执行中的程序：执行中的程序进程控制块（进程控制块（PCB）进程的状态进程的状态线线 程程未引入线程前的进程：资源分配单位（存储器、文件）未引入线程前的进程：资源分配单位（存储器、文件）和和CPU调度（分配）单位。调度（分配）单位。线程：成为线程：成为CPU调度单位，而进程只作为其他资源分配单位。调度单位，而进程只作为其他资源分配单位。线程只拥有必不可少的资源，如：线程状态、寄存器上下文和栈线程只拥有必不可少的资源，如：线程状态、寄存器上下文和栈同样具有就绪、阻塞和

2、执行三种基本状态同样具有就绪、阻塞和执行三种基本状态所有线程必须同时挂起，进程的终止导致它包含的所有线程的终止所有线程必须同时挂起，进程的终止导致它包含的所有线程的终止线程的优点：减小并发执行的时间和空间开销（线程的创建、线程的优点：减小并发执行的时间和空间开销（线程的创建、退出和调度），因此容许在系统中建立更多的线程来提高并退出和调度），因此容许在系统中建立更多的线程来提高并发程度。发程度。线程的创建时间比进程短；线程的创建时间比进程短；线程的终止时间比进程短；线程的终止时间比进程短；同进程内的线程切换时间比进程短；同进程内的线程切换时间比进程短；由于同进程内线程间共享内存和文件资源，可直接

3、进行不通过内核的由于同进程内线程间共享内存和文件资源，可直接进行不通过内核的通信通信；进程与线程的关系进程与线程的关系one processone threadmultiple processesone thread per processone processmultiple threadsmultiple processesmultiple threads per process进程和线程的比较进程和线程的比较地址空间和其他资源（如打开文件）：进程间相互独地址空间和其他资源（如打开文件）：进程间相互独立，同一进程的各线程间共享该进程地址空间和其他立，同一进程的各线程间共享该进程地址空间和其

4、他资源某进程内的线程在其他进程不可见资源某进程内的线程在其他进程不可见通信：进程间通信通过通信：进程间通信通过IPC，线程间可以直接读写进线程间可以直接读写进程数据段（如全局变量）来进行通信程数据段（如全局变量）来进行通信需要进程同需要进程同步和互斥手段的辅助，以保证数据的一致性步和互斥手段的辅助，以保证数据的一致性调度：线程上下文切换比进程上下文切换要快得多；调度：线程上下文切换比进程上下文切换要快得多；结论：结论：多线程能提高性能多线程能提高性能线程不像进程那样彼此隔离，并受到系统自动提供的保护，线程不像进程那样彼此隔离，并受到系统自动提供的保护，因此多线程应用程序开发需要付出更多努力因此

5、多线程应用程序开发需要付出更多努力非分布式系统中线程的使用非分布式系统中线程的使用使用多线程的优点：使用多线程的优点：在某线程阻塞时，其他线程可以继续工作在某线程阻塞时，其他线程可以继续工作利用多处理器，并行工作利用多处理器，并行工作缩短缩短IPC通信的时间通信的时间出于软件工程的考虑出于软件工程的考虑:字处理程序字处理程序(用户输入、用户输入、拼写检查、语法检查、文档布局拼写检查、语法检查、文档布局)非分布式系统中线程的使用非分布式系统中线程的使用IPC导致的进程上下文切换导致的进程上下文切换线程实现线程实现用户级线程用户级线程内核级线程内核级线程组合的方法组合的方法用户级线程用户级线程有关

6、线程管理的所有工作由应用程序通过有关线程管理的所有工作由应用程序通过线程库线程库完成，内核不知道线程的存在完成，内核不知道线程的存在应用程序和它的线程被分配给内核管理下应用程序和它的线程被分配给内核管理下的进程的进程优点：优点：创建和销毁线程的开销很小创建和销毁线程的开销很小线程切换不需要内核模式特权，节省切换开销线程切换不需要内核模式特权，节省切换开销调度策略可以是应用程序特定的调度策略可以是应用程序特定的用户级线程可以在任何操作系统中运行，不需要用户级线程可以在任何操作系统中运行，不需要对底层内核进行修改以支持用户级线程对底层内核进行修改以支持用户级线程缺点：缺点：一个线程被阻塞时，进程中

7、所有线程都被阻塞一个线程被阻塞时，进程中所有线程都被阻塞一个多线程应用程序不能利用多处理技术，内核一个多线程应用程序不能利用多处理技术，内核一次只把一个进程分配给一个处理机一次只把一个进程分配给一个处理机内核级线程内核级线程W2K,Linux,OS/2采用采用有关线程管理的所有工作由内核完成有关线程管理的所有工作由内核完成优点：优点：同一进程内线程可被分配到不同处理器上同一进程内线程可被分配到不同处理器上一线程被阻塞，可切换到另一线程一线程被阻塞，可切换到另一线程缺点：缺点：系统开销大系统开销大组合的方法组合的方法Solaris（最成功、应用最广泛的商业最成功、应用最广泛的商业UNIX版本）版

8、本）操作系统采用操作系统采用结合前两种线程优点，同时减少其缺点结合前两种线程优点，同时减少其缺点线程创建完全在用户空间完成，线程调度和同步在线程创建完全在用户空间完成，线程调度和同步在应用程序内进行应用程序内进行n个用户级线程被映射到一些（少于个用户级线程被映射到一些（少于n个）内核级线个）内核级线程上，程序员可为应用程序和机器调整内核级线程程上，程序员可为应用程序和机器调整内核级线程数目，以达到最佳效果数目，以达到最佳效果组合的方法组合的方法分布式系统中线程的使用分布式系统中线程的使用多线程客户：多线程客户：Web浏览器浏览器多线程服务器多线程服务器多线程服务器多线程服务器以分发器以分发器/

9、工作者组织的多线程服务器工作者组织的多线程服务器代码迁移代码迁移定义：将程序（或执行中的程序）传递到其它计算机定义：将程序（或执行中的程序）传递到其它计算机迁移动机：迁移动机：实现负载均衡实现负载均衡将进程从负载重的系统迁移到负载轻的系统，从而改善整将进程从负载重的系统迁移到负载轻的系统，从而改善整体性能体性能改善通信性能改善通信性能交互密集的进程可迁移到同一个节点执行以减少通信开销交互密集的进程可迁移到同一个节点执行以减少通信开销当进程要处理的数据量较大时，最好将进程迁移到数据所当进程要处理的数据量较大时，最好将进程迁移到数据所在的节点在的节点可用性可用性需长期运行的进程可能因为当前运行机器

10、要关需长期运行的进程可能因为当前运行机器要关闭而需要迁移闭而需要迁移使用特殊功能使用特殊功能可以充分利用特定节点上独有的硬件或软件功可以充分利用特定节点上独有的硬件或软件功能能代码迁移代码迁移客户首先获取必需的软件，然后调用服务器客户首先获取必需的软件，然后调用服务器代码迁移代码迁移-灵活性灵活性代码迁移模型代码迁移模型代码迁移的不同方法代码迁移的不同方法进程组成：进程组成：代码段代码段：正在运行的程序的所有指令：正在运行的程序的所有指令资源段资源段：包含进程需要的外部资源的指针：包含进程需要的外部资源的指针执行段执行段：存储进程的当前执行状态量：私有数据、堆栈和程序计数器：存储进程的当前执行

11、状态量：私有数据、堆栈和程序计数器弱可移动性与强可移动性弱可移动性与强可移动性弱可移动性：只能传输弱可移动性：只能传输代码段代码段以及某些初始化数据，程序以初始状态重新执行，简单以及某些初始化数据，程序以初始状态重新执行，简单强可移动性：还可以传输强可移动性：还可以传输执行段执行段，较难实现，较难实现发送者启动与接收者启动发送者启动与接收者启动发送者启动：计算服务器，客户需要访问服务器资源，客户端需要注册验证发送者启动：计算服务器，客户需要访问服务器资源，客户端需要注册验证接收者启动：可以是匿名的，接收者启动：可以是匿名的，Java applet，提高客户端性能，提高客户端性能迁移与本地资源迁

12、移与本地资源MV：移动资源：移动资源GR：建立全局系统范围内引用：建立全局系统范围内引用CP：复制资源的值：复制资源的值RB：将进程重新绑定到本地同类型资源：将进程重新绑定到本地同类型资源未连接未连接附着连接附着连接紧固连接紧固连接按标志符按标志符按值按值按类型按类型MV(or GR)CP(or MV,GR)RB(or MV,CP)GR(or MV)GR(or CP)RB(or GR,CP)GRGRRB(or GR)资源对机器绑定资源对机器绑定进程对进程对资源绑定资源绑定进程对资源绑定进程对资源绑定:按标志符（按标志符（URL）、按值和按类型）、按值和按类型资源对机器绑定：未连接（数据文件）、

13、附着连接（数据库）和资源对机器绑定：未连接（数据文件）、附着连接（数据库）和紧固连接（本地设备）紧固连接（本地设备）迁移代码时，根据引用本地资源方式不同所采取的不同做法迁移代码时，根据引用本地资源方式不同所采取的不同做法处理器任务分配处理器任务分配分配算法的设计原则分配算法的设计原则分配算法的实现问题分配算法的实现问题分配算法实例分配算法实例分配算法的设计原则分配算法的设计原则分配算法的设计原则：分配算法的设计原则：确定性算法和确定性算法和启发性启发性算法算法集中式算法和集中式算法和分布式分布式算法算法最优化算法和最优化算法和次优化次优化算法算法局部性算法和全局性算法局部性算法和全局性算法发送

14、者启动算法和接收者启动算法发送者启动算法和接收者启动算法局部性算法和全局性算法局部性算法和全局性算法第四个设计问题与迁移策略有关。第四个设计问题与迁移策略有关。当一个新进程被创建时，系统需要决定它是否在创建它的机器当一个新进程被创建时，系统需要决定它是否在创建它的机器上运行。若该机器繁忙，那这个新进程就必须迁移到其它机器上运行。若该机器繁忙，那这个新进程就必须迁移到其它机器上去运行。上去运行。对于是根据本机局部信息还是全局信息来决定新进程是否迁移，对于是根据本机局部信息还是全局信息来决定新进程是否迁移，目前存在着两种学派。目前存在着两种学派。1）一种学派主张简单的局部算法：若机器的负载低于某个

15、）一种学派主张简单的局部算法：若机器的负载低于某个阀值，那么新进程就在本地机器上运行；否则，就不允许该阀值，那么新进程就在本地机器上运行；否则，就不允许该进程在本地上运行。进程在本地上运行。2）另一种学派认为局部算法太武断了。最好在决定新进程）另一种学派认为局部算法太武断了。最好在决定新进程是否在本地机器上执行之前，先收集其它一些机器上的负载是否在本地机器上执行之前，先收集其它一些机器上的负载信息。信息。比较：比较：局部算法简单，但远远达不到最优；局部算法简单，但远远达不到最优；而全局算法需要可能付出巨大的代价来换取一个性能稍微好一而全局算法需要可能付出巨大的代价来换取一个性能稍微好一点的结果

16、。点的结果。发送者启动算法和接收者启动算法发送者启动算法和接收者启动算法最后一个设计问题与定位策略有关。最后一个设计问题与定位策略有关。一旦决定不允许一个进程在本地机器上运行，那一旦决定不允许一个进程在本地机器上运行，那么，迁移算法就必须决定将该进程应该迁移到哪么，迁移算法就必须决定将该进程应该迁移到哪台目的机器上。台目的机器上。显然，迁移算法不能是本地的。它需要通过获得显然，迁移算法不能是本地的。它需要通过获得其它机器上的负载信息来决定迁移的目的机器。其它机器上的负载信息来决定迁移的目的机器。这些负载信息可以通过两种途径来获得。这些负载信息可以通过两种途径来获得。一种是过载者启动的一种是过载

17、者启动的另一种是欠载者启动的另一种是欠载者启动的 过载者启动：由过载者来寻找迁移的目的机器过载者启动：由过载者来寻找迁移的目的机器如图：一个机器超载时，它向其它机器发送求助请求，如图：一个机器超载时，它向其它机器发送求助请求，希望将自己的一些新进程迁移到其它机器上运行。希望将自己的一些新进程迁移到其它机器上运行。欠载者启动：欠载者启动：当一个机器处于空闲状态即欠载状态时，由这台欠载机当一个机器处于空闲状态即欠载状态时，由这台欠载机器来宣布自己可以接收外来的工作。其目的就是寻找一器来宣布自己可以接收外来的工作。其目的就是寻找一台可以给自己增加一些额外工作的机器台可以给自己增加一些额外工作的机器

18、分配算法的实现问题分配算法的实现问题负载的度量负载的度量额外消耗额外消耗复杂性复杂性稳定性稳定性实现问题实现问题1：负载的度量负载的度量基本上，所有的算法都假定每一台机器都知基本上，所有的算法都假定每一台机器都知道它自己的负载，也就是说，它可以判断自道它自己的负载，也就是说，它可以判断自己是超载还是欠载，并且能够告诉其它机器己是超载还是欠载，并且能够告诉其它机器自己的负载。自己的负载。然而，度量一台机器是否超载并不象它看上然而，度量一台机器是否超载并不象它看上去那样简单。去那样简单。负载的度量：方法负载的度量：方法1度量方法度量方法1：以机器上的进程数量作为机器的：以机器上的进程数量作为机器的

19、负载负载优点：简单优点：简单原因：只需要计算机器上的进程数量原因：只需要计算机器上的进程数量缺点：用进程数量的多少来表示机器的负载是不缺点：用进程数量的多少来表示机器的负载是不确切的。确切的。原因：即使在一台空闲机器上，仍然会有一些后原因：即使在一台空闲机器上，仍然会有一些后台监视进程在运行，例如，邮件、新闻、守护进台监视进程在运行，例如，邮件、新闻、守护进程、窗口管理程序以及其它一些进程。程、窗口管理程序以及其它一些进程。负载的度量：方法负载的度量：方法2对度量方法对度量方法1进行如下改进：进行如下改进：只计算正在运行或已经就绪进程的数量。只计算正在运行或已经就绪进程的数量。原因：原因：每一

20、个正在运行或处于就绪状态的进程都会给系统每一个正在运行或处于就绪状态的进程都会给系统增加一定的负载，即便它是一个后台进程。增加一定的负载，即便它是一个后台进程。存在的问题：存在的问题：许多后台守护进程只是定时被唤醒，检查所感兴趣许多后台守护进程只是定时被唤醒，检查所感兴趣的事件是否发生，如果没有，则重新进入睡眠状态。的事件是否发生，如果没有，则重新进入睡眠状态。因此，这类进程只给系统带来很小的负载。因此，这类进程只给系统带来很小的负载。负载的度量：方法负载的度量：方法3直接使用处理机利用率：直接使用处理机利用率：就是处理机繁忙时间在全部时间中（繁忙时间就是处理机繁忙时间在全部时间中（繁忙时间+

21、空闲空闲时间）所占的比例。时间）所占的比例。一个利用率为一个利用率为20%的处理机负载要比利用率为的处理机负载要比利用率为10%的处理的处理机大机大优点：比较合理优点：比较合理原因：兼顾了用户进程和守护进程原因：兼顾了用户进程和守护进程实现问题实现问题2：额外开销：额外开销许多理论上的处理机分配算法都忽略了收集负载许多理论上的处理机分配算法都忽略了收集负载信息以及传送进程的额外开销。信息以及传送进程的额外开销。若一个算法将一个新创建的进程传送到远程机器若一个算法将一个新创建的进程传送到远程机器上运行仅使系统性能提高上运行仅使系统性能提高10%左右，那它最好不左右，那它最好不要这样做，原因是传送

22、进程的开销足以抵消所提要这样做，原因是传送进程的开销足以抵消所提高的性能。高的性能。一个好的算法应该考虑算法本身所消耗的处理机一个好的算法应该考虑算法本身所消耗的处理机时间、内存使用、以及网络带宽等。但很少有算时间、内存使用、以及网络带宽等。但很少有算法能做到这一点，因为它太难了。法能做到这一点，因为它太难了。实现问题实现问题3：复杂性：复杂性在处理机分配算法实现中还必须考虑复杂性。在处理机分配算法实现中还必须考虑复杂性。事实上，所有的研究者只分析、模拟或计算处事实上，所有的研究者只分析、模拟或计算处理机的利用率、网络的使用情况以及响应时间，理机的利用率、网络的使用情况以及响应时间，以此来衡量

23、他们所提出算法的好坏。以此来衡量他们所提出算法的好坏。很少有人考虑软件的复杂性对系统的性能、正很少有人考虑软件的复杂性对系统的性能、正确性和健壮性所产生的影响。算法性能有可能确性和健壮性所产生的影响。算法性能有可能只是比现有的算法稍好一点，却在实现上却复只是比现有的算法稍好一点，却在实现上却复杂得多。杂得多。处理机分配算法的实现问题处理机分配算法的实现问题然而，然而，Eager 等人在等人在1986年所做的研究使追求复年所做的研究使追求复杂和最优算法的人们看到了希望。杂和最优算法的人们看到了希望。他们研究了三个算法，在这三个算法中，所有的他们研究了三个算法，在这三个算法中，所有的机器都测量自己

24、的负载以判断它是否超载。机器都测量自己的负载以判断它是否超载。当一个新进程创建时，创建该进程的机器就会检当一个新进程创建时，创建该进程的机器就会检查自己是否超载，如果是，则它就寻找一台欠载查自己是否超载，如果是，则它就寻找一台欠载的远程机器去运行该进程。这三个算法的不同之的远程机器去运行该进程。这三个算法的不同之处在于寻找远程机器的方法。处在于寻找远程机器的方法。处理机分配算法的实现问题处理机分配算法的实现问题算法算法1随机地选择一台机器，并把新创建的随机地选择一台机器，并把新创建的进程进程传送到该机器上。传送到该机器上。如果该接收机器本身也超载，它也同样随如果该接收机器本身也超载，它也同样随

25、机地选择一台机器并把该进程传送过去。机地选择一台机器并把该进程传送过去。这个过程一直持续到有一台欠载的机器接这个过程一直持续到有一台欠载的机器接收它为止，或者指定计数器溢出停止该进收它为止，或者指定计数器溢出停止该进程的传送程的传送 处理机分配算法的实现问题处理机分配算法的实现问题算法算法2随机地选择一台机器，然后发送一个随机地选择一台机器，然后发送一个信息信息给该机器给该机器询问该机器是超载还是欠载。询问该机器是超载还是欠载。如果该机器欠载，它就接收新创建的进程；否则，如果该机器欠载，它就接收新创建的进程；否则，新进程的创建机器继续随机地选择一台机器并向其新进程的创建机器继续随机地选择一台机

26、器并向其发送一个询问消息。发送一个询问消息。这个过程一直持续到找到一台欠载机器为止，或超这个过程一直持续到找到一台欠载机器为止，或超过了一定的询问次数，如果找不到欠载机器，该新过了一定的询问次数，如果找不到欠载机器，该新创建的进程就只好留在本地机器上运行。创建的进程就只好留在本地机器上运行。处理机分配算法的实现问题处理机分配算法的实现问题算法算法3给给k台机器发送询问消息台机器发送询问消息，接收这，接收这k台回送的负载消台回送的负载消息。这个新进程将发送给负载最小的机器，并在它息。这个新进程将发送给负载最小的机器，并在它上面运行。上面运行。显然，如果我们不考虑所有发送询问负载消息和传显然，如果

27、我们不考虑所有发送询问负载消息和传送进程的额外开销，那么，人们会认为算法送进程的额外开销，那么，人们会认为算法3的性的性能最好，事实上也确实如此。能最好，事实上也确实如此。尽管算法尽管算法3的性能只比算法的性能只比算法2的性能稍好一点，但其的性能稍好一点，但其复杂性以及额外开销却比算法复杂性以及额外开销却比算法2要大的多。要大的多。Eager等人认为，如果一个简单算法只比复杂算法等人认为，如果一个简单算法只比复杂算法在性能上略低一点的话，那么，最好使用简单算法。在性能上略低一点的话，那么，最好使用简单算法。实现问题实现问题4：稳定性：稳定性最后一个实现问题就是稳定性。由于不同的机器都在最后一个

28、实现问题就是稳定性。由于不同的机器都在异步地运行各自的计算，所以，整个系统的负载很少异步地运行各自的计算，所以，整个系统的负载很少能够达到平衡。能够达到平衡。因此，有时候会发生这样一种情况：在某个时刻，机因此，有时候会发生这样一种情况：在某个时刻，机器器A得到的信息是机器得到的信息是机器B的负载较轻，因而，它就将的负载较轻，因而，它就将新创建的进程传送给机器新创建的进程传送给机器B。机器。机器B在收到该进程之在收到该进程之前负载又增加了，所以，收到该进程后，它发现机器前负载又增加了，所以，收到该进程后，它发现机器A的负载较轻，于是，它就将该进程又传送给机器的负载较轻，于是，它就将该进程又传送给

29、机器A。这样造成了某个可怜的进程被来回传送的情况。这样造成了某个可怜的进程被来回传送的情况。原因是原因是:每一个机器上的负载每时每刻都在变化。每一个机器上的负载每时每刻都在变化。分配算法实例分配算法实例1.图论确定算法图论确定算法假定：每个进程都知道假定：每个进程都知道 1）所需的处理机）所需的处理机2）所要求的内存）所要求的内存3）系统中任意一对进程间的平均通信量）系统中任意一对进程间的平均通信量若系统中处理机的数目若系统中处理机的数目k比进程数少，那么比进程数少，那么系统中的一些处理机就必须被分配多个进程系统中的一些处理机就必须被分配多个进程基于图论的确定性算法基于图论的确定性算法保证在保

30、证在系统网络通信量最小系统网络通信量最小的条件下对处理的条件下对处理机进行分配。机进行分配。系统的带权图表示系统的带权图表示系统可以被表示图系统可以被表示图G(V,E)，V中的每个节点表示一个进程中的每个节点表示一个进程E中的每条边表示两个进程需要通信，边上面的数字中的每条边表示两个进程需要通信，边上面的数字表示两个进程之间的通信量。表示两个进程之间的通信量。从数学角度看，处理机分配问题已经被简化为：从数学角度看，处理机分配问题已经被简化为：在一定的约束条件下（例如，每一个子图总的处理机在一定的约束条件下（例如，每一个子图总的处理机和内存需求量不超过某一个阀值）将图分割成和内存需求量不超过某一

31、个阀值）将图分割成k个不个不相连的子图。相连的子图。算法的目标就是在满足所有限制条件下，找到一个分算法的目标就是在满足所有限制条件下，找到一个分割方法，使得分割后各子图之间的通信量之和最小。割方法，使得分割后各子图之间的通信量之和最小。分割举例分割举例下图表示了一个图的两种不同的分割方法，并得下图表示了一个图的两种不同的分割方法，并得到了两个不同的通信量。到了两个不同的通信量。CPU1CPU2CPU3CPU1CPU2CPU3分割举例分割举例a中，系统图被分割为：中，系统图被分割为：A,E,G在处理机在处理机1上上B,F,H在处理机在处理机2上上C,D,I在处理机在处理机3上上整个网络通信量整个

32、网络通信量=被虚线分割开的边上被虚线分割开的边上的权值之和的权值之和=303+2+4+4=132+8+5+2=17分割举例分割举例b中显示的分割得到的通信量之和为中显示的分割得到的通信量之和为28如果它满足所有对内存和处理机的限制，那它就如果它满足所有对内存和处理机的限制，那它就是一个比较好的分割，因为它要求的是一个比较好的分割，因为它要求的网络通信量之和较小网络通信量之和较小。3+2+4+4=133+5+5+2=152.集中式算法集中式算法图论算法的局限性在于：图论算法的局限性在于：需要预先知道所有信息，这在一般情况下是需要预先知道所有信息，这在一般情况下是办不到的办不到的一个不需要预先知道

33、所有信息的集中式启发一个不需要预先知道所有信息的集中式启发式算法式算法:“上升上升-下降下降”(up-down)算法算法集中式算法集中式算法上升上升-下降算法的基本思想是下降算法的基本思想是1）由一个协调器来维护一张使用情况表）由一个协调器来维护一张使用情况表每个工作站在表中都对应着一项（初始值为零）每个工作站在表中都对应着一项（初始值为零）当发生一个重要事件时，就给协调器发送一个消息来当发生一个重要事件时，就给协调器发送一个消息来更新使用情况表更新使用情况表2）协调器根据使用情况表来分配处理机）协调器根据使用情况表来分配处理机分配时机：调度事件发生时分配时机：调度事件发生时典型的调度事件：典

34、型的调度事件：申请处理机申请处理机处理机进入空闲状态处理机进入空闲状态发生时钟中断发生时钟中断集中式算法集中式算法当创建一个进程时，如果创建该进程的机器当创建一个进程时，如果创建该进程的机器认为该进程应该在其它机器上运行，它就向认为该进程应该在其它机器上运行，它就向协调器申请分配处理机。协调器申请分配处理机。如果有可分配的处理机时，协调器就分配一如果有可分配的处理机时，协调器就分配一个处理机，否则，协调器就暂时拒绝该处理个处理机，否则，协调器就暂时拒绝该处理机的申请，并记录这个请求。机的申请，并记录这个请求。集中式算法集中式算法增加罚分：增加罚分：当一个工作站上的进程正在其它机器上运行时，它当

35、一个工作站上的进程正在其它机器上运行时，它的罚分每秒钟增加一个固定值。这个罚分将加在使的罚分每秒钟增加一个固定值。这个罚分将加在使用情况表中该工作站所对应的项上。用情况表中该工作站所对应的项上。减少情况减少情况1：每当工作站上的进程需要在其它机器：每当工作站上的进程需要在其它机器上运行的请求被拒绝时，该工作站在使用情况表中上运行的请求被拒绝时，该工作站在使用情况表中所对应项上的罚分就会减少一个固定值。所对应项上的罚分就会减少一个固定值。减少情况减少情况2：当没有等待的处理机分配请求，并且：当没有等待的处理机分配请求，并且处理机也未被使用时，使用情况表中该处理机所对处理机也未被使用时，使用情况表

36、中该处理机所对应项上的罚分就会每秒钟减去一个值，直到为应项上的罚分就会每秒钟减去一个值，直到为0。集中式算法集中式算法如图，由于罚分一会儿上升，一会儿下降，算法由此得名。如图，由于罚分一会儿上升，一会儿下降，算法由此得名。使用情况表中的罚分可以为正数、零和负数。使用情况表中的罚分可以为正数、零和负数。正数正数表示对应工表示对应工作站上的用户是在作站上的用户是在使用系统资源使用系统资源负数负数表示该工作表示该工作站需要系统资源。站需要系统资源。零零表示中性。表示中性。集中式算法集中式算法集中式分配算法的启发性在于：集中式分配算法的启发性在于：当一个处理机变成空闲状态时，首先分配给罚分最低当一个处

37、理机变成空闲状态时，首先分配给罚分最低正在等待处理机的申请。因此，等待时间最长，没有正在等待处理机的申请。因此，等待时间最长，没有使用处理机的请求将优先得到响应。使用处理机的请求将优先得到响应。实际上，若一个用户已使用了一段时间的系统资源，实际上，若一个用户已使用了一段时间的系统资源，另一个用户刚开始申请一个进程的运行，负载较轻的另一个用户刚开始申请一个进程的运行，负载较轻的后者要比负载较重的前者要优先得到资源。后者要比负载较重的前者要优先得到资源。集中式启发式算法公平地分配系统处理机。集中式启发式算法公平地分配系统处理机。模拟研究表明，在各种情况下，该算法都具有较模拟研究表明，在各种情况下，

38、该算法都具有较好的性能。好的性能。3.层次性算法层次性算法“上升上升-下降下降”作为一个集中式算法无法适用作为一个集中式算法无法适用于大型分布式系统。于大型分布式系统。原因：原因：协调器将成为整个系统的瓶颈口，此外，协调器的协调器将成为整个系统的瓶颈口，此外，协调器的崩溃将造成整个系统无法进行处理机的分配。崩溃将造成整个系统无法进行处理机的分配。上述问题可以通过使用上述问题可以通过使用层次分配算法层次分配算法来解决。来解决。层次分配算法既保持了集中式分配算法的简单性，层次分配算法既保持了集中式分配算法的简单性，又能更好地适应于大型分布式系统。又能更好地适应于大型分布式系统。层次性算法层次性算法

39、层次分配算法将所有处理机以一种层次分配算法将所有处理机以一种与物理拓扑与物理拓扑结构无关的方式组织成一个逻辑分层结构结构无关的方式组织成一个逻辑分层结构。这种逻辑分层结构与公司、军队、大学等现实这种逻辑分层结构与公司、军队、大学等现实世界中人的层次组成结构一样。例如，可以将世界中人的层次组成结构一样。例如，可以将一些机器看作为工人，而将另一些机器看作为一些机器看作为工人，而将另一些机器看作为工头。工头。层次性算法层次性算法例如：例如：对于每一组对于每一组k个教师来说，分配给一个系主任的任务是个教师来说，分配给一个系主任的任务是检查观察谁正忙碌，谁正空闲。检查观察谁正忙碌，谁正空闲。如果系统很大

40、，那就需要更多的管理者。于是，有些如果系统很大，那就需要更多的管理者。于是，有些机器将作为院长。每一个院长管理若干个系主任。机器将作为院长。每一个院长管理若干个系主任。如果院长较多，则设置一个校长来管理院长。如果院长较多，则设置一个校长来管理院长。这种层次关系可以进一步扩展下去，并且所需要的层这种层次关系可以进一步扩展下去，并且所需要的层次随着教师的数目成对数级增长。次随着教师的数目成对数级增长。由于每一个处理机只需要与一个上级和若干个下由于每一个处理机只需要与一个上级和若干个下属进行通信，所以就可以对系统的信息流进行管属进行通信，所以就可以对系统的信息流进行管理。层次性算法层次性算法崩溃的解

41、决方法崩溃的解决方法1当一个系主任，或者更严重地，一个院长停当一个系主任，或者更严重地，一个院长停止了工作（即崩溃了），系统将怎么办？止了工作（即崩溃了），系统将怎么办？一种方法就是一种方法就是由崩溃院长所管辖的一个系主任来接替该院长职由崩溃院长所管辖的一个系主任来接替该院长职位，位，这个院长职位这个院长职位1）可以由它下级选举产生）可以由它下级选举产生2）也可以由同级院长们选举产生）也可以由同级院长们选举产生3）还可以由它的上级来任命。）还可以由它的上级来任命。层次性算法层次性算法最高委员会最高委员会为了避免单个管理者在层次树的最顶层（造成系为了避免单个管理者在层次树的最顶层（造成系统不稳定

42、），可以像下图那样统不稳定），可以像下图那样去掉树的根节点，最上层组成一个委员会来作为最高去掉树的根节点，最上层组成一个委员会来作为最高决策机构。决策机构。当委员会中的一个成员不工作了，其他人员将在下一当委员会中的一个成员不工作了，其他人员将在下一层中选出某一个成员来代替。层中选出某一个成员来代替。院长委员会院长系主任 教师层次性算法层次性算法结构分析结构分析结构分析：结构分析：可行性：可行性：实践证明它是一个较好的结构。实践证明它是一个较好的结构。自重构性：自重构性：特别的是，这种系统可以自重构，并能够容忍被特别的是，这种系统可以自重构，并能够容忍被管理者或管理者的突发性崩溃，而不会产生任何

43、管理者或管理者的突发性崩溃，而不会产生任何长期的影响。长期的影响。层次性算法层次性算法处理器预定处理器预定算法中，一个处理机只能分配一个进程。算法中，一个处理机只能分配一个进程。若一个作业产生若一个作业产生S个进程，系统必须为它分配个进程，系统必须为它分配S个处理机。作业可以在层次树上的任何一层次个处理机。作业可以在层次树上的任何一层次上创建。每一个管理者跟踪并记录它辖区内有上创建。每一个管理者跟踪并记录它辖区内有多少个处理机可用。多少个处理机可用。如果有足够的处理机可供使用，那它将预定如果有足够的处理机可供使用，那它将预定R个处个处理机，但理机，但RS必须成立，因为这种估计不一定准确，必须成

44、立，因为这种估计不一定准确，有些机器可能已经关机。有些机器可能已经关机。层次性算法层次性算法处理器预定处理器预定如果没有足够的处理机可供分配，那就把这如果没有足够的处理机可供分配，那就把这个申请请求（逐级）向上传递，直到到达某个申请请求（逐级）向上传递，直到到达某个能够满足该请求的层次。个能够满足该请求的层次。在这一层次上，管理者把这个请求分解成多在这一层次上，管理者把这个请求分解成多个申请并向下传递给下级的管理者，一直传个申请并向下传递给下级的管理者，一直传递到树的底层。递到树的底层。在最低层，被分配的处理机被标为在最低层，被分配的处理机被标为“繁忙繁忙”，并把实际分配到的处理机数沿着树向上

45、逐，并把实际分配到的处理机数沿着树向上逐级报告。级报告。层次性算法：层次性算法：R的取值的取值1）R必须足够的大以便确保有足够数量的处必须足够的大以便确保有足够数量的处理机可供分配。否则，请求将沿着树向上传理机可供分配。否则，请求将沿着树向上传递。这样将会浪费了大量的时间。递。这样将会浪费了大量的时间。2）另一方面，如果）另一方面，如果R太大，那么将有过多的太大，那么将有过多的处理机被标为处理机被标为“繁忙繁忙”，这将浪费一些计算，这将浪费一些计算能力，直到分配消息返回顶层，这些处理机能力，直到分配消息返回顶层，这些处理机才会被释放。才会被释放。4.超载者启动的分布式启发式算法超载者启动的分布

46、式启发式算法 一个典型的分布式启发式算法一个典型的分布式启发式算法 算法描述：算法描述：当一个进程创建时，若创建该进程的机器发现自己超当一个进程创建时，若创建该进程的机器发现自己超载，就将询问消息发送给一个随机选择的机器，询问载，就将询问消息发送给一个随机选择的机器，询问该机器的负载是否低于一个阀值。该机器的负载是否低于一个阀值。1）如果是，那么该进程就被传送到该机器上去运行。）如果是，那么该进程就被传送到该机器上去运行。2）否则，就再随机地选择一台机器进行询问。）否则，就再随机地选择一台机器进行询问。这个过程最多执行这个过程最多执行N次，若仍然找不到一台合适的机器，次，若仍然找不到一台合适的

47、机器，那么算法将终止，新创建的进程就在创建它的机器上那么算法将终止，新创建的进程就在创建它的机器上运行。运行。算法分析算法分析当整个系统负载很重的时候，当整个系统负载很重的时候，每一个机器都不断地向其他机器发送询问消息每一个机器都不断地向其他机器发送询问消息以便找到一台机器愿意接收外来的工作。以便找到一台机器愿意接收外来的工作。在这种情况下，所有机器的负载都很重，没有在这种情况下，所有机器的负载都很重，没有一台机器能够接收其它机器的工作，所以，大一台机器能够接收其它机器的工作，所以，大量的询问消息不仅毫无意义，而且还给系统增量的询问消息不仅毫无意义，而且还给系统增添了巨大的额外开销。添了巨大的

48、额外开销。5.欠载者启动的分布式启发算法欠载者启动的分布式启发算法 在这个算法中，当一个进程结束时，系统就检查自在这个算法中，当一个进程结束时，系统就检查自己是否欠载。己是否欠载。如果是，它就随机地向一台机器发送询问消息。如果是，它就随机地向一台机器发送询问消息。如果被询问的机器也欠载，则再随机地向第二台、第三台如果被询问的机器也欠载，则再随机地向第二台、第三台机器发送询问消息。机器发送询问消息。如果连续如果连续N个询问之后仍然没有找到超载的机器，就暂时个询问之后仍然没有找到超载的机器，就暂时停止询问的发送，开始处理本地进程就绪队列中的一个等停止询问的发送，开始处理本地进程就绪队列中的一个等待

49、进程，处理完毕后，再开始新一轮的询问。待进程，处理完毕后，再开始新一轮的询问。如果既没有本地工作也没有外来的工作，这台机器就进入如果既没有本地工作也没有外来的工作，这台机器就进入空闲状态。空闲状态。在一定的时间间隔以后，它又开始随机地询问远程机器。在一定的时间间隔以后，它又开始随机地询问远程机器。算法分析算法分析在欠载者启动的分布式启发式算法中，在欠载者启动的分布式启发式算法中，当系统繁忙时，一台机器欠载的可能性很小。即当系统繁忙时，一台机器欠载的可能性很小。即使有机器欠载，它也能很快地找到外来的工作。使有机器欠载，它也能很快地找到外来的工作。在系统几乎无事可做时，算法会让每一台空闲机在系统几

50、乎无事可做时，算法会让每一台空闲机器都不间断地发送询问消息去寻找其它超载机器器都不间断地发送询问消息去寻找其它超载机器上的工作，造成大量的系统额外开销。上的工作，造成大量的系统额外开销。但是，在系统欠载时产生大量额外开销要比在系但是，在系统欠载时产生大量额外开销要比在系统过载时产生大量额外开销好得多。统过载时产生大量额外开销好得多。算法比较算法比较与超载者启动的分布式启发式算法相比：与超载者启动的分布式启发式算法相比：欠载者启动的算法不会在系统非常繁忙时给系欠载者启动的算法不会在系统非常繁忙时给系统增加额外的负载。统增加额外的负载。而超载者启动的算法中，一台机器却在系统非而超载者启动的算法中，