网格工作流调度

网格工作流调度（精选7篇）

网格工作流调度篇1

0 引言

网格中集成了大规模、分布和异构的资源,为进行科学研究提供了一个全球性的基础设施[1]。很多科学研究机构,从高性能物理、地球物理学、天文学到生物学,都在利用网格来共享、管理和处理大规模的数据集。为了支持复杂的科学实验研究,需要协作分布的资源诸如计算设备、数据库和科学设备等来共同完成。可以通过引入工作流技术来解决这一问题。

网格工作流[2]可以看作是一组任务的集合,任务之间存在着时序或因果的约束条件,并最终完成一个特定的目标。网格工作流和传统的工作流之间具有很大的差别,如基于虚拟组织的工作方式;网格资源的动态性导致网格的计算和处理能力随时间变化,应用性能估计困难;资源异构以及跨管理域等。

调度是网格工作流中最重要的课题,它不仅仅影响网格工作流的执行成功与否和效率的高低,同时也涉及到网格工作流的资源管理情况。网格工作流的调度不同于一般的任务调度,在调度时不仅要考虑为任务选择一个最佳的资源,还要考虑各个任务之间的时序或因果的约束条件,以及协调各个任务的执行来获取最终的执行结果。目前针对网格工作流调度的研究主要集中于下面几个方面:(1)调度策略和调度算法的研究;(2)具体的网格工作流系统和项目中的调度机制;(3)服务网格下的工作流应用及调度。

1 网格工作流调度的相关知识

1.1 调度的体系结构

网格工作流调度器的架构对于工作流系统的可扩展性、自动组合、服务质量以及性能保证具有重要作用,工作流调度器架构分为集中式、分层式和分布式三种[2]。

在Pegasus[9]系统中采用了集中式架构,这种架构的中央调度器负责生成所有任务的调度计划,它为工作流中所有的任务选择和分配资源;对于分层的调度架构,则由一个中央调度器与多个低级的子工作流调度器组成,中央调度器负责控制工作流的执行,并将子工作流任务分配给低级调度器,中央调度器和子工作流调度器可以使用不同的调度策略。在GridFlow[5,6]系统中,采用了这种体系结构;Triana [4]则采用了分布式调度架构,这种架构存在多个调度器但不存在中央调度器,各调度器相互通信完成工作流任务的执行。

可以看出,集中式调度能够获取工作流中所有任务的信息和所有可用资源的信息,因此能够生成有效的调度方案,但是扩展性差,容易产生单点失败,同时也不能较好地适应网格环境的动态性和分布性;分层的调度架构在一定程度上提高了调度的可扩展性、分布性,但因为存在中央调度器,同样存在单点失效的缺点;分布式调度虽然具有良好的扩展能力,但是难以产生可以考虑全局性能的调度方案。

1.2 资源性能估计

网格系统的资源性能估计分为两类:预测性的和非预测性的。

非预测性的资源性能估计只是使用当前任务和资源的状态信息,而无需考虑历史的信息,该方法又分为启发式方法(基于任务和资源的特征)和概率分布方法(基于对期望任务特征的离线统计分析)。

预测性的方法为了估计状态需要考虑当前和历史的信息(如应用以前的运行周期),又可分为启发式方法、价格模型方法和机器学习方法。GridFlow[5,6]使用了启发式方法来预测的资源性能,通过使用预定义的规则基于网格应用的某些期望的行为来指导资源性能预测:在价格模型的方法中,考虑资源的可用性和资源的需求等市场动态来对资源进行买卖交易;在机器学习的方法中,使用在线和离线的学习方案利用潜在的未知的分布来进行资源性能预测。

启发式或基于统计的技术既可用于预测性也可用于非预测性的资源性能估计。文献[10]提到的Myopic算法则使用了基于统计的技术来预测资源的性能。

1.3 调度策略

网格工作流的调度策略分为静态调度和动态调度两种。

静态调度是在工作流建模时就绑定相应的资源,如果绑定的资源在运行时无法获得则会造成任务的暂停和中断,而在运行环境中如有类似功能的资源也不能得到利用,因此静态调度的方法效率较低,容易造成任务运行的失败。因此采用这种调度策略的应用很少。

动态调度是在建模的时候不绑定具体的资源,而是绑定资源的描述,因此在调度时能够根据运行的实际情况,利用合适的资源来执行任务,效率较高。

在动态调度策略中,根据调度时机的不同,又可以分成全局动态调度和实时动态调度。全局动态调度是指在调度发生时,为工作流的所有任务一一指定好资源,文献[9,11,12,13,17,18,19]都是基于该调度策略进行工作流的调度;而实时动态调度,则是调度发生时,仅为当前的任务选择一个最佳的资源,直至工作流应用的完成。显然,实时的动态调度更加适应网格环境中资源的动态性,但是需要实时地获取资源的信息,为资源的选择提供依据,文献[10]提出了一种实时的调度算法Myopic,但只能调度简单的工作流。Triana[4]系统也提供了简单工作流的实时动态调度策略。

2 工作流调度算法的研究

现在大部分针对工作流应用的调度研究是基于有向无环图DAG(directed acyclic graphs)的调度,即把工作流应用描述成一个有向无环图G=(V,E)。V表示图中的所有节点(node),即工作流中的所有子任务;E表示图中的有向边,代表任务之间控制依赖关系(ControlLink)及数据依赖关系(DataLink)。

基于图的调度是一个NP难问题,很难求得精确解,目前的研究大都是采用一些启发式算法来解决调度问题,如贪心算法、列表调度算法和遗传算法等。

2.1 基于遗传算法的工作流调度

遗传算法是将问题的求解表示成染色体,从而构成一群染色体。将它们置于问题的环境中,根据适者生存的原则,从中选择出适应环境的染色体进行复制,通过交叉、变异产生出新一代更适应环境的染色体群,这样一代一代地不断进化,最后收敛到一个最适合环境的个体上,求得问题的最优解。

遗传算法实际是一个动态规划算法,可很好地解决组合优化问题。借助遗传算法可以为工作流应用中所有任务选择一个满足指定约束条件的资源集。

在文献[9,17,18,19]中,作者分别基于遗传算法进行任务与资源的映射,并通过实验验证了算法的有效性,其中文献[17,19]的作者改进了算法,定义了三种收敛判据,并采用最优保存策略实现了跨代保留,避免了算法存在的过早收敛问题,提高了调度性能,缩短了工作流执行的时间;文献[18]的作者考虑了服务质量约束,在使用遗传算法进行调度的时候,是以任务之间的服务质量约束条件为依据来选择资源的。

2.2 基于HEFT算法的工作流调度

HEFT[10]算法是一种列表调度算法,使用时包括三个步骤:(1)为工作流图中的节点和边赋权值;(2)按权值排序生成一个有序的任务列表;(3)映射,为任务分配资源。

任务节点权值是基于预测任务的执行时间来计算获取的,边的权值则是通过预测资源间数据传输的时间来计算的。在异构的环境中,在不同的资源上同一任务的预测执行时间是不同的,在不同的数据通信链路上预测数据传输时间也是不同的。针对不同的应用环境,有很多近似计算方法(如取算术平均值)来提供不同程度的精确值。

排序阶段是为每一个任务节点设置一个序列值,该值的大小包括当前节点的权值和所有前序节点的执行时间。所有的可用资源根据某种目标函数获取一个性能值,它们以非递增的顺序安排在资源列表中。在映射时,对于每一个任务,将为其分配能够提供最早执行时间的资源。

文献[11,12,13]改进了HEFT算法,其中文献[11]为该算法加入了回退(Backtracking)机制,可以更好地调度执行含有并行子任务的工作流应用,文献[12,13]以不同的方式使得HEFT算法支持预留资源,保证了某些实时性要求高的工作流的执行。

2.3 其他调度策略和算法

并行调度的引入,可以大大缩短工作流的完成时间。并行不仅指工作流中本身存在的并行子任务,还指某一子任务内在的并行性。文献[15]提出了一种预调度的调度策略,考虑了某些子任务内部的并行性,通过将其分解(事先为该类子任务设定了数据依赖点,并预测了该任务的调度时间和完成时间),使其能够与其他子任务并行执行,从而加快了工作流的执行。文献[14]在多集群的应用环境中,提出了一种双层工作流调度方法。AWS(Adaptive Workflow Splitting)算法将用户提交的工作流应用分解成多个子工作流;每个子工作流在分配的集群上采用PFAS(Performance Fluctuation Aware Scheduling) 算法为每一个子工作流中的任务分配最佳的资源。

对于一些实时性要求比较高的工作流应用,可以借助资源预留来保障资源的获取,加快工作流的执行。文献[12]通过对网格资源建模,将网格环境描绘成一个图,图中的节点表示计算资源,边表示网络资源,并通过改进HEFT算法使得支持并行性和资源预留,提出的HEFTSync和HEFTSyncBT算法能够为复杂的网格工作流分配和预留资源;文献[13]基于HEFT算法进行调度,为了支持资源预留,在利用HEFT算法进行资源映射时,不再提供有序的资源列表,并且增加了预留阶段,从而使得调度器可以为每个任务预留资源。

2.4 调度算法的性能分析及小结

遗传算法和HEFT算法的性能比较已在文献[10]中通过实验加以比较。对于平衡性较好、存在大量并行子任务的大型工作流应用,HEFT算法的性能要优于遗传算法。对于大而复杂的工作流,使用遗传算法时,当求解到一定范围时往往会做大量无为的冗余迭代,导致调度时间很长,调度性能不佳。对于平衡性差的工作流应用,遗传算法显示出较好的调度性能,因为它不需要为每个节点和边计算权值。

通过分析可知,现有的调度策略和调度算法存在如下的问题:

(1) 或者是针对某一类工作流的应用来设计的,或者仅仅是理论上提出的设想,或者运行在某一特定的环境中,有很强的针对性。

(2) 强调了算法要适应网格环境中的资源具有异构性和动态性,但在具体算法设计的时候却是假定资源的信息是可以实时获得的,并没有提出一个切实可行的方案来实时获取资源的动态信息。

(3) 资源的分布性、动态性和自治性势必导致工作流执行的不稳定性,针对这一问题,现在还不存在一个实时动态的带有容错机制的调度算法。

3 网格工作流调度系统

当前的网格工作流项目和系统主要有以下几种:

(1) GridFlow系统

GridFlow[5,6]使用的调度体系结构是分层式结构,采用有向无环图DAG来表示工作流,并使用了局部调度决策机制,采用了一种性能驱动的动态调度策略,数据以对等的方式传输。系统采用的容错技术是资源替换,采用分析模型对资源的性能进行估计。

系统包含全局网格工作流管理系统和局部网格子工作流系统。其中全局层提供模拟、执行和监控整个工作流的功能,而每个局部网格处理子工作流的调度和冲突。网格工作流全局管理器用广域网格工作流调度算法(GGWM)得到一个流程中子流程的最佳调度方案;局域网格子过程调度器则负责通过局域网格工作流调度算法(LGSS)解决局部网格资源的冲突问题,得到一个子流程中任务的最佳调度方案。

GridFlow系统引入了OGSA定义的标准和接口,并实现了一个性能预测服务来指导调度,但如何提高系统的安全性以及加强各种服务之间的协作还需进一步研究。

(2) Pegasus系统

在Pegasus[9]中,使用的调度体系结构是集中式结构,采用有向无环图DAG来表示工作流,并同时使用了局部和全局调度决策机制,采用了一种性能驱动的动态调度策略,数据以中间传输的方式传输。系统采用的容错技术是重试,并采用基于历史数据的方式对资源的性能进行估计。

早期的Pegasus系统采用一种静态调度算法来调度执行工作流应用。为了支持实时的动态调度,Pegasus系统增加了一个新的组件-分割器,用来将用户提交的抽象工作流分割成若干个子工作流,子工作流间的依赖关系反映了原工作流中任务之间的依赖关系,调度器按照子工作流间的约束条件依次调度执行。

Pegasus系统借助分割器实现了简单的实时调度,在一定程度上提高了调度性能;但是至今还没有设计出一个科学合理的分割算法及具有容错保障的调度算法。

(3) Triana项目

Triana[4]使用的调度体系结构是分布式结构,采用有向无环图DAG来表示工作流,并采用了一种性能驱动的调度策略,数据以对等的方式传输,其容错机制是采取对工作流中各种属性进行配置,比如重试次数、延迟时间以及可选处理器等,不提供资源性能的估计。

Triana是一个服务工作流管理系统,其利用网格技术开发高级中间件以支持人性化的生物实验。Triana引擎可以为任务动态的发现和绑定服务,它的分配策略分为并行执行和对等执行两种,较好地满足了网格环境中资源的动态性。

综上分析,可以发现:

1) 一些系统或项目没有考虑面向服务的网格架构,因此在以网格服务为核心的网格研究中,一些研究成果已不能适应OGSI的要求。

2) 调度系统中使用的调度策略和调度算法单一,缺乏优化,难以满足网格工作流应用的不同需求。

3) 调度系统中绝大部分没有提供对服务质量Qos的支持,并且只提供了基于性能预测的调度策略。对于日益发展的商业工作流应用,调度器势必要更多地考虑用户的Qos需求,考虑成本和安全问题,因此调度策略也将渐渐转向基于市场驱动和信任驱动的调度策略和调度算法的研究。

4 服务网格环境下的工作流调度问题

随着Web服务技术规范WSRF(Web service resource framework)的出现,网格技术和Web服务技术进一步相融合,以服务为基本构成元素的服务网格已经成为网格构建的主流方向之一。网格工作流作为实现网格中资源协同工作的一项重要技术手段,把网格中多个服务包装成一个更大粒度的服务部署在网格中,供其他服务或上层的应用访问。

基于网格环境的各类应用的差异性、动态性,网络应用软件的集约化不仅极大地增加了对核心功能需求的复杂度,而且对软件的可靠性、可维护性、安全性、可控性等非功能性需求也越来越高;同时,网络环境中同时存在着数量众多、功能相同或相近、服务质量等非功能特性各异的服务。根据服务质量等应用需求动态组合服务,实现应用的“按需服务”机制,实现服务间灵活、动态的协作和调度,需要解决如下几个问题:

(1) 基本服务语义描述问题。如果基本服务之间缺乏共同遵守的语义信息,服务之间不能相互识别,更加不能自动地组合和协作。

(2) 缺乏能够灵活、可扩展的动态服务调度模型。利用该模型可以实时地根据上下文环境、约束条件动态地修改或定义服务调度方案。

(3) 缺乏网格服务工作流的实时动态调度算法。由于网格中资源的不确定性,应用的执行常常会因为某些未知的因素而执行失败,所以要求调度算法要具有相应的容错机制,来保障工作流安全顺利地执行。

(4) 在应用层上对多维Qos 的支持。由于网格环境的动态性和不可预知性,Qos 决定服务的可用性和实用性,需要调度系统能够实现由用户的应用Qos 到服务Qos 的映射需求,并将Qos 作为服务调度的一种动态约束条件。

为实现动态的服务组合,可以考虑为服务添加元数据来增加语义的方法,如文献[20]和文献[24]通过使用本体来解决服务资源的异构性问题,从而不同的网格服务间就可以通过语义上的匹配进行动态组合。

为实现实时动态的调度,可以考虑借助数学模型来预测资源的动态信息,借助机器学习或人工智能的方法规划和指导调度。但它们带来的计算复杂度对调度的影响也需要进一步的研究。

在应用层上对多维Qos的支持,可以借鉴文献[18]提出的服务质量感知的工作流调度思想,为每个成员服务和整个工作流建立服务质量参数评价体系,综合考虑了服务的性能、花费、可靠性、完整性、可提供性和声誉。

5 结束语

随着网格技术的发展,科学领域和商务领域涌现了大量网格应用,这些应用大都需要大量的计算资源和其它资源,而且任务的过程也比较复杂,包含很多时间、空间和资源方面的约束条件。利用一般的处理方法,不但效率低下,而且导致某些应用无法完成,必须通过使用网格工作流来对网格应用进行构建、执行调度、管理监控。另一方面,网格环境中资源的异构性、分布性和动态性使得调度执行难以控制,现有的调度算法和调度系统对于复杂的应用来说过于简单,还不能很好地进行实时动态的调度。针对当前流行的服务网格,分析了在服务网格环境进行工作流应用要解决的问题,并就某些问题提出了解决的方法和思路。

摘要：阐述了工作流调度的基本概念和调度的相关知识,分析了目前流行的网格工作流的调度算法的优缺点,并对当前的网格系统和项目所采用的调度机制,从不同侧面对其进行了比较分析。随着服务网格的日益流行,提出了面向服务网格环境下的服务工作流调度,分析了调度中的关键问题,并给出了解决问题的方法和思路。

关键词：工作流,工作流调度,调度策略,服务工作流调度

网格工作流调度篇2

关键词：市场驱动,QoS,任务调度算法,网格工作流

0 引言

在网格环境中调度工作流应用是一个NP完全问题,目前已经提出了许多启发式的调度算法对其进行调度。这些算法所采用的调度策略可分为三类:性能驱动、市场驱动和信任驱动。性能驱动策略的目标是调度系统有效的分配工作流任务到合适的网格资源,使完成整个应用所花费的时间最少。目前,大多数网格工作流调度系统都采用这种策略(如GrADS,Prodan)。市场驱动策略则是在满足用户QoS需求的情况下,使完成整个应用所花费的成本最低。也有一些网格系统采用这个策略(如Nimrod-G)[1]。而信任驱动的策略才提出不久,应用较少。

本文旨在讨论一个市场驱动的网格工作流任务调度算法,即要在用户指定的时间约束范围内,使完成整个工作量所花费的成本最低。

1 问题描述

在网格环境中,不同的第三方提供了许多相似或相等的资源,使用这些资源都可以完成某项任务。但根据服务质量的不同,所需要花费的时间和成本就各不相同。因此,网格用户可以根据他们自身需求选择合适的资源。对于一个网格工作流管理系统,只考虑功能性的需求是不够的,必须考虑不同的QoS需求,如时间约束、成本约束等。目前,对工作流QoS的一般分类如图1所示。

在本文中我们只考虑时间约束。因为对于大部分用户,他们可能并不需要在最短的时间获得最好的服务,而是希望在某个时间期限内能够用最低的成本来完成某个应用。所以,我们提出的任务调度算法的目标就是在满足用户的时间需求的情况下,使完成应用所花费的成本最低。

2 工作流任务调度算法

为了实现上述目标,可以采用分治法来解决任务调度,实现的步骤分为三步:

(1) 资源发现和需求识别[2,3]

对工作流图中的每个任务,使用网格信息服务分别识别所有可用的资源,列出可用资源列表,并对资源按价格进行降序排列;同时获得用户的QoS参数,如时间约束。

(2) 分配时间约束:

将用户给定的总时间期限分配给每个任务网格工作流的流程运转模型分为四类:简单运转模型、发散运转模型、聚合运转模型、特殊运转模型。在本文中只考虑流程的结构为串行、并行发散和同步聚合的情况,如图2所示。

为了讲述问题的方便,也使读者更容易理解,本文后面部分都将以下述流程(图3)为例,对其进行任务调度。

a) 对于串行的情况,我们采用动态规划的方法来分配时间约束

将本文的目标函数描述成静态规划问题,如下:

${\begin{cases} Μ i n c = g_{1} (t_{1}) + g_{2} (t_{2}) + \dots + g_{n} (t_{n}) \\ t_{1} + t_{2} + \dots + t_{n} \leq D \\ t_{i} \geq 0 i = 1, 2, \dots, n \end{cases}$

其中D表示总的时间约束, ti表示分配给单个任务的子时间约束, gi(ti)表示在ti范围内对应的所采用资源的价格,c表示完成该流程所花费的总的成本。

把问题中的变量ti作为决策变量,将累积的量或随递推过程变化的量作为状态变量。设状态变量Si表示分配给任务Ti到任务Tn的子时间约束;决策变量di表示分配给任务Ti的子时间约束,即di=ti;这样就可以得到状态转移方程:Si+1=Si-di=Si-Ti,以及运行决策集合:

Di(Si)={di|0≤di=Ti≤Si}

从而写出动态规划的递推关系式为:

${\begin{cases} f_{i} (S_{i}) = \min_{0 \leq Τ_{i} \leq S_{i}} {g_{i} (Τ_{i}) + f_{i + 1} (S_{i} - Τ_{i})} i = n - 1, \dots, 1 \\ f_{n} (S_{n}) = \min_{Τ_{n} = S_{n}} g_{n} (Τ_{n}) \end{cases}$

利用这个递推关系式进行逐段计算,最后求得f1(D) 即为所求问题的最小花费。

b) 对于并行发散和同步聚合的情况,采用如下准则进行时间约束的分配

准则1:从开始任务到结束任务的每一条支路上的所有子时间约束之和小于等于总的时间约束D。

准则2:并行发散的每个分支所分配的子时间约束相同。如由Task9和Task10组成的分支和Task11的分支具有相同的时间约束。

准则3:分配给每个任务的子时间约束必须大于或等于其最小执行时间。

准则4:根据用三点时间估算法估计出来的时间来分配总的时间约束。

三点时间估算法所涉及的三个时间分别为:最早完成时间a;最可能完成时间m;最晚完成时间b。显然,完成某项任务所需要的上述三种时间都具有一定的概率。根据经验,这些时间的概率分布可以认为近似于正态分布,一般情况下,可按下列公式计算执行时间:T=(a+4m+b)/6。

根据上述准则,就可以将总的时间约束合理地分配给并行发散和同步聚合的任务。

(3) 任务调度

分别为每个任务在其所分配的时间约束的允许范围内选择价钱最低的服务,对这个价钱求和,就得到了完成这个工作流应用的总的花费。该调度算法的伪代码如下:

3 仿真实验及性能评价

GridSim[5]是为R Buyya开发的,是一种基于计算经济模型的网格仿真平台,可以提供时间约束和/或成本约束的调度,能够模拟网格的多方面特性,因此,本文将扩展Gridsim来进行仿真实验。

根据流程的需要,我们模拟了12种类型的资源,每种类型的资源都有4个不同的服务提供者,因服务质量不同,所需要花费的时间和价钱就有所不同,因此我们总共模拟了48个服务提供者。表1仅列出了用GridSim模拟的对Task1的测试资源。

在实验中,我们比较了两种不同的调度算法,一是本文提出的市场驱动的Market-Driven调度算法,二是不考虑约束条件,只要保证完成任务所花费成本最低的Min-Cost调度算法。我们以时间约束为横坐标,分别以所花费时间和所花费成本为纵坐标,对两种算法进行比较。

从图4中可以看出,本文提出的市场驱动的任务调度算法可以在用户时间约束范围内获得局部最优解,以按时抢占市场;而Min-Cost调度算法虽然可以以最低的成本完成某个应用,但所花费的时间却远远超出了用户的需求,这样就有可能导致用户错过市场先机,造成不可估量的损失。

4 总结和展望

本文在充分考虑了用户的QoS需求的情况下,提出了一种市场驱动的、对网格工作流进行调度的任务调度算法。仿真实验结果表明,该算法可以在用户指定的时间约束内完成某个应用,并获得较优的执行代价,能够满足市场的需求。

另外,在本文中只考虑了两种工作流运转模型,也只关注了QoS的一个方面——即时间约束。在未来的工作中,将充分考虑各种运转模型,并研究QoS其它方面对网格工作流任务调度的影响,以进一步改进本算法。

参考文献

[1]Buyya R.Economic-based Distributed Resource Management and Scheduling for Grid Computing.PhD Thesis,Monash University,Aus-tralia,2002,12.

[2]Buyya R,Murshed M.A Deadline Budget Constrained Cost-Time Opti-mize Algorithm for Scheduling Parameter Sweep Applications on the Grid.GridSim Toolkit Release Document,Dec.2001.

[3]Buyya R,Murshed M,Abramson D.ADeadline and Budget Constrained Cost-Time Optimization Algorithm for Scheduling Task Farming Appli-cations on Global Grids.Technical Report,Monash University,March2002.

[4]Wolski R,Plank J,Brevik J,Bryan T.Analyzing Market-based Re-source Allocation Strategies for the Computational Grid.International Journal of High-performance Computing Applications,2001,15(3).

移动网格资源调度算法篇3

随着移动无线网络系统的快速发展,用户在任何地点、任何时间都可以访问全球网络资源。这意味着除了静态结点外,网格系统也应考虑把移动结点包含在内,这种结合所产生的技术就称为“移动网格计算”。它以无缝、透明、安全、有效的方式支持移动用户和资源,是无线技术与网格计算这两种新技术的融合。

在移动网格体系结构(如图1)中定位移动设备的角色,可以考虑两种,一是可作为同网格系统交互的接口,使用者可通过移动设备向网格要求服务,利用网格资源来完成任务,可远程监控任务的执行,并从网格中获得所要求的结果;另一种是把移动设备也作为网格的计算资源,可参与到网格的计算任务中,而不仅仅是网格服务的接收者。因此,移动设备要有效地嵌入到网格中,既可以作为要求网格服务的接收者,也可以作为网格服务的提供者。

目前移动网格资源的选择和分配方法的模型主要有以下六种:

1)基于距离的选择。当有多个网格资源可用时,根据客户端距网格资源的远近,选择较近的资源。必须根据经验数据建立初始值,放入规则库;在运行时记录相关的参数,更新规则库。

2)基于资源的贪心选择算法。根据资源的丰富程度,选择对应用一次性尽量充足可用的资源。

3)基于优先队列的选择算法。将不同的应用请求根据客户的信誉度、应用的类型、紧急程度等进行分类,建立多个优先级队列。调度队列时,分配不同的权重给不同的队列,同一队列采用轮转(round trip)算法,对请求分配资源。

4)根据网格经济的原则,选择代价(网络跳数、时间或金钱等)最小的资源。当有多个因素要综合考虑时,使用加权求和的方式,选择决策值最优的资源。

5)基于协议的选择算法。由于不同的协议对数据的缓冲和交付策略不同,将应用请求按协议划分,比如TCP和UDP,按协议的时间敏感性优先的原则进行调度,对同一协议的请求队列按先来先服务(FIFO)的原则进行处理。

6)基于响应性能的选择算法。根据距离、计算能力、网络带宽等因素进行综合计算,得出预测的响应时间,选择响应性能最好的网格资源。

1 机动模型

一般讲用户的行为或移动设备是很难预言的,该文在移动网格环境中为资源调度提出了一种一般的机动性模型。对于一种移动的资源来说,其状态有两种可能性:一种是移动资源正反向分开,另一种是资源正相向接近。带有其它参数并且参加计算的资源,其移动性要在资源选择过程中重点被考虑。移动性参数用来表示一种资源保持的时间预言。任务分派基于预言的时间。为了区别不同的参数变量的影响,可以使用相似的信号或者资源的位置意识。本文对资源位置意识进行了解释,每种资源在任何瞬间都知道它的单元信息。机动模型假设移动末端设备以平均速度改变它的位置。移动性须假设为一个移动的终端改变位置的平均速度。机动模型(如图2)有两种形式:静止与移动(static-mobile)和移动与移动(mobile-mobile)。第一种形式静止与移动(static-mobile)即静止的一个核心资源和遍布其周围的移动的移动设备。第二种形式是核心资源和移动资源设备都是移动的。这种形式通常讨论的全部是分散的基础设施而没有静止的基础设施。

基于应用领域,在任务分配时传统的调度程序通常考虑不同的参数,例如计算能力和贮存工作任务的能力等,移动资源被认为有能力单独地处理一个被分配的工作。

这个机动性模型与移动网格环境中的资源调度程序结合起来改进资源调度的性能,提高了资源的利用率,缩短了移动资源的响应时间。机动性模型的用户及移动设备使用最基本的可计算的参数。模型使用的参数如“用户范围”,“平均机动性”和“在范围内的时间”等。“用户范围”是指用户能够覆盖的范围,并且在这个范围内用户能与移动设备进行通信。“平均机动性”,一个可计算的参数,是指一种资源或用户(基于用户和资源的移动性)的平均机动性。它主要是通过在用户和移动资源之间最近发生的通信量进行计算。“在范围内的时间”参数指在用户范围内为显示资源可用性被预言的时间。下面给出用于计算“平均机动性”和“在范围内的时间”两个参数的方程式如下:

实线表示静止,虚线表示移动,MD表示移动设备

方位可以简化为用户和资源之间的距离。方位通过找到两个最近相互发生作用的用户或移动设备之间的差别来计算。“在范围内的时间”这个参数通过方程式(2)计算。“距离”是指在用户和资源(新位置)的位置之间的网差别。

在单一的迭代里被分配到一种资源的工作数量通过方程式(3)计算。参数"放弃任务"是通过参数“在范围内的时间”和“工作完成时间”进行计算。参数“放弃任务”的价值是为一种资源分派任务。

基于"放弃任务"参数的价值,在对移动资源进行任务分派时,下列规则被使用:

上述模型是一个静止用户与移动设备资源进行资源调度时的机动性模型。模型需要扩展成为一个移动用户和移动的设备之间进行资源调度时的机动性模型。通过计算基于两个移动性因素的"平均机动性"参数对此机动性模型进行扩展。一个移动性因素考虑用户和另一个移动性考虑资源。用户平均机动性简化为通过从新位置中减去老位置而获得。用户维持了资源的两次方位。移动-移动模型的"平均机动性"通过方程式(4)计算

其它参数是通过上述静止-移动模型得到“在范围内的时间”和“放弃任务”参数方法的方程式得到,“距离”参数的计算现在是新用户位置和资源的新位置之间的网差别。

2 模型的试验

我们通过简单的实验证明被提议的机动性模型和资源预言。实验假设用户和资源在任何规定的时间都知道它们的具体位置。这个方位的确定通过GPS(全球卫星定位系统)很容易被实现与协调。当GPS为简单协调时,实施考虑XY两个参数。当与用户通信的移动资源改变它们的位置时,用户被认为是静止的。XY的变化范围在0和500之间考虑。用户的范围设为200米。用户的位置是(200,200),移动资源的第一个位置是(250,200),第二个位置是(300,200)。为了计算方位,两段距离从用户到资源被基于两个位置测量。第一个方位为50,第二个方位为100。根据测量的方位利用"平均机动性"方程式1求出平均机动性。计算"平均机动性"参数时使用的移动资源第一个方位为50。绝对价值被考虑在全部情况里,正的机动性价值显示资源正离开用户,负的机动性价值表明资源将移动向用户。参数“在范围内的时间”通过计算参数"在用户里的范围"和"平均机动性"获得的价值是2个单位时间。假定单位时间内能够完成被分配到一种资源的任务。基于这个预言模型,两个子任务将被分配到移动资源,并且移动资源在离开用户范围之前,提供结果。

为了延伸为一种用户和移动资源两个都是移动的模型环境中进行实验验证,实验进行如下,参照静止-移动模型提及的预测模型,用户的最初位置是(200,200)和资源的位置是(225,200)。第一个方位被给25的最初位置计算。用户和资源移到新位置。用户的新位置是(175,200)和资源的新位置是(250,200)。新距离从用户到资源为75。关于用户和资源的“平均机动性”是125。参数“在范围内的时间”的值是1个单位时间,这表示仅仅只有一个工作任务可能被分配到移动资源。

3 结论

该文在移动网格环境中为资源预言提出了一个一般的机动性模型,提出了一种简单的实验机制,并且证明了在两种机动性模型的基础上资源调度选择的机制,即静止-移动模型和移动-移动模型。第一种机动性模型是基于静止的用户和移动的资源。另一种则是机动性模型考虑移动用户和移动资源设备。在这个机动性模型上资源选择和任务分配被简单的实验所证明。在基于响应时间的基础上,资源被预言,它在用户范围内保持通信,未来的工作是为一般的机动性模型提出资源预言模型,并进行实验验证。

参考文献

[1]徐志伟,李伟.织女星网格的体系结构研究[D].中科院计算所,2002.

[2]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002.

[3]Weiser M.Ubiquitousc omputing[J].Computer,1993,26(10):1-72.

[4]Satyanarayanan M.Pervasive computing:Vision and challenges[M].IEEE Personal Communications,2001:10-1.

[5]移动网格变革服务[EB/OL].http://www.ccu.com.cn/houtai1/content.asp?newsid=1892.

[6]李玺,胡志刚.计算网格中的资源选择与调度算法[J].计算机工程与应,2005(11).

[7]都志辉,陈渝,刘鹏.网格计算[M].北京:清华大学出版社,2002.

[8]Park S M,Kim J H.Chameleon:A Resource Scheduler in a Data Grid Environment[C].Tokyo,Japan:2003IEEE/ACM International Sym-posium on Cluster Computing and the Grid(CCGRID'2003),2003.

网格任务调度模型的研究篇4

网格任务调度模型是对网格任务调度问题的一个映射或是一种解释。一个结构合理的调度模型应该能够很好地反映任务调度问题的相关流程，完整地解释所要讨论的问题范围，并给出严密的条件约束，不至使建立的模型无解或是无可行解。本文分析研究了经典的任务调度模型，提出了一个具有两层结构的调度模型，包含树形全局调度模型和局部调度模型两层,很好地解决经典模型中存在的问题，并保证了网格调度系统具有高安全性和活性等其他优点。

1 网格任务调度模型

中心式网格调度模型和分布式网格调度模型是两种经典的网格任务调度模型。中心式网格调度模型便于管理整个网格系统，但如果发生单点失效，后果是严重的，适用于中小规模、单管理域的网格系统中;分布式网格调度模型解决了中心式模型单点失效的问题，但是也存在不足。

1.1 中心式网格调度模型

中心式网格调度模型[1,2,3,4]只有一个网格调度器(Grid Scheduler,GS)。调度器负责接受用户提交的应用并监测网格中所有计算资源的静态和动态信息，为每一个或是每一批任务映射合适的资源。中心式调度模型可分两层：第一层为网格调度器，第二层为各个网格资源的资源代理。调度器通过与资源代理通信来监测网格资源和任务的分配。

中心式网格调度模型中只有一个网格调度器，如果发生单点失效，整个网格系统就会瘫痪，用户提交的任务也将丢失，资源上处理完的任务结果无法进行返回，所以必须保证其安全性和可靠性。有效的措施是建立备用网格调度器，这样就增加了额外的经济开销。因此，中心式网格调度模型适用于中小规模、单管理域的网格系统中。

1.2 分布式网格调度模型

在分布式网格调度模型中，每个网格调度器只管理本地域的任务调度和资源管理。通过多个调度器之间的协作，为任务选择合适的资源。网格调度模型的拓扑结构是网格调度器之间相邻关系的集合。中心式模型中只有一个网格调度器，不存在调度器之间的协作，所以网格调度器的拓扑结构是空集。文献[5]中把分布式调度模型器的拓扑结构描述成一个完全图，即每个网格调度器都互相直接连接;文献[6]中把拓扑结构描述成一个非完全图;文献[7]中则把拓扑结构描述成一棵树。

完全图结构的调度模型中，当某一个单点失效时，剩余调度器的拓扑结构依然是完全图，可保证系统的安全性和可靠性，也可保证失效节点上任务的最终执行。因为每个调度器都与其它调度器连接，可以实现任务与资源的最优映射，调度器之间的任务迁移代价最小。缺点是在大规模网格中的实现代价昂贵。非完全图结构的调度模型是完全图结构调度模型的简化形式，其拓扑结构是不规则的。因此发生单点失效时，拓扑结构会发生很大的变化，原本具有相邻关系的调度器可能会不再相邻。如果非完全图具有桥[8]，失效节点恰恰是桥的端点，则该拓扑结构将分裂成两个独立的调度空间。

2 树结构的网格调度模型

树形结构的调度模型可简化网格平台的实现，降低节点的通信复杂度和便于网格资源的管理。树形结构是一种规则的拓扑结构，当发生单点失效时，可利用有关树的相关算法，对分裂成两个独立空间的部分进行合并。本文提出的调度模型采用树形结构的网格调度模型。调度模型采用两层结构：全局调度和局部调度。

2.1 全局调度模型

每个节点有一个权值P，表示该节点单位任务的处理能力。新的网格调度器加入网格或是一个网格调度器退出网格系统，此拓扑结构就根据平衡二叉树的插入和删除算法进行调整，把分裂成两个独立结构的树重新进行组合。由此可以实现网格系统的可扩展性、安全性和可靠性，如图一所示。

根节点调度器是网格系统的入口，负责接收任务和向其子节点分配任务。调度过程为：当根节点接收到任务集合时，向负载较轻的子结点进行负载迁移。如果子节点负载较重，则使任务处于等待状态，直到其子节点负载较轻或是能够自己进行处理。各层的节点与根节点的工作原理一样，负载较轻时，接受父节点分配的任务;负载较重时，向其子结点分配任务。树形结构的全局调度过程是一个可实现各个网格节点负载平衡的任务迁移过程。因此，树形结构的网格调度模型具有天然的负载平衡的优点。

2.2 局部调度模型

局部调度模型的主要功能是负责管理本地域内的任务调度和信息检测。主要模块包含有任务池、容错处理器、任务调度器和信息检测器，如图二所示。

(1)任务池

任务池保存了本域内新到达的和以往已经映射过但还没有调度的任务，任务池中的任务都是已分解的独立任务，不包含优先约束关系。任务池保存任务副本直到其执行完毕并返回结果。

(2)任务调度器

任务调度器为每个任务按照其特性分配一个相应特性的机器，并把任务发送到指定的机器上运行。任务调度器在内部节点无任务或是负载较轻的前提下向其分配任务。为了防止出现任务总是得不到执行的情况，引入了老化因子。基本思想是，将上次没有得到执行的任务在下次重新映射时让它变老，相应的提高了该任务的执行优先级。任务调度器根据老化因子来对任务进行调度。

(3)容错处理器

容错处理器具有任务死锁的检测和处理功能。当任务的等待时间超过了生命周期规定的期限，但是依然没有反馈信息，容错处理器自动认为此任务处于死锁状态，杀死此任务并重新调度。容错处理器具有节点失效的检测、处理功能。当局部管理域中的一个站点失效不可用时，任务调度器将保存在任务池中的任务副本重新分配，保证任务的最终完成。

(4)信息检测器

信息检测器的功能是及时地检测资源的动态信息。节点的负载情况采用状态驱动策略[9]，状态驱动策略可以有效地避免负载抖动，降低通信开销。如果节点的CPU占用率过低或过高，信息检测器及时主动地向任务调度器发送信息，任务调度器将根据情况进行追加调度或是进行负载迁移。

3 结束语

本文首先介绍了两种经典的网格任务调度模型，中心式网格调度模型和分布式网格调度模型，分析了各自的优点和缺点，并在其基础之上设计了具有两层结构的调度模型：全局调度和局部调度。全局调度模型采用二叉树拓扑结构，很好地解决了网格调度器的单点失效问题，并且很好地实现了各个网格调度器之间的负载平衡。

摘要：网格任务调度是采用适当的调度策略把应用程序分配到异构的计算节点上进行高效的执行并返回正确结果的过程。本文研究了经典网格任务调度模型,分析了各自的优缺点,并提出了一种包含有树形全局调度模型和局部调度模型的两层结构模型,此树形全局调度模型通过负载从根节点自上而下的迁移,能够很好地实现网格系统的负载平衡。通过二叉树的节点删除算法能够很好地解决模型中节点的失效问题,因此具有很好的安全性和可靠性。

关键词：网格,任务调度模型,树形调度模型

参考文献

[1]Martino D,Sub V.Optimal Scheduling in a Grid Using Genetic Algorithms.International Paral-lel and Distributed Processing Symposium(IPDPS’03),2003:148-154.

[2]Ernemann C,Hamscher V,Schwiegelshohn U,et a1.On Advantages of Grid Computing for Parallel Job Scheduling.2nd IEEE/ACM International Sympo-sium on Cluster Computing and the Grid(CC-GRID2002),2002:31-38.

[3]Ranganathan K,Foster I.Decoupling Computa-tion and Data Scheduling in Distributed Data-Inten-sive Applications.11th IEEE International Sympo-sium on High Performance Distributed Computing,2002:352-258.

[4]Subramani V,Kettimuthu R,Srinivasan S,eta1.Distributed Job Scheduling on Computational Grids Using Multiple Simultaneous Requests.11th IEEE International Symposium on High Performance Distributed Computing,2002:359-366.

[5]Chen Hongtu,Maheswaran M.Distributed Dynam-ic Scheduling of Composite Tasks on Grid Computing Systems.16International Parallel and Distributed Processing Symposium(IPDPS’02),2002:88—97.

[6]Arora M,Das S K,Biswas R.A De-Centralized Scheduling and Load Balancing Algorithm for Hetero-geneous Grid Environments.International Conference on Parallel Processing Workshops,2002:499-505.

[7]Cao Junwei,Spooner D P,Jarvis S A,et a1.A-gent-based Grid Load Balancing Using Perfor-mance-driven Task Scheduling.International Paral-lel and Distributed Processing Symposium(IPDPS’03),2003:49-58.

[8]左孝陵,李为监,刘永才等.离散数学[M].上海:上海科学技术文献出版社,2003:280-286.

网格工作流调度篇5

“上海高校网格平台e-网格计算应用平台”(以下简称“e平台”)建立在OGSA[1]的基础上,采用了Globus Toolkit 3.2[1,2]网格软件开发包。“e平台”中原有的任务调度策略是基于用户和资源优先级的“抢先”(Preemptive)任务调度算法[3,6],算法遵循“始终保持队列中最高优先级任务运行在满足其资源需求的最高优先级资源结点上”[5]的抢先原则。该调度策略存在以下两个不足:吞吐率较低,调度环境适应性较差。本文将分别针对这两个问题提出调度优化的方案。

1 吞吐率的提高和时间片轮转任务调度

时间片轮转算法[7]作为操作系统中重要的进程调度方法之一,在提高系统吞吐率方面有着显著的作用。如果把它应用到“e平台”的任务调度机制中,可以很好地解决同一优先级别任务之间调度的问题。

1.1 网格系统中实现时间片轮转任务调度的特点

单机操作系统中使用的时间片轮转算法与“e平台”中要使用的时间片轮转任务调度有着很大的不同。这主要体现在单机操作系统中进程的运行方式是独占式的;“e平台”中的资源是不定的且随时变化的,网格任务对资源的需求也是各不相同的,所以时间片轮转任务调度要解决好资源匹配的问题,在调度策略上要比单机操作系统复杂得多。

1.2 时间片轮转任务调度的实现

“e平台”中时间片轮转任务调度由以下几个部分组成:

(1) 时间片确定

“e平台”在任务切换时,需要有开销。任务从保存的中间结果重新运行,也需要浪费一部分CPU时间。所以时间片的选取不应该太小,在“e平台”的实验中将时间片q取240min。

(2) 资源匹配

时间片轮转任务调度要解决的是同级别任务之间的调度问题,所以该调度只会发生在级别相同的任务之间,即调度的对象是优先级等于等待队列中最大任务优先级的所有在运行和等待的任务,并且把这样的任务称为可轮转任务。引入时间片轮转任务调度的目的是提高“e平台”的吞吐率,也就是要保证每一个可轮转任务都能获得相近的运行时间。同时调度还要解决好资源利用率的问题,在提高吞吐率的同时将空闲资源尽可能多地利用起来。

资源匹配是时间片轮转任务调度中最重要的一步,通过它可以体现出时间片轮转任务调度如何在调度过程中提高“e平台”的吞吐率和资源利用率。在资源匹配中将会决定在这一次轮转中要被中止的可轮转运行任务和要被提交的可轮转等待任务,其算法思想是:

① 使用timeshared来记录每个任务在时间片轮转任务调度中实际经过的运行次数,当可轮转等待任务要中止可轮转运行任务的运行时,等待任务的timeshared必须小于运行任务的timeshared。一次时间片轮转调度开始时,调度程序将扫描等待队列找出所有可轮转等待任务放入timesharejobwaitque中,同时扫描运行队列找出所有可轮转运行任务放入timesharejobrunque中。

② 资源匹配的原则是“优先中止运行时间最长的可轮转运行任务”和“优先提交等待时间最长的可轮转等待任务”。但是根据“e平台”的实际情况,要同时兼顾这两个方面是比较困难的。所以在具体实现中使用交叉匹配的方法,即将相邻两次的资源匹配分别用于实现“优先中止运行时间最长的可轮转运行任务”和“优先提交等待时间最长的可轮转等待任务”。资源匹配中会将要提交的任务放入subjobque中,将要中止的任务放入interjobque中。资源匹配的算法伪代码如下:

· “优先中止运行时间最长的可轮转运行任务”的算法描述:

·优先提交等待时间最长的可轮转等待任务”的算法描述:

(3)上述资源匹配的算法中存在这样一个问题:timeshared的记数开始时刻该如何确定。对于在时间片轮转任务调度过程中提交进来的可轮转新任务,如果只将它们的timeshared从0开始记数,那么这之前提交的可轮转任务很可能会受这些后提交任务的影响而很难再得到运行的机会;如果考虑在可轮转新任务提交之后将所有可轮转任务的timeshared都置0,就会打破可轮转任务在之前已经达到的各个任务的timeshared不均衡的状态。因此在时间片轮转调度中,提出一种针对可轮转新任务的补偿方法:调度会计算可轮转新任务的timeshared=在它提交前的所有可轮转任务的timeshared的平均值。

(3)资源匹配完成后,调度程序根据interjobque和subjobque的内容进行相应地任务调度,调度完成后调度线程执行sleep(q),从而完成一次完整的时间片轮转任务调度。

2 性能分析

在单机操作系统中使用时间片轮转算法一定可以提高系统的吞吐率,而在网格系统中由于存在资源匹配的问题,所以仍有可能造成一些可轮转任务的响应时间很短而另一些却很长的情况。因此在资源匹配中采用了交叉匹配的方法,通过它可以使不同资源需求的任务都能在比较接近的时间段内运行完成。

在“e平台”的实际使用过程中,大部分的任务都是基于探索性的实验任务,它们的运行时间一般都比较短,大致介于500分钟到800分钟之间;计算量比较大的任务的数量相对较少,它们的计算时间一般都在1000分钟以上;而计算量为800分钟到1000分钟之间的任务的数量则介于前两类任务之间。所以总的来看,如果以运行时间长短为标准,那么“e平台”中的任务基本呈现指数分布。同时,任务对资源的需求也基本满足指数分布,即资源需求较小的任务数量比较多,而资源需求较大的任务的数量则较少。据此,可以设置如下的实验环境:

在“e平台”中设置2个资源结点,每个资源结点上各有12个可用CPU,资源结点1的资源优先级高于资源结点2,待提交的是10个任务优先级均为2的任务,每个任务的具体情况如下:

依照这10个任务的顺序提交后,使用时间片轮转任务调度进行调度实验,可以得到如下的实验结果:

从实验结果可以看到,每个任务的总运行时间都比较接近,说明在时间片轮转任务调度中,使用交叉匹配方法可以很好地解决网格系统中由于任务的资源需求不同而可能引起的问题。

3 调度环境适应性的提高和遗传算法任务调度

“e平台”所使用的优先级抢先任务调度可以保证高优先级任务运行于低优先级任务之前[5],但是它无法确保目前所做的调度是一个全局最优调度,因为它并没有从全局考虑调度性能的提高。这样的调度策略在较高优先级任务的运行时间大大超过较低优先级任务的运行时间的情况下,可以得到一个不错的调度效率。但是如果较高优先级任务的运行时间大大短于较低优先级任务的运行时间时,调度效率就会比较差了。特别要注意的是,现在的“e平台”只有四个资源结点,如果未来“e平台”能够得到大规模的扩充,那么一定会大大增加资源结点的数量和用户任务数量。此时调度环境会变得更加复杂,继续使用优先级抢先调度,很有可能会给调度性能带来巨大的影响。此外,由于一个任务的运行时间可能不仅仅取决于CPU的快慢,还要受到诸如内存大小等因素的影响,如果这个影响对任务的运行是不可忽视时,目前使用的优先级定义就显得比较片面了,此时的优先级已经无法准确反映出一个资源结点的性能好坏。

因此,考虑当系统的规模如果在未来扩大到一定程度时,舍弃原有的优先级任务调度机制,针对调度问题复杂性的大幅增加,可以采用更适用于大规模搜索空间的遗传算法[8,9]调度机制来进行任务调度。

3.1 遗传算法任务调度的实现

遗传算法的步骤一般包括染色体编码、种群的初始化、适应值计算和个体选择、杂交、变异。染色体编码和适应值计算是其中的两个关键部分。根据“e平台”的实际情况,这两个部分的具体实现如下:

1)染色体编码

采用正整数编码,染色体的长度设为要提交的任务数量,其中的每一位都是正整数;染色体每一位的位置编号代表一个任务的编号,而该位置上的正整数值代表该任务所要提交到的资源结点的编号。

2) 适应值计算

根据上述染色体的编码,对其解码后就可以得到在每个资源结点上运行的任务序列,进而能计算得到在该资源结点上运行的所有任务的总运行时间。所以可以把适应值的计算公式写为:1/max(资源结点1上的总运行时间,资源结点2上的总运行时间,…)。显然该适应值越大,相应的染色体的适应度就越高,也就是调度之后的任务总运行时间越短,当然也就越接近于最优调度方案了。

3.2 性能分析

根据“e平台”中的任务按计算量呈指数分布且任务的资源需求也呈指数分布的特点,将分别使用三个不同的调度环境来进行任务调度实验:10个任务和2个资源结点,14个任务和4个资源结点,26个任务和8个资源结点。实验结果如下:

可见,随着调度环境复杂性的增加,遗传算法任务调度比优先级抢先任务调度具有更好的调度性能。使用遗传算法任务调度可以使“e平台”的任务调度程序具备应付更加复杂的调度环境的能力。

4 总结

本文的研究工作旨在提高“e平台”中调度程序的性能,对网格任务调度性能的追求正是进行调度策略优化的根本动力,据此可以说“e平台”的调度策略还有着很大的改进空间,如何进一步地提高调度性能值得更深入地去研究。

摘要：首先分析了“上海高校网格平台e-网格计算应用平台”现有的任务调度策略,针对它的不足之处,提出了两个优化的方案。第一个方案着重于研究如何提高系统的吞吐率,并且已经在系统中得到了实现;第二个方案着眼于系统未来的发展,提出了在系统规模扩大后可能会使用到的调度策略,并通过模拟,证明了该方案的可行性。

关键词：上海高校网格,任务调度,优化

参考文献

[1]Arun Thakore,Luis Ferreira.Grid Services Programming and Applica-tion Enablement.http://www.ibm.com/redbooks,May,2004.

[2]Chen Lin,Wang Choli,Francis C M Lau.A Gird Middleware for Dis-tributed Java Computing with MPI Binding and Process Migration Sup-ports J.Comput.Sci.&Technol,July,2003.

[3]Ramin Yahyapour.Design and Evaluation of Job Scheduling Strategies for Grid Computing.Doctorial Thesis,20.November,2002.

[4]邓志云.一个高分子模拟计算网格的作业管理.硕士学位论文,2005,1.

[5]柴亚辉.上海高校网格e-网格计算应用平台作业管理.硕士学位论文,2006,1.

[6]都志辉,陈渝,刘鹏.网格计算.北京:清华大学出版社,2002.

[7]何炎祥,李飞,李宁.计算机操作系统.北京:清华大学出版社,2004.

[8]王小平,曹立明.遗传算法——理论应用与软件实现.西安:西安交通大学出版社,2002.

网格环境中任务调度算法的研究篇6

随着网络在人们日常生活和工作中的日益普及,以及因特网的飞速发展,在网络中聚集了大量的可用资源,比如计算资源、存储资源、仪器设备等等。而这其中被闲置的、浪费的资源不计其数,因此,为了解决这一资源浪费问题,一种新的技术———网格技术出现了。它试图将这些资源进行整合,构成一个高性能的计算环境,实现计算资源共享和协同工作,使用户以最小的投入获得最大的计算效率和处理能力。但网格环境极奇复杂,不确定的因素太多,比如处理机之间通信的延迟、网格资源的动态性和异构性等等,故而拥有一个良好的任务调度算法才能保障网格中各类资源的协同工作,这样用户在调用算法时才能得到满意的结果,拥有好的体验。

1. 传统算法的分类

网格环境是一个异构系统,故而它的任务调度问题就显得非常关键,很明显它属于NP完全问题,因此,任务调度成为了网格计算中讨论的焦点,引起了很多学者的关注。传统的调度算法根据其思想的不同主要分为4类。

1.1 表调度算法

它的基本思想是首先确定各节点的优先级,并按照优先级将节点进行排序,之后用排序的结果来构造调度列表,最后按照以下两个步骤重复循环地操作,直到任务图中的节点全部被调用完[1]:1)按顺序从调度列表中取出一个节点;2)把此节点分配到处理机(此处理机具有使它的启动时间最早的能力)上。经典的算法主要有ETF(Earliest Task First)、MCP(modified Critica Path)、DLS(Dynamic Level Scheduling)等。

1.2 基于任务复制的调度算法

它的基本思想是将要执行的一些任务重复地分配到某些处理机上,想通过此方式来减少处理机之间的通信开销,换句话说,此算法的思想是想利用处理机的空闲时间来复制前驱任务,借此来减少需要传输的数据量,最终达到缩短处理器等待的时间[2]。经典算法主要有DSH(Duplication Scheduling Heuristic)、BTDH(Bottom-up Top-down Duplication Heuristic)、CPFD(Critical Path Fast Duplication)等。

1.3 基于任务聚类的调度算法

它的主要思想是把等待执行的所有任务分配到集群上,这些集群是没有数量限制的。假如在同一个聚类中有多个任务被分配到了,那就表示在同一个处理机上会对它们进行处理,在进行了聚类制作之外,最后还要在每个处理机上对聚类中的任务按时间的先后进行排序[3]。经典的算法主要有DSC(Dominant Sequence Clustering)、DCP(Dynamic Critical Path)等。

1.4 基于随机搜索的调度算法

它的基本思想不是简单的、纯粹的随机搜索,而是通过有指向性的随机选择来搜索问题的解。此类技术可以将前期搜索结果与特定的随机搜索特点进行整合,从而产生新的结果。经典的算法主要有遗传算法。遗传算法的调度结果一般情况下都是比较好的,但它的时间复杂度往往也比较高,并且在算法执行过程中需要确定相关的控制参数。另外在实际应用中不同的任务最优控制参数也是不同的,要找到能让大多数任务执行后有较好调度结果的控制参数很难。在当前的网格环境下,主要研究的是独立的任务调度,这与实际的网格环境(异构环境)特征不相符,此类的经典算法主要有Max-Min和Min-Min等。当然也有一些算法考虑到了异构环境下任务间的约束问题,如DLSLMT等。

2. 算法的对比与分析

2.1 ETF算法

ETF(Earliest Task First)是表调度的一个代表性算法。此算法首先计算出某个进入就绪状态的节点在每个处理机上的最早启动时间,通过将这些时间进行比较,选出那个最早启动时间的节点处理机,如果有多个时间是相同的、并且是最早的,那么选择静态b-level更大的。ETF算法要经历两个过程:一是确定任务图中各任务的优先级;二是要选择出适合的处理机来执行具有最高优先级的任务。ETF算法能够早早地计算出任务的最早启动时间,这是它最大优点;不足之处是它的每一次调度不能有效地减少任务图中当前的调度长度。另外,网格是分布式的异构环境,其中的资源是动态变化的,节点可能会随机地增多或剔除,通常情况下,处理机增多,理应会缩短任务的完成时间,但在调用ETF算法时,在处理机增多的情况下,任务的完成时间也不会减少。

2.2 DSH算法

DSH(Duplication Scheduling Heuristic)算法是基于任务复制调度的代表性算法[4]。此算法的思想是把每一个处理机上正在调度任务的启动时间与某个被调度任务的完成时间之间的间隔作为任务复制的间隔,算法尽最大可能地复制某个正在被调度任务的前驱任务到此间隔,直到间隔被填满或者被调度任务的启动时间不再被改善。此算法在同构环境中对于处理机间的通信延迟有所改善,它在执行任务的同时还要不断地复制其它任务,并且要对这些任务进行备份和存储,所以它的执行效率不是很高,在实际的网格环境中很难实现,因此,它只限于理论研究。

2.3 FCBSH算法

FCBSH算法是经过了改进的聚类算法。它的核心思想是最大限度地减少每个任务的完成时间[5]。但任务的完成时间由两个因素来决定,一是任务的起始时间,二是任务的执行时间。其中任务的起始时间由其前驱任务的执行情况和所在处理单元网络位置以当前任务的执行情况和所在处理单元网络位置决定。因此,将一个任务分配到目标系统中哪个处理单元来执行,对后续任务的执行情况影响很大。此算法有效地缩短了选择处理机的时间,而把大块的时间用于任务的处理,减少了一些时间开销。当然,此算法也有缺陷:它没有考虑网格环境(异构环境)下节点可以自由添加和退出,此外它还忽略了通信延迟及链接竞争等情况,因此它是一个理想状态下的算法。

2.4 遗传算法

遗传算法(Genetic Algorithm)是模拟生物进化而来的一种随机搜索算法。它通过模拟生物进化过程,根据遗传学机理和自然选择理论,挑选和生物遗传论中类似概念的变异因子和遗传因子,以父类杂交诞生子类,子类经过筛选变异再诞生子类的思想,进行算法模拟,从而能够动态地、先进地解决许多棘手算法问题,具有动态性和灵活性的特点。

遗传算法的求解过程,通过选择、交叉、进化流程迭代的动态的产生问题的近似解,与传统算法追求最优解不同,其所期望的结果是满意解。这就让遗传算法在工程使用中有了很强的实用性。而传统的遗传算法比较简单,只是对任务的粒度进行了理想化的划分,忽略了任务间的联系及通信开销,且为局部收敛[6]。近年来,国际学术界对其进行的一系列改进,可谓数目繁多,应用于网格的遗传算法也已经逐渐走入了人们视野,例如:J.Herrera(2005)等人提出的面向网格遗传算法、D.Lim(2006)等人提出的基于网格计算的多层并行遗传算法等。不难看出,遗传算法在网格上的发展和应用将会继续发展下去。

3. 算法存在的问题

经上文对几种经典算法的分析与对比,不管是国际的,还是国内的,都存在一些没有解决的问题,应用过程中将它们进行了理想化。而在现实的网格环境(异构环境)中,随时都有可能出现不可预料的问题,它们主要表现在以下几方面。

(1)现有算法都没有考虑网格环境中各节点执行任务的时间和处理机之间的通信延迟,认为它们是固定的、没有变化的,或是按线性关系进行变化。而现实的网格环境中,这些都可能随机地发生变化,并且变化是无规律的、复杂的,能够准确地描述这些变化的算法到目前为止还没有出现。

(2)现有算法的执行都是基于或多或少假设条件下进行的,例如任务之间的联系是确定的,处理机处在同构环境中并且连接完好,链路畅通无冲突,任务能够在任何处理机上执行等,而在实际的网格环境下,情况非常复杂,任务之间的联系是随机的、不确定的,处理机也处在异构环境中,传递信息或数据时链路冲突也是随时可能发生的,正因为有这诸多的因素存在,现有算法在实际应用时就会受到很多限制。

(3)众所周知,DAG图调度的本质就是一个Max———Min问题[7],也就是要均衡最大化任务的并行度和最小化任务间的通信时间,而对这个均衡点起关键性作用的因素就是DAG图的粒度选择,当前所有调度算法对各任务的粒度划分是相同的,完全没有考虑实际情况的多样性。

(4)目前也出现了很多基于某某算法的改进算法,但这些算法在改进的过程中,往往是以牺牲某一方面性能为代价的,改进能力有限,没能很好地均衡调度算法的核心参数。

(5)在异构的网格环境中,现有算法在某种程度上忽略了节点的动态性,节点是可以随机加入或退出的,这样就会存在这种情况:正在执行任务的节点突然退出了,但算法却没有给出一种对任务运行状态进行保存的容错机制,而是忽略不计或重新分配任务并执行。

4. 总结

经过对各类型经典算法的对比与存在问题的分析,现有网格环境中任务调度算法还没有达到预期效果,因此还有很多工作要做,结合分析情况,可以从两个方面来入手:一是全面、充分地了解实际的网格环境,分析它的特性,设计一个真实、可用的、非理想状态的通用算法,在算法中要充分地考虑网格环境的异构性、动态性、节点之间通信延迟的随机性,以及任务粒度划分的不可预料性等等;二是要均衡考虑任务执行时的核心参数,设计的算法要能使得任务调度的结果达到全局最优。

因此,在复杂多变的网格计算环境中建立一个并行的应用模型,并设计一个通用的任务调度算法是一个非常艰巨的任务。笔者后期将继续阅读国内外的相关文献,力求在这一方面有所突破。

摘要：本文通过对四种不同的任务调度形式及相应的经典算法进行分析对比,总结出了当前网格环境中任务调度存在的问题,指出了后期研究网格任务调度的方向。

关键词：任务调度,算法,网格

参考文献

[1]Lan Foster,Carl Kesselman,Sleven Trecke.The Analomy of the Grid Enabling Scalable Virtual Organizations|J|.|nl|J Supercomputer Applications,2001:1-25

[2]Annie s,Wu,Han Yu,Shiyuan Jin等.An incremental genetic algorithm approach to multiprocessor scheduling.IEEE Transactions on Parallel and Distributed Systems,2004,15(9):824-834

[3]段立荣,曹礼宇.网格中任务调度机制研究.山西科技,2006,5:58~61

[4]林剑柠,吴慧中。一种基于任务复制调度算法研究,小型微型计算机系统,Vo 1127 No.7 July 2006

[5]杜晓丽,蒋昌俊,徐国荣,丁志军。一种基于模糊聚类的网格DAG任务图调度算法,软件学报,Vol.17,No.11,November 2006

[6]李力,薛胜军,网格任务调度机制的研究,现代计算机(专业版),2008.4

浅析网格环境中的任务调度算法篇7

网格是以资源共享为目的,利用互联网将分散与不同地域的计算机组织起来,成为一个虚拟的“超级计算机”。每台参与的计算机就是一个“节点”,成千上万的节点组合起来,成为一张“网格”。从而能够充分地利用网络中的空闲计算能力,实现计算资源、存储资源、数据资源、信息资源、知识资源、专家资源等全面的共享。

随着Internet的发展, 网格计算技术逐渐成为新的研究领域。网格系统由大量异构资源组成,具有复杂、动态和自治等特点。高效的调度算法可以充分利用网格系统和处理能力,从而提高应用程序的性能。为了实现网格资源的优化配置,并为网格用户提供较为满意的服务质量,任务调度技术一直以来成为人们研究的热点。

文献[1]对当前现有的网格任务调度算法进行了深入而详细的讨论。文献[2]提出了一种基于任务池模型的分级调度方法,保持了系统资源之间的共享关系和高度可控性。文献[3]提出基于Min一Min算法的最小完成时间偏差调度算法(Dev_Min一Min),解决了任务调度的负载均衡和吞吐率高的问题。文献[4]提出了MD一sufferage算法,缩短调度跨度的同时保证较小的任务等待时间。文献[5]提出了同时考虑任务带宽要求和负载均衡要求的改进算法,设计了一种有依赖关系的任务调度算法。本文提出Segment Qos Min-Min RR任务调度算法,平衡了负载,提高了任务的完成时间和平均等待时间,达到算法简单并且效率较高的要求。

2 RR 算法

RR算法是一种动态调度算法。首先将网格任务以任意的顺序被提交到可用的处理单元(PE)上,直到所有的网格任务都提交完。然后把未执行完的任务连接成一个环,一旦此时有执行完的任务,立即从环中把一个还没有执行完的网格任务调度在此可用的处理单元上,即此时有多个处理单元同时在运行同一个网格任务。只要其中一个处理单元上的网格任务执行完,立即杀死所有的任务。重复上述过程,直到所有的任务执行完。如果此时动态有新的任务加入,就立即开始执行。

设T是一个大小为L的n个任务的集合,m为一个计算网格上处理器的数目,定义T的调度如下:

T的一个在具有m个处理器的网格上的调度S是一个三元组 <v,p,t> 的集合, 它们满足R1和R2规则,v∈T,1≤p≤m,t是任务v的起始时间,<v,p,t>∈S,意味着处理器p在时间间隔t~t+d执行任务v,d是通过p的处理能力和v的L计算出来的, 所以称t+d为任务v的完成时间。

R1:对每一个v∈T,至少有一个 <v,p,t>∈S。

R2:不存在这样的两个三元组 <v,p,t>,<v',p',t'>∈S;t≤t'≤t+d,t+d为任务v的完成时间。上述功能可以描述如下:

R1保证每一个任务v至少执行一次 ,R2是说每一个处理器在任何一个时刻最多只能执行一个任务,<v,p,t>∈S称为一个任务实体。

用下列公式来计算处理器的代价:

RR算法确定可以提高资源的利用率 , 但同时也造成了资源的浪费,另外,同一时刻有多个处理单元在运行同一个任务也是一种浪费。

改进的RR算法:就是所有的任务对处理单元都是共享的,只要有到来的任务想让它立即执行就可以。根据任务分配的处理速度 (MIPS), 定义了最大处理速度(MaxM IPS)、最小处理速度 (Min MIPS) 和最大任务数(Maxcount),所有的任务可以同时执行 ,所以任务的状态只有停止和运行,没有等待状态。此改进和算法大大提高了任务的完成时间,提高了系统的性能。

3 Min-Min 算法

在Min-Min算法中,首先分别计算每个任务在所有机器上的最小执行时间,执行时间最短的那个任务被选出来并被分配到相应的机器上,然后把这个最近被映射的任务从集合中删除,重复执行这个过程直到所有的任务都被映射。文献[3]研究表明,在不同的ETC矩阵下,Min一Min比OLB、MET、MCT、Max一min等算法均有更好的调度性能。但还存在局限性:(1)潜在的负载不均衡,使得资源利用率低;(2)没有考滤网格任务的服务要求。

对于一个由n个元任务构成的集合T,以及m个主机集合M,Min一Min算法的执行过程如下:

(l)对主机的就绪时间向量R进行初始化 ,使得对于任意Mj∈M有R(j)=0,然后根据预测执行时间矩阵ETC计算出每个任务Ti在每个主机Mj上的预测完成时间,根据预测完成时间定义,有CT(i,j)=ETC(i,j)+R(j);

(2)当任务集合T不为空时 ,反复执行以下操作直至任务集合为空:

a.对集合中的每个任务Ti(i=1,2,…,n),计算它在所有主机上的最小预测完成时间, 若它在主机Mj上的预测完成时间最小,记minC T(i)=CT(i,j),并记录min CT(i)所对应的主机编号host_min CT(i)=j;

b.找出min CT矩阵中的最小值 ,即找出具有最小的最小完成时间的任务, 并将它分配给对应的主机执行。例如,若任务Ta对应的min CT(a)最小,则将编号为host_min CT(a)的主机分配给任务Ta;

c. 从任务集合T中删除任务Ta, 更新主机Mk(k=host_minC T(a))的就绪时间R(k)=min CT(a),并更新预测完成时间矩阵CT。

4 Qo S Guided Min-Min 算法

这种算法是让高服务质量的任务先执行,低服务质量的后执行,并且不让高的服务质量的任务长期处于等待状态,从而减少了等待时间。

5 Segmented Min-Min 算法

每一个任务在每一台机器上都有一个期望时间ETC (Expected Time to Comput), 如果这里有t个任务和m台机器,就获得一个t X m的ETC矩阵,ETC(i,j)表示任务i在机器j上的执行时间。

Segmented Min-Min算法根据ETC来对这些任务进行排序。根据平均这些任务按序排成链表。然后这些链表中的每一个任务分成同样大小的片,并且大任务的所有片先调度。每一个任务中的片均采用Min-Min算法来调度。

6 Segment Qos Min-Min RR 算法

这种算法是在改进的RR算法的基础上,一是先加入Min-Min算法的思想, 让完成时间最短的任务先执行,让尽可能多的任务找到合适的机器来执行;二是加入Qos Guided Min-Min算法的思想,对任务和资源分别设定服务质量级别,有某个服务质量级别的任务只能在同等级别或高于此级别的任务和资源之间达到最合理的匹配;三是利用Segmented Min-Min算法的思想,让大的任务先执行并且考虑到任务的分解,这样不但平衡了负载,也同时在任务的完成时间和平均等待时间上得到了提高。

以上算法得到了几种实现。

(1)实现RR算法和改进和RR算法(RR1)。由于原始的任务提交是任意顺序的,因此在这里采用先来先服务的方式,即先到达的任务先被提交,后来的只能等待前面的都提交了才能被调度。

(2)实现Min-Min算法。由于要让最小完成时间的任务先提交,因此就要有一个衡量标准,即评价任务的完成时间。在这里只考虑任务的大小,而不考虑其他因素的影响,那任务越小,完成时间越短,也就意味着要先调度小的任务。

(3)实现Qos Min-Min算法。为了定义任务和资源的服务质量级别,这里增加了一个参数Qos。

(4)实现Segment Qos Min-Min RR算法。为了实现任务的分解,可以编写一个任务分解函数segmentgridlet(),把任务分成几个子任务片来调度。

7 实验仿真

常用的模拟器有Bricks、MicroG rid、Sim Grid、GridS im、Chic Sim、EDGSim等 ,其中重点Sim Grid。表1中的数据就是用Sim Grid模拟器仿真的。表1中记录了在任务数分别取200、300、400、500时,不同算法的任务最终完成时间。

8 结束语

【网格工作流调度】推荐阅读：

网格任务调度算法06-23

网格工作流02-10

网格工作考核方案06-20