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

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

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

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

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

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