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

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

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

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

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

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