浅析网格环境中的任务调度算法的问题和策略

　【 摘 要 】 网格系统由大量异构资源组成，具有复杂、动态和自治等特点。高效的调度算法可以充分利用网格系统和处理能力，从而提高应用程序的性能。本文提出Segment Qos Min-Min RR任务调度算法，平衡了负载，提高了任务的完成时间和平均等待时间。
　　【 关键词 】 网格；调度算法；Qos；平衡负载
　　1 引言
　　网格是以资源共享为目的，利用互联网将分散与不同地域的计算机组织起来，成为一个虚拟的“超级计算机” 。每台参与的计算机就是一个“节点”，成千上万的节点组合起来，成为一张“网格”。从而能够充分地利用网络中的空闲计算能力，实现计算资源、存储资源、数据资源、信息资源、知识资源、专家资源等全面的共享。
　　随着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是一个三元组的集合，它们满足R1和R2规则，v∈T，1≤p≤m，t是任务v的起始时间，∈S，意味着处理器p在时间间隔t～t+d执行任务v，d是通过p的处理能力和v的L计算出来的，所以称t+d为任务v的完成时间。
　　R1：对每一个v∈T，至少有一个∈S。
　　R2：不存在这样的两个三元组，∈S； t≤t'≤t+d，t+d为任务v的完成时间。上述功能可以描述如下：
　　R1保证每一个任务v至少执行一次，R2是说每一个处理器在任何一个时刻最多只能执行一个任务，∈S称为一个任务实体。
　　用下列公式来计算处理器的代价：
　　RR算法确定可以提高资源的利用率，但同时也造成了资源的浪费，另外，同一时刻有多个处理单元在运行同一个任务也是一种浪费。
　　改进的RR算法：就是所有的任务对处理单元都是共享的，只要有到来的任务想让它立即执行就可以。根据任务分配的处理速度（MIPS），定义了最大处理速度（MaxMIPS）、最小处理速度（MinMIPS）和最大任务数（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上的预测完成时间最小，记minCT（i）=CT（i，j），并记录minCT（i）所对应的主机编号host_minCT（i）=j；
　　b.找出minCT矩阵中的最小值，即找出具有最小的最小完成时间的任务，并将它分配给对应的主机执行。例如，若任务Ta对应的minCT（a）最小，则将编号为host_minCT（a）的主机分配给任务Ta；
　　c.从任务集合T中删除任务Ta，更新主机Mk（k=host_minCT（a））的就绪时间R（k）=minCT（a），并更新预测完成时间矩阵CT。
　　4 QoS 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来对这些任务进行排序。根据平均ETC（keyi=ETC（i，j）/m、最小ETC（keyi=ETC（i，j））或最大ETC（keyi=ETC（i，j））来把这些任务按序排成链表。然后这些链表中的每一个任务分成同样大小的片，并且大任务的所有片先调度。每一个任务中的片均采用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、MicroGrid、SimGrid、GridSim、ChicSim、EDGSim等，其中重点SimGrid。表1中的数据就是用SimGrid模拟器仿真的。表1中记录了在任务数分别取200、300、400、500时，不同算法的任务最终完成时间。
　　8 结束语
　　网格环境里如何有效地管理资源和进行任务调度是影响网格计算是否成功的重要因素之一。由于网格体系结构以及拓扑结构比较复杂，因此在网格调度研究领域，很多调度算法的研究往往是侧重某一方，以使其在这方面的性能有所提高，如Segment Min-Min调度算法侧重于各个主机之间的负载的均衡，Qos Guided Min-Min启发式调度算法侧重于链路带宽对任务调度的影响，而Segment Qos Min-Min RR不仅考虑到了服务质量，而且也考虑到了负载平衡和动态性，并且适用对任务数量大的任务进行调度。网格计算对信息化进程具有相当重要的作用，凭借其固有的资源共享和协同工作能力，网格不仅可以实现计算资源的最大化共享和应用，避免资源浪费，更能够降低应用人才的门槛、应用开发难度和应用运行成本，促使信息化实现本质上的飞跃。
　　参考文献
　　[1] 邓见光，潘晓衡，袁华强.网格计算技术及其任务调度策略研究[J].东莞理工学院学报，2012（12），19（1）.
　　[2] 孙振河，李金宝，任美睿.网格计算环境下基于任务池的任务调度方法[J].黑龙江大学自然科学学报，2005（2），22（1）.
　　[3] 王玲利，网格计算中启发式任务调度算法的研究[D].浙江工业大学，2007年4月.
　　[4] 樊莎.网格计算启发式任务调度算法的研究互Gridsim中的仿真[D].西北大学，20010.
　　[5] 王向慧.网格计算中任务调度算法的改进[D].大连交通大学，2009.
　　[6] 杨兵强，仇建伟.网格环境下负载平衡研究[J].计算机工程与设计，2005，26（11）： 2975-2979.
　　作者简介：
　　刘冬晖（1973-），女，甘肃天水人，1998年毕业于石河子大学，2009获华东师范大学软件工程硕士学位，副教授；主要研究方向和关注领域：计算机教学与科研。