基于QoS的改進(jìn)Min–Min調(diào)度算法

林志杰, 張友斌, 顧靜

?

基于QoS的改進(jìn)Min–Min調(diào)度算法

林志杰1, 張友斌1, 顧靜2

(1. 湖南幼兒師范高等專(zhuān)科學(xué)校教務(wù)處, 湖南常德, 415000; 2. 中南大學(xué)軟件學(xué)院, 湖南長(zhǎng)沙, 410075)

針對(duì)經(jīng)典Min–Min調(diào)度算法存在負(fù)載不均, 資源利用率低, 處理時(shí)間長(zhǎng)等問(wèn)題, 提出了P–Min算法。該算法根據(jù)任務(wù)的優(yōu)先級(jí)并結(jié)合貪心算法來(lái)實(shí)現(xiàn)調(diào)度。仿真結(jié)果表明: P–Min算法在負(fù)載均衡的資源利用率方面較Min–Min算法提高了17%, 任務(wù)總體執(zhí)行時(shí)間調(diào)高了8.03%。

云計(jì)算; QoS; 貪心策略; 負(fù)載均衡; Min–Min; P–Min

云計(jì)算[1]由網(wǎng)格計(jì)算[2]、分布式計(jì)算等技術(shù)發(fā)展而來(lái), 它提供一種“按需服務(wù)”的模式, 近年來(lái), 該技術(shù)受到大量國(guó)內(nèi)外學(xué)者的重視[3]。在云計(jì)算中, 任務(wù)調(diào)度是指通過(guò)一定的算法合理地安排各個(gè)任務(wù)的執(zhí)行, 使其處理時(shí)間短且資源利用率高[4]。廣泛應(yīng)用于云計(jì)算中的任務(wù)調(diào)度算法有Min–Min算法[5]、Min-Max[6]算法及模擬退火算法等, 其中Min–Min算法是一種最為簡(jiǎn)單快捷的算法, 但是它忽略了任務(wù)對(duì)QoS[4–5]的要求。

本文提出一種基于QoS的改進(jìn)Min–Min調(diào)度算法, 并設(shè)計(jì)仿真實(shí)驗(yàn)驗(yàn)證算法的有效性。

1 P–Min 調(diào)度算法分析

1.1 P–Min思想

Min–Min調(diào)度算法是基于任務(wù)運(yùn)行時(shí)間進(jìn)行調(diào)度的, 它盡可能地將小任務(wù)分配到執(zhí)行速度快的資源上去執(zhí)行, 從而使得任務(wù)總體完成時(shí)間最小[7]。Min–Min算法首先計(jì)算每個(gè)任務(wù)在個(gè)資源下的最小完成時(shí)間。然后將任務(wù)按照最小完成時(shí)間升序排序, 依次將每個(gè)任務(wù)分配到其最小完成時(shí)間所對(duì)應(yīng)的資源上。Min–Min算法最大的缺點(diǎn)在于其負(fù)載不均[8–9]。針對(duì)Min–Min算法存在的不足, 本文提出一種基于QoS的改進(jìn)Min–Min調(diào)度算法P–Min算法。其基本思想是根據(jù)任務(wù)的優(yōu)先級(jí)從高到低分配相應(yīng)的資源, 如果任務(wù)具有相同的優(yōu)先級(jí), 則處理時(shí)間越短的越先執(zhí)行。如果存在多種分配方法, 則將任務(wù)分配給運(yùn)行任務(wù)數(shù)最小的資源。

1.2 P–Min算法

幾個(gè)變量定義: RT(j)表示資源Rj等待時(shí)間; CT(i, j)表示任務(wù)Ti在資源Rj上的預(yù)測(cè)完成時(shí)間, 且滿(mǎn)足CT(i, j) = ETC(i, j) + RT(j); MCT(i)表示任務(wù)Ti的最小完成時(shí)間; host_MCT(i)表示任務(wù)Ti分配給資源host_MCT(i)。

P–Min算法描述如下:

For 任務(wù)集T中的每個(gè)任務(wù)Ti

For j = 1, 2, 3…m

初始化RT(j) = 0

計(jì)算任務(wù)Ti在各主機(jī)上的預(yù)測(cè)完成時(shí)間CT(i, j) = ETC(i, j) + RT(j)

End for

End for

While T 不為空 do

For 任務(wù)集合T中的每個(gè)任務(wù)Ti

計(jì)算其最小完成時(shí)間MCT(i)及相應(yīng)的主機(jī)編號(hào)host_MCT(i)

End for

按照優(yōu)先級(jí)從高到低的順序找出最小完成時(shí)間的任務(wù)Ti

將任務(wù)Ti分配給編號(hào)為host_MCT(i)的主機(jī)

從任務(wù)中刪除Ti

更新相應(yīng)主機(jī)的就緒時(shí)間RT(host_MCT(p)) = MCT(i) + MCT(p)

更新預(yù)測(cè)完成時(shí)間矩陣CT

End while

2 仿真條件與任務(wù)

實(shí)驗(yàn)環(huán)境在個(gè)人PC機(jī)上進(jìn)行, 軟硬件配置為: CPU, Broadwell i7–5500U 2.4 GHz; 內(nèi)存4 GB; 硬盤(pán)500 GB; 操作系統(tǒng), Windows 7, 32位; 編程及實(shí)現(xiàn), MyEclipse2014; 仿真平臺(tái), CloudSim[10]。

在CloudSim中模擬P–Min算法及Min–Min算法任務(wù)的調(diào)度情況, 主要驗(yàn)證任務(wù)總完成時(shí)間、任務(wù)總執(zhí)行時(shí)間、系統(tǒng)資源利用率及任務(wù)響應(yīng)時(shí)間4個(gè)指標(biāo)。任務(wù)總完成時(shí)間為所有任務(wù)完成時(shí)間總和; 任務(wù)總執(zhí)行時(shí)間為從第一個(gè)任務(wù)開(kāi)始執(zhí)行到最后一個(gè)任務(wù)完成所花的時(shí)間; 系統(tǒng)資源利用率表示系統(tǒng)資源使用程度; 任務(wù)響應(yīng)時(shí)間為任務(wù)進(jìn)入系統(tǒng)到該任務(wù)執(zhí)行完成所花時(shí)間, 定義為等待時(shí)間與執(zhí)行時(shí)間之和。

3 結(jié)果與分析

實(shí)驗(yàn)中有50個(gè)資源, 每個(gè)資源的處理能力隨機(jī)產(chǎn)生, 范圍為[50, 350]。隨機(jī)產(chǎn)生300個(gè)任務(wù), 任務(wù)執(zhí)行時(shí)間范圍為[500, 1 000]。隨機(jī)為每個(gè)任務(wù)分配優(yōu)先級(jí), 優(yōu)先級(jí)取值為{1, 2, 3, 4, 5}, 優(yōu)先級(jí)越高數(shù)值越大。仿真結(jié)果見(jiàn)表1。

表1 仿真結(jié)果

實(shí)驗(yàn)結(jié)果表明, P–Min算法與Min–Min算法相比, 在任務(wù)總體執(zhí)行時(shí)間上調(diào)高了8.03%, 在系統(tǒng)資源利用率上提高了17%, 其原因在于Min-Min算法總是將小任務(wù)放到最快的資源上去執(zhí)行, 使得處理速度較慢的資源空閑, 處理速度較快的資源CPU利用率過(guò)高, 從而增加了任務(wù)的總執(zhí)行時(shí)間, 降低了系統(tǒng)的資源利用率。P–Min算法通過(guò)給任務(wù)設(shè)定不同的優(yōu)先級(jí)使得不管是大任務(wù)還是小任務(wù)都在系統(tǒng)資源上有效執(zhí)行, 從而降低了任務(wù)的總執(zhí)行時(shí)間和提高了系統(tǒng)的平均資源利用率。

P–Min算法與Min–Min算法相比, 在平均任務(wù)響應(yīng)時(shí)間方面提高了10%, 其原因在于Min–Min算法總是將小任務(wù)放到最快的資源上去執(zhí)行, 使得大任務(wù)的等待時(shí)間過(guò)長(zhǎng)從而增加了系統(tǒng)的平均任務(wù)響應(yīng)時(shí)間。P–Min算法通過(guò)給任務(wù)分配不同的優(yōu)先級(jí)使得大小任務(wù)都得到有效地執(zhí)行, 從而降低了系統(tǒng)的平均任務(wù)響應(yīng)時(shí)間。

與P–Min算法相比, Min–Min算法在任務(wù)總完成時(shí)間上性能比較優(yōu)秀, 其原因在于該算法每次將最小的任務(wù)放在最快的資源上執(zhí)行, 因此它每次的執(zhí)行時(shí)間都是最短的。

4 結(jié)論

本文提出了一種新的調(diào)度算法P–Min算法, 該算法根據(jù)任務(wù)的優(yōu)先級(jí)從高到低分配相應(yīng)的資源。如果任務(wù)具有相同的優(yōu)先級(jí), 則處理時(shí)間越短的越先執(zhí)行。如果存在多種分配方法, 則將任務(wù)分配給運(yùn)行任務(wù)數(shù)最小的資源。仿真試驗(yàn)表明: 該算法在任務(wù)總執(zhí)行時(shí)間, 平均系統(tǒng)資源利用率和平均任務(wù)響應(yīng)時(shí)間方面都比Min–Min算法更好。本文中任務(wù)的優(yōu)先級(jí)是已知的, 但是云計(jì)算環(huán)境中的任務(wù)并不一定具有優(yōu)先級(jí), 因此, 如何定義任務(wù)的優(yōu)先級(jí)是以后研究的重點(diǎn)。

參考文獻(xiàn)：

[1] 李建峰, 彭艦. 云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J]. 計(jì)算機(jī)應(yīng)用, 2011, 31(1): 184–186.

[2] 張海賓, 莫琳莎, 劉立祥. 網(wǎng)格調(diào)度綜述[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2009, 30(9): 2 151–2 153.

[3] Agarwal A, Kumar P. Multidimensional QoS Oriented Task Scheduling In Grid Environments [J]. International Journal of Grid Computing & Application, 2011, 2(1): 28–37.

[4] 劉宴兵, 陳杰, 熊仕勇. 基于QoS相似度的網(wǎng)格任務(wù)調(diào)度算法[J]. 重慶郵電大學(xué)學(xué)報(bào), 2009, 21(3): 416–420.

[5] 吳高峰, 蔣玉明, 楊林, 等. 基于QoS改進(jìn)的Min-Min網(wǎng)格調(diào)度算法[J]. 微計(jì)算機(jī)信息, 2009(27): 110–112.

[6] Etminani K, Naghibzadeh M. A min-min max-min selective algorithm for grid task scheduling [C]// Tashkent: In 3th IEEE/IFIP International Conference in Central Asia on Internet, 2007.

[7] Engin O, Ceran G, Yilmaz M K. An efficient genetic algorithm for hybrid flow shop scheduling with multiprocessor task problems [J]. Applied Soft Computing, 2011, 11(3): 3 056–3 065.

[8] Ahmadi A A, Olshevsky A, Parrilo P A, et al. NP-hadness of deciding convexity of quartic polynomials and related problems[J]. Mathematical Programming, 2013, 137(1/2): 453–476.

[9] Duy T V T, Inoghchi Y. A prediction-based green scheduler for datacenters in clouds [J]. IEICE Transactions on Information and Systems, 2011, 94(9): 1 731–1 741.

[10] Calheiros R N, Ranjan R, Beloglazov A, et al. CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms [J]. Software-Practice and Experience, 2011, 41(1): 23–50.

(責(zé)任編校: 江河)

Improved Min-Min scheduling algorithm based on QoS

Lin Zhijie1, Zhang Youbin1, Gu Jing2

(1. Teaching Affairs Office, Hunan College for Preschool Education, Changde 415000, 2. China; School of Software, Central South University, Changsha 410075, China)

The classical Min-Min scheduling algorithm exists the problems of load unbalance, the low resource utilization rate and long processing time. To solve these problems, a scheduling algorithm named P-Min is proposed, which is based on task priority and combined greedy scheduling strategy to schedule. Experimental results show that, as compared with the Min-Min algorithm, the P-Min Algorithm improves 18% in load balance and 8.03% in the overall task execution time, respectively.

cloud computing; QoS; greedy strategy; load balance; Min-Min; P-Min

10.3969/j.issn.1672–6146.2015.03.003

TP 393.01

1672–6146(2015)03–0011–03

林志杰, 461635278@qq.com。

2015–03–17