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