21021064 程伟 网格环境下启发式任务调度算法.docx

21021064 程伟 网格环境下启发式任务调度算法.docx

《21021064 程伟 网格环境下启发式任务调度算法.docx》由会员分享，可在线阅读，更多相关《21021064 程伟 网格环境下启发式任务调度算法.docx（15页珍藏版）》请在冰点文库上搜索。

21021064程伟网格环境下启发式任务调度算法

网格环境下启发式任务调度算法综述

伴随着互联网技术的迅速发展，产生了一种新型分布式计算模式——网格计算，以实现大规模分布式资源共享及协同问题求解为目标，为解决超大规模、超级复杂的计算密集或者数据密集的问题提供了途径。

实现网格计算的一个重要目的在于实现地理分布、异构资源的统一描述方法，提供用户虚拟的统一资源界面，并将用户提出的服务要求透明、动态地分配给最适应的资源上执行。

由于网格计算系统融合了多种计算资源，一方面这些计算资源可能存在很性能差异，另一方面由于它们的工作负载也是动态变化的，因此如何高效地利用这些异构资源显得尤其重要，使得任务调度成为网格计算中的一项核心技术。

高效的任务调度算法可以充分利用网格资源，从而提高应用程序的性能。

然而，网格资源的动态性、异构性、自治性等特性，使得网格环境下的任务调度极其复杂，因此如何开发出有效的任务调度算法是网格计算面临的一大挑战，而且任务调度也已被证明是一个NP完全问题，引起了众多学者的关注和研究。

而现有的任务调度算法多以启发式方法为主，本文主要对启发式任务调度算法进行研究。

本文主首先介绍网格的概念和特点，阐述网格环境下任务调度的概念、特点、目标和主流模型，研究了经典的启发式任务调度算法。

1.网格的概念和特点

网格的概念来源于电网，产生于上世纪九十年代中期，人们试图实现类似于家用电器能够方便的从电网中使用电力资源，用户能够从广域分布的资源池中获得所需的资源。

网格有着多种不同的定义，在《网格：

一种未来计算基础设施蓝图》[1]一书中网格定义为：

网格是构筑在互联网上的一组新兴技术，它将互联网、计算机、大型数据库、传感器、远程设备等融为一体，为科技人员和普通老百姓提供更多的资源、功能和服务。

随着人么对网格的认识，2001年将网格重新定义为“在动态的，多机构的虚拟组织中协调资源共享和协同解决问题”[2]。

因此，网格就是一个集成的计算与资源环境，或者说是一个计算资源池。

网格以现有的国际互联网为基础，把地理位置上分散的计算资源、存储资源、数据资源、信息资源、软件资源、存储资源、通信资源、知识资源、专家资源等的全面共享资源集成起来的一种基础设施。

用户通过这一种设施．可以简单的获得或使用自己所需要的资源。

网格必须同时满足三个条件：

在非集中控制的环境中协同使用资源；使用标准的开放的和通用的协议和接口；提供非平凡的服务。

作为一种分布式计算系统，网格具有以下几个特点：

（1）分布与共享性。

网格资源是分布在不同地理位置决定了基于网格的计算一定是分布式计

算。

分布性是网格的最主要的一个特点。

虽然网格资源是分布的，但网格的目的是共享资源。

分布性是网格资源在物理上的特征，而共享是在网格软件下实现的逻辑上的特征。

（2）自相似性。

自相似性是指网格的局部和整体之间存在着一定的相似性，局部往往在许多地方具有全局的某些特征，而全局的特征在局部也往往有一定的体现。

（3）多样性。

网格环境中允许有不同体系结构的计算机系统和不同类别的资源，这就使网格资源具有多样性。

（4）动态性。

网格并不是一成不变的，原来拥有的资源或者功能，在某个时刻可能会出现故障或者不可用；而原来没有的资源，可能在某个时刻会加进来，这种动态的变化决定了网格一定要具有很高的可扩展性和自适应性。

（5）自治性与管理的多重性。

自治性是指网格资源的拥有者对该资源具有最高级别的管理权限网格应该允许资源拥有者对他的资源有自主的管理能力；网格的管理具有多重性，一方面网格资源的拥有者对网格资源具有自主性的管理权限，另一方面有要求网格资源必须接受网格的统一管理。

2．网格任务调度概述

2.1网格任务调度概念

网格任务调度[3]就是实现任务到资源的映射过程。

任务调度针对网格模型和任务模型，建立适当的调度模型、调度算法，并在调度策略和目标函数的作用下完成任务到资源的最佳匹配。

在保证任务的执行性能的同时，兼顾系统负载均衡及资源利用率是网格任务调度的核心。

同时为了提高调度性能，任务调度通常还与性能指标、评价策略发生联系。

一个典型的网格任务调度通常包括调度模型、调度策略、目标函数、调度算法这四个部分，见图1[4]所示。

图1网格任务调度组成

文献[5]阐明网格任务调度应由四部分组成，分别是资源发现、资源匹配、次序调度及任务执行。

其中资源发现时根据任务的需求，为待调度队列中的任务找到所有符合条件的计算资源；资源匹配是根据某中策略，为每一个任务在可用资源组中寻找一个最优匹配的资源；次序调度是处理任务间谁应先调度，谁应后调度的关系，经过次序调度，任务的执行顺序就可能不同于任务的提交顺序；任务执行部分负责将次序调度选中的任务提交到最优匹配的资源上执行。

2.2网格任务调度特点

在网格系统中，任务调度系统是其重要的组成部分,它要根据任务信息采用适当的策略把不同的任务分配到相应的资源节点上去运行。

由于网格系统的异构性和动态性,以及运行于网格系统之中的应用程序对于资源的不同需求,使得任务调度变得极其复杂,不好的任务分配策略,将会增加任务的执行时间、降低整个网格系统的吞吐量。

网格计算任务调度具有以下几个特点：

（1）任务调度是面向异构平台的。

由于网格系统是由分布在Internet上的各类资源组成的，包括各类主机、工作站甚至PC机，它们是异构的，可运行在Unix、Linux、WindowsNT等各种操作系统下，也可以是上述机型的机群系统、大型存储设备、数据库或其他设备。

因此网格系统中的任务调度必须面向异构平台，并在这些平台上实现网格任务的调度。

（2）任务调度是大规模的、非集中式的。

由于网格系统是一个大到整个Internet的分布式巨系统。

要实现一种全局的统一集中的任务调度管理是根本不可能的。

因此，网格的任务调度必须以分布、并行方式进行任务的管理与调度。

（3）任务调度不干涉网格节点内部的调度策略。

在网格系统中，各网格节点的内部调度策略是自治的，网格任务调度系统干预其内部的调度策略是没有必要的，也是不可能的。

（4）任务调度必须具有可扩展性。

网格系统初期的计算规模较小，随着超级计算机系统的不断加入，系统的计算规模也必将随之扩大。

因此，在网格资源规模不断扩大、应用不断增长的情况下，网格系统的任务调度必须具有可扩展性，不致降低网格系统的性能。

（5）任务调度能够动态自适应。

网格中的资源不但是异构的而且网格的结构总是不停地改变：

有的资源出现了故障，有的新资源要加入到网格中，有些资源重新开始工作等。

2.3网格任务调度目标

一种任务调度策略对应一种资源匹配方案及一种任务执行次序，网格任务调度的目标就是要找到这样一个资源匹配方案及任务执行次序，从而为用户提供高效的、稳定的且经济的应用程序执行环境，以及实现高的资源利用率、系统吞吐率及负载平衡等目标。

具体而言，网格任务调度的目标包括：

最优跨度、负载均衡、服务质量、经济原则[6]等。

（1）最优跨度：

每一个用户都期望提交的任务以尽可能短的时间执行完，因而跨度是一个最重要、最常见的目标。

跨度指的是从应用程序的第一个任务开始执行到最后一个任务执行完毕所经历的时间，跨度越短就说明调度算法的性能越好。

（2）负载均衡：

负载均衡对于并行计算与分布式计算来说是一个关键问题。

一个负载均衡的系统，所有资源的运行时间相当，且不存在高性能资源负荷过重，而其余低性能资源却长时间处于空闲状态的问题，因而具有较高的资源利用率。

因而任务调度必须解决好系统负载均衡问题，从而达到对系统资源的充分利用。

（3）服务质量：

服务质量反映了用户对资源的需求状况，不同用户对网格资源所提供的服务需求不同，例如有些用户请求使用高CPU运行速度的资源，有些用户请求高带宽的资源。

由于网格的最终目标是为用户提供较为满意的服务质量，因而在任务调度问题中引入用户的服务质量需求具有重要的意义，只有这样才能实现在分配任务时用户的服务质量需求得到满足。

（4）经济原则：

由于网格资源是地理上广泛分布的，每个资源分属于不同的管理域，均有各自的资源管理机制及策略。

根据经济学理论，高性能资源的使用费用一般较高，而低性能资源的使用费用相对较低，因此资源管理与任务调度必须在经济原则的驱动下，以消费双方“互惠互利”为原则，实现资源提供者与消费者利益最大化，这样才能使网格立足于实际应用领域。

2.4主流网格任务调度系统模型

任务调度系统是网格计算系统中不可或缺的一部分，当前主要存在以下几种主流任务调度系统模型：

（1）Condor[7]

Condor系统是面向高吞吐率计算计算而设计的，它的主要目的就是利用网络中工作站的空闲时间来为用户服务。

针对这种应用，Condor使用的调度方法就相对简单一些。

它定义了一套半结构化的数据模型用于描述资源的特性和表达用户的需求。

它的调度分为两部分：

匹配和声明，在匹配阶段，Matchmaker在可获得资源中找到最适合任务的资源，然后通知用户和服务提供者，随后用户和服务提供者再进行声明，以此确立两者之间消费与服务的关系。

Condor采用集中式调度模式，且不能保障用户服务质量。

（2）AppleS

AppleS（ApplicationLevelScheduling）是一个构建在诸如Globus等网格中间件之上的任务调度系统，该系统的设计目标是使得任务能采取最有效的方式被调度在资源上，从而获得高效的执行性能。

为了实现这一目标，每一个网格应用都由一个嵌入的AppleS智能主体预测或度量它在各个资源上的执行性能，最终依据该度量信息进行资源选择并做出调度决策。

（3）Nimrod-G[8]

Nimrod-Gtl4是一个派生的软件系统，它能够通过Globus及Nimrod的软件来使用多个位于不同管理域的资源，并且该系统还基于计算经济原则提出了几个独创的资源管理及作业调度算法，目标是在满足用户需求的条件下将用户的执行成本降低到最小。

该系统中主要的调度算法为DBC（DeadlineandBudgetConstrained）调度算法，又可细分为成本优化、时间优化、成本时间优化三种策略。

（4）Symphony[9]

Symphony是Platform公司从金融领域、财政公司等风险分析的应用需求出发，开发出的针对小数据量、需要及时响应作业的调度系统。

Symphony系统将若干个小数据量的任务封装为一个会话，当用户请求发送任务时必须创建一个会话，之后才能开始任务的发送；若某一会话的所有作业都执行完毕，且输出结果都反馈给用户时，该会话就被销毁。

Symphony将若干小任务封装为会话的好处是可以对这些任务以会话为单位进行整体调度，减少了单个任务在调度队列中的等待时间，从而降低了任务延迟、缩短了任务响应时间，提高了调度的实时性。

3启发式任务调度算法研究

网格环境下的任务调度已被证明是一个NP完全问题，在很多情况下，获得一个最优解对于求解该类问题几乎是不可能的，这是因为一个最优解的获得需要进行穷举搜索，然而由于任务调度所解决的问题是如何将n个任务调度在m台主机上，这样就存在

种映射方案，穷举搜索显然是不现实的。

在任务调度问题的全局最优解的获得较为困难的情况下，启发式算法自然就占据了主导位置。

启发式算法为解决NP完全问题提供了一个求解方法，但它仅仅是一种寻求答案的方法与技术，却无法保证一定能获得期望的最优解。

因此，在一般情况下，启发式算法常常是基于一些直观的启发，在可行解的基础上进行逐步优化，从而尽可能更逼近最优解的近似算法。

启发式的任务调度算法可以分为静态启发式调度算法和动态启发式调度算法。

静态启发式算法采用离线方式进行任务调度，调度决策在调度之前就已做出，因而也叫编译期间算法，相反地，动态启发式算法采用在线方式进行任务调度，调度决策在算法运行期间实时做出，因而也叫运行期间算法。

静态启发式调度算法的运行开销低，有足够的时间充分利用启发式信息，因而能产生有效的调度方案，但由于算法要求映射前应用程序的结构、任务在资源上的预测执行时间、参与调度的任务集合等参数都必须是已知的，这在网格这一不确定因素众多且动态变化的资源环境中难以实现，故静态启发式调度算法不具备较强的可用性。

3.1随机负载均衡算法

随机负载均衡算法（OpportunityLoadBalancing，OLB）是一种最简单的静态调度算法，其思想是：

随机把一个任务分配给下一个可用的机器，而不考虑任务在该机器上的预期执行时间。

OLB算法的目的是要尽量使得所有的机器都处于工作状态，其优点是算法实现简单。

由于该算法没有考虑任务的预期执行时间，因此可能会导致一个比较差的完成时间。

3.2模拟退火算法

模拟退火算法也是一种经典的静态启发式智能调度算法[10,11]。

来源于对固体退火现象的观察。

对固体加温时，其内部粒子运动剧烈且呈无序状，固体内能逐渐增大；固体冷却时，内部粒子运动逐渐有序，内能逐渐减小，在每个温度都能达到平衡态，最终在常温达到基态，此时内能最小。

采用模拟退火原理解决组合优化问题时，将固体内能看作是目标函数值，将温度看作是控制参数，算法的求解过程为：

从初始解与初始控制参数开始，逐步衰减控制参数值，然后计算产生的新解与当前解的目标函数差值，以此决定是否舍弃或接受这一新解，然后对这一过程进行反复迭代直至算法终止，此时获得的解即为近似最优解。

模拟退火算法的执行过程如下：

3.3遗传算法

遗传算法[12]是借鉴生物界的进化规律而产生的一种随机搜索方法，它将问题的求解模拟成染色体的进化过程。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。

执行过程为：

3.4Duplex算法

Duplex算法可以看作是对Min-Min与Max-Min算法的整合。

该算法的调度原理是，首先对同一个任务调度问题分别采用Min—Min与Max．Min算法进行调度，之后对二者的调度方案进行比较，从中选择一个调度效果较好的方案，然后完成资源的分配。

在Min-Min或Max-Min算法能产生较好调度性能的情况下，Duplex算法能进行有效的调度；然而当Min．Min与Max．Min都无法达到一个较好的调度效果时，Duplex算法就不具备较强的可用性。

3.5蚁群算法

蚁群算法[13]是模拟蚂蚁智能行为的一种仿生优化算法，来源于蚂蚁仿生，每一个运动的蚂蚁都会在路径上释放信息素，以此来与其余蚂蚁进行沟通与协作。

最短路径上经过的蚂蚁较多，其上的信息素浓度自然就会很快地增大，于是蚂蚁就能通过对信息素浓度的感知而实现最优路径的选择。

大量实验表明，蚁群算法能够有效求解NP类问题，而任务调度问题也被证明是NP完全的，且蚁群算法固有的鲁棒性、可扩展性与分布并行性，使其非常适用于解决网格计算中的任务调度问题。

基本蚁群算法的实现步骤如下：

3.6在线模式启发式算法

在线模式启发式算法是一类动态启发式调度算法。

依据映射事件的时间特征，动态启发式算法可划分为在线模式与批模式（BatchMode）两类。

在线模式是任务一旦到达调度器，调度器便立即做出决策，这一模式下的任务调度具备较强的实时性，但由于调度器无法充分掌握全局信息，从而对调度性能产生了不利影响。

最小执行时间算法MET（MinimumExecutionTime），也被称为LBA（LimitedBestAssignment）算法，尽可能地将任务分配给执行它最快的主机，保证每个任务的执行时间时间最少。

由于该算法在分配过程中并未考虑主机的就绪时间，因而会导致了多个任务被集中调度在一个或几个高性能主机上，从而引起主机间的负载严重不平衡。

最小完成时间算法MCT（MinimumCompletionTime）是以任意的顺序将任务映射到具有最早完成时间的主机上，它并不保证任务被指派到执行它最快的主机上，而仅关心如何最小化任务完成时间，因而可能导致任务在资源上的运行时间过长，从而潜在地增加了调度跨度。

KPB（K-PercentBestHeuristic）算法介于MCT与MET算法之间，它使用一个资源的子集来进行任务调度。

设m为可用主机的总数，该资源的子集由具有最短的任务执行时间

的主机构成，该算法每次将任务映射到资源子集中具有最小完成时间的主机上。

若k=100，则全部主机参与调度，该算法就与MCT算法等价；若

k，则KPB算法与MET算法等价，从而引起主机间严重的负载不均衡。

可见在该算法中对k值的定义是算法调度效果优劣的关键。

3.7批模式启发式算法

批模式调度算法并不是在任务到来之后立即做出决策，而是先将任务收集起来存放在一个待调度队列中，若映射事件到来，则将任务分发出去，因而批模式调度算法既具备动态算法的实时性，又具备静态算法的高效性。

快速贪心（FastGreedy）算法根据任务的到达顺序依次从任务集合中选择一个任务，计算该任务在所有主机上的预测执行时间，并将该任务指派到具有最小期望完成时间的主机上，如此重复直至任务集合为空。

Sufferage算法的原理是，一个任务将被分配给这样一个资源，如果该任务不分配给该资源，将会蒙受最大的损失。

该算法为每个任务指定一个Sufferage值，该值定义为任务的次小完成时间与最小完成时间之差，差值大的任务具有高的调度优先级。

Sufferage算法的执行过程为：

遍历待调度任务集合，找到具有最小的最小完成时间的任务

及相应的资源

；若

当前为可用状态，则将

指派给

上，否则比较已经指派给

的任务

与

的Sufferage值，当且仅当

的Sufferage值大于

时，

才被指派给

；重复此过程直至任务集合为空。

3.8Min-Min算法

Min-Min算法是一种经典的启发式算法，其总是执行具有最短完成时间的任务，具有实现简单、执行快速的特点。

该算法计算每个任务在各个机器上的期望完成时间，获得每个任务的最早完成时间机器计算资源，再将具有最小最早完成时间的任务分配给获得它的计算资源，分配完成后更新计算资源的就绪时间，并将已分配的任务从任务集合中删除。

如此重复，直到所有任务被分配完毕。

Min—Min算法的详细执行过程如下：

大量实验表明Min-Min算法存在着一个很大的缺点，就是算法的资源负载均衡性能（LoadBalancing）不高。

在实际的网格应用中，服务质量（QualityofService，QoS）是个不可忽略的问题。

有些应用可能对计算资源能够提供的QoS有要求，这就使得调度算法有必要对资源进行筛选，将任务分配到符合其要求的资源上去运行。

对网络来说，QoS是指其带宽；还有用户自己定义的服务质量，如任务完成期限、任务的优先级等。

很多研究者在Min-Min算法的基础上，引入Qos，对Min-Min算法做了改进，提出了多种QoSGuidedMin-Min算法。

如在文献[14]中只取QoS的一个方面，那就是网络带宽，文献[15]提出了基于双重QoS约束的调度算法，其他考虑的QoS有网络带宽和任务完成期限。

文献[16]更是在Min-Min基础上对基于多QoS约束的网格计算做了系统研究。

3.9Max-Min算法

Max-Min算法与Min-Min算法相似，都是将任务指派给具有最小预测完成时间的主机，不同的是Max-Min算法从所有任务的最小完成时间中选取一个最大值，然后进行相应任务。

主机映射，之后重复此过程直至待调度任务集合为空。

4结语

任务调度是网格计算中重要的研究课题，一个好的任务调度策略能够使资源得到充分的利用，进而缩短任务完成的总时间。

本文对网格中现有的基于启发式的调度算法进行了简单的综述。

到目前为止，人们提出了很多网格系统的调度技术和算法，尤其是基于启发式的智能调度算法。

但是，不少调度算法还没有完整的理论依据、一些调度技术的结论还只是来自仿真结果,至今还没有形成网格计算的任务调度理论。

因此,该领域的研究还有待进一步发展和完善。

今后网格计算系统的任务调度研究将进一步与人工智能算法紧密结合，可能产生出大量基于智能的调度算法，使得网格计算任务调度更加高效。

另外，目前大多数算法少有涉及安全机制，但是在网格系统中分布式的调度离不开安全控制，需要相应安全机制，也

就是说,网格任务调度系统必须具有一定的安全机制，以便为网格提供安全可靠的任务调度服务。

参考文献

[1]IanFoster,CarlKesslman.ThenGrid:

B1ueprintfornewComputingInfrastructure,1stedition[M],MorganKaufmannPublisher,SanFrancisco,USA,1999

[2]MaozhenLi,MarkBaker著,王相林,张善卿,王景丽译．网格计算核心技术[M].清华大学出版社.2006:

2-3

[3]StreitA.Self-TuningJobSchedulingStrategiesfortheResourceManagementofHPCSystemsandComputationalGrids[D]．Paderborn:

theUniversityofPaderborn,2003

[4]樊莎.网格计算启发式任务调度算法的研究及在GridSim中的仿真[D].西北大学.2010.

[5]GrimshawA.S.,WulfW.A.,eta1.Thelegionvisionofaworldwidevisualcomputer[J].CommunicationsoftheACM,1997,40

（1）:

39—45

[6]罗红,慕德俊,邓智群,王晓东.网格计算中任务调度研究综述[J].计算机应用研究,2005:

22（5）

[7]Available:

http:

//www.cs.wisc.edu/condor/.2011,Nov10

[8]BuyyaR,AbramsonD,GiddyJ.Nimrod/G:

anarchitectureforaresourcemanagementandschedulingsysteminaglobalcomputationalgrid[A].ProcofInternationalConferenceonHighPerformanceComputinginAsia-PacificRegion[C].Beijing,China,2000:

283-289

[9]WhitepaperfromPlatformandIntel.EnterpriseGrid-TheNextGenerationArchitectureforCapitalMarkets[EB/OL].

Available:

2005

[10]ColiM.,PalazzariP.Realtimepipelinedsystemdesignthroughsimulatedannealing[J].SystemsArchitecture.1996,42:

465-475

[11]阎平凡,张长水.人工神经网络与模拟进化计算[M].北京:

清华大学出版社,2005,387-387

[12]FatmaA.Omara,MonaM.Arafa.Geneticalgorithmsfortaskschedulingproblem[J].Joumal