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

1、計(jì)算機(jī)算法論文：網(wǎng)格計(jì)算啟發(fā)式任務(wù)調(diào)度算法的研究及在GridSim中的仿真【摘要】： 網(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ā)式方法為主。本文在詳細(xì)介紹網(wǎng)格計(jì)算中任務(wù)調(diào)度的概念、原理、目標(biāo)等相關(guān)問題的基礎(chǔ)上,集中對啟發(fā)式元

2、任務(wù)調(diào)度算法進(jìn)行研究,主要工作如下： 1.簡要介紹了網(wǎng)格計(jì)算與任務(wù)調(diào)度的研究背景和研究現(xiàn)狀,并對網(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)度跨度,但任務(wù)等待時(shí)間較長。因而當(dāng)用戶同時(shí)對調(diào)度跨度與任務(wù)等待時(shí)間存在需求時(shí),這兩個(gè)算法均不具備較強(qiáng)的可用性。 3.針對Sufferage算法在多個(gè)任務(wù)競爭同一資源時(shí),僅比較各任務(wù)的次小完成時(shí)間與最小完成時(shí)間差值的不充分性,本文設(shè)計(jì)并實(shí)現(xiàn)了MD-Sufferage算法。MD-

3、Sufferage算法的執(zhí)行流程為：首先對任務(wù)的所有完成時(shí)間按照升序排序,之后計(jì)算各完成時(shí)間與最小完成時(shí)間的差值；隨后在發(fā)生資源競爭時(shí),不單是比較各任務(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)性對調(diào)度性能的影響,首先計(jì)算所有任務(wù)的執(zhí)行時(shí)間波動(dòng)性；隨后以執(zhí)行時(shí)間波動(dòng)性均值為標(biāo)準(zhǔn)將調(diào)度集合劃分為高波動(dòng)性集合與低波動(dòng)性集合；最后,輪流調(diào)度高波動(dòng)性集合與低波動(dòng)性

4、集合,直至所有任務(wù)均被調(diào)度。在每一輪對這兩個(gè)子任務(wù)集合進(jìn)行調(diào)度時(shí),首先依據(jù)Min-Min算法的原理選取若干最小完成時(shí)間相對較小的任務(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-Sufferage算法獲得的調(diào)度跨度略優(yōu)于Sufferage算法；WTMB算法實(shí)現(xiàn)了調(diào)度跨度短與任務(wù)等待時(shí)間小的統(tǒng)一,因而綜合性能要優(yōu)于Min-Min、Sufferage、MD-Sufferage算法,并且具備更強(qiáng)

5、的靈活性?！娟P(guān)鍵詞】：網(wǎng)格計(jì)算 任務(wù)調(diào)度 啟發(fā)式 GridSim 【學(xué)位授予單位】：西北大學(xué)【學(xué)位級別】：碩士【學(xué)位授予年份】：2010【作者】：樊莎【索取全文】Q聯(lián)系Q：138113721 Q聯(lián)系Q:139938848【目錄】： · 摘要3-5· Abstract5-7· 目錄7-10· 第一章 緒論10-16· 1.1 研究背景10-11· 1.2 研究現(xiàn)狀11-14· 網(wǎng)格計(jì)算的研究現(xiàn)狀11-13· 網(wǎng)格任務(wù)調(diào)度的研究現(xiàn)狀13-14· 1.3 本文的主要工作14-15· 1.4 論文結(jié)構(gòu)1

6、5-16· 第二章 網(wǎng)格及任務(wù)調(diào)度概述16-30· 2.1 網(wǎng)格技術(shù)概述16-19· 網(wǎng)格的特點(diǎn)16· 網(wǎng)格體系結(jié)構(gòu)的發(fā)展16-19· 2.2 網(wǎng)格任務(wù)調(diào)度概述19-25· 網(wǎng)格任務(wù)調(diào)度的相關(guān)概念19-21· 網(wǎng)格任務(wù)調(diào)度的特點(diǎn)21-23· 網(wǎng)格任務(wù)調(diào)度模型23-24· 網(wǎng)格任務(wù)調(diào)度的目標(biāo)24-25· 2.3 啟發(fā)式任務(wù)調(diào)度算法概述25-28· 動(dòng)態(tài)啟發(fā)式任務(wù)調(diào)度算法25-27· 靜態(tài)啟發(fā)式任務(wù)調(diào)度算法27-28· 2.4 任務(wù)調(diào)度模擬工具的選擇28-29·

7、; 2.5 本章小結(jié)29-30· 第三章 經(jīng)典啟發(fā)式任務(wù)調(diào)度算法的研究30-46· 3.1 啟發(fā)式任務(wù)調(diào)度算法的研究意義30-31· 3.2 算法相關(guān)定義31-32· 3.3 Min-Min算法的分析32-36· Min-Min算法調(diào)度原理32-34· Min-Min算法存在的問題34-36· 3.4 Sufferage算法的分析36-41· Sufferage算法原理36-38· Sufferage算法存在的問題38-41· 3.5 Min-Min與Sufferage算法的實(shí)現(xiàn)41-45

8、83; 算法通用變量聲明41-43· Min-Min算法的實(shí)現(xiàn)43-44· Sufferage算法的實(shí)現(xiàn)44-45· 3.6 本章小結(jié)45-46· 第四章 改進(jìn)算法的設(shè)計(jì)與實(shí)現(xiàn)46-61· 4.1 任務(wù)調(diào)度系統(tǒng)模型的建立46-47· 4.2 MD-Sufferage算法的設(shè)計(jì)與實(shí)現(xiàn)47-52· MD-Sufferage算法的設(shè)計(jì)47-49· MD-Sufferage算法的實(shí)現(xiàn)49-52· 4.3 WTMB算法的設(shè)計(jì)與實(shí)現(xiàn)52-59· WTMB算法的設(shè)計(jì)52-56· WTMB算法的實(shí)現(xiàn)5

9、6-59· 4.4 本章小結(jié)59-61· 第五章 改進(jìn)算法在GridSim中的仿真61-70· 5.1 GridSim簡介61-63· Gridsim體系結(jié)構(gòu)61-62· GridSim仿真步驟62-63· 5.2 開發(fā)、運(yùn)行環(huán)境63· 5.3 算法性能評價(jià)指標(biāo)在GridSim中的求解63-64· 5.4 仿真環(huán)境的配置64-65· 5.5 MD-Sufferage算法性能測試65-66· 5.6 WTMB算法性能測試66-69· 取值分析66-68· 調(diào)度跨度與平均任務(wù)等待時(shí)間的測試68-69· 5.7 本章小結(jié)69-70· 總結(jié)與展望70-72· 全文工作總結(jié)70-71· 工