云計算中多層次公平性QoS約束任務調度算法*

鄭迎鳳， 宋 朝， 趙文彬

(1. 黃河科技學院 網絡與信息技術研究所， 鄭州 450000； 2. 石家莊鐵道大學 信息科學與技術學院， 石家莊 050043)

隨著數據量的指數級增長，越來越多的應用必須借助于云端資源來實現.云計算系統通過在云端整合各種類型的虛擬資源，可以實現對資源的統一化調度與管理[1].而當面對大規模多任務虛擬機資源分配與任務調度時，傳統的分配方法往往只注重分配效率，而忽略了資源對于執行任務的公平性問題.云計算環境中的資源供求關系類似于商品經濟模型，云資源提供者即等同于商品供應者，為用戶提供各類資源.資源用戶則等同于商品買家，為了獲得資源需求，買家需要支付費用.基于市場經濟模型的云任務調度算法即是建立資源提供者與資源消費者間的市場機制，并利用價格杠桿調整用戶需求與資源分配[2].眾所周知，高質量的服務與公平競爭原則是資源分配市場正常運行的基礎.在云計算環境中，不同用戶擁有不同類型的任務，隨著用戶數量的增加，云規模也將急劇擴展，此時，云計算的核心問題即是如何確保服務質量(quality of service，QoS)，并且為不同用戶提供使用云資源的公平機會.換言之，云計算的目標是如何使服務的用戶獲得更好的滿意度.

云計算是由經濟原則決定的一種新的計算模型，云計算中的資源分配行為與社會財富的分配行為具有極大的相似性.云計算中的資源分配問題更適合于以社會福利的分配理論進行求解，它不僅強調效率，更注重資源分配的公平性[3].

文獻[4]提出一種異構環境下的占優資源公平性分配(DRFH)算法，算法的目標是平衡多資源在任務上的公平分配，但算法得到的資源利用率相對較低；文獻[5]對DRFH算法進行了改進，提出了異構云中的占優資源聯合公平性分配(MDRF)算法，該算法雖然改善了資源利用率，但算法需要進行全局遍歷，復雜性過高；為了滿足公平性分配的條件，文獻[6]設計了一種多資源分配公平性度量模型，并在此基礎上提出了一種資源動態分配算法，為動態資源公平分配提供了定量分析工具；文獻[7]提出了基于信譽因子增強的公平性資源分配算法，算法通過信譽因子對資源使用進行評估，并引入懲罰性分配機制，增強資源分配的公平性保障，但算法同樣犧牲了資源的利用率；文獻[8]為了滿足不同的用戶需求，解決資源分配效率低和不均的問題，提出基于全局優勢的資源分配公平性(GDRF)算法，算法通過輪轉方式，以全局優勢資源共享比和全局優勢資源權重實現資源的公平性匹配；文獻[9]在文獻[8]基礎上進一步考慮了系統能耗的因素，從降低能耗的角度使資源得到公平利用；文獻[10]提出一種QoS分級任務調度模型，并根據任務制定不同的QoS約束，設計一種基于Chord優化算法的任務調度策略，使得QoS約束的任務可以獲得用戶滿意的執行時間；文獻[11]綜合考慮用戶任務截止時間和預算兩個QoS指標，提出了一種基于隸屬度函數的多QoS約束任務調度算法.

基于以上工作，本文將從新的視角研究云任務調度公平性問題，通過利用社會資源分配理論建立了一種任務調度的多重公平性QoS約束，以期實現云任務調度在多QoS約束下，最大程度地增強用戶對服務的滿意度.

1 模型描述

云計算中實體主要包括：用戶、資源提供者及調度系統，與之對應的研究目標則為用戶任務、資源以及調度策略.將社會福利分配公平性理論與云計算的資源分配問題進行映射，如圖1所示.此時需要解決的問題是用戶任務的分類、任務公平性函數的定義、資源與任務的參數化以及任務與資源間的映射.

圖1 問題映射Fig.1 Problem mapping

1.1 基于QoS偏好的任務分類機制

云計算環境中，QoS是用戶在執行任務過程中對云服務滿意度的一種度量.由于云計算的商業化特性，它需要為不同用戶提供滿足不同需求，即用戶對資源需求擁有不同偏好，而用戶本身的多樣性，導致此時的任務調度與資源分配將具有更高的復雜性.本文將對用戶任務依據QoS進行分類，重點考慮以下兩類QoS參數：

1) 任務完成時間.對于用戶的實時性任務，通常要求任務完成時間應盡可能短.

2) 網絡帶寬.若用戶運行對網絡通信帶寬要求較高，則應優先考慮滿足帶寬需求.

為了根據不同的QoS參數度量用戶滿意度，需要對不同的QoS參數建立不同的量化評估標準.

1.2 公平性約束

根據社會福利分配公平性原理，在云計算任務調度環境下建立了雙重公平性約束，如圖2所示.圖2中符號含義說明如下：cx為局部結構的目標特征；Cx為參考結構的目標特征；gox為局部結構的分配值；GOx為參考結構的分配值.

在云任務調度環境中，圖2中變量可作如下映射：cx為用戶任務的特征；Ex為用戶任務的期望資源；Cx為參考結構中用戶任務的QoS特征；gox為用戶任務實際的資源分配；GOx為一般期望效用，即認可的合理分配標準.

圖2 多重約束Fig.2 Multiple constraints

由于cx與Cx之間具有相似性，因此GOx對于決定gox具有參考性.為用戶任務進行資源分配時，gox與GOx之間所建立的約束關系將導致兩者趨于一致與收斂，即gox將等同于公平性分配.換言之，Cx、GOx與gox之間將形成約束關系，以確保資源選擇的公平性，Ex與gox之間進行定義公平性評估函數以評估資源分配的公平性.

在云計算環境中，資源使用的公平性主要體現為：云調度系統能夠根據用戶的任務特征和QoS偏好，為任務提供合理有效的資源，使得不同的用戶獲得所需求的服務滿意度.定義云計算環境下的任務公平性和系統公平性如下：

1) 任務公平性.對于任務而言，如果實際獲得的資源分配量是最大程度地接近于任務所期望的資源分配量，則稱任務的執行具有公平性.

對于任務Ti的公平性，可以通過評估函數進行定義，即

(1)

式中：α為一個常值，α∈(0，1]；Ma，i為任務Ti實際分配的資源量；Me，i為任務Ti期望分配的資源量.任務公平性具有以下3種情形：

① 如果Ma，i=Me，i，則Fi=0，表明此時的資源分配達到公平性分配；

② 如果Fi>0，則表明任務獲得了多于期望值的資源量，稱為過多非公平性分配；

③ 如果Fi<0，則表明任務未獲得期望的資源量，稱為過少非公平性分配.

在實際云計算任務調度環境中，資源實際分配量高于任務對資源的期望數量將有助于提高用戶的服務質量，因此，實際環境中允許出現過多非公平性分配.公平性評估函數即是用來評估資源分配結果是否滿足公平性約束.

2) 系統公平性.令T={T1，T2，…，Tn}表示云系統中的任務集合，F={F1，F2，…，Fn}表示與其對應的公平性評估函數集合，則整個云系統的公平性評估函數可表示為

(2)

當F達到最小值時，則表明整個用戶獲得了最大化的資源分配公平性要求，此時整個云系統的公平性要求也是最佳的，該參數即可用來優化整個系統的全局公平性.

1.3 一般期望約束

由于用戶任務需要由系統提供的資源執行，而用戶任務本身由于不同的應用特征所具有的QoS偏好也不相同.根據圖2的含義，在參考結構中QoS偏好對應的資源分配量即稱為一般期望，且屬于公平性分配.因此，資源分配與任務調度過程中的公平性約束即是通過一般期望約束，根據用戶任務的QoS特征，建立資源與任務間的最優映射過程.

根據一般期望約束的含義，即可優化在局部結構中的資源分配過程.用戶任務的QoS特征與任務和資源間的映射關系即可對應為圖2中Cx與GOx間的關系.Cx與GOx間的映射關系可用于Cx與gox間的映射約束，因此，用戶任務可逐漸獲得公平性的資源分配.

另外，資源分配過程的公平性約束可以通過一般期望約束完成，因此，需要根據用戶任務的QoS特征建立任務與資源間的映射關系.

1.4 任務與資源模型

云計算利用虛擬化技術將主機資源映射至虛擬機層，因此，云任務的調度主要實現于應用層與虛擬機層.云計算使用戶任務所需資源以虛擬機形式進行匹配，其資源映射過程即是尋找特定虛擬機資源的過程.

虛擬機的資源特征集合表示為

RCi={RCi，1，RCi，2，RCi，3}

(3)

式中，RCi，1、RCi，2、RCi，3分別為云系統中虛擬機的CPU資源、內存資源和帶寬資源.

虛擬機的性能集合表示為

Pi={Pi，1，Pi，2，Pi，3}

(4)

式中，Pi，k為虛擬機特征RCi，k所對應的性能取值.

為了約束資源分配過程的公平性，需要根據用戶任務的不同QoS目標調整所選虛擬機資源的性能比率參數.

任務類型i的一般期望集合表示為

GEi={GEi，1，GEi，2，GEi，3}

(5)

且

(6)

式中，GEi，1、GEi，2、GEi，3分別為CPU數量權值、內存權值和帶寬權值.

1.5 公平性評估函數計算

一般利用式(1)作為公平性評估函數評估資源分配結果的公平性.Fi值的計算需要通過用戶任務的期望資源分配量與實際資源分配量的比值獲得.由于用戶任務的QoS參數和云計算資源的參數之間擁有非一致的維度關系，并且兩者之間的映射關系是非線性的，因此需要建立維度的QoS需求與云計算資源參數之間的直接映射關系.期望資源分配量對應于Ex，實際資源分配量則對應于gox，一般期望的映射關系則對應于Cx與GOx之間的關系.

利用一般期望映射關系向量與實際資源分配中的歸一化資源參數向量的最小Euclidean距離約束gox與GOx之間的趨同，即可將社會福利公平性分配思想完美地融入云任務調度問題中.

1.5.1 任務完成時間

云任務調度系統中，任務完成時間被選取作為評估標準.假設云計算中虛擬機資源集合為VM={VM1，VM2，…，VMm}，其中，m表示虛擬機資源的總量.對于用戶任務Ti，具體處理過程如下：

1) 產生滿足任務執行條件的候選虛擬機資源集合VMi={VM1，VM2，…，VMk}，其中，k表示能夠滿足執行任務Ti條件的虛擬機資源總量.

2) 根據一般期望偏好約束從集合VMi中選擇最滿足任務期望的虛擬機執行用戶任務.

3) 對虛擬機的性能參數作歸一化處理，歸一化后其取值范圍為0～1之間，以實現一般期望值向量的統一比較.令Xij={X1j，X2j，…，Xij}表示VMi性能參數相同集合，歸一化后其值可表示為

(7)

式中：curXij為性能參數的當前值；minXij為性能參數的最小值；maxXij為性能參數的最大值.

利用式(5)將資源參數與用戶任務的一般期望GEi進行匹配，并計算兩者之間的Euclidean距離.當距離最小時，表明兩者間的相似性最佳.向量X={X1，X2，…，Xn}與向量Y={Y1，Y2，…，Yn}間Euclidean距離的計算方法為

(8)

任務Ti實際的總完成時間為tf=tw+te+ts，即任務提交至任務完成返回結果之間的時間，其中，tw為任務提交后任務等待資源處理的時間，te為任務在虛擬機資源上執行的時間，ts為任務的傳送時間.

任務Ti的期望完成時間texpt由用戶根據期望值指定分配，因此，式(1)可轉換為

(9)

1.5.2 網絡帶寬

帶寬需求適合于較頻繁的通信應用請求環境.本文首先根據式(7)對資源參數進行歸一化處理，然后，根據式(8)計算帶寬期望偏好的一般期望值向量的Euclidean距離，最后，將所調度任務映射至Euclidean距離最小的虛擬機上執行.令BWvm表示對于任務Ti從虛擬機上所獲得的實際帶寬，BWuser表示用戶任務期望的帶寬要求，因此，式(1)可轉換為

(10)

1.5.3 綜合一般期望效用

由于用戶任務通常具有多種類型的QoS需求，所以此時需要使用綜合一般期望，并從該點出發，選擇與GEi擁有最小Euclidean距離的虛擬機資源作為任務Ti的執行資源.對于一般期望值初始向量的調整，可以通過定義閾值|Fi|≤1進行約束，當|Fi|>1時，系統會自動調整一般期望值.任務可通過重復調度以獲取合理的一般期望向量.

1.6 算法設計

滿足多重公平性約束的多QoS云任務調度算法CTS_QFC(cloud tasks scheduling QoS algorithm meeting fairness constraint)的詳細過程如下：

1) 根據用戶任務的QoS分類，建立用戶任務的一般期望，以此作為資源分配與任務調度的公平性約束；

2) 根據參數化的用戶任務特征及與其對應的一般期望約束，選擇最佳虛擬機資源執行用戶任務；

3) 基于以上資源分配結果計算公平性評估函數的值，并統計用戶滿意度和調整模型.

2 仿真實驗

本節利用仿真方法測試和驗證任務調度算法CTS_QFC的有效性，仿真工具選取CloudSim平臺，實驗主要是通過擴展CloudSim中的DataCenterBroker類的bindCloudletToVM函數實現本文的任務調度算法.將最優執行時間OCT算法與文獻[4]的DRFH算法選取為比較算法，OCT算法的主要目標是以任意次序將每一個任務調度至最小完成時間的資源上執行.

2.1 實驗配置

為了與任務分類保持一致，不同任務的一般期望值的初始值是給定的，第1類任務GE1={0.7，0.1，0.2}，第2類任務GE2={0.3，0.2，0.5}，三個維度分別表示CPU數量權值、內存量權值和帶寬權值.

創建包括10個任務的用戶任務組，具體的參數配置如表1所示.表2為一組具有不同性能和偏好的虛擬機資源參數配置.

表1 任務參數配置Tab.1 Parameters setting of tasks

表2 虛擬機資源參數配置Tab.2 Parameters setting of virtual machine resources

2.2 實驗結果與分析

各算法任務完成時間如圖3所示.整體看來，CTS_QFC算法的執行效率差于OCT算法，但對于任務0～4，由于對計算能力的QoS偏好，其執行時間依然短于OCT算法.DRFH算法只注重公平性而忽略了執行效率，其執行時間普遍長于本文算法.

用戶滿意度比較結果如圖4所示.F=0表明用戶獲得了與期望一致的資源分配量；F>0表明用戶獲得了高于期望值的資源分配量；F<0表明用戶沒有獲得與期望相符合的資源分配量.可以看出，CTS_QFC算法得到的資源分配結果更加符合用戶的期望；OTC算法未考慮公平性分配問題，在任務4與7上均沒有得到滿足期望的資源分配；DRFH算法公平性方面強于OTC算法而弱于本文算法CTS_QFC，只有任務8上沒有得到期望資源分配，主要原因在于DRFH算法僅考慮了性能較強的占優資源的公平性分配問題.

圖3 任務執行時間Fig.3 Execution time of tasks

圖4 用戶滿意度Fig.4 Satisfaction of users

圖5為第1類任務0～4所獲得的CPU數量的對比圖.可以看出，CTS_QFC算法可以更好地滿足第1類任務對計算能力的需求，以更好的公平性滿足用戶的QoS偏好.另外兩種算法并未對任務按照QoS偏好進行分類，所分配的CPU數量只與用戶任務本身的要求相關，與任務的QoS偏好是無關的，其資源分配量是隨機的.

圖5 計算能力偏好型任務Fig.5 Tasks of computing capacity preference

圖6為第2類任務5～9所獲得的網絡帶寬量的對比圖.可以看出，該組任務對高帶寬擁有更高要求，CTS_QFC算法能夠更好地滿足其對該類資源的需求，以更好的公平性滿足用戶的QoS偏好.

圖6 帶寬能力偏好型任務Fig.6 Tasks of bandwidth capacity preference

3 結 論

本文利用社會福利分配中公平性分配理論對云任務調度問題進行分析與研究，提出了一種滿足公平性約束的云任務調度QoS算法.算法通過建立任務調度的多重公平性約束，將用戶任務對QoS的偏好進行分類，并利用定義的一般期望約束評估資源分配過程的公平性，通過評估結果實時修正資源分配公平性.實驗結果表明，算法不僅可以保證任務的執行效率，還可以更好地滿足任務調度與資源分配的公平性約束.