優(yōu)化后的網(wǎng)格時(shí)間最優(yōu)化算法

ISSN 1003044E-mail: ifoccnet.cnComputer Knowtedge and Technology電腦知識'$技術(shù)htp://w/ww dnzs.net.cnVol.6,No.19, July 2010, p.5173-5174,5193Tel:+86- 551-5690963 5690964優(yōu)化后的網(wǎng)格時(shí)間最優(yōu)化算法蔡宇翔,傅偉峰(福州大學(xué)敷計學(xué)院,福建福州350108)摘要:Nimrod- G是在計算經(jīng)濟網(wǎng)格體系結構(GRACE) 下開(kāi)發(fā)的網(wǎng)格資源管理系統，它提供了一套基于期限和預算的調度策略DBC (Deadline and Budget Constained,以?xún)?yōu)化任務(wù)調度過(guò)程中的時(shí)間和費用問(wèn)題。其中,時(shí)間最優(yōu)化算法是DBC策略中最主要的算法之一,該算法的主要目標是對任務(wù)的處理時(shí)間進(jìn)行優(yōu)化。但該算法在預算分配和預算使用方西存在著(zhù)不足,以致在任務(wù)預算較少時(shí)出現任務(wù)完成率低的現象。該文針對該算法的不足提出了一個(gè)改進(jìn)方法,有效地改進(jìn)了傳統的時(shí)間最優(yōu)化算法。關(guān)鍵詞:網(wǎng)格資源管理系統;期限;預算;任務(wù)完成率中圖分類(lèi)號:TP311文獻標識碼:A文章編號:1009- 3044(2010)19- -5173 -02時(shí)間最優(yōu)化算法是網(wǎng)格DBC調度策略中最主要的算法之-,它以任務(wù)完成時(shí)間為資源擇優(yōu)的標準,其主要思想是:根據任務(wù)的長(cháng)度,為用戶(hù)提交的任務(wù)集合中的每個(gè)子任務(wù)制定-個(gè)單獨的子預算;并在這個(gè)預算范圍內,把任務(wù)分配到能最早完成該任務(wù)的網(wǎng)格資源上。在預算比較寬松的情況下,時(shí)間最優(yōu)化算法能極大地縮短任務(wù)總的完成時(shí)間;但在預算比較緊縮的情況下,時(shí)間最優(yōu)化算法為每個(gè)子任務(wù)設定的單獨預算則成為任務(wù)調度中的一個(gè)瓶頸因素,極大地影響了任務(wù)的完成率。1傳統時(shí)間最優(yōu)化算法的不足在預算分配上,傳統時(shí)間最優(yōu)化算法缺乏對總預算進(jìn)行集中,動(dòng)態(tài)分配的機制。在時(shí)間最優(yōu)化算法中,未分配任務(wù)列表里的每一個(gè)任務(wù)都對應一個(gè)固定的子預算,此預算是根據該任務(wù)的長(cháng)度和列表中任務(wù)的總長(cháng)度,通過(guò)公式(1)計算得到的:h= Length(ti)(1)其中,Length()為任務(wù)q的長(cháng)度;L為未分配任務(wù)列表中任務(wù)的總長(cháng)度;B為剩余總預算;b為通過(guò)公式(1)計算得到的任務(wù)4的子預算。任務(wù)的子預算是進(jìn)行任務(wù)調度時(shí)網(wǎng)格資源的準人標準。在對某個(gè)子任務(wù)進(jìn)行資源分配時(shí)，首先要確定該子任務(wù)的可用資源列表。在所有的網(wǎng)格資源中.只有那些費用不超過(guò)任務(wù)的子預算的資源才能加入到該任務(wù)的可用資源列表中去。另外,只有當可用資源列表中存在能在期限內完成任務(wù)的資源時(shí)任務(wù)才能被成功調度。實(shí)際上,時(shí)間最優(yōu)化算法這種將總預算按子任務(wù)的長(cháng)度,分割成固定的子預算的做法是不合理的。因為在用戶(hù)提供的總預算較小時(shí),時(shí)間最優(yōu)化算法不能夠將有限的預算進(jìn)行集中,動(dòng)態(tài)地分配,從而使盡可能多的任務(wù)得到執行。同時(shí),對總預算進(jìn)行分割的做法會(huì )使所有任務(wù)的子預算都呈現一種緊縮狀態(tài),這通常會(huì )使得長(cháng)度較大的任務(wù)因找不到能在期限內完成該任務(wù)的資源而無(wú)法被調度。在預算使用上,時(shí)間最優(yōu)化算法缺乏對調度失敗的任務(wù)所占用的預算進(jìn)行回收利用的機制。另外.在具體的任務(wù)調度過(guò)程中，時(shí)間最優(yōu)化算法采用遍歷未分配任務(wù)列表的方法,逐個(gè)地對列表中的任務(wù)進(jìn)行調度。在這個(gè)過(guò)程中,如果-一個(gè)任務(wù)被成功調度,它將被移出未分配作業(yè)列表,并在以后的調度過(guò)程中不再占用預算份額。但是,如果一個(gè)任務(wù)沒(méi)能被成功調度,那么它將始終留在未分配作業(yè)列表中,并持續占用-個(gè)相應的預算份額.直到本輪調度結束。因此,如果一個(gè)任務(wù)沒(méi)能被成功調度,那么剩余的任務(wù)也很可能繼續因為預算不足而不能成功調度。2改進(jìn)后的時(shí)間最優(yōu)化算法2.1改進(jìn)方法鑒于上述時(shí)間最優(yōu)化算法在預算分配和使用上存在的不足,本文提出以下兩點(diǎn)改進(jìn)方法:方法1:通過(guò)計算和推斷的方法,預測任務(wù)在各網(wǎng)格資源上的執行費用和完成時(shí)間:如果某項任務(wù)在其初始子預算下無(wú)法找到可用的資源,則以初始子預算的3倍為限,逐步提高該項任務(wù)的預算,看是否能找到可用資源。在提高預算的過(guò)程中,采用逐步提高的辦法,只要在某-預算下找到了可用資源就不再繼續提高該任務(wù)的預算量。這樣做既可以幫助原先預算不足的任務(wù)找到可用資源,又可以盡量控制該任務(wù)的預算使用量。方法2:如果將某--項任務(wù)的預算量提升到其初始子預算的3倍后,依然找不到可用資源,則將該任務(wù)暫時(shí)地移出未分配作業(yè)列表,以釋放其占有的預算份額,緩解剩余任務(wù)的預算緊縮狀態(tài),提高任務(wù)調度的成功率。在此,預算增加之所以要以初始預算的3倍為限的原因是:也許通過(guò)繼續不斷增加預算最終能為任務(wù)找到可用資源,但為調度該任務(wù)付出的預算代價(jià)是巨大的;以其使用巨額的預算來(lái)保證一個(gè)任務(wù)的運行.還不如回收該任務(wù)占有的預算份額以增加后續任務(wù)的可用預算量,進(jìn)而提高整體任務(wù)的完成率。2.2改進(jìn)后的時(shí)間最優(yōu)化算法根據上節中提出的改進(jìn)方法,我們對時(shí)間最優(yōu)化算法進(jìn)行了優(yōu)化?，F*中國煤化工程介紹如下:YHCNMHG收稿日期:2010-04-27網(wǎng)絡(luò )遲訊及安全”5173Computer KnowWedge and Technoloy電腦知識與技術(shù)第6卷第19期(2010年7月)算法描述:1)資源發(fā)現:通過(guò)網(wǎng)格信息服務(wù)器,檢索出本次調度中能被使用的資源。2)資源交易:根據每秒的CPU費用和單位費用所能處理的任務(wù)量.得到任務(wù)在不同資源上的調度費用。3)如果用戶(hù)提供的是D.B參數,則根據用戶(hù)的需求和資源的價(jià)格計算出絕對期限和偵算。4)任務(wù)調度:重復以下步蠊,直到所有任務(wù)都分配,或者期限或預算超出限制: .①通過(guò)計算和推斷的方法,預測資源消耗率以及資源可用份額。②如果某個(gè)資源的可用性方面發(fā)生了變化,則將已經(jīng)分配給該資源,但還沒(méi)提交到資源上執行的任務(wù)適當移出一部分到未分配列表中。③對未分配列表中的任務(wù).重復如下步驟:a從未分配作業(yè)列表中取出一個(gè)任務(wù)(矩作業(yè)優(yōu)先)。b.確立任務(wù)的叮用資源列表:如果在任務(wù)的初始子預算下可用資源列表為空.則以初始子預算的3倍為限,逐步增加任務(wù)的預算量,直到找到可用資源為止。e.如果任務(wù)的叮用資源列表最終為空.則暫時(shí)將任務(wù)從未分配任務(wù)列表中移出.并轉至步驟a;否則轉至步驟d。d.對可用資源列表中的每個(gè)資源,根據先前任務(wù)的完成情況以及資源的川用性狀況,估算出任務(wù)在該資源上的完成時(shí)間。e.將資源列表按照任務(wù)完成時(shí)間的升序排列。f如果任務(wù)完成時(shí)間不超過(guò)期隈.則把任務(wù)分配給排序后的資源列表中的第一個(gè)資源,并將任務(wù)從未分配任務(wù)列表中移除。5)按照步驟4的分配方案，根據資源的處理能力,將作業(yè)異步地發(fā)送到資源上去執行。6)當作業(yè)處理完畢,資源將結果反饋給接收模塊,同時(shí)更新資源上的信息。3模擬實(shí)驗本文提出的對傳統時(shí)間最優(yōu)化算法的優(yōu)化方案,主要是在任務(wù)因子預算不足而無(wú)法找到可用資源時(shí).通過(guò)增加子預算并回收調度失敗的任務(wù)所占用的預算份額的方法,來(lái)保證低預算時(shí)任務(wù)的完成率。為了證明該優(yōu)化方案的優(yōu)化效果,本文取定了三個(gè)遞增的期限，并在這三個(gè)期限下觀(guān)察了預算對傳統的時(shí)間最優(yōu)化算法(以下簡(jiǎn)稱(chēng)為T(mén)0)和改進(jìn)后的時(shí)間最優(yōu)化算法(以下簡(jiǎn)稱(chēng)為oro)、莫南名 T廠(chǎng).路構，σs TPEMSISFE汽事黃略ICSPEMIs)的任務(wù)完成率的影響。Compg.Apha5164J3TI Sana,OSF13.1實(shí)驗數據設置在仿真實(shí)驗中，本文根據網(wǎng)格測試環(huán)境WWG (The Word-貯37。 Timec-sharedWide Crid)[51]的一個(gè)資源子集.模擬了不同體系和配置的計算資190.0源。其中模擬時(shí)需給出資源的如下屬性:資源名稱(chēng),服務(wù)器類(lèi)型、Q20.LImuxSiLOngn 3200操作系統.處理單元(PE)數目.每個(gè)處理單元的計算處理能力、每個(gè)處理單元每秒的價(jià)格。具體的資源設置表如圖1所示。SCI.Onp 300在網(wǎng)格任務(wù)方面，我們創(chuàng )建了100個(gè)網(wǎng)格任務(wù)，其長(cháng)度為SoL.Ongla 320010251000(MI)有10%浮動(dòng)輸人數據和數據結果文件大小為100KB,RIX帶有5%浮動(dòng)。另外,考慮到單用戶(hù)和多用戶(hù)對調度算法性能的評價(jià)結果是一-致的,所以本文只考慮單用戶(hù)的情況。sGL,Onga 3200Tume-shared3.2實(shí)驗結果對比RI0 SunLin.SolasTnm-hred123.66在既定的網(wǎng)格環(huán)境下,任務(wù)的完成情況主要是由用戶(hù)提供的困1資源配置圍Budget 和Deadline,以及選用的調度策略(算法)決定的。首先,從預算對兩個(gè)算法的任務(wù)完成率的影響方面進(jìn)行分析。隨著(zhù)預算的增加,TO和OTO算法的任務(wù)完成率都呈上升趨勢。但TO算法的任務(wù)完成率的增張呈現跳躍性狀態(tài),這是因為:T0算法為任務(wù)設置的靜態(tài)子預算是資源接人的巨大限制因素.如果只是少量地增加預算,那么由于子預算的限制.任務(wù)調度的可用資源列表可能依然保持不變,因此任務(wù)的完成率并沒(méi)有得到提商;但是如果預算增加到一定量,那么一些相對比較便宜的資源就可以加入到可用資源列表中.這時(shí)便會(huì )極大地提高其任務(wù)完成率。相對TO算法跳躍性的增幅,0T0算法下任務(wù)完成率的增幅則相對平穩,這是因為:0TO算法為任務(wù)設置了動(dòng)態(tài),可增加的子預算,子預算對資源接人的限制性會(huì )相對較小，因此即使小幅地增加預算也能--定最地提高任務(wù)完成率。接者,從期限對兩個(gè)算法的任務(wù)完成率的影響方鹵進(jìn)行分析。隨著(zhù)期限的增加,TO和0TO算法的任務(wù)完成率都呈上升趨勢.但T0算法增幅會(huì )比OTO算法的大些。這時(shí)因為:TO算法的靜態(tài)子預算極大地限制了任務(wù)調度的可用資源，這時(shí)只要適當地放寬期限,任務(wù)的叮用資源就會(huì )極大地增加.進(jìn)而提高任務(wù)完成率。而OTO算法因為采用了動(dòng)態(tài)子預算機制,所以任務(wù)調度時(shí)的可用資源受子預算的限制也相對較小,所以放寬期限對可用資源量地影響也較下,因此任務(wù)完成率的增幅也較小?？偟膩?lái)說(shuō),0T0算法因為采用了動(dòng)態(tài)子預算機制,從而能在預算不足時(shí)較集中地使用預算，進(jìn)而使得在預算限制內更多的任務(wù)得到成功調度,因此與T0算法相比,OTO算法在預算不足時(shí)極大地提高了中國煤化工4結論CNMH G本文首先分析了傳統時(shí)間最優(yōu)化算法TO的不足,并提出了相應的改進(jìn)刀法;按有,在以上化斷出巷硒上,我們設計了OTO算法,并介紹了該算法的思想.流程以及核心代碼;最后.我們在利用Gridsim搭建的仿真平臺上進(jìn)行了對比實(shí)驗,通過(guò)對比OTO算法和TO算法在不同期限和預算限制下的任務(wù)完成情況，充分證明了OTO算法的優(yōu)越性。(下轉第5193頁(yè))5174...網(wǎng)絡(luò )灑訊及安全.......本欄目責任編輯:馮蕾.第6卷第19期(2010年 7月)Computer Konowledge and Technalogy電有知識與技術(shù)從實(shí)驗結果可以看出，比較穩定的門(mén)限值在0.4到0.7之間，在這之間不同同查門(mén)限的情記內,平均損失比較固定。在門(mén)限為1的情況下,損失最低。加人成本分析后，系統誤判隨著(zhù)門(mén)限的不同而出現的情況如圖6所示，80圖6是針對doe攻擊的情況，從中可以看出誤判的比率隨著(zhù)門(mén)限的降低而降低.在0.65左布,進(jìn)入誤差為零的狀態(tài)。聲畚考文獻:川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.網(wǎng)絡(luò )安全事件響應[M].段海新,譯.北京:人民郵電出版社,002.(上接第5174頁(yè))參考文獻:[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]丁箐,陳國良,單九龍,等.一個(gè)基于證券市場(chǎng)的計算網(wǎng)格環(huán)境下的資源分配模型J.小型微型計算機系統203-.41);14-15.[4]夏靖波,劉穎.網(wǎng)格原理與開(kāi)發(fā)[|M].西安:西安電子科技大學(xué)出版社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]吳俊,張大方.一個(gè)擴展的以QoS為指向的網(wǎng)格任務(wù)調度算法J].計算機工程與科學(xué)20,2.(4);66-70.0[7]王大晨,王淑靜.成本/時(shí)間綜合優(yōu)化網(wǎng)絡(luò )資源調度策略及價(jià)格算法[J.北京理工大學(xué)學(xué)報204.24():617-621.[8]朱魯梅.基于計算經(jīng)濟的網(wǎng)格任務(wù)調度算法研究[D].長(cháng)沙:湖南大學(xué),2006.中國煤化工MYHCNMHG本欄男零年界疊幫.......網(wǎng)絡(luò )訊及安全“5193