优化后的网格时间最优化算法

ISSN 1003044E-mail: ifoccnet.cnComputer Knowtedge and Technology电脑知识'$技术htp://w/ww dnzs.net.cnVol.6,No.19, July 2010, p.5173-5174,5193Tel:+86- 551-5690963 5690964优化后的网格时间最优化算法蔡宇翔,傅伟峰(福州大学敷计学院,福建福州350108)摘要:Nimrod- G是在计算经济网格体系结构(GRACE) 下开发的网格资源管理系统，它提供了一套基于期限和预算的调度策略DBC (Deadline and Budget Constained,以优化任务调度过程中的时间和费用问题。其中,时间最优化算法是DBC策略中最主要的算法之一,该算法的主要目标是对任务的处理时间进行优化。但该算法在预算分配和预算使用方西存在着不足,以致在任务预算较少时出现任务完成率低的现象。该文针对该算法的不足提出了一个改进方法,有效地改进了传统的时间最优化算法。关键词:网格资源管理系统;期限;预算;任务完成率中图分类号:TP311文献标识码:A文章编号:1009- 3044(2010)19- -5173 -02时间最优化算法是网格DBC调度策略中最主要的算法之-,它以任务完成时间为资源择优的标准,其主要思想是:根据任务的长度,为用户提交的任务集合中的每个子任务制定-个单独的子预算;并在这个预算范围内,把任务分配到能最早完成该任务的网格资源上。在预算比较宽松的情况下,时间最优化算法能极大地缩短任务总的完成时间;但在预算比较紧缩的情况下,时间最优化算法为每个子任务设定的单独预算则成为任务调度中的一个瓶颈因素,极大地影响了任务的完成率。1传统时间最优化算法的不足在预算分配上,传统时间最优化算法缺乏对总预算进行集中,动态分配的机制。在时间最优化算法中,未分配任务列表里的每一个任务都对应一个固定的子预算,此预算是根据该任务的长度和列表中任务的总长度,通过公式(1)计算得到的:h= Length(ti)(1)其中,Length()为任务q的长度;L为未分配任务列表中任务的总长度;B为剩余总预算;b为通过公式(1)计算得到的任务4的子预算。任务的子预算是进行任务调度时网格资源的准人标准。在对某个子任务进行资源分配时，首先要确定该子任务的可用资源列表。在所有的网格资源中.只有那些费用不超过任务的子预算的资源才能加入到该任务的可用资源列表中去。另外,只有当可用资源列表中存在能在期限内完成任务的资源时任务才能被成功调度。实际上,时间最优化算法这种将总预算按子任务的长度,分割成固定的子预算的做法是不合理的。因为在用户提供的总预算较小时,时间最优化算法不能够将有限的预算进行集中,动态地分配,从而使尽可能多的任务得到执行。同时,对总预算进行分割的做法会使所有任务的子预算都呈现一种紧缩状态,这通常会使得长度较大的任务因找不到能在期限内完成该任务的资源而无法被调度。在预算使用上,时间最优化算法缺乏对调度失败的任务所占用的预算进行回收利用的机制。另外.在具体的任务调度过程中，时间最优化算法采用遍历未分配任务列表的方法,逐个地对列表中的任务进行调度。在这个过程中,如果-一个任务被成功调度,它将被移出未分配作业列表,并在以后的调度过程中不再占用预算份额。但是,如果一个任务没能被成功调度,那么它将始终留在未分配作业列表中,并持续占用-个相应的预算份额.直到本轮调度结束。因此,如果一个任务没能被成功调度,那么剩余的任务也很可能继续因为预算不足而不能成功调度。2改进后的时间最优化算法2.1改进方法鉴于上述时间最优化算法在预算分配和使用上存在的不足,本文提出以下两点改进方法:方法1:通过计算和推斷的方法,预测任务在各网格资源上的执行费用和完成时间:如果某项任务在其初始子预算下无法找到可用的资源,则以初始子预算的3倍为限,逐步提高该项任务的预算,看是否能找到可用资源。在提高预算的过程中,采用逐步提高的办法,只要在某-预算下找到了可用资源就不再继续提高该任务的预算量。这样做既可以帮助原先预算不足的任务找到可用资源,又可以尽量控制该任务的预算使用量。方法2:如果将某--项任务的预算量提升到其初始子预算的3倍后,依然找不到可用资源,则将该任务暂时地移出未分配作业列表,以释放其占有的预算份额,缓解剩余任务的预算紧缩状态,提高任务调度的成功率。在此,预算增加之所以要以初始预算的3倍为限的原因是:也许通过继续不断增加预算最终能为任务找到可用资源,但为调度该任务付出的预算代价是巨大的;以其使用巨额的预算来保证一个任务的运行.还不如回收该任务占有的预算份额以增加后续任务的可用预算量,进而提高整体任务的完成率。2.2改进后的时间最优化算法根据上节中提出的改进方法,我们对时间最优化算法进行了优化。现*中国煤化工程介绍如下:YHCNMHG收稿日期:2010-04-27网络迟讯及安全”5173Computer KnowWedge and Technoloy电脑知识与技术第6卷第19期(2010年7月)算法描述:1)资源发现:通过网格信息服务器,检索出本次调度中能被使用的资源。2)资源交易:根据每秒的CPU费用和单位费用所能处理的任务量.得到任务在不同资源上的调度费用。3)如果用户提供的是D.B参数,则根据用户的需求和资源的价格计算出绝对期限和侦算。4)任务调度:重复以下步蠊,直到所有任务都分配,或者期限或预算超出限制: .①通过计算和推断的方法,预测资源消耗率以及资源可用份额。②如果某个资源的可用性方面发生了变化,则将已经分配给该资源,但还没提交到资源上执行的任务适当移出一部分到未分配列表中。③对未分配列表中的任务.重复如下步骤:a从未分配作业列表中取出一个任务(矩作业优先)。b.确立任务的叮用资源列表:如果在任务的初始子预算下可用资源列表为空.则以初始子预算的3倍为限,逐步增加任务的预算量,直到找到可用资源为止。e.如果任务的叮用资源列表最终为空.则暂时将任务从未分配任务列表中移出.并转至步骤a;否则转至步骤d。d.对可用资源列表中的每个资源,根据先前任务的完成情况以及资源的川用性状况,估算出任务在该资源上的完成时间。e.将资源列表按照任务完成时间的升序排列。f如果任务完成时间不超过期隈.则把任务分配给排序后的资源列表中的第一个资源,并将任务从未分配任务列表中移除。5)按照步骤4的分配方案，根据资源的处理能力,将作业异步地发送到资源上去执行。6)当作业处理完毕,资源将结果反馈给接收模块,同时更新资源上的信息。3模拟实验本文提出的对传统时间最优化算法的优化方案,主要是在任务因子预算不足而无法找到可用资源时.通过增加子预算并回收调度失败的任务所占用的预算份额的方法,来保证低预算时任务的完成率。为了证明该优化方案的优化效果,本文取定了三个递增的期限，并在这三个期限下观察了预算对传统的时间最优化算法(以下简称为T0)和改进后的时间最优化算法(以下简称为oro)、莫南名 T厂.路构，σs TPEMSISFE汽事黄略ICSPEMIs)的任务完成率的影响。Compg.Apha5164J3TI Sana,OSF13.1实验数据设置在仿真实验中，本文根据网格测试环境WWG (The Word-贮37。 Timec-sharedWide Crid)[51]的一个资源子集.模拟了不同体系和配置的计算资190.0源。其中模拟时需给出资源的如下属性:资源名称,服务器类型、Q20.LImuxSiLOngn 3200操作系统.处理单元(PE)数目.每个处理单元的计算处理能力、每个处理单元每秒的价格。具体的资源设置表如图1所示。SCI.Onp 300在网格任务方面，我们创建了100个网格任务，其长度为SoL.Ongla 320010251000(MI)有10%浮动输人数据和数据结果文件大小为100KB,RIX带有5%浮动。另外,考虑到单用户和多用户对调度算法性能的评价结果是一-致的,所以本文只考虑单用户的情况。sGL,Onga 3200Tume-shared3.2实验结果对比RI0 SunLin.SolasTnm-hred123.66在既定的网格环境下,任务的完成情况主要是由用户提供的困1资源配置围Budget 和Deadline,以及选用的调度策略(算法)决定的。首先,从预算对两个算法的任务完成率的影响方面进行分析。随着预算的增加,TO和OTO算法的任务完成率都呈上升趋势。但TO算法的任务完成率的增张呈现跳跃性状态,这是因为:T0算法为任务设置的静态子预算是资源接人的巨大限制因素.如果只是少量地增加预算,那么由于子预算的限制.任务调度的可用资源列表可能依然保持不变,因此任务的完成率并没有得到提商;但是如果预算增加到一定量,那么一些相对比较便宜的资源就可以加入到可用资源列表中.这时便会极大地提高其任务完成率。相对TO算法跳跃性的增幅,0T0算法下任务完成率的增幅则相对平稳,这是因为:0TO算法为任务设置了动态,可增加的子预算,子预算对资源接人的限制性会相对较小，因此即使小幅地增加预算也能--定最地提高任务完成率。接者,从期限对两个算法的任务完成率的影响方卤进行分析。随着期限的增加,TO和0TO算法的任务完成率都呈上升趋势.但T0算法增幅会比OTO算法的大些。这时因为:TO算法的静态子预算极大地限制了任务调度的可用资源，这时只要适当地放宽期限,任务的叮用资源就会极大地增加.进而提高任务完成率。而OTO算法因为采用了动态子预算机制,所以任务调度时的可用资源受子预算的限制也相对较小,所以放宽期限对可用资源量地影响也较下,因此任务完成率的增幅也较小。总的来说,0T0算法因为采用了动态子预算机制,从而能在预算不足时较集中地使用预算，进而使得在预算限制内更多的任务得到成功调度,因此与T0算法相比,OTO算法在预算不足时极大地提高了中国煤化工4结论CNMH G本文首先分析了传统时间最优化算法TO的不足,并提出了相应的改进刀法;按有,在以上化断出巷硒上,我们设计了OTO算法,并介绍了该算法的思想.流程以及核心代码;最后.我们在利用Gridsim搭建的仿真平台上进行了对比实验,通过对比OTO算法和TO算法在不同期限和预算限制下的任务完成情况，充分证明了OTO算法的优越性。(下转第5193页)5174...网络洒讯及安全.......本栏目责任编辑:冯蕾.第6卷第19期(2010年 7月)Computer Konowledge and Technalogy电有知识与技术从实验结果可以看出，比较稳定的门限值在0.4到0.7之间，在这之间不同同查门限的情记内,平均损失比较固定。在门限为1的情况下,损失最低。加人成本分析后，系统误判随着门限的不同而出现的情况如图6所示，80图6是针对doe攻击的情况，从中可以看出误判的比率随着门限的降低而降低.在0.65左布,进入误差为零的状态。声畚考文献:川Landwehr C E.Bull A R,McDermot J P,et alA Taxonomy of Computer Pro-gram Security Flaws[J].ACM Computing Surveys,1994,26(3):211-254.[2] Lindqvist UJonsson E.How to systematically cassif computer security intu-田6误判情况sions[C].Oakland CA:Proceedings of the IEEE Symposium on Research in Se-curity and Privacy,1997.[3] Howard J D,Longsta T A.A conmon language for computer security nidens[R].Technical Repot SAND98-8667,Sandia National Lab-oratories,1998.[4] Schultz E E.网络安全事件响应[M].段海新,译.北京:人民邮电出版社,002.(上接第5174页)参考文献:[1] BUYYA R.Economic-based distributed resource management and scheduling for grid computing[D],Melbourne:School of Computer Sci-ence and Software Engineeing, Monash University,2002.[2] BUYYA R,ABRAMSON D,GIDY J.Ninrod/C: architecture for a Resource management and scheduling sytem in a global computa-tional grid[CV/Proc of the 4th Intemnational Conference on High Performance Computing in the Asia-Pacific Region.IEEE ComputerSo-ciety2000:283- -289.[3]丁箐,陈国良,单九龙,等.一个基于证券市场的计算网格环境下的资源分配模型J.小型微型计算机系统203-.41);14-15.[4]夏靖波,刘颖.网格原理与开发[|M].西安:西安电子科技大学出版社200633-37.[5] FOSTER L,KESSALMAN C.The grid blueprint for a new compuing infrastructure [M].San Francisco: Morgan Kaufmann Publishers Ine,1998:279- -309.[6]吴俊,张大方.一个扩展的以QoS为指向的网格任务调度算法J].计算机工程与科学20,2.(4);66-70.0[7]王大晨,王淑静.成本/时间综合优化网络资源调度策略及价格算法[J.北京理工大学学报204.24():617-621.[8]朱鲁梅.基于计算经济的网格任务调度算法研究[D].长沙:湖南大学,2006.中国煤化工MYHCNMHG本栏男零年界叠帮.......网络讯及安全“5193