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

吳譽蘭，黃 衛(wèi)

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

1 引言

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

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

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

2 云計算的實時任務(wù)調(diào)度問題

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

圖1 Map/Reduce編程模型運行機制

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

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

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

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

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

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

(1)

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

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

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

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

3.1 調(diào)度框架

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

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

(2)

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

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

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

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

(3)

(4)

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

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

(5)

(6)

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

(7)

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

(8)

整合上述公式，得到主機CPU消耗功耗計算公式為

(9)

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

(10)

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

(11)

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

(12)

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

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

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

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

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

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

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

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

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

4 仿真與分析

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

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

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

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

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

4.2 不同方法下云計算資源利用率對比

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

表1 資源利用率

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

5 結(jié)束語

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