邓见光 潘晓衡 袁华强

(1．东莞理工学院 工程技术研究院，广东东莞 523808;2．华南理工大学 计算机科学与工程学院，广州 510006)

网格计算技术及其任务调度策略研究

邓见光1，2潘晓衡1袁华强1

(1．东莞理工学院 工程技术研究院，广东东莞 523808;2．华南理工大学 计算机科学与工程学院，广州 510006)

对网格计算技术及其任务调度策略进行了论述与总结。首先介绍了网格计算技术的起源和网格系统应具备的基本条件，然后论述了网格计算不同于传统分布式计算的独特特征，接下来对网格计算的应用领域进行了简单探讨。最后从网格任务调度的特点、评价指标以及现有的调度算法等方面对网格计算的任务调度策略进行了详细讨论。全文工作将指导我们未来进一步深入研究网格计算。

网格计算;分布式计算;任务调度;负载均衡

目前关于网格计算的研究已经取得了很大的进步，然而其还没有一个能够被普遍认可的定义。Foster等人指出，网格是一种由软、硬件构成的基础设施，它支持一种一致、可靠、普遍和廉价接入的计算能力［1］，旨在于动态异构的虚拟组织之间实现资源共享和协同解决问题。具体来说，网格系统应同时满足三个条件，首先，其应在非集中控制的环境中协同使用资源;其次，网格系统必须使用开放、标准、通用的协议以及接口;最后网格系统应提供非平凡的计算能力和服务质量。

网格系统是一个分布式的计算环境，它集成了世界上众多的闲置资源，实现了网络上所有计算的连通和资源的共享，有效地突破了过去强加在单个计算资源之上的计算能力以及地域的限制;其通过充分协同利用世界范围内闲置的计算资源，实现真正意义的资源共享与协作，从而为人们提供一种全新的方式来使用计算资源和解决复杂问题。

1 网格的特点

网格计算系统具有许多独特的特点［2］，这些特点主要表现在以下方面。

1.1 网格资源的分布和共享

网格计算资源跨越的地域较广，涉及的规模巨大，因此其是一种分布式计算。网格资源的分布性使得其必须解决好资源分配、任务调度、安全通信、实时性保障等问题。另外，网格资源虽是分布式的，但它们却可以充分共享，网格系统的资源可以提供给任一个网格用户。资源共享是网格计算的目的，也是网格计算的核心内容。这里的共享包括计算资源、数据库、仪器设备以及人力资源等各类资源的共享。

1.2 网格资源的自治与统一管理

网格资源由分布在互联网中分属于不同组织或个人的资源构成。网格资源首先属于资源的所有者，资源所有者对其资源具有自主管理权，这即是网格资源的自治性。此外，网格资源也必须接受网格系统的统一管理，否则不同的分布式资源就无法建立联系，更无法实现资源的共享协同。因此，网格一方面允许网格资源的所有者对其资源进行自主管理，另一方面又要求网格资源必须接受网格系统的统一管理。

1.3 自相似性与资源异构

网格的自相似性表现在网格的局部与整体相似，网格的自相似性在构建和研究网格时具有重要意义。与自相似性相对应的是网格资源的异构性，这表现在网格资源不仅体系结构各异，而且类型复杂。网格资源不仅包括各类计算能力各异的计算机，而且包括各种类型的数据库、仪器设备甚至人力资源。将这些异构的计算机系统和类别不同的资源进行统一管理，解决相互之间的通信和互操作问题，共同协作完成各类任务要求是网格计算技术的一个重要研究课题。

1.4 网格环境的动态性

由于网格资源是分布自治的，因此网格环境具有动态性。某一时刻网格拥有的某一资源或功能在下一时刻就可能出现故障或者不可用，而原来没有的资源随着时间推移可能会随时加入网格环境。网格管理必须解决好资源的动态性问题，当网格资源动态减少或出现故障时，网格应能够及时采取措施，实现任务的自动迁移，尽可能减少用户损失;网格资源的动态增加则要求网格具有可扩展性，即应允许新的资源随时加入网格，并可以和原有资源融合在一起，共同发挥作用。

2 网格计算的应用领域

网格计算的应用领域非常广泛。概括来说，网格计算目前主要应用在分布式超级计算、分布式仪器系统、高吞吐率计算、数据密集型计算、远程沉浸和信息集成等领域。

分布式超级计算是指将分布在不同地点的各类计算资源用高速网络连接起来，形成比单台超级计算机强大得多的计算系统。目前许多复杂问题在任何一台超级计算机上都无法完成其计算任务，网格系统可以把分布在世界各地的闲置资源集中起来，协同解决复杂的大规模问题。

分布式仪器系统是指基于网格来管理分布在世界各地的贵重仪器设备，通过网格计算环境提供一种远程访问仪器设备的手段，从而在方便用户的同时提高贵重仪器设备的利用率。

高性能计算主要关注系统的计算速度和效率，而高吞吐率计算和高性能计算不同，它主要关注一个较长时间段内系统所完成的总任务量。实际应用中，许多问题对计算速度要求并不高，但对系统整体的吞吐率要求则比较苛刻。网格可以将大量闲置的计算资源集中起来提供给那些对时间不敏感的问题，共同完成大量计算，实现较高的系统吞吐率。

当用于数据密集型计算时，网格更侧重于数据的存储、传输和处理。许多高能物理实验、航空航天计算、天气预测等都属于数据密集型计算问题。对于该类问题，数据的采集、处理、分析、存储，以及可视化设备的安置等往往是分散的，求解该类问题往往会产生很大的通信和计算需求。网格系统通过集成众多分散的闲置资源可以很好地求解这类问题。

远程沉浸共享一个集中的虚拟环境，该环境可以是对场景或问题的真实反映，也可以是一个纯粹的虚构空间，显然这是网格在信息集成领域的一个典型应用。此外，网格技术还可以应用于科学研究领域。例如，应用于生物医学，网格能够为药品研发提供强大的计算能力;运用于工程领域，基于网格可以进行复杂的仿真与设计;运用于数据搜集分析，使用网格可以存储和处理各种海量数据信息，等等。

3 网格计算的任务调度策略

如何使网格充分发挥作用，使应用获得最大性能，这是网格任务调度策略要解决的问题。本节对网格任务调度的特点、评价指标以及现有的网格任务调度算法进行讨论。

3.1 网格任务调度的特点

在网格中，大量任务共享各种网格资源，网格资源的动态性、异构性和多样性使得网格任务调度要比传统高性能计算复杂得多。网格任务调度策略应建立随时间变化的性能预测模型，模型应能够根据网格的动态信息来预测网格性能的波动。此外，网格任务调度还要考虑调度算法的可移植性、可扩展性、调度效率、可重复性以及网格调度和本地调度之间的相互影响等一系列问题。总的来说，网格任务调度具有平台异构、规模大、非集中、不干涉网格节点的内部调度、可扩展以及动态自适应等特点［2］。

3.2 网格任务调度的评价指标

网格调度的目标是实现对大量用户任务的最优调度，提高网格系统的总体吞吐率。具体来说，网格任务调度的性能可从总执行时间、负载均衡性、服务质量以及经济性原则等几个方面来进行衡量。任务总执行时间越小说明调度策略越好，任务调度的一个重要目标就是希望得到最小的总执行时间。负载均衡是指网格系统中各资源之间的负载平衡情况，一个优秀的调度方案应使各类网格资源都充分发挥作用，最大限度地利用网格资源，使任务尽可能快地完成。另外随着网格服务逐步由无偿演变为付费，任务调度也必须考虑其经济性，合理的任务调度策略应在保证一定服务质量的同时，尽可能地减少用户开支。

3.3 网格任务调度算法

目前已有的任务调度算法众多，根据调度算法的执行时间，可将其分为静态调度和动态调度两大类［3］。静态调度是指所有网格任务与计算资源之间的映射关系在执行调度之前即全部确定;动态调度与静态调度不同，其部分任务到计算资源的映射关系在调度执行期间才根据具体情况确定下来。下面分别介绍。

3.3.1 静态任务调度

目前 常 用 的 静 态 调 度 算 法 有 OLB［4］、MET［5］、 MCT［6］、 Min-min［7］、 Max-min［8］、 Duplex［9］、GA［10］、SA［11］以及蚁群算法［12］等。

OLB(Opportunistic load balancing)即机会负载均衡，这是一种典型的静态调度算法。其做法是把任务随机地分配给下一个就绪机器;若同时存在多个就绪机器，就把任务随机地分配给其中的一个。该算法简单直观，然而其不考虑任务的执行时间和机器的期望完成时间，因此可能会导致较大的时间跨度。

MET(Minimum execution time)即最小执行时间，它总是将任务指派给执行最快的机器，因此可以保证每个任务都花费最少的执行时间，然而同时也容易导致大多数任务总是在几个性能最好的机器上执行，使得计算资源之间负载不均衡。

MCT(Minimum completion time)即最早完成时间，该算法总是将任务分配给具有最早完成时间的计算资源，它可以保证调度的任务尽快执行结束和计算资源负载均衡。然而由于该算法并非将任务指派给执行最快的机器，因此可能会增加全部任务的最大完成时间。

Min－min算法首先计算每个任务在各个机器上的期望完成时间，获得每个任务在所有机器上的最早完成时间，然后将具有最小最早完成时间的任务指派给相应的机器;指派后更新对应机器的就绪时间，并将已指派的任务从任务集中删除。重复上述过程，直至全部任务调度完毕。Max－min算法与Min－min类似，其区别在于Max－min首先调度长任务，即首先调度具有最大最早完成时间的任务。

Duplex算法是Min－min与Max－min的结合，其对两者进行比较，并选择调度效果较好的方案执行任务调度。Duplex算法在Min－min和Max－min二者中的任意一个执行效果较好的情况下即能够得到不错的调度性能。

遗传算法 (Genetic algorithm，GA)将问题的解构造成染色体，并基于染色体的进化来求取问题的最优解。算法根据适者生存法则，首先构造一群染色体，然后基于某种适应度函数从中选择能够较好适应环境的若干染色体进行复制，并通过交叉、变异操作产生新一代能够更好适应环境的染色体群。迭代上述过程，通过不断进化，最后将染色体群收敛到一个最适应环境的个体上，即问题的最优解。

模拟退火算法 (Simulated Annealing，SA)来源于固体的退火原理。固体加热时，其内部粒子随温度升高逐渐变为无序状，固体冷却时粒子渐趋有序，并在每个温度都达到平衡态，最后在常温时达到基态，内能变为最小。用固体降温过程模拟任务调度问题，将内能E模拟为目标函数值f，温度T描述控制参数t，即得到求解任务调度问题的模拟退火算法。由初始解i和控制参数初始值t开始，对当前解重复“计算新解→计算目标函数值→接受或拒绝”的迭代过程，逐步减小t值，迭代终止时即得到调度问题的解。

蚁群算法通过模拟蚂蚁觅食行为来进行问题的求解。蚂蚁觅食时会在其经过的路径上释放一种信息素，其他蚂蚁会感知到这种信息素的存在并选择信息素多的路径通过，而信息素随着时间延长会逐渐挥发。初始阶段，所有路径上的蚂蚁数量相当，随着时间的延长，较短路径上的信息素增加较快;接下来其他蚂蚁选择较短路径通过的概率增大，最终所有的蚂蚁都将选择最短的路径通过。蚁群算法具有并发性和可扩展性，将某一时刻所有影响网格资源状态的因素都由信息素来描述，即可快速求解网格任务调度问题。

除了上述算法，静态的网格任务调度算法还有很多，如结合了GA和SA的遗传模拟退火算法 (Genetic simulated annealing，GSA)［13］、启发式的 A*算法［14］、基于解空间搜索的 Tabu 算法［15］等等。

3.3.2 动态任务调度

现有的动态调度算法可分为在线模式 (On－line mode)和批模式 (Batch mode)两大类［16］。在线模式是指当调度器收到一个任务时立即为其指派计算资源;而在批模式下，调度器收到一个任务后并不立即为其分配计算资源，只有当到达任务组成一批并且影射事件到达后，调度器才为这些任务指派计算资源。

常见的在线模式调度算法有MCT、MET、OLB、SA、KPB等算法。其中MCT、MET、OLB的做法和静态调度类似。SA算法 (Switching algorithm)基于应用负载在计算资源间的分布情况，周期性地使用MCT和MET算法实施调度，因此SA算法同时具有MCT和MET的特点。K最优调度 (K－percent best，KPB)在执行调度时仅考虑部分可用的计算资源。设M为可用资源数目，K满足100/M≤K≤100，则1≤KM/100≤M。KPB算法从全部可用资源中选取KM/100个参与任务调度，算法每次将任务指派给具有最小完成时间的机器。显然，如K=100，则全部机器参与调度，此时KPB算法等同于MCT算法;如果K=100/M，则仅一台机器参与调度，此时KPB算法等同于MET算法。

常见的批模式调度算法有Min－min、Max－min、快速贪吃算法、最大时间跨度算法等。其中Min－min、Max－min的做法和静态调度类似。快速贪吃算法根据到达顺序依次从当前批中选择任务，并计算该任务的期望执行时间;然后将当前具有最小期望完成时间的计算资源指派给该任务。最大时间跨度算法不保证当前调度最佳，但其未来调度趋势趋于最佳。算法首先依次找出当前批任务中每个任务的最小最早完成时间和次小最早完成时间及各自对应的计算资源;然后计算每个任务的次小最早完成时间和最小最早完成时间的差，即时间跨度;最后选取时间跨度最大的任务进行调度。如此重复，直到当前批任务全部调度完毕。

综上，对网格任务调度算法进行了详细介绍。其中，静态调度算法相对简单，算法开销小，对数据的依赖性不高;尽管如此，该类算法实时性不高，并且可能会导致资源负载不均衡。与静态算法相比，动态调度能够有效处理计算资源的负载评估、作业选择以及任务迁移等问题，因此动态调度算法能够较好地保证负载均衡，但同时动态调度算法需要付出较高的系统开销。

4 结束语

本文对网格计算技术及其任务调度策略进行了探讨。网格计算是针对复杂的科学计算问题而产生的一种新型计算模式，由于网格计算资源分散在世界各地，其资源的动态性、异构性和多样性使得网格任务调度问题要比传统高性能计算复杂得多。网格任务的调度策略应具有动态自适应性，此外调度算法还应综合考虑可移植性、可扩展性、服务质量、负载均衡以及网格调度和本地调度之间的相互影响等问题。根据上述指标，本文对当前现有的网格任务调度算法进行了深入而详细的讨论。本文工作将为我们未来对网格计算技术进行更深入的研究奠定基础。

［1］徐志辉，陈渝，刘鹏．网格计算［M］．北京：清华大学出版社，2002．

［2］罗红，慕德俊，邓智群，等．网格计算中任务调度研究综述［J］．计算机应用研究，2005，22(5)：16－19．

［3］Tracy D B，Howard J S，Noah B，et al．A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems［J］．Journal of parallel and distributed computing，2001，61(6)：810 － 837．

［4］Noriyuki F，Kenichi H．A comparison among grid scheduling algorithms for independent coarse－grained tasks［J］．Proceedings of the 04’symposium on applications and the internet－ workshops，2004：674 －680．

［5］Richard F，Michael G，Stephen A，et al．Scheduling resources in multi-user，heterogeneous，computing environments with smartnet．Proc［M］．of the 7thIEEE heterogeneous computing workshop．1998：184－199．

［6］徐志伟，冯百明，李伟．网格计算技术［M］．北京：电子工业出版社，2004．

［7］Liu Jue-fu，Li Gang．An improved Min-min grid tasks scheduling algorithm based on Qos constraints．Proceedings of the 2010 int［M］．conference on optics photonics and energy engineering．2010：281－283．

［8］Muthucumaru M，Shoukat A，Howard J，et al．Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems［M］．Proceedings of the 8thheterogeneous computing workshop．Washington，USA，1999：30 －44．

［9］Cheng S T，Hsieh M T，Chen B F．Fairness-based scheduling algorithm for time division duplex mode IEEE 802．16 broadband wireless access systems［J］．IET communications，2010，4(9)：1065 －1072．

［10］Vincenzo D，Marco M．Scheduling in a grid computing environment using genetic algorithms．Proceedings of the 16th international parallel and distributed processing symposium［M］．Florida，US，2002：235 －239．

［11］Ajith A，Rajkumar B，Nath B．Nature＇s heuristics for scheduling jobs on computational grids．Proc．of the 8th international conference on advanced computing and communications［M］．Cochin，India，2000：45 －52．

［12］Xu Zhihong，Hou Xiangdan，Sun Jizhou．Ant algorithm －based task scheduling in grid computing．Proc［M］．of the IEEE Canadian conference on electrical and computer engineering，2003：1107 －1110．

［13］Marco A C，Abelardo R，Erika Y A，et al．Genetic － annealing algorithm in grid environment for scheduling problems［M］．Security － Enriched Urban Computing and Smart Grid，Springer Berlin Heidelberg，2010．

［14］Chow K，Liu B．On mapping signal processing algorithms to a heterogeneous multiprocessor system［J］．Proc．of the 1991 international conference on acoustics，speech，and signal processing，1991(3)：1585 －1588．

［15］De Falco I，Del Balio R，Tarantino E，et al．Improving search by incorporating evolution principles in parallel tabu search［J］．In IEEE Conference on Evolutionary Computation，1994(2)：823 －828．

［16］丁等，陈国良，顾钧．计算网格环境下一个统一的资源映射策略［J］．软件学报，2002，13(7)：1303－1308．

Grid Computing Technology and Its Task Scheduling Strategies

DENG Jian-guang1，2PAN Xiao-heng1YUAN Hua-qiang1
(1．Engineering ＆ Technology Institute，Dongguan University of Technology，Dongguan 523808，China;2．School of Computer Science ＆ Engineering，South China University of Technology，Guangzhou 510006，China)

The grid computing technology and its task scheduling strategies were discussed and summarized in detail in this paper．First，we introduced the origin of grid computing and the basic requirements which the grid system must be satisfied．Then we focused on the particular characteristics of grid computing that were different from the traditional distributed computing system，and briefly discussed the application fields of grid technology．Finally，the grid task scheduling strategy was discussed especially，which included the scheduling characteristic，the evaluation criterion，and the existing scheduling algorithm．The paper will be the guideline for our future study on grid computing．

grid computing;distributed computing;task scheduling;load balance

TP399

A

1009－0312(2012)01－0030－05

2011－06－30

国家自然科学基金 (65073145);广东省科技计划项目 (2011B061300103);东莞市科技计划项目 (201010814006);东莞理工学院自然科学青年基金 (2010ZQ10)。

邓见光 (1981—)，男，河南商水人，助理研究员，博士生，主要从事海量存储技术、虚拟现实技术研究。

科学计算作为继理论推导、科学实验之后进行科学研究与知识发现的第三种手段，已经成为更好的认识世界的工具。随着科学研究的不断深入，人们迫切需要性能更高、速度更快的计算机系统。目前，网络技术飞速发展，网络带宽日益提升;另一方面，随着个人计算机系统的计算能力不断提高，产生了大量的闲置计算资源。在这种背景下，一种新型的基于异构、动态、跨域的协同资源共享和问题求解方式应运而生，这即是网格计算。网格可以把各种孤立的闲置计算资源通过互联网连接起来，形成一个虚拟的超级计算机系统，其致力于为终端用户提供与具体地理位置和计算资源无关的通用计算能力。网格的美好前景吸引了大量的研究人员投入其中，目前它已成为信息学科最热门的研究方向之一。

book=0,ebook=111