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

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

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

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

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