基于負載均值的云調(diào)度算法研究

鄧先瑞，李春艷，齊 偉

（1. 唐山師范學(xué)院 計算機科學(xué)系，河北 唐山 063000；2. 唐山市先進仿真技術(shù)重點實驗室，河北 唐山 063000；3. 北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044）

基于負載均值的云調(diào)度算法研究

鄧先瑞1,2，李春艷1,3，齊 偉3

（1. 唐山師范學(xué)院 計算機科學(xué)系，河北 唐山 063000；2. 唐山市先進仿真技術(shù)重點實驗室，河北 唐山 063000；3. 北京交通大學(xué) 計算機與信息技術(shù)學(xué)院，北京 100044）

在云計算環(huán)境中，由于調(diào)度算法的局限性而易造成某些節(jié)點負載過重，進而導(dǎo)致整個云計算平臺負載不均衡和資源利用效率低下。針對此問題，在經(jīng)典的Min-Min調(diào)度算法的基礎(chǔ)上，提出了一種基于負載均值思想的任務(wù)調(diào)度算法。采用云計算模擬器CloudSim對算法進行仿真。仿真結(jié)果表明，改進的算法在實現(xiàn)了物理機和虛擬機層的負載均衡的同時，有效地提高了資源利用率。

Min-Min；負載均值；CloudSim；云計算

1 引言

云計算是網(wǎng)格計算的發(fā)展，在一定程度上，云計算的任務(wù)調(diào)度與網(wǎng)格計算具有相似性和可借鑒性，網(wǎng)格計算的任務(wù)調(diào)度和資源分配已得到廣泛研究。云計算不同于網(wǎng)格計算，它所采用的商業(yè)理念、形式、成熟的虛擬化技術(shù)以及非標準化的規(guī)范，使得云計算環(huán)境下的任務(wù)調(diào)度呈現(xiàn)不同的特點[1]。

任務(wù)調(diào)度是一個NP完全問題。目前關(guān)于這個問題，國內(nèi)外已經(jīng)作了很多研究工作，出現(xiàn)了很多經(jīng)典的任務(wù)調(diào)度算法。比如Hadoop默認FIFO[2]調(diào)度算法來進行任務(wù)調(diào)度，其有較好的調(diào)度效率，但不能保證小任務(wù)的及時執(zhí)行。FaceBook針對此缺點開發(fā)了能夠保證小任務(wù)得到迅速響應(yīng)，大任務(wù)保證服務(wù)水平的公平調(diào)度算法[3]。Yahoo提出了計算能力調(diào)度算法即Capacity調(diào)度器[8]。Baomin Xu等基于伯格模型提出了公平調(diào)度算法。在任務(wù)與資源進行匹配時，以QoS參數(shù)的匹配作為依據(jù)，依據(jù)資源分配的公平性原則將最佳匹配的資源分配給任務(wù)[4]。

云環(huán)境下任務(wù)調(diào)度的本質(zhì)是在任務(wù)和資源之間建立起一個映射，然后按照給定的映射關(guān)系將任務(wù)調(diào)度到合適的計算資源上執(zhí)行。因此，云環(huán)境下任務(wù)調(diào)度的策略就是如何在任務(wù)和資源之間找到一個合適的映射關(guān)系，使得云環(huán)境下的任務(wù)調(diào)度在實現(xiàn)用戶任務(wù)基本需求的基礎(chǔ)上達到各個性能指標的優(yōu)化。其中，考察云環(huán)境下的任務(wù)調(diào)度算法的主要指標之一就是負載均衡。即如果某些節(jié)點的負載超過其能夠承受的負載閾值，平臺的整體性能將受很大影響，并且會造成計算資源分配不均，導(dǎo)致資源的浪費。任務(wù)調(diào)度應(yīng)該盡量將任務(wù)調(diào)度到負載較輕的節(jié)點運行以維持系統(tǒng)的負載均衡。由于云系統(tǒng)中的計算機數(shù)量非常龐大，組成復(fù)雜。使得目前云計算中負載均衡和最優(yōu)跨度的實現(xiàn)成為具有挑戰(zhàn)性的問題[5]。

本文在對經(jīng)典的Min-Min算法[6]進行分析的基礎(chǔ)上，針對云計算系統(tǒng)中可能因負載不均衡而造成的系統(tǒng)效率低下的問題，提出了一個改進的任務(wù)調(diào)度算法。該算法充分考慮任務(wù)分配過程中QoS[7]因素的影響，以節(jié)點的負載均值為標準，賦予任務(wù)不同的優(yōu)先級，從優(yōu)先級最高的(即對主機QoS要求最高)任務(wù)開始分配，從而獲得較小的最優(yōu)跨度（makespan）。

2 背景知識

2.1 任務(wù)調(diào)度問題

任務(wù)調(diào)度問題的實質(zhì)就是在一個由m個需要調(diào)度的任務(wù)，n個可用的任務(wù)執(zhí)行單元（集群中的節(jié)點）構(gòu)成的分布運行環(huán)境下，把m個任務(wù)T={t1, t2, …, tm}以合理的方式調(diào)度到n個主機H={h1,h2,…, hn}上去，設(shè)法獲得盡可能小的總執(zhí)行時間。

假設(shè)每個任務(wù)在任意一臺機器上的靜態(tài)運行時間是預(yù)知的，任務(wù)的期望運行時間（Expected Time to Compute）可以由ETC矩陣來描述。m個任務(wù)在n個不同機器上的預(yù)測執(zhí)行時間ETC是一個m×n的矩陣。矩陣的每一行代表某一個任務(wù)在n臺機器上的不同執(zhí)行時間，每一列代表在同一臺機器上，m個不同任務(wù)的不同執(zhí)行時間。

當一個任務(wù)ti被分配到一個機器時，其期望完成時間MCT(i,j)可定義為機器hj的期望就緒時間與任務(wù)ti在機器hj的期望執(zhí)行時間之和，即

其中TASKSTART(j)為機器j的期望就緒時間。

2.2 經(jīng)典Min-Min算法

Min-Min算法[8,9]是目前分布環(huán)境下比較經(jīng)典的任務(wù)調(diào)度算法之一，該算法的主要思想如下：當需要調(diào)度的任務(wù)集合非空時，反復(fù)執(zhí)行如下操作直至集合為空：

（1）對集合T中每一個等待分配的任務(wù)ti，分別計算把該任務(wù)ti分配到n臺機器上的最小完成時間MinTime(i)，可得到一個含有m個元素的一維數(shù)組MinTime；

（2）設(shè)MinTime中最小的元素為MinTime(k)，其中任務(wù)k對應(yīng)的主機為h，則把任務(wù)k分配到機器h上；從任務(wù)集合中刪除任務(wù)k，同時更新MCT矩陣。

理論上已經(jīng)證明，在一般情況下，Min-Min算法能夠獲得較小的makespan，效率較高，但是這種方法存在著一個很大的缺點，即算法的負載平衡性能不高。其主要原因是Min-Min算法并沒有考慮調(diào)度過程中涉及到的QoS的因素。不同計算資源能夠提供不同的QoS，不同任務(wù)對于資源QoS的要求也不盡相同。忽視QoS因素的就會出現(xiàn)這樣的情況，即對QoS要求比較低的任務(wù)占用了高QoS的資源，而對QoS要求較高的任務(wù)只有等待高QoS的資源空閑后才能夠得到執(zhí)行。這顯然大大降低了效率及資源的利用率。

3 改進的Min-Min算法

3.1 預(yù)備知識

為了便于后面對算法進行描述，這里先介紹幾個基本概念。

（1）離散型隨機變量Si，其中i=1,2…m，它的取值為任務(wù)ti在各個計算節(jié)點上的期望執(zhí)行時間，共有n個，分別為ETC(i,1)，ETC(i,2)…ETC(i,n)，同時任務(wù)ti分配到任何一個計算節(jié)點上的概率是相同的，為1/n。

（2）隨機變量Si的數(shù)學(xué)期望ESi，其中i=1,2…m，它表示任務(wù)ti在n個計算節(jié)點上的期望執(zhí)行時間的均值。故

（3）負載均值ES。每個任務(wù)ti在n個計算節(jié)點上期望執(zhí)行時間的均值ESi可以理解為該任務(wù)給可用的計算節(jié)點提供執(zhí)行時間為ESi的負載。最理想的情況，就是m個任務(wù)分配到n個計算節(jié)點上，實現(xiàn)了完全的負載平衡，定義ES為ESi（i=1，2，3…m）的平均值：

（4）集合T1。在改進的Min-Min算法中，所有的任務(wù)都要根據(jù)其對資源QoS的要求賦予優(yōu)先級。以負載均值ES為標準，具體對某一任務(wù)來說，可能其在某些計算節(jié)點上的執(zhí)行時間會超過ES。T1集合內(nèi)的任務(wù)滿足的條件是：其中一個任務(wù)在各個計算節(jié)點上的期待完成時間中超過負載均值的個數(shù)最多，也可以理解為該集合中的任務(wù)對資源QoS的要求最高。

3.2 算法描述

改進的Min-Min算法可分為兩個階段：第一階段計算每個任務(wù)ti在各計算節(jié)點上的最小完成時間，得到一維數(shù)組MinTime，同時記錄任務(wù)ti無效計算節(jié)點個數(shù)NUMi（無效計算節(jié)點是指任務(wù)在這些計算節(jié)點上的期望完成時間超過負載均值ES），得到集合T1；第二階段，在任務(wù)集合T1上使用Min-Min算法分配一個任務(wù)。分配過的任務(wù)將從T中移走，然后清空任務(wù)集合T1。

算法的具體執(zhí)行步驟為：

1. 根據(jù)ETC矩陣計算每個任務(wù)在n個虛擬機上執(zhí)行時間的均值ESi和負載均值ES；

2. 將每臺虛擬機的期望就緒時間TASKSTART(j)初始化為0，若T不為空，采用循環(huán)重復(fù)以下操作：

（1）初始化任務(wù)組T1為空；

（2）對于每個任務(wù)ti，計算它在每個虛擬機hj上的期待完成時間MCT(i,j)，將該任務(wù)的最小完成時間賦給一維數(shù)MinTime(i)；

（3）在步驟2的同時，比較ES和任務(wù)ti在各個虛擬機上期待完成時間MCT(i,j)的大小關(guān)系，根據(jù)任務(wù)ti的無效虛擬機的數(shù)目，將滿足要求的任務(wù)添加到任務(wù)組T1；

（4）對任務(wù)組T1，利用傳統(tǒng)Min-Min算法來分配一個任務(wù)，分配成功后修改相應(yīng)的MCT矩陣。若T不為空回到步驟1。

4 實驗與結(jié)果分析

4.1 實驗環(huán)境

在這里使用云模擬器CloudSim[10,11]對實驗算法進行仿真研究。CloudSim是2009年4月澳大利亞墨爾本大學(xué)的網(wǎng)格實驗室和Gridbus項目宣布推出的云計算仿真軟件。其首要目標是在云基礎(chǔ)設(shè)施上對不同應(yīng)用和服務(wù)模型的調(diào)度和分配策略的性能進行量化和比較，從而達到控制云計算資源使用的目的。在使用CloudSim時，研究者和開發(fā)者只需要關(guān)注特定系統(tǒng)的抽象層的算法、策略和協(xié)議的開發(fā)，無須關(guān)注與云基礎(chǔ)設(shè)施和服務(wù)等底層相關(guān)的實現(xiàn)細節(jié)。

進行模擬實驗時，CloudSim中采用5個不同的虛擬機，各個虛擬機的具體配置如表1所示。

表1 Cloudlet的資源配置

4.2 實驗結(jié)果

實驗中假定有10臺機器，任務(wù)的預(yù)測執(zhí)行時間矩陣ETC給定，我們根據(jù)任務(wù)數(shù)的不同分別作三組實驗，每組的任務(wù)數(shù)分別為20、40、50個。在每一組實驗中，我們隨機使用4組ETC用例來查看實驗結(jié)果，三組實驗結(jié)果分別如表2、表3和表4所示。

表2 第一組實驗結(jié)果（任務(wù)數(shù)為20個）

表3 第二組實驗結(jié)果（任務(wù)數(shù)為40個）

表4 第三組實驗結(jié)果（任務(wù)數(shù)為50個）

三組實驗結(jié)果表明，在任務(wù)調(diào)度過程中，本文提出的改進算法得到的makespan同傳統(tǒng)Min-Min算法取得的makespan相比明顯減少，可以提高系統(tǒng)的有效性。

5 結(jié)束語

本文在經(jīng)典的Min-Min調(diào)度算法的基礎(chǔ)上，引入QoS因素，提出了一種基于負載均值思想的改進策略，并且在CloudSim中對改進的算法進行了仿真驗證。仿真結(jié)果表明，改進算法達到了既能夠在云計算環(huán)境下安全高效地執(zhí)行任務(wù)，又能夠?qū)崿F(xiàn)系統(tǒng)中負載基本均衡的目標。

[1] 劉美林.云計算中基于博弈論的任務(wù)調(diào)度算法研究[D].北京:北京工業(yè)大學(xué),2014:18-19.

[2] Kamal Kc, Kemafor Anyanwu. Scheduling hadoop jobs to meet deadlines[C]. Indianapolis, Indiana, USA: IEEE Second International Conference on Cloud Computing Technology and Science (CloudCom), 2010: 388-392.

[3] http://hadoop.apache.org/docs/r1.2.1/fair_scheduler.html.

[4] Randles, Martin, David Lamb, A Taleb-Bendiab. A com-parative study into distributed load balancing algorithms for cloud computing[C]. 24th IEEE International Conference on Advanced Information Networking and Applications Workshops (WAINA), Perth, Australia, 2010: 551-556.

[5] Baomin Xu, Chunyan Zhao, Enzhao Hu, et al. Job scheduling algorithm based on Berger model in cloud environment[J]. Advances in Engineering Software, 2011, 42(7): 419-425.

[6] Xiaoshan He, Xianhe Sun, Gregor Von Laszewski. QoS guided min-min heuristic for grid task scheduling[J]. Journal of Computer Science and Technology, 2003, 18(4): 442-451. [7] B. Sabata, S. Chatterjee, M. Davis, et al. Taxonomy for QoS specifications[C]. Newport Beach, CA: Workshop on Object-Oriented Real-Time Dependable Systems, 1997: 100-107.

[8] X Ma, Y Wang, and X Pei. A Scalable and Reliable Matching Service for Content-Based Publish/Subscribe Systems[J]. IEEE Transactions on Cloud Computing, 2014, 3(1):1-13.

[9] L Heilig, S Voss. A Scientometric Analysis of Cloud Computing Literature[J]. IEEE Transactions on Cloud Computing, 2014, 2(3):266-278.

[10] Rodrigo N. Calheiros, Rajiv Ranjan, Anton Beloglazov, 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.

[11] 鄧見光.云計算任務(wù)調(diào)度策略研究[D].廣州:華南理工大學(xué), 2014:22-25.

（責(zé)任編輯、校對：趙光峰）

中國學(xué)術(shù)期刊影響因子年報（人文社會科學(xué)?2014版）

編號：CST-JIFR 2014 TSSF

期刊名稱：唐山師范學(xué)院學(xué)報

主辦單位：唐山師范學(xué)院

學(xué)科類目：綜合性人文、社會科學(xué) 研究層次：理論研究

CN/ISSN：CN 13-1301/G ISSN 1009-9115

影響因子種類 即年指標 影響因子 他引影響因子5年影響因子 他引5年影響因子 影響因子學(xué)科排序復(fù)合JIF 0.033 0.223 0.209 0.264 0.257 395/631期刊綜合JIF 0.029 0.082 0.068 0.077 0.070 466/631人文社科JIF 0.022 0.071 0.057 0.057 0.050 446/631

來源：中國學(xué)術(shù)期刊（光盤版）雜志社

中國科學(xué)文獻計量評價研究中心

2014-12-05

The Research on Cloud Scheduling Algorithm Based on Load Average

DENG Xian-Rui1,2, LI Chun-Yan1,3, QI Wei3

(1. Department of Computer Science, Tangshan Normal University, Tangshan 063000, China; 2. Tangshan Advanced Simulation Technology Key Laboratory, Tangshan 063000, China; 3. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China)

A task scheduling algorithm based on load average is presented in this paper, which is developed from the classical Min-Min task scheduling algorithm. The proposed algorithm is used for Cloud Computing, in which the loads of some nodes get too heavy that the load of the whole Cloud Computing platform becomes imbalanced and the utilization of resources becomes low because of the limitation of scheduling algorithms. The simulation of the proposed algorithm was done by using Cloud Computing Simulator (CloudSim). The result shows the improved algorithm can achieve load balancing between physical machines and virtual machines and it can promote the utilization of resources.

Min-Min; load average; CloudSim; Cloud Computing

TP393.09

A

1009-9115(2015)02-0038-04

10.3969/j.issn.1009-9115.2015.02.012

河北省科技計劃項目（13220319D），唐山師范學(xué)院博士基金項目（07A01）

2014-08-31

鄧先瑞（1973-），女，四川成都人，博士，副教授，研究方向為計算機算法。

計算機科學(xué)與技術(shù)