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

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

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

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

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

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