《高级操作系统AdvancedOperatingSystem011》由会员分享，可在线阅读，更多相关《高级操作系统AdvancedOperatingSystem011（121页珍藏版）》请在金锄头文库上搜索。
1、高级操作系统高级操作系统Advanced Operating System陈香兰（代）0551-3606864-83中国科学技术大学计算机系第五章第五章 分布式进程和处理机管理分布式进程和处理机管理l分布式系统模型l分布式处理机分配算法l分布式进程调度l分布式系统容错l实时分布式系统上次课主要内容上次课主要内容l5.1 分布式系统模型l工作站模型l怎样找到一个空闲工作站 服务器端驱动的算法客户端驱动的算法 l怎样透明地运行一个远程进程如何设置远程运行环境 l如果空闲工作站的主人回来重新使用它，怎么办？继续/强制取消/进程迁移 l处理机池模型l用排队论来描述和分析处理机池模型的性能l混合模型 5
2、.2 分布式处理机分配算法分布式处理机分配算法l分布式系统包括多个处理机，具有较大的处理能力。l另外，一个作业将产生多个任务或进程，它们需要分配在多个处理机上并行执行，以充分利用分布式系统提供的巨大的处理能力。l因此，分布式系统需要一个优良的资源分配算法来决定每个进程或任务应分配到哪一个处理机上执行l通常，这个算法被称为处理机分配算法或任务分配算法或负载分配算法（通常不称作进程分配算法，尽管但两者的意思完全相同）5.2.1 分配模型分配模型l首先介绍一下处理机分配的基本模型、假定和目标：1）关于处理器：l假定所有的机器都是相同的，至少是代码兼容的，不同的只是运行速度。l一些分配模型还假定系统具
3、有多个互不相关的处理机池，每一个处理机池都是相同的。5.2.1 分配模型分配模型2）关于互连拓扑：l假定系统是完全互连的，即每一个处理机都可以与其它任意一个处理机相连接。l这并不表示每一个机器与其它任意一台机器之间都有线路连接，这个假定只是意味着每一对机器都可以互相通信。至于消息是如何从一台机器到达另一台机器的问题只是低层通信软件的事，处理机分配算法无需考虑。但有一些处理机分配算法利用了网络的广播或者多播的特性。5.2.1 分配模型分配模型新进程的产生和处理机的分配新进程的产生和处理机的分配l当一个运行中的进程决定创建一个子进程时，新的工作随之产生。l在有些情况下，创建进程是由系统的命令解释程
4、序（即shell）来完成的。它为用户指定的命令而执行该命令所对应的程序。l而在另一些情况下，用户进程本身也可以创建一个或者多个子进程，以获得较高的系统性能。l对新进程必须考虑分配到哪个处理器上运行5.2.1 分配模型分配模型处理机的分配策略处理机的分配策略l处理机分配策略可以分为两大类：1）非迁移的2）可迁移的l第一类是非迁移的（nonmigratory）l在非迁移策略中，当创建一个进程时，系统就决定它被分配到哪台处理机上。一旦一个进程被分配到一台机器上，那么，它就在那台机器上运行，一直到终止，不管这台处理机的负载是多么的重，而别的处理机是多么的空闲，它都不能迁移到别的处理机上运行。5.2.1
5、 分配模型分配模型处理机的分配策略处理机的分配策略l第二类是可迁移的（migratory）l对于可迁移策略来说，一个进程即使已经被分配到一台处理机上并已经运行了一段时间，它也可以动态地迁移到其它轻负载的处理机上继续运行。l虽然可迁移策略可以使系统达到良好的负载平衡，但实现起来却异常复杂。5.2.1 分配模型分配模型分配算法的分配算法的优化优化l处理机分配算法必须尽可能优化。否则，我们完全可以随机地或按数字顺序来分配处理机。l不同系统的优化内容是不一样的l优化目标1：提高处理机利用率l优化目标2：最小化平均响应时间5.2.1 分配模型分配模型优化目标优化目标1：提高处理机利用率：提高处理机利用率
6、l通常的一个优化目标就是：尽量提高处理机的利用率l让处理机在每个小时内执行用户工作的周期数尽可能地大l换句话说，要尽量减少空闲处理机周期数。5.2.1 分配模型分配模型优化目标优化目标2：最小化平均响应时间：最小化平均响应时间l另一个有价值的优化目标就是：使平均响应时间最小化5.2.1 分配模型分配模型平均响应时间举例平均响应时间举例l假设有两个处理机。处理机1以10MIPS的速度运行，处理机2以100MIPS的速度运行，其中等待队列中的进程需要5秒才能完成。l有两个进程。进程A有1亿条指令，执行时间分别为10秒（在处理机1上）和1秒（在处理机2上）进程B有3亿条指令，执行时间分别为30秒和3
7、秒5.2.1 分配模型分配模型平均响应时间举例平均响应时间举例l这两个进程在每一个处理机上的响应时间（包括等待时间）如图所示。5+1 =5+3 =5.2.1 分配模型分配模型平均响应时间举例平均响应时间举例l平均响应时间l如果把进程A和B分别分配给处理机1和2，那么平均响应时间是(10+8)/2=9秒。l若反向分配，那么平均响应时间就是(30+6)/2=18秒。l显然，前者的平均响应时间要比后者小。5.2.1 分配模型分配模型最小响应时间的另一种形式最小响应时间的另一种形式l最小响应时间的另一种形式就是最小响应率。l响应率定义为：在一台机器上运行一个进程所需的时间除以该进程在无负载的标准处理机
8、上运行所需的时间。l对于大多数用户，响应率比响应时间更重要。原因在于：响应率考虑了大任务要比小任务花费更多时间这一情况。例如：l一个1秒的任务花了5秒，而一个1分钟的任务花了70秒，从响应时间上看，前者好，但从响应率上看，后者更好，因为5/170/60。 5.2.2 分配算法的分类分配算法的分类l负载分配方法可做如下分类：l局部和全局 局部负载分配局部负载分配处理单个处理器上的进程对时间片（单元）的分配。全局负载分配全局负载分配首先进行进程对处理器的分配，然后完成每个处理器内这些进程的局部调度表 l静态和动态（在全局类中） 静态负载分配静态负载分配中，进程对处理器的分配是在进程执行以前的编译阶
9、段完成的，而动态负载分配动态负载分配要到进程在系统中执行时才做出分配。静态方法又叫做确定性调度，而动态方法叫做负载平衡。 5.2.2 分配算法的分类分配算法的分类l最优和次优（在静态和动态两种类型中） 如果根据某种标准（例如，最小执行时间和最大系统输出）可以取得最优分配最优分配，那么就可以认为这种负载分配方法是最优的。一般地，负载分配问题是NP完全问题。某些情况下，次优方案次优方案也是可以接受的。l有四类算法（对于最优的和次优的）被使用：1）解空间枚举搜索、2）图模型、3）数学编程（例如0/1编程）4）队列模型5.2.2 分配算法的分类分配算法的分类l近似和启发式（在次优类型中） 在近似方法近
10、似方法中，负载分配算法仅搜索一个解空间的子集，当寻找到一个好的解时，终止执行在启发式方法启发式方法中，调度算法使用某些特殊参数，能够近似地对真实系统建模。 5.2.2 分配算法的分类分配算法的分类l集中控制的和分散控制的（在动态类型中） 在分散控制中，决策工作被分配给不同的处理器。在集中控制中，决策工作由一个处理器完成l协作的和非协作的（对分散控制） 动态负载分配机制可以分成：协作的（分布式对象间有协同操作）和非协作的（处理器独立做出决策）5.2.2 分配算法的分类分配算法的分类l下图显示了上述负载分配算法的分类情况5.2.2 分配算法的分类分配算法的分类l还有其他负载分配算法的分类方法，包括
11、一些不能直接归入上面分类的负载分配类型：l单个和多个应用程序 多数负载分配算法是针对单个应用程序。多应用程序情况可以转换成单个应用程序情况多应用程序情况可以转换成单个应用程序情况。例如，应用图模型时对多应用程序的多个图可以认为是一张图。然而，多应用程序情况下的进程分配远复杂于单个应用程序的情况。l多应用程序情况下用平均子图完成时间作为衡量指标，单个应用程序情况下用最小完成时间作为衡量指标。 5.2.2 分配算法的分类分配算法的分类l非抢占式的和抢占式的 对非抢占式非抢占式的负载分配算法，一个任务（进程）开始执行后就不能中断。在抢占式抢占式负载分配算法中，进程可以中断，并从处理器上移走，过后继续
12、执行 l非自适应的和自适应的 非自适应非自适应负载分配只使用一种负载分配算法，不会依据系统反馈而改变白己的行为。自适应自适应负载分配能够根据系统反馈调整分配算法。典型地，一个自适应负载分配算法是许多负载分配算法的集合，依据系统的各种参数来选择一个合适的算法。5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题l一般来说，设计者在设计算法时，需要考虑以下五个方面的情况：l算法是确定式还是启发式的。l算法是集中式的还是分布式的。l算法是最优的还是次优的。l算法是局部的还是全局的。l算法是过载者启动的还是欠载者启动的。5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题设计问题设计问
13、题1：确定还是启发式：确定还是启发式l确定式算法需要预先知道进程所有的信息。l一般，进程的信息包括：l进程的计算需求l文件需求l通讯需求等等l如果设计者能够获得所有进程的信息，那就可以设计出一个完美的分配方案，并获得最佳的分配结果。l但只有极少的一些系统可以事先获得所有进程的信息5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题可预测系统可预测系统 vs 不可预测系统不可预测系统l在可预测系统中，可以通过合理的近似来事先得到所有进程的信息。例如，在银行业、保险业、民航定票系统中，每天的情况都基本相似，民航根据经验可以预测到早春第一周周一的清晨大约有多少人要从天津去北京，这样就保证了确
14、定式算法的可行性。l与可预测系统相反，有些系统的负载是完全无法预测的。用户所做的工作每一个小时，甚至每一分钟都在动态地改变。在这种系统中的处理机分配不能用一种在数学上确定的算法实现，而需要使用一种称之为启发式的算法。 5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题设计问题设计问题2：集中还是分布：集中还是分布l集中式算法需要将系统中所有的信息都收集到某个机器上，这会造成系统不够坚定，并且该机器负载过于沉重。因此，一般都采用分布式算法来实现处理机分配。然而，一些集中式算法仍然被采用，原因是没有相应的分布式算法来取代它。5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题设计
15、问题设计问题3：最优还是次优：最优还是次优l第三个设计问题与前两个问题有关，是获得一个最优解？还是一个可行的次优解？l一般来说，采用集中式和分布式算法都能够得到最优解，但得到最优解所花费的代价要比得到次优解复杂得多。l此外，最优解需要收集更多的信息以及进行全面复杂的处理。l对于大多数分布式系统来说，只要有一个启发、分布、次优的处理机分配算法就可以了。因为，要获得最优解实在是太难了。 5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题设计问题设计问题4：迁移策略：迁移策略l第四个设计问题与迁移策略有关。l当一个新进程被创建时，系统需要决定它是否在创建它的机器上运行。若该机器繁忙，那这个
16、新进程就必须迁移到其它机器上去运行。l对于是根据本机局部信息还是全局信息来决定新进程是否迁移，目前存在着两种学派。1）一种学派主张简单的局部算法：若机器的负载低于某个阀值，那新进程就在本地机器上运行；否则，就不允许该进程在本地上运行。2）另一种学派认为局部算法太武断了。最好在决定新进程是否在本地机器上执行之前，先收集其它一些机器上的负载信息，称为全局算法。l比较：局部算法简单，但远远达不到最优；而全局算法需要付出巨大的代价来换取一个性能稍微好一点的结果。5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题设计问题设计问题5：l最后一个设计问题与迁移的目的机器有关。l一旦决定不允许一个进
17、程在本地机器上运行，那么，迁移算法就必须决定将该进程应该迁移到哪台目的机器上。显然，迁移算法不能是本地的。它需要通过获得其它机器上的负载信息来决定迁移的目的机器。这些负载信息可以通过两种途径来获得。l一种是过载者启动的，l另一种是欠载者启动的。 5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题设计问题设计问题5：l过载者启动：由过载者来寻找迁移的目的机器l如图：一个机器超载时，它向其它机器发送求助请求，希望将自己的一些新进程迁移到其它机器上运行。l欠载者启动：l当一个机器处于空闲状态即欠载状态时，由这台欠载机器来宣布自己可以接收外来的工作。其的目的就是寻找一台可以给自己增加一些额外
18、工作的机器 5.2.3 处理机分配算法的设计问题处理机分配算法的设计问题设计问题设计问题5：l不管是过载者启动的算法还是欠载者启动的算法，不同的算法采用不同的策略来决定谁收集信息、收集时间多长以及如何处理收集的信息。 5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题问题问题1：负载的度量：负载的度量l基本上，所有的算法都假定每一台机器都知道它自己的负载，也就是说，它可以判断自己是超载还是欠载，并且能够告诉其它机器自己的负载。l然而，度量一台机器是否超载并不象它看上去那样简单。5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题度量方法度量方法 1l度量方法1：以机器上的进程
19、数量作为机器的负载l优点：简单原因：只需要计算机器上的进程数量l缺点：用进程数量的多少来表示机器的负载是不确切的，它几乎说明不了什么问题。 原因：即使在一台空闲机器上，仍然会有一些后台监视进程在运行，例如，邮件、新闻、守护进程、窗口管理程序以及其它一些进程。因此，5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题度量方法度量方法2l对度量方法1进行如下改进：只计算正在运行或已经就绪进程的数量。原因：l每一个正在运行或处于就绪状态的进程都会给系统增加一定的负载，即便它是一个后台进程。存在的问题：l许多后台守护进程只是定时被唤醒，检查所感兴趣的事件是否发生，如果没有，则重新进入睡眠状态。
20、因此，这类进程只给系统带来很小的负载。 5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题度量方法度量方法3l直接使用处理机利用率：就是处理机繁忙时间在全部时间中（繁忙时间+空闲时间）所占的比例。l一个利用率为20%的处理机负载要比利用率为10%的处理机大l优点：比较合理原因：兼顾了用户进程和守护进程5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题测量手段测量手段l测量手段：设置一个定时器，它周期地中断处理机，每次都检查处理机的状态。并按照上述公式计算处理机利用率l存在的问题：使用定时器中断所产生的一个问题就是当处理机内核正在执行原语时，它屏蔽了包括定时器中断在内的所有中
21、断。当原语执行时发生定时器中断，中断就会在原语执行完毕才能得到响应。如果该原语正阻塞前一个活动进程，那么，计算出的处理机利用率就会比实际情况要低。 5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题实现问题实现问题2：额外开销：额外开销l许多理论上的处理机分配算法都忽略了收集负载信息以及传送进程的额外开销。l若一个算法将一个新创建的进程传送到远程机器上运行仅使系统性能提高10%左右，那它最好不要这样做，原因是传送进程的开销足以抵消所提高的性能。l一个好的算法应该考虑算法本身所消耗的处理机时间、内存使用、以及网络带宽等。但很少有算法能做到这一点，因为它太难了。 5.2.4 处理机分配算
22、法的实现问题处理机分配算法的实现问题问题问题3：复杂性：复杂性l在处理机分配算法实现中还必须考虑复杂性。l事实上，所有的研究者只分析、模拟或计算处理机的利用率、网络的使用情况以及响应时间，以此来衡量他们所提出算法的好坏。l很少有人考虑软件的复杂性对系统的性能、正确性和坚固性所产生的影响。很少有人考虑复杂性。也很少有人发表一个新算法，也不会有人提出了一个新算法并宣称它的性能有多么好，然后，得出结论说这个算法不值得使用，因为它的算法性能有可能只是比现有的算法稍好一点，却在实现上却复杂得多。 5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题l然而，Eager 等人在1986年所做的研究使
23、追求复杂和最优的人们看到了希望。他们研究了三个算法。在这三个算法中，所有的机器都测量自己的负载以判断它是否超载。当一个新进程创建时，创建该进程的机器就会检查自己是否超载，如果是，则它就寻找一台欠载的远程机器去运行该进程。这三个算法的不同之处在于寻找远程机器的方法。 5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题l算法1随机地选择一台机器，并把新创建的进程传送到该机器上。如果该接收机器本身也超载，它也同样随机地选择一台机器并把该进程传送过去。这个过程一直持续到有一台欠载的机器接收它为止，或者指定计数器溢出停止该进程的传送 机器1机器2机器3机器n机器k5.2.4 处理机分配算法的实
24、现问题处理机分配算法的实现问题l算法2：随机地选择一台机器，发送一个信息给该机器询问它是超载/欠载。若欠载，它就接收新进程；否则，新进程的创建机器继续随机地选择一台机器并向其它发送一个询问消息。这个过程一直持续到找到一台欠载机器为止，或超过了一定的询问次数，若找不到欠载机器，新进程就只好留在本地机器上运行。 机器1机器2机器3机器n机器k5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题l算法3给k台机器发送询问消息，接收这k台回送的负载消息。这个新进程将发送给负载最小的机器，并在它上面运行。机器1机器2机器3机器n机器k5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题l
25、显然，如果我们不考虑所有发送询问负载消息和传送进程的额外开销，那么，人们会认为算法3的性能最好。事实上也确实如此。尽管算法3的性能只比算法2的性能稍好一点，但其复杂性以及额外开销却比算法2要大的多。lEager等人认为，如果一个简单算法只比复杂算法在性能上略低一点的话，那么，最好使用简单算法。5.2.4 处理机分配算法的实现问题处理机分配算法的实现问题实现问题实现问题4：稳定性：稳定性l最后一个实现问题就是稳定性。由于不同的机器都在异步地运行各自的计算，所以，整个系统的负载很少能够达到平衡。因此，有时候会发生这样一种情况：在某个时刻，机器A得到的信息是机器B的负载较轻，因而，它就将新创建的进程
26、传送给机器B。机器B在收到该进程之前负载又增加了，所以，收到该进程后，它发现机器A的负载较轻，于是，它就将该进程又传送给机器A。这样造成了某个可怜的进程被来回传送的情况。原因是，每一个机器上的负载每时每刻都在变化。 5.2.5 处理机分配算法举例处理机分配算法举例l为了进一步加深对处理机分配的理解，在本节中我们将讨论几个不同的算法。尽管这些算法已经包括了大部分处理机分配算法的类型，但是仍然有一些类型未提及到。5.2.5 处理机分配算法举例处理机分配算法举例静态负载分配静态负载分配l静态分配算法根据系统的先验知识做出决策l运行时负载不能够重新分配。l算法目标：调度一个任务集合，使它们在各个目标P
27、E上有最小的执行时间。l设计算法时的三个主要的因素：l处理器互连l任务划分（粒度决策）l任务分配5.2.5 处理机分配算法举例处理机分配算法举例静态负载分配静态负载分配l静态分配问题即便在简单地对计算开销和通信开销做某种假设以后，依然是一个NP完全问题。l因此，通常利用数学工具如图、启发式规则来得到次优的解l通常，用图模型表示任务和PE 结构l可以用任务优先图或者任务交互作用图对任务集合建模。静态负载分配静态负载分配任务优先图任务优先图l任务优先图又称为有向无环图（DAG） 如图，l每个链接：定义任务间的优先关系l节点上的标记：表示任务执行时间l链接上的标记：表示任务完成后启动后续任务所需的时
28、间间隔静态负载分配静态负载分配任务交互作用图任务交互作用图l任务交互作用图如图：l链接：定义两个任务间的相互关系l每个链接赋予一对数：表示这两个任务在同一个PE 上时的通信开销和在不同PE 上时的通信开销 静态负载分配静态负载分配任务划分任务划分 l任务划分的粒度：一个给定任务划分的粒度定义是任务分解中影响通信开销的所有单元的平均尺度。根据数据单元的大小，算法可以分成l细粒度：数据单元小l粗粒度：数据单元大l中粒度：介于上述两者之间l粒度的大小：1）若太大，会降低并行度，因为潜在的并行任务可能被划分进同一个任务而分配给一个处理器。2）若太小，进程切换和通信的开销就会增加。 静态负载分配静态负载
29、分配任务划分任务划分l任务划分的一个主要目标：尽可能消除处理器间通信引起的开销。可以使用三种方法： 1、水平或者垂直划分。主要思想是在给定的任务优先图中垂直或者水平划分。关键路径（最长路径）的概念常常在垂直划分中使用。水平划分把给定的任务分成若干层，任务的优先级由它们所在的层次决定 静态负载分配静态负载分配任务划分任务划分2、通信延迟最小划分。主要思想是把通信频繁的节点归成一类。然而，这些需要通信的任务分配在一个处理器上会丧失任务间的并发性。有的研究者认为：如果减小通信延迟的好处抵销了并行任务串行化的损失，就采用通信延迟最小划分。可以把一个划分问题转换成一个网络流问题，将在后面的小节中讨论。
30、静态负载分配静态负载分配任务划分任务划分3、任务复制。这是任务划分的一个可选方法。主要思想是通过在PE上复制任务来降低通信开销。这个方法保留了任务原有的并行性；但是存储空间要求和同步开销增加了。可以利用任务复制来达到容错性，可以实现无错调度以保证处理器出现错误时最后计算结果正确。静态负载分配静态负载分配任务划分任务划分l有时，任务划分被称做任务聚类，以强调在给定的图模型中对小任务分类。任务划分把图当做一个整体，划分成不同的类（颗粒）。不论任务划分还是任务聚类，都生成一个颗粒集合。通常颗粒的数目等于处理器的个数，以此简化下一步的任务分配程序。 静态负载分配静态负载分配任务分配任务分配 l任务分配
31、就是在给定了互连网络的并行系统或者分布式系统中分配颗粒（颗粒是任务划分的结果）。l若任务图和处理器图的节点数目都是n ，那么就有n!种不同的分配方法把任务图Gt里的节点分配到处理器图Gp的节点上。l通常把每种方法称做Gt到Gp的一个映射。l在总执行时间概念下，有些映射比较好。静态负载分配静态负载分配任务分配任务分配l下面是关于Gp的典型假设： l存储器容量无限。l每个PE 有相同的处理能力。 l忽略网络拥塞，虽然通信进程间的距离是影响通信延迟的因素。 l注意，任务调度不必要一定分任务划分和任务分配两个步骤做。分两步的方法只是为了简化原本是NP完全的调度过程。 一、一、基于任务优先图的任务调度基
32、于任务优先图的任务调度l假定一个进程集合P=P1, P2, P3, Pn，在一系列同样的处理器上执行。l任务优先图：定义P上的偏序关系，构成(P, )关系集，并用G=(V, A)描述，其中，lV是顶点的集合，表示进程集；lA是弧集合，表示进程间的优先关系。lA中的一个链接表示为(u, v), u和v是V中的两个连接进程（节点）。基于任务优先图的任务调度基于任务优先图的任务调度l对每个节点和链接都定义有代价函数w。lW(u)(0, )是节点u的代价，u属于V; lW(u, v)=(l, l )是链接(u, v)的代价，其中l ：同一处理器内的通信代价（若u和v被分配在同一个处理器上）l：处理器间
33、的通信代价（若u和v被分配在不同处理器上）。 基于任务优先图的任务调度基于任务优先图的任务调度关于处理器互连关于处理器互连l任务优先关系图模型中不考虑处理器互连l假设每对处理器间的通信延迟是一个固定数值l事实上，处理器通信延迟在l中得到了体现。l通常，处理器内部通信代价l 相对于处理器间通信代价l 要小。因此可以忽略，记做W(u, v)=l。 基于任务优先图的任务调度基于任务优先图的任务调度任务分配的描述任务分配的描述l甘特图能够最有效描述进程对处理器的分配情况。l甘特图以处理器为纵坐标，时间为横坐标。图中的每个方块表示进程在某个系统中的开始时间，持续时间和结束时间。处理器内的时问延迟和处理器
34、间的时间延迟都能够在图中体现。 基于任务优先图的任务调度基于任务优先图的任务调度举例举例l图a显示了一个实例的任务优先图l圆圈中的数对应任务的执行时间l与每个链接相关的数对应于处理器间的通信时间（延迟）。两个连接任务分配在不同的处理器上时就会发生通信延迟l例如，W(T1)=2和W(T1,T2)=1表示T1的执行时间是2, T1和T2间处理器间的通信代价是1 （没有给出处理器内的通信代价）。l图b是对处理器P1, P2的一个调度结果。l本例中，两个处理器间的通信发生在有1个单位通信延迟的T2T4和有2 个单位通信延迟的T4T5。总的执行时间是12 。 (a)(b)l通信延迟使调度算法大大地变复杂
35、。l例：图b, c, d给出了针对a中任务优先图的三种不同的调度l对于c和d，若通信延迟d大于T2的执行时间，图c的调度就比图d 要好。可以说，若通信延迟太大的话，所有任务分配在一个处理器上是比较合适的。 基于任务优先图的任务调度基于任务优先图的任务调度通信延迟的影响通信延迟的影响(a)(b)(c)(d)？(a)(b)(c)(d)基于任务优先图的任务调度基于任务优先图的任务调度通信延迟的影响通信延迟的影响l通常总是尝试尽量增加并行度，同时尽可能降低通信延迟。然而在多数时间这两个目标是互相矛盾的。因此需要某种程度折衷。有时可以使用任务复制的方法减少通信需求。显然，由于通过任务复制而避免了处理器间
36、的通信，图b的结果是最好的。基于任务优先图的任务调度基于任务优先图的任务调度线性与非线性调度线性与非线性调度l前面提到了任务划分（又称做任务聚类）中的粒度问题，是把指定应用程序的任务分成一个个任务类。l通常类的数目应等于处理器个数l若至少有一个类中包含两个独立的任务，则分类是非线性非线性的；否则，分类就是线线性性的。l右图分别是三个进程的线性调度和非线性调度，进程2和进程3是两个独立的任务。基于任务优先图的任务调度基于任务优先图的任务调度粒度的定义粒度的定义l一个任务优先图可以认为是许多分叉和合并操作的集合，如右图所示l为了判别好的分类算法，引入了对每个分叉或者合并的粒度的概念。l右图中，分叉
37、x（合并x）的粒度是：=最小的进程代价与最大的连接代价的比值l给定任务优先图G 的粒度是：基于任务优先图的任务调度基于任务优先图的任务调度粒度的定义粒度的定义l如果合并或分叉x（或图G）就是粗粒度的；否则，就是细粒度的。l上例中的任务划分是粗粒度，因为最小的进程代价大于最大的连接代价(g(x)=2/1=2)。基于任务优先图的任务调度基于任务优先图的任务调度线性分类与非线性分类的比较线性分类与非线性分类的比较l例中图a的线性分类的执行时间是7。图b中非线性分类的执行时间是9。基于任务优先图的任务调度基于任务优先图的任务调度线性分类与非线性分类的比较线性分类与非线性分类的比较l如果把W(T1, T
38、3)和W(T1, T2)改成4，相应的图变成细粒度分叉，非线性分类的执行时间是9，优于执行时间是10的线性分类。 基于任务优先图的任务调度基于任务优先图的任务调度算法实例：两种最优调度算法算法实例：两种最优调度算法 l下面介绍两种有约束的调度问题，它们有多项式时间的执行复杂度。l两种方法都假设通信代价可以忽略和优先图中每个节点的执行时间是一样的（一个时间单元）。l具体限制如下： l在第一个有约束的调度问题中，优先图是一棵树。 l在第二个有约束的调度问题中，只有两个处理器可用l两种调度算法都是最高优先级优先的方法，也就是说，通过节点的等级（优先级）来选择节点。 基于任务优先图的任务调度基于任务优
39、先图的任务调度算法案例算法案例1：优先级定义：优先级定义l案例1中节点u的等级是它到根节点的距离加1l注意：节点的等级越高，它的优先级就越高。l当若干个节点有相同的等级时，所有先导节点都已执行的节点被第一个选中；如果还有若干个节点符合上述条件，则做随机选择。 算法案例算法案例1：优先图举例优先图举例l右图显示了一个树结构的优先图T1, T2, T3和T4 在等级5T5, T6和T7在等级4 T8和T9在等级3T10, T11和T12在等级2 T13在等级1l等级5的任务有最高优先级，等级1的任务优先级最低。同一等级的任务有相同优先级。算法案例算法案例1：任务分配举例任务分配举例l上例在三个处理
40、器上的最优调度，如右下图所示l从第一个时间槽开始根据优先级进行分配。l有先后关系的任务不能分配在同一个时间槽中。l例如T6必须被分配在T4后面的时间槽中。 T=1T=2T=3T=4T=5T=6算法案例算法案例1：分配算法的实现：就绪队列定义分配算法的实现：就绪队列定义l就绪队列被用来高效的实现上述调度算法l就绪队列包括所有节点，它们的先导节点都已经执行完毕l根据优先级从就绪队列中选择后续节点执行。l注意，一个节点被调度时，就绪队列就必须更新。算法案例算法案例1：就绪队列举例：就绪队列举例：l图9-8 中， 为方便起见，队列中的任务按优先级排序1.初始就绪队列是T1,T2,T3,T4,T5,T7
41、,T9,T10,T12 队列中的前三个任务分配在第一个时间槽2.就绪队列变成T4,T5,T7,T9,T10,T12。T4,T5和T7分配在时间槽2 算法案例算法案例1：就绪队列举例：就绪队列举例：3.T6加入就绪队列T6,T9,T10,T12。再将队列中前三个任务分配给下一个时间槽4.就绪队列变为T8,T12。T8和T12都分配在时间槽4 ，5.T11加入就绪队列。T11分配在时间槽5，6.T13加入就绪队列，并在时间槽6 执行。 基于任务优先图的任务调度基于任务优先图的任务调度案例案例2：优先级定义：优先级定义l案例2假定有两个处理器。优先图中不同节点的等级不相同。下面的算法生成一个优先图：
42、l假定有k个终止节点（无后续节点），从1到k依次标记这些节点。l令S是未被标记的节点的集合，并且其中每个节点的后续节点都已被标记，从中选一个标记成i。方法如下：l令lex(u)是u的所有直接后续节点的标记的升序排列。若对S中所有u(uu), lex(u)lex(u) （字典序），那么u可以赋予i 。案例案例2：优先图举例优先图举例l右图表示一个优先图，每个节点都用上面的方法进行了标记。节点的标记可以当做它的优先级l任务按照优先级升序排序为：T1,T2,T3,T4,T5,T6,T11, T8,T7, T10,T9 l注意：终止任务T1,T2,T3的顺序是随机选择的，例中它们的优先级分别是1,2,
43、3T4的直接后续节点是T1和T2，因此lex(T4)=(1, 2)。显然lex(T4) Iex(T5)所以T4的标记是4 ，T5的标记是5 。 案例案例2：任务分配举例任务分配举例l图9-6b 是甘特图表示的最优调度。 二、基于任务相互关系图的任务调度二、基于任务相互关系图的任务调度任务图定义任务图定义 l第二个任务调度模型是利用任务相互关系图和进程的集合来表示应用程序。l任务相互关系图由无向图Gt(Vt, Et)表示Vt：是进程的集合Et：是边的集合， 其中每条边表示两个通信进程间的相互作用关系，用相关两个进程的通信代价标记（不是优先关系）基于任务相互关系图的任务调度基于任务相互关系图的任务
44、调度处理器图定义处理器图定义l与任务优先图模型不同之处是处理器间通信在任务相互关系图调度模型中有重要作用。l处理器图由Gp(Vp, Ep)表示顶点集Vp中每个元素是一个处理器边集Ep中每个元素是一个通信信道l一般来说，|Vt|2)，lb）两个通信进程被映射到两个处理器上，这两个处理器在处理器图中的距离是2 。l需要图嵌入技巧来区分上面两种情况。 5.2.5 处理机分配算法举例处理机分配算法举例三、三、基于图论的确定性分配算法基于图论的确定性分配算法 l假定：每个进程都知道1）所需的处理机2）所要求的内存3）知道系统中任意一对进程间的平均通信量若系统中处理机的数目k比进程数少，那系统中的一些处理
45、机就必须被分配多个进程l基于图论的确定性算法基于图论的确定性算法保证在系统网络通信量最小的条件下对处理机进行分配。基于图论的确定性分配算法基于图论的确定性分配算法系统的带权图表示系统的带权图表示l系统的带权图表示：系统可以被表示图G(V,E)，V中的每个节点表示一个进程E中的每条边表示两个进程需要通信， 边上面的数字表示两个进程之间的通信量。l从数学角度看，处理机分配问题已经被简化为：在一定的约束条件下（例如，每一个子图总的处理机和内存需求量不超过某一个阀值）将图分割成k个不相连的子图。算法的目标就是在满足所有限制条件下，找到一个分割方法，使得分割后各子图之间的通信量之和最小。基于图论的确定性
46、分配算法基于图论的确定性分配算法分割举例分割举例l下图表示了一个图的两种不同的分割方法，并得到了两个不同的通信量。CPU1CPU2CPU3CPU1CPU2CPU3基于图论的确定性分配算法基于图论的确定性分配算法分割举例分割举例a中，系统图被分割为：A,E,G在处理机1上B,F,H在处理机2上C,D,I在处理机3上整个网络通信量=被虚线分割开的边上的权值之和=30。3+2+4+4=132+8+5+2=17基于图论的确定性分配算法基于图论的确定性分配算法分割举例分割举例l在图b中显示的分割得到的通信量之和为28l如果它满足所有对内存和处理机的限制，那它就是一个比较好的分割，因为它要求的网络通信量之
47、和较小。3+2+4+4=133+5+5+2=155.2.5 处理机分配算法举例处理机分配算法举例四、集中式分配算法：四、集中式分配算法：up-down l图论算法的局限性在于：需要预先知道所有信息，这在一般情况下是办不到的l下面介绍一个不需要预先知道所有信息的集中式启发式算法。l“上升-下降”(up-down)算法Mutka and Livny在1987年提出的。5.2.5 处理机分配算法举例处理机分配算法举例上升上升-下降算法的下降算法的基本思想基本思想l上升-下降算法的基本思想是1）由一个协调器协调器来维护一张使用情况表使用情况表l每个工作站在表中都对应着一项（初始值为零）l当发生一个重要
48、事件时，就给协调器发送一个消息来更新更新使用情况表。2）协调器根据使用情况表来分配处理机。l分配时机：调度事件发生时l典型的调度事件：l申请处理机处理机进入空闲状态发生时钟中断 5.2.5 处理机分配算法举例处理机分配算法举例上升上升-下降算法的目标下降算法的目标l集中式分配算法的目标：让每个工作站公平地使用系统处理机的计算能力，而不是尽可能地提高处理机的利用率。原因：其它算法有可能在给一个用户分配处理机时，为了让每一台处理机都繁忙起来而将所有处理机都分配给该用户。本集中式算法能够避免这种情况的发生。 5.2.5 处理机分配算法举例处理机分配算法举例上升上升-下降算法：新进程下降算法：新进程l
49、当创建一个进程时，如果创建该进程的机器认为该进程应该在其它机器上运行，它就向协调器申请分配处理机。1）如果有可分配的处理机时，协调器就分配一个处理机；2）否则，协调器就暂时拒绝该处理机的申请，并记录这个请求。5.2.5 处理机分配算法举例处理机分配算法举例上升上升-下降算法：下降算法：罚分的变化罚分的变化l增加：当一个工作站上的进程正在其它机器上运行时，它的罚分每秒钟增加一个固定值。这个罚分将加在使用情况表中该工作站所对应的项上。l减少情况1：每当工作站上的进程需要在其它机器上运行的请求被拒绝时，该工作站在使用情况表中所对应项上的罚分就会减少一个固定值。l减少情况2：当没有等待的处理机分配请求
50、，并且处理机也未被使用时，使用情况表中该处理机所对应项上的罚分就会每秒钟减去一个值，直到为0。5.2.5 处理机分配算法举例处理机分配算法举例上升上升-下降算法：罚分的取值下降算法：罚分的取值l由于每个处理机的罚分一会儿上升，一会儿下降，算法由此得名l使用情况表中的罚分可以为正数、零和负数。l正数表示对应工作站上的用户是在使用系统资源l负数表示该工作站需要系统资源。l零表示介于两者之间。5.2.5 处理机分配算法举例处理机分配算法举例上升上升-下降算法分析下降算法分析l上升上升-下降算法的启发性下降算法的启发性在于l当一个处理机变成空闲状态时，首先分配给罚分最低正在等待处理机的申请。因此，等待
51、时间最长，没有使用处理机的请求将优先得到响应。l实际上，若一个用户已使用了一段时间的系统资源，另一个用户刚开始申请一个进程的运行，那负载较轻的后者要比负载较重的前者要优先得到资源l集中式启发式算法的特征集中式启发式算法的特征即公平地分配系统处理机。l模拟研究表明，在各种情况下，该算法都具有较好的性能。 5.2.5 处理机分配算法举例处理机分配算法举例五、层次分配算法五、层次分配算法 l“上升-下降”作为一个集中式算法无法适用于大型分布式系统。原因在于：协调器将成为整个系统的瓶颈口，此外，协调器的崩溃将造成整个系统无法进行处理机的分配。l上述问题可以通过使用层次分配算法来解决。l层次分配算法既保
52、持了集中式分配算法的简单性，又能更好地适应于大型分布式系统。 5.2.5 处理机分配算法举例处理机分配算法举例层次分配算法层次分配算法l层次分配算法将所有处理机以一种与物理拓扑结构无关的方式组织成一个逻辑分层结构。这种逻辑分层结构与公司、军队、大学等现实世界中人的层次组成结构一样。例如，可以将一些机器看作为工人，而将另一些机器看作为工头。 5.2.5 处理机分配算法举例处理机分配算法举例层次分配算法层次分配算法l例如：l对于每一组k个教师来说，分配给一个系主任的任务是观察谁正忙碌，谁正空闲。l如果系统很大，那就需要更多的管理者。于是，有些机器将作为院长。每一个院长管理若干个系主任。l如果院长较
53、多，则设置一个校长来管理院长。l这种层次关系可以进一步扩展下去，并且所需要的层次随着教师的数目成对数级增长。l由于每一个处理机只需要与一个上级和若干个下属进行通信，所以就可以对系统的信息流进行管理。 5.2.5 处理机分配算法举例处理机分配算法举例层次分配算法：崩溃的解决方法层次分配算法：崩溃的解决方法l当一个系主任，或者更严重地，一个院长停止了工作（即崩溃了），系统将怎么办？l一种方法就是由崩溃院长所管辖的一个系主任来接替该院长职位这个院长职位1）可以由它下级选举产生2）也可以由同级院长们选举产生3）还可以由它的上级来任命。5.2.5 处理机分配算法举例处理机分配算法举例层次分配算法：层次分
54、配算法：最高委员会最高委员会l为了避免单个管理者在层次树的最顶层（造成系统不坚定），可以象下图那样1）去掉树的根节点，最上层组成一个委员会来作为最高决策机构。2）当委员会中的一个成员不工作了，其他人员将在下一层中选出某一个成员来代替。院长委员会院长系主任 教师5.2.5 处理机分配算法举例处理机分配算法举例层次分配算法：结构分析层次分配算法：结构分析l结构分析：l可行性：尽管这种层次结构并不是真正分布式的，但它却是可行的，并且实践证明它是一个较好的结构。l自重构性：特别的是，这种系统可以自重构，并能够容忍被管理者或管理者的突发性崩溃，而不会产生任何长期的影响。5.2.5 处理机分配算法举例处理
55、机分配算法举例层次分配算法：层次分配算法：处理器的预定处理器的预定l算法中，一个处理机只能分配一个进程。l若一个作业产生S个进程，系统必须为它分配S个处理机。作业可以在层次树上的任何一层次上创建。每一个管理者跟踪并记录它辖区内有多少个处理机可用。1）如果有足够的处理机可供使用，那它将预定R个处理机，但RS必须成立，因为这种估计不一定准确，有些机器可能已经关机。 5.2.5 处理机分配算法举例处理机分配算法举例层次分配算法：处理器预定层次分配算法：处理器预定 2）如果没有足够的处理机可供分配，那就把这个申请请求（逐级）向上传递，直到到达某个能够满足该请求的层次。在这一层次上，管理者把这个请求分解
56、成多个申请并向下传递给下级的管理者，一直传递到树的底层。在最低层，被分配的处理机被标为“繁忙”，并把实际分配到的处理机数沿着树向上逐级报告。 5.2.5 处理机分配算法举例处理机分配算法举例层次分配算法：层次分配算法：R的取值的取值l在预定处理器的时候，RS必须成立1）R必须足够的大以便确保有足够数量的处理机可供分配。否则，请求将沿着树向上传递。这样将会浪费了大量的时间。2）另一方面，如果R太大，那么将有过多的处理机被标为“繁忙”，这将浪费一些计算能力，直到分配消息返回底层，这些处理机才会被释放。5.2.5 处理机分配算法举例处理机分配算法举例六、六、超载者启动的分布式启发式算法超载者启动的分
57、布式启发式算法 l这是一个典型的分布式启发式算法，由Eager等人在1986年提出l算法描述：当一个进程创建时，若创建该进程的机器发现自己超载，那就将询问消息发送给一个随机选择的机器，询问该机器的负载是否低于一个阀值。1）如果是，那么该进程就被传送到该机器上去运行。2）否则，就再随机地选择一台机器进行询问。这个过程最多执行N次，若仍然找不到一台合适的机器，那么算法将终止，新创建的进程就在创建它的机器上运行。5.2.5 处理机分配算法举例处理机分配算法举例算法分析算法分析l当整个系统负载很重的时候，l每一个机器都不断地向其他机器发送询问消息以便找到一台机器愿意接收外来的工作。l在这种情况下，所有
58、机器的负载都很重，没有一台机器能够接收其它机器的工作，所以，大量的询问消息不仅毫无意义，而且还给系统增添了巨大的额外开销。 5.2.5 处理机分配算法举例处理机分配算法举例七、七、欠载者启动的分布式启发算法欠载者启动的分布式启发算法 l在这个算法中，当一个进程结束时，系统就检查自己是否欠载。l如果是，它就随机地向一台机器发送询问消息。l如果被询问的机器也欠载，则再随机地向第二台、第三台机器发送询问消息。l如果连续N个询问之后仍然没有找到超载的机器，就暂时停止询问的发送，开始处理本地进程就绪队列中的一个等待进程，处理完毕后，再开始新一轮的询问。l如果既没有本地工作也没有外来的工作，这台机器就进入
59、空闲状态。l在一定的时间间隔以后，它又开始随机地询问远程机器。 5.2.5 处理机分配算法举例处理机分配算法举例算法比较算法比较l与超载者启动的分布式启发式算法相比：l欠载者启动的算法不会在系统非常繁忙时给系统增加额外的负载。l而超载者启动的算法中，一台机器却在系统非常繁忙时发送大量的毫无意义的询问。5.2.5 处理机分配算法举例处理机分配算法举例算法分析算法分析l在欠载者启动的分布式启发式算法中，l当系统繁忙时，一台机器欠载的可能性很小。即使有机器欠载，它也能很快地找到外来的工作。l在系统几乎无事可做时，算法会让每一台空闲机器都不间断地发送询问消息去寻找其它超载机器上的工作，造成大量的系统额
60、外开销。l但是，在系统欠载时产生大量额外开销要比在系统过载时产生大量额外开销好得多。 5.2.5 处理机分配算法举例处理机分配算法举例超超/欠载者启动的结合欠载者启动的结合l可以将上述两种算法结合起来，让超载机器清除一些工作，而让欠载机器去寻找一些工作。l此外，系统中的机器可以通过保留以前的询问以及进行随机地询问来判断是否机器一直过载或欠载，这样可以提高系统性能。 5.2.5 处理机分配算法举例处理机分配算法举例八、八、拍卖算法拍卖算法 l拍卖算法把分布式系统看成一个小经济社会，由买卖双方和供求关系来决定服务的价格。进程为了完成自己的任务必须购买处理机时间，而处理机将它的处理机时间拍卖给出价最
61、高的进程。l算法的执行步骤：1、每一个处理机将自己估计的价格写入一个公共可公共可读的文件读的文件中以此来进行拍卖。说明：1）价格并不是一直不变的，初始的价格只是表示所提供服务的近似价格（一般，它是以前最后一个买主出的价格）。2）根据处理机的运算速度、内存大小、浮点运算能力以及其它一些特性来确定每个处理机的价格。3）处理器提供的服务（例如，预计的响应时间）也要公布出来5.2.5 处理机分配算法举例处理机分配算法举例拍卖算法拍卖算法2、当一个进程要启动一个子进程时，1）查询公共可读文件看有谁能够提供它所需要的服务。2）确定一个它可以付得起钱的处理机集合。通过计算从这个集合中选出一个最好的处理机。最
62、好的标准是最便宜、速度最快或者性能价格比最高。3）给第一个选中的处理机发送一个出价信息，这个出价有可能高于或低于处理机公布的价格。5.2.5 处理机分配算法举例处理机分配算法举例拍卖算法拍卖算法3、处理机1）收集所有发送给它的出价信息2）选择一个出价最高的进程并将通知发送给选中的进程和未选中的进程。3）开始执行被选中的进程。此时，公共可读文件中该处理机的价格将被更新以便反映处理机当前最新的价格。5.2.5 处理机分配算法举例处理机分配算法举例拍卖算法：问题拍卖算法：问题lFerguson等人在1988年提出了这个拍卖算法。但他们并未考虑实现细节。该算法所引起的问题是：l进程从哪里获得钱来购买处
63、理机？l它们有稳定的工资收入吗？l每个进程的月薪都相同吗？还是有些进程的工资高有些进程的工资低呢？l如果用户数量增加而系统未增加相应的一些资源，那么，会不会造成系统通货膨胀？l处理机之间会不会形成同盟来漫天要价敲进程的竹杠？l进程联合工会是否允许这样做呢？l使用磁盘是否也要收费？激光打印机是否收费更高？l等等。 本次课的主要内容本次课的主要内容l分布式处理器分配算法l分配模型l假定l处理器分配策略l分配算法的优化目标l处理器分配算法的分类l处理器分配算法的5个设计问题l处理器分配算法的4个实现问题l算法举例l静态负载分配的基本概念l基于任务优先图的任务调度l基于任务相互关系图的任务调度l基于图论的确定性分配算法l集中式分配算法：上升-下降l层次分配算法l超/欠载者启动的分配算法l拍卖算法
