蔣維成，李蘭英，劉華春，侯向?qū)?/p>

(成都理工大學(xué)工程技術(shù)學(xué)院 電子信息與計(jì)算機(jī)工程系，四川 樂山 614000)

0 引 言

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

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

1 相關(guān)工作

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

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

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

2 算法框架

2.1 任務(wù)模型

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

2.2 調(diào)度模型

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

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

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

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

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

圖1 調(diào)度模型

定義1 標(biāo)準(zhǔn)任務(wù)，用來衡量實(shí)時(shí)任務(wù)的規(guī)模和任務(wù)量大小，抽象出來的量，大小為一個(gè)單位任務(wù)量，用S0表示。具體任務(wù)可以通過標(biāo)準(zhǔn)任務(wù)來衡量任務(wù)量的大小。

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

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

(1)

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

定義3 任務(wù)處理速率，指單位時(shí)間內(nèi)完成標(biāo)準(zhǔn)任務(wù)的數(shù)量，用V表示。它反應(yīng)虛擬機(jī)對任務(wù)處理的快慢，與虛擬機(jī)的計(jì)算能力有關(guān)。計(jì)算能力越強(qiáng)，單位時(shí)間內(nèi)完成標(biāo)準(zhǔn)任務(wù)越多，任務(wù)處理速率也就越大。

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

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

(2)

任務(wù)分配時(shí)，首先查找任務(wù)窗口尺寸大于任務(wù)所需尺寸大小的虛擬機(jī)，若存在，則在這些虛擬機(jī)集合中，進(jìn)一步查找等待時(shí)間Tw

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

(3)

(4)

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

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

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

3 結(jié)果分析

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

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

(5)

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

Tt=Tc/fi

(6)

采用截止期基準(zhǔn)來控制任務(wù)的截止期，具體計(jì)算公式如式(7)所示

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

(7)

式中：βd為截止期基準(zhǔn)。

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

圖2 時(shí)延符合要求任務(wù)

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

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

圖3 截止期影響

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

圖4 耗時(shí)

4 結(jié)束語

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