一種改進的網格任務調度算法

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

一種改進的網格任務調度算法

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

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

網格計算； 任務調度； Min-Min算法； 負載均衡； 分段

0 前言

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

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

2 Min-Min算法

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

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

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

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

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

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

(7)轉到(2).

(8)退出任務調度。

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

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

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

3 改進的任務調度算法

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

3.1 與算法有關的參數定義

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

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

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

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

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

3.2 改進算法的描述

設在網格環境中，有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為例，根據改進的算法可以得出：RCL={4,5,3}，RCT=={2,3,3,3,1}，調度的序列為：t5調度到r2上，t1調度到r1上，t2調度到r2上，t3調度到r3上，t4調度到r1上。與Min-Min算法的結果比較如圖1所示。

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

5 結論

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

(a)

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

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

[2] 羅宇平. 基于Min-Min改進后的網格調度算法[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-),男,碩士研究生,研究方向：數據挖掘.仇 磊(1992-),男, 碩士研究生,研究方向：數據挖掘.

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

TP301.6

A

2017.08.08)