吉林大学研究所课程-并行计算课件-第5章-分布式调度.ppt

第5章 分布式调度 5.3 动态调度 动态调度的组成要素 动态调度算法有六个策略：启动策略、转移策略、选择策略、收益性策略、定位策略和信息策略。 启动策略的责任是决定谁应该激活负载平衡活动。 转移策略决定一个节点是否在合适的状态参与负载转移。 选择策略选择最适合转移最能起平衡作用的任务，并发送给合适的目标处理器。 收益性策略量化系统中负载不平衡程度，并且作为系统负载平衡潜在受益的估计，评估系统负载平衡是否是有收益的。 定位策略是寻找合适的节点共享负载。 信息策略决定收集系统中其他节点状态信息的时机、收集的方法和收集的信息。 第5章 分布式调度 5.3 动态调度 动态负载平衡算法的分类、设计决策和使用的参数 动态负载平衡算法可以分成以下几类： (1) 全局的和局部的。局部负载平衡算法在相邻的节点间转移工作负载。全局负载平衡算法不仅在相邻节点间转移负载，还在全系统内计算负载，根据全局情况调整处理器负载。 (2) 集中控制的和分散控制的。在集中控制算法中，中心控制器收集状态信息，做出负载平衡决策。分散控制算法把控制机制分散到全系统的各个节点。混合式负载平衡算法是集中控制和分散控制算法的折衷。 第5章 分布式调度 5.3 动态调度 动态负载平衡算法的分类、设计决策和使用的参数 动态负载平衡算法可以分成以下几类： (3) 不协作的和协作的。在不协作方法中，各个节点不知道系统中其他节点的状态，独立决定自己的定位和负载转移规则。在协作算法中，节点间相互配合来决定负载平衡决策。 (4) 适应性的和非适应性的。在适应性算法中，负载平衡策略根据系统状态变化而改变；而非适应性方法中，这些策略是不变的。 第5章 分布式调度 5.3 动态调度 动态负载平衡算法的分类、设计决策和使用的参数 动态负载平衡算法的设计决策包括如下一些内容： (1)非抢先式的和抢先式的:抢先式的主要目的是负载共享，节点只分配新到达的任务，又称为任务放置(placement)。抢先式的算法的主要目的是充分利用系统资源，能够重新分配正在运行的任务，又称为进程迁移(migration)。 (2) 采用何种信息策略。与信息策略有关的问题有：(a)周期性收集信息还是非周期性收集信息；(b)收集局部信息还是全局信息；(c)处理器负载指标。 (3)集中控制算法和分散控制算法：集中控制算法有一个中心处理器从系统中其他处理器收集负载信息。分散控制算法是通过每个处理器发送自己负载变化情况给所有处理器或者它的邻居来实现的。 第5章 分布式调度 5.3 动态调度 动态负载平衡算法的分类、设计决策和使用的参数 动态负载平衡算法的设计决策包括如下一些内容： (4) 采用何种启动策略。启动策略有三种：发送者启动的、接受者启动的和对称启动的。 (5) 资源复制。任务转移的时候，涉及到的文件和数据也必须被复制到目标处理器。为了减少转移的代价，常用的任务和数据可以事先被复制和分配到不同的处理器。 (6) 进程分类。依据特征来区分进程类型。如果系统中运行的进程有很大的区别，它们就必须分在不同的类。当系统中有多个进程类型时，负载平衡算法必须考虑进程的类型，根据不同的类型做出改变。 第5章 分布式调度 5.3 动态调度 动态负载平衡算法的分类、设计决策和使用的参数 负载平衡算法使用的参数 ： (1)系统的规模。系统中处理器的数目是影响负载平衡决策的一个参数。 (2)系统负载情况。 需要避免颠簸现象。 (3)处理器的输入流量。进程可以以任何随机模式到达处理器，如果处理器能够测定自己的输入流量并且和其他处理器比较，它就能比较容易评估系统即时的负载水平，从而对任务转移做出更好的决策。 (4)转移的负载门限。系统中触发任务转移的负载门限是一个关键参数，因为选择不当会导致系统不平衡和任务转移的连锁反应。 第5章 分布式调度 5.1 调度算法概述 调度算法的分类 第5章 分布式调度 5.1 调度算法概述 调度算法的分类 其他一些分类方法 ： (1) 非抢先式的(non-preemptive)和抢先式的(preemptive)。对非抢先式的调度算法，一个进程开始执行后就不能中断。在抢先式调度算法中，进程可以中断，从一个处理机上移走，到另一个处理机上继续执行。 (2) 适应性(adaptive)和非适应性的(non-adaptive)。非适应性调度算法只使用一种负载分配策略，不会根据系统的反馈而改变自己的行为。适应性调度算法能够根据系统的反馈调整自己的行为，采用不同的负载分配策略。典型地，一个适应性调度算法是许多种调度算法的集合，根据系统的各种参数来选择一种合适的算法。 第5章 分布式调度 5.1 调度算法概述 调度算法的目标和有