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

(北京交通大學計算機與信息技術學院, 北京 100044)

0 引 言

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

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

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

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

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

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

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

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

1.1 調(diào)度模型

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

1.1.1 相關定義

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

ti=(tri,tpi)

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

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

tri=[tri1,tri2,…,trid]

同理,用戶任務的偏好tpi定義為

tpi=[tpi1,tpi2,…,tpid]

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

rfj=[rfj1,rfj2,…,rfjf]

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

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

在實際應用中,不同的任務需求往往具有不同的表達形式和數(shù)值范圍,因此,為了進行綜合評價,首先需要對各個任務需求的值進行歸一化處理,使得所有任務需求的值具有可比性。可以采用最小-最大規(guī)格化等方法對任務需求矩陣TR中任務需求的取值進行線性變換,消除不同量綱對調(diào)度結果的影響。

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

0≤trik≤1

(1)

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

(2)

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

0≤rfjk≤1

(3)

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

rfj=[rfj1,rfj2,…,rfjf]

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

2.1 算法基本思想

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

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

2.2 算法描述

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

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

輸入TR,TP和RF

匹配閾值θ

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

輸出為每一個用戶任務分配合適的資源

01 fori:=1 tomdo

02 do

03t=0

04 forj:=1 tondo

05 計算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中只有一個滿足用戶需求的資源then

17 將這個唯一滿足條件的資源分配給當前的用戶任務ti

18 endif

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

20 forj:=1 tondo

21 計算用戶任務在每個可用資源rj上運行的效益

22 endfor

23 將效益最大的資源分配給當前的用戶任務ti

24 endif

25 更新用戶任務ti的TR和TP

26t=t+1

27 untilt>γ

28 endfor

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

2.2.1 資源匹配

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

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

(4)

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

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

(5)

2.2.2 資源選擇

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

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

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

(6)

(7)

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

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

2.2.3 基于用戶行為的反饋

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

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

(8)

(9)

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

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

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

2.3 算法性能分析

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

3 實驗與結果

3.1 實驗環(huán)境與設置

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

3.2 實驗結果與分析

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

3.2.1 運行時間

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

表1 調(diào)度算法運行時間比較

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

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

3.2.2 用戶滿意度

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

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

3.2.3 資源利用率

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

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

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

4 結束語

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

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

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

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

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

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

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

[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] 陳賡, 鄭緯民. 云計算:系統(tǒng)實例與研究現(xiàn)狀[J]. 軟件學報, 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] 鐘海.面向云計算環(huán)境的應用遷移策略及資源管理技術研究[D].云南: 云南大學, 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] 張永強, 徐宗昌, 呼凱凱, 等. 基于私有云和改進粒子群算法的約束優(yōu)化求解[J]. 系統(tǒng)工程與電子技術, 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] 丁丁, 羅四維, 艾麗華. 基于雙向拍賣的適應性云計算資源分配機制[J]. 通信學報, 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] 李智勇, 陳少淼, 楊波, 等. 異構云環(huán)境多目標Memetic優(yōu)化任務調(diào)度方法[J]. 計算機學報, 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.