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

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

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

0 引 言

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

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

1 相關工作

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

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

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

2 算法框架

2.1 任務模型

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

2.2 調度模型

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

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

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

在系統中增加一個實時任務監控器，用于監測實時虛擬機中實時任務的執行情況，監測和記錄實時任務超時發生的任務個數，發生的時間，實時任務比計劃時間提前完成的時間。

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

圖1 調度模型

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

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

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

(1)

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

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

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

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

(2)

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

2.3 窗口調整和資源伸縮

(3)

(4)

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

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

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

3 結果分析

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

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

(5)

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

Tt=Tc/fi

(6)

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

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

(7)

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

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

圖2 時延符合要求任務

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

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

圖3 截止期影響

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

圖4 耗時

4 結束語

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