高级操作系统 Advanced Operating System

Presentation on theme: "高级操作系统 Advanced Operating System"— Presentation transcript:

1 高级操作系统 Advanced Operating System
熊焰 中国科学技术大学计算机学院

2 第四章 分布式进程和处理机管理 分布式系统模型 分布式处理机分配算法 分布式进程调度 分布式系统容错 实时分布式系统

3 3.2 分布式处理机分配算法 处理机分配的理由: 分布式系统包括多个处理机，具有较大的分布处理能力。
另外，一个作业将产生多个任务或进程，它们需要分配在多个处理机上并行执行，以充分利用分布式系统提供的巨大处理能力。 因此，分布式系统需要一个良好的处理机分配算法来决定每个进程或任务应分配到哪一个处理机上执行通常，这个算法被称为处理机分配算法或任务分配算法（通常不称作进程分配算法，尽管但两者的意思完全相同）。

4 3.2分布式处理机分配算法 处理机分配的基本模型、假定和目标： 1）关于处理器：
假定所有的机器都是相同的，至少是代码兼容的，不同的只是运行速度。 有些还假定系统具有多个互不相关的处理机池，每一个处理机池都是相同的。

5 3.2分布式处理机分配算法 2）关于互连拓扑： 假定系统是完全互连的，即每一个处理机都可以与其它任意一个处理机通信。
这并不表示每一个机器与其它任意一台机器之间都有线路直接连接，这个假定只是意味着每一对机器都可以互相通信。至于消息是如何从一台机器到达另一台机器的问题只是低层通信软件的事，处理机分配算法无需考虑。但有一些处理机分配算法利用了网络的广播或者多播的特性。

6 3.2分布式处理机分配算法 新进程的产生和处理机的分配： 当一个运行中的进程决定创建一个子进程时，产生了下列工作：
在有些情况下，创建进程是由系统的命令解释程序（即shell）来完成的。它为用户执行其指定的命令所对应的程序。 而在另一些情况下，用户进程本身也可以创建一个或者多个子进程，以获得较高的系统性能。 对新进程必须考虑分配到哪个处理器上运行

7 3.2分布式处理机分配算法 处理机分配策略可以分为两大类： 1）非迁移的 2）可迁移的 第一类是非迁移的（nonmigratory）
在非迁移策略中，当创建一个进程时，系统就决定它被分配到哪台处理机上。一旦一个进程被分配到一台机器上，那么，它就在那台机器上运行，一直到终止，不管这台处理机的负载是多么的重，而别的处理机是多么的空闲，它都不能迁移到别的处理机上运行。

8 3.2分布式处理机分配算法 第二类是可迁移的（migratory）
对于可迁移策略来说，一个进程即使已经被分配到一台处理机上并已经运行了一段时间，如果其负载变重了,它也可以动态地迁移到其它轻负载的处理机上继续运行。 虽然可迁移策略可以使系统达到良好的负载平衡，但实现起来却异常复杂。

9 3.2分布式处理机分配算法 处理机分配算法必须尽可能优化。否则，我们完全可以随机地或按数字顺序来分配处理机。 不同系统的优化内容是不一样的
优化目标1：提高处理机利用率 优化目标2：最小化平均响应时间

10 3.2分布式处理机分配算法 第一个优化目标就是： 尽量提高处理机的利用率 让处理机在每个小时内执行用户工作的周期数尽可能地大
换句话说，要尽量减少空闲处理机周期数。

11 3.2分布式处理机分配算法 第二个有价值的优化目标就是： 使平均响应时间最小化

12 3.2分布式处理机分配算法 举例: 假设有两个处理机。
处理机1以10MIPS的速度运行， 处理机2以100MIPS的速度运行，其中等待队列中的进程需要5秒才能完成。 有两个进程。 进程A有1亿条指令，执行时间分别为10秒（在处理机1上）和1秒（在处理机2上） 进程B有3亿条指令，执行时间分别为30秒和3秒

13 3.2分布式处理机分配算法 这两个进程在每一个处理机上的响应时间（包括等待时间）如图所示。 5+1 = 5+3 =

14 3.2分布式处理机分配算法 平均响应时间： 如果把进程A和B分别分配给处理机1和2，那么平均响应时间是(10+8)/2=9秒。
若反向分配，那么平均响应时间就是(30+6)/2=18秒。 显然，前者的平均响应时间要比后者小。

15 3.2分布式处理机分配算法 最小响应时间的另一种形式就是最小响应率。
响应率定义为：在一台机器上运行一个进程所需的时间除以该进程在无负载的标准处理机上运行所需的时间。

16 3.2分布式处理机分配算法 对于大多数用户来说，响应率比响应时间更重要。 其原因是： 考虑了大任务要比小任务花费更多时间这一情况。 例如：
一个1秒的任务花了5秒，而一个1分钟的任务花了70秒，从响应时间上看，前者好，但从响应率上看，后者更好，因为5/1>>70/60。

17 3.2分布式处理机分配算法 考虑负载的分配方法：
局部和全局 局部负载分配处理单个处理器上的进程对时间片（单元）的分配。全局负载分配首先进行进程对处理器的分配，然后完成每个处理器内这些进程的局部调度。 静态和动态（在全局类中） 静态负载分配中，进程对处理器的分配是在进程执行以前的编译阶段完成的，而动态负载分配要到进程在系统中执行时才做出分配。静态方法又叫做确定性调度，而动态方法叫做负载平衡。

18 3.2分布式处理机分配算法 最优和次优（在静态和动态两种类型中） 如果根据某种标准（例如，最小执行时间和最大系统输出）可以取得最优分配，那么就可以认为这种负载分配方法是最优的。 一般地，负载分配问题是NP完全问题。某些情况下，次优方案（神经网络方法）也是可以接受的。 有四类算法（对于最优的和次优的）被使用： 1）解空间枚举搜索、 2）图模型、 3）数学编程（例如0/1规划） 4）队列模型

19 3.2分布式处理机分配算法 近似和启发式（在次优类型中） 在近似方法中，负载分配算法仅搜索一个解空间的子集，当寻找到一个好的解时，终止执行 在启发式方法中，调度算法使用某些特殊参数，能够近似地对真实系统建模。

20 3.2分布式处理机分配算法 集中控制的和分散控制的（在动态类型中） 在分散控制中，分配决策工作被分配给不同的处理器。在集中控制中，分配决策工作由一个处理器完成。 协作的和非协作的（对分散控制） 动态负载分配机制可以分成：协作的（分布式对象间有协同操作）和非协作的（处理器独立做出决策）。

21 3.2分布式处理机分配算法 下图显示了上述负载分配算法的分类情况

22 3.2分布式处理机分配算法 其他负载分配算法的分类方法：
单个和多个应用程序 多数负载分配算法是针对单个应用程序。 多应用程序情况可以转换成单个应用程序情况。例如，应用图模型时．对多应用程序的多个图可以认为是一张图。 然而，多应用程序情况下的进程分配远复杂于单个应用程序的情况。 多应用程序情况下用平均子图完成时间作为衡量指标，单个应用程序情况下用最小完成时间作为衡量指标。

23 3.2分布式处理机分配算法 非抢占式的和抢占式的 对非抢占式的负载分配算法，一个任务（进程）开始执行后就不能中断。在抢占式负载分配算法中，进程可以中断，并从处理器上移走，以后继续执行 。 非自适应的和自适应的 非自适应负载分配只使用一种负载分配算法，不会依据系统反馈而改变白己的行为。自适应负载分配能够根据系统反馈调整分配算法。典型地，一个自适应负载分配算法是许多负载分配算法的集合，依据系统的各种参数来选择一个合适的算法。

24 3.2分布式处理机分配算法 一般来说，设计者在设计算法时，需要考虑以下五个方面的情况： 算法是确定式还是启发式的。
算法是集中式的还是分布式的。 算法是最优的还是次优的。 算法是局部的还是全局的。 算法是过载者启动的还是欠载者启动的。

25 3.2分布式处理机分配算法 确定式算法需要预先知道进程所有的信息: 一般，进程的信息包括： 进程的计算需求 文件需求 通讯需求等等
如果设计者能够获得所有进程的信息，那就可以设计出一个完美的分配方案，并获得最佳的分配结果。 但只有极少的一些系统可以事先获得所有进程的信息。

26 3.2分布式处理机分配算法 可预测系统 vs 不可预测系统
在可预测系统中，可以通过合理的近似来事先得到所有进程的信息。例如，在银行业、保险业、民航定票系统中，每天的情况都基本相似，民航根据经验可以预测到早春第一周周一的清晨大约有多少人要从纽约去芝加哥，这样就保证了确定式算法的可行性。 与可预测系统相反，有些系统的负载是完全无法预测的。用户所做的工作每一个小时，甚至每一分钟都在动态地改变。在这种系统中的处理机分配不能用一种在数学上确定的算法实现，而需要

27 3.2分布式处理机分配算法 使用一种称之为启发式的算法。
集中式算法需要将系统中所有的信息都收集到某个机器上，这会造成系统不够坚定，并且该机器负载过于沉重。因此，一般都采用分布式算法来实现处理机分配。然而，一些集中式算法仍然被采用，原因是没有相应的分布式算法来取代它。

28 3.2分布式处理机分配算法 第三个设计问题与前两个问题有关，是获得一个最优解？还是一个可行的次优解？
一般来说，采用集中式和分布式算法都能够得到最优解，但得到最优解所花费的代价要比得到次优解复杂得多。 此外，最优解需要收集更多的信息以及进行全面复杂的处理。 对于大多数分布式系统来说，只要有一个启发、分布、次优的处理机分配算法就可以了。因为，要获得最优解实在是太难了。

29 3.2分布式处理机分配算法 第四个设计问题与迁移策略有关：
当一个新进程被创建时，系统需要决定它是否在创建它的机器上运行。若该机器繁忙，那这个新进程就必须迁移到其它机器上去运行。 对于是根据本机局部信息还是全局信息来决定新进程是否迁移，目前存在着两种学派。 1）一种学派主张简单的局部算法：若机器的负载低于某个阀值，那新进程就在本地机器上运行；否则，就不允许该进程在本地上运行。 2）另一种学派认为局部算法太武断了。最好在决定新进程是否在本地机器上执行之前，先收集

30 3.2分布式处理机分配算法 其它一些机器上的负载信息。
比较： 局部算法简单，但远远达不到最优； 而全局算法需要付出巨大的代价来换取一个性能稍微好一点的结果。

31 3.2分布式处理机分配算法 最后一个设计问题与迁移的目的机器有关。
一旦决定不允许一个进程在本地机器上运行，那么，迁移算法就必须决定将该进程应该迁移到一台目的机器上。显然，迁移算法不能是本地的。它需要通过获得其它机器上的负载信息来决定迁移的目的机器。这些负载信息可以通过两种途径来获得。 过载者启动。 欠载者启动。

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

33 3.2分布式处理机分配算法 不管是过载者启动的算法还是欠载者启动的算法，不同的算法要采用不同的策略来决定谁收集信息、收集时间多长以及如何处理收集的信息。 通常，所有的算法都假定每一台机器都知道它自己的负载，也就是说，它可以判断自己是超载还是欠载，并且能够告诉其它机器自己的负载。 然而，度量一台机器是否超载并不象它看上去那样简单。

34 3.2分布式处理机分配算法 负载度量方法1： 以机器上的进程数量作为机器的负载。 优点：简单 原因：只需要计算机器上的进程数量
缺点：用进程数量的多少来表示机器的负载是不确切的，它几乎说明不了什么问题。 原因：即使在一台空闲机器上，仍然会有一些后台监视进程在运行，例如，邮件、新闻、守护进程、窗口管理程序以及其它一些进程。因此，

35 3.2分布式处理机分配算法 对度量方法1进行如下改进： 只计算正在运行或已经就绪进程的数量。 原因：
每一个正在运行或处于就绪状态的进程都会给系统增加一定的负载，即便它是一个后台进程。 存在的问题： 许多后台守护进程只是定时被唤醒，检查所感兴趣的事件是否发生，如果没有，则重新进入睡眠状态。因此，这类进程只给系统带来很小的负载。

36 3.2分布式处理机分配算法 一个利用率为20%的处理机负载要比利用率为10%的处理机大。 优点：比较合理。 原因：兼顾了用户进程和守护进程。
直接使用处理机利用率： 处理机繁忙时间在全部时间中（繁忙时间+空闲时间）所占的比例。 一个利用率为20%的处理机负载要比利用率为10%的处理机大。 优点：比较合理。 原因：兼顾了用户进程和守护进程。

37 3.2分布式处理机分配算法 利用率的测量： 设置一个定时器，它周期地中断处理机，每次都检查处理机的状态。并按照上述公式计算处理机利用率。它存在的问题： 使用定时器中断所产生的一个问题就是当处理机内核正在执行原语时，它屏蔽了包括定时器中断在内的所有中断。当原语执行时发生定时器中断，中断就会在原语执行完毕才能得到响应。如果该原语正阻塞前一个活动进程，那么，计算出的处理机利用率就会比实际情况要低得多。

38 3.2分布式处理机分配算法 许多理论上的处理机分配算法都忽略了收集负载信息以及传送进程的额外开销：
若一个算法将一个新创建的进程传送到远程机器上运行仅使系统性能提高10%左右，那它最好不要这样做，原因是传送进程的开销足以抵消所提高的性能。 一个好的算法应该考虑算法本身所消耗的处理机时间、内存使用、以及网络带宽等。但很少有算法能做到这一点，因为它太难了。

39 3.2分布式处理机分配算法 在处理机分配算法实现中还必须考虑复杂性：
事实上，所有的研究者只分析、模拟或计算处理机的利用率、网络的使用情况以及响应时间，以此来衡量他们所提出算法的好坏。很少有人考虑软件的复杂性对系统的性能、正确性和坚固性所产生的影响。 也不会有人提出了一个新算法并宣称它的性能非常好，然后，得出结论说这个算法不值得使用，因为它的算法性能有可能只是比现有的算法稍好一点，但在实现上却复杂得多。

40 3.2分布式处理机分配算法 然而，Eager 等人在1986年所做的研究使追求低复杂和最优的人们看到了希望。他们研究了三个算法。在这三个算法中，所有的机器都测量自己的负载以判断它是否超载。当一个新进程创建时，创建该进程的机器就会检查自己是否超载，如果是，则它就寻找一台欠载的远程机器去运行该进程。这三个算法的不同之处在于寻找远程机器的方法。

41 3.2分布式处理机分配算法 算法 随机地选择一台机器，并把新创建的进程传送到该机器上。如果该接收机器本身也超载，它也同样随机地选择一台机器并把该进程传送过去。这个过程一直持续到有一台欠载的机器接收它为止，或者指定计数器溢出停止该进程的传送。

42 3.2分布式处理机分配算法 算法 随机地选择一台机器，然后发送一个信息给该机器询问该机器是超载还是欠载。如果该机器欠载，它就接收新创建的进程；否则，新进程的创建机器继续随机地选择一台机器并向其发送一个询问消息。这个过程一直持续到找到一台欠载机器为止，或超过了一定的询问次数，如果找不到欠载机器，该新创建的进程就只好留在本地机器上运行。

43 3.2分布式处理机分配算法 算法3 给k台机器发送询问消息，接收这k台回送的负载消息。这个新进程将发送给负载最小的机器，并在它上面运行。
显然，如果我们不考虑所有发送询问负载消息和传送进程的额外开销，那么，人们会认为算法3的性能最好。事实上也确实如此。尽管算法3的性能只比算法2的性能稍好一点，但其复杂性以及额外开销却比算法2要大的多。Eager等人认为，如果一个简单算法只比复杂算法在性能上略低一点的话，那么，最好使用简单算法。

44 3.2分布式处理机分配算法 最后一个实现问题就是稳定性:
由于不同的机器都在异步地运行各自的计算，所以，整个系统的负载很少能够达到平衡。因此，有时候会发生这样一种情况：在某个时刻，机器A得到的信息是机器B的负载较轻，因而，它就将新创建的进程传送给机器B。机器B在收到该进程之前负载又增加了，所以，收到该进程后，它发现机器A的负载较轻，于是，它就将该进程又传送给机器A。这样造成了某个可怜的进程被来回传送的情况。原因是，每一个机器上的负载每时每刻都在变化。

45 3.2分布式处理机分配算法 静态分配算法根据系统的先验知识做出决策: 运行时负载不能够重新分配。
算法目标： 调度一个任务集合，使它们在各个目标PE上有最小的执行时间。 设计算法时的三个主要的因素： 处理器互连 任务划分（粒度决策） 任务分配 处理器互连用来给出处理器之间的物理连接拓扑

46 3.2分布式处理机分配算法 静态分配问题即便在简单地对计算开销和通信开销做某种假设以后，依然是一个NP完全问题。因此，可以利用数学工具如图、启发式规则来得到次优的解。通常，用图模型表示任务和PE 结构。可以用任务优先图或者任务交互作用图对任务集合建模。

47 3.2分布式处理机分配算法 任务优先图又称为有向无环图（DAG）： 如图， 每个链接：定义任务间的优先关系 节点上的标记：表示任务执行时间
链接上的标记：表示任务完成后启动后续任务所需的时间间隔

48 3.2分布式处理机分配算法 任务交互作用图： 如图： 链接：定义两个任务间的相互关系
每个链接赋予一对数：表示这两个任务在同一个PE 上时的通信开销和在不同PE 上时的通信开销。

49 3.2分布式处理机分配算法 任务划分的粒度： 一个给定任务划分的粒度定义是任务分解中影响通信开销的所有单元的平均尺度。根据数据单元的大小，算法可以分成。 细粒度：数据单元小 粗粒度：数据单元大 中粒度：介于上述两者之间 粒度的大小： 1）若太大，会降低并行度，因为潜在的并行任务可能被划分进同一个任务而分配给一个处理器。 2）若太小，进程切换和通信的开销就会增加。

50 3.2分布式处理机分配算法 任务划分的一个主要目标： 尽可能消除处理器间通信引起的开销。可以使用三种方法：
任务划分的一个主要目标： 尽可能消除处理器间通信引起的开销。可以使用三种方法： 水平或者垂直划分。 主要思想是在给定的任务优先图中垂直或者水平划分。关键路径（最长路径）的概念常常在垂直划分中使用。水平划分把给定的任务分成若干层，任务的优先级由它们所在的层次决定

51 3.2分布式处理机分配算法 通信延迟最小划分： 主要思想是把通信频繁的节点归成一类。然而，这些需要通信的任务分配在一个处理器上会丧失任务间的并发性。 有的研究者认为：如果减小通信延迟的好处抵销了并行任务串行化的损失，就采用通信延迟最小划分。 可以把一个划分问题转换成一个网络流问题，将在后面的小节中讨论。

52 3.2分布式处理机分配算法 任务复制，这是任务划分的一个可选方法： 主要思想是通过在PE上复制任务来降低通信开销。这个方法保留了任务原有的并行性；但是存储空间要求和同步开销增加了。 可以利用任务复制来达到容错性，可以实现无错调度以保证处理器出现错误时最后计算结果正确。

53 3.2分布式处理机分配算法 任务划分被称做任务聚类，它强调在给定的图模型中对小任务分类。任务划分把图当做一个整体，划分成不同的类（颗粒）。不论任务划分还是任务聚类，都生成一个颗粒集合。通常颗粒的数目等于处理器的个数，以此简化下一步的任务分配程序。

54 3.2分布式处理机分配算法 任务分配就是在给定了互连网络的并行系统或者分布式系统中分配颗粒（颗粒是任务划分的结果）。
若任务图和处理器图的节点数目都是n ，那么就有n!种不同的分配方法把任务图Gt里的节点分配到处理器图Gp的节点上。 通常把每种方法称做Gt到Gp的一个映射。 在总执行时间概念下，有些映射比较好。

55 3.2分布式处理机分配算法 关于Gp的典型假设： 存储器容量无限。 每个PE 有相同的处理能力。
忽略网络拥塞，虽然通信进程间的距离是影响通信延迟的因素。 注意：任务调度不必要一定分两个步骤做，即任务划分和任务分配。分两步的方法只是为了简化原本是NP完全的调度过程。

56 3.2分布式处理机分配算法 假定一个进程集合P={P1, P2, P3, … Pn}，在一系列同样的处理器上执行。
任务优先图：定义P上的偏序＜关系，构成(P, <)关系集，并用G=(V, A)描述，其中， V是顶点的集合，表示进程集； A是弧集合，表示进程间的优先关系。 A中的一个链接表示为(u, v), u和v是V中的两个连接进程（节点）。

57 3.2分布式处理机分配算法 对每个节点和链接都定义有代价函数w： W(u)∈(0, ∞)是节点u的代价，u属于V;
W(u, v)=(l, l ’)是链接(u, v)的代价，其中 l ’：同一处理器内的通信代价（若u和v被分配在同一个处理器上） l：处理器间的通信代价（若u和v被分配在不同处理器上）。

58 3.2分布式处理机分配算法 任务优先关系图模型中不考虑处理器互连： 假设每对处理器间的通信延迟是一个固定数值
事实上，处理器通信延迟在l中得到了体现。 通常，处理器内部通信代价l ’相对于处理器间通信代价l 要小。因此可以忽略， 记做W(u, v)=l。

59 3.2分布式处理机分配算法 甘特图能够最有效描述进程对处理器的分配情况:
甘特图以处理器为纵坐标，时间为横坐标。图中的每个方块表示进程在某个系统中的开始时间，持续时间和结束时间。处理器内的时间延迟和处理器间的时间延迟都能够在图中体现。

60 3.2分布式处理机分配算法 图a显示了一个实例的任务优先图 图b是对处理器P1, P2的一个调度结果。 圆圈中的数对应任务的执行时间
与每个链接相关的数对应于处理器间的通信时间（延迟）。两个连接任务分配在不同的处理器上时就会发生通信延迟 例如，W(T1)=2和W(T1,T2)=1表示T1的执行时间是2, T1和T2间处理器间的通信代价是1 （没有给出处理器内的通信代价）。 图b是对处理器P1, P2的一个调度结果。 本例中，两个处理器间的通信发生在有1个单位通信延迟的T2T4和有2 个单位通信延迟的T4T5。总的执行时间是12 。 (b)

61 基于任务优先图的任务调度 通信延迟的影响 通信延迟使调度算法大大地变复杂。 例：图b, c, d给出了针对a中任务优先图的三种不同的调度
对于c和d，若通信延迟d大于T2的执行时间，图c的调度就比图d 要好。可以说，若通信延迟太大的话，所有任务分配在一个处理器上是比较合适的。 (a) (b) (c) (d)

62 基于任务优先图的任务调度 通信延迟的影响 通常总是尝试尽量增加并行度，同时尽可能降低通信延迟。然而在多数时间这两个目标是互相矛盾的。因此需要某种程度折衷。 有时可以使用任务复制的方法减少通信需求。显然，由于通过任务复制而避免了处理器间的通信，图b的结果是最好的。 (a) (b) (c) (d)

63 基于任务优先图的任务调度 线性与非线性调度
前面提到了任务划分（又称做任务聚类）中的粒度问题，是把指定应用程序的任务分成一个个任务类。 通常类的数目应等于处理器个数 若至少有一个类中包含两个独立的任务，则分类是非线性的；否则，分类就是线性的。 右图分别是三个进程的线性调度和非线性调度。

64 基于任务优先图的任务调度 粒度的定义 一个任务优先图可以认为是许多分叉和合并操作的集合，如右图所示
为了判别好的分类算法，引入了对每个分叉或者合并的粒度的概念。 右图中，分叉x（合并x）的粒度是： =最小的进程代价/最大的连接代价 给定任务优先图G 的粒度是：

65 基于任务优先图的任务调度 粒度的定义 如果 合并或分叉x就是粗粒度的； 否则，就是细粒度的。
下图中的任务划分是粗粒度，因为最小的进程代价大于最大的连接代价(g(x)=2/1=2)。

66 基于任务优先图的任务调度 线性分类与非线性分类的比较
例中图a的线性分类的执行时间是7。图b中非线性分类的执行时间是9。

67 基于任务优先图的任务调度 线性分类与非线性分类的比较
如果把W(T1, T3)和W(T1, T2)改成4，相应的图变成细粒度分叉，非线性分类的执行时间是9，优于执行时间是10的线性分类。

68 基于任务优先图的任务调度 算法实例：两种最优调度算法
两种有约束的调度问题，它们有多项式时间的执行复杂度。 两种方法都假设通信代价可以忽略和优先图中每个节点的执行时间是一样的（一个时间单元）。 具体限制如下： 在第一个有约束的调度问题中，优先图是一棵树。 在第二个有约束的调度问题中，只有两个处理器可用 两种调度算法都是最高优先级优先的方法，也就是说，通过节点的等级（优先级）来选择节点。

69 基于任务优先图的任务调度 案例1：优先级定义
案例1中节点u的等级是它到根节点的距离加1 注意：节点的等级越高，它的优先级就越高。 当若干个节点有相同的等级时，所有先导节点都已执行的节点被第一个选中；如果还有若十个节点符合上述条件，则做随机选择。

70 优先图举例 右图显示了一个树结构的优先图 等级5的任务有最高优先级， 等级1的任务优先级最低。 同一等级的任务有相同优先级。
T1, T2, T3和T4 在等级5 T5, T6和T7在等级4 T8和T9在等级3 T10, T11和T12在等级2 T13在等级1 等级5的任务有最高优先级， 等级1的任务优先级最低。 同一等级的任务有相同优先级。

71 算法案例1： 任务分配举例 三个处理器上的最优调度，如右下图所示 从第一个时间槽开始根据优先级进行分配。
有先后关系的任务不能分配在同一个时问槽中。 例如T6必须被分配在T4后面的时间槽中。

72 算法案例1： 分配算法的实现：就绪队列定义 就绪队列被用来高效的实现上述调度算法 就绪队列包括所有节点，它们的先导节点都已经执行完毕
根据优先级从就绪队列中选择后续节点执行。 注意，一个节点被调度时，就绪队列就必须更新。

73 算法案例1： 就绪队列举例： 图9-8 中， 为方便起见，队列中的任务按优先级排序
图9-8 中， 为方便起见，队列中的任务按优先级排序 初始就绪队列是{T1,T2,T3,T4,T5,T7,T9,T10,T12} 队列中的前三个任务分配在第一 个时间槽 就绪队列变成{T4,T5,T7,T9,T10, T12}。 T4,T5和T7分配在时间槽2

74 算法案例1： 就绪队列举例： T6加入就绪队列{T6,T9,T10,T12}。 再将队列中前三个任务分配给下一个时间槽

75 基于任务优先图的任务调度 案例2：优先级定义
案例2假定有两个处理器。优先图中不同节点的等级不相同。下面的算法生成一个优先图： 假定有k个终止节点（无后续节点），从1到k依次标记这些节点。 令S是没有被分配（未被标记）的节点的集合，并且其中每个节点的后续节点都已被标记，从中选一个标记成i。方法如下： 令lex(u)是u的所有直接后续节点的标记的升序排列。 若对S中所有u’(u’≠u), lex(u)<lex(u’) （字典序），那么u可以赋予i 。

76 案例2： 优先图举例 图9-9 表示一个优先图，每个节点都用上面的方法进行了标记。节点的标记可以当做它的优先级
任务按照优先级升序排序为： T1,T2,T3,T4,T5,T6,T11, T8,T7, T10,T9 注意终止任务T1,T2,T3的顺序是随机选 择的，例中它们的优先级分别是1,2,3 T4的直接后续节点是T1和T2， 因此lex(T4)=(1, 2)。 显然lex(T4)< Iex(T5) 所以T4的标记是4 ，T5的标记是5 。

77 案例2： 任务分配举例 图9-6b 是甘特图表示的最优调度。

78 基于任务相互关系图的任务调度 任务图定义 第二个任务调度模型是利用任务相互关系图和进程的集合来表示应用程序。
任务相互关系图由无向图Gt(Vt, Et)表示 Vt：是进程的集合 Et：是边的集合， 其中每条边表示两个通信进程间的相互作用关系，用相关两个进程的通信代价标记（不是优先关系）

79 基于任务相互关系图的任务调度 处理器图定义
与任务优先图模型不同的是处理器间通信在任务相互关系图调度模型中有重要作用。 特别地，处理器图由Gp(Vp, Ep)表示 顶点集Vp中每个元素是一个处理器 边集Ep中每个元素是一个通信信道 一般来说，|Vt|<=|Vp|，因此可以假设任务划分已经完成。然后，进行分配M:VtVp以及执行时间的估计。注意，w(u)和w(u, v)分别表示节点u和链接(u, v)的代价。

80 基于任务相互关系图的任务调度 负载定义 处理器p的计算负载，p∈Vp: 通信负载： 在一个应用程序中总的计算和通信量是：
注意链接的通信代价被计算了两次：两个节点各一次。因此，对每个处理器计算通信代价时被2 除是必要的。

81 基于任务相互关系图的任务调度 负载定义 程序总的执行时间大概是：
其中，α依据每个PE的执行速度，β依据每个通信信道的通信速度和通信进程间的距离。 注意如果两个进程u和v在Gt邻接，它们在Gp的映像（M 的映像结果）可能邻接也可能不邻接。理想的情况下，所有通信进程被分配在邻接的处理器上，以此减少处理器间通信。

82 基于任务相互关系图的任务调度 映射的势 注意通常两个进程不应该映射在一个处理器上。
任务分类时这两个进程应当分类进同一个类。 评估映射质量的一个指标是 映射的势，即 任务图Gt中的边映射到处理器图Gp的边的数目。也是Gt中映射到Gp中邻接处理器的通信进程对的数目。 映射的势不能超过Gt中的链接数。 如果一个映射的势最大，它就是一个理想映射

83 基于任务相互关系图的任务调度 映射的势举例
下图中，左边是一个任务相互关系图，右边是一个具有9个处理器的处理器图。 右图显示了任务与处理器的映射关系，该映射的势是8（13条边）。 13-5条虚边=8

84 基于任务相互关系图的任务调度 映射的势 有时映射的势可能不能准确地反映映射的质量。比如，它不能区分下面两种情况：
a）两个通信进程被映射到两个处理器上，这两个处理器在处理器图中的距离是k(k>2)， b）两个通信进程被映射到两个处理器上，这两个处理器在处理器图中的距离是2 。 需要图嵌入技巧来区分上面两种情况。

85 3.2.5 处理机分配算法举例 基于图论的确定性分配算法
假定：每个进程都知道 1）所需的处理机 2）所要求的内存 3）知道系统中任意一对进程间的平均通信量 若系统中处理机的数目k比进程数少，那系统中的一些处理机就必须被分配多个进程。 基于图论的确定性算法 保证在系统网络通信量最小的条件下对处理机进行分配。

86 基于图论的确定性分配算法 系统的带权图表示
系统的带权图表示： 系统可以被表示图G(V,E)， V中的每个节点表示一个进程 E中的每条边表示两个进程需要通信， 边上面的数字表示两个进程之间的通信量。 从数学角度看，处理机分配问题已经被简化为： 在一定的约束条件下（例如，每一个子图总的处理机和内存需求量不超过某一个阀值）将图分割成k个不相连的子图。 算法的目标就是在满足所有限制条件下，找到一个分割方法，使得分割后各子图之间的通信量之和最小。

87 基于图论的确定性分配算法 分割举例 下图表示了一个图的两种不同的分割方法，并得到了两个不同的通信量。 CPU1 CPU2 CPU3 CPU1

88 基于图论的确定性分配算法 分割举例 a中，系统图被分割为： 整个网络通信量 = 被虚线分割开的边上 的权值之和 = 30。
A,E,G在处理机1上 B,F,H在处理机2上 C,D,I在处理机3上 整个网络通信量 = 被虚线分割开的边上 的权值之和 = 30。 =17 =13

89 基于图论的确定性分配算法 分割举例 b中显示的分割得到的通信量之和为28
如果它满足所有对内存和处理机的限制，那它就是一个比较好的分割，因为它要求的 网络通信量之和较小。 =15 =13

90 3.2.5 处理机分配算法举例 集中式分配算法：up-down
图论算法的局限性在于： 需要预先知道所有信息，这在一般情况下是办不到的 下面介绍一个不需要预先知道所有信息的集中式启发式算法。 “上升-下降”(up-down)算法 Mutka and Livny在1987年提出的。

91 3.2.5 处理机分配算法举例 上升-下降算法的基本思想
上升-下降算法的基本思想是 1）由一个协调器来维护一张使用情况表 每个工作站在表中都对应着一项（初始值为零） 当发生一个重要事件时，就给协调器发送一个消息来更新使用情况表。 2）协调器根据使用情况表来分配处理机。 分配时机：调度事件发生时 典型的调度事件： 申请处理机 处理机进入空闲状态 发生时钟中断

92 3.2.5 处理机分配算法举例 上升-下降算法的目标 集中式分配算法的目标： 让每个工作站公平地使用系统处理机的计算能力,而不是尽可能地提高处理机的利用率。 原因： 其它算法有可能在给一个用户分配处理机时，为了让每一台处理机都繁忙起来而将所有处理机都分配给该用户。本集中式算法能够避免这种情况的发生。

93 3.2.5 处理机分配算法举例 上升-下降算法：新进程
当创建一个进程时，如果创建该进程的机器认为该进程应该在其它机器上运行，它就向协调器申请分配处理机。如果有可分配的处理机时，协调器就分配一个处理机，否则，协调器就暂时拒绝该处理机的申请，并记录这个请求。

94 3.2.5 处理机分配算法举例 上升-下降算法：罚分的变化
增加： 当一个工作站上的进程正在其它机器上运行时，它的罚分每秒钟增加一个固定值。这个罚分将加在使用情况表中该工作站所对应的项上。 减少情况1：每当工作站上的进程需要在其它机器上运行的请求被拒绝时，该工作站在使用情况表中所对应项上的罚分就会减少一个固定值。 减少情况2：当没有等待的处理机分配请求，并且处理机也未被使用时，使用情况表中该处理机所对应项上的罚分就会每秒钟减去一个值，直到为0。

95 3.2.5 处理机分配算法举例 上升-下降算法：罚分的取值
如图，由于罚分一会儿上升，一会儿下降，算法由此得名。 使用情况表中的罚分可以为正数、零和负数。 正数表示对应工作站上的 用户是在使用系统资源 负数表示该工作站需 要系统资源。 零表示介于两者之间。

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

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

98 3.2.5 处理机分配算法举例 层次分配算法 层次分配算法将所有处理机以一种与物理拓扑结构无关的方式组织成一个逻辑分层结构。这种逻辑分层结构与公司、军队、大学等现实世界中人的层次组成结构一样。例如，可以将一些机器看作为工人，而将另一些机器看作为工头。

99 3.2.5 处理机分配算法举例 层次分配算法 例如： 对于每一组k个教师来说，分配给一个系主任的任务是检查观察谁正忙碌，谁正空闲。 如果系统很大，那就需要更多的管理者。于是，有些机器将作为院长。每一个院长管理若干个系主任。 如果院长较多，则设置一个校长来管理院长。 这种层次关系可以进一步扩展下去，并且所需要的层次随着教师的数目成对数级增长。 由于每一个处理机只需要与一个上级和若干个下属进行通信，所以就可以对系统的信息流进行管理。

100 3.2.5 处理机分配算法举例 层次分配算法：崩溃的解决方法1
当一个系主任，或者更严重地，一个院长停止了工作（即崩溃了），系统将怎么办？ 一种方法就是 由崩溃院长所管辖的一个系主任来接替该院长职位 这个院长职位 1）可以由它下级选举产生 2）也可以由同级院长们选举产生 3）还可以由它的上级来任命。

101 3.2.5 处理机分配算法举例 层次分配算法：最高委员会
为了避免单个管理者在层次树的最顶层（造成系统不坚定），可以象下图那样 去掉树的根节点，最上层组成一个委员会来作为最高决策机构。 当委员会中的一个成员不工作了，其他人员将在下一层中选出某一个成员来代替。 院长委员会 院长 系主任 教师

102 3.2.5 处理机分配算法举例 层次分配算法：结构分析
结构分析： 可行性： 尽管这种层次结构并不是真正分布式的，但它却是可行的，并且实践证明它是一个较好的结构。 自重构性： 特别的是，这种系统可以自重构，并能够容忍被管理者或管理者的突发性崩溃，而不会产生任何长期的影响。

103 3.2.5 处理机分配算法举例 层次分配算法：处理器预定
算法中，一个处理机只能分配一个进程。 若一个作业产生S个进程，系统必须为它分配S个处理机。作业可以在层次树上的任何一层次上创建。每一个管理者跟踪并记录它辖区内有多少个处理机可用。 如果有足够的处理机可供使用，那它将预定R个处理机，但R≥S必须成立，因为这种估计不一定准确，有些机器可能已经关机。

104 3.2.5 处理机分配算法举例 层次分配算法：处理器预定
如果没有足够的处理机可供分配，那就把这个申请请求（逐级）向上传递，直到到达某个能够满足该请求的层次。在这一层次上，管理者把这个请求分解成多个申请并向下传递给下级的管理者，一直传递到树的底层。在最低层，被分配的处理机被标为“繁忙”，并把实际分配到的处理机数沿着树向上逐级报告。

105 3.2.5 处理机分配算法举例 层次分配算法：R的取值

106 3.2.5 处理机分配算法举例 超载者启动的分布式启发式算法
一个典型的分布式启发式算法： 超载者启动的分布式启发式算法 由Eager等人在1986年提出 算法描述： 当一个进程创建时，若创建该进程的机器发现自己超载，那就将询问消息发送给一个随机选择的机器，询问该机器的负载是否低于一个阀值。 1）如果是，那么该进程就被传送到该机器上去运行。 2）否则，就再随机地选择一台机器进行询问。 这个过程最多执行N次，若仍然找不到一台合适的机器，那么算法将终止，新创建的进程就在创建它的机器上运行。

107 3.2.5 处理机分配算法举例 算法分析 当整个系统负载很重的时候，
每一个机器都不断地向其他机器发送询问消息以便找到一台机器愿意接收外来的工作。 在这种情况下，所有机器的负载都很重，没有一台机器能够接收其它机器的工作，所以，大量的询问消息不仅毫无意义，而且还给系统增添了巨大的额外开销。

108 3.2.5 处理机分配算法举例 欠载者启动的分布式启发算法
在这个算法中，当一个进程结束时，系统就检查自己是否欠载。 如果是，它就随机地向一台机器发送询问消息。 如果被询问的机器也欠载，则再随机地向第二台、第三台机器发送询问消息。 如果连续N个询问之后仍然没有找到超载的机器，就暂时停止询问的发送，开始处理本地进程就绪队列中的一个等待进程，处理完毕后，再开始新一轮的询问。 如果既没有本地工作也没有外来的工作，这台机器就进入空闲状态。 在一定的时间间隔以后，它又开始随机地询问远程机器。

109 3.2.5 处理机分配算法举例 算法比较 与超载者启动的分布式启发式算法相比： 欠载者启动的算法不会在系统非常繁忙时给系统增加额外的负载。
而超载者启动的算法中，一台机器却在系统非常繁忙时发送大量的毫无意义的询问。

110 3.2.5 处理机分配算法举例 算法分析 在欠载者启动的分布式启发式算法中，
当系统繁忙时，一台机器欠载的可能性很小。即使有机器欠载，它也能很快地找到外来的工作。 在系统几乎无事可做时，算法会让每一台空闲机器都不间断地发送询问消息去寻找其它超载机器上的工作，造成大量的系统额外开销。 但是，在系统欠载时产生大量额外开销要比在系统过载时产生大量额外开销好得多。

111 3.2.5 处理机分配算法举例 超/欠载者启动的结合 可以将上述两种算法结合起来，让超载机器清除一些工作，而让欠载机器去寻找一些工作。
此外，系统中的机器可以通过保留以前的询问以及进行随机地询问来判断是否机器一直过载或欠载，这样可以提高系统性能。

112 3.2.5 处理机分配算法举例 拍卖算法 拍卖算法把分布式系统看作为一个小经济社会，由买卖双方和供求关系来决定服务的价格。进程为了完成自己的任务必须购买处理机时间，而处理机将它的处理机时间拍卖给出价最高的进程。 每一个处理机将自己估计的价格写入一个公共可读的文件中以此来进行拍卖。 价格并不是一直不变的，初始的价格只是表示所提供服务的近似价格（一般，它是以前最后一个买主出的价格） 根据处理机的运算速度、内存大小、浮点运算能力以及其它一些特性来确定每一个处理机的价格。 处理器提供的服务（例如，预计的响应时间）也要公布出来

113 3.2.5 处理机分配算法举例 拍卖算法 当一个进程要启动一个子进程时，
1）查询公共可读文件看有谁能够提供它所需要的服务。 2）确定一个它可以付得起钱的处理机集合。通过计算从这个集合中选出一个最好的处理机。最好的标准是最便宜、速度最快或者性能价格比最高。 3）给第一个选中的处理机发送一个出价信息，这个出价有可能高于或低于处理机公布的价格。

114 3.2.5 处理机分配算法举例 拍卖算法 处理机 1）收集所有发送给它的出价信息 2）选择一个出价最高的进程并将通知发送给选中的进程和未选中的进程。 3）开始执行被选中的进程。 此时，公共可读文件中该处理机的价格将被更新以便反映处理机当前最新的价格。

115 3.2.5 处理机分配算法举例 拍卖算法：问题 Ferguson等人在1988年提出了这个拍卖算法。但他们并未考虑实现细节。该算法所引起的问题是： 进程从哪里获得钱来购买处理机？ 它们有稳定的工资收入吗？ 每个进程的月薪都相同吗？还是有些进程的工资高有些进程的工资低呢？ 如果用户数量增加而系统未增加相应的一些资源，那么，会不会造成系统通货膨胀？ 处理机之间会不会形成同盟来漫天要价敲进程的竹杠？ 进程联合工会是否允许这样做呢？ 使用磁盘是否也要收费？激光打印机是否收费更高？ 等等。