基于資源延遲感知的云計(jì)算實(shí)時(shí)任務(wù)調(diào)度仿真

吳譽(yù)蘭，黃 衛(wèi)

(南昌航空大學(xué)科技學(xué)院，江西 南昌 332020)

1 引言

云計(jì)算利用網(wǎng)絡(luò)將龐大的計(jì)算處理任務(wù)分割成多個(gè)不同的子任務(wù)，再通過(guò)服務(wù)器搜索分析，最終反饋給用戶，提供資源的網(wǎng)格被稱為“云”[1]。云計(jì)算具有計(jì)算速度快、范圍廣的特點(diǎn)，在各個(gè)領(lǐng)域都得到了廣泛的應(yīng)用，因此計(jì)算服務(wù)需求急劇增加。為了能夠滿足這些需求，在云計(jì)算數(shù)據(jù)中心部署了更多的主機(jī)。據(jù)資料統(tǒng)計(jì)，一個(gè)數(shù)據(jù)中心的主機(jī)數(shù)量可以達(dá)到幾萬(wàn)，甚至幾十萬(wàn)臺(tái)。這些主機(jī)在運(yùn)行時(shí)，云服務(wù)系統(tǒng)會(huì)消耗大量電能，高能耗不僅會(huì)提高工作成本，同時(shí)也會(huì)帶來(lái)一定的環(huán)境污染。如何解決云計(jì)算數(shù)據(jù)中心的高能耗問(wèn)題已經(jīng)成為當(dāng)前學(xué)術(shù)界的研究熱點(diǎn)[2]。

雖然目前針對(duì)云計(jì)算任務(wù)調(diào)度和資源分配進(jìn)行了一定的研究，但是并未取得顯著的研究成果。云計(jì)算是一種收費(fèi)計(jì)算，根據(jù)云的使用時(shí)間來(lái)判定收取費(fèi)用額度，因此當(dāng)前所研究的資源調(diào)度算法的關(guān)注點(diǎn)多是在縮短任務(wù)時(shí)間上。文獻(xiàn)[3]提出一類柔性流水調(diào)度與平行機(jī)調(diào)度相結(jié)合的兩階段流水調(diào)度模型，模型中第1階段有1臺(tái)機(jī)器，第2階段有m臺(tái)同構(gòu)并行機(jī)，每個(gè)任務(wù)在第2階段需要size_i臺(tái)機(jī)器同時(shí)并行執(zhí)行，目標(biāo)是所有任務(wù)都完成的完工時(shí)間最小化。詳細(xì)分析了前人近似算法基本過(guò)程，給出該算法近似比分析的局限性。給出近似比為3的算法，摒棄了前人給出的約束條件。研究了當(dāng)?shù)?階段機(jī)器數(shù)為2和3時(shí)的兩種特定情況，采用列表調(diào)度思想完成任務(wù)調(diào)度，但此方法存在調(diào)度時(shí)間長(zhǎng)的問(wèn)題。文獻(xiàn)[4]提出了基于反向自適應(yīng)量子粒子群算法(RAQPSO)的云計(jì)算任務(wù)資源調(diào)度方法。通過(guò)調(diào)整慣性權(quán)值參數(shù)并加入反向?qū)W習(xí)算子來(lái)提高算法的全局搜索能力。采用自適應(yīng)機(jī)制，將適應(yīng)度函數(shù)的變化程度作為慣性權(quán)值的更新因子，從而使粒子不易陷入局部最優(yōu)。加入粒子反向?qū)W習(xí)算子，加強(qiáng)了粒子全局搜索能力。經(jīng)過(guò)實(shí)驗(yàn)表明，RAQPSO算法節(jié)約任務(wù)完成時(shí)間，但資源利用率較低。文獻(xiàn)[5]提出基于蜂群算法的云計(jì)算任務(wù)資源調(diào)度方法。引入高斯變異和自適應(yīng)因子改進(jìn)人工蜂群算法，兼顧算法前期全局搜索能力和后期局部細(xì)致搜索。引入自適應(yīng)交叉概率改進(jìn)差分進(jìn)化算法，提出差分進(jìn)化人工蜂群算法。兩種改進(jìn)算法并行尋優(yōu)并及時(shí)交流最優(yōu)解及位置信息，使兩算法能夠快速靠近最優(yōu)解，減少算法迭代次數(shù)，提高算法收斂速度和精度，但是該方法在調(diào)度過(guò)程中耗時(shí)較長(zhǎng)。

鑒于此，基于資源延遲感知提出了一種新的實(shí)時(shí)任務(wù)調(diào)度方法，根據(jù)感知的機(jī)器啟動(dòng)時(shí)間來(lái)提高云計(jì)算數(shù)據(jù)中心保障實(shí)時(shí)任務(wù)調(diào)度的實(shí)效性，較低云計(jì)算能耗。

2 云計(jì)算的實(shí)時(shí)任務(wù)調(diào)度問(wèn)題

云計(jì)算以分布式并行處理的方式處理大規(guī)模計(jì)算任務(wù)，將一個(gè)大任務(wù)分解成多個(gè)小任務(wù)。在分析任務(wù)信息后，將不同的任務(wù)分配到不同的節(jié)點(diǎn)上，所有子任務(wù)的處理結(jié)果即是大任務(wù)的處理結(jié)果，這一結(jié)果最終會(huì)反饋給用戶[6]。云計(jì)算使用的編程模型通常為Map/Reduce編程模型，該模型運(yùn)行機(jī)制如下圖1所示：

圖1 Map/Reduce編程模型運(yùn)行機(jī)制

分析圖1可知，一個(gè)并行處理任務(wù)包括多個(gè)Map任務(wù)和多個(gè)Reduce任務(wù)，運(yùn)行機(jī)制將任務(wù)執(zhí)行階段分為兩個(gè)結(jié)算，分別是Map階段和Reduce階段[7]。

Map階段：計(jì)算分配到自身的數(shù)據(jù)，根據(jù)Map輸出的key值，將所有得到的結(jié)果映射到對(duì)應(yīng)的Reduce任務(wù)中；

Reduce階段：聚集處理Map階段傳輸?shù)臄?shù)據(jù)，得到最終的輸出結(jié)果。

在云計(jì)算環(huán)境中，有多種不同的服務(wù)類型，不同服務(wù)類型的資源使用指標(biāo)、負(fù)載類型指標(biāo)和性能評(píng)價(jià)指標(biāo)有很大的不同，因此服務(wù)類型會(huì)直接影響資源調(diào)度效果[8]。云計(jì)算服務(wù)包括數(shù)據(jù)計(jì)算密集型服務(wù)和交互密集型網(wǎng)絡(luò)處理服務(wù)兩種，研究的資源調(diào)度方法主要是針對(duì)第一種服務(wù)類型。

在進(jìn)行資源調(diào)度時(shí)，將資源自身因素考慮在內(nèi)，通過(guò)劃分資源等級(jí)確保短時(shí)間內(nèi)平衡資源。分類云計(jì)算中的資源后，通過(guò)可標(biāo)識(shí)資源自身屬性的資源可見(jiàn)度β這一指標(biāo)判斷云計(jì)算資源的計(jì)算能力和通訊能力，β的計(jì)算公式如式(1)所示

β=a×m×p+b×D+c×B

(1)

式(1)中，m代表CPU的個(gè)數(shù)，p代表云計(jì)算環(huán)境下CPU的處理能力，a代表資源計(jì)算能力在資源可見(jiàn)度中的比重，取值為40%，D代表云計(jì)算環(huán)境下的磁盤(pán)容量，單位為MB，b代表磁盤(pán)容量在資源可見(jiàn)度中的比重，取值為20%，B代表云計(jì)算資源所在環(huán)境的網(wǎng)絡(luò)帶寬，單位為Mb/s，c代表網(wǎng)絡(luò)帶寬在資源可見(jiàn)度中的比重，取值為40%。

根據(jù)式(1)計(jì)算資源可見(jiàn)度β，從而實(shí)現(xiàn)資源等級(jí)分類，當(dāng)β≥35%時(shí)，定位為1級(jí)；當(dāng)20%≤β≤35%時(shí)，資源定位為2級(jí)；當(dāng)10%≤β≤20%時(shí)，資源定位為3級(jí)；當(dāng)β≤10%時(shí)，資源定位為4級(jí)[9]。

傳統(tǒng)的云計(jì)算實(shí)時(shí)任務(wù)調(diào)度算法會(huì)將所有的任務(wù)都集中在一個(gè)節(jié)點(diǎn)上運(yùn)行，這樣就會(huì)導(dǎo)致該節(jié)點(diǎn)負(fù)載過(guò)重，單個(gè)節(jié)點(diǎn)資源利用率高達(dá)100%，而其它資源閑置，嚴(yán)重影響資源負(fù)載[10]。此次研究通過(guò)改進(jìn)傳統(tǒng)算法缺陷，平衡擁塞和閑置的資源，從而達(dá)到資源平衡。

3 基于資源延遲感知的云計(jì)算實(shí)時(shí)任務(wù)調(diào)度

3.1 調(diào)度框架

設(shè)定虛擬云服務(wù)系統(tǒng)的主機(jī)集合為H，內(nèi)部的主機(jī)用h表示，則有

H={h1，h2，……，hm}

(2)

式(2)中，m代表主機(jī)的數(shù)量，所有的主機(jī)共同組成硬件平臺(tái)，在分析硬件平臺(tái)性能時(shí)，要判斷主機(jī)中最大的CPU頻率(MHz)，內(nèi)存(GB)、帶寬(Mb/s)和最大功耗(W)。

調(diào)度框架中的調(diào)度層由滾動(dòng)窗口來(lái)分析新的任務(wù)，并判斷等待的任務(wù)狀態(tài)；由資源監(jiān)控器監(jiān)控云計(jì)算環(huán)境下資源調(diào)度工作狀態(tài)，所有的監(jiān)控信息都會(huì)反饋到資源底層，從而使資源底層獲得豐富的信息；任務(wù)調(diào)度分析器會(huì)將滾動(dòng)窗口中的任務(wù)傳到虛擬機(jī)上；如果云計(jì)算數(shù)據(jù)中心的負(fù)載出現(xiàn)變化，資源調(diào)配器會(huì)以動(dòng)態(tài)的方式伸縮資源，每一個(gè)虛擬機(jī)都會(huì)放置一個(gè)正在執(zhí)行的任務(wù)[11]。

3.2 資源延遲感知的云計(jì)算實(shí)時(shí)任務(wù)調(diào)度模型

用戶提交到云服務(wù)系統(tǒng)中的應(yīng)用具有動(dòng)態(tài)性和隨機(jī)性，因此研究的任務(wù)調(diào)度算法是針對(duì)實(shí)時(shí)、非周期性的獨(dú)立任務(wù)開(kāi)展的。任務(wù)集設(shè)定為T(mén)，則有T={t1，t2，……，tm}，每個(gè)子任務(wù)都是由到達(dá)時(shí)間、任務(wù)長(zhǎng)度和截止時(shí)間來(lái)決定。由于虛擬機(jī)CPU處理能力存在異構(gòu)性，則任務(wù)ti在虛擬機(jī)上的執(zhí)行時(shí)間可以用式(3)來(lái)表示

(3)

(4)

式(4)中，Vi表示主機(jī)CPU的工作電壓，fi表示主機(jī)CPU的工作頻率，由式(4)可知，活躍能耗與主機(jī)CPU工作電壓的平方和工作頻率成正比[12]。

CPU的工作電壓和工作頻率二者呈現(xiàn)線性關(guān)系，隨著工作頻率的增加，工作電壓也在增加，因此主機(jī)的活躍功率可以只通過(guò)工作頻率來(lái)表示，如式(5)

(5)

(6)

主機(jī)hj活躍能耗計(jì)算式(7)

(7)

根據(jù)主機(jī)的活躍能耗計(jì)算公式和空閑能耗計(jì)算公式，得到整個(gè)主機(jī)CPU消耗功耗計(jì)算公式，如式(8)所示

(8)

整合上述公式，得到主機(jī)CPU消耗功耗計(jì)算公式為

(9)

式(9)中，設(shè)定在執(zhí)行任務(wù)集合的起始時(shí)刻為st，結(jié)束時(shí)刻為et，則處理任務(wù)集T的主機(jī)總能耗計(jì)算式(10)為

(10)

則處理云數(shù)據(jù)m臺(tái)主機(jī)消耗的總能耗計(jì)算公式可以表示為

(11)

在不同的約束條件下，使用的調(diào)度模型不同，調(diào)度方式也不同。通過(guò)不同的調(diào)度方法來(lái)確保任務(wù)能夠在短時(shí)間內(nèi)最大程度地完成，減少能量損耗。調(diào)度模型如式(12)所示

(12)

式(12)中，xi，jk代表任務(wù)與虛擬機(jī)之間的映射關(guān)系，如果任務(wù)能夠順利地映射到虛擬機(jī)上，則xi，jk=1；如果任務(wù)不能夠順利地映射到虛擬機(jī)上，則xi，jk=0。

調(diào)度過(guò)程中，所有的任務(wù)需在截止時(shí)間之內(nèi)完成，才能確保服務(wù)質(zhì)量滿足用戶要求。所有的任務(wù)都是不可分割的。1臺(tái)虛擬機(jī)可以執(zhí)行多個(gè)任務(wù)，但是1個(gè)任務(wù)不可以在2臺(tái)或2臺(tái)以上虛擬機(jī)上執(zhí)行，在整個(gè)調(diào)度過(guò)程中，主機(jī)分配給虛擬機(jī)的CPU能力、內(nèi)存和帶寬都不能超過(guò)自身的資源能力。至此，完成云計(jì)算實(shí)時(shí)任務(wù)調(diào)度模型的構(gòu)建。

3.3 資源延遲感知的云計(jì)算實(shí)時(shí)任務(wù)調(diào)度過(guò)程

當(dāng)活躍主機(jī)剩余的CPU資源超過(guò)應(yīng)急虛擬機(jī)的資源需求，就要將主機(jī)頻率增加。調(diào)度過(guò)程圖示如圖2所示。

圖2 資源延遲感知的云計(jì)算實(shí)時(shí)任務(wù)調(diào)度過(guò)程

分析圖2可知，在應(yīng)急虛擬機(jī)未得到任務(wù)時(shí)，虛擬機(jī)的工作狀態(tài)為空閑狀態(tài)，占用的CPU資源較少，主機(jī)內(nèi)部擁有充足的剩余CPU資源，當(dāng)應(yīng)急虛擬機(jī)得到任務(wù)后，主機(jī)頻率會(huì)迅速增大，確保能夠?yàn)閼?yīng)急虛擬機(jī)提供足夠的CPU資源，一旦任務(wù)完成，應(yīng)急虛擬機(jī)就會(huì)釋放資源。由此可知，當(dāng)主機(jī)能夠擁有充分的空閑資源，被創(chuàng)建的新虛擬機(jī)消耗的時(shí)間開(kāi)銷就會(huì)很短，實(shí)時(shí)任務(wù)延遲時(shí)間也會(huì)對(duì)應(yīng)縮短，系統(tǒng)的任務(wù)時(shí)效性執(zhí)行能力更強(qiáng)。

上述調(diào)度方法僅限于主機(jī)空閑狀態(tài)，如果主機(jī)上存在正在執(zhí)行的虛擬機(jī)任務(wù)，或者是在等待執(zhí)行任務(wù)，主機(jī)就要將能夠忍受延遲的資源轉(zhuǎn)移到應(yīng)急虛擬機(jī)，由應(yīng)急虛擬機(jī)完成任務(wù)后釋放資源，工作過(guò)程如圖3所示。

圖3 特殊條件下云計(jì)算實(shí)時(shí)任務(wù)調(diào)度過(guò)程

分析圖3可知，主機(jī)的CPU內(nèi)部資源絕大部分都分給了兩個(gè)虛擬機(jī)。當(dāng)應(yīng)急虛擬機(jī)得到緊急任務(wù)時(shí)，主機(jī)內(nèi)部的資源并不能滿足應(yīng)急虛擬機(jī)的要求。所以要將其它虛擬機(jī)的資源調(diào)度出來(lái)，使應(yīng)急虛擬機(jī)能夠迅速執(zhí)行任務(wù)。

4 仿真與分析

為驗(yàn)證本文研究的云計(jì)算任務(wù)調(diào)度方法性能優(yōu)劣，設(shè)計(jì)一次仿真。實(shí)驗(yàn)環(huán)境為MATLAB環(huán)境，操作系統(tǒng)為Windows10，主機(jī)頻率為3.21GHz。利用文獻(xiàn)[4]提出的基于反向自適應(yīng)量子粒子群算法的云計(jì)算任務(wù)調(diào)度方法和文獻(xiàn)[5]方法提出的基于蜂群算法的云計(jì)算任務(wù)調(diào)度方法作為本次實(shí)驗(yàn)對(duì)照組，與研究方法進(jìn)行性能對(duì)比。實(shí)驗(yàn)測(cè)試迭代次數(shù)為140次，實(shí)驗(yàn)設(shè)定在云計(jì)算任務(wù)數(shù)分別為50種、100種、200種這三種情況下對(duì)比不同方法的云計(jì)算任務(wù)調(diào)度耗時(shí)和資源利用率兩個(gè)指標(biāo)。具體實(shí)驗(yàn)結(jié)果以及分析如下：

4.1 不同方法下云計(jì)算任務(wù)調(diào)度耗時(shí)對(duì)比

為驗(yàn)證論文方法的時(shí)間成本性能，進(jìn)行一次云計(jì)算任務(wù)耗時(shí)對(duì)比實(shí)驗(yàn)。得到的仿真結(jié)果如圖4所示。

圖4 不同任務(wù)種類下三種方法耗時(shí)對(duì)比

分析圖4實(shí)驗(yàn)結(jié)果可知，當(dāng)云計(jì)算任務(wù)種類數(shù)為50時(shí)，在前期迭代過(guò)程中，文獻(xiàn)[4]、文獻(xiàn)[5]方法和研究方法調(diào)度任務(wù)完成時(shí)間相差較小，在迭代次數(shù)到達(dá)40次之后任務(wù)完成時(shí)間趨于穩(wěn)定。但是從總體來(lái)看，隨著迭代更新次數(shù)的增加，研究方法所用時(shí)間小于文獻(xiàn)[4]、文獻(xiàn)[5]方法，完成時(shí)間為100s。當(dāng)任務(wù)增大到100種時(shí)，文獻(xiàn)[4]、文獻(xiàn)[5]方法和研究方法任務(wù)完成時(shí)間差距逐漸加大，文獻(xiàn)[4]方法調(diào)度任務(wù)完成時(shí)間最高，當(dāng)?shù)螖?shù)為140個(gè)時(shí)完成時(shí)間為139s，文獻(xiàn)[5]方法次之，當(dāng)?shù)螖?shù)為140個(gè)時(shí)完成時(shí)間為118s，研究方法完成時(shí)間最少，當(dāng)?shù)螖?shù)為140個(gè)時(shí)完成時(shí)間為80s，此時(shí)研究方法調(diào)度任務(wù)完成時(shí)間對(duì)比兩種傳統(tǒng)方法，其優(yōu)勢(shì)逐漸凸顯。隨著任務(wù)量增大，三種方法花費(fèi)的調(diào)度時(shí)間相差越來(lái)越大，當(dāng)任務(wù)種類數(shù)增大到200時(shí)，三種任務(wù)調(diào)度方法的完成時(shí)間對(duì)比明顯，當(dāng)?shù)螖?shù)為140時(shí)，文獻(xiàn)[4]、文獻(xiàn)[5]方法的完成時(shí)間分別為155s、141s，研究方法的完成時(shí)間為64s，對(duì)比兩種傳統(tǒng)方法分別減少了91s、77s。根據(jù)上述數(shù)據(jù)說(shuō)明研究方法的調(diào)度任務(wù)時(shí)間更短，相比傳統(tǒng)方法而言更具有實(shí)際應(yīng)用意義。

4.2 不同方法下云計(jì)算資源利用率對(duì)比

為了驗(yàn)證研究的調(diào)度方法資源利用率情況，運(yùn)用三種方法在相同的實(shí)驗(yàn)環(huán)境中，對(duì)不同數(shù)量的任務(wù)進(jìn)行調(diào)度，并計(jì)算資源利用率。不同方法的資源利用率如表1所示。

表1 資源利用率

對(duì)比表1的數(shù)據(jù)結(jié)果，研究方法能有效提高資源利用率，當(dāng)任務(wù)種類為50種時(shí)，文獻(xiàn)[4]、文獻(xiàn)[5]方法的資源利用率分別為35%、41%，研究方法的資源利用率為51%；當(dāng)任務(wù)種類為100種時(shí)，文獻(xiàn)[4]、文獻(xiàn)[5]方法的資源利用率分別為48%、53%，研究方法的資源利用率為67%；當(dāng)任務(wù)種類為200種時(shí)，文獻(xiàn)[4]、文獻(xiàn)[5]方法的資源利用率分別為75%、80%，研究方法的資源利用率為98%。隨著任務(wù)數(shù)量的增加，兩種傳統(tǒng)方法的局限性十分明顯，研究方法的資源利用率高。

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

針對(duì)傳統(tǒng)實(shí)時(shí)任務(wù)調(diào)度方法計(jì)算時(shí)間長(zhǎng)、資源利用率低的問(wèn)題，提出基于資源延遲感知的云計(jì)算實(shí)時(shí)任務(wù)調(diào)度。為了研究云計(jì)算的實(shí)時(shí)任務(wù)調(diào)度，通過(guò)設(shè)立調(diào)度模型來(lái)提高調(diào)度費(fèi)用和調(diào)度效率，實(shí)驗(yàn)結(jié)果證明，研究的調(diào)度方法能夠減緩兩種傳統(tǒng)調(diào)度方法資源不平衡的問(wèn)題，使資源得到最大化利用，同時(shí)考慮縮短調(diào)度任務(wù)時(shí)間，從而提高調(diào)度效果。未來(lái)將從如何提高云計(jì)算服務(wù)質(zhì)量方面進(jìn)行研究，進(jìn)一步完善云計(jì)算實(shí)時(shí)任務(wù)調(diào)度方法。