李 杰 張 靜 李偉東 張學(xué)杰

1(云南大學(xué)信息學(xué)院 昆明 650500)2(云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 昆明 650500)

云計(jì)算資源提供商可以將云計(jì)算資源動(dòng)態(tài)地提供給用戶使用，由于其可靠性和方便的特點(diǎn)，目前大量的企業(yè)和個(gè)人都傾向于將計(jì)算和存儲(chǔ)任務(wù)提交到云平臺(tái)上執(zhí)行.如何提高資源利用率，無(wú)論從高效或者降低成本的角度來(lái)說(shuō)，對(duì)于用戶和資源提供商都是當(dāng)前關(guān)注的重點(diǎn).資源共享方式[1]，是一種非常有效的提高資源利用率的方法，系統(tǒng)通過(guò)云計(jì)算虛擬化技術(shù)將計(jì)算資源整合，實(shí)現(xiàn)資源共享功能，如Mesos[2]和Hadoop Yarn[3]等.在資源共享系統(tǒng)中，如何保證在用戶間公平高效地分配資源是需要解決的關(guān)鍵問(wèn)題.

目前，對(duì)于多種資源分配機(jī)制的公平性和高效性主要由經(jīng)濟(jì)學(xué)中一些屬性來(lái)定義.

1) 激勵(lì)共享[4].系統(tǒng)中所有用戶在共享情形下由機(jī)制分配的資源量不小于其在獨(dú)自占有資源情形下獲得的資源量.

2) 帕累托最優(yōu)[4].系統(tǒng)中任意一個(gè)用戶在分配機(jī)制中獲得比原來(lái)更多資源時(shí)，至少有另外一個(gè)用戶將受到損失.

3) 無(wú)嫉妒[5].系統(tǒng)中沒(méi)有任何用戶嫉妒其他用戶所分配的任意一種資源.

4) 可信[5].系統(tǒng)中任何謊報(bào)任務(wù)資源需求的用戶將不會(huì)獲得更多的資源.

目前，占優(yōu)資源公平分配機(jī)制(dominant resource fairness, DRF)[6]被廣泛用于Mesos和Hadoop Yarn等云計(jì)算系統(tǒng)中.DRF計(jì)算用戶任務(wù)所需的每種資源累計(jì)分配量占系統(tǒng)中該資源總量的比值，所有資源中比值最大的那種資源為占優(yōu)資源(dominant resource, DR),與其相對(duì)應(yīng)的比值為占優(yōu)份額(dominant share，DS).DRF機(jī)制的基本思想是使所有用戶中占優(yōu)資源份額最小的用戶所分得的資源盡可能大.該機(jī)制能夠在多資源并存情形下保證分配的公平.然而，DRF機(jī)制是基于資源由第三方提供分配，在實(shí)際資源共享系統(tǒng)中，每個(gè)用戶對(duì)資源的共享量可能不同，共享資源多的往往期望得到更多的資源.

文獻(xiàn)[7]針對(duì)動(dòng)態(tài)情形下資源分配公平性和效率做出了改進(jìn)，允許用戶隨時(shí)進(jìn)入系統(tǒng)但不離開系統(tǒng)，假設(shè)每個(gè)用戶的任務(wù)數(shù)是無(wú)限的，并未考慮實(shí)際環(huán)境中用戶任務(wù)數(shù)是有限的情形；文獻(xiàn)[8]在DRF機(jī)制的基礎(chǔ)上提出了一種解決動(dòng)態(tài)情形下資源分配的機(jī)制，即動(dòng)態(tài)占優(yōu)資源公平分配機(jī)制(dynamic dominant resource fairness mechanism, DDRF)，并給出了求解DDRF機(jī)制的一種線性多項(xiàng)式時(shí)間算法，該算法在動(dòng)態(tài)資源分配中有很好的效果，但未考慮異構(gòu)云計(jì)算環(huán)境下資源分配的問(wèn)題；文獻(xiàn)[9]針對(duì)系統(tǒng)中具有多個(gè)異構(gòu)虛擬機(jī)的資源分配問(wèn)題提出了面向異構(gòu)云計(jì)算系統(tǒng)占優(yōu)資源公平分配機(jī)制(dynamic dominant resource fairness mechanism in heterogeneous cloud computing system, DRFH)，該機(jī)制利用全局占優(yōu)資源份額公平[9]的概念對(duì)具有異構(gòu)虛擬機(jī)的云計(jì)算資源系統(tǒng)進(jìn)行資源分配，該機(jī)制假設(shè)用戶任務(wù)數(shù)沒(méi)有上限，并未考慮用戶具有有限任務(wù)數(shù)的情形；針對(duì)用戶有限任務(wù)數(shù)的資源分配問(wèn)題，文獻(xiàn)[10]提出了一種資源分配機(jī)制，考慮了在動(dòng)態(tài)情形下用戶具有有限個(gè)任務(wù)數(shù)需求的資源分配問(wèn)題；文獻(xiàn)[11]提出了多種啟發(fā)式資源分配算法，在異構(gòu)資源分配情形下取得了較好效果，但算法未考慮資源共享情形下用戶具有多組資源需求的情形.針對(duì)用戶具有多組資源需求的動(dòng)態(tài)資源分配情形，文獻(xiàn)[12]設(shè)計(jì)了一種啟發(fā)式算法，提出了資源共享公平概念,解決了用戶具有多組任務(wù)需求的問(wèn)題，但是該文并未考慮系統(tǒng)具有多個(gè)異構(gòu)的虛擬機(jī)，用戶在不同時(shí)刻每個(gè)任務(wù)所需資源不同的情形.

綜上，在多種共享虛擬資源分配的問(wèn)題上，目前的研究已經(jīng)取得了許多積極的成果，但是在考慮用戶共享資源[1-2]，用戶在不同時(shí)刻有不同的任務(wù)需求和有限的任務(wù)數(shù)情形下，用戶貢獻(xiàn)資源與分配資源的公平性問(wèn)題上仍然面臨挑戰(zhàn).本文研究一種公平的多資源動(dòng)態(tài)分配機(jī)制，旨在解決用戶在不同時(shí)刻具有多組有限時(shí)變?nèi)蝿?wù)需求情形下云計(jì)算資源共享系統(tǒng)的資源分配問(wèn)題.本文具體包括2方面研究:

1) 多資源動(dòng)態(tài)分配機(jī)制設(shè)計(jì).動(dòng)態(tài)情形下，用戶可提出多組有限時(shí)變多資源的任務(wù)需求，較其他分配機(jī)制，可使得用戶在多組時(shí)變需求情形下，滿足共享資源量與分配的資源量公平性，為云計(jì)算資源動(dòng)態(tài)分配問(wèn)題提出了更現(xiàn)實(shí)的解決方案.

2) 多資源分配算法設(shè)計(jì).結(jié)合字典序最優(yōu)[13]的概念，提出了合理的資源分配模型以滿足動(dòng)態(tài)云計(jì)算資源分配場(chǎng)景，設(shè)計(jì)了啟發(fā)式的資源分配算法，解決了共享資源系統(tǒng)中共享公平性問(wèn)題.

理論和實(shí)驗(yàn)表明：本文提出的方法解決了云計(jì)算共享資源系統(tǒng)中用戶多組時(shí)變?nèi)蝿?wù)需求的多資源公平分配問(wèn)題.

1 問(wèn)題描述及模型定義

1.1 問(wèn)題描述

在云計(jì)算資源共享系統(tǒng)[12]中，用戶將服務(wù)器資源共享到云計(jì)算虛擬機(jī)集群中，用戶有任務(wù)需求時(shí)，系統(tǒng)再將資源分配給用戶以達(dá)到更高的資源利用率.用戶任務(wù)的資源請(qǐng)求是由具有不同資源配置的虛擬機(jī)進(jìn)行響應(yīng).用戶任務(wù)的資源分配過(guò)程為虛擬機(jī)資源調(diào)度過(guò)程.

文獻(xiàn)[13]假定用戶需求的任務(wù)數(shù)在不同時(shí)刻是有限的，用戶i在時(shí)刻t需求任務(wù)數(shù)上限為Bi(t).與文獻(xiàn)[13]不同的是，本文假定每個(gè)用戶在不同時(shí)刻的任務(wù)資源需求是不相同的.令:

αi(t)=(αi1(t),αi2(t),…,αim(t))，

為用戶i在時(shí)刻t的每個(gè)任務(wù)所需資源向量，其中αij(t)表示用戶i在時(shí)刻t的每個(gè)任務(wù)對(duì)第j種資源的需求量.對(duì)于任意一個(gè)用戶i∈U，令i在時(shí)刻t的最大任務(wù)資源需求為向量

Di(t)=(Di1(t),Di2(t),…,Dim(t))，

其中,Dij(t)=αij(t)·Bi(t)表示在時(shí)刻t用戶i的任務(wù)對(duì)第j種資源的最大需求量.方便起見(jiàn)，對(duì)于任意用戶i∈U和任意資源j(1≤j≤m)，令Dij(t)>0，任務(wù)執(zhí)行時(shí)長(zhǎng)為單位時(shí)長(zhǎng).

對(duì)任意用戶i∈U在時(shí)刻t的資源分配向量U(t)已知情形下，用戶i在時(shí)刻t在虛擬機(jī)k上能執(zhí)行的最大任務(wù)數(shù)為

(1)

用戶i在時(shí)刻t能執(zhí)行的最大任務(wù)數(shù)為

(2)

(3)

根據(jù)文獻(xiàn)[14]可知,用戶完成的任務(wù)數(shù)跟其任務(wù)需求中的占優(yōu)資源有關(guān)，令:

(4)

為任意一個(gè)用戶i∈U，在時(shí)刻t每個(gè)任務(wù)中資源需求量占總資源容量比例最大值，我們定義用戶i到時(shí)刻t為止的累計(jì)帶權(quán)全局占優(yōu)資源份額為

(5)

其中:

為用戶i到時(shí)刻t為止在虛擬機(jī)k上所分得的累計(jì)帶權(quán)的全局占優(yōu)資源份額.為了方便起見(jiàn)，我們將累計(jì)帶權(quán)的全局占優(yōu)資源份額簡(jiǎn)稱為累計(jì)全局占優(yōu)資源份額.

1.2 資源共享公平定義

(6)

在時(shí)刻t用戶i的第j種資源在所有虛擬機(jī)全局共享系數(shù)為

(7)

根據(jù)文獻(xiàn)[14],由于在多種資源分配中，用戶分得的資源所能執(zhí)行的任務(wù)數(shù)由其占優(yōu)資源決定，定義用戶i在時(shí)刻t的全局共享系數(shù)為

(8)

在共享資源情形中，βi>1表示i用戶完成的任務(wù)數(shù)比不共享資源情形多，稱為共享受益;βi<1表示表示i用戶完成的任務(wù)數(shù)比不共享資源情形少，稱為共享缺損;βi=1表示i用戶完成的任務(wù)數(shù)與不共享資源情形相同.為了使用戶在共享資源的情形下執(zhí)行的任務(wù)數(shù)不小于不共享情形，必有βi≥1.

1.3 資源動(dòng)態(tài)分配公平性質(zhì)

在云計(jì)算資源共享系統(tǒng)中，資源分配的公平性是非常關(guān)鍵的.只有當(dāng)每個(gè)系統(tǒng)中用戶能夠公平分配到資源時(shí)，多資源共享分配才可行.文獻(xiàn)[4]中引入了4個(gè)重要屬性：激勵(lì)共享、帕累托最優(yōu)、無(wú)嫉妒、可信.下面結(jié)合本文所研究用戶具有時(shí)變有限任務(wù)資源需求的情形，將上述公平性進(jìn)行描述.

1.3.1 激勵(lì)共享

系統(tǒng)中對(duì)于任意一個(gè)用戶i∈U.在任意一個(gè)時(shí)刻t有βi(t)≥1.即系統(tǒng)中所有用戶在共享情形下獲得資源量不小于其在獨(dú)自占有資源情形獲得資源量，則認(rèn)為該機(jī)制滿足激勵(lì)共享屬性.

1.3.2 帕累托最優(yōu)

1.3.3 無(wú)嫉妒

若用戶i∈U到時(shí)刻t由分配機(jī)制分配的資源為向量Ui(t).首先，當(dāng)用戶完成累計(jì)任務(wù)數(shù)達(dá)到其累計(jì)需求任務(wù)數(shù)上限，即:

則用戶i不會(huì)嫉妒其他用戶.

其次，當(dāng)用戶完成累計(jì)任務(wù)數(shù)小于其累計(jì)需求任務(wù)數(shù)上限時(shí)，即:

用戶h≠i在時(shí)刻t由分配機(jī)制分配的資源為Uh(t),當(dāng)至少存在一種資源j(1≤j≤m),到時(shí)刻t為止用戶i累計(jì)分配的第j種資源與共享權(quán)重之比不比用戶h所分配的少，即:

滿足時(shí)，稱資源分配機(jī)制滿足無(wú)嫉妒屬性.

1.3.4 可信

2 TV-DRF機(jī)制設(shè)計(jì)

本文設(shè)計(jì)一種針對(duì)用戶在不同時(shí)刻提出有限時(shí)變資源需求的無(wú)浪費(fèi)資源公平 (time varied-DRF, TV-DRF) 分配機(jī)制.由于資源的有限性，如何設(shè)計(jì)分配機(jī)制使資源能夠公平地分配是一個(gè)難點(diǎn)，根據(jù)文獻(xiàn)[13]，字典序最大最小公平分配策略是一種較好的滿足任務(wù)數(shù)和資源數(shù)都有限情形下的分配策略:

令G(t)=(G1(t),G2(t),…,Gn(t))為時(shí)刻t系統(tǒng)中所有用戶累計(jì)全局占優(yōu)資源份額向量.根據(jù)文獻(xiàn)[13]，結(jié)合本文我們得出累計(jì)全局占優(yōu)資源份額向量滿足字典序最大最小最優(yōu)的定義：

G(t)=(1.0,0.2,0.6)，

G′(t)=(0.6,0.3,0.4)，

按遞增排列為

maxGτ(t),

(9)

βi(t)≥1,?t,i∈U.

Gτ(t)表示在分配Ui(t)已知情形下任意時(shí)刻t累計(jì)全局占優(yōu)資源份額向量的遞增排序.式(9)目標(biāo)函數(shù)是指當(dāng)所分配資源使用戶累計(jì)全局累計(jì)占優(yōu)資源份額向量G(t)滿足字典序最優(yōu).式(9)第1個(gè)約束條件表示在時(shí)刻t所有用戶在任意1臺(tái)虛擬機(jī)分得的資源量不能超過(guò)該虛擬機(jī)的資源總量，第2個(gè)約束條件是指分配機(jī)制保證所有用戶不發(fā)生共享缺損.

因?yàn)橛脩鬷在時(shí)刻t的最大需求任務(wù)數(shù)具有上限值為Bi(t)，所以根據(jù)式(5)可得用戶i在時(shí)刻t累計(jì)全局累計(jì)占優(yōu)資源份額最大值為

根據(jù)文獻(xiàn)[13],在時(shí)刻t對(duì)于任意一個(gè)非負(fù)數(shù)G(t)>0,令A(yù)(G(t))=(G1(t),G2(t),…,Gn(t))為用戶累計(jì)全局占優(yōu)資源份額向量，其中:

假設(shè)有一個(gè)用戶k∈U在時(shí)刻t的累計(jì)全局占優(yōu)資源份額為

其中:

由于G′(t)為一個(gè)可行的累計(jì)全局占優(yōu)資源份額向量，可得:

且有:

證畢.

引理2.若用戶k到時(shí)刻t分配資源所完成累計(jì)任務(wù)數(shù)小于時(shí)刻t累計(jì)提交任務(wù)需求上限，即:

成立時(shí)，字典序最優(yōu)累計(jì)全局占優(yōu)資源份額向量G*(t)中用戶k累計(jì)全局占優(yōu)資源份額大于或等于所有用戶累計(jì)全局占優(yōu)資源份額,即:

證畢.

其中:

根據(jù)式(5)，我們可以得到時(shí)刻t新的累計(jì)全局占優(yōu)資源份額向量

其中:

由式(5)可得:

證畢.

定理1.當(dāng)系統(tǒng)中有n個(gè)用戶、K個(gè)虛擬機(jī)時(shí)，TV-DRF機(jī)制所滿足激勵(lì)共享屬性.

證明. 若到任意時(shí)刻t為止，使任意一個(gè)用戶i∈U分得的累計(jì)資源量為其獨(dú)有的資源量時(shí)，有βi(t)=1.這就是說(shuō)在任意時(shí)刻t,對(duì)于任意一個(gè)用戶i∈U而言，有使βi(t)≥1的分配是存在.從而有，到任意t時(shí)刻為止,TV-DRF機(jī)制使所有用戶全局共享系數(shù)均大于等于1的分配也是存在的，即βi(t)≥1,?t,i∈U.所以TV-DRF機(jī)制滿足激勵(lì)共享屬性.

證畢.

定理2.當(dāng)系統(tǒng)中有n個(gè)用戶、K個(gè)虛擬機(jī)時(shí)， TV-DRF機(jī)制滿足帕累托最優(yōu)屬性.

且不會(huì)使其他用戶最大可執(zhí)行任務(wù)減少，相應(yīng)地，根據(jù)式(5)可得新的時(shí)刻t累計(jì)全局累計(jì)占優(yōu)資源份額向量為

其中，

證畢.

定理3.當(dāng)系統(tǒng)中有n個(gè)用戶、K個(gè)虛擬機(jī)時(shí)，TV-DRF機(jī)制滿足無(wú)嫉妒屬性.

根據(jù)式(4)可得:

根據(jù)式(5)可得:

上式矛盾，所以TV-DRF機(jī)制滿足無(wú)嫉妒屬性.

證畢.

定理4.當(dāng)系統(tǒng)中有n個(gè)用戶、K個(gè)虛擬機(jī)時(shí)，TV-DRF機(jī)制滿足可信性.

則用戶i在任何時(shí)刻謊報(bào)資源需求也不會(huì)增加其效用.所以，我們考慮用戶i累計(jì)完成任務(wù)數(shù)沒(méi)有達(dá)到提交任務(wù)數(shù)上限情形，即：

根據(jù)引理2可得:

(10)

根據(jù)式(1)～(5),TV-DRF機(jī)制所得用戶i在時(shí)刻t謊報(bào)資源需求時(shí)字典序最優(yōu)全局累計(jì)占優(yōu)資源份額向量為

根據(jù)式(1)(2)可知，若用戶i在時(shí)刻t謊報(bào)資源需求時(shí)，獲得的資源比誠(chéng)實(shí)情形下多,則用戶i至少在某一個(gè)虛擬機(jī)k∈S上分得的資源比誠(chéng)實(shí)情形下多：

(11)

根據(jù)式(5)可知, 當(dāng)用戶i在時(shí)刻t謊報(bào)資源需求時(shí),在虛擬機(jī)k上的累計(jì)全局占優(yōu)資源份額比誠(chéng)實(shí)情形下多：

根據(jù)式(5)可得:

(12)

所以一定存在至少一個(gè)用戶h≠i,當(dāng)i在時(shí)刻t謊報(bào)需求時(shí),在虛擬機(jī)k上獲得的第j種資源比i誠(chéng)實(shí)報(bào)告需求時(shí)少：

(13)

結(jié)合上式，根據(jù)式(2)及用戶完成任務(wù)數(shù)不超過(guò)上限有:

(14)

(15)

根據(jù)引理2有:

(16)

結(jié)合式(10)(12)(15)(16)可得:

上式矛盾，所以TV-DRF機(jī)制滿足可信屬性.

證畢.

3 TV-DRF算法

本文結(jié)合第3節(jié)TV-DRF機(jī)制與文獻(xiàn)[9，12]的啟發(fā)式算法設(shè)計(jì)一個(gè)動(dòng)態(tài)資源調(diào)度算法，即基于云計(jì)算資源共享系統(tǒng)多虛擬機(jī)情形下用戶提交多組有限的時(shí)變?nèi)蝿?wù)需求的動(dòng)態(tài)多資源公平分配的啟發(fā)式算法TV-DRF (time varied-DRF)算法.

(17)

3) 執(zhí)行步驟1、步驟2，當(dāng)系統(tǒng)中的某種資源j,1≤j≤m分配完畢時(shí)，或者所有用戶任務(wù)執(zhí)行完畢時(shí)，資源分配結(jié)束.

算法1.TV-DRF算法.

輸出:資源分配向量U(t).

βi(t)←0；*任意一個(gè)用戶i∈U,時(shí)刻t全局共享系數(shù)*

G(t)=(G1(t),G2(t),…,Gn(t))←0；*時(shí)刻t所有用戶累計(jì)全局占優(yōu)資源份額向量*

② While 用戶任務(wù)沒(méi)有完成,?i∈U

③ Fori=1 ton

⑤ Ifβj(t)<1

⑥alloc(j)；

⑦ Else

⑧ Fori=1 ton

⑩alloc(g)；

在時(shí)刻t1，由于用戶A需要完成的任務(wù)數(shù)少，TV-DRF算法將2臺(tái)虛擬機(jī)資源分配給用戶A執(zhí)行15個(gè)任務(wù)所需資源后將余下資源分給用戶B，用戶B分得70個(gè)任務(wù)所需資源，此時(shí)資源耗盡.根據(jù)全局共享系數(shù)定義可得βA(t1)=1，βB(t1)=1.4.在時(shí)刻t2開始時(shí)，根據(jù)2個(gè)用戶第2個(gè)時(shí)刻資源需求及時(shí)刻t1分配可知，用戶A全局共享系數(shù)為0.23，用戶B全局共享系數(shù)為0.7,優(yōu)先分配資源給用戶A，分配資源(35CPU,35 GB)給用戶A，使得用戶A全局共享系數(shù)不小于用戶B.此時(shí)按照共享系數(shù)最小用戶優(yōu)先分配資源的方式分配，當(dāng)用戶A，B分別分得(50CPU,50 GB)和(40CPU,20 GB)資源時(shí),2個(gè)用戶共享系數(shù)已等于1.此時(shí)按照累計(jì)全局占優(yōu)資源份額最小的用戶最大的方式分配最終得βA(t2)=1.125，βB(t2)=1.

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

本文采用來(lái)自阿里巴巴集群數(shù)據(jù)集[15]12 951個(gè)任務(wù)運(yùn)行所需的CPU和Memory資源作為本文實(shí)驗(yàn)中用戶資源需求.數(shù)據(jù)集中每個(gè)用戶以Job的形式提交多組任務(wù)資源需求，每個(gè)Job包含多組任務(wù)需求，每組任務(wù)由多個(gè)具有相同資源需求的實(shí)例組成,實(shí)驗(yàn)從該數(shù)據(jù)集中隨機(jī)選取5，20，100個(gè)用戶，用戶資源需求如圖1和圖2所示，圖1，2中縱坐標(biāo)表示用戶每個(gè)實(shí)例需要CPU數(shù)，橫坐標(biāo)表示每個(gè)實(shí)例需要內(nèi)存數(shù)，實(shí)心圓的面積與用戶任務(wù)數(shù)成正比，任務(wù)數(shù)越多則圓的面積越大.本文實(shí)驗(yàn)?zāi)M服務(wù)器配置如表1所示，其中服務(wù)器臺(tái)數(shù)為每個(gè)用戶所具有的服務(wù)器資源.本文假設(shè)用戶共享資源后虛擬機(jī)數(shù)與物理服務(wù)器數(shù)量相同.

Fig.1 20 users demand distribution圖1 20個(gè)用戶需求分布

Fig. 2 100 users demand distribution圖2 100個(gè)用戶需求分布

User NumberPer User Own MachinesCPU Capacity∕coreMemory Capacity∕GB512504020125040100120040

本文實(shí)驗(yàn)平臺(tái)配置為:CPU為Intel i5-3230 M,12 GB內(nèi)存，500 GB硬盤，實(shí)驗(yàn)配置如下：

1) 由于一個(gè)用戶可以提出多組時(shí)變?nèi)蝿?wù)需求，本文將數(shù)據(jù)集batch_task文件中每組task看作為一個(gè)用戶在一個(gè)時(shí)刻的任務(wù)資源需求.

2) 實(shí)驗(yàn)假設(shè)每個(gè)用戶共享到集群中每一臺(tái)虛擬機(jī)的每一種資源比例相同.

3) 將數(shù)據(jù)集中batch_task文件的create_timestamp認(rèn)為是用戶任務(wù)需求的提交時(shí)間,任務(wù)執(zhí)行時(shí)長(zhǎng)為單位時(shí)長(zhǎng).

4) 通過(guò)用戶任務(wù)實(shí)例隊(duì)列方式，對(duì)資源配置進(jìn)行模擬，即每個(gè)用戶有一個(gè)任務(wù)實(shí)例隊(duì)列，需求提交事件看做是實(shí)例到達(dá)事件發(fā)生，此時(shí)TV-DRF算法對(duì)用戶共享資源進(jìn)行分配.

本文通過(guò)實(shí)驗(yàn)比較TV-DRF算法與用戶在資源不共享的分配情形下中，5用戶最小用戶累計(jì)占優(yōu)資源份額和20,100用戶情形下資源利用率，執(zhí)行100次取平均來(lái)評(píng)估TV-DRF算法性能.

1) 使用戶累計(jì)占優(yōu)資源份額滿足字典序最優(yōu)

從圖3可以看出，由于TV-DRF算法目標(biāo)是使用戶累計(jì)占優(yōu)資源份額滿足最大、最小，因?yàn)橛脩舨还蚕砬樾蜗路值玫馁Y源為其自有資源.所以，TV-DRF算法與用戶不共享資源情形相比，最小的累計(jì)占優(yōu)資源份額，隨著時(shí)間的推移，差距越來(lái)越大.這說(shuō)明TV-DRF算法保證了分配過(guò)程中累計(jì)占優(yōu)資源最小的用戶能分配最多的資源，也就是該用戶完成任務(wù)數(shù)最大.與不共享算法相比，保證了用戶完成的累計(jì)任務(wù)數(shù)盡可能多.

Fig. 3 Cumulative dominant share圖3 累計(jì)占優(yōu)資源份額

Fig. 4 CPU utilization (20 users)圖4 CPU利用率(用戶數(shù)20)

2) 高資源利用率

本文將TV-DRF算法下的資源利用率與用戶在不共享資源的條件下系統(tǒng)的資源率進(jìn)行比較.圖4～7分別表示在用戶數(shù)為20和用戶數(shù)為100情形下系統(tǒng)的資源利用率.可以看出TV-DRF算法在任意時(shí)刻的系統(tǒng)資源利用率都高于用戶在不共享資源條件下系統(tǒng)的資源利用率.

Fig. 5 Memory utilization (20 users)圖5 Memory利用率(用戶數(shù)20)

Fig. 6 CPU utilization (100 users)圖6 CPU利用率(用戶數(shù)100)

Fig. 7 Memory utilization (100 users)圖7 Memory利用率(用戶數(shù)100)

總之，TV-DRF算法在滿足公平性，使所有分配用戶能夠完成較多任務(wù)的同時(shí)，具有很高的資源利用率.

5 結(jié)束語(yǔ)

本文針對(duì)云計(jì)算資源共享系統(tǒng)中用戶有限多組時(shí)變?nèi)蝿?wù)資源需求的分配問(wèn)題，提出了一種基于資源共享公平的多資源公平分配機(jī)制.該機(jī)制根據(jù)用戶不同時(shí)刻的有限時(shí)變?nèi)蝿?wù)需求和用戶共享資源量建立規(guī)劃模型，證明了在這種機(jī)制下用戶所得分配滿足4個(gè)公平屬性：激勵(lì)共享、帕累托最優(yōu)、無(wú)嫉妒、可信.最后，實(shí)驗(yàn)基于用戶累計(jì)占優(yōu)資源份額，資源利用率與不共享資源算法進(jìn)行對(duì)比，進(jìn)一步說(shuō)明TV-DRF算法能在保證用戶滿足累計(jì)占優(yōu)資源份額字典序最優(yōu)的同時(shí)，有較高資源利用率.但是，由于在算法執(zhí)行過(guò)程中需要判斷用戶共享缺損，累計(jì)資源分配量等因素，使得算法在用戶數(shù)和虛擬機(jī)數(shù)較多時(shí)分配執(zhí)行速度不占優(yōu)勢(shì).所以如何有效地使任務(wù)和虛擬機(jī)得到更優(yōu)化的分配，以提高分配速度將是下一步研究重點(diǎn).