一个三层分布式计算网格任务调度系统

摘要：将调度系统与网格中其他组件有效整合、建立网格环境下任务调度体系结构、构建真实网格环境下的资源管理与任务调度系统具有重要的现实意义。本文提出了一个三层分布式网格任务调度体系结构模型，侧重解决网格固有的异构、站点自治与策略可扩展性；网格域调度器是分布式调度系统核心组件，详细阐述了网格域调度器的功能模块设计与任务调度步骤；最后，通过一个应用级网格任务调度实例，给出网格任务调度过程及效果。关键词:分布式处理系统；计算网格；任务调度；域调度服务0.引言现代高科技飞速发展，从宏观的星图描绘，到微观的粒子结构的研究；从军事领域的模拟核试验，到生物领域的后基因组计划的解读，再到大规模网络测量、仿真与模拟……，这些重大挑战性计算问题需要跨管理域利用大量分布式计算资源，而传统的分布式计算系统无法满足应用日益膨胀的需求，因此网络计算系统应运而生。网络计算系统(NetworkcomputingSystem)是由互联的异构机器通过共享本地资源构成的虚拟计算机，而网格(TheGird)是大规模的网络计算系统。跨越多组织和多管理域的计算资源由高速通讯链路连接，共同构成了Internet级的网络计算系统［1］。网格系统按照网格的设计目的可以分为计算网格(ComputationalGrid)>数据网格(DataGrid)、服务网格(ServiceGrid))三类。其中计算网格目的是将资源的计算能力聚合解决那些单系统无法在合理时间内解决的大规模科学计算和工程应用问题。网格资源管理与任务调度机制的研究具有重要的理论与实践意义。首先，网格资源管理机制是网格服务实现与整合的基础，是网格的“心脏”。资源管理的基本功能是接受网格中作业对资源的请求，从网格资源池中选择具有用户使用权限同时又满足应用约束条件的机器。资源管理系统匹配作业请求和资源属性，调度作业至匹配的资源，在调度资源集上运行作业。网格服务的实现与整合通过发现、分配、协商、监测等资源管理方式管理网格资源，保证端到端或全局的服务质量(QoS)。其次，网格资源的跨管理域、对象外延扩大化等网格特征引发了资源管理的新问题。在传统的计算系统中，批处理调度器、作业流引擎和分布式操作系统等资源管理系统得到了广泛的研究。这些资源管理系统均假设拥有资源的完全控制权，因此可以独立地实现高效机制与策略。然而，同样的假设并不适用于网格环境。我们需要开发新的资源管理方法管理跨不同管理域的资源，处理随之而来的资源异构性、绝对控制权丧失和安全策略的差异性。同时，由于采用面向服务的网格架构，网格资源管理机制不仅仅面向传统的资源(计算服务、网络带宽、存储系统空间等)，还包括数据库、数据传输、模拟等发布方式一致而功能各不相同的虚拟服务。最后，网格的协同任务调度是计算网格中高端应用分布式求解的性能保证。传统的计算系统或者以提高系统吞吐量，或者以降低挑战性问题的运行时间为单一的目标，然而随网络结构的日益复杂，不同组织采用不同的策略运作资源，资源使用者与资源提供者的目标存在不一致性甚至完全相悖。同时，网格应用要求并发分配隶属于多个管理域的资源，导致网格任务调度机制愈加复杂。综上所述，开发基于网格的资源管理框架和协同任务调度系统体系结构具有重要的理论研究价值。相关工作及其局限性近年来，随着Globus[2]，Legion[3]，Condor-G[4]和UNICORE[5]等保障作业可以远程部署到多个异构机群的网格基础设施不断完善，作为网格核心中间件与用户级中间件的重要组成部分，计算网格环境的资源管理和任务调度算法研究得到广泛关注。目前，国内外计算网格环境下的任务调度策略研究根据研究对象不同可以分为两类[6]：作业级任务调度(jobscheduling)与应用级任务调度(workflowscheduling/application-levelscheduling)。计算网格任务调度器的主要代表是Wisconsin大学的Condor-G、Poznan超级计算和网络中心提出的KB(Knowledge-based)Metascheduler[7]和PBS(PortableBatchSystem)[8]等Wisconsin大学的Linvy等人于1985年开始了一项称为Condor的计划，目的是利用空闲的计算资源。Condor-G是网格中间件Globus与分布式资源调度器Condor的结合，为用户提供基于网格的“个人批处理系统”。Condor-G利用特有的“聚合技术”(Flocking)技术依次连接各地的资源池，直到队列中作业需求被满足。KB(Knowledge-based)Metascheduler基于人工智能技术的元调度器是Poznan超级计算和网络中心提出的多目标资源管理体系结构的核心部分。这个调度器采用人工智能的多目标搜索技术进行调度决策。允许用户目标由单一的程序时间开销(响应时间、工作执行时间、加权平均延迟时间)，扩展到资源耗费标准(主存耗费、计算耗费、通讯耗费)和用户资金开销标准等。KBMetascheduler实现依托于Globus基础设施，同时提供一些高级服务，包括资源保持MDS信息扩展等。但是，KB系统仅仅处在预研阶段，很多技术并不完善。PBS(PortableBatchSystem):PBS是高性能计算机和LINUX机群系统的任务调度系统。PBS提出了资源管理和任务调度的全新思想，即将调度策略与资源请求、任务提交剥离开，形成一个完整可定制的调度模块°PBS的目的是对批处理任务的初始化和执行提供附加的控制。同时，批处理系统允许资源拥有者定义可用资源比例和权限°PBS系统组件间的交互基于客户服务器模式，服务器由一系列守护进程构成，采用任务请求对象队列模式管理任务。国内外作业级调度机制的研究处于起步阶段，当前的任务调度技术或者局限于具体的应用、或者忽视了网格资源跨管理域与多策略性，缺乏对开放、异构、动态环境的支持。其中，集中式的任务调度器一般由一个或多个机器共同构成，资源请求被转发到资源调度器，进行协同调度，由于瓶颈效应很难在网格上采用。而分布式调度器没有核心的调度组件，调度功能分布在各个网络资源中，资源请求者与资源提供者直接决定资源分配与调度，信息局部性和大流量导致无法实际应用于网格环境。因此，研究先进的网格任务调度系统对于解决大规模挑战性问题意义深远。计算网格调度系统的三层体系结构网格系统内部的任务调度模块是网格资源管理的核心，负责映射资源请求到匹配的资源。研究调度器组织方式与体系结构对任务映射与调度效率至关重要，应避免瓶颈效应、信息局部性和大流量效应，保证规模可扩展性与站点自治性。本文采用层级式的体系结构设计方法对应用在大粒度上采用高层调度器进行调度，而在小粒度上采用底层调度器进一步划分。层次式模型不仅可以避免集中与纯分布方式的缺陷，同时解决了网格固有的异构、站点自治与策略可扩展性。设计的三层分布式网格任务调度系统如图1所示。计算网格调度系统的三层体系结构位于此结构中最上层的是网格信息服务器(GridInformationServers)和网格元调度服务器(GridMetaSchedulingServer)，中间层由若干自治域组成，每个域内包含一定数量的网格域调度服务器(GridDomainSchedulingServer)，各种集群本地调度器、网格计算资源(GridComputingResources)与网格用户(GridUserGroups)构成了网格调度模型的第三级。网格信息服务器是任何网格软件基础设施中必不可少的组成部分，提供基本的资源信息发现与监测等基本机制。各个自治域至少拥有一个网格信息服务器。信息服务器位于域边界，动态的收集网络资源信息并周期性的与其他信息服务器交换信息。信息服务器需要处理元调度器、域调度器与用户提出的信息请求，匹配资源并返回可用资源集合给请求者。网格元调度器主要目的是协同各网格域调度的调度行为，避免域调度器过于关注最优调度结果而引发的资源争用、网格整体性能下降等负面效应。元调度接受域调度器的调度请求，通过与其他元调度器协同，提高系统吞吐量。网格域调度器是调度模型中的核心组成部分，同时拥有域与全局资源选择与映射能力，以降低用户应用执行时间为目标，并不具备协作和提高系统吞吐量的能力。域调度器数目依赖于域的规模。当网格用户向域调度器提交任务后，域调度器通过网格信息服务器收集网格信息。然后，域调度采用决策模块确定资源调度集，将元调度请求发送至元调度器。最后，根据元调度结果自动分发任务。网格计算资源一般为异构高性能计算资源，通过高速互联网络连接而成。不同的网格计算资源向本域的信息服务器注册，作为域调度与元调度器的映射目标。网格域调度器的设计网格域调度器是网格调度系统的核心，本节给出网格域调度器的功能模块划分和调度流程。3.1域调度器功能部件网格域调度器包括五个功能模块：文件解析模块、资源发现模块、调度模块、分发编译模块和提交执行模块。文件解析模块：解析XML文件，把其中的关于应用程序和用户要求的信息提取出来，并保存到合适的数据结构中，以供系统中的其它模块使用。资源发现模块：在不考虑应用程序模型的情况下，利用用户认证、用户授权、用户和应用程序的基本要求对网格中的资源进行粗过滤形成可用资源表，而后再对可用资源列表中的资源收集详细信息，这样有助于降低信息收集过程中的开销。调度模块：根据用户需求可以分为作业级任务调度模块和应用级任务调度模块。作业级任务调度的对象是高性能机群上的作业集，分别针对独立作业与并行作业，采用作业级调度算法实现映射过程。此外，最终调度结果需要与其他管理域的调度器协调求解。应用级任务调度由传统机群环境下基于任务图(DAG)的调度问题演化而来。通过将计算密集型网格应用抽象为粗粒度约束任务图，采用经济模型和数学规划策略将其映射到网格计算资源，目的是优化网格环境下某个或某类具体应用的运行性能。性能模板库将应用的性能模型与应用运行模型紧密结合，应用级调度器通过用户描述或编译分析得从性能模板库中抽取应用的性能模型。分发和编译模块：因为网格中各个资源的异构性，因此需要在各个资源上重新编译源文件。这个模块把应用程序源文件分发到满足最小要求的资源集合中的每一个资源上并重新编译。输入为满足最小要求的资源列表和应用程序信息，输出为在其成功完成了重新编译的资源列表。提交执行模块：根据调度方案，启动应用程序执行。输入为调度方案，输出为应用程序执行结果。3.2域调度器执行过程网格域调度器的调度步骤一般可分为三个阶段：1）资源发现阶段；2）资源信息收集和最优资源集合确定阶段；3）任务提交和运行阶段。资源发现阶段的主要目的是，用户获得潜在可用资源的资源清单，确定满足用户最低需求的资源集合，减轻详细信息收集的负担。绝大多数用户遵循授权过滤、应用程序需求确定、最低工作需求过滤三个步骤完成资源发现。网格域调度器功能模块与行为的综合分析如图2所示。网格域调度器结构与行为描述一个网格任务调度实例本节以同步迭代网格应用(N体问题)作为调度实例，阐述在实际网格环境下网格调度系统实现技术，展示网格调度系统的可用性、易用性和有效性。4.1网格软/硬件设置网格系统中包括20台主机，拓扑关系如图3所示。其中8台主机(hostl至host8)主频为Pentium1GHz，内存为1GB，安装的操作系统是RedHatLinuxrelease7.1，处在一个100M互连局域网段(subnet1)内；8台主机(host9至host16)的主频为PentiumIII500MHz，安装的操作系统是RedHatLinuxrelease7.2，处在一个100M互连的局域网(subnet2)内；2台IBMAIX服务器(host17至host18)，处理器为400MHz，512M内存；2台曙光天阔R220s系列服务器(host19至host20)，处理器为双CPU赛扬2.4GHz，2GB内存，操作系统为RedHatLinux7.3。局域网subnet1、曙光服务器和AIX服务器均通过10M以太网与交换机连接，而subnet2通过100M以太连接核心交换机。

H-45MsJTI...J计算网格实验床结构图H-45MsJTI...J网格资源管理与安全基础设施采用GlobusToolkit2.4,NWS作为网格监测系统，MPICH-G2作为消息通讯库。N体应用提交基于Web的网格资源使用方式可提供给用户图形化的界面及方便、易用的操作环境，把用户作业执行等复杂的操作交由后台程序完成，从而屏蔽计算主机上复杂的系统操作。用户可以随时随地利用通用浏览器来访问和使用网格资源，而无需安装和管理其它客户端软件。这种Web式资源访问界面称为网格门户。网格门户如图4所示。分布式计算网格门户用户在网格门户中输入信息包括同步迭代的应用程序相关信息和性能需求信息。应用程序相关信息包括程序的规模和程序在系统中的路径信息。性能需求信息包括：1）用户需要查询的MDS服务器，即用户需要查询的GIIS服务器。GIIS通过查询GRIS的注册信息得到整个网格环境中的资源信息；2）对软件环境的要求，主要包括一些必须和可选软件环境的要求，例如，MPICH-G2是运行并行进程必不可少的环境，NWS是预测未来系统环境信息的必要工具，用户可选的软件环境包括操作系统信息等；3）对内存和运行空间的要求，用户可以选择输入应用程序需要的内存和运行空间。N体应用调度网格域调度器根据子网分布情况分别布置在subnetl、subnet2、AIX与曙光节点上面，共计4台。相互间采用对等方式交换调度信息。网格环境中元调度器负责收集并协同域调度器运行。域调度器接受网格门户提出的用户需求后，采用网格资源自动发现收集网格资源信息。同时，分析N体应用的性能模型，从性能模板库中抽取合适的性能模型匹配。匹配结果发现符合同步迭代网格应用的性能模型，可以正确进行运行时间预测。而后采用应用级调度算法选择资源并进行映射。决策后调度系统调用分发与编译模块传输源代码至远程资源并重新编译。分发和编译模块的实现算法描述如下：for（可用资源表中的每一个资源）｛把应用程序的源文件分发到这个资源上用户的工作目录中if（上一步失败）从可用资源表中删除该资源else｛在这个资源上编译该源文件生成可执行文件if（上一步失败）从可用资源表中删除该资源｝N体应用执行在提交运行模块的实现中，我们没有直接利用网格中间件globus提供的服务，而是利用网格开发环境MPICH-G2中的任务提交命令，mpirun根据调度方案启动应用程序的执行。MPICH-G2中的任务提交命令mpirun利用网格中间件globus提供的服务完成上述功能。MPICH-G2中的任务提交方式是在命令中指定一个RSL文件，文件用RSL语言描述用户的资源请求和相关参数，mpirun根据RSL文件中的内容决定怎样使用网格中的资源。这样就可以用RSL语言描述我们最终的调度方案，然后利用MPICH-G2中mpirun命令按照这个调度方案提交并运行应用程序，在程序执行完毕后返回结果。N体应用运行结果应用级调度算法首先针对网络带宽因子进行聚类将20台网格资源划分为6个子集，分别为｛(hosts1，…，hosts8)，(hosts9，…，hosts16)，(host17)，(host18)，(host19)，(host20)｝。此后采用基于线性规划的迭代搜索方法从此6个子集中选择(hosts1，…，hosts8)和(hosts9，…，hosts16)作为映射集。此外，实现了贪心启发式作为比较对象。图5可见基于调度算法的N体问题执行时间较基于贪心启发式算法降低50%。当任务执行完毕后，网格门户将自动为用户收集运行结果并调用图形显示模块，将任务执行结果以图形的方式直观地显示在用户面前。运行结果的收集与显示采用基于Web浏览器的VRML技术来实现对N体问题的三维显示技术。通过收集N体程序运行结果传送各点的坐标值，写入相应的VRML文件中，通过浏览器开以打开相应的WML文件进行N体应用结果的3D观察，如图6所示。结论本文分析了采用集中式与纯分布式网格调度器进行任务调度的局限性，提出一个由网格元调度器、域调度器与本地调度器构成的三层分布式网格任务调度体系结构。合理的功能模块划分、网格资源自动发现、基于Web的应用提交与显示、自动分发编译、调度执行结果可视化使系统易于部署实施和使用。实践结果证明了系统的有效性。参考文献Fosterl,KesselmanC.TheGrid:BlueprintforaNewComputingInfrastructure[M].MorganKaufmann,SanFransisco,CA,1999:279~290.FosterI,KesselmanC,NickJ,etal.ThePhysiologyoftheGrid:AnOpenGridServicesArchitectureforDistributedSystemsIntegration[EB/OL].OpenGridServiceInfrastructureWG,GlobalGridForum,June22,2002./research/papers/ogsa.pdf.ChapinSJ,KatramatosD,KarpovichJ,etal.TheLegionResourceManagementSystem[J].JobSchedulingStrategiesforParallelProcessing.SpringerVerlag.1999:162~178.FreyJ,TannenbaumT,LivnyM,etal.Condor-G:AComputationManagementAgentforMulti-InstitutionalGrids[J].Clu