左利云，左利鋒

（1.廣東石油化工學院 實驗教學部，廣東 茂名525000；2.鄭州宇通客車股份有限公司 新能源產(chǎn)品部，河南 鄭州450016）

0 引 言

云計算是當前IT界的研究熱點，其強大能力最終通過其任務(wù)的運行性能體現(xiàn)，而資源調(diào)度算法設(shè)計的好壞對系統(tǒng)效率的高低起著至關(guān)重要的作用［1－3］。如何充分利用云計算中的計算資源并高效合理的使用是云計算領(lǐng)域的一個研究重點和難點。云計算的使用是付費的，而其費用開銷主要體現(xiàn)在云的使用時間上。因此研究重點還是放在縮短完成時間上。云計算中包含大量異構(gòu)資源，且資源動態(tài)變化，并存在多個任務(wù)競爭資源等問題，這使得傳統(tǒng)的資源調(diào)度算法備受限制［4－8］?，F(xiàn)有的資源調(diào)度算法中以追求最短完成時間為目標的有經(jīng)典的啟發(fā)式算法如Min－Min算法、Max－Min算法和sufferage算法等，另外還有些相應(yīng)的改進算法［9－12］，但是它們沒有很好的兼顧調(diào)度執(zhí)行時間最小與負載平衡問題，這對于以資源共享和追求最大可能利用資源的云計算是很不利的。本文提出一種新的調(diào)度資源算法，以期在實現(xiàn)最小執(zhí)行時間的同時平衡負載，從而實現(xiàn)云計算中資源共享和最大可能的利用資源。

1 預先分類調(diào)度模型

1.1 云計算環(huán)境中的調(diào)度

之前提到云計算中資源異構(gòu)且動態(tài)變化等特點會影響到調(diào)度策略問題，事實上云計算環(huán)境中的服務(wù)類型也會影響到云計算資源的調(diào)度［13］，因為不同的服務(wù)類型，在資源使用、負載類型和性能評價指標等方面也有很大差異。

云計算中的服務(wù)大致分為兩大類：數(shù)據(jù)計算密集型服務(wù) （下簡稱計算型）和交互密集型網(wǎng)絡(luò)處理服務(wù) （下簡稱交互型），在負載類型、資源使用和性能評價的差異如下：

（1）負載特征：計算型負載是并行批處理作業(yè)，交互型負載是一系列的單鏈接或多鏈接的請求序列組成；

（2）資源使用特征：計算型需要獨占資源處理作業(yè)，交互型請求可以在共享資源上并發(fā)執(zhí)行；

（3）服務(wù)性能指標：計算型服務(wù)的用戶可以容忍作業(yè)的排隊等等，直到獲得運行的資源，而交互型服務(wù)的用戶請求需要在線立即地響應(yīng)。

本文的調(diào)度算法主要針對計算型云計算服務(wù)而進行研究的。因此批處理算法中的經(jīng)典算法——Min－Min算法無論從其追求最小完成時間的目標，還是針對數(shù)據(jù)計算密集型服務(wù)調(diào)度的特點，都說明該算法比較適合云計算中計算型服務(wù)調(diào)度。該算法簡單、快速，通過計算兩次最小值來完成資源的調(diào)度，盡可能將大量的任務(wù)調(diào)度到執(zhí)行它最快的資源，以使得總體完成時間最小。但它總優(yōu)先調(diào)度小作業(yè)，造成對大任務(wù)不公平的問題，也使得部分資源繁忙，部分資源閑置。針對此問題也有一些對應(yīng)的改進算法，如文獻 ［14］為了平衡負載根據(jù)QoS需求對資源簡單分成兩大類：特殊資源和一般資源，對任務(wù)也分類標記，將指定高要求的任務(wù)調(diào)度至特定資源，但它對資源分類過于簡單，沒有提及分類依據(jù)。

在此也提出對Min－Min算法進行改進優(yōu)化，首先對云計算中資源根據(jù)其屬性信息進行預先分類，以確保負載平衡，再對分類后資源結(jié)合Min－Min算法思想進行調(diào)度，以實現(xiàn)調(diào)度時間最小，從而兼顧執(zhí)行時間最小與負載均衡。

1.2 預先分類調(diào)度模型

由于Min－Min算法僅考慮作業(yè)在資源的執(zhí)行時間，故嘗試將資源本身的因素考慮在內(nèi)，在調(diào)度前先對資源進行等級劃分，在調(diào)度時結(jié)合資源等級及任務(wù)調(diào)度執(zhí)行時間，從而確保時間最小并充分利用資源平衡負載。基于此思想，調(diào)度模型的調(diào)度器由兩部分組成：預先分類窗口和調(diào)度窗口。首先在預先分類窗口對云計算系統(tǒng)中資源的屬性信息進行分類，將分類后資源等級數(shù)據(jù)信息送入下一單元——調(diào)度窗口，再使用Min－Min改進優(yōu)化算法進行調(diào)度輸出，如圖1所示。

2 預先分類方法

圖1 預先分類模型框架

為了充分利用云計算中的資源，尤其是優(yōu)勢資源，在調(diào)度器中先對云計算系統(tǒng)中的資源進行分類，在此采用可標識資源自身屬性的資源可見度η這一指標，該指標用來衡量資源的計算能力和通信能力，它是根據(jù)在資源加入云計算系統(tǒng)時提供的屬性信息來計算的，主要包括CPU個數(shù)h及處理能力P、磁盤容量C（MB）和資源所在的網(wǎng)絡(luò)帶寬B（Mb／s）。其中，CPU個數(shù)h和處理能力P主要反映資源計算能力，帶寬反映資源的通信能力。資源可見度具體計算公式如下

式中：a、b、c——資源計算能力、磁盤容量、帶寬在資源可見度這一指標中所占的比重。由于現(xiàn)在調(diào)度的對象是云計算中數(shù)據(jù)計算密集型服務(wù)，故根據(jù)需要在此分別將a、b、c設(shè)定為40%、20%、40%。

根據(jù)計算出的資源可見度η進行資源等級分類。具體做法是對資源按η從大到小進行排序，排名前35%的定為第1級，以下的30%、20%、15%分別定為第2、3、4等級。

3 基于預先分類的Min－Min優(yōu)化調(diào)度算法

首先分析原始Min－Min算法的調(diào)度思想和執(zhí)行過程，針對其負載不均衡問題進行改進優(yōu)化，結(jié)合之前對資源劃分的等級提出新的改進算法，即基于預先分類的Min－Min優(yōu)化調(diào)度算法 （reservation category Min－Min，RCMM）。

3.1 原始的 Min－Min算法

原始的Min－Min算法盡可能將任務(wù)分配到執(zhí)行時間最小的資源上，從而使得整體完成時間最小。Min－Min算法中 “Min－Min”的含義是通過計算兩次最小值來完成資源的調(diào)度，兩次最小值分別指的是首先計算每個任務(wù)在相應(yīng)資源上的最小完成時間，再從這些最小完成時間中擇其最小值，那么此時的資源－任務(wù)組合即為最佳資源－任務(wù)組合［15］。算法過程如下。

首先假設(shè)云計算環(huán)境中有n個任務(wù)Y＝ ｛y1，y2，…，yn｝和m個資源X＝ ｛x1，x2，…，xm｝。循環(huán)執(zhí)行以下步驟直至集合為空：

（1）for each yiin Y；

求 mintime（yi至x1，x2，…，xm）；

Tmin（i）＝Min（mintime（yi至x1，x2，…，xm））；

得到有m個元素的數(shù)組Tmin（i）；

（2）if Tmin（i）最??；

yi調(diào)度至xj；

（3）delete yi；

Next yi

表1列出了每個作業(yè)任務(wù)在相應(yīng)資源的預期執(zhí)行時間矩陣的值，其中 “－”代指該作業(yè)無法在此資源運行，如作業(yè)y1只能在資源x1、x3、x4上執(zhí)行，而作業(yè)y3則可以在任何一個資源執(zhí)行。由算法執(zhí)行過程可知，調(diào)度順序為：y5（x1），y2（x1），y1（x1），y3（x1），y4（x1）。此時任務(wù)總體完成時間為：4＋3＋7＋10＋2＝26ms。但此時所有的作業(yè)都使用資源x1，而資源x2、x3、x4完全空閑，導致資源嚴重失衡，這就是Min－Min算法的最大缺點，它總是優(yōu)先調(diào)度小任務(wù)而不能確保云計算資源負載平衡。這對于以資源共享和追求最大可能利用資源的云計算來說是非常嚴重的問題。因此必須改善這種狀況，以適應(yīng)云計算環(huán)境的需要。

表1 作業(yè)任務(wù)在資源上的預期執(zhí)行時間

3.2 RCMM調(diào)度算法

針對以上對原始Min－Min調(diào)度算法的分析，提出基于預先分類的 Min－Min優(yōu)化調(diào)度算法——RCMM調(diào)度算法，給出其執(zhí)行過程，并與原始算法進行對比分析。

3.2.1 算法執(zhí)行過程

由以上分析知原始的Min－Min調(diào)度算法存在的負載不均衡問題，改進的Min－Min調(diào)度算法就是要解決這個問題的，考慮資源差異，首先算出每個作業(yè)任務(wù)在所有資源上的執(zhí)行組合值 （即作業(yè)在資源上的執(zhí)行時間與資源等級的乘積）情況，然后從中選擇執(zhí)行組合值最小的任務(wù)－資源對進行調(diào)度，這樣既能保證執(zhí)行時間最小，又同時保證了調(diào)度過程的負載平衡。

仍然假設(shè)云計算環(huán)境中有n個任務(wù)Y＝ ｛y1，y2，…，yn｝和m個資源X＝ ｛x1，x2，…，xm｝。循環(huán)執(zhí)行以下步驟至集合為空：

（1）for each yiin Y

求 mintime（yi至x1，x2，…，xm）；

yiTmin（i）＝Min（mintime（yi至x1，x2，…，xm））；

（2）Comxy（i，j）＝y(tǒng)iTmin（i）×資源等級；

得到二維數(shù)組Comxy［i，j］；

（3）對Comxy［i，j］排序；

（4）if Comxy［i，j］最小；

將yi調(diào)度至xj；

（5）delete yi；

Next yi

該算法相對于原始的Min－Min算法，除依然追求最小執(zhí)行時間，還考慮到了平衡負載。

3.2.2 算法分析

對于資源x1、x2、x3、x4由預先分類方法計算出相應(yīng)等級類別分別為3、2、1、1。通過RCMM調(diào)度算法，得出作業(yè)與資源相關(guān)數(shù)據(jù)信息如表2所示。

表2 作業(yè)任務(wù)在資源上的預期執(zhí)行時間和資源等級屬性

從表2可以看出：如果采用原始的Min－Min調(diào)度算法來執(zhí)行的話，那么所有的任務(wù)都選擇在資源x1上執(zhí)行，調(diào)度的順序依次為：y5（x1），y2（x1），y1（x1），y3（x1），y4（x1）。造成x1負載過重，單個資源利用率為100%，而x2、x3、x4卻閑置，利用率為0。這是原始的Min－Min調(diào)度算法的最大問題。若采用本文改進的算法，先計算每個作業(yè)任務(wù)與各個資源的執(zhí)行組合值分別為：y1（4＊4，－，4.5＊1，5＊2）；y2（3＊4，3.5＊3，12＊1，－）；y3（7＊4，8＊3，7.5＊1，9＊2）；y4（10＊4，11＊3，－，10.5＊2）；y5（2＊4，9.5＊3，9＊1，6＊2）。對每個作業(yè)取執(zhí)行組合值最小的作業(yè)－資源對，調(diào)度順序為：y1（x3），y5（x1），y2（x2），y3（x3），y4（x4）。這時作業(yè)整體完成時間為：4.5＋3.5＋7.5＋10.5＋2＝28ms。

由以上分析可知，改進后的算法使得作業(yè)整體完成時間增加了2ms，但是平衡了負載，原始的Min－Min調(diào)度算法使得所有的任務(wù)都在x1上執(zhí)行，而x2、x3、x4空閑，導致x1負載過重，資源嚴重失衡，資源x1的利用率為100%，而x2、x3、x4的利用率均為0。而改進后的算法使得資源x1、x2、x3、x4的利用率分別為20%、20%、40%、20%，提高了資源的整體利用率，避免了資源調(diào)度中部分資源擁塞而部分資源閑置的現(xiàn)象。因此雖使得作業(yè)整體完成時間略有增加，但解決了原有算法最大的問題——負載不均衡，使得資源——尤其是優(yōu)勢資源得到充分利用，這對于以資源共享和最大利用為主要目的的云計算是非常重要的。

4 實驗驗證

為了評估提出的調(diào)度算法的性能，使用云計算仿真軟件CloudSim采用離散事件模擬了云計算實驗環(huán)境，主要來驗證：①所提算法適用于云計算環(huán)境；②實現(xiàn)原始 Min－Min調(diào)度算法和改進算法的性能比較。

通過以下4個指標評估算法性能：①任務(wù)響應(yīng)時間RT（response time），指從任務(wù)進入云計算系統(tǒng)起到該任務(wù)完成這段時間，定義為任務(wù)的等待時間與完成時間的和；②任務(wù)總體完成時間，即所有任務(wù)總的完成時間，是從第一個任務(wù)進入云計算系統(tǒng)到最后一個任務(wù)完成這段時間；③速度下降比S（slowdown），表示任務(wù)在云計算環(huán)境中執(zhí)行與在單一站點中執(zhí)行時的速度下降率，定義為任務(wù)響應(yīng)時間與實際完成時間的比值；④系統(tǒng)資源利用率 （Ui），表示資源的忙閑程度，它也是云計算環(huán)境下任務(wù)調(diào)度比較好的一個指標，因為云計算的目的主要在于資源的有效共享和最大利用。

在仿真的云計算數(shù)據(jù)計算密集型實驗系統(tǒng)中，實現(xiàn)了本文算法和原始的Min－Min算法，該系統(tǒng)中有500個計算節(jié)點和300個數(shù)據(jù)源，其中每個計算節(jié)點的處理能力不同，數(shù)據(jù)源與不同計算節(jié)點間的傳輸速率隨機產(chǎn)生，范圍是100－250kbps。實驗中共采用3組任務(wù)，任務(wù)數(shù)分別為1000、2000和3000。任務(wù)的進入時間和執(zhí)行時間也隨機產(chǎn)生，范圍是1－205s。任務(wù)也是隨機進入仿真實驗系統(tǒng)的，任務(wù)在數(shù)據(jù)源中的存儲量隨機產(chǎn)生，范圍是200－10000KB。另外計算節(jié)點只能接收處理能力范圍內(nèi)的任務(wù)。實驗仿真結(jié)果如圖2所示。

圖2 兩種算法的仿真實驗結(jié)果

從圖2可以看出，改進算法在任務(wù)平均響應(yīng)時間方面比原始Min－Min算法有了明顯的提高，如在任務(wù)數(shù)量為3000時，平均任務(wù)響應(yīng)時間為3.5s，比 Min－Min算法減少了約1.5s；在不同任務(wù)數(shù)量的情況下改進算法得到的總?cè)蝿?wù)完成時間與原始Min－Min算法相差無幾，特別是在任務(wù)數(shù)量比較多的情況下，這種差距更?。桓倪M算法的任務(wù)平均速度下降比比原始的 Min－Min算法提高了15%左右；4個指標中改進算法的整個系統(tǒng)的利用率方面的表現(xiàn)最好，比Min－Min算法提高了56%左右。從實驗結(jié)果可以看出，改進算法更適合在本地執(zhí)行的任務(wù)，從而得到更小的平均任務(wù)響應(yīng)時間、平均速度下降比和更高的系統(tǒng)利用率。當任務(wù)數(shù)量增加時，改進算法仍然得到較小的任務(wù)總體完成時間，這表明該方法非常適用于云計算這種數(shù)據(jù)計算密集型服務(wù)環(huán)境。

5 結(jié)束語

原始Min－Min算法中的負載不均衡現(xiàn)象會嚴重影響以資源共享和追求資源最大利用為目的的云計算系統(tǒng)的性能。同時考慮云的使用付費問題，故本文算法將縮短云計算的使用時間 （包括響應(yīng)時間和完成時間）、平衡負載和充分利用優(yōu)勢資源作為主要目的。根據(jù)資源CPU個數(shù)h及處理能力P、磁盤容量C和資源所在的網(wǎng)絡(luò)帶寬B等3個參數(shù)計算資源的可見度，并據(jù)此對資源進行分類，計算出分類等級，通過計算資源等級與作業(yè)在資源上的預期執(zhí)行時間的乘積，該乘積值最小的即為最適合的資源－任務(wù)對。為驗證RCMM調(diào)度算法和原始Min－Min算法是否適合云計算環(huán)境，利用云仿真軟件模擬了云計算環(huán)境，采用RT、任務(wù)總體完成時間、S和Ui等指標比較兩算法的優(yōu)劣。實驗結(jié)果表明，RCMM算法除在任務(wù)總體完成時間方面表現(xiàn)稍遜于原始算法外，在RT、S和Ui的表現(xiàn)均優(yōu)于原始的 Min－Min算法，特別是在系統(tǒng)利用率方面的表現(xiàn)尤為出色，這對于云計算這種以追求資源共享和最大限度利用資源的系統(tǒng)來說是十分重要的。雖然任務(wù)總體完成時間方面稍遜于原始算法，但這種差距隨著任務(wù)量的增多而縮小，說明該算法非常適合云計算中數(shù)據(jù)密集型服務(wù)調(diào)度的。

本文研究主要針對云計算中數(shù)據(jù)密集型服務(wù)調(diào)度，至于云計算中交互密集型網(wǎng)絡(luò)處理服務(wù)調(diào)度，還有待進一步研究。

［1］WANG Jiajun，LU Zhihui，WU Jie，et al.Cloud computing technology development analysis and applications discussion［J］.Computer Engineering ＆ Design，2010，31 （20）：4404－4409（in Chinese）.［王佳雋，呂智慧，吳杰，等.云計算技術(shù)發(fā)展分析及其應(yīng)用探討 ［J］.計算機工程與設(shè)計，2010，31（20）：4404－4409.］

［2］FANG Bingyi，ZHANG Yunyong，CHENG Ying.Analysis in the present and developing status of cloud computing ［J］.Telecommunication Science，2010，55 （S1）：1－6 （in Chinese）.［房秉毅，張云勇，程瑩.云計算國內(nèi)外發(fā)展現(xiàn)狀分析［J］.電信科學，2010，55 （S1）：1－6.］

［3］Francesco Maria Aymerich，Gianni Fenu，Simone Surcis.An approach to a cloud computing network ［C］.First International Conference on the Applications of Digital Information and Web Technologies，2008：113－118.

［4］Ahson S，Ilyas M.Cloud computing and software services［M］.Florida，USA：CRC Press，2009.

［5］TANG Xiaochun，LIU Jian.Better allocation of meta－zone in cloud computing environment ［J］.Computer Engineering and Applications，2010，46 （34）：237－241 （in Chinese）. ［湯小春，劉健.基于元區(qū)間的云計算基礎(chǔ)設(shè)施服務(wù)的資源分配算法研究 ［J］.計算機工程與應(yīng)用，2010，46 （34）：237－241.］

［6］Foster I，Zhao Yong，Raicu I，et al.Cloud computing and grid computing 360degree compared ［C］.Proceedings of the Grid Computing Environments Workshop.Washington，DC：IEEE Computer Society，2008：1－10.

［7］Caron E，Desprez F，Loureiro D，et al.Cloud computing resource management through a grid middleware：A case study with DIET and eucalyptus［C］.Bangalore，India：IEEE International Conference on Cloud Computing，2009.

［8］LI Jianfeng，PENG Jian.Task scheduling algorithm based on improved genetic algorithm in cloud computing environment ［J］.Journal of Computer Applications，2011，31 （1）：184－186 （in Chinese）.［李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算法 ［J］.計算機應(yīng)用，2011，31 （1）：184－186.］

［9］TIAN Guanhua，MENG Dan，ZHAN Jianfeng.Reliable resource provision policy for cloud computing ［J］.Computer Journal，2010，33 （10）：1859－1871 （in Chinese）. ［田冠華，孟丹，詹劍鋒.云計算環(huán)境下基于失效規(guī)則的資源動態(tài)提供策略 ［J］.計算機學報，2010，33 （10）：1859－1871.］

［10］GAO Hongqing，XING Ying.Research on cloud resource management model based on economics ［J］.Computer Engineering ＆ Design，2010，31 （19）：4139－4142 （in Chinese）.［高宏卿，邢穎.基于經(jīng)濟學的云資源管理模型研究［J］.計算機工程與設(shè)計，2010，31 （19）：4139－4142.］

［11］Kimj S，Nam B，Marsh M，et al.Creating a robust desktop

grid using peer to peer services ［EB／OL］. ［2009－10－16］.

ftp：／／ftp.cs.umd.edu／pub／hpsl／papers／papers－pdf／ngs07.pdf.［12］Blythe J，Jain S，Declman E，et al.Task scheduling strategies for workflow－based applications in grids ［EB／OL］.http：／／grid.cs.tsinghua.edu.cn，2005.

［13］SUN Ruifeng，ZHAO Zhengwen.Resource scheduling strategy based on cloud computing ［J］.Aeronautical Computing Technique，2010，40 （3）：103－105 （in Chinese）. ［孫瑞鋒，趙政文.基于云計算的資源調(diào)度策略 ［J］.航空計算技術(shù)，2010，40 （3）：103－105.］

［14］WU Gaofeng，CAI Yuming，YANG Lin，et al.Scheduling algorithm of modified Min－Min based on QoS in grid ［J］.Micro Computer Information，2009，26 （9）：110－112 （in Chinese）.［吳高峰，蔣玉明，楊林，等.基于QoS改進的網(wǎng)格調(diào)度算法［J］.微計算機信息，2009，26 （9）：110－112.］

［15］DU Yuxia，LIU Fangai，GUO Lei.Research and improvement of Min－Min scheduling algorithm ［J］.Computer Engineering and Applications，2010，46 （24）：107－109 （in Chinese）. ［杜玉霞，劉方愛，郭磊.Min－Min調(diào)度算法的研究與改進 ［J］.計算機工程與應(yīng)用，2010，46 （24）：107－109.］