網(wǎng)格計算啟發(fā)式任務(wù)調(diào)度算法的研究及在GridSim中的仿真.pdf

1、網(wǎng)格計算是伴隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展而產(chǎn)生的一種新型分布式計算模式，以實現(xiàn)大規(guī)模分布式資源共享及協(xié)同問題求解為目標(biāo)。任務(wù)調(diào)度是網(wǎng)格計算的一項核心技術(shù)，高效的任務(wù)調(diào)度算法可以充分利用網(wǎng)格資源，從而提高應(yīng)用程序的性能。然而，網(wǎng)格資源的動態(tài)性、異構(gòu)性、自治性等特性，使得網(wǎng)格環(huán)境下的任務(wù)調(diào)度極其復(fù)雜，因此如何開發(fā)出有效的任務(wù)調(diào)度算法是網(wǎng)格計算面臨的一大挑戰(zhàn)。
　　 任務(wù)調(diào)度已被證明是一個NP難問題，因而現(xiàn)有的任務(wù)調(diào)度算法多以啟發(fā)式方法為

2、主。本文在詳細(xì)介紹網(wǎng)格計算中任務(wù)調(diào)度的概念、原理、目標(biāo)等相關(guān)問題的基礎(chǔ)上，集中對啟發(fā)式元任務(wù)調(diào)度算法進(jìn)行研究，主要工作如下：
　　 1.簡要介紹了網(wǎng)格計算與任務(wù)調(diào)度的研究背景和研究現(xiàn)狀，并對網(wǎng)格計算與任務(wù)調(diào)度的相關(guān)理論進(jìn)行詳細(xì)說明。
　　 2.深入研究了Min-Min與Sufferage算法的調(diào)度原理，并通過分析總結(jié)出，Min-Min算法能夠獲得較短的任務(wù)等待時間，但調(diào)度跨度不理想；Sufferage算法能獲得較理想的調(diào)

3、度跨度，但任務(wù)等待時間較長。因而當(dāng)用戶同時對調(diào)度跨度與任務(wù)等待時間存在需求時，這兩個算法均不具備較強(qiáng)的可用性。
　　 3.針對Sufferage算法在多個任務(wù)競爭同一資源時，僅比較各任務(wù)的次小完成時間與最小完成時間差值的不充分性，本文設(shè)計并實現(xiàn)了MD-Sufferage算法。MD-Sufferage算法的執(zhí)行流程為：首先對任務(wù)的所有完成時間按照升序排序，之后計算各完成時間與最小完成時間的差值；隨后在發(fā)生資源競爭時，不單是比較各任

4、務(wù)的次小完成時間與最小完成時間的差值，而是依次比較所有完成時間與最小完成時間的差值。
　　 4.為了在縮短調(diào)度跨度的同時保證較小的任務(wù)等待時間，本文設(shè)計并實現(xiàn)了WTMB(Waiting Time and Makespan Balance)算法。WTMB算法的執(zhí)行流程為：考慮到任務(wù)執(zhí)行時間波動性對調(diào)度性能的影響，首先計算所有任務(wù)的執(zhí)行時間波動性；隨后以執(zhí)行時間波動性均值為標(biāo)準(zhǔn)將調(diào)度集合劃分為高波動性集合與低波動性集合；最后，輪流調(diào)

5、度高波動性集合與低波動性集合，直至所有任務(wù)均被調(diào)度。在每一輪對這兩個子任務(wù)集合進(jìn)行調(diào)度時，首先依據(jù)Min-Min算法的原理選取若干最小完成時間相對較小的任務(wù)構(gòu)成候選任務(wù)集，之后采用MD-Sufferage算法對該候選任務(wù)集進(jìn)行調(diào)度。
　　 5.對GridSim網(wǎng)格模擬工具進(jìn)行了深入的研究，并采用GridSim對Min-Min、Sufferage、MD-Sufferage、WTMB算法進(jìn)行仿真。仿真結(jié)果表明：MD-Sufferag