分布式调度.ppt

中南大学信息科学与工程学院 第十章 分布式调度 主讲 陈志刚 教授 10.1 调度算法概述 调度算法的分类 Casavant和Kuhl对调度算法做了如下分类： 10.1 调度算法概述 调度算法的分类 对于大量的实时调度方法而言，还存在着其他一些划分方法： 抢占式(preemptive)和非抢占(non-preemptive)调度：对抢占式调度算法，正在运行的任务可能被其他任务所打断。而后者一旦任务开始运行，该任务只有在运行完成而主动放弃CPU资源，或是因为等待其他资源被阻塞的情况下才会停止运行。 实时内核大都采用了抢占式调度算法，使关键任务能够打断非关键任务的执行，确保关键任务的截止时间能够得到满足。 10.1 调度算法概述 调度算法的分类 适应性(Adaptive)和非适应性(Non-Adaptive)调度：非适应性调度算法只是用一种负载分配策略，不会根据系统的反馈而改变自己的行为。适应性调度算法能够根据系统的反馈调整自己的行为，采用不同的负载分配策略。 一个适应性调度算法是许多种调度算法的集合，根据系统的各种参数来选择一种合适的算法。 调度算法的目标和有效性评价 分布式调度的基本目标是尽快得到计算结果和有效地利用资源。其具体目标有2个： 负载平衡(Load Balancing)：它的努力目标是维持整个分布式系统中各个资源上的负载大致相同。 负载共享(Load Sharing)：它的目标仅仅是防止某个处理机上的负载过重。 调度算法的目标和有效性评价 从调度算法的有效性来看，调度算法分为最优调度算法和次优调度算法。 从理论上来说，最优调度只有在能够完全获知所有任务在处理、同步和通信方面的需求，以及硬件的处理和时间特性的基础上才能实现。 实际的应用很难实现，特别是需要获知的信息处于动态变化的情况下。 即使在这些需要的信息都是可以预见的情况下，常用的调度问题仍然是一个NP难题。 调度的复杂性将随调度需要考虑的任务和约束特性的数量呈现出指数增长。 调度算法的目标和有效性评价 选择调度算法时，通常需要综合考虑如下因素 通信代价：这个参数考虑了向一个给定的节点传送或者从一个给定节点接收一个报文所花费的时间，更为重要的是必须考虑为一个进程分配一个执行地点而引起的通信代价。 执行代价：这个参数反映的是将一个进程分配到一个指定的执行节点，在这个节点的执行环境下，执行这个程序所需的额外开销。 资源利用率参数：表明基于分布式系统当前各个节点的负载情况，给一个进程分配的执行节点是否合适。 调度算法的目标和有效性评价 次优的调度算法分为两类： 近似的次优调度算法：在近似次优调度方法中，负载分配算法仅有哪些信誉好的足球投注网站一个解空间的子集，当寻找到一个好的解时，终止执行。使用近似的次优调度算法必须能够判定所得到的解是否是可以被接受的，也就是说，必须能够确定最优解和次优解之间的近似程度。 启发式的次优调度算法：使用比较简明的规则和一些直觉的规则来进行调度。这些启发式的规则往往是不能证明其正确性，在特定情况下可能还是错误的，但是在绝大多数的情况下是能够被接受的。 10.2 静态调度 静态调度算法是根据系统的先验知识做出决策。运行时负载不能重新分配。 设计调度策略时要考虑的三个主要因素是处理机的互连、任务的划分和任务的分配。通常用图模型表示任务和处理机的结构。 我们用任务优先图或者任务交互作用图对任务集合建模。 任务优先图又称为有向无环图(DAG)，每个链接定义了任务间的优先关系。节点和链接上的标记表示任务执行时间和任务完成后启动后续任务所需的时间间隔。 任务交互作用图中，链接定义了两个任务间的相互关系。每个链接赋予一对数，表示这两个任务在同一个处理机上时的通信开销和在不同处理机上时的通信开销。 10.2 静态调度 10.2 静态调度 任务划分与分配 任务划分的一个主要目标就是尽可能消除处理器间通信引起的开销。 一个给定任务划分的粒度被定义为任务的计算量与通信量的比值。粒度太大，就会降低并行度，因为潜在并行任务可能被划分进同一个任务而分配给一个处理器。粒度太小，进程切换和通信的开销就会增加。 任务聚类：在图模型中，任务的划分被称作任务聚类，即在给定的图模型中对小任务进行分类。任务划分把任务图当作一个整体，将图中的小任务(节点)划分成不同的聚类，聚类中的小任务串行执行，不同的聚类之间并行执行。任务聚类中可以使用两种策略： 将不相关的任务映射到一个聚类中； 将DAG中一条优先路径上的任务映射到一个聚类中。 10.2 静态调度 任务划分与分配 任务划分的方法 关键路径划分：主要思想是在给定的任务优先图中垂直或者水平划分。关键路径(最长路径)的概念常常在垂直划分中使用。水平划分把给定的任务分