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

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

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

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

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

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