基于關(guān)鍵路徑的網(wǎng)格任務(wù)調(diào)度算法研究.pdf

1、隨著網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)上充斥著更多可以利用的廉價(jià)資源。利用此類(lèi)資源的網(wǎng)格計(jì)算解決規(guī)模龐大、復(fù)雜問(wèn)題具有重要的意義。網(wǎng)格資源具有規(guī)模龐大、分布異構(gòu)和動(dòng)態(tài)性等特點(diǎn)。實(shí)現(xiàn)高效的網(wǎng)格計(jì)算需要解決許多復(fù)雜的問(wèn)題，任務(wù)調(diào)度問(wèn)題就是其中的一個(gè)關(guān)鍵問(wèn)題。 網(wǎng)格資源動(dòng)態(tài)性主要反應(yīng)在資源能力衰減、增強(qiáng)以及新資源的加入和舊資源的退出。以往的很多調(diào)度算法主要關(guān)注調(diào)度方案制定，直接將任務(wù)加入到資源節(jié)點(diǎn)的待執(zhí)行任務(wù)序列，忽略了方案制定時(shí)和方案執(zhí)行時(shí)

2、資源能力的變化。若在方案制定時(shí)的資源能力在方案執(zhí)行時(shí)衰減(退出)，使得高權(quán)限任務(wù)占有了低性能資源，造成任務(wù)執(zhí)行時(shí)間增加，有可能增加整個(gè)應(yīng)用的并行完成時(shí)間(Makespan)；若在方案制定時(shí)的資源能力在方案執(zhí)行時(shí)增強(qiáng)，任務(wù)執(zhí)行時(shí)間減小，有可能減小整個(gè)應(yīng)用的Makespan；當(dāng)新資源加入時(shí)，由于已經(jīng)為任務(wù)分配資源，所以不影響任務(wù)執(zhí)行時(shí)間和整個(gè)應(yīng)用的Makespan。 為了減小資源能力衰減引起應(yīng)用Makespan增加的程度，以及增加能

3、力出眾的新加入資源對(duì)作業(yè)Makespan的影響，本算法根據(jù)調(diào)度執(zhí)行開(kāi)始時(shí)間(BT)將任務(wù)調(diào)度分為調(diào)度方案制定(TSPF)和調(diào)度方案執(zhí)行(TSPE)兩個(gè)階段，定義了網(wǎng)格環(huán)境下的調(diào)度執(zhí)行最晚開(kāi)始時(shí)間、調(diào)度執(zhí)行開(kāi)始時(shí)間和任務(wù)優(yōu)先圖(DAG)中邊的權(quán)值，分析了任務(wù)圖凍結(jié)消減和執(zhí)行消減對(duì)任務(wù)圖結(jié)構(gòu)的影響以及方案制定和方案執(zhí)行時(shí)間的資源能力變化對(duì)調(diào)度準(zhǔn)確性的影響。 基于關(guān)鍵路徑的調(diào)度算法(CPA)認(rèn)為，盡量提前任務(wù)優(yōu)先圖關(guān)鍵路徑中每個(gè)任務(wù)的

4、完成時(shí)間，就能縮短整個(gè)作業(yè)的Makespan，即關(guān)鍵路徑上的任務(wù)具有更高的優(yōu)先權(quán)。但是，與基于最早開(kāi)始時(shí)間的調(diào)度算法(ETF)比較發(fā)現(xiàn)，最早開(kāi)始時(shí)間同樣影響著作業(yè)Makespan，且在一定條件下ETF算法優(yōu)于CPA算法。 當(dāng)前大多數(shù)調(diào)度算法主要通過(guò)預(yù)防搶奪解決資源搶奪，即在任何情況下都不允許資源搶奪。本算法在關(guān)鍵路徑算法的基礎(chǔ)上，根據(jù)關(guān)鍵路徑長(zhǎng)度(CP)定義了任務(wù)優(yōu)先權(quán)，并且考慮最早開(kāi)始時(shí)間對(duì)作業(yè)Makespan的影響，允許未分

5、配資源的任務(wù)搶奪已經(jīng)被任務(wù)占有的資源。在此基礎(chǔ)上定義了資源搶奪和調(diào)度最小圖，分析了資源搶奪有可能出現(xiàn)的幾種情況，以及對(duì)任務(wù)圖和調(diào)度結(jié)果的影響，并且針對(duì)一種資源搶奪情況，提出了兩個(gè)啟發(fā)式原則用以決定是否允許資源搶奪。 最后，提出了基于BT的允許資源搶奪的網(wǎng)格依賴(lài)任務(wù)調(diào)度算法(BTTS)。重點(diǎn)分析了網(wǎng)格模擬平臺(tái)GridSim，并在此平臺(tái)上實(shí)現(xiàn)ETF算法、CPA算法和BTTS算法，試驗(yàn)結(jié)果發(fā)現(xiàn)BTTS算法優(yōu)于其它兩種算法，且有效地降低