分布式调度课件.ppt

1、第十章第十章 分布式调度分布式调度主讲主讲 陈志刚陈志刚 教授教授第十章第十章 分布式调度分布式调度 22023-6-11中南大学信息科学与工程学院10.1 调度算法概述调度算法概述n调度算法的分类调度算法的分类Casavant和和Kuhl对调度算法做了如下分类：对调度算法做了如下分类：调度算法 局部调度 全局调度 静态调度 动态调度 分散式调度 集中式调度 协作式调度 非协作式调度 优化调度 次优化调度 近似调度 启发式调度 优化调度 次优化调度 近似调度 启发式调度 第十章第十章 分布式调度分布式调度 32023-6-11中南大学信息科学与工程学院n调度算法的分类调度算法的分类 对于大量的

2、实时调度方法而言，还存在着其他一些对于大量的实时调度方法而言，还存在着其他一些划分方法：划分方法：抢占式抢占式(preemptive)和非抢占和非抢占(non-preemptive)调度调度：对抢占式调度算法，正在运行的任务可能被其：对抢占式调度算法，正在运行的任务可能被其他任务所打断。而后者一旦任务开始运行，该任务只他任务所打断。而后者一旦任务开始运行，该任务只有在运行完成而主动放弃有在运行完成而主动放弃CPU资源，或是因为等待其资源，或是因为等待其他资源被阻塞的情况下才会停止运行。他资源被阻塞的情况下才会停止运行。实时内核大都采用了抢占式调度算法，使关键任务能实时内核大都采用了抢占式调度算

3、法，使关键任务能够打断非关键任务的执行，确保关键任务的截止时间够打断非关键任务的执行，确保关键任务的截止时间能够得到满足。能够得到满足。10.1 调度算法概述调度算法概述第十章第十章 分布式调度分布式调度 42023-6-11中南大学信息科学与工程学院n调度算法的分类调度算法的分类适应性适应性(Adaptive)和非适应性和非适应性(Non-Adaptive)调调度度：非适应性调度算法只是用一种负载分配策略，不：非适应性调度算法只是用一种负载分配策略，不会根据系统的反馈而改变自己的行为。适应性调度算会根据系统的反馈而改变自己的行为。适应性调度算法能够根据系统的反馈调整自己的行为，采用不同的法能

4、够根据系统的反馈调整自己的行为，采用不同的负载分配策略。负载分配策略。一个适应性调度算法是许多种调度算法的集合，根据一个适应性调度算法是许多种调度算法的集合，根据系统的各种参数来选择一种合适的算法。系统的各种参数来选择一种合适的算法。10.1 调度算法概述调度算法概述第十章第十章 分布式调度分布式调度 52023-6-11中南大学信息科学与工程学院n调度算法的目标和有效性评价调度算法的目标和有效性评价 分布式调度的基本目标是尽快得到计算结果和分布式调度的基本目标是尽快得到计算结果和有效地利用资源。其具体目标有有效地利用资源。其具体目标有2个：个：负载平衡负载平衡(Load Balancing)

5、：它的努力目标是维：它的努力目标是维持整个分布式系统中各个资源上的负载大致相同。持整个分布式系统中各个资源上的负载大致相同。负载共享负载共享(Load Sharing)：它的目标仅仅是防止：它的目标仅仅是防止某个处理机上的负载过重。某个处理机上的负载过重。10.1 调度算法概述调度算法概述第十章第十章 分布式调度分布式调度 62023-6-11中南大学信息科学与工程学院n调度算法的目标和有效性评价调度算法的目标和有效性评价 从调度算法的有效性来看，调度算法分为最优调度从调度算法的有效性来看，调度算法分为最优调度算法和次优调度算法。算法和次优调度算法。从从理论上理论上来说，最优调度只有在能够完全

6、获知所有任来说，最优调度只有在能够完全获知所有任务在处理、同步和通信方面的需求，以及硬件的处理务在处理、同步和通信方面的需求，以及硬件的处理和时间特性的基础上才能实现。和时间特性的基础上才能实现。n实际的应用实际的应用很难实现，特别是需要获知的信息处很难实现，特别是需要获知的信息处于动态变化的情况下。于动态变化的情况下。n即使在这些需要的信息都是可以预见的情况下，即使在这些需要的信息都是可以预见的情况下，常用的调度问题仍然是一个常用的调度问题仍然是一个NPNP难题难题。n调度的复杂性将随调度需要考虑的任务和约束特调度的复杂性将随调度需要考虑的任务和约束特性的数量呈现出指数增长。性的数量呈现出指

7、数增长。10.1 调度算法概述调度算法概述第十章第十章 分布式调度分布式调度 72023-6-11中南大学信息科学与工程学院n调度算法的目标和有效性评价调度算法的目标和有效性评价 选择调度算法时，通常需要综合考虑如下因素选择调度算法时，通常需要综合考虑如下因素通信代价通信代价：这个参数考虑了向一个给定的节点传送或：这个参数考虑了向一个给定的节点传送或者从一个给定节点接收一个报文所花费的时间，更为者从一个给定节点接收一个报文所花费的时间，更为重要的是必须考虑为一个进程分配一个执行地点而引重要的是必须考虑为一个进程分配一个执行地点而引起的通信代价。起的通信代价。执行代价执行代价：这个参数反映的是将

8、一个进程分配到一个：这个参数反映的是将一个进程分配到一个指定的执行节点，在这个节点的执行环境下，执行这指定的执行节点，在这个节点的执行环境下，执行这个程序所需的额外开销。个程序所需的额外开销。资源利用率参数资源利用率参数：表明基于分布式系统当前各个节点：表明基于分布式系统当前各个节点的负载情况，给一个进程分配的执行节点是否合适。的负载情况，给一个进程分配的执行节点是否合适。10.1 调度算法概述调度算法概述第十章第十章 分布式调度分布式调度 82023-6-11中南大学信息科学与工程学院n调度算法的目标和有效性评价调度算法的目标和有效性评价 次优的调度算法分为两类：次优的调度算法分为两类：近似

9、的次优调度算法近似的次优调度算法：在近似在近似次优调度次优调度方法中，负载方法中，负载分配算法仅搜索一个解空间的子集，当寻找到一个好分配算法仅搜索一个解空间的子集，当寻找到一个好的解时，终止执行。的解时，终止执行。使用近似的次优调度算法必须能使用近似的次优调度算法必须能够判定所得到的解是否是可以被接受的，也就是说，够判定所得到的解是否是可以被接受的，也就是说，必须能够确定最优解和次优解之间的近似程度。必须能够确定最优解和次优解之间的近似程度。启发式的次优调度算法启发式的次优调度算法：使用比较简明的规则和一些：使用比较简明的规则和一些直觉的规则来进行调度。这些启发式的规则往往是不直觉的规则来进行

10、调度。这些启发式的规则往往是不能证明其正确性，在特定情况下可能还是错误的，但能证明其正确性，在特定情况下可能还是错误的，但是在绝大多数的情况下是能够被接受的。是在绝大多数的情况下是能够被接受的。10.1 调度算法概述调度算法概述第十章第十章 分布式调度分布式调度 92023-6-11中南大学信息科学与工程学院 静态调度算法静态调度算法是根据系统的先验知识做出决策。运行是根据系统的先验知识做出决策。运行时负载不能重新分配。时负载不能重新分配。设计调度策略时要考虑的三个主要因素是处理机的互设计调度策略时要考虑的三个主要因素是处理机的互连、任务的划分和任务的分配。通常用图模型表示任务和连、任务的划分

11、和任务的分配。通常用图模型表示任务和处理机的结构。处理机的结构。我们用任务优先图或者任务交互作用图对任务集合建模。我们用任务优先图或者任务交互作用图对任务集合建模。任务优先图任务优先图又称为有向无环图又称为有向无环图(DAG)(DAG)，每个链接定义了任务间的优，每个链接定义了任务间的优先关系。节点和链接上的标记表示任务执行时间和任务完成后启先关系。节点和链接上的标记表示任务执行时间和任务完成后启动后续任务所需的时间间隔。动后续任务所需的时间间隔。任务交互作用图任务交互作用图中，链接定义了两个任务间的相互关系。每个链中，链接定义了两个任务间的相互关系。每个链接赋予一对数，表示这两个任务在同一个

12、处理机上时的通信开销接赋予一对数，表示这两个任务在同一个处理机上时的通信开销和在不同处理机上时的通信开销。和在不同处理机上时的通信开销。10.2 静态调度静态调度第十章第十章 分布式调度分布式调度 102023-6-11中南大学信息科学与工程学院10.2 静态调度静态调度 2 1 1 4 2 1 1 4 2 2 T1 T2 T3 T4 T5(a)任务优先图 2 3 4 2 3 T1 T2 T3 T4 T5 1,4 1,5 1,4 1,3 1,5 1,4(b)任务相互作用图 第十章第十章 分布式调度分布式调度 112023-6-11中南大学信息科学与工程学院n任务划分与分配任务划分与分配 任务划

13、分的一个主要目标就是尽可能消除处理器间通任务划分的一个主要目标就是尽可能消除处理器间通信引起的开销。信引起的开销。一个给定任务划分的粒度被定义为任务的计算量与通信量的比值。一个给定任务划分的粒度被定义为任务的计算量与通信量的比值。粒度太大，就会降低并行度，因为潜在并行任务可能被划分进同粒度太大，就会降低并行度，因为潜在并行任务可能被划分进同一个任务而分配给一个处理器。粒度太小，进程切换和通信的开一个任务而分配给一个处理器。粒度太小，进程切换和通信的开销就会增加。销就会增加。任务聚类任务聚类：在图模型中，任务的划分被称作任务聚类，即在给定：在图模型中，任务的划分被称作任务聚类，即在给定的图模型中

14、对小任务进行分类。任务划分把任务图当作一个整体，的图模型中对小任务进行分类。任务划分把任务图当作一个整体，将图中的小任务将图中的小任务(节点节点)划分成不同的聚类，聚类中的小任务串行划分成不同的聚类，聚类中的小任务串行执行，不同的聚类之间并行执行。任务聚类中可以使用两种策略：执行，不同的聚类之间并行执行。任务聚类中可以使用两种策略：n将不相关的任务映射到一个聚类中；将不相关的任务映射到一个聚类中；n将将DAG中一条优先路径上的任务映射到一个聚类中。中一条优先路径上的任务映射到一个聚类中。10.2 静态调度静态调度第十章第十章 分布式调度分布式调度 122023-6-11中南大学信息科学与工程学

15、院n任务划分与分配任务划分与分配任务划分的方法任务划分的方法n关键路径划分关键路径划分：主要思想是在给定的任务优先图中垂直或者水主要思想是在给定的任务优先图中垂直或者水平划分。关键路径平划分。关键路径(最长路径最长路径)的概念常常在垂直划分中使用。的概念常常在垂直划分中使用。水平划分把给定的任务分成若干层，任务的优先级由它们所在水平划分把给定的任务分成若干层，任务的优先级由它们所在的层次决定。的层次决定。n通信延迟最小划分通信延迟最小划分：主要思想是把通信频繁的节点归成一类。：主要思想是把通信频繁的节点归成一类。然而，这些需要通信的任务分配在一个处理器上会丧失任务间然而，这些需要通信的任务分配

16、在一个处理器上会丧失任务间的并发性。如果减小通信延迟的好处抵销了并行任务串行化的的并发性。如果减小通信延迟的好处抵销了并行任务串行化的损失，就采用通信延迟最小划分。损失，就采用通信延迟最小划分。n任务复制任务复制：为了消除任务间的通信开销，将任务在处理机上进为了消除任务间的通信开销，将任务在处理机上进行复制有时是最有效的方法行复制有时是最有效的方法。这个方法保留了任务原有的并行。这个方法保留了任务原有的并行性；但是存储空间要求和同步开销增加了。可以利用任务复制性；但是存储空间要求和同步开销增加了。可以利用任务复制来达到容错性。任务复制也被用来实现无错调度，以保证处理来达到容错性。任务复制也被用

17、来实现无错调度，以保证处理器出现错误时最后计算结果正确。器出现错误时最后计算结果正确。10.2 静态调度静态调度第十章第十章 分布式调度分布式调度 132023-6-11中南大学信息科学与工程学院n任务划分与分配任务划分与分配10.2 静态调度静态调度关键路径划分的例子关键路径划分的例子132457964252472T1T2T5T3T6T4T7消除通信延迟的划分消除通信延迟的划分133112T2T3T4T5T63133312T1第十章第十章 分布式调度分布式调度 142023-6-11中南大学信息科学与工程学院n任务划分与分配任务划分与分配任务复制：任务复制：10.2 静态调度静态调度 1 3

18、 2 4 5 7 9 6 4 2 5 2 4 7 2 T1 T2 T5 T3 T6 T4 T7 时间 处理机 1 处理机 2 处理机 3 1 T1 T1 T1 2 T2 T3 T4 4 T2 T2 T4 5 T3 T2 T4 6 T3 T2 T2 7 T5 T6 T2 9 T5 T6 T7 第十章第十章 分布式调度分布式调度 152023-6-11中南大学信息科学与工程学院n任务划分与分配任务划分与分配基于任务优先图的任务调度基于任务优先图的任务调度 甘特图甘特图(gantt chart)能够最有效描述进程对处理能够最有效描述进程对处理器的分配情况。甘特图以处理器为纵坐标，以时间为横器的分配情

19、况。甘特图以处理器为纵坐标，以时间为横坐标。图中的每个方块表示进程在某个系统中的开始时坐标。图中的每个方块表示进程在某个系统中的开始时间、持续时间和结束时间。处理器内的时间延迟和处理间、持续时间和结束时间。处理器内的时间延迟和处理器间的时间延迟都能够在图中体现。器间的时间延迟都能够在图中体现。10.2 静态调度静态调度第十章第十章 分布式调度分布式调度 162023-6-11中南大学信息科学与工程学院n任务划分与分配任务划分与分配基于任务优先图的任务调度基于任务优先图的任务调度 10.2 静态调度静态调度 2 1 1 4 2 1 1 4 2 2 T1 T2 T3 T4 T5(a)任务优先图(b

20、)甘特图 时间 处理器 P1 P2 T1 0 2 T2 3 T3 T4 7 T5 12 第十章第十章 分布式调度分布式调度 172023-6-11中南大学信息科学与工程学院n任务划分与分配任务划分与分配基于任务优先图的任务调度基于任务优先图的任务调度通信延迟和任务复制对调度的影响：通信延迟和任务复制对调度的影响：10.2 静态调度静态调度 T1 T2 T3 d d 时间 处理器 P1 P2 T1 T1 T2 T3 时间 处理器 P1 P2 T1 T2 T3 时间 P1 P2 处理器 T1 T2 T3 d(a)任务优先图(b)使用任务复制的调度(c)任务分配在一个处理器上(d)通信延迟对调度的影

21、响 第十章第十章 分布式调度分布式调度 182023-6-11中南大学信息科学与工程学院n任务划分与分配任务划分与分配基于任务优先图的任务调度基于任务优先图的任务调度 线性聚类与非线性聚类线性聚类与非线性聚类：如果至少有一个聚类中：如果至少有一个聚类中包含两个独立的任务，则聚类是非线性的；否则，聚包含两个独立的任务，则聚类是非线性的；否则，聚类就是线性的。类就是线性的。10.2 静态调度静态调度 4 3 2 T1 T2 T3 1 1 4 3 2 T1 T2 T3 1 1(a)线性聚类(b)非线性聚类 第十章第十章 分布式调度分布式调度 192023-6-11中南大学信息科学与工程学院n两种最优

22、调度算法两种最优调度算法 多数调度算法是多数调度算法是NP完全的。下面介绍完全的。下面介绍2种有约束的调度问种有约束的调度问题，他们有多项式时间的执行复杂度。两种方法都假设通信代题，他们有多项式时间的执行复杂度。两种方法都假设通信代价可以忽略，优先图中每个节点的执行时间是一样的，即一个价可以忽略，优先图中每个节点的执行时间是一样的，即一个时间单元。具体限制如下：时间单元。具体限制如下：在第一个有约束的调度问题中，优先图是一棵树。在第一个有约束的调度问题中，优先图是一棵树。在第二个有约束的调度问题中，只有两个处理器可用。在第二个有约束的调度问题中，只有两个处理器可用。两种调度算法都是最高层优先两

23、种调度算法都是最高层优先(highest-level-first)方法，也就是说，通过节点的优先级来选择节点方法，也就是说，通过节点的优先级来选择节点。10.2 静态调度静态调度第十章第十章 分布式调度分布式调度 202023-6-11中南大学信息科学与工程学院n两种最优调度算法两种最优调度算法 10.2 静态调度静态调度 T1 T2 T3 T4 T5 T6 T7 T8 T9 T10 T11 T12 T13 时间 处理器 P1 P2 P3 0 T1 T2 T3 T4 T5 T7 T6 T9 T10 T8 T12 T11 T13(a)树结构的任务优先图 (b)对三个处理器的调度 树结构任务优先图

24、的最优调度树结构任务优先图的最优调度第十章第十章 分布式调度分布式调度 212023-6-11中南大学信息科学与工程学院n两种最优调度算法两种最优调度算法 10.2 静态调度静态调度任务优先图对双处理器的最优调度任务优先图对双处理器的最优调度 T9 T10 T11 T7 T8 T6 T4 T5 T1 T2 T3 1 2 3 4 5 6 7 8 9 10 11(a)优先级的标记 时间 处理器 P1 P2 T9 T10 T7 T8 T11 T6 T5 T4 T3 T2 T1(b)对双处理器的调度 第十章第十章 分布式调度分布式调度 222023-6-11中南大学信息科学与工程学院n基于任务相互关系

25、图的任务调度基于任务相互关系图的任务调度任务相互关系图由无向图任务相互关系图由无向图Gt(Vt,Et)表示，表示，Vt是进程集是进程集合，合，Et是边集合，每条边用相关两个进程的通信代价是边集合，每条边用相关两个进程的通信代价标记；标记；处理器图处理器图Gp(Vp,Ep)用顶点集用顶点集Vp和边集和边集Ep表示，表示，Vp中的中的每个元素是一个处理器，每个元素是一个处理器，Ep中的每个元素是一个通信中的每个元素是一个通信信道；信道；然后进行分配然后进行分配M：进行：进行VtVp的变换和执行时间的估计。的变换和执行时间的估计。假设假设w(u)和和w(u,v)分别表示节点分别表示节点u和链接和链接

26、(u,v)的代的代价。价。10.2 静态调度静态调度第十章第十章 分布式调度分布式调度 232023-6-11中南大学信息科学与工程学院10.2 静态调度静态调度n基于任务相互关系图的任务调度基于任务相互关系图的任务调度对分配对分配M的评估：的评估：n处理器处理器p的计算负载为：的计算负载为：n处理器处理器p的通信负载为：的通信负载为：n整个应用程序中总的计算量是：整个应用程序中总的计算量是：n整个应用程序中总的通信量是：整个应用程序中总的通信量是：tVupuMuwpComp)(|)()(pptVpVpVupuMuwpCompComp)(|)()(ptpVpEvuVpvMpuMvuwpComm

27、pComm),(2121)()(|),()(tEvuvMpuMvuwpCommp),()()(|),()(第十章第十章 分布式调度分布式调度 242023-6-11中南大学信息科学与工程学院10.2 静态调度静态调度n基于任务相互关系图的任务调度基于任务相互关系图的任务调度对分配对分配M的评估：的评估：n程序总的执行时间大概是：程序总的执行时间大概是：是依据处理器的执行速度确定的值，是依据处理器的执行速度确定的值，是依据每个通信信道的是依据每个通信信道的通信速度和通信进程间的距离确定的值。注意如果两个进程通信速度和通信进程间的距离确定的值。注意如果两个进程u和和v在在Gt中邻接，它们在中邻接，

28、它们在Gp的映像的映像(M的映像结果的映像结果)可能邻接也可能不邻可能邻接也可能不邻接。理想的情况下，所有通信进程被分配在邻接的处理机上，以此接。理想的情况下，所有通信进程被分配在邻接的处理机上，以此减少处理器间通信。减少处理器间通信。(两个进程通常不应该映射在一个处理器上两个进程通常不应该映射在一个处理器上,任务聚类时任务聚类时,这两个进程应当聚类到同一进程这两个进程应当聚类到同一进程.)pVppCommpCompT),()(max第十章第十章 分布式调度分布式调度 252023-6-11中南大学信息科学与工程学院10.2 静态调度静态调度n基于任务相互关系图的任务调度基于任务相互关系图的任

29、务调度映射的势映射的势：评估映射质量的一个指标是任务图：评估映射质量的一个指标是任务图Gt中的中的边映射到处理器图边映射到处理器图Gp中的边的数目。这个数目被称作中的边的数目。这个数目被称作映射的势映射的势(cardinality)，就是，就是Gt中映射到中映射到Gp中邻中邻接处理器的通信进程对的数目。映射的势不会超过接处理器的通信进程对的数目。映射的势不会超过Gt中的链接数目。如果一个映射的势最大，它就是一个中的链接数目。如果一个映射的势最大，它就是一个理想的映射。理想的映射。第十章第十章 分布式调度分布式调度 262023-6-11中南大学信息科学与工程学院10.2 静态调度静态调度n基于

30、任务相互关系图的任务调度基于任务相互关系图的任务调度图中，映射的势是图中，映射的势是8，任务关系图中边的为，任务关系图中边的为13条。条。1 2 3 4 5 6 7 8 9 3 1 2 4 6 7 5 9 8(a)任务相互关系图(b)任务到处理器的映射 第十章第十章 分布式调度分布式调度 272023-6-11中南大学信息科学与工程学院10.2 静态调度静态调度n基于任务相互关系图的任务调度基于任务相互关系图的任务调度 嵌入嵌入：设想任务相互关系图和处理器图被各自看作：设想任务相互关系图和处理器图被各自看作Gt和和Gp。为了通过。为了通过Gt得到对得到对Gp的有效模拟，也就是在的有效模拟，也就

31、是在Gp中嵌入中嵌入Gt。嵌入的不同代价指标：嵌入的不同代价指标：Gt的边的膨胀。的边的膨胀。Gt的边的膨胀定义为被映射成的边的膨胀定义为被映射成Gt里的一条边的里的一条边的Gp中对应的路径的长度。嵌入的膨胀为中对应的路径的长度。嵌入的膨胀为Gt中的最大边膨胀。中的最大边膨胀。嵌入的扩大。嵌入的扩大定义为嵌入的扩大。嵌入的扩大定义为Gt里的节点数对里的节点数对Gp里的节点数的里的节点数的比率。比率。嵌入的拥塞。嵌入的拥塞定义为包含嵌入的拥塞。嵌入的拥塞定义为包含Gp中的一条边的最大路径数，中的一条边的最大路径数，Gp中的每条路径表示中的每条路径表示Gt中的一条边。中的一条边。嵌入的负载。嵌入的

32、负载是嵌入的负载。嵌入的负载是Gt分配给分配给Gp中任意处理器的进程的最中任意处理器的进程的最大数目。大数目。第十章第十章 分布式调度分布式调度 282023-6-11中南大学信息科学与工程学院典型的动态调度算法由以下典型的动态调度算法由以下6个策略组成：个策略组成：n启动策略启动策略决定谁应该激活负载平衡活动。决定谁应该激活负载平衡活动。n转移策略转移策略决定一个节点是否在合适的状态参与负载转移。决定一个节点是否在合适的状态参与负载转移。n选择策略选择策略选择最适合转移最能起平衡作用的任务，并发送选择最适合转移最能起平衡作用的任务，并发送给合适的目标处理器。给合适的目标处理器。n收益性策略收

33、益性策略量化系统中负载不平衡程度，并且作为系统负量化系统中负载不平衡程度，并且作为系统负载平衡潜在受益的估计，评估系统负载平衡是否是有收益载平衡潜在受益的估计，评估系统负载平衡是否是有收益的。的。n定位策略定位策略寻找合适的节点共享负载。寻找合适的节点共享负载。n信息策略信息策略决定收集系统中其他节点状态信息的时机、收集决定收集系统中其他节点状态信息的时机、收集的方法和收集的信息。的方法和收集的信息。10.3 动态调度动态调度第十章第十章 分布式调度分布式调度 292023-6-11中南大学信息科学与工程学院n动态负载平衡算法的分类动态负载平衡算法的分类局部和全局局部和全局 局部负载分配处理单

34、个处理器上的进程对时间片局部负载分配处理单个处理器上的进程对时间片(单单元元)的分配。全局负载分配首先进行进程对处理器的分配，的分配。全局负载分配首先进行进程对处理器的分配，然后完成每个处理器内这些进程的局部调度。然后完成每个处理器内这些进程的局部调度。集中控制的和分散控制的集中控制的和分散控制的(在动态类型中在动态类型中)在分散控制中，决策工作被分配给不同的处理器。在在分散控制中，决策工作被分配给不同的处理器。在集中控制中，这些工作是由一个处理器完成的集中控制中，这些工作是由一个处理器完成的。10.3 动态调度动态调度第十章第十章 分布式调度分布式调度 302023-6-11中南大学信息科学

35、与工程学院n动态负载平衡算法的分类动态负载平衡算法的分类协作的和非协作的协作的和非协作的(对分散控制对分散控制)协作的分布式对象间有协同操作，非协作的协作的分布式对象间有协同操作，非协作的处理器独立做出决策。处理器独立做出决策。非自适应的和自适应的非自适应的和自适应的 非自适应负载分配只使用一种负载分配算法，不会依非自适应负载分配只使用一种负载分配算法，不会依据系统反馈而改变自己的行为。自适应负载分配能够根据据系统反馈而改变自己的行为。自适应负载分配能够根据系统反馈调整分配算法。典型地，一个自适应负载分配算系统反馈调整分配算法。典型地，一个自适应负载分配算法是许多负载分配算法的集合，依据系统的

36、各种参数来选法是许多负载分配算法的集合，依据系统的各种参数来选择一个合适的算法。择一个合适的算法。10.3 动态调度动态调度第十章第十章 分布式调度分布式调度 312023-6-11中南大学信息科学与工程学院10.3 动态调度动态调度n动态负载平衡算法的分类动态负载平衡算法的分类动态负载平衡算法的设计决策包括如下一些内容：动态负载平衡算法的设计决策包括如下一些内容：非抢先式的和抢先式的非抢先式的和抢先式的:抢先式的主要目的是负载共享，节点只分抢先式的主要目的是负载共享，节点只分配新到达的任务，又称为任务放置配新到达的任务，又称为任务放置(placement)。抢先式的算法。抢先式的算法的主要目

37、的是充分利用系统资源，能够重新分配正在运行的任务，的主要目的是充分利用系统资源，能够重新分配正在运行的任务，又称为进程迁移又称为进程迁移(migration)。采用何种信息策略采用何种信息策略。信息策略有三种：。信息策略有三种：(a)周期策略；周期策略；(b)需求策需求策略；略；(c)状态变化驱动策略。状态变化驱动策略。集中控制算法和分散控制算法集中控制算法和分散控制算法：集中控制算法有一个中心处理器：集中控制算法有一个中心处理器从系统中其他处理器收集负载信息。分散控制算法是通过每个处从系统中其他处理器收集负载信息。分散控制算法是通过每个处理器发送自己负载变化情况给所有处理器或者它的邻居来实现

38、的。理器发送自己负载变化情况给所有处理器或者它的邻居来实现的。第十章第十章 分布式调度分布式调度 322023-6-11中南大学信息科学与工程学院10.3 动态调度动态调度n动态负载平衡算法的分类动态负载平衡算法的分类动态负载平衡算法的设计决策包括如下一些内容：动态负载平衡算法的设计决策包括如下一些内容：采用何种启动策略采用何种启动策略。启动策略有三种：发送者启动的、接收者启。启动策略有三种：发送者启动的、接收者启动的和对称启动的。动的和对称启动的。资源复制资源复制。任务转移的时候，涉及到的文件和数据也必须被复制。任务转移的时候，涉及到的文件和数据也必须被复制到目标处理器。为了减少转移的代价，

39、常用的任务和数据可以事到目标处理器。为了减少转移的代价，常用的任务和数据可以事先被复制和分配到不同的处理器。先被复制和分配到不同的处理器。进程分类进程分类。依据特征来区分进程类型。如果系统中运行的进程有。依据特征来区分进程类型。如果系统中运行的进程有很大的区别，它们就必须分在不同的类。当系统中有多个进程类很大的区别，它们就必须分在不同的类。当系统中有多个进程类型时，负载平衡算法必须考虑进程的类型，根据不同的类型做出型时，负载平衡算法必须考虑进程的类型，根据不同的类型做出改变。改变。第十章第十章 分布式调度分布式调度 332023-6-11中南大学信息科学与工程学院10.3 动态调度动态调度n动

40、态负载平衡算法的分类、动态负载平衡算法的分类、设计决策和使设计决策和使用的参数用的参数 负载平衡算法使用的参数负载平衡算法使用的参数：系统的规模系统的规模：处理器的数目是影响负载平衡决策的一个参数。：处理器的数目是影响负载平衡决策的一个参数。系统负载情况系统负载情况：需要避免颠簸现象。：需要避免颠簸现象。处理器的输入流量：处理器的输入流量：进程可以以任何随机模式到达处理器，如果进程可以以任何随机模式到达处理器，如果处理器能够测定自己的输入流量并且和其他处理器比较，它就能处理器能够测定自己的输入流量并且和其他处理器比较，它就能比较容易评估系统即时的负载水平，从而对任务转移做出更好的比较容易评估系

41、统即时的负载水平，从而对任务转移做出更好的决策。决策。转移的负载门限转移的负载门限。系统中触发任务转移的负载门限是一个关键参。系统中触发任务转移的负载门限是一个关键参数，因为选择不当会导致系统不平衡和任务转移的连锁反应。数，因为选择不当会导致系统不平衡和任务转移的连锁反应。第十章第十章 分布式调度分布式调度 342023-6-11中南大学信息科学与工程学院10.3 动态调度动态调度n动态负载平衡算法的分类、动态负载平衡算法的分类、设计决策和使设计决策和使用的参数用的参数 负载平衡算法使用的参数负载平衡算法使用的参数：任务大小任务大小。一般来说，转移一个运行时间太短的任务是不恰当。一般来说，转移

42、一个运行时间太短的任务是不恰当的。类似的，太大的进程或者涉及到大量数据和文件的进程最的。类似的，太大的进程或者涉及到大量数据和文件的进程最好在本地处理器上执行。好在本地处理器上执行。管理成本管理成本。组成管理成本的主要因素是：处理器当前负载的测。组成管理成本的主要因素是：处理器当前负载的测量、处理器决策使用的负载信息、决策发生的位置和处理器间量、处理器决策使用的负载信息、决策发生的位置和处理器间任务的传送。任务的传送。第十章第十章 分布式调度分布式调度 352023-6-11中南大学信息科学与工程学院10.3 动态调度动态调度n动态负载平衡算法的分类、动态负载平衡算法的分类、设计决策和使设计决

43、策和使用的参数用的参数 负载平衡算法使用的参数负载平衡算法使用的参数：负载平衡的视界负载平衡的视界。一个节点能够在其邻接节点范围内为一个任。一个节点能够在其邻接节点范围内为一个任务寻找可能的目标节点，在其上运行该任务。这个邻接节点范务寻找可能的目标节点，在其上运行该任务。这个邻接节点范围的直径称为视界围的直径称为视界(horizon)。这个参数设置了寻找目标节点。这个参数设置了寻找目标节点过程中探查的邻接节点的数量。过程中探查的邻接节点的数量。资源要求资源要求。任务对系统资源的要求会影响它的转移。需要较多。任务对系统资源的要求会影响它的转移。需要较多资源的进程可能会持续等待资源变得可用，这就可

44、能影响系统资源的进程可能会持续等待资源变得可用，这就可能影响系统的响应时间。的响应时间。第十章第十章 分布式调度分布式调度 362023-6-11中南大学信息科学与工程学院10.4 空闲工作站的调度结构空闲工作站的调度结构n工作站共享问题工作站共享问题 工作站共享问题包括：对工作站使用模式的工作站共享问题包括：对工作站使用模式的分析，设计分配远程处理能力的算法和结构，研分析，设计分配远程处理能力的算法和结构，研究远程执行设备。究远程执行设备。全局调度机构的主要目标有：全局调度机构的主要目标有：性能要求性能要求：调度机构占用整个系统的开销最小，它们：调度机构占用整个系统的开销最小，它们不应该占用

45、不使用此机构的应用程序的时间，也不应不应该占用不使用此机构的应用程序的时间，也不应该使被调度的应用程序的执行产生大的延迟。该使被调度的应用程序的执行产生大的延迟。支持的系统规模支持的系统规模：能支持几百个甚至上千个工作站。：能支持几百个甚至上千个工作站。第十章第十章 分布式调度分布式调度 372023-6-11中南大学信息科学与工程学院10.4 空闲工作站的调度结构空闲工作站的调度结构n工作站共享问题工作站共享问题 容错容错：一个或几个机器崩溃时，系统的远程执行设备：一个或几个机器崩溃时，系统的远程执行设备应该在几秒钟之后能够继续工作。应该在几秒钟之后能够继续工作。公平性公平性：不管分配作业到

46、哪个机器上，为该作业提供：不管分配作业到哪个机器上，为该作业提供的性能都是同样可接受的。的性能都是同样可接受的。自治性自治性：工作站属于个人所有，其他人使用不应影响：工作站属于个人所有，其他人使用不应影响主人的工作。主人的工作。第十章第十章 分布式调度分布式调度 382023-6-11中南大学信息科学与工程学院10.4 空闲工作站的调度结构空闲工作站的调度结构n工作站共享问题工作站共享问题 有关负载的信息是如何传送的，使用公布的还是回答有关负载的信息是如何传送的，使用公布的还是回答查询的办法？即选择哪一种信息策略。查询的办法？即选择哪一种信息策略。谁主动发起远程执行的请求，是作业进入的顾客节点

47、谁主动发起远程执行的请求，是作业进入的顾客节点(源节点源节点)还是处理此作业的节点还是处理此作业的节点(服务员节点服务员节点)？这？这里所要解决的是选择什么样的启动策略。里所要解决的是选择什么样的启动策略。谁来决策为一个作业谁来决策为一个作业(程序程序)选择一个合适的执行主机，选择一个合适的执行主机，请求的发起者还是一个集中的服务员节点？这里要解请求的发起者还是一个集中的服务员节点？这里要解决的是定位策略的问题。决的是定位策略的问题。这是设计全局调度设施在结构上要解决的三个主要问题这是设计全局调度设施在结构上要解决的三个主要问题。第十章第十章 分布式调度分布式调度 392023-6-11中南大

48、学信息科学与工程学院10.4 空闲工作站的调度结构空闲工作站的调度结构n集中式调度集中式调度 集中式调度是在系统中有一个中央调度服务员，负集中式调度是在系统中有一个中央调度服务员，负责搜集状态信息并做出全部调度决策。各机器周期性地责搜集状态信息并做出全部调度决策。各机器周期性地向它发送状态更新报文，报告它们的负载信息；顾客向向它发送状态更新报文，报告它们的负载信息；顾客向它发送远程执行请求。中央调度服务员根据负载情况，它发送远程执行请求。中央调度服务员根据负载情况，建立一个主机候选者的有序表，对顾客的远程执行请求建立一个主机候选者的有序表，对顾客的远程执行请求进行响应。使用中央调度服务员查询状

49、态会减少报文传进行响应。使用中央调度服务员查询状态会减少报文传送数目。但是容易产生状态信息过时的问题。解决集中送数目。但是容易产生状态信息过时的问题。解决集中式调度的式调度的容错问题容错问题的典型方法是提供多个备用服务员。的典型方法是提供多个备用服务员。集中调度的最后一个问题是集中调度的最后一个问题是在何处运行调度程序在何处运行调度程序。调度程序没有任何特殊要求，可放到任何空闲机器上，调度程序没有任何特殊要求，可放到任何空闲机器上，并可根据需要迁移。并可根据需要迁移。第十章第十章 分布式调度分布式调度 402023-6-11中南大学信息科学与工程学院10.4 空闲工作站的调度结构空闲工作站的调

50、度结构n分散式调度分散式调度 在全分散方案中，每个机器自己进行选择活动。它在全分散方案中，每个机器自己进行选择活动。它必须不断地记录整个系统状态或者当需要时查询系统状必须不断地记录整个系统状态或者当需要时查询系统状态信息。在前一种情况下，每个机器态信息。在前一种情况下，每个机器(即使是忙碌的机器即使是忙碌的机器)要定期地产生更新报文并向其他主机广播要定期地产生更新报文并向其他主机广播(公布公布)。而每。而每个主机中维持一个主机状态表。在后一种情况下只有对个主机中维持一个主机状态表。在后一种情况下只有对主机选择有兴趣的那些主机才关心状态信息主机选择有兴趣的那些主机才关心状态信息(查询查询)。采。