分布式环境下任务调度探讨

摘要：在信息处理与自动控制飞速发展的今天，分布计算的重要性日益提高，应用领域不断拓宽，而任务调度是分布计算研究中的一个关键问题。该文介绍了分布式计算的优势，分析了任务调度的类型，最后提出了一种基于分布式环境下的实时任务调度算法。

关键词：分布式；任务调度；实时；算法

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)19-4715-02

随着计算机技术的不断发展，计算机应用领域不断扩大，分布式计算越来越重要，分布式适时系统应用也越来越广，任务调度是分布式适时系统中一个非常关键的问题。在任务调度过程中要考虑的任务的偏序关系，如何提高效率，怎样进行资源约束等。分布式实时系统的任务调度算法能够并行的处理任务，保证实时任务的可调度性，保持网络的负载均衡。本文介绍了分布式技术，分析了分布式环境下的各种任务调度算法的利弊，最后提出了一种分布式环境下实时任务调度算法。

1 分布式技术概述

分布式计算是计算机技术领域中的一门科学，分布式计算将需要巨大的计算能力才能解决的问题分成许多的小的部分，再将这些小的部分分配给许许多多的计算机进行处理，最后将处理结果汇总得到需要解决的问题的最终结果。分布式计算就是两个或多个软件相互共享信息，通过互联网技术在一台机或多台机上运行，可以调用共享的所有计算机的闲置计算能力，来处理计算量非常大，由单个计算机或个人在能够接受的时间内无法完成的计算。分布式计算可以共享稀有资源，均衡多台计算机上的负载，可以将程序放在最合适运行它的计算机上。

分布式系统是由多个具有计算能力的结点组成，如果不考虑各个节点的性能差异的情况下，各个结点都可以执行相应的任务。分布式系统对用户是透明的，看来起就是普通的系统，只是运行在分布式系统上的每一个自治处理单元都有各自己的物理存储器，而且信息传输延迟不能忽略不计，分布式系统分为共享存储多处理剂，分布存储多计算机两种类型。

2 分布式环境下的任务调度算法

分布式环境之下的任务调度分为任务分配及任务调度两部分。任务分配是分配应用所需求的资源，即分配任务在什么结点上执行。分配决策必须在调度执行决策之前执行。任务调度给出任务占用资源的起止时间，即分配任何什么时候执行。精确的判断任务集的可调度性是在分配任务之后，在系统中各结点上的任务通过调度算法的可调节性方法 来决定任务集是否可调度。

在分布式系统计算环境下，任务调度的主要作用是均衡分布式系统中各结点的负载，提高系统的运行效率。在分布式计算系统中，采用与运算相适应的算法进行任务调度，为了保证任务调度算法的性能，在采用任务调度算法之中，通常会建立任务调度模型。通过采用任务调度模型的大量的模拟分析，寻找符合条件的任务调度优化算法。

分布式任务调度算法没有集中的调度主机，对局部范围内的一些结点的负载进行均衡调节，每个结点与其他一部分结点进行通信。分布式任务调度算法可适用大规模并行分布系统，扩展性能好。但是分布式任务调度算法复杂、较难实现，信息分散，没有全局信息，跟踪程序运行困难。分布式任务调度结构如图1所示。

在分布式环境下，任务调度是为了保持各结点负载均衡，提高系统的效率。根据就绪任务队列的位置、任务调度器的位置以及两者之间的关系，现有分布式环境下的任务调度算法可分为以下4种类型：

1）整个系统中仅有一个就绪任务队列和一个任务调度器。这种算法的优点是任务调度管理简单，容易均衡处理各节点的负载。其缺点是不但对任务的派遣处理需要较多的额外开销，影响运行效率。而且对维护就绪结点及运行任务调节器的结点的可靠性要求高，一旦结点出现问题，整个系统会处于瘫痪状态。

2）整个系统中只有一个就绪队列，但每个计算结点上都有任务调度器。这种算法的优点是对各结点的负载容易进行均衡处理，而且，一个结点出现问题系统造成的问题不大，只是减小了计算能力。其缺点是对就绪队列操作要花费额外的系统开销，影响系统运行效率，而且维护就绪任务队列的结点必须具有很高的可靠性。

3）整个系统中的每一个计算节点上都有就绪队列及任务调度器。这种算法的优点是就绪队列及任务调度器分散在每一个计算结点上，结点出现故障时不会造成对整个系统较大的影响，只是减少了该节点的计算能力。但该算法的缺点也是非常明显的，因为将本结点的计算任务调度到其他结点上运行，对结点间负载均衡问题难以控制。

4）整个系统中的每个计算结点上都有就绪任务队列，但只有一个任务调度器。这种算法需要很大的额外系统开销，不具有实用价值，在此不再多论。

3 一种分布式环境下实时任务调度算法设计

在分布式环境下的实时系统可分为静态实时系统和动态实时系统两种。静态实时系统是在任务运行之前就调度好了的，在执行任务时，只需要到表中查找该如何调度任务，如何执行操作就可以了。动态调度是在运行期间根据具体的情况进行调度。动态调度要求比较严格，大多数系统采用静态实时调度。本文所设计的实时调度算法也是采用静态实时调度。在前面已经介绍了分布式任务调度分为任务分配与任务调度两个部分。

在任务分配设计时要将更多的处理任务分配到计算能力强的节点上；若某个节点的负载很大时，不再调度其他任务到该节点。本文所设计的静态实时算法中，为了适应系统的实时要求，采用已有的速率单调调度算法对任务进行调度。本文所设计的分布式实时任务调度结构框图如图2所示，它包括任务分配、任务调度两个部分。实时任务分配部分主要完成任务集的读取，任务分配采用加权轮转调度算法将任务分配到各个结点。实时任务调度部分在系统中的每一个结点上执行，根据各个结点能力不同调度不同的任务，按速率单调算法进行优先级别分配，然后按照优先级别的高低调度启动各个任务，并执行任务。在任务分配器中的任务可抽象为包的形式存在，各项任务以包的形式发送到任务调度部分，在各节点上打开任务进行调度。该分布式实时任务调度算法可以简单的理解为：利用加权轮转调度算法的策略对预定义的任务集合理的分配到各个结点中，再利用基于优先级的调度策略对各结点中的任务进行调度。

在实时任务调度过程中每个任务的处理过程可以采用下在伪代码进行描述：

Task n(Task中的任务)

{If (true)

{等待任务触发；

执行任务处理函数；

下一次执行时间=触发时间+最小时间间隔;

等待下一次执行时间；

}}

4 结束语

分布式环境下的任务调度技术是计算机技术中的一个非常重要的技术，在计算机领域应用越来广泛。分布式环境下的任务调度能使系统中各结点负载均衡，提高系统的运行效率。本文介绍了分布式技术，分析了分布式环境下的四种任务调度算法，最后提出了一种分布式环境下实时任务调度算法。文中所设计的实时任务调度算法中采用的加权转调算法通常应用在网络中进行任务调度且加权转调算法在实际应用中比较成熟。任务分配阶段采用速率单调调度算法，可以使负载均衡，实现了分布式实时系统中任务的执行。文中所提出的该静态实时任务调度方案有效的提高了系统的利用效率。

参考文献：

[1] 孟宪福.分布式环境下任务调度模型研究[J].大连理工大学学报,2006,46(6):920-925.

[2] 孙芳,陈后金,张敏.分布计算环境下任务调度双的研究[J].计算机与数字工程,2006,34(2):47-49.

[3] 何琨,赵勇,陈阳.分布式环境下多任务调度问题的分析与求解[J].系统工程理论与实践,2007,27(5):119-125.

[4] 余科军.分布式实时系统任务调度算法的设计和实现[D].四川大学,2006.

[5] 谭宜勇,王锐,范玉顺.分布式工作流中的自适应实时任务调度方法[J].计算机集成制造系统,2010,16(9):1887-1895.

[6] 刘侃侃.一种用于异构环境中任务调度的高效算法[J].计算机系统应用,2010,19(11):102-105.

[7] 余科军,蒋毅.分布式实时系统任务调度算法的设计和实现[J].中国测试技术,2008,34(6):69-72.

[8] 顾学民.分布式制造环境下的作业调度研究[D]:西北工业大学,2005.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文