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

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

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

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

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

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

0 前言

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

2 Min-Min算法

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

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

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

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

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

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

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

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

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

表1 任務(wù)在各個(gè)資源上的預(yù)計(jì)完成時(shí)間

表1給出了5個(gè)任務(wù)，3個(gè)資源以及每個(gè)任務(wù)ti在各個(gè)可用資源rj上的預(yù)計(jì)完成時(shí)間形成的矩陣ECT，其中X表示該任務(wù)在該資源上無法運(yùn)行。由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上運(yùn)行，導(dǎo)致了負(fù)載的不均衡，而且運(yùn)行時(shí)間較長(zhǎng)。

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

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

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

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

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

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

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

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

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

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

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

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

(3)for in 資源集R；

(4)計(jì)算ECT矩陣；

(5)end for；

(6)end for；

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

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

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

(10)while gt;=0.5

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

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

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

(14)end if

(15)else if rcli相同

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

(17)end else if

(18)end if

(19)else

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

(21)end else

(22)end while

(23)while lt;0.5

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

(25)end while

4 實(shí)驗(yàn)驗(yàn)證

以表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ù)的時(shí)間效率比Min-Min算法得到了有效提高，而且任務(wù)的在資源上的分配即負(fù)載均衡也得到了有效的改善。

5 結(jié)論

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

(a)

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

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

[2] 羅宇平. 基于Min-Min改進(jìn)后的網(wǎng)格調(diào)度算法[J]. 微電子學(xué)與計(jì)算機(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)