常民, 仇磊(河海大學(xué) 計算機(jī)與信息學(xué)院,江蘇 南京 211100)

一種改進(jìn)的網(wǎng)格任務(wù)調(diào)度算法

常民, 仇磊
(河海大學(xué) 計算機(jī)與信息學(xué)院,江蘇 南京 211100)

任務(wù)調(diào)度算法是網(wǎng)格計算中研究的熱點問題之一。其中，Min-Min調(diào)度算法是一個簡單、快速、有效經(jīng)典的任務(wù)調(diào)度算法，但該算法存在著負(fù)載不均衡的缺陷。針對此缺陷，在Min-Min算法的基礎(chǔ)上提出了一種新的任務(wù)調(diào)度算法，該算法定義了一個向量RT={rt1,rt2,…,rti,…rtn}，rti代表第i個資源已經(jīng)分配任務(wù)運行時間之和，并根據(jù)未被調(diào)度的任務(wù)數(shù)所占的比例，把任務(wù)分成兩部分調(diào)度，不同的部分使用不同的規(guī)則進(jìn)行調(diào)度。最后對改進(jìn)的算法進(jìn)行了有效性和合理性驗證。

網(wǎng)格計算； 任務(wù)調(diào)度； Min-Min算法； 負(fù)載均衡； 分段

0 前言

網(wǎng)格計算即分布式計算，是計算機(jī)領(lǐng)域中研究的熱點問題之一，它研究如何把那些需要巨大的計算能力才能解決的問題分成許多小的部分，然后把這些小的部分調(diào)度給許多計算機(jī)進(jìn)行處理，最后把各個計算機(jī)處理的結(jié)果整合起來得到最終結(jié)果[1-2]。在網(wǎng)格計算中任務(wù)調(diào)度是研究的重點，也是一個NP完全問題。網(wǎng)格任務(wù)調(diào)度的目的就是合理調(diào)度任務(wù)，以使完成的總時間盡可能的最小化，同時提高資源的利用率。最經(jīng)典的任務(wù)調(diào)度算法Min-Min算法具有簡單、快速、有效的特點，但該算法存在著負(fù)載不均衡的缺陷。針對Min-Min的這種缺陷，也有很多學(xué)者提出了基于Min-Min算法的各種改進(jìn)算法[1-5]。

本文在分析Min-Min算法的基礎(chǔ)上提出了一種新的任務(wù)調(diào)度算法，根據(jù)未被調(diào)度的任務(wù)數(shù)所占的比例，把任務(wù)分成兩部分調(diào)度，不同的部分使用不同的規(guī)則進(jìn)行調(diào)度。最后對改進(jìn)的算法進(jìn)行了有效性和合理性的驗證。

2 Min-Min算法

Min-Min算法是一個比較傳統(tǒng)、經(jīng)典的任務(wù)調(diào)度算法，具有簡單、快速、有效的特點，算法的思想是首先映射小的任務(wù)，并且映射到執(zhí)行快的機(jī)器上。假設(shè)有m個需要執(zhí)行的任務(wù)T={t1,t2…,ti,…tm}，n個可用的資源節(jié)點R={r1,r2,…,rj,…rn}。該算法的形式化描述如下：

(2)判斷任務(wù)集T是否為空，不為空則執(zhí)行(3)，否則跳到(8)。

(3)對任務(wù)集中的所有任務(wù)，求出它們映射到所有可用資源上的最早完成時間存儲到向量MCT(Minimum Completion Time)中。

(4)根據(jù)向量MCT找出最早完成時間最小的那個任務(wù)ti和所對應(yīng)的資源rj。

(5)將任務(wù)ti調(diào)度到對應(yīng)的資源rj上，并將該任務(wù)從任務(wù)集合T中刪除。

(6)更新其它任務(wù)在資源rj上的最早完成時間，即加上上次被分配任務(wù)的資源的就緒時間。

(7)轉(zhuǎn)到(2).

(8)退出任務(wù)調(diào)度。

Min-Min算法總是優(yōu)先調(diào)度預(yù)期完成時間最短的任務(wù)，并且總是將任務(wù)調(diào)度到完成該任務(wù)最快的資源上，已達(dá)到最終完成時間最短，但當(dāng)任務(wù)集中存在一些長任務(wù)時，那么這些任務(wù)就不會及時得到執(zhí)行，很容易導(dǎo)致系統(tǒng)的負(fù)載不均衡。例如，以文獻(xiàn)[1]的數(shù)據(jù)為例，如表1所示：

表1 任務(wù)在各個資源上的預(yù)計完成時間

表1給出了5個任務(wù)，3個資源以及每個任務(wù)ti在各個可用資源rj上的預(yù)計完成時間形成的矩陣ECT，其中X表示該任務(wù)在該資源上無法運行。由Min-Min調(diào)度算法可以得出調(diào)度序列為：t3調(diào)度到r1上，t2調(diào)度到r1上，t4調(diào)度到r1上，t5調(diào)度到r2上，t1調(diào)度到r1上?？梢娰Y源r3一直處于空閑狀態(tài)，而大部分任務(wù)在資源r1上運行，導(dǎo)致了負(fù)載的不均衡，而且運行時間較長。

3 改進(jìn)的任務(wù)調(diào)度算法

針對Min-Min算法在網(wǎng)格任務(wù)調(diào)度的缺點，文中在Min-Min的基礎(chǔ)上提出了一種新的任務(wù)調(diào)度算法。該算法根據(jù)沒有分配到資源的任務(wù)數(shù)，即剩余任務(wù)數(shù)所占的比例，把整個任務(wù)的調(diào)度過程分成兩部分調(diào)度，不同的部分使用不同的規(guī)則進(jìn)行調(diào)度。

3.1 與算法有關(guān)的參數(shù)定義

假設(shè)網(wǎng)格環(huán)境中有m個獨立的任務(wù)，T={t1,t2…,ti,…tm}，其中ti代表第i個任務(wù)；n個參與調(diào)度的可用資源，R={r1,r2,…,rj,…rn}，其中rj代表第j個可用資源。

定義2：設(shè)向量RT={rt1,rt2,…,rti,…rtn}，初始值都為0，其中rti代表第i個資源已經(jīng)分配的任務(wù)在第i個資源上執(zhí)行時間之和。

定義3：設(shè)向量RCL={rcl1,rcl2,…,rcli,…,rcln}，初始值都為0，其中rcli代表第i個資源可以運行的任務(wù)數(shù)。該向量中的值由ECT矩陣算的，即計算資源所在的列不為X的數(shù)。

定義4：設(shè)向量RCT=={rct1,rct2,…,rctj,…,rctm}，初始值都為0，其中rctj代表能夠運行第j個任務(wù)的資源數(shù)。

定義5：設(shè)總?cè)蝿?wù)數(shù)為m，沒有分配到資源的任務(wù)數(shù)為k，則沒有分配到資源的任務(wù)所占的比率為∝=m/k。

3.2 改進(jìn)算法的描述

設(shè)在網(wǎng)格環(huán)境中，有m個獨立的任務(wù)，n個可用的資源，改進(jìn)算法的描述如下：

(1)初始化向量RT，RCL值都為0；

(2)for in任務(wù)集T；

(3)for in 資源集R；

(4)計算ECT矩陣；

(5)end for；

(6)end for；

(7)遍歷ECT矩陣，計算向量RCL和RCT；

(8)遍歷向量RCT，選擇值為1的對應(yīng)的任務(wù)，分配給相應(yīng)的資源，并把該資源運行任務(wù)的完成時間加到相應(yīng)的rti上，同時把該任務(wù)從任務(wù)集中刪除并更新ECT矩陣；

(9)選取ECT矩陣中第一個沒有分配過的任務(wù)，取完成該任務(wù)用時最小的資源運行該任務(wù),同時將時間加到對應(yīng)資源的rti上，同時把該任務(wù)從任務(wù)集中刪除并更新ECT矩陣；

(10)while gt;=0.5

(11)if 還有資源沒有分配過任務(wù)

(12)if 該任務(wù)在不同的資源上運行時間相同

(13)選擇rcli最小的對應(yīng)資源運行該任務(wù)，同時把該任務(wù)從任務(wù)集中刪除并更新ECT矩陣；

(14)end if

(15)else if rcli相同

(16)選擇rti值最小的運行該任務(wù)，同時把該任務(wù)從任務(wù)集中刪除并更新ECT矩陣；

(17)end else if

(18)end if

(19)else

(20)選擇rti值最小的運行該任務(wù)，同時把該任務(wù)從任務(wù)集中刪除并更新ECT矩陣；

(21)end else

(22)end while

(23)while lt;0.5

(24)選擇rti值最小的運行該任務(wù)，同時把該任務(wù)從任務(wù)集中刪除并更新ECT矩陣；

(25)end while

4 實驗驗證

以表1為例，根據(jù)改進(jìn)的算法可以得出：RCL={4,5,3}，RCT=={2,3,3,3,1}，調(diào)度的序列為：t5調(diào)度到r2上，t1調(diào)度到r1上，t2調(diào)度到r2上，t3調(diào)度到r3上，t4調(diào)度到r1上。與Min-Min算法的結(jié)果比較如圖1所示。

從圖1結(jié)果可知，本文改進(jìn)算法完成任務(wù)的時間效率比Min-Min算法得到了有效提高，而且任務(wù)的在資源上的分配即負(fù)載均衡也得到了有效的改善。

5 結(jié)論

文中在對Min-Min算法的研究之后，在Min-Min算法的基礎(chǔ)上提出了一種新的任務(wù)調(diào)度算法，并根據(jù)未被調(diào)度的任務(wù)數(shù)所占的比例，把任務(wù)分成兩部分調(diào)度，不同的部分使用不同的規(guī)則進(jìn)行調(diào)度。最后實驗表明改進(jìn)后的算法的有效性和合理性。

(a)

(b)圖1 改進(jìn)后的算法和Min-Min算法任務(wù)調(diào)度完成時間比較參考文獻(xiàn)

[1] 趙英, 李棟. 改進(jìn)的Min-Min網(wǎng)格任務(wù)調(diào)度算法[J]. 電子設(shè)計工程, 2012, 20(12):55-57.

[2] 羅宇平. 基于Min-Min改進(jìn)后的網(wǎng)格調(diào)度算法[J]. 微電子學(xué)與計算機(jī), 2009, 26(3).

[3] Fang Y, Wang F, Ge J. A task scheduling algorithm based on load balancing in cloud computing [M]//Web Information Systems and Mining. Springer Berlin Heidelberg, 2010: 271-277.

[4] Lee Y H, Leu S, Chang R S. Improving job scheduling algorithms in a grid environment[J]. Future generation computer systems, 2011, 27(8): 991-998.

[5] Wu M Y, Shu W, Zhang H. Segmented min-min: a static mapping algorithm for meta-tasks on heterogeneous computing systems[C]// Heterogeneous Computing Workshop, 2000. (HCW 2000) Proceedings. 9th. IEEE, 2000:375-385.

AnImprovedSchedulingAlgorithminGridComputing

Chang Min, Chou Lei
(School of Computer and Information, Hohai University Jiangsu, Nanjing 211100，China)

Task scheduling algorithm is one of the hottest issues in grid computing. Min-Min scheduling algorithm is a simple, fast and efficient classical task scheduling algorithm, but the algorithm has the defect of load imbalance. Based on the Min-Min algorithm, this paper proposes a new task scheduling algorithm. It defines a vector RT= {rt1, rt2… rti… rtn}, and rti represents the running time sum of the first i resource that have been allocated to tasks. And according to the proportion of the number of non-scheduled tasks, a task is divided into two parts to schedule, different parts use different rules for scheduling. Finally, the validity and rationality of the improved algorithm are verified.

Grid computing; task scheduling; Min-Min algorithm; load balancing; segmentation

常 民(1989-),男,碩士研究生,研究方向：數(shù)據(jù)挖掘.仇 磊(1992-),男, 碩士研究生,研究方向：數(shù)據(jù)挖掘.

1007-757X(2017)11-0030-02

TP301.6

A

2017.08.08)