基于任務遷移和需求控制的云計算成組調度性能及代價評估

陳斌 東一舟 毛明榮

摘 要：對成組調度技術在云計算中的應用效果展開了研究，該效果體現在其性能和耗費代價的綜合指標上。文章對該模式的研究是通過虛擬化以分析基于任務遷移和需求控制的成組調度性能和綜合代價為手段，以基于Amazon彈性云計算架構（EC2）為實驗背景進行效率評估實驗以獲取支撐數據。結果顯示，該調度策略可以有效地部署于云環境，并且該云平臺可以被真實的高性能計算環境或其它高性能領域所應用，具有較高的性能代價比。

關鍵詞：云計算；成組調度；高性能計算；虛擬機

中圖分類號：TP39 文獻標識碼：A 文章編號：2095-1302（2016）05-00-05

0 引 言

云計算指的是計算資源作為公共事業的一種模型，就像水和電力一樣，用戶可以按照其所需而獲取計算資源。基礎設施即服務（IaaS）和網格計算這樣的既有模型不同，它對于提供給用戶的軟件或服務的類型沒有任何限制。事實上，云提供了有效的應用基于已有的或定制的任何軟件的能力。

云計算的重要性在于為小公司或組織在沒有先前投資的情況下提供接入計算基礎設施的機會。因此，所需要的資金投入總額可以被縮減為最小化的投入代價并減小了運行風險。

云計算可以被運用到高性能計算上這一結論已被證實。小的機構和個體科研組織現在可以接入大型計算資源，不僅可以通過帶有限制的網格，還可以通過提供了虛擬無限資源為基礎平臺的云集群，這些集群在維護上只需要原有的部分代價，并且通過使用即付費的模式來運作。

任何分布式系統的核心都在于它的任務調度器，其作用在于向服務器或者虛擬機分配任務。通常，調度器的調度策略目標是達到更快的響應時間和更低的故障率，這是通過最小化冗余延遲來實現的[1]。

在我們的模型中，調度器必須以趨于最小時間花費的虛擬機目標策略來獲得最佳的代價效率比。該建模系統實現了一個稱為成組調度的并行任務調度的特殊實例，該實例中的任務必須同時執行及被調度，以滿足其持續互相通信的要求。這就需要在任務和虛擬機之間建立一張點對點映射圖[2]，并且要避免由來源于另一個非運行任務作為任務輸入等待條件所可能帶來的瓶頸問題及其引起的死鎖。

在分布式和集群系統領域，近些年成組調度已經被廣泛研究。Karatza在其文獻中提到了對適應性先來先服務（AFCFS）以及最大優先級任務先服務（LJFS）的性能研究[3]。與此同時他還研究了成組調度在輸入輸出調度和處理器失敗情況下的應用研究[4]。Papazachos和Karatza研究了該成組調度在兩個不同集群系統中的應用情況。先前提到的公共應用成組調度都是設計于預先安排好服務器總數量及單機范圍任務大小的靜態系統。

使用虛擬計算機作為處理單元的網格模型系統的彈性被Nie和Xu等人研究[5]。其發表的研究聚焦于沒有執行期限的非并行任務和目標與當維持最小化失敗率時的最大化利用率。

云計算平臺的調度策略在之前已經被研究。Assuncao等人對通過云完成的擴展私有集群進行了研究[6]。Sotomayor等人使用模糊虛擬機管理架構對在并行任務批量調度虛擬機利用率問題上進行了研究。在這些模式中，任務并不需要交互操作，并且可以被獨立的調度執行[7]。

我們研究了在動態提供虛擬機的分布式云計算系統中應用成組調度策略的方法和效用。我們利用了兩個任務調度算法即之前提到的AFCFS和LJFS，并且控制虛擬多樣化工作和多重任務規模的范圍。評估結果同時對性能和代價效率調度算法有效。然而，我們先前的工作沒有考慮任務的遷移以提高響應時間和減小任務分離，同樣沒有考慮到高負荷工作的適應算法，應用可能引起很多等不到執行機會的任務。在該新研究中，我們的模型中整合了遷移機制和需求控制系統，并且比較了這些方法的有效性，這些方法有著較好的綜合性能和代價效率。之前的研究并沒有考慮到成組調度在基于云計算架構的復雜模型中的應用。

1 系統及工作模式

虛擬建模開發包括動態虛擬機集群及其虛擬機調度器（DVM）。當系統初始化時，無需進行虛擬機租約的確定，虛擬機數量可以動態增加和縮減。

在虛擬機調度器有能力進行分布式并行任務調度的情況下每一個虛擬機將實現其自己的等待隊列。虛擬機調度器同樣有一個任務隊列，它們既不能按照虛擬機不均勻到達時間進行調度也不能按照系統負載來進行調度。出于簡單的目的，虛擬機調度器本身并不包括在虛擬機總數中。同樣，任務遷移和需求控制機制由虛擬機控制器進行管理。

虛擬機間通信可以認為是自由競爭關系，然而任何潛在的通信都包含了任務執行時間。所以，我們必須要考慮到當任務調度器隊列存在任務調度延誤的情況。

除此之外，虛擬機被考慮在包括相同EC2的實例類中，并且因此具有完全相同的特性。雖然虛擬機可能具有不同的處理性能，就像非虛擬系統一樣，研究表明，除卻輸入輸出可能產生的影響，虛擬機可以提供近似相同的性能[8]。由于在我們的研究中沒有考慮到輸入輸出情況，假設任何包括任務執行時間在內的影響性能的臨時原因都是隱含被屏蔽的。

成組調度需要任務并行運作[9]，因此每一個任務需要一系列等價于為執行需要而并行化的空閑虛擬機。在我們的模型中，并行化的程度是隨機的，其符合離散均勻分布并可以歸納為以下兩類：

（1）低并行化任務：任務的數量以q為概率維持在1至16個之間。

（2）高并行化任務：任務的數量以1-q為概率維持在17至32個之間。

q是決定了任務總數的任務數量并發系數，該系數可以屬于第一類或第二類。

因此平均任務數量（AJS）可以按照式（1）計算得出：

這里，E代表的是離散均勻分布等量范圍值。任務同時到達時間的意思是以1/λ為平均值的指數分布并且平均服務時間是以1/μ為平均值的指數分布。服務時間和任務數量之間沒有關系，因此，一個低并行度任務可以擁有一個較長的服務時間。最終研究顯示，成組調度的上下文切換需要較高代價，故任務并不會常以搶占的方式執行完成[10]。該系統的控制模型如圖1所示。

圖1 系統模型

2 調度遷移和需求控制策略

2.1 任務分發

圖1所示的系統入口點是虛擬機調度器。任務并行化程度小于或等于時可用立即分發虛擬機。對于虛擬機任務的分布，虛擬機調度器應用最短隊列優先算法，該算法向虛擬機分發任務按照最短隊列原則進行。

2.2 任務調度

模型應用了兩個常用的成組調度算法。不管是AFCFS還是LJFS都在集群計算領域有著一定程度的研究。服務調度原則如下：

（1）適應性先來先服務：AFCFS試圖調度那些在其各自隊列之前的任務，當每一次虛擬機變為空閑時，如果沒有這個任務的存在，AFCFS將試圖以最快降低隊列長度的方式來調度任務。因為這種AFCFS調度方式趨于針對較小任務，這些任務更易于調度但會增加最大任務的等待時間。

（2）最大優先級任務先服務： LJFS調度方式提供了針對大任務的更優先的調度策略。在每一個調度周期內，LJFS都將嘗試調度分布于空閑虛擬機中的最大優先級任務。該方法通過授權方式在很大程度上增加了大任務的響應時間。同樣，由于大任務在調度過程中經常將大量虛擬機資源空余出來，相對于AFCFS，較小的任務在等待時間上將被縮減。

2.3 任務遷移

成組調度中有一個共性問題，即通常當等待任務被調出隊列的過程中處理器總會處于空閑狀態[11]。為了避免出現這種時間碎片，遷移的實施是必須的。遷移的處理包括了從虛擬機隊列中的繁忙虛擬機中向可用空閑虛擬機上遷移切換任務。雖然該處理方式解決了前面提到的碎片問題，但其本身也給系統帶來了大量的開銷[12]。

本文設計的系統在考慮了應用任務遷移安全性的前提下減少了系統開銷。具體做法是：只有在系統不能通過正常途徑進行任務調度的情況下才允許任務遷移。當這種情況發生時，遷移系統嘗試查找是否在任務隊列中有適合于在當前空閑虛擬機中運行的任務。如果存在這樣的任務，系統將使用以下兩種策略中的一種來對任務進行遷移，具體選擇哪種依賴于虛擬機的配置。這兩種策略如下：

（1）首位適應：在合適的任務隊列中，直接選擇排在首位的任務。該方法實現簡單，帶來的平均開銷少。

（2）最佳適應：選擇最適合的任務，該任務對于空閑的虛擬機來說，具有最高等級的并行化適應性。該方法由于需要執行最佳任務適應算法，從而將帶來較多的額外開銷。

為了高效達到該遷移任務的目的，我們還引入了一個遷移監控機制用于減少總的遷移次數，該監控可以確保任務調度只發生在適配任務數小于指定數量的情況下。

當遷移處理結束后，遷移的任務將被調度到執行狀態，并立刻在下一個時鐘周期被執行。該處理方式可防止對同一任務的多次重復遷移，避免對系統產生更多負載開銷。

2.4 需求控制

我們的系統中還設計有一個包含了隊列優先權的專用子系統，該子系統的實現目的在于進行需求控制。當該隊列包含了“需求控制”任務時，常規的任務調度和遷移會被暫停。當系統的膨脹系數Xfactor達到了設置的需求門限，則該任務會自動觸發。膨脹系數的計算方法見式（2）：

這里，IWTj和ej是實例等待時間，該時間的長短取決于各個實際執行任務j本身的運行時間。

對膨脹系數的選擇在整個任務控制處理中起到了非常重要的作用。另外，在我們的模型中有需求的任務可能會發生遷移，并沒有被上面提及的監控系統所綁定，因此需求控制系統也可能導致在所設置的膨脹系數滿足的情況下形成任務遷移潮。

3 虛擬機控制策略

云向用戶提供了其對計算資源按照實際請求虛擬機數量進行增容或減容的能力。該過程包括了一個延遲，該延遲由虛擬機管理者創建和設置新的虛擬機所需時間而產生。在每次請求中該延遲通常小于十分鐘。在我們的虛擬模型中，該延遲是按照均值為0.1而設計的，滿足U（0，0.4）的持續均勻分布的隨機數。

3.1 虛擬機供給機制

一個復雜的子系統被實現用于從系統中添加和去除虛擬機。遇到以下條件之一時將發生虛擬機租借的情況：

（1）虛擬機不足。當一個任務包含了多個子任務，其總數超過了可用虛擬機數目，將會發生這種情況。該任務被排列在虛擬機管理器中直到新的虛擬機可以供給。

（2）虛擬機過載。在每一次分發中，系統都會檢查虛擬機等待隊列的狀態，計算平均負載因子的公式見式（3）。

這里，Jk是虛擬機k中的當前等待任務數，Pk是系統當前已租借虛擬機數。

（3）

ALF總體而言要優于之前定義的負載門限，系統提供了一個虛擬機控制器能力等價于達到任務數的新虛擬機，其任務隊列將處于等待狀態直到新虛擬機可用為止。

出現上述兩種情況的任一種，系統都不會去嘗試申請租借更多的虛擬機。同樣，當每一個提供的租借虛擬機被暫停，在第十個周期到達后將會由系統為新的虛擬機進行填補。

3.2 虛擬機釋放機制

在當前環境下，當系統不再需要使用某些虛擬機時，可能會進行虛擬機的釋放。該操作由于會影響系統的整體開銷，所以特別重要。如何評價一個虛擬機是否滿足可釋放條件取決于以下三點：

（1）虛擬機是空閑的并且其等待隊列也是空的；

（2）虛擬機管理器隊列中沒有等待重新調度的任務；

（3）沒有正處于計劃遷移激活態的任務。

若以上三點標準同時滿足，我們就認為該虛擬機處于可釋放狀態。

4 性能與代價評估

該研究既集中于系統性能的評估，也關注代價的評估。

4.1 性能評價指標

以下指標都在性能評價中使用：

（1）響應時間RTk：表示了任務k的請求在到達與反饋之間的間隔時間。它的平均值可以定義如下：

這里N代表任務的總數。

（2）響應遲緩比Sk：其定義為Sk=RTk/ek，該指標顯示了一個任務相對于其服務時間ek的延誤容忍比度。由于該指標可以很容易被作為分母的數值很小的服務時間所影響，所以我們使用下述限制指標：

我們的實驗里λ被設置為10-3。

（3）遷移總數目migtot：由于上述原因，我們使用有明確影響的遷移總數量以對系統綜合性能的虛擬化進行評估。

4.2 代價評估

由于云的運作是有代價關聯的，所以系統必須在響應時間和所需代價之間維持一個較好的平衡。因此，我們需要整合代價性能效率的指標，即虛擬機完全租賃時間（LT）和平均響應時間（RT）。

CPE=DLT+DRT

這里，DLT是LT和兩個虛擬實驗的相關差異，DRT是響應時間之間的相關差異。我們必須注意到，最佳適配先服務作為基礎較最大任務先服務策略在CPE數據上具有負向效果，所以顯示出最佳適配先服務作為基礎較最大優先級任務先服務策略的優越性。圖2所示是在相同到達率情況下不同響應時間和不同響應延遲比的性能指標圖。圖3所示是相同到達率情況下的任務遷移數指標。

（a）同到達率情況下不同響應時間的性能指標

（b） 同到達率情況下不同響應延遲比的性能指標

圖2 相同到達率情況下不同響應時間和

不同響應延遲比的性能指標

圖3 相同到達率情況下的任務遷移數指標

4.3 仿真參數

上面描述的模型是通過非連續模擬事件實現的。這里表征的每一個結果都是由平均差異實例對每一個到達率（λ）的調度算法，遷移算法以及每一個任務大小的協同虛擬化實驗所反饋的結果。每一個仿真運行都將在完成100 000個任務后自動終結。

三個不同任務規模的協同實現如下：

（1）p=0.25，其中平均任務數量為22.5；

（2）p=0.5，其中平均任務數量為16.3；

（3）p=0.75，其中平均任務數量為12.8。

這些值被選擇以研究任務規模對系統性能的影響。

對λ值的簡單選擇并不能滿足系統復合結構的要求。通過實證研究我們選擇了可以使系統有能力進行動態租借和釋放虛擬機的值。對每一個任務規模協同分布到達率，我們給出如下參數的結論：

（1）p=0.25，到達率λ=[1.75，2.0，2.25，2.5]；

（2）p=0.5，到達率λ=[2，2.25，2.5，2.75]；

（3）p=0.75，到達率λ=[2.5，3.0，3.5，4.0]。

同樣前面描述過，由于膨脹系數在需求控制中起到了一個很重要的作用，我們對以下兩個分離值進行了測試：

（1）Xfactor=10

（2）Xfactor=20

對于每一個平均值，都以95%的可信區間進行評估。所有可信區間的半寬都小于其各自值的5%。

4.4 結果

該結果由預測性能和代價在兩個不同配置的調度算法下的差異而生成。由于該模型由離散事件模擬，所以響應時間由理論時間片計算獲得。

圖2描述了上述性能指標（包括RT和BSLD）以及p=[0.25，0.50，0.75]等各種情況下的狀態。每一張圖都顯示了最佳適配先服務與最大優先級任務先服務對任務到達率、響應時間、響應延遲比以及膨脹系數之間協同的作用效果。圖3顯示了每一個實驗中的遷移任務數量，由此完成對遷移的評估。最終，表1顯示了在所有參數情況下的性能與代價效率數據。

（1）響應時間：很明顯，遷移系統與需求控制系統一同有效的工作可將響應時間維持在低水平上并保持較低或中等的到達率。在p=0.25和Xfactor=20的高到達率情況下，這里在響應時間上存在著顯著差異。在同樣情況下，最近任務先服務與最佳適配機制相結合提供了最適度的結果。

正如我們在圖3中看到的在相應配置的情況下，p=0.25，Xfactor=20相對于Xfactor=10來說允許更少的遷移發生，從響應時間的角度來看，具有更低的到達率。相比之下，當到達率提高時，不僅同等級膨脹系數下的性能差異微小，同時遷移數量與Xfactor=10相當。一方面p=0.5和p=0.75，Xfactor=20能夠使平均響應時間維持在一個較好的水平上，與Xfactor=10相比可以提供上限為40%的遷移。因此可以得出結論：即當處理中低等級并行化任務時，更大的膨脹系數是可取的，而對于處理高級別并發任務時，特別是針對較大到達率的情況下，較小的膨脹系數則是更優的選擇。

（2）響應遲緩比：這是一個很容易受到較短服務時間影響的指標，雖然我們的指標進行了界限設定，但其依然可以隨時間變化。

在圖2中，綁定響應延遲比指標對于p=0.75和p=0.5及一些異常值的情況下顯示了一個持續穩定的行為結果。這些結果顯示，響應延遲發生在遷移算法和需求控制介于中低等級的并發任務規模的協同程度處于可控制水平的情況下。對于p=0.25，相對結果顯示在響應延遲比上則會與預期結果有較大的不一致。這可以歸于遷移和需求控制方法在時間上以短服務時間劃分任務以至在等待隊列里以相對于期望的立即影響的響應延遲比需要更長的周期。

（3）代價與性能效率：在我們之前的工作中，是沒有包括遷移和需求控制的，因此得到的結論是對于所有任務在較高到達率情況下，最大優先級任務先服務與適應性先來先服務相比有著更高的代價效率。表1顯示了這些在遷移和需求控制起作用的情況下基本消失的差異。不同的任務規模效應和擴展因素看起來有著較小的影響，同時，當使用負值對適應性先來先服務進行描述的話，差異實際可以忽略不計。

表1 代價和性能效率表

λ 先來先服務（10） 最佳適應先服務（10） 先來先服務（20） 最佳適應先服務（20）

p=0.25

1.75 -0.016 32 0.012 79 -0.058 01 -0.051 02

2.50 -0.056 49 -0.029 13 0.015 14 -0.029 27

3.25 -0.061 12 -0.033 13 -0.137 15 -0.203 18

4.00 -0.041 45 -0.042 13 -0.025 31 -0.051 99

p=0.50

1.75 -0.012 07 -0.002 80 0.004 13 -0.038 12

2.50 -0.041 32 0.008 77 -0.042 32 -0.045 41

3.25 -0.057 69 0.007 49 -0.018 32 -0.076 81

4.00 -0.061 42 -0.021 93 -0.121 47 -0.048 02

p=0.75

1.75 -0.031 58 -0.033 11 -0.006 91 -0.031 85

2.50 -0.048 15 -0.021 88 -0.051 01 -0.079 03

3.25 -0.021 10 -0.018 98 -0.066 13 -0.035 73

4.00 -0.027 41 -0.047 26 -0.088 01 -0.075 15

5 結 語

本研究將任務遷移和需求控制兩個重要的概念整合入模型中。結果模型被通過多負載多任務規模的成組調度，遷移和需求控制集成的虛擬器進行測試。多種指標都被應用以對滿配置情況下的性能和系統代價進行評估。

遷移和需求控制的應用對實驗模型有很深刻的影響。雖然遷移平衡了響應時間的差異，它們的總數量在系統性能問題上扮演了一個非常重要的角色，同時它們提供了一個新的比較基準。另外膨脹系數的差異提供了更好的調整機制以在不同的環境下獲得更好的結果。

在將來，我們希望對新的工作負載模型進行測試，以與云計算更好地進行適配。同樣對該機制在系統中各式各樣的應用，如果任何屬于實時云系統的結論被提出，性能因素都應該進行深入的研究。

參考文獻

[1] Z. C. Papazachos，H. D. Karatza.The impact of task service time variability on gang scheduling performance in a two-cluster system.Simul[J].Modell.Pract.Theory， 2009，17（7）：1276-1289.

[2] Y. Zhang， H. Franke， J. Moreira，et al.An integrated approach to parallel scheduling using gang-scheduling， backfilling， and migration[J]. Dept. of Electr. & Comput. Eng.，State Univ.of New Jersey，Piscataway，NJ， USA.IEEE Transactions on Parallel and Distributed Systems，2003， 14（3）：236-247.

[3] Y.Wiseman，D.G.Feitelson.Paired gang scheduling[J].IEEE Trans. Parallel Distrib. Syst.，2003，14（6）：581-592.

[4] A. M. Law.Simulation Modeling and Analysis[Z].4th ed. McGraw-Hill Higher Education， 2007.

[5] D. G. Feitelson.Metrics for parallel job scheduling and their convergence[Z].in Revis. Pap. from the 7th Int. Worksh. on Job Sched. Strateg. for Parallel Process.， ser. JSSPP 01. London， UK： Springer-Verlag， 2001：188-206.

[6] M. Guazzone， C. Anglano， M. Canonico.Energy-Efficient Resource Management for Cloud Computing Infrastructures[Z].presented at the Cloud Computing Technology and Science （CloudCom），IEEE 3rd Int. Conf.， 2011：424-431.

[7] F.R.Dogar，P.Steenkiste，K.Papagiannaki.Catnap： Exploiting high bandwidth wireless interfaces to save energy for mobile devices[Z].in Proc.ACM MobiSys10，San Francisco， California， 2010：107-122.

[8] N. Vallina-Rodriguez，J.Crowcroft.ErdOS： achieving energy savings in mobile OS[Z].in Proceedings of the sixth international workshop on MobiArch， ser. MobiArch 11. New York， NY， USA： ACM， 2011：37-42.

[9] 劉亮，向碧群，桂曉菁.基于云計算的多污染區域綜合檢測系統設計[J].計算機測量與控制，2012，20（8）：2089-2091.

[10] 張瀟丹，李俊.一種基于云服務模式的網絡測量與分析架構[J]. 計算機應用研究，2012，29（2）：725-729.

[11] G. Wang，T.S.E. Ng.The Impact of Virtualization on Network Performance of Amazon EC2 Data Center[Z].Proceedings of IEEE INFOCOM， 2010：1-9.

[12] V. Chang， G. Wills， D. De Roure.A Review of Cloud Business Models and Sustainability[Z].IEEE 3rd International Conference on Cloud Computing， 2010： 43-50.