基于Kriging代理模型的動(dòng)態(tài)云任務(wù)調(diào)度方法

李召軍 ，李 征 ，王希誠(chéng) ，李克秋

1.大連理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 大連 116023

2.大連理工大學(xué) 工業(yè)裝備結(jié)構(gòu)分析國(guó)家重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116023

1 引言

云計(jì)算提供了一種按需分配的服務(wù)模式，憑借云平臺(tái)提供的高性能軟硬件資源運(yùn)行作業(yè)，可以在較大程度上為用戶節(jié)約計(jì)算成本和運(yùn)行時(shí)間。任務(wù)調(diào)度作為云計(jì)算環(huán)境下資源調(diào)度的一個(gè)重要子課題，其好壞程度直接影響了用戶的使用體驗(yàn)。近年來(lái)，智能優(yōu)化算法在云計(jì)算的任務(wù)調(diào)度領(lǐng)域發(fā)展迅速。如果能夠使用有效的方法對(duì)復(fù)雜環(huán)境下的云任務(wù)進(jìn)行性能分析和建模，優(yōu)化計(jì)算后獲取其最佳的資源分配方案，將對(duì)云平臺(tái)本身的資源分配模式及用戶的使用體驗(yàn)產(chǎn)生重要的影響。

本文發(fā)展了一種基于Kriging代理模型的動(dòng)態(tài)云任務(wù)調(diào)度方法：該方法使用Kriging代理模型建立云任務(wù)一種有效的有限時(shí)間的資源分配方案與其計(jì)算性能之間存在的近似模型，從而方便地計(jì)算出最優(yōu)的資源調(diào)度策略；而云平臺(tái)所提供的API函數(shù)能夠?qū)υ迫蝿?wù)進(jìn)行動(dòng)態(tài)的資源配給，最終達(dá)到最合理和最高效的資源分配目的。為檢驗(yàn)該方法在云計(jì)算任務(wù)調(diào)度中的效果，本文對(duì)OpenStack平臺(tái)下兩個(gè)工程計(jì)算應(yīng)用的云任務(wù)進(jìn)行調(diào)度測(cè)試；統(tǒng)計(jì)數(shù)據(jù)表明，本文提出的方法可有效應(yīng)用在云計(jì)算環(huán)境下的類似任務(wù)調(diào)度問(wèn)題中。

2 研究背景

2.1 云計(jì)算及任務(wù)調(diào)度問(wèn)題

經(jīng)過(guò)近十年左右的發(fā)展，云計(jì)算領(lǐng)域逐漸形成了以基礎(chǔ)設(shè)施云（IaaS）、平臺(tái)云（PaaS）和軟件云（SaaS）等為代表的平臺(tái)系統(tǒng)，按照虛擬化的不同層次對(duì)外提供服務(wù)[1]。商業(yè)云平臺(tái)如Amazon EC2、Google App Engine、Microsoft Azure、阿里云、百度云等正為全世界范圍內(nèi)的用戶提供各式服務(wù)；而如CloudStack、OpenStack等開源云平臺(tái)的崛起也正在改變著云計(jì)算世界的版圖[2-3]。

任務(wù)調(diào)度問(wèn)題是云計(jì)算領(lǐng)域的資源調(diào)度問(wèn)題之一，可簡(jiǎn)單描述為將用戶的作業(yè)請(qǐng)求（CPU、內(nèi)存、文件等資源的集合）映射到系統(tǒng)的虛擬資源（通常是虛擬機(jī)，VM）上并執(zhí)行的過(guò)程。通常使用一種預(yù)計(jì)完成時(shí)間（ETC）矩陣對(duì)云任務(wù)調(diào)度問(wèn)題進(jìn)行分析：其長(zhǎng)度為云任務(wù)的數(shù)量，寬度為VM數(shù)量，矩陣的元素為云任務(wù)在指定的VM上運(yùn)行的時(shí)間。按任務(wù)之間的相互關(guān)系，云任務(wù)調(diào)度問(wèn)題可分為元調(diào)度問(wèn)題（任務(wù)之間無(wú)依賴關(guān)系）及存在依賴關(guān)系的調(diào)度問(wèn)題[4-5]。本文僅分析元調(diào)度問(wèn)題。

云任務(wù)調(diào)度問(wèn)題的目標(biāo)通常包括響應(yīng)時(shí)間，資源負(fù)載，服務(wù)成本等。顯然，云任務(wù)調(diào)度問(wèn)題是典型的NP難問(wèn)題，使用一個(gè)良好的調(diào)度算法可以極大增加用戶的使用粘度，并提高云系統(tǒng)本身的資源使用效率。然而在復(fù)雜的云應(yīng)用環(huán)境下，特別是對(duì)于大型工程應(yīng)用數(shù)量眾多的云平臺(tái)而言，一個(gè)準(zhǔn)確或有效的ETC通常是很難獲取的，如何能夠使用代理模型分析這類應(yīng)用任務(wù)在不同資源組合下的計(jì)算特征，正在成為一個(gè)重要的新興研究課題[6-7]。

2.2 任務(wù)調(diào)度算法

先來(lái)先服務(wù)（FCFS）算法、短作業(yè)優(yōu)化算法、輪循（RR）算法等傳統(tǒng)操作系統(tǒng)層面的算法是最先應(yīng)用在云任務(wù)調(diào)度問(wèn)題中的算法，其特點(diǎn)是簡(jiǎn)單易行[8-9]。而針對(duì)云任務(wù)調(diào)度問(wèn)題的特殊性，許多新型算法也被廣泛發(fā)展，如Huang提出了元節(jié)點(diǎn)的調(diào)度策略[10]，Lee設(shè)計(jì)了考慮云服務(wù)和其他服務(wù)的成本模型的算法[11]，Garg發(fā)展了以最小碳排放和最大經(jīng)濟(jì)效益為目標(biāo)的多數(shù)據(jù)中心調(diào)度算法等[12]。

同時(shí)，諸如遺傳算法、粒子群算法、蟻群算法等啟發(fā)式智能算法也在云任務(wù)調(diào)度問(wèn)題中得到廣泛應(yīng)用。例如Mezmaz提出基于遺傳算法的混合式算法以獲取最小能量損耗和最小響應(yīng)時(shí)間[13]，Li發(fā)展了負(fù)載平衡的蟻群算法試圖在獲取最小響應(yīng)的同時(shí)平衡整個(gè)系統(tǒng)的負(fù)載[14]，Pandey設(shè)計(jì)了基于粒子群算法的調(diào)度策略，用以同時(shí)考慮任務(wù)計(jì)算成本和數(shù)據(jù)傳輸成本[15]。

2.3 Kriging代理模型

假設(shè)樣本組為X=[x1，x2，…，xn]，對(duì)應(yīng)的響應(yīng)值為y，Kriging模型可構(gòu)建為[16-17]：

該模型包含線性回歸部分和隨機(jī)部分。β為回歸系數(shù)，f(x)為確定性漂移，通常使用x的多項(xiàng)式形式對(duì)整個(gè)設(shè)計(jì)域進(jìn)行全局近似，隨機(jī)函數(shù)z(x)為波動(dòng)，對(duì)整個(gè)設(shè)計(jì)域進(jìn)行局部近似，其均值為0，方差可表示為σ2。

工程領(lǐng)域經(jīng)常使用稱為DACE的開源Matlab優(yōu)化工具箱來(lái)建立樣本與響應(yīng)的Kriging替代函數(shù)模型。使用者可簡(jiǎn)單提供樣本及響應(yīng)值數(shù)據(jù)，并設(shè)定好一個(gè)用來(lái)定義模型建立精確度的θ函數(shù)值，用以創(chuàng)建最基本的Kriging代理模型。

2.4 OpenStack開源云平臺(tái)

OpenStack是由Rackspace和NASA所發(fā)起的開源基礎(chǔ)設(shè)施云平臺(tái)項(xiàng)目，現(xiàn)在已經(jīng)發(fā)展成為包括150多個(gè)商業(yè)公司及2 000多個(gè)研究組織所共同參與的云計(jì)算科研項(xiàng)目。OpenStack通常由負(fù)責(zé)租戶及用戶管理的keystone模塊、鏡像管理的glance模塊、存儲(chǔ)管理的cinder模塊、網(wǎng)絡(luò)管理的quantum模塊和計(jì)算管理的nova模塊等五個(gè)核心模塊組成。OpenStack同時(shí)提供RESTful的編程接口（API），云服務(wù)提供商可根據(jù)自己的需求開發(fā)適合自己的云平臺(tái)，從而為終端用戶提供計(jì)算資源及定制化的服務(wù)[18-19]。如圖1所示。

圖1 OpenStack架構(gòu)

3 基于Kriging代理模型的動(dòng)態(tài)云任務(wù)調(diào)度方法

3.1 調(diào)度的目標(biāo)函數(shù)確立

在某種資源分配下，考慮具有類似圖2所示的資源和時(shí)間的計(jì)算特征的云應(yīng)用：（1）應(yīng)用中有若干近似平穩(wěn)的計(jì)算期（SP），亦即平穩(wěn)期內(nèi)對(duì)資源的使用沒(méi)有較大的變化，平穩(wěn)期之間是過(guò)渡期（TP）；（2）平穩(wěn)期的持續(xù)時(shí)間要遠(yuǎn)大于過(guò)渡期的時(shí)間。

圖2 資源和時(shí)間的計(jì)算特征

通常情況下，以工程計(jì)算為代表的資源密集型應(yīng)用具有上述特點(diǎn)：該類應(yīng)用在某些特定計(jì)算階段對(duì)資源的耗費(fèi)相對(duì)集中，密集程度較高，可抽象為平穩(wěn)期；相應(yīng)的，不同計(jì)算時(shí)期之間的邏輯程序調(diào)整、分析和計(jì)算等過(guò)程，則可抽象為過(guò)渡期。通常情況下，類似應(yīng)用的SP和TP的時(shí)間片設(shè)定可由應(yīng)用開發(fā)人員自行完成，并由云平臺(tái)開發(fā)者針對(duì)云環(huán)境下的特殊情況提供必要的調(diào)整和優(yōu)化解決方案。同時(shí)，對(duì)于不同的資源分配方案，此類應(yīng)用一般呈現(xiàn)如圖3所示的資源和分配的計(jì)算特征：（1）隨著資源分配不斷增長(zhǎng)，資源的實(shí)際使用量不斷增加；（2）存在一個(gè)應(yīng)用可最大利用的資源上限，亦即應(yīng)用所最大需要的資源分配量。

圖3 資源和分配的計(jì)算特征

例如，沒(méi)有并行性的應(yīng)用程序通常只能使用一個(gè)CPU物理核心，一個(gè)32位的應(yīng)用程序通常不能使用超過(guò)4 GB的內(nèi)存。假定對(duì)第i個(gè)資源Pi分配的資源數(shù)量為Pi(s)，而應(yīng)用在該SP中實(shí)際需要的i資源數(shù)量為Pi(n)，Ui為資源的使用率，則該應(yīng)用在第i個(gè)資源上消耗的時(shí)間可近似表示為：

考慮到所有可能的資源數(shù)i=1，2，…，k，k為資源種類的總數(shù)量，則式（2）可表示為：

而資源消耗總量則為：

若要獲取最短的響應(yīng)時(shí)間和最小資源消耗，則T應(yīng)該盡可能的小，C也應(yīng)該盡可能的小，表示為：

考慮到Pi(n)為未知的特定常數(shù)，并且使用加權(quán)求和方法將式（5）和式（6）轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，可得：

使用加權(quán)方式組合式（7）和式（8），可得

式（9）即本文所使用的調(diào)度目標(biāo)函數(shù)，該式可理解為最大化應(yīng)用所真正利用的計(jì)算資源的同時(shí)，減少因?yàn)閼?yīng)用可能達(dá)到如圖3所示的峰值點(diǎn)后所造成的資源浪費(fèi)。

3.2 基于應(yīng)用的抽樣

一般地，抽樣是工程領(lǐng)域?yàn)閷?duì)應(yīng)用進(jìn)行分析使用通用或特定抽樣算法從設(shè)計(jì)變量的設(shè)計(jì)域內(nèi)生成一系列樣本點(diǎn)的過(guò)程。樣本生成之后，作為輸入由特定的分析軟件計(jì)算后獲得其響應(yīng)值（特定的關(guān)鍵數(shù)據(jù)值）。樣本和響應(yīng)均得到之后，則可對(duì)該應(yīng)用從整體層面分析、理解。

就云任務(wù)的調(diào)度問(wèn)題而言，若要分析出應(yīng)用對(duì)于不同資源分配的性能表現(xiàn)，則可定義樣本組為不同的資源數(shù)量組合，即x=[P1(n)，P2(n)，…，Pk(n)]，對(duì)應(yīng)的響應(yīng)可定義為資源的使用率，即y=[U1，U2，…，Uk]。為從理論上對(duì)應(yīng)用的資源使用率和分配值進(jìn)行分析，本文采用如下所述的基于應(yīng)用的抽樣方式：

（1）在每個(gè)SP開始前，云任務(wù)暫停計(jì)算過(guò)程。

（2）保存計(jì)算的上下文到數(shù)據(jù)庫(kù)中并上傳到平臺(tái)后端，如關(guān)鍵變量的值，重要的參數(shù)文件等。

（3）基于用戶定義的資源分配數(shù)量上下限，隨機(jī)生成m個(gè)（通常至少4倍或5倍于設(shè)計(jì)變量的維度，從而保證Kriging替代函數(shù)模型的有效性）樣本組X=[x1，x2，…，xm]，作為資源分配的組合。

（4）平臺(tái)后端通過(guò)API啟動(dòng)具有如上樣本值（資源數(shù)量組合）的虛擬機(jī)樣本實(shí)例。

（5）樣本實(shí)例下載已經(jīng)保存好的計(jì)算上下文到本地，開啟SP計(jì)算較短時(shí)間過(guò)程（可因應(yīng)用和SP的持續(xù)時(shí)間而異，本文采用60秒）。

（6）樣本實(shí)例收集該應(yīng)用在該SP內(nèi)的計(jì)算特征，如CPU和內(nèi)存使用率等，集中發(fā)送到云任務(wù)所在的主機(jī)上作為響應(yīng)組Y=[y1，y2，…，ym]，以供下述資源優(yōu)化過(guò)程所用。

（7）平臺(tái)后端關(guān)閉所有的樣本實(shí)例，并發(fā)送喚醒信號(hào)給暫停的云任務(wù)。

（8）云任務(wù)接收到喚醒信號(hào)，進(jìn)行資源的優(yōu)化過(guò)程。

3.3 云任務(wù)資源的優(yōu)化

通過(guò)抽樣過(guò)程所得到的相關(guān)樣本和響應(yīng)數(shù)據(jù)，云任務(wù)可以使用預(yù)先在其主機(jī)鏡像中內(nèi)置的DACE模塊開啟優(yōu)化過(guò)程，描述為：

（1）基于樣本點(diǎn)（資源的數(shù)量組合X=[x1，x2，…，xm]）和響應(yīng)值（資源的使用率Y=[y1，y2，…，ym]），使用DACE工具箱建立k個(gè)Kriging代理模型，從而獲得所有k種資源對(duì)該應(yīng)用任務(wù)的影響情況模型。

（2）使用優(yōu)化算法計(jì)算（本文使用基于梯度的序列二次規(guī)劃方法）對(duì)應(yīng)于應(yīng)用任務(wù)，該SP的最優(yōu)值xopt，優(yōu)化的目標(biāo)函數(shù)按3.1節(jié)的式（9）進(jìn)行定義。

（3）上述最優(yōu)值即為云任務(wù)該SP下最佳的資源調(diào)度組合，該組合將作為后續(xù)云任務(wù)資源重新調(diào)度時(shí)的輸入值，因此作為數(shù)據(jù)上傳到平臺(tái)后端保存。

優(yōu)化過(guò)程包含三個(gè)子任務(wù)過(guò)程：建立Kriging替代函數(shù)過(guò)程、優(yōu)化計(jì)算過(guò)程、結(jié)果上傳過(guò)程。DACE模塊具有強(qiáng)大的矩陣運(yùn)算處理功能，因此前兩者的時(shí)間消耗非常低；平臺(tái)提供的強(qiáng)大API支持可以保證最后一個(gè)子任務(wù)在較短的時(shí)間內(nèi)完成。因此，資源優(yōu)化過(guò)程一般只需要20～30 s的計(jì)算時(shí)間，遠(yuǎn)小于云任務(wù)本身所持續(xù)的時(shí)間，可以忽略不計(jì)。

3.4 云任務(wù)的資源重新調(diào)度

xopt獲取之后，平臺(tái)后端即可相應(yīng)地做出云任務(wù)資源的重新分配，從技術(shù)層面上講，即是對(duì)運(yùn)行著的云任務(wù)主機(jī)重新分配計(jì)算資源的過(guò)程。一般地，這種動(dòng)態(tài)的主機(jī)資源分配過(guò)程需要虛擬機(jī)管理軟件的支持，從而保證主機(jī)在短暫夯機(jī)（或掛起）后重新啟動(dòng)時(shí)，數(shù)據(jù)的正確和一致性。比較流行的開源云平臺(tái)通常已經(jīng)將常用虛擬機(jī)管理軟件的類似API進(jìn)行了功能包裝、增強(qiáng)，并提供給云服務(wù)商方便地使用。借助云平臺(tái)的特定API函數(shù)，可以對(duì)云任務(wù)的資源分配進(jìn)行動(dòng)態(tài)的調(diào)整，亦即“resize”的過(guò)程。本文建立的是基于OpenStack開源云平臺(tái)的測(cè)試環(huán)境，OpenStack平臺(tái)對(duì)主機(jī)動(dòng)態(tài)資源配置的API函數(shù)是nova的resize命令，其主要參數(shù)是主機(jī)的編號(hào)和其重新調(diào)度后的資源組合編號(hào)（flavor id），而調(diào)整結(jié)束后需要手動(dòng)（或者由系統(tǒng)定義一個(gè)時(shí)間閥）確認(rèn)調(diào)整的完成，整個(gè)過(guò)程需要事先使用驗(yàn)證信息（租戶名稱tenant name、用戶名user name等）獲得keystone模塊的操作令牌（token）。基于這些條件，該過(guò)程可簡(jiǎn)單表述如下：

（1）使用諸如tenant name，user name等的身份信息與keystone模塊通信，獲取操作所需要的令牌（token）。

（2）檢測(cè)是否有如優(yōu)化解xopt的資源組合存在（flavor）；如果不存在，則使用nova模塊的flavor添加命令增加該組合，并最終獲得該資源組合編號(hào)（id）。

（3）使用nova模塊API的resize指令，對(duì)該云任務(wù)所在主機(jī)的資源按得到的資源組合編號(hào)進(jìn)行重新分派。

（4）當(dāng)resize操作結(jié)束后（OpenStack平臺(tái)下主機(jī)將呈現(xiàn)“VERIFY_RESIZE”狀態(tài)），使用nova模塊的對(duì)應(yīng)于resize指令的確定（confirm）命令完成該重新調(diào)度操作。

（5）平臺(tái)后端喚醒主機(jī)上的云任務(wù)，云任務(wù)繼續(xù)計(jì)算任務(wù)，使用其新配給的資源方案xopt，開啟接下來(lái)的SP過(guò)程。

重新調(diào)度（resize）操作的執(zhí)行時(shí)間可因云平臺(tái)硬件及軟件（虛擬機(jī)管理軟件等）性能的不同而有所差異，通常來(lái)說(shuō)可從30秒到幾分鐘不等。就所建立的測(cè)試平臺(tái)而言，在使用了NFS文件系統(tǒng)和高性能的固態(tài)硬盤運(yùn)行應(yīng)用實(shí)例后，該過(guò)程可在30秒左右，與云任務(wù)本身而言，這個(gè)過(guò)程的時(shí)間消耗也同樣可以忽略不計(jì)。

3.5 運(yùn)行機(jī)制

為更好地描述本文所提出的動(dòng)態(tài)調(diào)度方法，本節(jié)對(duì)包含用戶、平臺(tái)后端和任務(wù)主機(jī)（由虛擬機(jī)生成的云任務(wù)計(jì)算載體）三個(gè)實(shí)體的運(yùn)行機(jī)制進(jìn)行分析和描述，如圖4所示。

關(guān)鍵步驟說(shuō)明：

（1）用戶通過(guò)平臺(tái)門戶申請(qǐng)要運(yùn)行某個(gè)應(yīng)用的任務(wù)并提交相關(guān)的作業(yè)信息，諸如初始資源方案、調(diào)度模式（初始分配、動(dòng)態(tài)配置）等，并定義其任務(wù)計(jì)算資源的上下限。

（2）平臺(tái)后端按要求完成對(duì)應(yīng)任務(wù)的初始化工作（數(shù)據(jù)庫(kù)操作、日志記錄、權(quán)限檢測(cè)等），返回該任務(wù)運(yùn)行的任務(wù)主機(jī)編號(hào)給用戶。

（3）用戶向任務(wù)主機(jī)提交運(yùn)算任務(wù)請(qǐng)求。

（4）平臺(tái)后端按初始資源對(duì)任務(wù)主機(jī)進(jìn)行調(diào)度，啟動(dòng)相應(yīng)的虛擬機(jī)主機(jī)。

（5）任務(wù)主機(jī)按應(yīng)用要求配置其計(jì)算環(huán)境和完成相應(yīng)的初始化工作（主機(jī)名定義、IP地址分配等）。

（6）在新SP即將到來(lái)之前，使用3.2節(jié)的方法對(duì)該應(yīng)用進(jìn)行抽樣。

（7）抽樣結(jié)束后，利用3.3節(jié)的方法對(duì)應(yīng)用任務(wù)該SP下的計(jì)算資源配置進(jìn)行優(yōu)化計(jì)算。

（8）優(yōu)化計(jì)算完成后，平臺(tái)后端按照優(yōu)化后的資源配比使用3.4節(jié)的方法對(duì)任務(wù)主機(jī)重新調(diào)度。

（9）主機(jī)上的云任務(wù)按應(yīng)用的要求完成任務(wù)的該SP階段計(jì)算。

（10）沒(méi)有新的SP且所有計(jì)算結(jié)束后，平臺(tái)后端將對(duì)該任務(wù)主機(jī)進(jìn)行銷毀，回收其占用的計(jì)算資源。

圖4 運(yùn)行機(jī)制

4 測(cè)試算例

我們開發(fā)了包括汽輪機(jī)基礎(chǔ)優(yōu)化和模具分析的兩個(gè)工程計(jì)算應(yīng)用，用來(lái)測(cè)試本文所提出的動(dòng)態(tài)任務(wù)調(diào)度方法。兩個(gè)應(yīng)用均具有第三章所描述的計(jì)算特征，并分別有2個(gè)和4個(gè)SP，且它們的任務(wù)主機(jī)初始化時(shí)間均約為12分鐘。鑒于過(guò)渡期的時(shí)間較短，因此在時(shí)間耗費(fèi)統(tǒng)計(jì)時(shí)與相鄰的上一個(gè)SP合并，方便分析數(shù)據(jù)。簡(jiǎn)單起見，這里僅對(duì)包括虛擬CPU和虛擬MEM的兩類計(jì)算資源進(jìn)行調(diào)度測(cè)試。

兩個(gè)測(cè)試應(yīng)用均采用[1，2]和[6，12]的資源分配上下限（分別為虛擬CPU和虛擬MEM），且應(yīng)用任務(wù)的初始資源使用方案均定義為[3，6]。任務(wù)執(zhí)行時(shí)的抽樣樣本點(diǎn)數(shù)量設(shè)定為8個(gè)。

4.1 測(cè)試算例一

測(cè)試算例一具有2個(gè)SP，并有約12分鐘的初始化期。該算例調(diào)度情況如圖5和圖6所示，每單位時(shí)間片代表3分鐘（180 s）。

圖5 算例一的虛擬CPU調(diào)度

算例中云任務(wù)的SP時(shí)間片始終范圍分別為#1 SP（5～54），（5～46）和#2 SP（55～126），（47，112）（初始分配在前）。對(duì)比于初始分配的資源組合[3，6]，采取3.1節(jié)所描述的目標(biāo)函數(shù)進(jìn)行動(dòng)態(tài)調(diào)度后，該應(yīng)用任務(wù)優(yōu)化后的兩個(gè)SP資源組合分別為[3，7]和[4，7]，在大幅度減少任務(wù)的響應(yīng)時(shí)間的同時(shí)（14個(gè)時(shí)間片），并未增加過(guò)多的資源消耗。

圖6 算例一的虛擬MEM調(diào)度

4.2 測(cè)試算例二

測(cè)試算例二具有4個(gè)SP，并同樣具有約12分鐘的初始化期。該算例的調(diào)度情況如圖7和圖8所示，每個(gè)單位時(shí)間片的長(zhǎng)度也為3分鐘（180 s）。

圖7 算例二的虛擬CPU調(diào)度

圖8 算例二的虛擬MEM調(diào)度

算例中云任務(wù)的SP時(shí)間片始終范圍分別為#1 SP（5～26），（5～27）、#2 SP（27～62），（28，65）、#3 SP（63，92），（66，90）和#4 SP（93，161），（91，154）（初始分配在前）。從圖7和圖8中可以看出，使用第3章的方法進(jìn)行動(dòng)態(tài)任務(wù)調(diào)度后，該任務(wù)優(yōu)化后的SP資源配給分別為[2，7]，[3，5]，[1，8]和[4，6]。從某些 SP上看，初始分配方案具有更高的資源數(shù)組合，會(huì)有一些響應(yīng)時(shí)間上的優(yōu)勢(shì)（如#1 SP）；不過(guò)從整體上看，優(yōu)化過(guò)后的調(diào)度方案，整體資源的分配更合理：在耗費(fèi)了[453，959]計(jì)算資源的前提下，僅使用了154個(gè)時(shí)間片即完成了整個(gè)任務(wù)；相應(yīng)的，初始分配策略使用了共計(jì)[483，966]計(jì)算資源，卻使用了更多的161個(gè)時(shí)間片完成該任務(wù)。

4.3 結(jié)果分析與討論

一般的，云應(yīng)用任務(wù)的響應(yīng)時(shí)間和資源耗費(fèi)是兩個(gè)矛盾的因素：較快的響應(yīng)時(shí)間通常意味著更多的計(jì)算資源投入（如算例一）。然而，如果能夠合理地分析出云應(yīng)用的計(jì)算特征，獲取出其在不同資源配比下的性能表現(xiàn)，就能夠作出合理的資源調(diào)度：在投入了較少的資源時(shí)，反而能夠得到較快的響應(yīng)時(shí)間（如算例二）。工程算例復(fù)雜多樣，對(duì)不同資源的需求也不盡相同，若能使用Kriging替代函數(shù)模型獲取這些應(yīng)用的特定計(jì)算特征并優(yōu)化計(jì)算得到其最優(yōu)資源分配，將在加快這些應(yīng)用任務(wù)的執(zhí)行速度的同時(shí)，降低任務(wù)消耗的資源總量。

本文第3章所發(fā)展的調(diào)度目標(biāo)函數(shù)，忽略了云應(yīng)用不同階段（SP和TP等）有可能出現(xiàn)的不同資源消耗權(quán)重問(wèn)題，而選擇相同的加權(quán)因子整合它們；同時(shí)對(duì)于響應(yīng)時(shí)間和資源消耗，也采取了相同的加權(quán)系數(shù)進(jìn)行整合。在未來(lái)的生產(chǎn)環(huán)境中，通過(guò)云應(yīng)用開發(fā)人員和用戶共同設(shè)計(jì)符合特定要求的調(diào)度函數(shù)，并使用類似本文第3章的方法調(diào)度，將有望得到一種“所付即所需”的云服務(wù)體驗(yàn)。

5 結(jié)束語(yǔ)

云計(jì)算為用戶提供了一種以服務(wù)作為形式使用計(jì)算機(jī)軟硬件資源的新型途徑。而數(shù)據(jù)中心作為云平臺(tái)的核心結(jié)構(gòu)，必須能夠及時(shí)和高效地對(duì)用戶提交的任務(wù)進(jìn)行調(diào)度執(zhí)行。本文發(fā)展了一種基于Kriging代理模型的方法，可應(yīng)用在云任務(wù)的動(dòng)態(tài)調(diào)度問(wèn)題中。該方法將Kriging代理函數(shù)模型建立在云任務(wù)的資源配給和其對(duì)應(yīng)的計(jì)算性能特征之上，并按照設(shè)定好的目標(biāo)函數(shù)進(jìn)一步計(jì)算得到其最佳的優(yōu)化資源分配方案。通過(guò)對(duì)汽輪機(jī)基礎(chǔ)優(yōu)化和模具設(shè)計(jì)兩個(gè)工程計(jì)算應(yīng)用組成的測(cè)試算例分析可知，本文所發(fā)展的方法可有效應(yīng)用在云任務(wù)的動(dòng)態(tài)調(diào)度問(wèn)題中：在盡可能得到較快的響應(yīng)時(shí)間的同時(shí)，減少任務(wù)所消耗的計(jì)算資源總量。

Kriging代理模型方案僅是眾多的替代函數(shù)模型中使用較為廣泛的一種，其他的如神經(jīng)網(wǎng)絡(luò)也可以類比地遷移到該問(wèn)題當(dāng)中；本文所設(shè)計(jì)的優(yōu)化目標(biāo)函數(shù)，是基于云任務(wù)特別是資源密集型的工程應(yīng)用的共性，并按照若干假設(shè)而提出的，可在實(shí)際使用時(shí)作出必要的修正；適應(yīng)于求解代理模型的優(yōu)化算法也有很多，序列二次規(guī)劃只是常用的基于梯度的一種，使用不同的優(yōu)化算法，最終的優(yōu)化解也不盡相同。同時(shí)，本文所提出的動(dòng)態(tài)調(diào)度方法，是從云任務(wù)相對(duì)微觀的資源層面進(jìn)行分析和優(yōu)化，從而得出其有針對(duì)性的資源解決方案。類似的解決思路也可以應(yīng)用在宏觀層面：從全局的高度去分析云任務(wù)，勢(shì)必也將對(duì)云任務(wù)的資源調(diào)度產(chǎn)生同樣積極的影響。

[1]張建勛，古志民，鄭超.云計(jì)算研究進(jìn)展綜述[J].計(jì)算機(jī)應(yīng)用研究，2010，27（2）：429-433.

[2]Bist M，Wariya M，Agarwal A.Comparing delta，open stack and Xen Cloud Platforms：A survey on open source IaaS[C].Ghaziabad，2013.

[3]von Laszewski G，Diaz J，F(xiàn)ugang W，et al.Comparison of multiple cloud frameworks[C].Honolulu，HI，2012.

[4]T Ograph B，Morgens Y R.Cloud computing[J].Communications of the ACM，2008，51（7）.

[5]Zhong H，Tao K，Zhang X.An approach to optimized resource scheduling algorithm for open-source cloud systems[C].2010.

[6]朱宗斌，杜中軍.基于改進(jìn)GA的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（5）：77-80.

[7]史恒亮.云計(jì)算任務(wù)調(diào)度研究[D].南京：南京理工大學(xué)，2012.

[8]Singh A，Malhotra M.A comparative analysis of resource scheduling algorithms in cloud computing[J].American Journal of Computer Science and Engineering Survey，2013，1（1）：14-32.

[9]Bhattacharya A A，Culler D，F(xiàn)riedman E，et al.Hierarchical scheduling for diverse datacenter workloads[C].ACM，2013.

[10]Huang Y，Bessis N，Norrington P，et al.Exploring decentralized dynamic scheduling for grids and clouds using the community-aware scheduling algorithm[J].Future Generation Computer Systems，2013，29（1）：402-415.

[11]Lee Y C，Wang C，Zomaya A Y，et al.Profit-driven scheduling for cloud services with data access awareness[J].Journal of Parallel and Distributed Computing，2012，72（4）：591-602.

[12]Garg S K，Yeo C S，Anandasivam A，et al.Environmentconscious scheduling of HPC applications on distributed cloud-oriented data centers[J].Journal of Parallel and Distributed Computing，2011，71（6）：732-749.

[13]Mezmaz M，Melab N，Kessaci Y，et al.A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems[J].Journal of Parallel and Distributed Computing，2011，71（11）：1497-1508.

[14]Li K，Xu G，Zhao G，et al.Cloud task scheduling based on load balancing ant colony optimization[J].IEEE，2011.

[15]Pandey S，Wu L，Guru S M，et al.A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[J].IEEE，2010.

[16]Ryu J，Kim M，Cha K，et al.Kriging interpolation methods in geostatistics and DACE model[J].KSME International Journal，2002，16（5）：619-632.

[17]高月華，張崎，王希誠(chéng).基于Kriging模型的汽輪機(jī)基礎(chǔ)動(dòng)力優(yōu)化設(shè)計(jì)[J].計(jì)算力學(xué)學(xué)報(bào)，2008，25（5）：610-615.

[18]Bist M，Wariya M，Agarwal A.Comparing delta，open stack and Xen cloud platforms：A survey on open source IaaS[C].Ghaziabad，2013.

[19]Schmidberger M，Schmidberger M.Software engineering as a service for HPC[C].Munich：2012.