分布式系統(tǒng)中處理機的任務調(diào)度算法研究——智能算法在網(wǎng)格任務調(diào)度中的研究.pdf

1、網(wǎng)格作為典型的分布式應用系統(tǒng)，由大量分布共享的異構資源組成，這些資源協(xié)同提供了巨大的計算能力。由于網(wǎng)格計算中資源具有在廣域上分布、自主管理、本質(zhì)上異構、負載動態(tài)變化等特性，使得網(wǎng)格環(huán)境下的任務調(diào)度所面臨的問題比傳統(tǒng)分布式環(huán)境要復雜得多，是一個NP完全問題(除極少數(shù)特殊情況外)。調(diào)度技術一直為計算機學者們研究的焦點，是網(wǎng)格的核心技術，它可以描述為合理解決計算任務在地理分布的各種資源之間的動態(tài)調(diào)度。總的來說，一個好的任務調(diào)度算法其關鍵的技術

2、參數(shù)是在最短的時間內(nèi)實現(xiàn)最優(yōu)分配策略，從而提高系統(tǒng)資源的利用率以及保持系統(tǒng)較好的系統(tǒng)負載均衡。 本文通過對智能算法--蟻群與遺傳算法的深入研究，將它們引入到網(wǎng)格任務調(diào)度中，提出了基于改進型蟻群算法的網(wǎng)格任務調(diào)度技術與基于蟻群與遺傳混合算法的網(wǎng)格任務調(diào)度技術。 基于改進型蟻群算法的網(wǎng)格任務調(diào)度技術，主要針對現(xiàn)有網(wǎng)格任務調(diào)度算法負載均衡、資源利用率、跨度等方面的不足而提出。該算法的關鍵問題就是如何確定負載，使各個結點的負載基

3、本趨于均衡，以達到網(wǎng)格系統(tǒng)任務調(diào)度要求總的執(zhí)行時間最小以及系統(tǒng)的利用率最高。蟻群算法的正反饋特性容易導致搜索結果過早的陷入局部最優(yōu)，改進型蟻群算法針對這一現(xiàn)象做出一系列改進：增加信息素權值、增加揮發(fā)平衡因子、引入前輩們提出的轉(zhuǎn)移概率準則以及對信息素總量進行限制。 蟻群算法基于隨機搜索的特性，在算法的初期按啟發(fā)信息進行求解，收斂速度緩慢。通過對遺傳算法的研究，本文針對具有快速響應要求的網(wǎng)格任務調(diào)度提出了以仿真時間為優(yōu)先目標的蟻群與

4、遺傳混合算法，該調(diào)度算法將蟻群與遺傳算法混合應用于網(wǎng)格任務調(diào)度中，取兩種算法之所長，去其所短，優(yōu)勢互補，從而在時間效率上優(yōu)于蟻群算法。新算法在滿足調(diào)度的限定條件之前采用遺傳算法，充分利用遺傳算法的群體性、快速搜索等優(yōu)勢生成初始解(即產(chǎn)生有關問題的初始信息素分布)，隨后采用本文提出的基于獎勵因子的蟻群算法，在有一定初始信息素分布的情況下，最大限度地利用蟻群算法的正反饋性來快速求解任務的最優(yōu)解。 通過使用基于SimJava的網(wǎng)格資源