高级操作系统Advanced Operating System.ppt

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