丁 丁, 艾麗華, 羅四維, 徐保民

(北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院, 北京 100044)

0 引 言

作為一種新興的并行計(jì)算技術(shù),云計(jì)算[1-3]是分布式處理、并行處理、網(wǎng)格計(jì)算的發(fā)展和延伸,是這些計(jì)算機(jī)科學(xué)概念的商業(yè)實(shí)現(xiàn),適應(yīng)當(dāng)今巨型信息化處理的需求。云計(jì)算的優(yōu)勢在于平臺能夠?qū)崿F(xiàn)資源的整合,并且可以為用戶按需提供規(guī)?？勺兊馁Y源,這給用戶帶來了極大的方便,同時(shí)也減少了資源的浪費(fèi)[4-5]。如今,云計(jì)算的商業(yè)應(yīng)用已成為現(xiàn)實(shí)。如Amazon的EC2(Elastic Compute Cloud)[6],Google的App Engine[7],IBM的Blue Cloud[8],Microsoft的Windows Azure[9]等云計(jì)算平臺都已出現(xiàn)在市場之上。學(xué)術(shù)界也紛紛從提高物理資源利用率、優(yōu)化平臺和應(yīng)用性能等諸多方面對云計(jì)算進(jìn)行了深層次的研究。

資源調(diào)度是云計(jì)算技術(shù)的一個(gè)重要組成部分,其效率直接影響整個(gè)云計(jì)算環(huán)境的工作性能,同時(shí)也決定了云計(jì)算用戶的參與和接受程度。圍繞著云計(jì)算中的資源調(diào)度問題,國內(nèi)外開展了一系列的研究工作,先后提出了各種調(diào)度算法。

在目前常見的開源云平臺中,實(shí)現(xiàn)和使用的調(diào)度策略多為傳統(tǒng)算法,如貪心算法、輪循算法、加權(quán)輪循算法等。此外,還有最小連接度及其改進(jìn)算法、目標(biāo)地址散列算法、源址散列算法等[10]。傳統(tǒng)算法普遍比較簡潔,通常只是單純的尋找滿足要求的物理結(jié)點(diǎn)運(yùn)行虛擬機(jī),一般不考慮整體的服務(wù)質(zhì)量(quality of service, QoS)和資源利用率。

啟發(fā)式智能算法是云計(jì)算資源調(diào)度主要采用的一類調(diào)度策略。目前,廣泛應(yīng)用的有基于遺傳算法、模擬退火算法、粒子群算法、蟻群算法的資源調(diào)度算法,以及這些算法的改進(jìn)算法[11-14]。啟發(fā)式智能算法的優(yōu)點(diǎn)是自適應(yīng)并且能夠較好地為NP難的資源調(diào)度問題尋找最優(yōu)或近似最優(yōu)解,一定程度上提高了算法的性能和資源利用率,但是算法本身和建模過程往往比較復(fù)雜,而且對于不同的問題,收斂性也會有所不同。

關(guān)于云計(jì)算環(huán)境中資源調(diào)度策略的另外一類研究來自于文獻(xiàn)[15-16],提出了基于市場的資源定位的云計(jì)算架構(gòu)和基于市場的資源調(diào)度策略,以支持服務(wù)級協(xié)商(service-level agreement, SLA)的資源定位。這種基于經(jīng)濟(jì)學(xué)模型的資源調(diào)度的基本思想是在資源消費(fèi)者和資源提供者之間建立市場機(jī)制,并把宏觀經(jīng)濟(jì)學(xué)和微觀經(jīng)濟(jì)學(xué)的各種模型應(yīng)用到資源調(diào)度過程中,利用價(jià)格杠桿對用戶需求和資源分配進(jìn)行調(diào)節(jié),從而優(yōu)化系統(tǒng)和提高效率。主要的調(diào)度方法包括基于一般經(jīng)濟(jì)模型的調(diào)度策略和用戶效用驅(qū)動的調(diào)度策略[17-18]。

除以上介紹的資源調(diào)度算法之外,還有一些綜合和改進(jìn)的調(diào)度算法,例如,在原有的調(diào)度算法中加入優(yōu)先級、QoS、信任機(jī)制等約束的算法。也有在原有算法之上改進(jìn),以提高算法的負(fù)載均衡性能,或者降低算法的能耗開銷等[19]。

以上研究通過不同的方法實(shí)現(xiàn)云計(jì)算環(huán)境下的資源調(diào)度,即接受來自于云計(jì)算用戶的資源請求,將資源池或云中滿足要求的資源分配給請求者。然而,隨著云計(jì)算的發(fā)展和廣泛應(yīng)用,云計(jì)算環(huán)境中用戶的需求不斷地變化,資源的種類、數(shù)量等也持續(xù)地增加,并以各種不同形式出現(xiàn)。面對種類日新月異、數(shù)量日益巨大的云計(jì)算資源,用戶的需求表達(dá)越來越難以得到滿足。除此之外,在現(xiàn)實(shí)的云計(jì)算環(huán)境中,當(dāng)用戶對云計(jì)算平臺進(jìn)行資源請求時(shí),由于所面對的信息常常是不完整的、不確定的,甚至是模糊的,往往也無法精確地給出資源的種類、數(shù)量等需求,或者只能在最關(guān)注的某一方面或某幾個(gè)方面提出詳細(xì)的需求說明,而忽略了其他方面。這些都對云計(jì)算環(huán)境下的資源調(diào)度提出了更高、更新的要求,即如何根據(jù)當(dāng)前有限的用戶需求信息,探索更加有效的信息提取、過濾和分析技術(shù)以獲取用戶的真實(shí)目的,從而在資源調(diào)度中反饋給用戶更加準(zhǔn)確的資源?；诖?本文嘗試從用戶的角度出發(fā),從用戶行為的全新角度著手,運(yùn)用用戶本身的行為信息,挖掘出更多的用戶需求信息,支持資源調(diào)度完成。具體的做法是通過結(jié)合相關(guān)反饋機(jī)制將用戶調(diào)度等行為信息融入到資源調(diào)度過程中,利用用戶行為所體現(xiàn)出的相關(guān)性和穩(wěn)定性,建立資源調(diào)度的主動發(fā)現(xiàn)網(wǎng)絡(luò)和反饋網(wǎng)絡(luò),深層挖掘用戶的真實(shí)意圖,研究面向用戶需求的調(diào)度機(jī)制,從而為具有不同需求的用戶提供有保障的服務(wù),從根本上提高云計(jì)算的服務(wù)水平,實(shí)現(xiàn)對云計(jì)算環(huán)境的規(guī)范化和高效管理。

1 調(diào)度模型及相關(guān)定義

1.1 調(diào)度模型

為簡化問題,不考慮任務(wù)的跨節(jié)點(diǎn)執(zhí)行,假設(shè)用戶向系統(tǒng)提交的任務(wù)就是資源調(diào)度器進(jìn)行任務(wù)分配的最小單位,大型任務(wù)的分解由用戶來完成。任務(wù)集由m個(gè)相互獨(dú)立的元任務(wù)組成,記為T={t1,t2,…,tm}。用到的云系統(tǒng)可抽象為n個(gè)異構(gòu)資源,記為R={r1,r2,…,rn}。每個(gè)資源節(jié)點(diǎn)都可以將數(shù)據(jù)傳輸?shù)狡渌我庖粋€(gè)資源節(jié)點(diǎn)上,當(dāng)任務(wù)被調(diào)度到不同地理位置的資源節(jié)點(diǎn)上運(yùn)行時(shí),存取所需數(shù)據(jù)的花費(fèi)有可能相差很大。

1.1.1 相關(guān)定義

為了從用戶的角度研究云計(jì)算環(huán)境下的資源調(diào)度問題,對用戶需求的分析就顯得至關(guān)重要。考慮到云計(jì)算運(yùn)行過程中用戶的實(shí)際需求,從最低需求和用戶偏好兩個(gè)方面對用戶的差異性需求進(jìn)行建模,使用二元組對用戶提交的任務(wù)ti(ti∈T,1≤i≤m)表示為

ti=(tri,tpi)

式中,tri為用戶任務(wù)ti的最低需求;tpi為用戶任務(wù)ti的偏好。tri、tpi均可在用戶提交任務(wù)時(shí)得到。

事實(shí)上,用戶的需求往往是多方面的,可以包括時(shí)間性需求、安全性需求、可靠性需求、可信性需求、費(fèi)用需求等。不失一般性,假設(shè)用戶需求的維度是d,則用戶任務(wù)的最低需求tri定義為

tri=[tri1,tri2,…,trid]

同理,用戶任務(wù)的偏好tpi定義為

tpi=[tpi1,tpi2,…,tpid]

本文研究的重點(diǎn)是基礎(chǔ)設(shè)施即服務(wù)(infrastructure-as-a-service,IaaS)層的資源調(diào)度,即對底層硬件資源進(jìn)行分配,每個(gè)系統(tǒng)資源由多個(gè)資源特征進(jìn)行描述。不失一般性,假設(shè)資源特征的個(gè)數(shù)為f,則資源rj(rj∈R,1≤j≤n)的特征向量rfj定義為

rfj=[rfj1,rfj2,…,rfjf]

所有n個(gè)系統(tǒng)資源的特征矩陣可以表示為

1.1.2 數(shù)據(jù)預(yù)處理

在實(shí)際應(yīng)用中,不同的任務(wù)需求往往具有不同的表達(dá)形式和數(shù)值范圍,因此,為了進(jìn)行綜合評價(jià),首先需要對各個(gè)任務(wù)需求的值進(jìn)行歸一化處理,使得所有任務(wù)需求的值具有可比性?？梢圆捎米钚?最大規(guī)格化等方法對任務(wù)需求矩陣TR中任務(wù)需求的取值進(jìn)行線性變換,消除不同量綱對調(diào)度結(jié)果的影響。

歸一化處理后,任務(wù)需求矩陣TR中的每一個(gè)trik(1≤i≤m,1≤k≤d)都將滿足

0≤trik≤1

(1)

對于用戶的偏好,簡單地說,其本質(zhì)是用戶對不同任務(wù)需求的重視程度存在差異。根據(jù)自己的實(shí)際需要,用戶可能更關(guān)注其中的某些任務(wù)需求而不重視其他需求,這是實(shí)際應(yīng)用中的常態(tài)。因此,需要用戶綜合考慮任務(wù)需求的所有維度,對各個(gè)任務(wù)需求的重視程度進(jìn)行衡量。本文考慮采用層次分析法(analytic hierarchy process, AHP)[20]對各個(gè)任務(wù)需求偏好進(jìn)行兩兩對比,盡可能降低由于主觀判斷不一致造成的影響,使用戶的偏好信息通過量化比較得以體現(xiàn)和傳遞,從而實(shí)現(xiàn)對用戶的按需服務(wù)。經(jīng)過AHP的處理,任務(wù)偏好矩陣TP中的每一個(gè)tpik(1≤i≤m,1≤k≤d)都將滿足

(2)

對于資源的特征矩陣RF中資源特征的取值進(jìn)行歸一化處理,使RF中每一個(gè)rfjk(1≤j≤n,1≤k≤f)都滿足

0≤rfjk≤1

(3)

此外,由于RF中的特征向量往往是基于低層次的特征信息進(jìn)行描述的,如硬件平臺、操作系統(tǒng)、最小內(nèi)存或磁盤空間需求等。而用戶習(xí)慣用一些高層次概念對任務(wù)需求進(jìn)行描述,這就使得用戶的需求和資源的特征常常不在一個(gè)層次上,因此,對資源的特征矩陣RF中的數(shù)據(jù)進(jìn)行進(jìn)一步的預(yù)處理,將低層次的資源特征信息映射到高層次的用戶需求信息上,同時(shí)去掉資源的特征矩陣RF中多余的特征信息,使特征矩陣RF與任務(wù)需求矩陣TR保持在相同的維度d上,即

rfj=[rfj1,rfj2,…,rfjf]

2 基于用戶行為反饋的云資源調(diào)度

2.1 算法基本思想

在云計(jì)算環(huán)境中,不同的用戶對資源的需求雖然各不相同,但是有研究表明[21-22],對于同一個(gè)用戶來說,他/她的行為方式在一段時(shí)間內(nèi)是比較穩(wěn)定的,也就是說,用戶未來請求的資源和其之前使用過的資源極可能是相似的、甚至是相同的。例如,如果之前用戶在Amzon上購買了一些商品,那么Amzon就會“記住”用戶購物歷史,并且在用戶再次回來購物時(shí)試圖推薦類似的東西。這恰恰正是基于用戶過去的需求和未來需求之間相對穩(wěn)定的關(guān)系。在其他一些更加正式的應(yīng)用中,一些基于趨勢、或者季節(jié)性和周期性數(shù)據(jù)的預(yù)測也是使用用戶歷史記錄來預(yù)測用戶未來行為的例子。本文正是從用戶行為所體現(xiàn)出的這種穩(wěn)定性出發(fā),結(jié)合相關(guān)反饋技術(shù),建立用戶需求的主動發(fā)現(xiàn)網(wǎng)絡(luò)和反饋網(wǎng)絡(luò),基于用戶行為反饋實(shí)現(xiàn)面向用戶需求的資源調(diào)度。

相關(guān)反饋是信息檢索系統(tǒng)中一種用戶指導(dǎo)性學(xué)習(xí)的技術(shù),通過與用戶的交互來優(yōu)化查詢。按照用戶最初給定的查詢條件,系統(tǒng)返回給用戶查詢結(jié)果,用戶可以人為地或者由系統(tǒng)自動地選擇最符合用戶查詢意圖的返回結(jié)果作為正反饋,或者最不符合用戶查詢意圖的返回結(jié)果作為負(fù)反饋,系統(tǒng)根據(jù)這些不斷變化的反饋信息來更新查詢條件,重新進(jìn)行查詢,從而使隨后的搜索更符合查詢者的真實(shí)意圖。根據(jù)相關(guān)反饋的思想,將云計(jì)算環(huán)境下的資源調(diào)度也看作是一個(gè)分類問題,將用戶交互過程作為一種訓(xùn)練過程,把用戶的歷史調(diào)度信息作為正向訓(xùn)練數(shù)據(jù)對資源調(diào)度過程進(jìn)行反饋控制,使資源調(diào)度的結(jié)果與用戶的主觀感知更加接近,確保用戶任務(wù)按照其期望值更好地被執(zhí)行。

2.2 算法描述

本文從用戶的角度著手,基于用戶行為對云資源調(diào)度問題進(jìn)行研究,提出了基于用戶行為反饋的資源調(diào)度機(jī)制(user behavior-based resource scheduling mechanism with feedback control, UBRSM-FC)。UBRSM-FC將用戶調(diào)度等行為信息融入到資源調(diào)度過程中,并引入相關(guān)反饋機(jī)制對調(diào)度過程不斷微調(diào)和優(yōu)化,因此,是一個(gè)逐步求精的過程。具體過程如算法1所示。

算法1基于用戶行為反饋的資源調(diào)度機(jī)制

輸入TR,TP和RF

匹配閾值θ

最大循環(huán)次數(shù)γ

輸出為每一個(gè)用戶任務(wù)分配合適的資源

01 fori:=1 tomdo

02 do

03t=0

04 forj:=1 tondo

05 計(jì)算tri、rfj之間的相似性

06 if sim(tri,rfj)≥θthen

07ARi←rj

08 endif

09 endfor

10 ifARi=? then

11 ift=0 then

12 return “無滿足用戶需求的資源”

13 endif

14 break;

15 endif

16 ifARi中只有一個(gè)滿足用戶需求的資源then

17 將這個(gè)唯一滿足條件的資源分配給當(dāng)前的用戶任務(wù)ti

18 endif

19 ifARi中存在多個(gè)滿足用戶需求的資源then

20 forj:=1 tondo

21 計(jì)算用戶任務(wù)在每個(gè)可用資源rj上運(yùn)行的效益

22 endfor

23 將效益最大的資源分配給當(dāng)前的用戶任務(wù)ti

24 endif

25 更新用戶任務(wù)ti的TR和TP

26t=t+1

27 untilt>γ

28 endfor

整個(gè)調(diào)度算法在一個(gè)for循環(huán)的控制下完成,每次循環(huán)處理一個(gè)用戶任務(wù)。每個(gè)用戶任務(wù)的調(diào)度過程分為資源匹配、資源選擇和基于用戶行為的反饋3個(gè)階段,這3個(gè)階段循環(huán)完成,循環(huán)由參數(shù)t控制,循環(huán)的次數(shù)設(shè)為γ,一般取經(jīng)驗(yàn)值。

2.2.1 資源匹配

首先是資源匹配階段(算法1第4～9步)。資源匹配的主要功能是按照用戶需求查找資源,獲得所有符合條件的資源列表的過程。因此,需要根據(jù)用戶的需求(調(diào)度初始時(shí)只包括用戶提交的資源請求中的最低需求,之后還包括經(jīng)過反饋網(wǎng)絡(luò)反饋回來的用戶需求信息),按照一定的算法與資源集內(nèi)的所有資源進(jìn)行相似性匹配。

給定用戶任務(wù)ti(ti∈T,1≤i≤m),則該用戶任務(wù)的資源需求與資源集內(nèi)任一資源rj(rj∈R,1≤j≤n)特征的相似性可通過余弦相似度計(jì)算方法得到,表示為

(4)

式中,sim(tri,rfj)即為用戶任務(wù)ti的資源需求和資源rj在特征描述上的相似度；trik為用戶任務(wù)ti第k維的資源需求,trik與rfjk對應(yīng)。如果計(jì)算出的相似度大于給定的匹配閾值θ,就認(rèn)為資源rj的特征與用戶任務(wù)ti的資源需求相似,重復(fù)計(jì)算資源集R中的所有資源,最終返回給用戶任務(wù)ti一個(gè)候選資源集ARi，表示為

ARi={rj|sim(tri,rfj)≥θ,rj∈R,j=1,2,…,n}

(5)

2.2.2 資源選擇

接下來是資源選擇階段,資源選擇主要負(fù)責(zé)在資源匹配得到的候選資源集中根據(jù)資源調(diào)度策略選擇適合的資源,比如使用戶費(fèi)用最低,或者系統(tǒng)性能最高等,并將資源分配到相應(yīng)的請求中。

算法1第10～24步對候選資源集ARi所有可能的結(jié)果分情況進(jìn)行處理:當(dāng)ARi=?時(shí),表示本次循環(huán)沒有滿足用戶需求的資源可用,此時(shí)即使沒有達(dá)到指定的循環(huán)次數(shù)γ,循環(huán)也會被終止;當(dāng)ARi中只有1個(gè)滿足用戶需求的資源時(shí),按照盡量保證用戶任務(wù)能夠完成的原則,不計(jì)較運(yùn)行的效益,直接將這個(gè)唯一滿足條件的資源分配給該任務(wù);算法1第19～24步對ARi中存在多個(gè)可用資源的情況進(jìn)行處理,此時(shí)有多個(gè)滿足用戶需求的資源可供選擇,調(diào)度算法需要計(jì)算用戶任務(wù)在各個(gè)資源上運(yùn)行的效益來決定任務(wù)的分配。

不失一般性,假設(shè)給定用戶任務(wù)ti(ti∈T,1≤i≤m),則該用戶任務(wù)運(yùn)行在資源rj(rj∈R,1≤j≤n)上的效益函數(shù)為

(6)

(7)

在這種“差距”的計(jì)算中,直接用rfjk和trik相減。如果rfjk-trik>0,代表資源能夠滿足用戶任務(wù)的資源需求,“差距”直接體現(xiàn)為兩個(gè)數(shù)的差值,即rfjk-trik;如果rfjk-trik<0,代表資源不能滿足用戶任務(wù)的資源需求,此時(shí)如果存在其他可以滿足用戶需求的資源(差值為正數(shù)的資源),則首先應(yīng)考慮那些資源。因此將這些為負(fù)數(shù)的差值取絕對值后加上這一維度上差值絕對值的最大值,使處理后的數(shù)值一定大于原有的差值為正的資源的差值,保證差值為負(fù)的資源的優(yōu)先級低于差值為正的資源優(yōu)先級。而且在沒有滿足用戶需求的資源存在的情況下,同樣都是差值為負(fù)的數(shù)值經(jīng)過這樣的處理后,仍然保持差值越小,優(yōu)先級越大,被選中運(yùn)行的可能性越大;在rfjk-trik=0的特殊情況下,為了避免式(6)中效益函數(shù)的分母為0,取這一維度上所有差值絕對值的最小值,以保證這種情況的優(yōu)先級最高。

最后,式(6)取處理后數(shù)值的倒數(shù),與用戶偏好矩陣TP中相應(yīng)的元素相乘,目的是體現(xiàn)用戶在不同需求維度上的偏好程度。處理后元素取倒數(shù)使得原來越小的數(shù)得到的結(jié)果越大,這樣,計(jì)算用戶任務(wù)在所有滿足條件的資源上的效益,取獲得效益最大的資源進(jìn)行分配。

2.2.3 基于用戶行為的反饋

在資源選擇階段,根據(jù)已得到的候選資源集,用戶會最終選取能最大化某種評價(jià)標(biāo)準(zhǔn)的資源。這種資源選擇的結(jié)果實(shí)際上反映的就是用戶需求與對應(yīng)資源之間的關(guān)系,這本身也包含了大量的用戶行為信息,而且起著重要的導(dǎo)向作用。如果能將這些資源選擇結(jié)果的相關(guān)信息進(jìn)行反饋,如哪些資源是用戶已經(jīng)調(diào)用的,或者可以調(diào)用的,那么就可以通過對這些信息的分析進(jìn)而獲得用戶的行為信息,幫助云系統(tǒng)主動發(fā)現(xiàn)和收集用戶潛在的需求,進(jìn)一步挖掘出用戶的真實(shí)需求。正是基于這樣的想法,把用戶這種資源調(diào)用作為用戶行為的體現(xiàn),結(jié)合相關(guān)反饋機(jī)制,將最終選取資源的相關(guān)信息作為正反饋對調(diào)度過程進(jìn)行微調(diào)和優(yōu)化,實(shí)現(xiàn)基于用戶行為的反饋。一方面對任務(wù)需求矩陣TR進(jìn)行更新,利用這種交互行為所反饋回來的行為信息輔助完成資源的匹配;另一方面對任務(wù)偏好矩陣TP進(jìn)行更新,輔助完成最終資源的選擇。

給定用戶任務(wù)ti(ti∈T,1≤i≤m),假設(shè)rs是用戶在資源選擇階段選取的資源,根據(jù)rs被用作正反饋的概率,可以得到任務(wù)ti用戶需求和偏好的更新公式分別為

(8)

(9)

式中,p(rs)即為rs被用作正反饋的概率,可以從用戶的歷史調(diào)度信息中計(jì)算得到。

這種基于用戶行為的反饋會在資源選擇后自動完成,更新后的任務(wù)需求矩陣和任務(wù)偏好矩陣將作為下一個(gè)調(diào)度循環(huán)的初始條件,實(shí)現(xiàn)用戶需求信息的主動發(fā)現(xiàn)和收集。而且這個(gè)反饋過程會反復(fù)進(jìn)行,使隨后的調(diào)度過程更加符合查詢者的真實(shí)意圖,實(shí)現(xiàn)用戶需求的自動調(diào)節(jié)。

達(dá)到指定的循環(huán)次數(shù)γ后,反饋過程終止,一個(gè)用戶任務(wù)的調(diào)度結(jié)束。上述過程重復(fù)執(zhí)行m次可以完成全部m個(gè)用戶任務(wù)的資源調(diào)度過程。

2.3 算法性能分析

基于用戶行為反饋的資源調(diào)度算法UBRSM-FC通過循環(huán)的方式為每一個(gè)用戶任務(wù)尋找效益最大的資源進(jìn)行分配,而每一次分配都要對資源在各個(gè)需求維度上的表現(xiàn)進(jìn)行比較和處理,因此,算法的時(shí)間復(fù)雜度與用戶任務(wù)的數(shù)目m、資源的數(shù)目n以及用戶需求維度d都有密切的關(guān)系。同時(shí),由于算法加入了反饋的環(huán)節(jié),因此,算法的時(shí)間復(fù)雜度與反饋的循環(huán)次數(shù)γ也息息相關(guān)。最差情況下,整個(gè)算法的時(shí)間復(fù)雜度為O(mγ(nd+nd+d))=O(mγnd),這比傳統(tǒng)調(diào)度算法的時(shí)間復(fù)雜度O(mnd)[23]要高一些,與一些涉及迭代次數(shù)的調(diào)度算法(例如一些利用遺傳算法進(jìn)行調(diào)度的策略)的時(shí)間復(fù)雜度差不多。

3 實(shí)驗(yàn)與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境與設(shè)置

本文采用仿真工具CloudSim(版本3.0.3)模擬實(shí)驗(yàn)云環(huán)境,實(shí)驗(yàn)硬件配置為HP Elitedesk800計(jì)算機(jī),i7-4790 CPU,主頻3.6GHz,內(nèi)存4 GB。實(shí)驗(yàn)設(shè)置了2個(gè)數(shù)據(jù)中心,分別對應(yīng)300個(gè)虛擬機(jī)和700個(gè)虛擬機(jī)。不同虛擬機(jī)的計(jì)算能力、存儲能力、帶寬等性能可能相差很大,用來模擬總共1 000個(gè)高異構(gòu)的系統(tǒng)資源。隨機(jī)生成了300個(gè)云任務(wù)代表用戶的資源請求。用戶請求的到達(dá)符合泊松分布。除此之外,實(shí)驗(yàn)中擴(kuò)展了云任務(wù)的屬性,使每個(gè)用戶請求具有4個(gè)在實(shí)際應(yīng)用中常用的需求維度,包括時(shí)間性需求、安全性需求、可靠性需求以及花費(fèi)需求。用戶請求的時(shí)間性需求定義為用戶任務(wù)的最遲完成時(shí)間,可靠性需求定義為用戶要求的最小成功完成概率,安全性需求定義為用戶要求的安全保障等級,花費(fèi)需求定義為用戶可以承擔(dān)的最高花費(fèi)。同樣,也擴(kuò)展了虛擬機(jī)的屬性,使每個(gè)資源的特征向量也可以經(jīng)過預(yù)處理映射到這4個(gè)維度上。具體的映射方法可參考文獻(xiàn)[24]。

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

通過3組實(shí)驗(yàn)對基于用戶行為反饋的資源調(diào)度算法UBRSM-FC的性能進(jìn)行說明。第1組實(shí)驗(yàn)考察算法本身的運(yùn)行時(shí)間,第2組實(shí)驗(yàn)從用戶角度出發(fā)衡量算法的用戶滿意度,第3組實(shí)驗(yàn)從系統(tǒng)的角度出發(fā)衡量算法的資源利用率。對每種情況實(shí)驗(yàn)100次,然后統(tǒng)計(jì)平均值。

3.2.1 運(yùn)行時(shí)間

運(yùn)行時(shí)間是算法產(chǎn)生給定任務(wù)集的調(diào)度結(jié)果所經(jīng)過的時(shí)間跨度。通常,運(yùn)行時(shí)間越小,算法越實(shí)用。表1是具有反饋控制的調(diào)度算法UBRSM-FC與不進(jìn)行反饋控制的調(diào)度算法(簡寫為UBRSM)的運(yùn)行時(shí)間對比。

表1 調(diào)度算法運(yùn)行時(shí)間比較

如表1所示,具有反饋控制的調(diào)度算法UBRSM-FC的運(yùn)行時(shí)間比不進(jìn)行反饋控制的調(diào)度算法UBRSM的運(yùn)行時(shí)間要高一些。這是因?yàn)閁BRSM-FC算法需要花費(fèi)一些額外的時(shí)間在資源選擇之后對任務(wù)需求矩陣和任務(wù)偏好矩陣進(jìn)行更新。當(dāng)然,從表1中最后一列的數(shù)據(jù)可以看出,隨著用戶數(shù)量的增加,這些時(shí)間花費(fèi)在總的時(shí)間成本中所占的比重會越來越小,甚至可以忽略不計(jì)。

但是,表1中記錄的是UBRSM-FC沒有進(jìn)行反饋循環(huán)之前的運(yùn)行時(shí)間,反饋循環(huán)開始后,運(yùn)行時(shí)間將會隨著反饋循環(huán)的次數(shù)成比例增長。然而,這些代價(jià)通常是可以接受的。這是因?yàn)?在實(shí)際情況中,相對于用戶任務(wù)的數(shù)目和系統(tǒng)資源的數(shù)目,反饋的循環(huán)次數(shù)一般都小得多,可能只是個(gè)位數(shù)。而且,反饋循環(huán)結(jié)束后,最終的任務(wù)需求矩陣和任務(wù)偏好矩陣將會存儲在系統(tǒng)中,并作為同一用戶下一次任務(wù)請求的初始條件,直到該用戶明確修改其用戶需求和用戶偏好的參數(shù)值。這在一定程度上可以幫助系統(tǒng)主動發(fā)現(xiàn)用戶的潛在需求,降低用戶使用云系統(tǒng)的難度。事實(shí)上,從長遠(yuǎn)的角度來看,基于用戶行為反饋的資源調(diào)度算法就是通過增加一些反饋循環(huán)上的開銷來挖掘用戶的真實(shí)需求,提高用戶使用云系統(tǒng)的滿意程度。

3.2.2 用戶滿意度

用戶滿意度是用戶對調(diào)度結(jié)果的滿意程度。在本文中,用調(diào)度結(jié)果與用戶需求之間的匹配程度來衡量用戶滿意度。給定用戶ti(ti∈T,1≤i≤m),用戶滿意度USDi具體定義為

(10)

圖1展示了匹配閾值θ分別取0.2,0.5,0.8三種情況中不同反饋循環(huán)次數(shù)下用戶滿意度的變化。

圖1 UBRSM-FC的用戶滿意度Fig.1 User satisfaction degree of UBRSM-FC

從圖1可以看出,只要匹配閾值θ設(shè)置在合理范圍內(nèi)(這里綜合考慮用戶滿意度和時(shí)間成本兩方面,取平衡值0.5),2次反饋循環(huán)后,基于用戶行為反饋的資源調(diào)度算法UBRSM-FC就可以取得超過80%的用戶滿意度,而且,隨著反饋循環(huán)次數(shù)的不斷增加,4次反饋循環(huán)后,算法的用戶滿意度可以達(dá)到將近90%的用戶滿意度。這樣的結(jié)果主要得益于基于用戶行為的反饋機(jī)制的引入,通過反饋循環(huán)對調(diào)度過程不斷微調(diào)和優(yōu)化,使得隨后的調(diào)度過程更加符合查詢者的真實(shí)意圖,提高了用戶的滿意度。

同樣注意到,6次反饋循環(huán)后,算法用戶滿意度的變化不再明顯,此時(shí)算法的用戶滿意度已達(dá)到近95%。這比不進(jìn)行反饋控制的調(diào)度算法70%多的用戶滿意度,即圖1中反饋次數(shù)為0的數(shù)據(jù),要高出近20%。這也意味著,算法通過有限的反饋循環(huán)就可以達(dá)到一個(gè)比較有效和穩(wěn)定的狀態(tài)。

3.2.3 資源利用率

系統(tǒng)資源利用率是以系統(tǒng)的角度衡量調(diào)度算法的一個(gè)重要指標(biāo)。在本文中,資源的利用率可以用被使用的資源負(fù)載容量總和與系統(tǒng)資源可使用負(fù)載容量總和的比值來計(jì)算。在這一部分,將本文提出的基于用戶行為反饋的資源調(diào)度算法UBRSM-FC與傳統(tǒng)的先來先服務(wù)算法(first come first serve,FCFS)的資源利用率進(jìn)行對比。采用先來先服務(wù)算法FCFS的主要原因是該算法是CloudSim自帶的調(diào)度算法,同時(shí)也是用來與優(yōu)化算法進(jìn)行性能比較最常見的調(diào)度算法。圖2展示了不同用戶任務(wù)數(shù)量下兩種算法系統(tǒng)資源利用率的變化。

圖2 資源利用率比較Fig.2 Resource utilization rate comparision

從圖2可以看出,隨著用戶任務(wù)數(shù)從50增加到300,兩種算法的資源利用率都在不斷提高。原因很明顯,因?yàn)楦嗟挠脩羧蝿?wù)意味著將有更多的系統(tǒng)資源將被占用。但是無論用戶任務(wù)數(shù)目如何變化,相對于FCFS算法,UBRSM-FC算法的系統(tǒng)資源利用率總是要高一些。這是因?yàn)閁BRSM-FC算法能夠篩選出與用戶任務(wù)需求最接近的資源,而不是性能最優(yōu)的資源,避免將能力過高的資源分配給需求過低的任務(wù),使系統(tǒng)資源的利用率得到提高。因此,UBRSM-FC算法更能夠體現(xiàn)云平臺充分利用系統(tǒng)空閑資源的特點(diǎn)。

4 結(jié)束語

作為互聯(lián)網(wǎng)資源利用的新模式,云計(jì)算的商業(yè)性使其調(diào)度機(jī)制更加關(guān)注用戶的需求。然而,云計(jì)算中的資源具有異構(gòu)性、自治性的特點(diǎn),而且往往是分布式的,云計(jì)算中用戶的需求也千差萬別,這些都使得云計(jì)算環(huán)境下的資源調(diào)度問題更加復(fù)雜。因此,如何在云計(jì)算資源中獲取用戶真實(shí)所需的資源,實(shí)現(xiàn)高效、經(jīng)濟(jì)、準(zhǔn)確的資源調(diào)度是當(dāng)前迫切需要解決的問題,這就要求研究人員根據(jù)云計(jì)算的發(fā)展趨勢,做出準(zhǔn)確分析提出新的方法。

針對這一問題,從用戶的角度著手,基于用戶行為對資源調(diào)度問題進(jìn)行深入的研究:通過引入相關(guān)反饋機(jī)制,將用戶行為信息融入到資源調(diào)度過程中,在此基礎(chǔ)上,提出了基于用戶行為反饋的資源調(diào)度機(jī)制,深層挖掘用戶的真實(shí)意圖,實(shí)現(xiàn)面向用戶需求的資源調(diào)度,從而為具有不同需求的用戶提供有保障的服務(wù)?？傮w來說,這種基于用戶行為反饋的資源調(diào)度機(jī)制具有以下優(yōu)點(diǎn):

首先,用戶作為云計(jì)算的最終使用者,對云計(jì)算的發(fā)展起著重要的作用。因此,從用戶的角度出發(fā),根據(jù)用戶的不同興趣、愛好和領(lǐng)域等用戶行為信息對云計(jì)算環(huán)境下的資源調(diào)度問題進(jìn)行研究,符合云計(jì)算的發(fā)展方向;

其次,這種方法是面向用戶的,可以針對每個(gè)用戶的特點(diǎn)進(jìn)行個(gè)性化的資源反饋分析,實(shí)現(xiàn)用戶需求的主動發(fā)現(xiàn)和收集;

再次,這種方法具備學(xué)習(xí)的功能,通過多次反饋,可以對用戶需求進(jìn)行自動的調(diào)節(jié),使結(jié)果更加符合用戶的真實(shí)需求。

模擬實(shí)驗(yàn)進(jìn)一步證明,這種基于用戶行為反饋的資源調(diào)度機(jī)制能夠在最大程度滿足用戶需求的同時(shí),兼顧系統(tǒng)資源的利用率,更加符合開放、復(fù)雜的云計(jì)算環(huán)境。

今后,將進(jìn)一步嘗試更加簡單有效的方法,對用戶需求矩陣和用戶偏好矩陣進(jìn)行更新,在充分考慮時(shí)間成本和空間成本的基礎(chǔ)上,關(guān)注如何讓用戶的調(diào)度行為信息更好地為挖掘用戶的真實(shí)需求服務(wù)。除此之外,考慮到用戶的行為方式往往在一段時(shí)間內(nèi)是比較穩(wěn)定的,因此,在下一步的工作中,將關(guān)注用戶行為相關(guān)性和穩(wěn)定性的時(shí)效性。

[1] FOSTER I, ZHAO Y, RAICU I, et al. Cloud computing and grid computing 360-degree compared[C]∥Proc.of the Grid Computing Environments Workshop, 2008: 1-10.

[2] ARMBRUST M, FOX A, GRIFFITH R, et al. A view of cloud computing[J].Communications of the ACM,2010,53(4):50-58.

[3] MELL P, GRANCE T. The NIST definition of cloud computing, NIST SP 800-145 [R]. Gaithersburg, MD, United States: National Institute of Standards and Technology, 2011.

[4] BUYYA R, YEO C S, VENUGOPAL S, et al. Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility [J]. Future Generation Computer Systems, 2009, 25(6): 599-616.

[5] 陳賡, 鄭緯民. 云計(jì)算:系統(tǒng)實(shí)例與研究現(xiàn)狀[J]. 軟件學(xué)報(bào), 2009, 20(5): 1337-1348.

CHEN G, ZHENG W M. Cloud computing: system instances and current research [J]. Journal of Software, 2009, 20(5): 1337-1348.

[6] Amazon elastic compute cloud (EC2) [EB/OL]. [2016-10-30]. http:∥www.amazon.com/ec2/.

[7] Google app engine [EB/OL]. [2016-10-30]. http:∥appengine.google.com.

[8] SIMS K. IBM introduces ready-to-use cloud computing-collaboration services get clients started with cloud computing [EB/OL]. [2016-10-30]. http:∥www-03.ibm.com/press/us/en/pressrelease/22613.wss.

[9] Microsoft azure [EB/OL]. [2016-10-30]. http:∥www.microsoft.com/azure/.

[10] 鐘海.面向云計(jì)算環(huán)境的應(yīng)用遷移策略及資源管理技術(shù)研究[D].云南: 云南大學(xué), 2011.

ZHONG H. Research on applications migration strategy and resources management technology towards cloud environment [D]. Yunnan: Yunnan University, 2011.

[11] MITTAL A, KAUR P D. Genetic based QoS task scheduling in cloud-upgrade genetic algorithm [J]. International Journal of Grid and Distributed Computing, 2015, 8(4): 145-152.

[12] PANDIT D, CHATTOPADHYAY S, CHATTOPADHYAY M, et al. Resource allocation in cloud using simulated annealing[C]∥Proc.of the International Conference on Applications and Innovations in Mobile Computing, 2014: 21-27.

[13] 張永強(qiáng), 徐宗昌, 呼凱凱, 等. 基于私有云和改進(jìn)粒子群算法的約束優(yōu)化求解[J]. 系統(tǒng)工程與電子技術(shù), 2016, 38(5): 1086-1092.

ZHANG Y Q, XU Z C, HU K K, et al. Constrained optimization problems solving based on private cloud and improved particle swarm optimization [J]. Systems Engineering and Electronics, 2016, 38(5): 1086-1092.

[14] SINGH J, MISHRA S. Improved ant colony load balancing algorithm in cloud computing[J]. International Journal of Computers and Technology, 2015, 4(3): 5636-5644.

[15] BUYYA R, YEO C S, VENUGOPAL S. Market-oriented cloud computing: vision, hype, and reality for delivering IT services as computing utilities[C]∥Proc.of the 10th IEEE International Conference on High Performance Computing and Communications, 2008: 5-13.

[16] BUYYA R. Market-oriented cloud computing: opportunities and challenges[C]∥Proc.of the 17th IEEE International Enterprise Distributed Object Computing Conference, 2013: 3.

[17] 丁丁, 羅四維, 艾麗華. 基于雙向拍賣的適應(yīng)性云計(jì)算資源分配機(jī)制[J]. 通信學(xué)報(bào), 2012, 33(Z1): 132-140.

DING D, LUO S W, AI L H. An adaptive double auction mechanism for cloud resource allocation [J]. Journal on Communications, 2012, 33(Z1): 132-140.

[18] ZHANG R, WU K, LI M, et al. Online resource scheduling under concave pricing for cloud computing [J]. IEEE Trans.on Parallel and Distributed System, 2015, 27(4): 1131-1145.

[19] 李智勇, 陳少淼, 楊波, 等. 異構(gòu)云環(huán)境多目標(biāo)Memetic優(yōu)化任務(wù)調(diào)度方法[J]. 計(jì)算機(jī)學(xué)報(bào), 2016, 39(2): 377-390.

LI Z Y, CHEN S M, YANG B, et al. Multi-objective memetic algorithm for task scheduling on heterogeneous cloud [J]. Chinese Journal of Computers, 2016, 39(2): 377-390.

[20] SAATY T L. Analytic hierarchy process [M]. New York: Wiley, 2014.

[21] ASVANUND A, KRISHNAN R, SMITH M, et al. Interest-based self-organizing peer-to-peer networks: a club economics approach [EB/OL]. [2016-10-30]. Ssrn Electronic Journal, http:∥ssrn.com/abstract=657403.

[22] CRESPO A, Garcia-Molina H. Semantic overlay networks for P2P system[C]∥Proc.of the 3rd International Workshop on Agents and Peer-to-Peer Computing, 2005: 1-13.

[23] SINGH S, CHANA I. A survey on resource scheduling in cloud computing: issues and challenges [J]. Journal of Grid Computing, 2016, 14(2): 217-264.

[24] DING D, LUO S W, AI L H, et al. A user preference driven approach for multi-QoS constrained task scheduling in grid[C]∥Proc.of the 13th International Conference on Parallel and Distributed Computing, Application, and Technologies, 2012: 493-498.