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

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

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

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

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

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

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

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

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

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

1 引言

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

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

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

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

3 模型設(shè)計(jì)

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

3.1 模型的評(píng)價(jià)指標(biāo)

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

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

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

圖1 算法模型示意圖

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

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

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

（3）平均請(qǐng)求處理時(shí)間(tm)

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

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

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

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

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

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

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

3.2.1 服務(wù)請(qǐng)求的隊(duì)列排序

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

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

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

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

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

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

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

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

3.2.2 服務(wù)器的選擇

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

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

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

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

云計(jì)算平臺(tái)的平均負(fù)載狀況AvgDC則可表示為：

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

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

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

3.3 模型的算法步驟

3.3.1 服務(wù)請(qǐng)求的優(yōu)先排隊(duì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Wn=DMapnkTn

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟2當(dāng)?shù)谝徊糠峙抨?duì)策略選出服務(wù)m的請(qǐng)求處理進(jìn)程被觸發(fā)時(shí)，對(duì)于每個(gè)服務(wù)器i，依次執(zhí)行以下步驟：

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)環(huán)境

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

表1 云計(jì)算IaaS平臺(tái)服務(wù)器配置

表2 云平臺(tái)虛擬資源模板

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

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

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

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

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

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

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

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

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

5 結(jié)束語

本文設(shè)計(jì)并提出一種基于隨機(jī)模型考慮負(fù)載均衡的調(diào)度策略，解決基于代數(shù)模型的調(diào)度策略請(qǐng)求丟失率高以及其他基于隨機(jī)模型調(diào)度策略負(fù)載均衡指標(biāo)性能較差的問題，以優(yōu)化云計(jì)算IaaS平臺(tái)的整體性能。通過與Best-fit，M in-m in等經(jīng)典算法和其他隨機(jī)模型調(diào)度實(shí)驗(yàn)比較發(fā)現(xiàn)，該算法在較少任務(wù)積壓量和負(fù)載均衡上都具有良好的性能。在下一階段，云計(jì)算服務(wù)調(diào)度策略的運(yùn)行環(huán)境的復(fù)雜性將進(jìn)一步增強(qiáng)，擴(kuò)充云系統(tǒng)的集群數(shù)量和部署更豐富的異構(gòu)環(huán)境加以測(cè)試與驗(yà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]林偉偉，齊德昱.云計(jì)算資源調(diào)度研究綜述[J].計(jì)算機(jī)科學(xué)，2012，39（10）：1-6.

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

[10]左利云，曹志波.云計(jì)算中調(diào)度問題研究綜述[J].計(jì)算機(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

教育部-中國(guó)移動(dòng)研究基金（No.MCM 20123041）；福建省教育廳科技項(xiàng)目（No.JB13198，No.JA 13343，No.JA 12352）；福建師范大學(xué)福清分校科技研究項(xiàng)目（No.KY 2013001）。

趙少卡（1980—），男，講師，主要研究領(lǐng)域?yàn)樵朴?jì)算、軟件工程；李立耀（1970—），男，副教授，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)；徐聰（1986—），男，博士研究生，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)；楊家海（1966—），男，博士，教授，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(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