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

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

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

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

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

0 前言

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

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

2 Min-Min算法

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

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

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

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

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

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

(7)轉到(2).

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

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

表1 任務在各個資源上的預計完成時間

表1給出了5個任務，3個資源以及每個任務ti在各個可用資源rj上的預計完成時間形成的矩陣ECT，其中X表示該任務在該資源上無法運行。由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上。可見資源r3一直處于空閑狀態(tài)，而大部分任務在資源r1上運行，導致了負載的不均衡，而且運行時間較長。

3 改進的任務調(diào)度算法

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

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

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

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

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

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

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

3.2 改進算法的描述

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

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

(2)for in任務集T；

(3)for in 資源集R；

(4)計算ECT矩陣；

(5)end for；

(6)end for；

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

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

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

(10)while gt;=0.5

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

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

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

(14)end if

(15)else if rcli相同

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

(17)end else if

(18)end if

(19)else

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

(21)end else

(22)end while

(23)while lt;0.5

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

(25)end while

4 實驗驗證

以表1為例，根據(jù)改進的算法可以得出：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算法的結果比較如圖1所示。

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

5 結論

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

(a)

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

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

[2] 羅宇平. 基于Min-Min改進后的網(wǎng)格調(diào)度算法[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)