云計(jì)算中多層次公平性QoS約束任務(wù)調(diào)度算法*

鄭迎鳳， 宋 朝， 趙文彬

(1. 黃河科技學(xué)院 網(wǎng)絡(luò)與信息技術(shù)研究所， 鄭州 450000； 2. 石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 石家莊 050043)

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

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

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

基于以上工作，本文將從新的視角研究云任務(wù)調(diào)度公平性問題，通過利用社會(huì)資源分配理論建立了一種任務(wù)調(diào)度的多重公平性QoS約束，以期實(shí)現(xiàn)云任務(wù)調(diào)度在多QoS約束下，最大程度地增強(qiáng)用戶對(duì)服務(wù)的滿意度.

1 模型描述

云計(jì)算中實(shí)體主要包括：用戶、資源提供者及調(diào)度系統(tǒng)，與之對(duì)應(yīng)的研究目標(biāo)則為用戶任務(wù)、資源以及調(diào)度策略.將社會(huì)福利分配公平性理論與云計(jì)算的資源分配問題進(jìn)行映射，如圖1所示.此時(shí)需要解決的問題是用戶任務(wù)的分類、任務(wù)公平性函數(shù)的定義、資源與任務(wù)的參數(shù)化以及任務(wù)與資源間的映射.

圖1 問題映射Fig.1 Problem mapping

1.1 基于QoS偏好的任務(wù)分類機(jī)制

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

1) 任務(wù)完成時(shí)間.對(duì)于用戶的實(shí)時(shí)性任務(wù)，通常要求任務(wù)完成時(shí)間應(yīng)盡可能短.

2) 網(wǎng)絡(luò)帶寬.若用戶運(yùn)行對(duì)網(wǎng)絡(luò)通信帶寬要求較高，則應(yīng)優(yōu)先考慮滿足帶寬需求.

為了根據(jù)不同的QoS參數(shù)度量用戶滿意度，需要對(duì)不同的QoS參數(shù)建立不同的量化評(píng)估標(biāo)準(zhǔn).

1.2 公平性約束

根據(jù)社會(huì)福利分配公平性原理，在云計(jì)算任務(wù)調(diào)度環(huán)境下建立了雙重公平性約束，如圖2所示.圖2中符號(hào)含義說(shuō)明如下：cx為局部結(jié)構(gòu)的目標(biāo)特征；Cx為參考結(jié)構(gòu)的目標(biāo)特征；gox為局部結(jié)構(gòu)的分配值；GOx為參考結(jié)構(gòu)的分配值.

在云任務(wù)調(diào)度環(huán)境中，圖2中變量可作如下映射：cx為用戶任務(wù)的特征；Ex為用戶任務(wù)的期望資源；Cx為參考結(jié)構(gòu)中用戶任務(wù)的QoS特征；gox為用戶任務(wù)實(shí)際的資源分配；GOx為一般期望效用，即認(rèn)可的合理分配標(biāo)準(zhǔn).

圖2 多重約束Fig.2 Multiple constraints

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

在云計(jì)算環(huán)境中，資源使用的公平性主要體現(xiàn)為：云調(diào)度系統(tǒng)能夠根據(jù)用戶的任務(wù)特征和QoS偏好，為任務(wù)提供合理有效的資源，使得不同的用戶獲得所需求的服務(wù)滿意度.定義云計(jì)算環(huán)境下的任務(wù)公平性和系統(tǒng)公平性如下：

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

對(duì)于任務(wù)Ti的公平性，可以通過評(píng)估函數(shù)進(jìn)行定義，即

(1)

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

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

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

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

在實(shí)際云計(jì)算任務(wù)調(diào)度環(huán)境中，資源實(shí)際分配量高于任務(wù)對(duì)資源的期望數(shù)量將有助于提高用戶的服務(wù)質(zhì)量，因此，實(shí)際環(huán)境中允許出現(xiàn)過多非公平性分配.公平性評(píng)估函數(shù)即是用來(lái)評(píng)估資源分配結(jié)果是否滿足公平性約束.

2) 系統(tǒng)公平性.令T={T1，T2，…，Tn}表示云系統(tǒng)中的任務(wù)集合，F(xiàn)={F1，F(xiàn)2，…，F(xiàn)n}表示與其對(duì)應(yīng)的公平性評(píng)估函數(shù)集合，則整個(gè)云系統(tǒng)的公平性評(píng)估函數(shù)可表示為

(2)

當(dāng)F達(dá)到最小值時(shí)，則表明整個(gè)用戶獲得了最大化的資源分配公平性要求，此時(shí)整個(gè)云系統(tǒng)的公平性要求也是最佳的，該參數(shù)即可用來(lái)優(yōu)化整個(gè)系統(tǒng)的全局公平性.

1.3 一般期望約束

由于用戶任務(wù)需要由系統(tǒng)提供的資源執(zhí)行，而用戶任務(wù)本身由于不同的應(yīng)用特征所具有的QoS偏好也不相同.根據(jù)圖2的含義，在參考結(jié)構(gòu)中QoS偏好對(duì)應(yīng)的資源分配量即稱為一般期望，且屬于公平性分配.因此，資源分配與任務(wù)調(diào)度過程中的公平性約束即是通過一般期望約束，根據(jù)用戶任務(wù)的QoS特征，建立資源與任務(wù)間的最優(yōu)映射過程.

根據(jù)一般期望約束的含義，即可優(yōu)化在局部結(jié)構(gòu)中的資源分配過程.用戶任務(wù)的QoS特征與任務(wù)和資源間的映射關(guān)系即可對(duì)應(yīng)為圖2中Cx與GOx間的關(guān)系.Cx與GOx間的映射關(guān)系可用于Cx與gox間的映射約束，因此，用戶任務(wù)可逐漸獲得公平性的資源分配.

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

1.4 任務(wù)與資源模型

云計(jì)算利用虛擬化技術(shù)將主機(jī)資源映射至虛擬機(jī)層，因此，云任務(wù)的調(diào)度主要實(shí)現(xiàn)于應(yīng)用層與虛擬機(jī)層.云計(jì)算使用戶任務(wù)所需資源以虛擬機(jī)形式進(jìn)行匹配，其資源映射過程即是尋找特定虛擬機(jī)資源的過程.

虛擬機(jī)的資源特征集合表示為

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

(3)

式中，RCi，1、RCi，2、RCi，3分別為云系統(tǒng)中虛擬機(jī)的CPU資源、內(nèi)存資源和帶寬資源.

虛擬機(jī)的性能集合表示為

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

(4)

式中，Pi，k為虛擬機(jī)特征RCi，k所對(duì)應(yīng)的性能取值.

為了約束資源分配過程的公平性，需要根據(jù)用戶任務(wù)的不同QoS目標(biāo)調(diào)整所選虛擬機(jī)資源的性能比率參數(shù).

任務(wù)類型i的一般期望集合表示為

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

(5)

且

(6)

式中，GEi，1、GEi，2、GEi，3分別為CPU數(shù)量權(quán)值、內(nèi)存權(quán)值和帶寬權(quán)值.

1.5 公平性評(píng)估函數(shù)計(jì)算

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

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

1.5.1 任務(wù)完成時(shí)間

云任務(wù)調(diào)度系統(tǒng)中，任務(wù)完成時(shí)間被選取作為評(píng)估標(biāo)準(zhǔn).假設(shè)云計(jì)算中虛擬機(jī)資源集合為VM={VM1，VM2，…，VMm}，其中，m表示虛擬機(jī)資源的總量.對(duì)于用戶任務(wù)Ti，具體處理過程如下：

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

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

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

(7)

式中：curXij為性能參數(shù)的當(dāng)前值；minXij為性能參數(shù)的最小值；maxXij為性能參數(shù)的最大值.

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

(8)

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

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

(9)

1.5.2 網(wǎng)絡(luò)帶寬

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

(10)

1.5.3 綜合一般期望效用

由于用戶任務(wù)通常具有多種類型的QoS需求，所以此時(shí)需要使用綜合一般期望，并從該點(diǎn)出發(fā)，選擇與GEi擁有最小Euclidean距離的虛擬機(jī)資源作為任務(wù)Ti的執(zhí)行資源.對(duì)于一般期望值初始向量的調(diào)整，可以通過定義閾值|Fi|≤1進(jìn)行約束，當(dāng)|Fi|>1時(shí)，系統(tǒng)會(huì)自動(dòng)調(diào)整一般期望值.任務(wù)可通過重復(fù)調(diào)度以獲取合理的一般期望向量.

1.6 算法設(shè)計(jì)

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

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

2) 根據(jù)參數(shù)化的用戶任務(wù)特征及與其對(duì)應(yīng)的一般期望約束，選擇最佳虛擬機(jī)資源執(zhí)行用戶任務(wù)；

3) 基于以上資源分配結(jié)果計(jì)算公平性評(píng)估函數(shù)的值，并統(tǒng)計(jì)用戶滿意度和調(diào)整模型.

2 仿真實(shí)驗(yàn)

本節(jié)利用仿真方法測(cè)試和驗(yàn)證任務(wù)調(diào)度算法CTS_QFC的有效性，仿真工具選取CloudSim平臺(tái)，實(shí)驗(yàn)主要是通過擴(kuò)展CloudSim中的DataCenterBroker類的bindCloudletToVM函數(shù)實(shí)現(xiàn)本文的任務(wù)調(diào)度算法.將最優(yōu)執(zhí)行時(shí)間OCT算法與文獻(xiàn)[4]的DRFH算法選取為比較算法，OCT算法的主要目標(biāo)是以任意次序?qū)⒚恳粋€(gè)任務(wù)調(diào)度至最小完成時(shí)間的資源上執(zhí)行.

2.1 實(shí)驗(yàn)配置

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

創(chuàng)建包括10個(gè)任務(wù)的用戶任務(wù)組，具體的參數(shù)配置如表1所示.表2為一組具有不同性能和偏好的虛擬機(jī)資源參數(shù)配置.

表1 任務(wù)參數(shù)配置Tab.1 Parameters setting of tasks

表2 虛擬機(jī)資源參數(shù)配置Tab.2 Parameters setting of virtual machine resources

2.2 實(shí)驗(yàn)結(jié)果與分析

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

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

圖3 任務(wù)執(zhí)行時(shí)間Fig.3 Execution time of tasks

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

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

圖5 計(jì)算能力偏好型任務(wù)Fig.5 Tasks of computing capacity preference

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

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

3 結(jié) 論

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