網(wǎng)格環(huán)境下任務調度機制的研究與仿真.pdf

1、網(wǎng)格技術將所有可用于共享的資源(例如，計算機、高性能設備、昂貴儀器、存儲設備、科學數(shù)據(jù)、軟件、數(shù)據(jù)庫等)通過網(wǎng)絡連接起來，并將它們轉化成一種隨處可得的、可靠的、標準的、經(jīng)濟的計算能力。用戶將任務提交給網(wǎng)格后，需要對任務進行合理的分配和調度，即將任務分配給網(wǎng)格資源去執(zhí)行。 由于網(wǎng)格中任務調度直接影響到整個系統(tǒng)的計算性能，因此調度成為網(wǎng)格計算中的一項關鍵技術。任務調度問題是一類NPC問題，經(jīng)典調度理論一般僅能獲得問題的近似最優(yōu)解。

2、 本文采用理論分析與仿真實驗相結合的方法，研究網(wǎng)格計算中具有依賴關系的多任務分配與調度的遺傳算法。遺傳算法是一種有導向性的隨機搜索算法，它以適應度函數(shù)為導向，模擬自然界生物進化和遺傳過程，搜索全局最優(yōu)解。 本文針對網(wǎng)格系統(tǒng)中任務調度問題提出一個適用的遺傳算法框架。算法中染色體的編碼采用二維0-1矩陣，即文中的“資源-任務”匹配矩陣。在此基礎上采用三類遺傳算子，即外部交叉算子、內部交叉算子和可變的變異算子。外部交叉算子和內部

3、交叉算子具有生成最優(yōu)解的能力；變異算子有效的保存了種群的多樣性。為了保證遺傳算法的全局搜索能力，采用任務最大深度值與最小深度值來共同確定任務的深度值；為了防止早熟，算法自適應的加大變異概率。 遺傳算法中主要控制參數(shù)的取值通過仿真實驗確定，而任務DAG圖、任務數(shù)、任務工作量、資源數(shù)、資源計算能力、資源間通信延遲均可在仿真系統(tǒng)初始化時手動或隨機生成。經(jīng)仿真試驗的結果數(shù)據(jù)比較，本文算法具有較好的解全局搜索能力，以及較快的收斂速度，能夠