移動云計算中時延保證的任務分配方法

蔣維成，李蘭英，劉華春，侯向寧

(成都理工大學工程技術學院 電子信息與計算機工程系，四川 樂山 614000)

0 引 言

移動云計算中的服務請求受環(huán)境影響，許多任務要求在規(guī)定的時間內(nèi)完成，如過程控制、環(huán)境監(jiān)測中的數(shù)據(jù)處理，以及移動手機中的各種實時信息的獲取等。若時延超過某一范圍將導致不利影響，或任務的失敗。這些具有時延要求的任務，對服務器中的虛擬機提出了實時要求。由于這些任務種類繁多，變化很大，增加了創(chuàng)建虛擬機的困難，若根據(jù)任務類型創(chuàng)建虛擬機，將給系統(tǒng)帶來巨大開銷。另外，管理這些虛擬機也是一個復雜的問題。創(chuàng)建虛擬機需要時間，將推遲任務的執(zhí)行，影響任務的提交，對實時任務造成不利影響。

為了縮短實時任務的響應時間，可以將任務分配到已經(jīng)創(chuàng)建的虛擬機中。在任務指派過程中，需要考慮任務量的大小，任務量大的任務需要分配到計算能力強的虛擬機中，才能滿足時延要求。此外，虛擬機中指派的任務不能過多，不然造成任務的響應時間過長，導致任務失敗。為了對移動云計算中的實時任務提供時延有保障的服務，本文根據(jù)虛擬機計算能力來構建任務窗口，將任務調(diào)度到能在截止期之前完成的虛擬機中，對任務執(zhí)行過程進行監(jiān)控，確保任務的有效完成。

1 相關工作

云計算中任務的分配引起了學者的廣泛關注和深入研究。文獻[1]提出了一種任務調(diào)度算法，把任務分為不同種類，每類任務具有相似的屬性(用戶類型、任務類型、任務大小和任務延遲)，根據(jù)類別，選擇最小執(zhí)行時間的任務進行執(zhí)行。文獻[2]根據(jù)任務在計算節(jié)點的處理頻度、等待時間和執(zhí)行時間等參數(shù)構建數(shù)學模型，采用優(yōu)先級來進行任務分配。為了減少結點間的數(shù)據(jù)傳輸，文獻[3]采用數(shù)據(jù)復制方法來提高任務調(diào)度數(shù)據(jù)的效率。

云服中管理系統(tǒng)的服務對象包含企業(yè)生產(chǎn)經(jīng)營的一系列活動的流程。這些流程構成信息流動和資源交換的重要載體，可以劃分為多個任務單元[4]。分配和調(diào)度這類任務單元保障整個流程的順利完成成為研究的熱點問題[5,6]。通過合并低效率的處理器,降低資源使用數(shù)量，文獻[7]提出了一種云工作流任務調(diào)度能效優(yōu)化算法，在不違背任務順序和截止時間約束前提下降低工作流執(zhí)行總能耗。根據(jù)任務平均運行時間進行調(diào)度的算法，很難最小化任務的完成時間，建立任務的運行時間和能耗模型，文獻[8]提出能耗感知的調(diào)度算法。任務復制的調(diào)度算法中存在過度復制任務造成資源浪費的現(xiàn)象，文獻[9]最小化任務的復制量，以求達到最小化應用的完成時間和能量消耗。文獻[10]提出了基于MapReduce的能量感知多作業(yè)調(diào)度模型，設計遺傳算法，對云計算中大規(guī)模任務調(diào)度進行優(yōu)化，以提高服務器的能源效率。文獻[11]建立資源總租賃成本的調(diào)度優(yōu)化數(shù)學模型，構造插入鄰域和交換鄰域的迭代局部搜索算法，以一定概率的插入和交換操作實現(xiàn)擾動當前解，增加群體多樣性，選擇算法性能最優(yōu)的參數(shù)組合，構建云環(huán)境下多模態(tài)工作流調(diào)度方法。文獻[12]提出了資源動態(tài)增加與收縮策略，并設計了實時任務的一種節(jié)能調(diào)度算法EARH。文獻[13]設計了基于仿生自主神經(jīng)系統(tǒng)的云調(diào)度管理系統(tǒng)，利用最優(yōu)性分析和自主觸發(fā)機制實現(xiàn)局部資源管理，采用啟發(fā)式算法來獲取面向用戶請求分發(fā)的全局最優(yōu)調(diào)度策略，以實現(xiàn)兼顧性能和能耗的云調(diào)度管理機制。

但是，這些調(diào)度算法存在如下問題，對實時任務無法提供時延保證的服務，使得任務能夠在有效截止期內(nèi)完成，保障任務實時可用性，尤其是數(shù)據(jù)中心服務器負載突然增加或執(zhí)行過程的某些不確定因素造成任務響應時間過大，導致實時任務的提交延誤或無效。本文針對這些問題，提出一種基于任務窗口時延確保的調(diào)度方法(scheduling method for task window delay guarantee，TWDG)，以提高移動云計算數(shù)據(jù)中心實時任務的可用性。

2 算法框架

2.1 任務模型

在移動云計算中，用戶提交的任務具有很大的隨機性，本文針對的應用是非周期的實時性要求較高的獨立任務。任務執(zhí)行若超時將造成不良影響。這些任務表示為P={p1,p2,p3…pn}。 這些任務的到達時間和截止期在任務到達之后才能得知。對于某任務集合P中的任何一個任務pi∈P，可以采用三元組來表示。 pi=(Ai,Si,Di)。 這里Ai表示任務pi的到達時間，Si表示pi的任務量大小，Di表示pi的截止期。

2.2 調(diào)度模型

移動云計算系統(tǒng)是由多個物理服務站點組成，每個站點有若干臺服務器。物理服務器構成集合B={b1,b2,b3…bn}，n為服務器的數(shù)量。這些服務器構成為用戶提供計算服務的基礎設置平臺(IaaS)。其中某臺服務器bi可以表示為Q=(F,E,R)，這里F表示服務器的CPU頻率(MHz)，E表示內(nèi)存大小(MB)，R表示網(wǎng)絡帶寬(Mbps)。

每臺服務器上創(chuàng)建若干個虛擬機，這些服務器上的虛擬機集合表示為VM={VM(1),VM(2),VM(3),…VM(m)}，使用fi、ei和ri表示虛擬機VM(i)中該虛擬機的CPU頻率、內(nèi)存大小和網(wǎng)絡帶寬。

創(chuàng)建虛擬機需要一定的時間[14]，這將影響實時任務的執(zhí)行。為了減少因創(chuàng)建虛擬機導致任務時延的增加。在系統(tǒng)中維持一個備用虛擬機。通常備用虛擬機處于休眠狀態(tài)，僅分配極少必要的資源，而當系統(tǒng)資源不夠時，喚醒備用虛擬機，立即分配資源，并為其指派任務。此時系統(tǒng)中就不存在備用虛擬機，立即創(chuàng)建一個備用虛擬機，始終保持系統(tǒng)中存在一個備用虛擬機，以減少創(chuàng)建虛擬機的時間，確保實時任務得到及時響應。

在系統(tǒng)中增加一個實時任務監(jiān)控器，用于監(jiān)測實時虛擬機中實時任務的執(zhí)行情況，監(jiān)測和記錄實時任務超時發(fā)生的任務個數(shù)，發(fā)生的時間，實時任務比計劃時間提前完成的時間。

本文的調(diào)度模型如圖1所示，新到達的任務經(jīng)任務分析器進行分析，得到任務量的大小和截止期要求。交給調(diào)度器，調(diào)度器根據(jù)任務窗口的大小和截止期的要求，將任務分配到滿足條件的虛擬機中執(zhí)行。任務監(jiān)測器對虛擬機中實時任務執(zhí)行進行監(jiān)測，對任務執(zhí)行時間增加的超時現(xiàn)象和執(zhí)行時間大幅減少的情況進行處理。并對任務窗口進行調(diào)整。

圖1 調(diào)度模型

定義1 標準任務，用來衡量實時任務的規(guī)模和任務量大小，抽象出來的量，大小為一個單位任務量，用S0表示。具體任務可以通過標準任務來衡量任務量的大小。

定義2 虛擬機計算能力，表示虛擬機的計算處理能力，用C表示。它與CPU頻率、內(nèi)存大小和網(wǎng)絡帶寬有關。通常虛擬機的CPU頻率越高，內(nèi)存越大，網(wǎng)絡帶寬較高條件下，虛擬機的計算能力就越強。用式(1)表示

C=k1·F+k2·E+k3·R

(1)

式中：k1，k2，k3為比例系數(shù)，表示虛擬機的計算能力C同CPU頻率、內(nèi)存大小、網(wǎng)絡帶寬之間的關系。

定義3 任務處理速率，指單位時間內(nèi)完成標準任務的數(shù)量，用V表示。它反應虛擬機對任務處理的快慢，與虛擬機的計算能力有關。計算能力越強，單位時間內(nèi)完成標準任務越多，任務處理速率也就越大。

定義4 任務窗口，表示分配給虛擬機任務量多少的度量，用W表示。計算能力越強的虛擬機其任務窗口越大，在相同的截止期條件下，該虛擬機可以分配的任務就越多。反之，則越少。每個虛擬機根據(jù)其計算處理能力構建相應的任務窗口，它是任務指派的依據(jù)和度量。虛擬機受自身計算能力的限制，超過任務窗口的任務將不再分配給該虛擬機，只有任務量小于任務窗口尺寸的任務才能指派給虛擬機。每分配一個任務，任務窗口尺寸減小相應的值。當任務窗口尺寸減少到0時，不再給虛擬機分配任務。相應的，完成一個任務則對任務窗口增加相應的量。它是一個動態(tài)變化的量。

若虛擬機VM(j)中已經(jīng)分配的任務隊列中的待處理任務集合為P={p1,p2,p3…pm}，這些任務相應的任務量為 {S1,S2,S3…Sm}，那么等待時間為式(2)

(2)

任務分配時，首先查找任務窗口尺寸大于任務所需尺寸大小的虛擬機，若存在，則在這些虛擬機集合中，進一步查找等待時間Tw

2.3 窗口調(diào)整和資源伸縮

(3)

(4)

虛擬機中發(fā)生任務超時采用2倍任務窗口量進行減少，而對虛擬機中任務提前完成僅增加1/2倍任務窗口量進行增加，這樣來對任務窗口進行修正，使得任務窗口的大小動態(tài)地與任務量大小相平衡，符合虛擬機計算機能力的要求，減少超時的發(fā)生，保證實時任務能夠在截止期到來之前完成。

若系統(tǒng)中任務窗口長期處于最大值，表明該虛擬機較長時間處于空閑狀態(tài)。如果系統(tǒng)中存在較多的虛擬機處于閑置狀態(tài)，可以將這類虛擬機中的任務進行合并，從而關閉一部分虛擬機，減少系統(tǒng)資源的浪費。

當出現(xiàn)某任務的提交超時時，對任務窗口中的任務執(zhí)行造成不利影響，此刻需要對已分配的任務進行檢查，設超時造成的時間增加量為Δt’，若后續(xù)任務均可以在截止期內(nèi)完成，則表明超時造成的時間增加Δt’是允許的，不會造成后續(xù)任務的超時，只需把虛擬機的任務窗口減少；若可能造成后續(xù)任務超時時，則將這些任務按新的到來時間，重新分配到計算能力強且負載又低的虛擬機中。

3 結果分析

為了檢驗本文提出的TWDG算法的性能，與任務分配方法FIFO算法和RR算法進行了比較實驗。實驗過程采用Cloudsim仿真平臺和Opennet軟件來模擬移動云計算中的基礎設置。采用Google云服務系統(tǒng)中任務數(shù)據(jù)和仿真數(shù)據(jù)源來對隨機任務進行分配。根據(jù)文獻[14]來設置任務周期和截止期等信息。任務周期(Tc)由任務開始時間(ts)和結束時間(te)、主機CPU的平均利用率來確定，如式(5)所示

Tc=(te-ts)×Ua×C′

(5)

式中：C′為主機CPU的處理能力。任務的執(zhí)行時間由任務周期和虛擬機CPU頻率決定。如式(6)所示

Tt=Tc/fi

(6)

采用截止期基準來控制任務的截止期，具體計算公式如式(7)所示

Dk=Ai+(te-ts)×βd

(7)

式中：βd為截止期基準。

任務和符合時延要求的任務數(shù)結果如圖2所示。

圖2 時延符合要求任務

從圖2可以看出，隨著任務規(guī)模的增加，符合時延要求的任務數(shù)不斷增加。在任務數(shù)為350～500這4種不同情況中，TWDG算法時延達標的數(shù)量是相當高的，達標任務數(shù)接近于任務數(shù)。而FIFO算法和RR算法中時延達標的數(shù)量卻比TWDG算法少。這主要是這兩個算法缺少對任務截止期的考慮，另外，F(xiàn)IFO算法和RR算法中時延達標數(shù)也不穩(wěn)定，偶然性比較大，存在時高時低的現(xiàn)象。TWDG算法采用基于任務窗口的方式來對任務進行分配，把任務分配給能在截止期之前完成的虛擬機中執(zhí)行，保證了任務的實時可用性。

圖3是在截止期基準率不斷增大情況下，提交任務中符合時延要求的任務數(shù)。隨著截止期基準率的增大，任務時延增加，實時性要求降低。從圖3可用看出，TWDG算法受截止期基準變化影響較小，時延達標任務都很高。而FIFO算法和RR算法則受截止期基準率變化影響較大，F(xiàn)IFO算法和RR算法在截止期允許范圍增大時，達標任務數(shù)增加較多。TWDG算法中備用虛擬機減少了創(chuàng)建虛擬機時延增加，保證任務突然增多時能及時地進行響應，從而增加了達標的數(shù)量。因此，無論是在截止期基準較小的高實時要求下，還是在截止期基準較大的低實時情況下，達標的任務數(shù)都是很高的，表明TWDG算法的應用范圍廣，既適合時延要求高的環(huán)境，也適合時延要求低的環(huán)境。

圖3 截止期影響

圖4是任務截止期相同情況下，三算法的吞吐量的比較。從圖4可用看出，在同等任務條件下，TWDG算法所耗時間要少，因而吞吐量要比FIFO算法和RR算法要大。TWDG算法根據(jù)虛擬機的計算能力來構建任務窗口大小，對于計算能力存在差異的異構型系統(tǒng)來說，有利于保持負載均衡，從而提高了任務的吞吐量。

圖4 耗時

4 結束語

移動云計算中終端設備種類繁多，服務請求多種多樣，很多任務具有實時要求，增加了服務器處理的復雜性，為這些任務提供實時保障的服務具有挑戰(zhàn)性。本文根據(jù)虛擬機的計算能力來構建任務窗口，按任務截止期和任務窗口大小來進行實時任務的調(diào)度，保證分配到虛擬機的任務都符合時延要求，同時，對虛擬機中任務執(zhí)行進行監(jiān)測，進一步減少超時發(fā)生，并建立相應的反饋機制來保障后續(xù)任務的分配不受超時影響，提高實時任務分配的可用性。為了降低因創(chuàng)建虛擬機而延誤實時任務的執(zhí)行，在系統(tǒng)中增加備用虛擬機，備用虛擬機在普通情況下處于休眠狀態(tài)，占用極少資源，在需要時激活，能夠及時進行響應，減少時延。建立服務器中資源的伸展和收縮策略，以提高資源的利用率。本文算法能有效地應對任務量的變化，滿足時延要求，適用范圍廣。