分布式系统中的任务调度问题与遗传算法应用.研究

《分布式系统中的任务调度问题与遗传算法应用.研究》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、篁三童坌童垄墨丝丝苎堡叁堡堡旦璧——第一章分布式系统及其任务调度问题1．1分布式系统概述分布式系统是二十世纪九十年代以来计算机领域的研究热点之一。作为网络一体化和并行处理分布化的产物，分布式系统解决了系统透明性及处理机动态分配等问题，表现出比计算机网络更强的生命力和更大的吸引力。一个被大家公认的分布式系统的定义是：“分布式系统是一些独立的计算机的集合。但在用户看来却是一台计算机⋯。”在硬件结构上，尽管所有的分布式系统都是由多个CPU构成的，但可以用不同的方法将硬件组织起来，形成不同的系统，并且不同类别的计算机系统应采用不同的操作

2、系统。分布式系统按照硬件结构的不同可分为四类：总线型多处理机、交换型多处理机、总线型多计算机、交换型多计算机。分类图如下：图1分布式系统分类图分布式系统与集中式系统相比，有其自身的优点。分布式系统有较高的性能价格比，它还可能具有任何价位上的大型机都无法达到的性能。随着计算机的发展，其应用领域越来越广，其中许多应用本身就是分布式的。与集中式系统相比，分布式系统能更好地处理分布式应用。分布式系统的另一个优点是它有更高的可靠性，通过将任务交由多个机器共同承担，单个芯片的故障只会让一台机器停下来，而其他的机器将继续工作。对于一些关键性应

3、用来说，例如控制核反应堆或飞机，使用分布式系统来达到高可靠性是最主要的考虑因素。第一章分布式系统及其任务调度问题并且在负载增加时分布式系统较集中系统更容易扩展。1．2分布式系统中的任务调度问题在单机操作系统中，进程调度是处理机调度的核心。而在分布式操作系统中，与之对应的是任务调度。它是并行处理的关键。其处理过程要求根据一定的调度规则和调度策略，把组成并行程序的一组任务或构成工作负载的一组作业，按照一定的执行时序分配到分布式系统的多个计算节点上，以期获得较好的系统执行性能。分布式操作系统中的任务调度问题对发挥系统的并行性能和保持负

4、载平衡有重大的意义。由于该问题不能在多项式时间内求得最优解，因而被公认为一个NP完全问题”1。在论及任务调度的必要性时，RichardF．Freund等人列举过一个假设具有多层并发度计算需求的计算实例”1。经计算分析表明，“该程序对于普通串行机需要运行100个时间单位，对于向量机需要50个时间单位，而采用由5种机器组成的异构分布式系统，计算过程仅需5个时间单位。显然，后者所付出的代价是，必须进行适当的任务分解、分配与调度。”任务的分解、分配与调度又统称为任务调度问题。近年来，人们提出了大量的任务调度算法。首先讨论一下算法中涉及的

5、几个主要问题。①任务调度的时机根据任务调度的时机不同，一般可分为静态调度、动态调度和混合调度。静态调度是指在并行程序编译时，就决定每个任务分配的处理器及其执行时序。这经常用于任务图比较确定的情况下。动态调度是在并行程序运行过程中，根据当前任务调度及系统执行情况，临时决定每个任务的处理器及起始执行时刻。动态调度主要用于任务图不确定的情况，不可避免地带来一些额外开销。混合调度是介于静态调度和动态调度两者之间的一种调度方法。在编译时先静态调度一部分任务，剩余部分则采用动态调度方法在系统运行过程中给它们分配处理器。②调度目标的实现要求丝

6、三耋坌童苎垒丝丝基丝丝型堡塑墼——从任务调度目标的实现上看，任务调度划分为最优调度和次优调度两类。前者以系统的最优调度为目标，获取系统的最高并行度；后者则追求一种次优调度，以用户要求的时限为标准，达到较高的并行度。因为任务调度问题是一个NP完全问题，要找到一个最优调度算法是很困难的，所以通常采用启发式算法，以得到问题的次优解。③紧迫性任务的响应问题按照调度程序所执行的调度操作是否允许任务抢先执行，可分为抢占式调度和非抢占式调度。如果一个任务一旦占有处理单元，那么它就不能被中断执行，而是必须一直运行完毕后才释放该处理器，这种情形即

7、为非抢占执行方式。由于抢占执行方式所引起的环境切换会增加系统开销，所以一般情况下不采用。④任务迁移问题根据任务是否允许迁移执行，任务调度可分为两大类：第一类是非迁移算法，当一个进程创建时就已决定好它应在的位置。一旦把它放在某台处理机上，它将一直在那台处理机上运行，直到完成。无论它所在的机器负载有多重，也无论有多少其它的处理机空闲，它都不能移动。另一类是迁移分配算法，即使一个任务已经开始运行，它也可以移动。这种迁移策略能更好地平衡负载，但实现起来也非常复杂。⑤容错问题⑥系统的实时性要求这几个因素并不是相互独立的，而是互相联系，相互

8、影响的。通常在设计一类分布式系统的任务分配方案时，要综合考虑几个方面的因素。比如实时分布式系统是一类很重要的系统，而容错问题也是设计其任务调度策略时必须考虑的一个方面。1．3任务调度问题的研究现状1．3．1任务调度问题的传统算法应用遗传算法解决任务调度之前的算法