《一种应用于网格计算环境的任务调度模式.doc》由会员分享，可在线阅读，更多相关《一种应用于网格计算环境的任务调度模式.doc（16页珍藏版）》请在三一文库上搜索。
1、一种应用于网格计算环境的任务调度模式1网格计算中的任务调度问题 网格计算1是分布式计算的一种，目的是为用户构建一个统一的、整合的、虚拟的计算资源，以实现跨组织的资源共享、管理与访问。网格所要实现的功能，远不止是数值科学计算，还包括各种形式的协同工作、业务流整合、数据信息共享与互操作等。要真正实现网格在现实生活中的应用，需要解决的技术问题还很多，如标准、安全、资源管理、任务调度、中间件设计与实现等。其中，网格计算的任务调度是一个至关重要的问题，网格环境中的管理程序需要运用合适的策略，协调多个用户之间对网格资源的合理使用，即将一组相关的任务调度到特定的计算资源上去执行，任务调度的策略和算法将直接影
2、响到任务执行的效率以至成败。 在传统的分布式计算领域，有很多比较成熟的任务调度理论与方法，如基于图论的调度算法、01规划策略、启发式调度算法、基于遗传算法和模拟退火算法的任务调度策略、启发式表调度算法等2。不过，这些算法的理论基础是高度抽象了的传统分布式计算环境以及任务模型，而网格计算的任务调度问题中计算资源和任务都具有其本身的特点，如计算资源的自治性、计算资源组织的自相似性、任务对特定计算资源的依赖性等。因而需要去探究更合适的任务调度模型，并在此基础之上设计并开发简单实用的调度算法，以尽量贴近特定的实际应用。各研究机构也已经提出了很多任务调度模式，如基于简单轮询方法、微观经济模型、各种经典非
3、线性优化算法等，也有综合多种策略的模式。这些模式各有其优缺点，仍处于不断发展与完善的过程之中，同时人们也在努力探索新的任务调度模式，以期更高效地进行网络计算环境中的任务调度。 本文提出了一种新的任务调度模式，充分考虑了网格计算环境本身虚拟化、分层次及自治的本质特征，以及网格任务的粗粒度、资源依赖、重复执行等特性。同时设计实现了一个可扩展的网格任务调度器，以验证并评价本文所提出的任务调度模式及相关算法。 2网格任务调度模式 网格计算环境中的任务调度，就是根据一定的规则和策略，将构成网格应用程序的一组任务映射网络计算环境中的多个节点上去执行，以期取得较好的系统执行性能，实现系统的负载平衡。任何一个
4、任务调度系统都是由运行环境、程序任务、调度程序构成。相应地，在网格环境的任务调度问题中，此三部分分别为网格计算任务、网格计算资源和任务调度程序。 21网格计算任务 由于网格计算环境本身的复杂性，小规模的应用程序并没有必要部署到网格环境中。并不是任意的任务都适于在网格环境中运行，适于在网格计算环境中运行的应用程序具有如下基本特性： a）任务粒度大。网格上运行的任务，一般运行时间都比较长，计算量较大，子任务间通信量小；否则，其效率可能低于在普通的计算环境中运行的效率。 b）任务可划分。在网格之上运行的应用程序，一般可以划分为若干个子任务，由不同的计算资源协同完成，各个子任务之间有着明确的先后约束关
5、系。 c）对特定计算资源的依赖性。就当前的技术以及近期的技术趋势而言，尚无法做到在任意的计算资源上运行任意的任务，尤其当某个子任务只能由特定的仪器或设备来完成时，其他资源无法替代，因而，只能是在特定的某个或某些计算资源上运行特定的任务。 对于网格任务，建立的描述模型如下所述：在提交任务时，需给出任务时限要求，即最早开始时间与最迟完成时间；任务可以划分为预定义的网格子任务，并给出（或估算出）各个子任务计算及其他开销所需要的时间；给定可以完成特定子任务的计算资源；任务的各个子任务构成一个 DAG（directed acyclic graph，有向无环图）。DAG任务图示例如图1所示。其中：nx为任
6、务的序号；括号内的数字为计算量参数。 22网格计算资源 从任务调度的角度来考虑，无论是OGSA3还是 WSRF4，或是文献5提出的任务池模型，基本思想都是将网格中的各种计算资源抽象为虚拟组织6，各个虚拟组织通过网格服务7连接起来构成虚拟的网格环境；同时，各个虚拟组织所提供的网格服务也不尽相同。例如，会有专门提供某种算法的高性能计算服务的虚拟组织，也会有专用设备作为网格环境中的一个虚拟组织。这就使得网格中的资源会具有如下特点：资源间的耦合度比较松；每个资源都有特定的可用时间；资源实际上有组织，只是不为最终用户所感觉；资源具有相当的自治能力。 基于以上分析，本文建立了如下的针对任务调度的网格资源模
7、型。网格中的资源可以抽象为分层级的虚拟组织（virtual organization，VO）。一个 VO 中可以有一个或多个更小的VO，以完成更具体的任务。一般来说，认为最底层的VO只能完成一种特定功能。上层VO可以获得其下层VO的参数、状态以及未来任务计划，包括指定的下层 VO 的可用时间。在本文所提出的调度模式中，有一个集中的资源描述服务，但具体调度分层级完成。对资源描述服务来说，网格资源分为三个逻辑上的层级：第一个层级为对它来说有调度权限的能完成某一特定功能的逻辑上的组织；第二个层级为逻辑组织中各个网格计算资源；第三个层级为计算资源中具体的物理计算设备。同一个物理资源中的各个网格资源可以
8、属于不同的逻辑组织，而若一个网格资源同时提供多种服务，则认为它同时表现为多个网格资源，如图2所示。 23网格计算任务调度程序 网格计算环境中的任务调度程序所要完成的工作是将划分后的子任务安排到适当的计算资源上去运行。 任务调度系统的数据来源包括：a）任务描述，即新下达的任务，以及网格环境中此调度系统可以管理的计算资源中已经在运行的任务及其参数；b)计算资源描述，即各网格计算资源能完成的工作、能力、当前负载情况以及任务队列中的排除情况以及其他相关信息；c)统计数据，主要是计算资源以前完成任务情况的统计，为新的调度及优化策略提供参考，包括计算资源的实际利用率、宕机频率等。 任务调度的过程：取得新下
9、达任务的描述，按相关说明将其划分为一组子任务，并计算得出各个子任务的最早/最迟完成时间，生成子任务对象；导入当前所管辖的计算资源的信息数据，包括计算资源本身的参数、当前正在运行的任务、任务队列情况等；根据经过划分和计算的子任务的需求，以及计算资源的现有条件，按一定规则将各个子任务调度到适当的计算资源。在调度的过程中，如果发生某个或某些计算资源无法完成任务而导致整个任务无法在指定时间内完成的情况，则进行调度方案的优化并重新执行调度。 3任务调度算法设计 基于上述调度模式的任务调度算法由三个部分构成，即子任务生成算法、初始调度算法和自动调整算法。其中:子任务生成算法负责算出各个子任务的最早开始时间
10、和最迟完成时间；初始调度算法将各个子任务直接调度到计算资源；自动调整算法用于对调度结果自动进行调整。 31子任务生成算法 子任务生成算法需要完成的任务是生成子任务对象，并根据给出的所有任务计划最早开始时间和最迟完成时间以及每个子任务估计需要的时间（包括通信等其他时间开销的估计值），计算出每个子任务的最早开始时间（earliest start time，EST）和最迟完成时间（latest finish time，LFT）。用 Task 表示任务整体，SubTaski表示第i个子任务对象，totalLoad 表示子任务所需总时间估计值，workLoad 表示子任务工作时间的估计值，overloa
11、d表示子任务的其他开销的估计值，n表示子任务数目，则子任务生成算法如下： SubTask0.EST=Task.EST; SubTaskn+1.LFT=Task.LFT;/引入两个虚任务 Construct DAG;/构造 DAG，描述各子任务依赖关系 for i=1 to n do/计算子任务所需时间 SubTaski.totalLoad=SubTaski.workLoad+SubTaski.overload; Time findEST(SubTask) /计算最早开始时间 Time est=SubTask0.EST; if(SubTaskj.prev=SubTask0) return est
12、; for each SubTaskj in SubTask if(SubTaskj.EST=null) SubTaskj.EST=findEST(SubTaskj.prev); est=max(est,SubTaskj.EST+SubTaskj.totalLoad); return est; for i=1 to n do/计算每个子任务的最早开始时间 if SubTaski.EST=null; SubTaski.EST=findEST(SubTaski.prev); /计算各子任务最晚完成时间的算法与计算最早开始时间算法基本相同，从略 32初始调度算法 首先定义描述资源的符号。Factor
13、y 表示可以完成特定功能的逻辑上的组织，Workshop 表示网格计算资源，Device 表示具体执行功能的计算设备，三者是不同级别的功能单位。MaxLoad 为功能单位最大可承受的负载，CurrentLoad 为功能单位当前负载。其余符号将在算法描述中说明。 在进行初始调度之前，需要有一张STR表（子任务资源对应列表）。进行任务调度时，首先根据STR表将各个子任务调度到各个 Factory 的任务列表中；然后由 Factory自动调整该子任务调度给哪个 Workshop 来执行；最后由Workshop决定由哪个 Device 来具体执行此项子任务。每一项任务都有多个 Workshop（Dev
14、ice）可以完成。任务的初始调度原则是，根据预定义的优先级，将任务调度到优先级尽可能高的Workshop（Device）。可以看出，Factory 需要的调度与自动调整算法和Workshop 所需算法相同，这一特性实际上是由网格环境的自相性决定的。以 Factory 为例介绍初始调度算法及自动调整算法。 为方便进行判断和调整子任务的加载方案，将每个 Workshop 按时间段划分，用符号 WorkUnit 来表示某个时间段内的某个资源，将子任务加载到其最迟完成时间所在的 WorkUnit。任务初始调度算法如下： Factory.addSubTask(SubTask) unAdjustedSub
15、Task.add(SubTask);/将子任务添加到未调整列表 currentLoad+=SubTask.totalLoad; flag=flase; for each Workshop /按优先级顺序尝试 if(Workshop.add(SubTask)/是否能成功取决于加载后负载 量是否超出限度 flag=ture; break; if(!flag)/如果最终加载失败，则加载到优先级最高的Workshop Workshop0.forceAdd(SubTask); for each SubTask Factoryi.addSubTask(SubTask); /将子任务添加到 Factory，
16、i由子任务资源对应列表决定 33自动调整算法 在初始调度算法中，只是简单地将任务加载到 Workshop，并没有考虑某些 Workshop负载过载的处理，因此，在初始调度完成后，需要对方案再进行调整，以解决可能出现的负载过载的问题。从初始调度算法可以看出，只有优先级最高的 Workshop 可能会出现负载过载，它需要执行如下自动调整算法： Boolean autoAdjust() from last WorkUnit to first WorkUnit /从最晚的WorkUnit开始调整 if currentLoad 仿真数据提供模块：只用于进行网格环境及任务的仿真，主要完成的功能包括：根据配
17、置生成特定的网格任务描述；构造虚拟的网格环境，指定各个网格资源的属性（能力、角色、可用时间、当前工作负载情况等）以及网格资源构成的虚拟组织；仿真执行调度的结果，给出调度后各个网格资源的情况、任务调度的情况，以及详细的调度过程描述。 网格任务与资源管理中间件：只用于将来实际的网格计算环境，负责将网格环境中的资源和任务参数提供给数据抽象模块。仿真实验无须此模块的支持。 数据抽象模块：用统一的数据结构来描述网格任务、网格资源和调度方案，这样，调度算法只需直接使用这个统一的数据结构，不必考虑它是在仿真环境中还是在实际的网格环境中进行调度，以使得本文所提出的算法或者将来设计开发的其他算法，在经过了仿真环
18、境的验证之后，无须修改就可以直接应用于实际网格环境。 算法模块：利用数据抽象模块所提供的数据结构，完成资源对象的初始化、子任务展开、初始调度、自动调整等各个算法，最后得到一个调度方案，给出经过格式化的结果，或者给出无法完成调度的报告。另外，算法模块提供接口供进行测试的和将来实际应用中的其他模块进行调用。 通用工具模块：实现的是开发环境（Java）所没有提供而多个模块会同时用到的功能，如对网格资源或任务的排序、时间日期格式转换、定制的通用数据结构等。 配置模块：对调度器的配置，以配置文件的形式给出，调度器开始运行时，首先读取此配置文件中的系统参数。 用户与调度器通过用户视图模块进行交互。 调度器
19、中与本文调度算法最密切相关的类包括任务、子任务以及各级网格资源所对应的类，称为核心类，其他类统称为辅助类。核心类在调度器的体系结构中均属于算法模块。类之间的关系如图4所示。辅助类完成数据读入、生成数据结构、输出结果、配置等任务。 42调度算法的仿真实现与评价 对任务调度模式及调试算法的仿真实现的分析与评价从以下三个角度进行： a）正确性。只有在保证算法实现正确的前提下，方可对此任务调度模式的其他方面进行评价。算法正确性的具体表现在，子任务展开过程中根据整体任务及各个子任务的工作量计算得到的各个子任务的最早开始时间与最迟结束时间，初始调度过程中根据子任务以及网格计算资源参数调度各个子任务的行为，
20、以及自动调整过程中判断与调整，均与手工推演结果一致。测试用例覆盖了可能会出现的调度结果：未调整子任务而加载成功、调整优先级最高的计算资源的子任务而加载成功、调整多个计算资源的子任务而加载成功、调整多个计算资源后加载失败。 b)效果。任务调度算法的效果表现在两个方面：a)调度的成功率，即调度后任务能够成功执行的概率；b)计算资源整体上的负载平衡情况。 在完成初始调度后，对每个发生任务量超载的计算资源执行自动调整算法，去判断是否能够通过在计算资源所属的 WorkUnit 之间移动部分任务而达到每个 WorkUnit 的工作负荷都不超出最大工作能力的要求，这样，就保证了只要最终判定调度方案可行，则每
21、个计算资源的每个 WorkUnit 的工作负荷都将不会超出最大工作能力，调度算法本身最大程度地保证了调度的成功率。任务成功执行的概率直接取决于计算资源本身正常工作的概率，在初始调度算法和自动调整算法中，都是尽量将任务调度到优先级较高的计算资源上去运行，而优先级主要由计算资源的能力和稳定性来决定，所以，这也进一步提高了任务能够成功执行的概率。 负载平衡的目的是为了避免网格计算环境中某个计算资源任务特别繁重而成为整体上的瓶颈。在初始调度算法中，子任务最先尝试加载到优先级最高的计算资源所包含的WorkUnit，如果超出则尝试优先级次之的计算资源，依次类推，如果尝试至优先级最低的计算资源仍无法加载，则
22、直接加载到优先级最高的计算资源，这样会造成优先级最高的计算资源中某个WorkUnit 的工作负荷超出其最大工作能力，然后再通过自动调整算法进行调整。在自动调整算法中，也是先在优先级最高的计算资源中进行，如果失败则将部分任务移至优先级次之的计算资源，再次进行自动调整，依次类推，直到得出成功或失败的结论。优先级最高的计算资源计算能力更强，也更稳定，因而能够成功完成任务的概率也就越高，所以将尽可能多的任务交给这些计算资源去执行。这样，可以充分保证以更高概率按计划完成任务的前提下，每个计算资源上任一时刻的工作负载都不会超过其最大的工作能力，不会成为网格计算环境的瓶颈。 c）效率。对网格任务调度算法本身
23、运行效率的评价，当前尚无成熟的模型与基准，难以进行横向对比。本文在此分析与评价的是算法效率本身的一个重要方面：子任务数增加时计算完成调度方案所需时间变化趋势。 仿真实验过程中，仿真数据提供模块预设了 50 个逻辑组织（Factory），每个逻辑组织下有不定数量的能力不同的计算资源（Workshop 和Device），并在部分计算资源上随机设置了预调度的负载。然后，分别向调度器提交具有不同子任务数的任务，以验证算法的正确性并分析算法的执行效率。子任务之间的关系根据文献8的构造方法生成。图5给出了各算法模块的处理不同子任务数的网格任务运行时间统计，不考虑调度器初始化等开销。 由图5可知，在上述条件
24、下，随着展开得到的子任务数目的增加，各个算法的计算时间消耗基本呈线性增长趋势。调度过程中可能最坏情形是在所有的计算资源上都执行一遍自动调整，其所需要的时间将主要取决于计算资源的数目和能力、各个计算资源上原有子任务的数目和任务量，以及展开得到的新子任务的数目和任务量。 5结束语 本文提出了一种新的网格任务调度模式及相应的任务调度算法，设计并实现了相应的算法以及一个网格任务调度器。网格资源模型贴近实际的网格计算环境，充分考虑了网格计算资源的自治特性，任务调度分层级、分布式自主进行；面向特定应用，适用于网格任务分解后所得到子任务粒度较大且有一定规则可循的网格应用；支持对任务调度模式具体实现的定制，相
25、对于通用的任务调度模式，可以获得更高的效率；在网格任务执行之前，根据计算资源的能力及当前已经加载的工作量的情况，对能否成功调度新下达的网格任务进行判定，避免在网格应用程序的运行过程中动态调度而降低整体的效率；在算法中，调度到优先级较高的资源上的任务更多且不会超出其最大工作能力，保证了任务可以更快速地完成，同时提高了任务整体的成功率；网格任务调度器体系结构设计具备良好的可扩展性，同时兼顾了任务调度仿真与具体应用的需求。 此任务调度模式中尚存在一些问题亟待深入讨论： a）子任务工作量的估计模型。在仿真实验中，各个子任务的工作量是直接指定的。当应用于实际的网格环境时，必然要面临估算子任务计算量的问题
26、。可以通过两种途径尝试解决:(a)根据算法的时间和空间复杂度对计算量进行估计，直接在任务描述中给出计算量的估计值；（b）更为理想的方法是使用专门估计计算量的程序来完成，通过使用数值操作、存储器访问操作和消息传递原语操作等来估计得到任务的计算量。 b)计算资源的计算能力量化模型，包括计算资源的优先级、最大工作能力等。在描述所提出的任务调度模式的模型时，已经为计算资源的描述设计了一种实现途径，即将每个计算资源的能力划分为若干个相同的部分，这样性能各不相同的计算资源在任务调度系统中将各自表现为多个相同能力的计算资源的组合，似于操作系统中对处理器的时间片划分；另外一种方法是计算各个计算资源的相对性能。对于能够完成某一子任务的所有计算资源，设置一个基准最大工作能力C，代表在固定时间内能够完成的计算量，以计算资源在同一固定时间内能够完成的计算量与C的比值作为此计算资源能力系数，在生成WorkUnit对象时，通过基准最大工作能力与计算资源的能力系数求得其本身的最大工作能力。