趙少卡，李立耀，徐聰，楊家海

1.福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系，福建福清 350300

2.清華大學(xué)網(wǎng)絡(luò)科學(xué)與網(wǎng)絡(luò)空間研究院，北京 100084

基于隨機模型的云平臺資源調(diào)度策略設(shè)計

趙少卡1，2，李立耀1，徐聰2，楊家海2

1.福建師范大學(xué)福清分校數(shù)學(xué)與計算機科學(xué)系，福建福清 350300

2.清華大學(xué)網(wǎng)絡(luò)科學(xué)與網(wǎng)絡(luò)空間研究院，北京 100084

針對云計算資源管理的實際需求，提出一種基于隨機模型的云平臺調(diào)度策略，設(shè)計合理高效的資源調(diào)度算法，解決傳統(tǒng)代數(shù)模型請求丟失率高以及其他隨機模型負載均衡指標(biāo)性能較差的問題，從而在服務(wù)性能和執(zhí)行效率的基礎(chǔ)上保證服務(wù)器的資源負載，使云平臺處于相對穩(wěn)定的狀態(tài)。在實驗環(huán)境中的驗證結(jié)果表明，該調(diào)度策略能夠優(yōu)化虛擬資源的使用效率和服務(wù)響應(yīng)時間，同時能夠達到較好的負載均衡并降低運營成本。

云計算；資源調(diào)度；負載均衡；隨機模型

1 引言

伴隨著分布式計算特別是網(wǎng)格技術(shù)的發(fā)展，產(chǎn)生了云計算這一新型的服務(wù)計算模型。云計算體系架構(gòu)中，基礎(chǔ)設(shè)施即服務(wù)（Infrastructure as a Service，IaaS）以服務(wù)的方式為用戶提供包括處理、存儲、網(wǎng)絡(luò)和其他基本的計算資源的使用，用戶可以在其申請到的虛擬資源中部署或運行應(yīng)用程序，而不需要了解計算資源提供過程的細節(jié)。隨著數(shù)據(jù)中心規(guī)模的日益增大，云平臺中服務(wù)器的數(shù)目不斷增加，同時虛擬化環(huán)境也日趨復(fù)雜，這種情形下如果不能夠提升IaaS平面的管理能力，使其能夠充分全面地調(diào)度數(shù)據(jù)中心的各項資源，則很大程度上會降低整個數(shù)據(jù)中心的工作性能。因此，虛擬資源的調(diào)度問題成為IaaS平臺中的一個主要問題，設(shè)計并實現(xiàn)一套較為完善的資源調(diào)度策略具有十分重要的理論和現(xiàn)實意義。

2 云平臺調(diào)度的研究現(xiàn)狀

資源調(diào)度是將資源從提供方分配給用戶的過程。云數(shù)據(jù)中心的資源調(diào)度技術(shù)是云計算應(yīng)用的核心，是云計算得以大規(guī)模應(yīng)用和提高系統(tǒng)性能、兼顧節(jié)能減排的關(guān)鍵技術(shù)。現(xiàn)有的IaaS調(diào)度策略主要分為兩種，一種是基于代數(shù)模型[1-4]，主要是以最優(yōu)化服務(wù)性能為目標(biāo)的M in-m in調(diào)度策略、suffrage調(diào)度策略，以優(yōu)化系統(tǒng)性能指標(biāo)為目標(biāo)的Best-Fit、First-Fit調(diào)度策略，以及其他一些以優(yōu)化經(jīng)濟收益為目標(biāo)的調(diào)度策略。這些調(diào)度策略主要以提高云計算系統(tǒng)的總體吞吐率為核心的優(yōu)化目標(biāo)，如最優(yōu)化請求的響應(yīng)時間、請求處理效率等服務(wù)質(zhì)量指標(biāo)，以及服務(wù)器負載狀況、資源利用率等系統(tǒng)性能指標(biāo)。總體來看，目前大部分云計算平臺使用的都是基于代數(shù)模型的調(diào)度策略，這些策略雖然能夠滿足當(dāng)前的調(diào)度達到最優(yōu)值，但是缺乏對于階段性調(diào)度結(jié)果的總體評估，并經(jīng)常導(dǎo)致請求的丟失以及系統(tǒng)整體吞吐率的下降。

另一種是基于隨機模型的調(diào)度機制[5-7]，希望在保證系統(tǒng)及服務(wù)性能的同時降低請求的丟失率，但目前的隨機調(diào)度機制雖然彌補了代數(shù)模型的諸多不足，但針對云計算平臺調(diào)度特點來說，依然存在缺陷，例如，在優(yōu)化系統(tǒng)及服務(wù)性能指標(biāo)時忽略了服務(wù)器負載均衡方面的指標(biāo)。因此，一種基于隨機模型更為完善的調(diào)度機制亟待提出。

3 模型設(shè)計

本算法模型基于隨機模型的云平臺資源負載均衡調(diào)度策略，主要分為兩部分：服務(wù)請求的隊列排序和服務(wù)器優(yōu)化選擇。用戶發(fā)送申請?zhí)摂M機請求到達云隊列，隊列將根據(jù)用戶請求的優(yōu)先級進行排序，將第一個請求發(fā)送至服務(wù)器進行分配，云端根據(jù)負載均衡算法，挑選出最合適的服務(wù)器接受這一待處理的請求（如圖1所示）。其中，第一部分主要是對資源請求的調(diào)度，在優(yōu)化服務(wù)指標(biāo)性能的Best-Fit算法思想基礎(chǔ)上引入隨機模型，使用基于優(yōu)先級別的隊列，減少輕量級服務(wù)請求被丟棄的概率以及請求積壓的數(shù)量，提高系統(tǒng)的吞吐率；第二部分是對目標(biāo)主機的選擇，在綜合考慮服務(wù)器負載情況以及資源請求的積壓狀況的情況下，選擇相應(yīng)時間最快同時負載情況相對較小的目標(biāo)主機進行虛擬資源的分配，使得調(diào)度策略在優(yōu)化服務(wù)性能指標(biāo)的同時，在服務(wù)器負載均衡方面效果更佳。

3.1 模型的評價指標(biāo)

（1）服務(wù)請求丟失率(R0(t))

在一時間單元t內(nèi)有NA(t)個服務(wù)請求到達，其中如果有N0(t)個請求由于隊列溢出而被丟棄，則定義該時間單元內(nèi)服務(wù)請求的丟失率為：

（2）服務(wù)請求積壓狀況(L(t))

圖1 算法模型示意圖

服務(wù)請求的積壓狀況記錄了在某一時刻尚未被處理的請求的數(shù)目，請求積壓情況越嚴重，則該時刻服務(wù)響應(yīng)的效率就會下降。具體地，定義t時刻某項服務(wù)m被積壓的請求數(shù)目為Lm(t)，該時刻的請求積壓量由前一時刻的請求積壓量，t時刻內(nèi)到達的新的請求數(shù)目Am(t)以及t時刻內(nèi)處理掉的請求的數(shù)目Hm(t)共同決定，具體關(guān)系為：

對于云系統(tǒng)整體的資源調(diào)度隊列，t時刻所有任務(wù)積壓量的總和L(t)則表示為：

為了減小請求的丟失情況同時提高系統(tǒng)的響應(yīng)時間，增大吞吐率，合理的調(diào)度策略應(yīng)當(dāng)使系統(tǒng)處于穩(wěn)定狀態(tài)時，請求積壓量維持在一個有限值，即盡可能地滿足：

（3）平均請求處理時間(tm)

服務(wù)的平均請求處理時間反映了云計算系統(tǒng)處于穩(wěn)定狀態(tài)時平均的工作效率。平均請求處理時間的長短不僅與穩(wěn)態(tài)時系統(tǒng)的請求積壓量有關(guān)，而且與請求到達的速率相關(guān)。具體來說，假設(shè)某項IaaS服務(wù)m的請求到達服從強度為λm的泊松分布，那么云平臺達到穩(wěn)定狀態(tài)時，該服務(wù)請求的平均處理時間tm為：

（4）云服務(wù)器負載均衡狀況(σDC)

在某一時刻t時，設(shè)一個由N臺服務(wù)器組成的云計算IaaS平臺中，第i臺服務(wù)器的資源利用率為P(t)，那么在這一時刻整個IaaS平臺的平均負載狀況AvgDC可以被定義為：

同時，用σDC來定義云服務(wù)器的負載均衡狀況，σDC的值越小則服務(wù)器的負載越均衡：

在具體的IaaS資源調(diào)度場景中，初始開始調(diào)度時服務(wù)請求的積累量相對較小，服務(wù)丟失率較低，平均響應(yīng)時間也很快。隨著不同種類服務(wù)調(diào)用請求的增加，有限的IaaS資源不能同時滿足所有的請求需求，會導(dǎo)致請求的不斷積壓，L(t)的值不斷增大，同時請求的平均處理時間tm逐漸增加；當(dāng)某一時刻，積壓的請求量大于系統(tǒng)設(shè)定的等待隊列的上限時會造成服務(wù)請求的丟失，出現(xiàn)R0＞0的情況；最終，隨著調(diào)度過程的不斷繼續(xù)，云計算系統(tǒng)最終會處于一個相對穩(wěn)定的狀況，系統(tǒng)的各項性能評價指標(biāo)會相對穩(wěn)定在一個固定的值上，本調(diào)度策略主要對系統(tǒng)處于穩(wěn)態(tài)時各項性能指標(biāo)進行綜合的優(yōu)化與分析。

在云計算IaaS平臺處于穩(wěn)定狀態(tài)時，如果R0＞0，但服務(wù)積壓量L(t)的值很小，說明該調(diào)度策略將很多對虛擬資源需求量較大的重量級任務(wù)積壓在了隊列當(dāng)中，雖然響應(yīng)時間能夠保證相對較小，但吞吐率并不大，不是理想的調(diào)度策略，需要改變每次優(yōu)先選取的任務(wù)，增大資源的分配粒度；如果服務(wù)積壓量L(t)的值一直處于最大值，則任務(wù)一直處于大量積壓狀態(tài)，這種情況會造成任務(wù)請求的大量丟失，也不是理想的調(diào)度策略，需要對被積壓的服務(wù)特征進行分析，采用優(yōu)先排隊的策略，減小等待隊列的長度；如果服務(wù)積壓量L(t)、服務(wù)丟失率R0以及響應(yīng)時間tm的值都比較理想，但是負載均衡參數(shù)σDC的值較大，說明該方法對于任務(wù)的排序方式是合理的，但服務(wù)器的選擇方面不能保證負載均衡的情況，需要優(yōu)化服務(wù)器選擇的方式。

3.2 模型的詳細設(shè)計

3.2.1 服務(wù)請求的隊列排序

模型的第一步就是要進行服務(wù)請求的隊列排序，目的是在保證吞吐率的前提下，使等待隊列的長度維持在一個固定的上限之內(nèi)，避免出現(xiàn)無限等待的情況。和其他的調(diào)度方式類似，本調(diào)度策略中也使用等待隊列對暫時無法處理的服務(wù)請求進行排隊，當(dāng)其他任務(wù)釋放之后，云平臺具備了足夠的資源，會從隊列之中選擇合適的任務(wù)進行處理。目前通用的調(diào)度算法之所以階段性調(diào)度結(jié)果并不理想，是因為大部分的調(diào)度策略都是單目標(biāo)優(yōu)化的代數(shù)過程，一方面這些策略僅考慮了瞬時調(diào)度的最優(yōu)情況而忽略了階段性整體調(diào)度的情況，導(dǎo)致了大量請求的積壓以及無限等待的情況出現(xiàn)；另一方面，這些策略的優(yōu)化目標(biāo)一直是固定的，而實際調(diào)度過程的不同階段往往需要根據(jù)實際需求不斷調(diào)整調(diào)度策略的優(yōu)化目標(biāo)，如當(dāng)平臺資源剩余較多時應(yīng)以最大化吞吐率為優(yōu)化目標(biāo)，盡量多地將剩余資源分配出去，而當(dāng)請求積壓嚴重時，應(yīng)以最大限度減小積壓狀況，提高服務(wù)響應(yīng)時間為優(yōu)化目標(biāo)，此時往往需要調(diào)度一些輕量級的服務(wù)，目前的調(diào)度算法由于忽略了這些因素導(dǎo)致結(jié)果調(diào)度并不理想。本調(diào)度算法將根據(jù)調(diào)度過程的不同階段不斷調(diào)整優(yōu)化目標(biāo)，使整體的階段性調(diào)度結(jié)果達到一個相對理想的狀態(tài)。

首先，在云計算平臺資源富裕的情況下，調(diào)度策略以優(yōu)化每次調(diào)度的吞吐率為首要目標(biāo)，此時的調(diào)度策略與Best-Fit算法相似，每次選取資源需求最大的請求進行處理。假設(shè)t時刻服務(wù)m（比如某種特定種類的虛擬機模板）對某種硬件資源k（如：CPU、內(nèi)存等）的需求量為Dmk，服務(wù)器i對該資源的占有總量為Cik，同時該時刻服務(wù)器中已經(jīng)分配了Nmi(t)個服務(wù)m資源，則三者應(yīng)當(dāng)滿足的約束條件為（M為總的服務(wù)種類數(shù)目）：

此時的調(diào)度策略可以抽象成為如下的優(yōu)化模型，此時由于請求積壓量較小，不足以影響調(diào)度的效率，因此，單次調(diào)度的資源數(shù)目作為首要的優(yōu)化目標(biāo)，而服務(wù)器的資源總量作為主要的限制條件。

其中，K為硬件資源的總的種類數(shù)目，M(t)為t時刻已被觸發(fā)的服務(wù)種類的集合，MaxqueueLength為等待隊列的隊長上界。此時以優(yōu)化一次調(diào)度的資源總量為目標(biāo)，調(diào)整等待隊列中服務(wù)請求的順序，將資源需求量最大的服務(wù)置于隊首優(yōu)先被處理。

隨著調(diào)度的進行，資源的需求量逐漸達到或超過云系統(tǒng)的資源總量，此時沿用先前的調(diào)度策略會造成大量的請求被積壓，此時應(yīng)以盡量增加調(diào)度任務(wù)的數(shù)目，減小任務(wù)的積壓，減少服務(wù)請求的丟失率為首要調(diào)度目標(biāo)，優(yōu)化模型調(diào)整為：

此時的調(diào)度以盡量減少任務(wù)積壓為目標(biāo)，在云平臺資源緊張的情況下，可以考慮適當(dāng)增加輕量級任務(wù)的優(yōu)先級，減少等待隊列的長度。此時的優(yōu)先隊列會增加輕量級任務(wù)在隊列中的優(yōu)先級，由于在上一個場景中，輕量級任務(wù)往往會在隊列中積壓，因此本策略除了任務(wù)對資源的需求量之外還根據(jù)任務(wù)的積壓時間來調(diào)整不同服務(wù)請求的優(yōu)先級。

之后，云計算系統(tǒng)進入了穩(wěn)定狀態(tài)，隊列中任務(wù)的積壓量，系統(tǒng)的平均吞吐率和任務(wù)處理的響應(yīng)時間會維持在一個相對穩(wěn)定的范圍之內(nèi)。在穩(wěn)定狀態(tài)時，由于云計算系統(tǒng)仍然處于資源供不應(yīng)求的階段，因此，一個比較理想的調(diào)度策略應(yīng)當(dāng)盡量減小任務(wù)的積壓量，即使得等待隊列盡量不要出現(xiàn)溢出的情況：

本文提出的資源調(diào)度策略，在服務(wù)請求排序的部分以穩(wěn)態(tài)時任務(wù)的積壓狀況為主要的優(yōu)化目標(biāo)，在保證等待隊列不會溢出的前提下，盡量優(yōu)化每次資源分配的吞吐率，使得該排隊策略能夠根據(jù)調(diào)度過程的各個階段不斷調(diào)整調(diào)度的優(yōu)化目標(biāo)，從而使階段性的調(diào)度結(jié)果盡可能達到最優(yōu)。

3.2.2 服務(wù)器的選擇

第一部分對服務(wù)請求的優(yōu)先排序主要是合理調(diào)整資源調(diào)度任務(wù)執(zhí)行的先后順序，優(yōu)化服務(wù)積壓量、服務(wù)請求響應(yīng)時間等服務(wù)質(zhì)量指標(biāo)；而第二部分的工作主要是對每個服務(wù)請求，在最合適的服務(wù)器上進行資源的分配。與第一部分考慮的服務(wù)質(zhì)量因素不同，該部分主要考慮的因素是云計算系統(tǒng)服務(wù)器的負載均衡問題。

該部分調(diào)度模型引入一些新的參數(shù)：

pni(t)：t時刻服務(wù)n請求的資源被分配到服務(wù)器i上的概率。

Dnk：t時刻位于隊首的服務(wù)n請求的資源k的數(shù)量。此時，t時刻服務(wù)器i的資源負載可以表示為：

云計算平臺的平均負載狀況AvgDC則可表示為：

此時在考慮服務(wù)器負載情況的同時，也考慮了每個服務(wù)器的任務(wù)積壓情況，在盡量滿足負載均衡的前提下，減少每個服務(wù)器中的任務(wù)積壓量。設(shè)t時刻服務(wù)器i的任務(wù)積壓量為qi(t)，t時刻處理結(jié)束的任務(wù)數(shù)目為hi(t)，則有：

將上述影響因素綜合考慮，第二部分的調(diào)度策略可以抽象為一個多目標(biāo)的優(yōu)化模型，具體形式化描述如下：

服務(wù)器選擇策略的優(yōu)化過程，就是不斷調(diào)整pni(t)取值的過程，使得σDC(t)和qi(t)的取值都達到相對理想的情況。具體算法實現(xiàn)過程中，選擇負載相對較輕的一些服務(wù)器作為候選服務(wù)器集合，之后比較該集合中所有服務(wù)器的任務(wù)積壓量，綜合考慮負載均衡與服務(wù)效率兩方面的因素，選擇積壓量較小的服務(wù)器進行資源的分配。

3.3 模型的算法步驟

3.3.1 服務(wù)請求的優(yōu)先排隊

對于每個提交給云計算系統(tǒng)的服務(wù)調(diào)用請求，執(zhí)行以下步驟：

步驟1根據(jù)具體的系統(tǒng)規(guī)模、服務(wù)數(shù)量以及調(diào)度執(zhí)行的階段，初始化如下參數(shù)：

Dmk：服務(wù)m所需要的虛擬資源k的數(shù)量，此參數(shù)在算法執(zhí)行開始時初始化。

Mapn：任務(wù)n對應(yīng)的服務(wù)種類，此參數(shù)在第n個任務(wù)到達隊列時初始化。

Tn：任務(wù)n的積壓時間，此參數(shù)在第n個任務(wù)到達隊列時初始化，初始值設(shè)為1。

Wn：等待隊列中任務(wù)n的權(quán)重，此參數(shù)在第n個任務(wù)到達隊列時初始化，初始值設(shè)為Mapn。

MaxqueueLength：等待隊列的隊長上限值，此參數(shù)在算法執(zhí)行開始時初始化。

Fexecute：每次調(diào)度執(zhí)行的頻率（以分鐘、小時為時間單元來執(zhí)行調(diào)度），此參數(shù)在算法執(zhí)行開始時初始化。

R0(t)：t時刻服務(wù)請求的丟失率，此參數(shù)在算法執(zhí)行開始時初始化，初始設(shè)為0。

L(t)：t時刻等待隊列中任務(wù)的積壓量，即隊列長度。此參數(shù)在算法執(zhí)行開始時初始化，初始值設(shè)為0。

步驟2初始化時間計數(shù)器t=1，隨著調(diào)度過程的推進，每經(jīng)過一個時間單元，計數(shù)器增加t=t+1，在每個時間單位Fexecute中依次執(zhí)行以下步驟：

步驟2.1將任務(wù)計數(shù)器count變量設(shè)為0，該時間單位每到達一個新的服務(wù)請求，count變量值加1。

步驟2.2判斷此時L(t-1)+count與MaxqueueLength的大小關(guān)系，若二者大小關(guān)系滿足L(t-1)+count≤MaxqueueLength，則將所有請求排入隊列當(dāng)中；若不滿足此關(guān)系則丟棄掉多余的請求，更新R0(t)的值。

步驟2.3對于等待隊列中的每一個任務(wù)n，依次執(zhí)行以下步驟：

（1）重新計算該任務(wù)在以資源k為核心的調(diào)度過程中所占的權(quán)重。

Wn=DMapnkTn

（2）根據(jù)新的權(quán)重值重新調(diào)整該任務(wù)在隊列中的位置，權(quán)重越大的任務(wù)在隊列中的位置越靠近隊首。

（3）所有任務(wù)的隊列位置調(diào)整完畢之后，結(jié)束步驟2.3。

步驟2.4如果經(jīng)過步驟2.3后，對于處于隊首的任務(wù)，根據(jù)服務(wù)器選擇策略的結(jié)果（在3.3.2節(jié)中進行詳細描述），在適當(dāng)?shù)姆?wù)器中進行資源的分配。

步驟2.5根據(jù)式（1）、式（2）更新L(t)的值。

步驟2.6對每個仍然處在等待隊列中的任務(wù)i，更新任務(wù)積壓時間Ti=Ti+1。

步驟3一段時間之后，如果等待隊列一直處于滿載狀況，同時請求丟失概率一直處于接近100%，說明此時的隊長上限不適合請求到達的速率，需要增加隊長上限MaxqueueLength的取值，之后返回步驟1重新觀察系統(tǒng)性能能否達到穩(wěn)定狀態(tài)。如果等待隊列的長度處于一個相對穩(wěn)定的取值范圍內(nèi)，同時請求丟失率維持在一個相對較低的程度，說明系統(tǒng)在此排隊策略下達到了穩(wěn)態(tài)，返回步驟2，請求排隊可以繼續(xù)按該策略進行。

3.3.2 服務(wù)器的優(yōu)化選擇策略

對于每個處于等待隊列隊首，即將要被處理的請求，執(zhí)行以下步驟：

步驟1根據(jù)具體的系統(tǒng)規(guī)模、服務(wù)數(shù)量以及調(diào)度執(zhí)行的階段，初始化如下參數(shù)：

qi(t)：t時刻服務(wù)器i的等待隊列中任務(wù)的積壓量，即隊列長度。此參數(shù)在算法執(zhí)行開始時初始化，初始值設(shè)為0。

Cik：服務(wù)器i對資源k的占有總量，此參數(shù)在算法執(zhí)行開始時初始化。

Nmi(t)：t時刻服務(wù)器i上已經(jīng)分配了的服務(wù)m的數(shù)目。此參數(shù)在算法執(zhí)行開始時初始化，初始值設(shè)為0。

isHandled：布爾變量，記錄當(dāng)前資源分配任務(wù)能否被處理，1表示可以，0表示無法處理。參數(shù)在算法執(zhí)行開始時初始化，初始值設(shè)為0。

candidateSet：數(shù)組，記錄針對每個任務(wù)可能的候選服務(wù)器的集合，參數(shù)在每次請求處理進程被觸發(fā)時（即步驟2執(zhí)行時）都進行一次初始化，初始值為空。

N：云計算平臺服務(wù)器的總數(shù)，參數(shù)在算法執(zhí)行開始時初始化。

β：調(diào)整閾值，用來限定每次優(yōu)化選擇的可行區(qū)間的規(guī)模，參數(shù)在算法執(zhí)行開始時初始化，在本方法中初始值設(shè)為30%。

步驟2當(dāng)?shù)谝徊糠峙抨牪呗赃x出服務(wù)m的請求處理進程被觸發(fā)時，對于每個服務(wù)器i，依次執(zhí)行以下步驟：

步驟2.2計算并更新該服務(wù)器的剩余資源Cik(1-P(t))，并與服務(wù)需求的資源量Dmk作比較，若Cik(1-P(t))≥Dmk，則說明該服務(wù)器有能力處理該服務(wù)請求，將isHandled的值調(diào)整為1，并將該服務(wù)器加入到候選服務(wù)器集合中，更新集合candidateSet中的元素。

步驟3根據(jù)步驟2執(zhí)行之后的結(jié)果，若isHandled的值為0，說明目前云平臺的剩余資源量不足以處理該服務(wù)請求，本次任務(wù)調(diào)度終止，返回任務(wù)調(diào)度失敗的結(jié)果，等待其他任務(wù)結(jié)束之后資源的釋放；若isHandled的值為1，說明目前云平臺的剩余資源量可以處理該服務(wù)請求，進入步驟4繼續(xù)完成服務(wù)器選擇的操作。

步驟4步驟3執(zhí)行之后，判斷候選服務(wù)器集合中元素的數(shù)目，并與服務(wù)器總數(shù)進行比較，若|candidateSet|≤Nβ，則說明可選服務(wù)器并不多，目前大部分服務(wù)器都處于負載較重的狀況，此時直接進入步驟6，考慮優(yōu)化服務(wù)響應(yīng)時間；若|candidateSet|＞Nβ，則說明目前服務(wù)器負載情況不是很嚴重，此時以優(yōu)化負載均衡狀況為第一目標(biāo)，進一步精簡候選服務(wù)器集合的數(shù)目。

步驟5步驟4執(zhí)行之后，根據(jù)candidateSet集合中每個服務(wù)器i的剩余資源量Cik(1-P(t))對candidateSet集合中的元素進行篩選，集合中只保留剩余資源量相對較大的前Nβ個服務(wù)器，更新candidateSet集合。

步驟6對于candidateSet集合中的每個服務(wù)器i，依次執(zhí)行如下的操作：

步驟6.1計算該服務(wù)器的任務(wù)積壓量qi(t)。

步驟6.2令Pmi(t)=1，Pmj(t)=0，i≠j，根據(jù)式（3）、（4）計算σDC(t)的值并記錄。

步驟7選出使得σDC(t)達到最小值時的候選服務(wù)器j，在服務(wù)器j上根據(jù)服務(wù)m的需求分配虛擬資源，更新P(t)、Cjk、qj(t)的取值，返回并記錄分配結(jié)果。步驟8時間單元t結(jié)束時，對云平臺的每個服務(wù)器i，判斷該服務(wù)器上是否有資源回收的操作被觸發(fā)，如果有，則根據(jù)回收的資源量依次更新P(t)、Cjk、qj(t)的取值。

步驟9返回步驟2，進行下一次的服務(wù)器選擇。

基于隨機模型的云平臺資源負載均衡調(diào)度策略的具體算法流程如圖2所示。

圖2 基于隨機模型的負載均衡調(diào)度算法流程

4 實驗與分析

4.1 實驗環(huán)境

基于開源軟件OpenStack搭建一個包含6臺服務(wù)器的云計算IaaS平臺，服務(wù)器詳細配置如表1所示。該平臺以虛擬資源的方式為用戶提供虛擬資源的使用，提供的虛擬資源的模板種類如表2所示。為了對本文調(diào)度策略進行評估，將本文提出的調(diào)度算法用Java語言進行實現(xiàn)，并和目前使用較為廣泛使用的諸多調(diào)度策略進行了對比實驗。

表1 云計算IaaS平臺服務(wù)器配置

表2 云平臺虛擬資源模板

具體實驗中，將表2中列出的服務(wù)類型按照占用資源由小到大進行排序，編號為服務(wù)1～服務(wù)6，對應(yīng)每種服務(wù)模擬出一串服從特定強度的泊松到達請求序列。根據(jù)實際需求量的統(tǒng)計，用戶對微型、小型主機的需求比對大型、超大型主機的需求量明顯要大，因此在本實驗中服務(wù)1～服務(wù)6的請求到達頻率依次遞減。采用不同的調(diào)度策略用于對服務(wù)請求進行調(diào)度并對虛擬資源進行分配，本實驗重點考察的調(diào)度策略有目前使用較為廣泛的Best-Fit、M in-m in調(diào)度策略，OpenStack開源軟件提供的SimpleSchedule、ChanceSchedule分配策略，學(xué)術(shù)界提出的隨機調(diào)度策略以及本文提出的調(diào)度策略等。

實驗通過在500個時間單位內(nèi)，統(tǒng)計不同調(diào)度算法的任務(wù)積壓量和機器平均負載均衡狀況進行對比。任務(wù)積壓量從第一個時間片就開始采集，負載均衡是在各節(jié)點達到穩(wěn)態(tài)時進行數(shù)據(jù)采集。由多次實驗數(shù)據(jù)得到，從第300時間單位開始，各節(jié)點的CPU負載情況基本處于穩(wěn)態(tài)，因此負載均衡的實現(xiàn)結(jié)果選擇從第300個時間點開始統(tǒng)計，每隔5個時間點采集一次數(shù)據(jù)，到500個時間單位結(jié)束后，計算每個節(jié)點的平均負載情況。

4.2 實驗結(jié)果與分析

實驗結(jié)果顯示，本文提出的調(diào)度算法不論在任務(wù)積壓量還是服務(wù)器的負載均衡指標(biāo)上都有明顯較優(yōu)的結(jié)果。

圖3顯示了隨著調(diào)度過程的進行，使用不同的調(diào)度方法時造成的任務(wù)積壓的狀況。從中可以看出，本調(diào)度策略在任務(wù)積壓量指標(biāo)上明顯優(yōu)于Best-Fit和M in-M in策略，與其他隨機調(diào)度策略相比基本持平。使用以優(yōu)化單次調(diào)度吞吐量和單次調(diào)度響應(yīng)時間為目標(biāo)的Best-Fit和M in-m in策略處理請求時，調(diào)度初始階段效果相對較為理想，但隨著越來越多的資源被分配出去時，由于這兩個策略缺乏對調(diào)度效果的階段性評估，導(dǎo)致大量單次未被調(diào)度的請求被積壓。而使用基于隨機模型的優(yōu)先隊列排序，考慮到了階段性調(diào)度的總體性能，提高了被積壓任務(wù)的優(yōu)先級，在云平臺負載較輕的階段保證任務(wù)調(diào)度吞吐率的同時，在負載較重時能夠減小任務(wù)的積壓量，避免積壓量無限增長的情況出現(xiàn)。

圖3 各算法在任務(wù)積壓量上的結(jié)果

圖4顯示了本調(diào)度策略在負載均衡指標(biāo)上明顯優(yōu)于各類對比算法。由于同時考慮了任務(wù)積壓情況qi(t)和資源負載情況P(t)，使得本方法在負載均衡方面相比其他調(diào)度方法也有明顯的優(yōu)勢。其他的基于隨機模型的調(diào)度策略，雖然在請求調(diào)度上也做到了減小任務(wù)的積壓和請求的丟失，但在服務(wù)器選擇部分考慮的因素不夠全面，導(dǎo)致服務(wù)器負載均衡的效果并不理想。

圖4 各算法在負載均衡上的結(jié)果

通過和其他算法調(diào)度結(jié)果的對比分析，本調(diào)度策略使用了基于隨機模型的優(yōu)先隊列，在云平臺負載較輕時優(yōu)化了資源調(diào)度算法的吞吐率，在云平臺資源負載較重時減小了任務(wù)的積壓量和請求的丟失率；同時本策略在服務(wù)器選擇策略上綜合考慮了服務(wù)器的資源負載情況以及任務(wù)積累情況，在保證服務(wù)性能和執(zhí)行效率的基礎(chǔ)上盡量均衡了服務(wù)器的資源負載，使云平臺處于相對穩(wěn)定的狀態(tài)。由于解決了現(xiàn)有調(diào)度策略存在的一些問題，調(diào)度結(jié)果在某些服務(wù)質(zhì)量指標(biāo)的衡量下效果更加理想。因此，本文提出的調(diào)度算法是一個滿足云平臺資源調(diào)度要求的良好的策略。

5 結(jié)束語

本文設(shè)計并提出一種基于隨機模型考慮負載均衡的調(diào)度策略，解決基于代數(shù)模型的調(diào)度策略請求丟失率高以及其他基于隨機模型調(diào)度策略負載均衡指標(biāo)性能較差的問題，以優(yōu)化云計算IaaS平臺的整體性能。通過與Best-fit，M in-m in等經(jīng)典算法和其他隨機模型調(diào)度實驗比較發(fā)現(xiàn)，該算法在較少任務(wù)積壓量和負載均衡上都具有良好的性能。在下一階段，云計算服務(wù)調(diào)度策略的運行環(huán)境的復(fù)雜性將進一步增強，擴充云系統(tǒng)的集群數(shù)量和部署更豐富的異構(gòu)環(huán)境加以測試與驗證，并不斷完善調(diào)度策略。

[1]Speitkamp B，Bichler M.A mathematical programming approach for server consolidation problems in virtualized data centers[J].IEEE Transactions on Services Computing，2010，3（4）：266-278.

[2]Beloglazov A，Buyya R.Energy efficient allocation of virtual machines in cloud data centers[C]//10th IEEE/ACM International Conference on Cluster，Cloud and Grid Computing，2010：577-578.

[3]Qin X，Xie T.An availability-aware task scheduling strategy for heterogeneous systems[J].IEEE Transactions on Computers，2008，57（2）：188-199.

[4]Song S，Hwang K，Kwok Y.Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling[J].IEEE Transactions on Computers，2006，55（6）：703-719.

[5]Maguluri S T，Srikant R，Ying L.Stochastic models of load balancing and scheduling in cloud computing clusters[C]//Proceedings of IEEE INFOCOM Conference，2012.

[6]Bramson M，Lu Y，Prabhakar B.Random ized load balancing with general service time distributions[C]//Proceedings of the ACM SIGMETRICS International Conference on M easurement and modeling of Computer Systems，New York，USA，2010：275-286.

[7]Maguluri S T，Srikant R，Ying L.Heavy traffic optimal resource allocation algorithms for cloud com puting clusters[C]//International Teletraffic Congress，2012.

[8]林偉偉，齊德昱.云計算資源調(diào)度研究綜述[J].計算機科學(xué)，2012，39（10）：1-6.

[9]田文洪.云計算資源調(diào)度管理[M].北京:國防工業(yè)出版社，2011.

[10]左利云，曹志波.云計算中調(diào)度問題研究綜述[J].計算機應(yīng)用研究，2012，29（11）：4023-4027.

ZHAO Shaoka1，2,LI Liyao1,XU Cong2,YANG Jiahai2

1.Department of Mathematics and Computer Science, Fuqing Branch of Fujian Normal University, Fuqing, Fujian 350300, China
2.Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, China

In view of cloud computing actual needs of resource management, cloud platform scheduling strategy based on stochastic model is proposed, and reasonable and efficient resource scheduling algorithm is designed in order to reduce the request loss rate of traditional algebraic model and improve poor load balancing performance of other stochastic models.Through load balancing on the basis of service performance and efficiency, cloud platform stability is ensured. Experimental results show that the scheduling strategy can optimize the efficiency of virtual resource usage and the response time of the service while being able to achieve better load balance and reduce operating costs.

cloud computing; resource scheduling; load balancing; stochastic model

ZHAO Shaoka, LI Liyao, XU Cong, et al. Cloud platform resource scheduling strategy design based on stochastic model. Computer Engineering and Applications, 2014, 50（17）：56-62.

A

TP393

10.3778/j.issn.1002-8331.1306-0101

教育部-中國移動研究基金（No.MCM 20123041）；福建省教育廳科技項目（No.JB13198，No.JA 13343，No.JA 12352）；福建師范大學(xué)福清分?？萍佳芯宽椖浚∟o.KY 2013001）。

趙少卡（1980—），男，講師，主要研究領(lǐng)域為云計算、軟件工程；李立耀（1970—），男，副教授，主要研究領(lǐng)域為計算機網(wǎng)絡(luò)；徐聰（1986—），男，博士研究生，主要研究領(lǐng)域為計算機網(wǎng)絡(luò)；楊家海（1966—），男，博士，教授，主要研究領(lǐng)域為計算機網(wǎng)絡(luò)。E-mail：zska@cernet.edu.cn

2013-06-13

2013-08-09

1002-8331（2014）17-0056-07

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-10-17,http://www.cnki.net/kcms/detail/11.2127.TP.20131017.1529.011.htm l