基于冗余分配的网格任务调度模型
2008-07-15
作者：宋 玮
摘 要： 研究了现有的调度算法，针对以出卖计算力为目的的网格，提出了基于冗余分配的调度模型，通过冗余分配实现了具有计算结果验证功能的调度算法。对该算法中的预测器" title="预测器">预测器、资源信息服务" title="信息服务">信息服务、调度器" title="调度器">调度器" title="资源调度器" title="资源调度器">资源调度器">资源调度器及分配器进行了详细介绍。
关键词： 网格计算 任务调度" title="任务调度">任务调度 冗余分配 结果验证
网格(Grid)是新一代的分布式计算环境与基础设施，它提供无缝的、面向主题的全面资源共享和高性能计算。它向人类描绘了一台虚拟的超级计算机画面，整个网格就是一台计算机，其资源可以取之不尽、用之不竭。目前，比较有影响的网格体系结构为国内的织女星网格体系结构[1]、五层沙漏结构[2]、开放网格服务体系结构[3](OGSA)和开放网格服务基础结构[4](OGSI)。任务调度是这些体系结构中必不可少的环节，因为用户的请求最终会被分置到网格的各资源节点上执行，从而最小化任务的执行时间，充分利用网格资源。
在网格计算中，通过对网格中计算力资源的整合，充分使用网格中的剩余计算力是一种最常见的利用资源的形式。在这种以出卖计算力为主的网格中，一个客户无法知道陌生的远端机计算出来的结果的正确性：有可能远端机为了获取经济利益故意伪造结果；或是远端主机本身的处理能力不够，如产生了错误的浮点结果等[5]。本文针对该问题研究了现有的网格调度算法，并对以出卖计算力为主的网格提出了基于冗余分配的调度模型。
1 网格中的调度算法
任务调度是根据任务的信息和资源的信息采用适当的策略把不同的任务分配到合适的资源节点上运行的过程。网格中任务调度的特点为：
(1)导致网格资源异构并且状态多变的因素主要有客观和主观两方面。客观上，网格是大范围的环境，自然会有很多意外的情况发生，这要求调度中具有预测系统，通过资源的历史记录对其现况进行预测。主观上，网格环境中大多数网格成员并不是专门为计算网格中的任务服务，只是提供部分计算力完成某些任务。资源的所有者并不希望它的资源专门为网格服务，因此会为自己的资源加上某些限制，如闲置周期以及用户对资源的使用权限等。同时资源的所有者有其自身的本地任务，不可能为网格上的远程任务提供完全的服务。在这种环境下的任务调度要复杂一些。
(2)由于任务对资源的需求各异，网格环境中的调度器必须综合考虑应用和服务质量的约束，以获得应用与资源之间较好的匹配，因此提出了基于服务质量的调度算法。这里服务质量的概念对于不同的资源可能有不同意义。例如，对于网络资源，QoS可为提供给应用程序的可用带宽；而对CPU资源，QoS意味着任务所想获得的处理速度，如浮点运算速度[6]。
(3)现有的调度算法都是基于粗粒度，并且相互之间独立或只有极少联系的任务。因为若任务联系过密，会导致通信量增加，反而使整个计算效率下降。这样，适合于网格计算的通常是一些容易分割成相互独立子任务的应用。
任务调度的基本思路可概括如下：
任务ti在机器mj的期望执行时间ETij(Expected Execution Time)定义为mj空载时执行ti的总时间。ti在机器mj的期望完成时间CTij定义为最终完成的时间(应包括完成其前面所有任务的时间)。设ai是ti的到达时间，bi是ti的开始时间，则CTij＝bi＋ETij。
常用的调度算法描述为：
(1) while there are tasks to schedule
(2) for all task i to schedule
(3) for all host j
(4) compute CTi，j=CT(task i，host j)
(5) end for
(6) compute metrici=f1(CTi，1，CTi，2，……)
(7) end for
(8) select best metric match(m，n)=f2(metric1，metric2……)
(9) compute minimum CTm，n
(10) schedule task m on n
(11) end while
算法需要不断地计算未调度的任务的期望完成时间。(2)～(4)为计算每个任务在每个机器上的期望完成时间；(6)是按照某种评价方式f1对任务i在每台机器上的期望完成时间得出其评价值metrici；(8)为使用某种标准f2在每个任务的评价值中找出符合标准要求的最优的任务与机器的匹配match(m，n)；最后将任务m分配到机器n上执行。
例如，Min-min和Max-min算法定义评价方式f1为取最小的完成时间，即某个任务i的metric值为它在所有机器上的完成时间的最小值。不同的是，Min-min的标准f2是选择metric值中的最小值，而Max-min是选择最大值。
从上面的分析可以看出，一个好的调度取决于两个方面，即对资源系统信息的预测及对应用程序(也可以认为是任务信息)的预测。资源系统的信息包括使用率、任务服务的速率、任务到达的速率等；应用程序的信息为工作量、可分割性、可并行性、完成时间等。一个关键的问题是：当为某些子任务指定的资源显示出不正常的状态时(从它的历史数据中预测而得)，如何保证并行应用的性能，即调度系统应在执行期间预测出资源的不正常状态(如负载过重)，重新安排调度。因此，一个调度算法是否成功取决于系统及应用状态预测的精确度。这种预测是从其历史信息中获得的。
根据预测的性质可将调度分为两种：一种是基于短期预测的调度，如AppLe项目使用了NWS服务提供的短期预测系统；另一种是基于长期预测的调度，采用这种方式的是GHS(Grid Harvest Service)。
2 基于冗余分配的调度算法
通过网格购买空闲的计算力有很大的发展前景，但这种方法很难保证所获得的计算力能够计算出正确的结果。这里提出冗余分配任务，使之在二个或多个节点上运行。其结果被多次验证后认为是正确的。
调度模型由资源调度器、任务分配器、资源信息服务和预测器构成。资源调度器从现有网格中的节点资源中找出合适的节点集，它和资源信息服务配合使用；任务分配器将任务分配到节点集中；资源状态预测需要消耗计算力，所以这里只做简单预测，同时忽略对任务信息的预测。
2.1 预测器
这里对计算资源的状况进行简单的短期预测。预测由计算资源节点提供，目的是减轻资源调度器的负担。
预测器收集节点自身信息并在资源调度器需要时给出预测值，它作为一个后台程序一直运行在节点机上。一旦节点开始运行，就主动加入网格，提供自身的信息。预测器获得系统的基本信息和可变信息。基本信息只需一次性获得，在资源加入节点时提供给资源调度器；可变信息随着时间变化，主要包括CPU的使用率和内存使用率。短期预测策略方式如下：
(1)设置一个线程，每隔1s收集一次动态信息，如CPU的使用率和内存的使用率。
(2)设置一个循环队列，将一分钟内的平均值不断地写入该队列。
(3)当有预测需求时将队列中的数值读出再取其平均值作为预测值。例如，当队列的大小设为5时就表示使用前五分钟的平均值作为预测值。
2.2 资源信息服务
提供资源信息服务的是哈希表，该哈希表的信息组织形式如图1所示。哈希表为调度器查找资源节点集提供依据。
哈希表的key以节点状态表示。因为节点状态是时刻变化的，所以对节点可用性的描述不需要用十分精确的定量方式得出具体的数值，可采用模糊的定性的方式表述[7]，即设置median、vacant、very vacant、busy、very busy五种状态，以计算节点的性能参数wholePerformace作为分类标准。例如：wholePerformace>=85，其状态为very busy；wholePerformace∈(60，85)，为busy；wholePerformace∈[40，60]，为median；wholePerformace∈(20，40)，为vacant；whole-Performace∈[0，20]，为very vacant。
2.3 资源调度器
调度器为某一应用找到合适的资源节点集。其策略为当要分配某一节点时再次获取它的信息，以该最新信息作为调度的标准。描述如下：
(1)获得应用的子任务数，并以其作为资源个数的最大请求数。
(2)在哈希表中从资源情况最好的队列中开始查询，如“very vacant”队列。
(3)从该队列中依次取节点，并依次与节点对应的计算资源联系，以获得其现有状态。
(4)若该状态差于该节点原来的状态，则不分配该节点，并把它从现有的队列中删除，插入到与其状态相一致的队列中；若优于现有的状态，则分配该节点，也把它从现有的队列中删除，插入到与其状态相一致的队列中；若等同于现有的状态，则分配；若探测到该节点不可用(退出网格)，则将其从队列中删除。
例如，一节点位于“very vacant”队列，但在分配时查询其性能参数值wholePerformace为50％，此时不分配该节点，同时将它从“very vacant”队列删除并插入到“median”队列中。
(5)整个查询结束的条件是：当找到子任务数个资源或是当资源数少于子任务数时，直接把所有的资源分给应用。
(6)当是单任务应用时，需找出两个或多个资源。
2.4 分配器
(1)冗余分配
当分配器获得合适的资源节点集后，就要决定如何安排子任务到各合适的机器上，以获得最佳的性能。这里提出一种冗余分配策略，即将一个子任务分配到多个机器上执行。采取这种方式的原因是：
①在分配节点集的时候是一种模糊分配，因为对资源信息的描述采用定性的方式。
②在描述资源性能时并未考虑网络的状态而且未对应用程序信息做出预测。所以，在同一个状态队列中，性能参数wholePerformace大的计算节点的运算结果有可能先于性能参数wholePerformace小的到达。
③冗余分配可以实现冗余执行，冗余执行具有两种功能。其一，如②所述，若将一个任务发送到多个节点执行，现状最好的节点会最早将结果送回。这样可以以较快的速度获得结果，同时避免了只发送到一个计算节点的缺点：若出现意外情况，需要重新调度任务到节点。其二，冗余的执行可以实现结果验证的功能。
(2)分配算法
分配器的算法描述如下：
对于每个子任务设置三个标志位：“分配状态”，其值为整数，说明分配的次数，初值为0；“已获得结果”，记录获得的资源节点计算的结果，若存在相等的结果，则为该子任务打上“删除标记”。
分配器一开始将子任务随机分配到调度器所找出的资源集上，分配状态变为1；若有资源送回子任务的计算结果，则将该结果记录到相应的标志位；若存在相等的结果，则为该子任务打上删除标记，并且通知其他运行该任务的计算节点停止该任务的计算，若不存在，各标住位不能做任何改变；同时再次随机选择一个未打上删除标记的子任务，将其分配到刚送回结果的计算资源上，分配状态相应加1。整个分配结束的条件是所有的子任务都打上删除标记。
3 算法性能评价
(1)减轻了预测的工作量。因为资源具有动态性，所以保留对资源的短期预测；因为适合网格计算的应用在划分时很容易转化为同样大小的子任务，所以忽略对任务的预测。
(2)分配策略可以很好地支持动态性，即节点的动态退出。若某资源节点P1不知原因地退出了网格，如用户误操作、自身系统出问题等，则分配给它的子任务V1总是无法完成。但是按照分配策略，V1总会被分配在节点集的其他资源上执行，最终V1会被执行完。这时P1上V1的运行情况已经不重要了。
(3)调度器和分配器的协作达到了负载均衡的效果。若节点机P1负载小，则它的计算节点的性能参数小，获得新任务的几率大；当它的负载逐渐变大时，计算节点的性能参数也变大，获得新任务的几率变小，新的任务会向其他性能好的节点分配，同时在其任务队列中的任务，也会因为任务在别处提前完成而被逐渐删除。
(4)该算法适用于以计算为主的网格。以计算为主的应用结果容易比较，但有可能出现各机器精度不一致的情况。这时可以对所需要的精度范围作出规定，对结果进行简单处理后再比较。
本文给出了基于冗余分配的调度模型，适用于以出卖计算力为目的的网格。希望此算法能为今后的网格研究提供一定的思路。
参考文献
1 徐志伟，李 伟.织女星网格的体系结构研究.计算机研究与发展，2002；39(8)
2 Foster J，Kesselman C，Tuecke S.The anatomy of the grid：Enabling scalable virtual organizations.International Journal Supercomputer Applicatins，2001；15(3)
3 Foster J，Kesselman C，Nick J M et al.The Physiology of the Grid：An Open Grid Services Architecture for Dist ributed Systems Integration.http：//www.globus.org/research/papers/ogsa.pdf
4 Tuecke S，Czajkowski K，Foster L et al.Open Grid Services Inf rast ructure (OGSI).http：//www.ggf.org/ogsi2wg，2003
5 Alexandrov A D，Ibel M，Schauser K E et al.SuperWeb：Re-search Issues in Java-Based Global Computing.http：//www.citeseer.ist.psu.edu/alexandrov96superweb.html
6 HE X S，Sun X H，Laszewski G V.QoS Guided Min-Min Heuristic for Grid Task Scheduling.http：//www.cs.iit.edu/~scs/psfiles/jcst_XHe-5-28.pdf
7 汤勇平.Java并行计算环境中的负载监测与预报系统.上海交通大学硕士论文集，2002