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