基于共享資源量的動態(tài)多資源公平分配策略

張瀟璐，劉曦，李偉東，張學(xué)杰

（云南大學(xué)信息學(xué)院，云南 昆明 650091）

基于共享資源量的動態(tài)多資源公平分配策略

張瀟璐，劉曦，李偉東，張學(xué)杰

（云南大學(xué)信息學(xué)院，云南 昆明 650091）

針對云計(jì)算共享系統(tǒng)中多資源分配問題，提出一種基于共享資源量的動態(tài)多資源公平分配策略。該策略根據(jù)不同用戶資源需求和共享資源量建立一個線性規(guī)劃模型，同時證明該模型滿足公平分配的4個重要屬性：動態(tài)帕累托最優(yōu)、激勵共享、動態(tài)無嫉妒性和防止策略性操作，而且給出一種改進(jìn)的動態(tài)多資源公平分配算法來提高算法運(yùn)行效率。實(shí)驗(yàn)結(jié)果表明，所提動態(tài)多資源公平分配策略能夠在滿足任務(wù)資源需求的同時，盡可能保證公平分配下最大化占優(yōu)資源份額，并且改進(jìn)的分配算法能夠有效地提高資源的分配效率。

云計(jì)算；多資源公平分配；占優(yōu)資源；共享資源量

1 引言

云計(jì)算共享系統(tǒng)通過虛擬化技術(shù)將多種計(jì)算資源進(jìn)行整合，實(shí)現(xiàn)資源的共享功能，為資源的統(tǒng)一管理和調(diào)度提供技術(shù)保證和條件。對云共享系統(tǒng)而言，資源分配調(diào)度是一個至關(guān)重要的組件。云共享系統(tǒng)根據(jù)當(dāng)前各個虛擬機(jī)節(jié)點(diǎn)的資源需求，對資源進(jìn)行合理分配，使虛擬機(jī)節(jié)點(diǎn)能夠有足夠的資源完成計(jì)算任務(wù)并保證用戶之間公平有效地共享資源。因此，如何有效地將有限資源分配給各虛擬機(jī)節(jié)點(diǎn)，使云共享系統(tǒng)滿足任務(wù)資源需求的同時兼顧資源分配的公平和效率是需要解決的關(guān)鍵問題。

目前，很多工作對資源公平分配問題進(jìn)行了深入而廣泛的研究。最常用的分配策略是最大最小公平模型（max-min fairness）[1]，最早用于控制網(wǎng)絡(luò)流量，以實(shí)現(xiàn)公平分配網(wǎng)絡(luò)帶寬。最大最小公平模型的基本思想是使資源分配的最小分配量盡可能最大化，防止任何網(wǎng)絡(luò)流被“餓死”，同時在一定程度上盡可能增加每個流的速率。最大最小公平模型被認(rèn)為是一種很好權(quán)衡公平性和有效性的自由分配策略，由此衍生出的大量算法被應(yīng)用于各種資源分配上，包括網(wǎng)絡(luò)帶寬、CPU、內(nèi)存等，但這些公平分配的研究主要集中在單一資源類型。

在云共享系統(tǒng)中，每個虛擬機(jī)節(jié)點(diǎn)的資源都是多維的，加上用戶任務(wù)資源需求的多樣性，相對于單一資源的分配，多資源類型的分配更難做到完全的公平性。另外，用戶為了得到更多資源，可能通過需求欺騙、惡意占用等手段破壞資源分配的公平性，因此，多資源的公平合理分配顯得尤為重要。已有的多資源公平分配研究成果中，DRF（DRF,dominant resource fairness）機(jī)制[2]被廣泛應(yīng)用到Hadoop Yarn[3]和Mesos[4]系統(tǒng)中。DRF計(jì)算每個用戶每種資源的分配數(shù)量與資源總量的比值，所有比值中的最大值為該用戶的占優(yōu)資源份額（dominant share），與其相對應(yīng)的資源為該用戶的占優(yōu)資源（dominant resource）。DRF機(jī)制的基本思想是最大化所有用戶占優(yōu)資源份額中的最小者，從而將多資源分配問題轉(zhuǎn)化為單資源分配問題。該機(jī)制擴(kuò)展了最大最小公平模型，使其能夠在多種不同資源并存情況下保證分配的公平性。然而，DRF機(jī)制的提出是基于每個用戶對資源池共享相同資源量的假設(shè)，在實(shí)際情況中，每個用戶對資源的共享量可能不同，且共享量多的用戶希望得到更多的資源。因此，文獻(xiàn)[2]又提出加權(quán)DRF機(jī)制（weighted DRF），該機(jī)制對每個用戶都關(guān)聯(lián)一個共享資源量（權(quán)值向量），最大化用戶得到的占優(yōu)資源份額與其共享資源量的比值中最小值來實(shí)現(xiàn)資源的公平分配。如果所有用戶的共享資源量相同，則加權(quán)DRF機(jī)制轉(zhuǎn)換為DRF機(jī)制。

加權(quán) DRF機(jī)制解決基于不同共享資源量的公平分配問題，但在實(shí)際云共享系統(tǒng)中，用戶會在不同的時刻進(jìn)入系統(tǒng)，用戶帶來的共享資源量使系統(tǒng)中可分配的資源總量發(fā)生動態(tài)變化，資源分配機(jī)制應(yīng)該根據(jù)用戶資源需求對資源分配情況進(jìn)行重新調(diào)整，確保盡可能公平分配，而靜態(tài)分配機(jī)制無法解決由用戶動態(tài)性帶來的資源分配公平性和效率問題。文獻(xiàn)[5]針對資源分配的動態(tài)性做出較大改進(jìn)，允許用戶隨時進(jìn)入系統(tǒng)但不離開的情形，然而研究者也是基于用戶進(jìn)入云共享系統(tǒng)時帶來相同資源份額的假設(shè)，并未考慮實(shí)際用戶對資源共享的差異性所帶來的公平性問題，并且在資源分配過程中采用注水（water filling）算法[5]，該算法的運(yùn)行時間復(fù)雜度是關(guān)于輸入長度的偽多項(xiàng)式函數(shù)，操作性和用戶資源需求與資源公平分配適應(yīng)性比較差，從而導(dǎo)致比較低的資源分配效率。

針對上述問題，本文對動態(tài)情形下，用戶的資源需求以及用戶動態(tài)進(jìn)入系統(tǒng)時所共享資源量的差異性帶來的公平性和資源利用率問題做進(jìn)一步綜合考慮，面向云共享系統(tǒng)，提出基于共享資源量的動態(tài)多資源公平分配策略（DMFA-SRQ, dynamic multi-resources fair allocation based on shared resource quantity）。該策略基于用戶資源需求和共享資源量，重新定義動態(tài)情形下占優(yōu)資源份額，給出一個線性規(guī)劃模型，在滿足用戶資源需求同時，盡可能實(shí)現(xiàn)占優(yōu)資源的最大公平性分配，并且證明該模型滿足公平分配的4個重要屬性：動態(tài)帕累托最優(yōu)（DPO, dynamic Pareto optimality）、激勵共享（SI,sharing incentive）、動態(tài)無嫉妒性（DEF, dynamic envy freeness）和防止策略性操作（SP, strategy proofness）；提出改進(jìn)的動態(tài)多資源公平分配算法使算法運(yùn)行時間復(fù)雜度減小到Ο ( n2logn)（n為系統(tǒng)中用戶數(shù)）。理論和實(shí)驗(yàn)表明，本文提出的方法解決了動態(tài)情形下基于不同共享資源量的多資源公平分配問題，且有效提高了算法的運(yùn)行效率。

2 相關(guān)工作

近年來，研究者們提出了各種各樣有關(guān)公平性的資源分配算法。在單一資源類型的公平分配研究中，文獻(xiàn)[6～9]研究 CPU時間、鏈路帶寬資源的公平分配策略，利用“max-min fairness”思想，最大化每個用戶分配到的最小資源，保證多數(shù)用戶的資源需求得到滿足，實(shí)現(xiàn)公平性分配。文獻(xiàn)[10,11]研究在2個用戶利益之間尋求資源分配平衡機(jī)制，提出“proportional fairness”方法；Zukerman等[12]提出針對單一資源在公平和效率之間進(jìn)行折中的效用評估算法；Lan等[13]基于公平分配理論屬性，提出一種資源分配機(jī)制，并為公平性的度量提供了準(zhǔn)則。

在多資源公平分配研究中，Ghodsi等[2]最早系統(tǒng)地研究云計(jì)算系統(tǒng)中多資源公平分配問題，基于用戶相同共享資源量的假設(shè)，提出一種DRF機(jī)制。該機(jī)制顯示出諸多令人滿意的公平屬性，吸引了大量研究者的關(guān)注，并得到了廣泛推廣。Dolev等[14]提出基于瓶頸資源的公平分配（BBF, bottleneck based fairness）算法，并證明BBF滿足激勵共享和無嫉妒性2種公平屬性；Gutman等[15]考慮DRF在多個效用模型下的通用性，并且能夠在多項(xiàng)式時間內(nèi)解決BBF公平分配問題；Bhattacharya[16]重新定義 DRF以此來支持多層次資源分配；Wang等[17]提出改進(jìn) DRF機(jī)制，使其能夠適用于異構(gòu)云計(jì)算環(huán)境；Joe-Wong等[18]推廣 DRF，量化并使其成為一個一體化的框架，以權(quán)衡分配公平和分配效率；Psomans等[19]研究在多個計(jì)算節(jié)點(diǎn)上對離散任務(wù)的多資源公平分配方法；Parks等[20]用多種方法擴(kuò)展DRF機(jī)制，適用于某些資源的零需求、不可劃分任務(wù)和不同權(quán)重等情形。

以上工作都是基于系統(tǒng)中所有用戶資源需求的靜態(tài)分配，與目前云共享系統(tǒng)中用戶隨時進(jìn)入和退出的動態(tài)性有本質(zhì)的不同，而且資源分配過程中并沒有考慮到歷史分配信息。在動態(tài)情形下，Zeldes等[21]提出基于資源瓶頸和全局屬性的在線公平分配機(jī)制；文獻(xiàn)[22,23]分別在靜態(tài)和動態(tài)情形下研究基于用戶有限任務(wù)請求數(shù)量的多資源公平分配機(jī)制，但未解決在用戶動態(tài)進(jìn)入云共享系統(tǒng)時用戶資源請求和共享資源量的差異性對多資源公平分配的影響。Kash等[5]雖提出基于用戶相同共享資源量的多資源公平分配策略DDRF，但這種策略并沒有考慮用戶共享資源量的差異性所帶來的實(shí)際資源分配的公平性和效率問題。

綜上，雖然目前很多工作在多資源公平分配問題上取得了一定進(jìn)展，但對用戶動態(tài)性以及資源需求和共享資源量差異性帶來的分配公平性和資源利用率問題缺乏進(jìn)一步考慮，因此，本文引入一種基于共享資源量的動態(tài)多資源公平分配策略DMFA-SRQ，給出一個線性規(guī)劃分配模型，并提出一種改進(jìn)的動態(tài)多資源公平分配算法。

3 問題描述及相關(guān)定義

在云共享系統(tǒng)中，用戶請求是由具有不同資源配置的虛擬機(jī)進(jìn)行響應(yīng)，為方便以下討論，這里做個假定：用戶任務(wù)的資源請求可認(rèn)為是虛擬機(jī)資源請求，用戶任務(wù)的資源分配過程即虛擬機(jī)資源部署過程。

假定云共享系統(tǒng)中資源池包含m種硬件資源，如CPU、內(nèi)存、磁盤、網(wǎng)絡(luò)帶寬等。令 R = {1,2,…,m}表示資源種類集合， U= {1,2,…, n}表示用戶集合。用戶i的資源需求向量為 Di=(Di1,… , Dim)，其中，Dij表示用戶i的任務(wù)對資源j的需求量占整個資源池中資源j總量的比例，且 Dij> 0。對Di做歸一化

令 wi表示用戶i對資源池中每種資源的共享資源量，且當(dāng)系統(tǒng)中有k個用戶時，k ∈ {1,… ,n}，令 xik表示用戶i分配得到的占優(yōu)資源份額數(shù)，即可執(zhí)行的任務(wù)數(shù)。定義用戶i的占優(yōu)資源份額（dominant share）為

根據(jù)占優(yōu)資源定義，上式可簡化為

在動態(tài)情形下，假定用戶在不同時刻順序到達(dá)，即用戶k在用戶k?1之后到達(dá)，且用戶（i>k）的資源需求di>k未知。用戶進(jìn)入系統(tǒng)后不會離開，并且每個用戶任務(wù)所需資源量不會隨時間發(fā)生改變。當(dāng)系統(tǒng)中有k個用戶時，得到一個動態(tài)多資源公平分配方案Ak=(Ak,… ,,… ,)， 其 中 ，= (,…,

在資源j上分配得到的資源數(shù)量，滿足以下公式

并且對任意用戶i， i≤k? 1，k≥2，其分配結(jié)果是一個不可逆過程，即≥。對所有用戶i， 給定一個分配 Ak，則在虛擬機(jī)上被調(diào)度執(zhí)行的最大

ij任務(wù)數(shù)按如下公式計(jì)算

i + ij對任意資源 j， j∈R，若存在這樣一個y，使=d y成立，則稱 Ak為無浪費(fèi)分配方案。ij ij

本文設(shè)計(jì)一種動態(tài)情形下無浪費(fèi)資源分配方案：基于共享資源量的動態(tài)多資源公平分配策略（DMFA-SRQ），目標(biāo)是當(dāng)系統(tǒng)中存在k個用戶時，最大化占優(yōu)資源份額kM ，從而得到最大化的占優(yōu)資源份額數(shù)，并且盡可能保證資源分配的公平性。因此，DMFA-SRQ策略可形式化為

該線性規(guī)劃模型中第一個約束條件是盡可能保證占優(yōu)資源的公平分配，同時，共享資源量越多的用戶分配得到的占優(yōu)資源份額數(shù)就越多。另外，還給出在多資源分配過程中其他2個約束條件，即當(dāng)系統(tǒng)中有k個用戶時，對任意用戶分配得到的占優(yōu)資源份額數(shù)不小于系統(tǒng)中有k?1個用戶時的分配情況，滿足分配的不可逆性；當(dāng)系統(tǒng)中有k個用戶時，系統(tǒng)可以分配的資源量最多為

圖1舉例說明DMFA-SRQ策略的資源分配情況。假設(shè)系統(tǒng)中共有3個用戶，分別順序進(jìn)入系統(tǒng)。每個用戶的資源需求向量和共享資源量分別為當(dāng)系統(tǒng)中只有用戶1時，分配得到的占優(yōu)資源份額；當(dāng)系統(tǒng)中

在靜態(tài)分配情形下，根據(jù)文獻(xiàn)[15,21]以及式(4)的線性規(guī)劃方程組，可通過式(5)求得靜態(tài)最優(yōu)解

接下來提出一種快速算法 DMFA-SRQ以解決動態(tài)分配情形下kM 最大化問題。

4 DMFA-SRQ策略的公平性分析

無論是在云共享系統(tǒng)[2,19]，還是在經(jīng)濟(jì)學(xué)[24,25]中，資源分配的效率和公平性被廣泛認(rèn)為是最重要的屬性，也是衡量一個公平分配機(jī)制優(yōu)劣的判斷標(biāo)準(zhǔn)。文獻(xiàn)[5]引入在動態(tài)情形下多資源公平分配機(jī)制所滿足的4個重要屬性：動態(tài)帕累托最優(yōu)、激勵共享、動態(tài)無嫉妒性、防止策略性操作。本文在此基礎(chǔ)上，針對動態(tài)情形下用戶資源需求以及用戶共享資源量的差異所提出的公平分配機(jī)制應(yīng)滿足的4個重要屬性做進(jìn)一步討論。

1) 動態(tài)帕累托最優(yōu)

對于所有用戶的可行分配方案 Ak，其中任意一個用戶i的資源分配方案，有() >()成立， 那么將存在一個用戶h，使 N () <()成立。

h

2) 激勵共享

如果一種動態(tài)公平分配機(jī)制系統(tǒng)中有k個用戶時，對任意用戶i，i∈U ，i≤k，有 N (Ak)≥ N( w )

i i i i成立，則認(rèn)為該機(jī)制滿足SI屬性。

3) 動態(tài)無嫉妒性

在動態(tài)公平分配機(jī)制中，如果用戶i嫉妒用戶h，i, h∈U，說明用戶h是在用戶i之前進(jìn)入系統(tǒng)，并且自用戶i進(jìn)入系統(tǒng)之后用戶h未再被分配資源，則該機(jī)制滿足DEF屬性。即當(dāng)系統(tǒng)中有k個用戶時，如果成立，則有h

4) 防止策略性操作

用戶不能通過謊報資源需求來提高自己的占優(yōu)資源份額，此屬性滿足需求不可欺騙性。令為用戶i謊報虛假資源di，而其他用戶都提交真實(shí)資源需求情況下得到的分配方案，則有i≤k成立。

圖1 DMFA-SRQ策略的資源分配結(jié)果

DPO屬性表明當(dāng)用戶資源分配已經(jīng)達(dá)到飽和時，它可能在影響其他用戶分配的前提下，增加自己的占優(yōu)資源份額數(shù)。SI屬性確保用戶最終分配得到的占優(yōu)資源份額數(shù)不少于用戶帶來的共享資源量，并且用戶帶來的共享資源量越多，分配到的資源就越多。DEF屬性說明如果一種動態(tài)分配機(jī)制是有嫉妒性的，則用戶會嫉妒比其早進(jìn)入系統(tǒng)且分配到較多占優(yōu)資源份額的用戶。SP屬性規(guī)定用戶不能通過謊報自己的需求來獲得更多額外資源。

引理1 當(dāng)系統(tǒng)中有k個用戶時，k ∈{1,…, n}，對用戶i，i∈U ，i≤k，=max{Mkw, xk?1}。

i i

證明 考慮系統(tǒng)中有k個用戶時，根據(jù)式(4)中前 2個 約束 條 件≥Mkw， xk≥ xk?1，得 到i i i

證明 利用數(shù)學(xué)歸納法證明。當(dāng)i>k，h>k時，== 0。假設(shè)當(dāng)系統(tǒng)中有k?1個用戶存在時， k ∈ {h, … , n}，不等式成立。當(dāng)系統(tǒng)中存在k個用戶時，根據(jù)引理1及得出即證畢。

h則有根據(jù)h

從引理1可以看出，對系統(tǒng)中每個用戶而言，不同資源需求的用戶根據(jù) DMFA-SRQ策略分配得到的占優(yōu)資源份額隨著更多用戶在不同時刻進(jìn)入系統(tǒng)后呈現(xiàn)單調(diào)非遞減性。引理2表明用戶得到的占優(yōu)資源份額隨著用戶進(jìn)入系統(tǒng)的先后順序呈現(xiàn)單調(diào)非遞增性。引理3則表示當(dāng)系統(tǒng)中有k個用戶時，如果用戶h的占優(yōu)資源份額大于用戶i，說明用戶h比用戶i更早進(jìn)入系統(tǒng)，且自用戶i進(jìn)入系統(tǒng)后，用戶h未被再分配資源，因此，用戶i會嫉妒用戶h，這與動態(tài)無嫉妒屬性（DEF）所描述的含義相同。下面根據(jù)以上的引理，驗(yàn)證 DMFA-SRQ策略滿足4個重要屬性：動態(tài)帕累托最優(yōu)、激勵共享、動態(tài)無嫉妒性、防止策略性操作。

定理1 當(dāng)系統(tǒng)中有k個用戶時，k ∈{1,…, n}，DMFA-SRQ策略滿足DPO屬性。

證明 當(dāng)系統(tǒng)中有k個用戶時，至少存在一種資源 j(j∈R)和一個最優(yōu)解 Mk，使式(4)中第3個約束條件成立。否則，如果存在一個不滿足分配方案的用戶i，在不影響其他用戶分配情況下，提高自己分配到的占優(yōu)資源份額數(shù)，即增加一個很小的量+ε，ε>0，使 Mk值也相應(yīng)增加，與 Mk是問題最優(yōu)解相矛盾，因此，DMFA-SRQ滿足DPO屬性。

定理2 當(dāng)系統(tǒng)中有k個用戶時，k ∈{1,…, n}，DMFA-SRQ策略滿足SI屬性。

證明 考慮系統(tǒng)中只有一個用戶時，根據(jù)式(4)中第1個約束條件，有=w1，M1=1，則可以得到≥ M1w ≥ w。接下來，利用數(shù)學(xué)歸納法證明

1 1當(dāng)系統(tǒng)中有k個用戶時， k ∈ {2,…, n}，對任意用戶i，i∈U ，i≤k，則有)≥wi)，即≥wi。

定理3 當(dāng)系統(tǒng)中有k個用戶時，k ∈{1,…, n}，DMFA-SRQ策略滿足DEF屬性。

證明 當(dāng)系統(tǒng)中有k個用戶時，如果對任意用戶i, h≤k，用戶i嫉妒用戶h，即根據(jù)引理 3，則有由上述不等式可以推出否則，得出以下不等式

其中，j*為用戶i的占優(yōu)資源，由式(6)可知用戶i得到比用戶h更多的占優(yōu)資源份額，與條件矛盾。因此，由及引理3可以推出DMFA- SRQ滿足DEF屬性。證畢。

接下來，證明DMFA-SRQ策略滿足SP屬性，首先，給出引理 4。當(dāng)系統(tǒng)中有k個用戶時，k ∈ {1,… , n}，假設(shè)用戶i，i∈U，謊報不真實(shí)的資源需求向量，則至少存在一個用戶t，t∈ {i, … ,k}，自加入系統(tǒng)之后使用戶i獲得比較多的優(yōu)勢份額數(shù)量。此時，對任意其他真實(shí)需求用戶h，在不真實(shí)資源需求環(huán)境下分配得到的占優(yōu)資源份額數(shù)表示為，h≤k，同時， M?k為求解線性規(guī)劃方程式(4)得到的最優(yōu)解。

證明 考慮以下2種情況。

定理4 當(dāng)系統(tǒng)中有k個用戶時，k ∈{1,… ,n}，DMFA-SRQ策略滿足SP屬性。

證明 利用反證法證明。當(dāng)系統(tǒng)中有k個用戶時，用戶i謊報不真實(shí)資源需求，當(dāng)?shù)趖個用戶進(jìn)入系統(tǒng)時，用戶i分配得到較多的優(yōu)勢份額數(shù)，則存在一種資源j，j∈R，使分配滿足動態(tài)帕累托最優(yōu)性質(zhì)，并根據(jù)引理4可以推出以下不等式

不等式(7)與式(4)中第3個約束條件相矛盾，因此，DMFA-SRQ滿足SP屬性。證畢。

5 DMFA-SRQ算法

Water filling算法[5]是一種在動態(tài)情形下實(shí)現(xiàn)資源最大最小化公平分配的經(jīng)典算法，但代價是算法運(yùn)行時間過長。本文基于第3節(jié)中提出的線性規(guī)劃模型，設(shè)計(jì)了一個更為快速的Ο ( n2logn)多項(xiàng)式時間復(fù)雜度算法，即用基于共享資源量的動態(tài)多資源公平分配算法改進(jìn)求解最優(yōu)分配方案的算法運(yùn)行效率問題。

該算法基于本文定義的最大化 Mk以及約束條件，尋找一個用戶τ對應(yīng)的vτ，使如果> vτ成立, 則否則從而確定，并最終得到該算法主要思想如下。

1) 當(dāng)系統(tǒng)中有k個用戶時，對k?1個 xik?1值進(jìn)行非遞增排序（i

3) 根據(jù)式(4)線性規(guī)劃方程組中前2個約束條件以及引理 1，當(dāng)系統(tǒng)中有k個用戶時，每個用戶i被分配執(zhí)行的任務(wù)數(shù)為，即從而最終得到用戶i在資源 j上的分配方案。DMFA-SRQ算法的操作過程如算法1所示。

算法1 DMFA-SRQ算法

1) 輸入：Demanddi,1≤i≤k

4)k←2;

7)

8) else, do

10)

12)

14) goto 10);

15) else, do

17) goto 10);

18) end if;

19) end while;

21)

24)k ←k+1;

25) end while

當(dāng)系統(tǒng)中有k個用戶時，本文提出的DMFA-SRQ 算法利用二分法思想確定vτ，并得到和最終分配方案(,… ,xk)，算法的運(yùn)行時間取k決于求解vτ值的迭代次數(shù)，因此，該算法的時間復(fù)雜度為Ο ( klogk)。當(dāng)系統(tǒng)中共有n個用戶時，整體算法運(yùn)行時間為

6 實(shí)驗(yàn)評估

實(shí)驗(yàn)將采用Google 集群中真實(shí)計(jì)算任務(wù)負(fù)載數(shù)據(jù)集[26]中500個任務(wù)類型文件中的143 601 184個任務(wù)運(yùn)行所需的CPU和Memory資源作為本文實(shí)驗(yàn)中用戶資源請求。實(shí)驗(yàn)從該數(shù)據(jù)集中隨機(jī)選取20、100、500個用戶，對每個用戶的資源需求向量＜CPU,Memory>進(jìn)行歸一化處理，并隨機(jī)設(shè)置每個用戶的共享資源量wi，使其滿足其中，100、500個用戶的資源需求分布如圖 2所示。本文對所提DMFA-SRQ算法與加權(quán)DRF算法進(jìn)行仿真模擬，實(shí)現(xiàn)2種算法的資源分配，并基于最小占優(yōu)資源份額、占優(yōu)資源份額數(shù)和、資源利用率3個最大化目標(biāo)分別在不同用戶數(shù)下各執(zhí)行1 000次取均值得到2種算法的實(shí)驗(yàn)結(jié)果，以此來評估 DMFA- SRQ算法性能。

圖2 用戶資源需求分布

圖3和圖4分別給出了在100個、500個用戶下，用戶共享資源量對用戶資源分配的影響。實(shí)驗(yàn)設(shè)置用戶隨機(jī)動態(tài)進(jìn)入系統(tǒng)并隨機(jī)設(shè)置其共享資源量 wi，滿足

采樣點(diǎn)均勻選取其中 20個用戶分配得到的占優(yōu)資源份額數(shù)，并對wi進(jìn)行升序排列。從圖3和圖4中可以看出，用戶共享資源量與占優(yōu)資源份額數(shù)呈現(xiàn)單調(diào)非遞減性，即用戶共享資源量 wi越多，其分配得到的占優(yōu)資源份額數(shù)就越多。該實(shí)驗(yàn)結(jié)果表明，DMFA-SRQ算法保證資源分配的公平性，并且共享資源量越多的用戶，分配得到的資源也越多。

圖3 100個用戶下占優(yōu)資源份額數(shù)基于wi的變化

圖4 500個用戶下占優(yōu)資源份額數(shù)基于wi的變化

DMFA-SRQ算法目標(biāo)是在盡可能保持公平分配情況下，最大化占優(yōu)資源份額，因此，為進(jìn)一步驗(yàn)證所提出的 DMFA-SRQ算法能夠保證資源分配的公平性和分配效率，本文基于最小占優(yōu)資源份額、占優(yōu)資源份額數(shù)和、資源利用率3個最大化目標(biāo)與靜態(tài)情形下加權(quán) DRF算法進(jìn)行對比分析。

1) 最小占優(yōu)資源份額最大化

i驗(yàn)分配結(jié)果如圖5所示。

圖5 最小占優(yōu)資源份額

從圖5中可以看出，動態(tài)情形下DMFA-SRQ算法得到的占優(yōu)資源份額低于靜態(tài)情形下加權(quán)DRF算法得到的結(jié)果，這主要是因?yàn)閯討B(tài)情形下用戶資源需求未知，分配過程中無法比較所有用戶的最小占優(yōu)資源份額，而且動態(tài)分配需要滿足分配的不可逆性條件。通過實(shí)驗(yàn)結(jié)果也可以看出，基于不同共享資源量的 DMFA-SRQ分配算法在不違背公平性原則的情況下，實(shí)現(xiàn)動態(tài)情形下最小占優(yōu)資源份額最大化分配目標(biāo)，也進(jìn)一步驗(yàn)證了該算法滿足SI屬性。

2) 占優(yōu)資源份額數(shù)和最大化

在經(jīng)濟(jì)學(xué)中，占優(yōu)資源份額數(shù)和是衡量策略效率的一個重要指標(biāo)[5]。當(dāng)系統(tǒng)中有k個用戶時，給出占優(yōu)資源份額數(shù)和的定義為圖 6 給出DMFA-SRQ算法與加權(quán)DRF算法的占優(yōu)資源份額數(shù)和的對比。

圖6 占優(yōu)資源份額數(shù)和

從圖6中可以看出，動態(tài)情形下的DMFA-SRQ算法分配得到的占優(yōu)資源份額數(shù)和與靜態(tài)加權(quán)DRF算法結(jié)果相接近，說明 DMFA-SRQ算法在滿足式(4)線性規(guī)劃方程組中的約束條件下，能夠?qū)崿F(xiàn)動態(tài)情形下所有用戶占優(yōu)資源份額最大化分配目標(biāo)。

3) 資源利用率最大化

在云共享系統(tǒng)中，資源利用率是衡量分配策略效率的重要標(biāo)準(zhǔn)之一[14]。因此，本文測試DMFA-SRQ算法下的CPU和Memory資源利用率，并與加權(quán)DRF算法進(jìn)行比較。圖7和圖8分別給出了2種算法的CPU和Memory資源利用率結(jié)果。

從圖7和圖8中2種算法資源利用率的對比可以看出，DMFA-SRQ算法下的資源利用率值與靜態(tài)情形下的加權(quán) DRF算法結(jié)果相接近，且用戶數(shù)越多，2種算法的資源利用率越接近。實(shí)驗(yàn)結(jié)果驗(yàn)證本文所提算法的資源利用率并沒有因?yàn)閯討B(tài)情形下用戶資源需求未知以及資源共享總量的差異而有所降低，說明該策略既保證資源分配的公平性，又兼顧到分配效率。

圖7 CPU資源利用率

圖8 Memory資源利用率

7 結(jié)束語

本文針對云計(jì)算共享系統(tǒng)中虛擬化資源分配的公平性問題，基于用戶資源需求和共享資源量，提出基于共享資源量的動態(tài)多資源公平分配策略。該策略建立一個線性規(guī)劃模型來實(shí)現(xiàn)對占優(yōu)資源的盡可能公平分配，并證明該模型滿足公平分配的4個重要屬性：動態(tài)帕累托最優(yōu)、激勵共享、動態(tài)無嫉妒性、防止策略性操作，此外，本文還提出基于共享資源量的動態(tài)多資源公平分配算法來改進(jìn)算法運(yùn)行效率。而且，本文所提出的策略和算法不僅可以應(yīng)用于云共享系統(tǒng)資源的動態(tài)分配，也適用于WLAN和WSN等領(lǐng)域的網(wǎng)絡(luò)帶寬分配。最后，實(shí)驗(yàn)基于最小占優(yōu)資源份額、占優(yōu)資源份額數(shù)和、資源利用率最大化目標(biāo)與加權(quán) DRF算法進(jìn)行比較，進(jìn)一步表明本文所提DMFA-SRQ策略能夠有效地保證動態(tài)情形下多用戶多資源分配的公平性和資源利用率。但由于云計(jì)算環(huán)境的異構(gòu)性以及資源分布在多服務(wù)器等復(fù)雜情況，還可能面臨更為復(fù)雜的多資源分配問題，因此，對異構(gòu)環(huán)境下的動態(tài)多用戶多資源公平分配問題將是下一步的研究工作。

[1] Max-min fairness[EB/OL]. http：//en.wikipedia.org/wiki/Max-min_fairness.

[2] GHODSI A, ZAHARIA M, HINDMAN B, et al. Dominant resource fairness： fair allocation of multiple resource types[C]//The 8th USENIX Conference on Networked Systems Design and Implementation. c2011： 24.

[3] Hadoop[EB/OL]. http：//hadoop.apache.org/.

[4] Mesos[EB/OL]. http：//mesos.apache.org/.

[5] KASH I, PROCACCIA A D, SHAH N. No agent left behind： dynamic fair division of multiple resources[J]. Journal of Artificial Intelligence Research, 2013(1)： 351-358.

[6] JAIN R, CHARNY A, CLARK D. Congestion control with explicit rate indication[C]// 1995 IEEE International Conference on Communications.c1995： 1954-1963.

[7] GOYAL P, VIN H M, CHEN H. Start-time fair queueing： a scheduling algorithm for integrated services packet switching networks[C]//ACM Sigcomm Computer Communication Review. c1996： 157-168.

[8] STOICA I, SHENKER S, ZHANG H. Core-stateless fair queueing：achieving approximately fair bandwidth allocations in high speed networks[C]//The ACM Sigcom. c1998： 118-130.

[9] CAPRITA B, CHAN W C, NIEH J, et al. Group ratio round-robin： O(1)proportional share scheduling for uniprocessor and multiprocessor systems[C]//Usenix Technical Conference. c2005： 337-352.

[10] KELLY F. Charging and rate control for elastic traffic[J]. European Transactions on Telecommunications, 1997, 8(1)：33-37.

[11] MASSOULIE L, ROBERTS J. Bandwidth sharing： objectives and algorithms[C]//18th Joint Conference of the IEEE Computer and Communications Societies(INFOCOM '99). New York. c1999： 1395-1403.

[12] ZUKERMAN M, TAN L, WANG H, et al. Efficiency-fairness tradeoff in telecommunications networks [J]. IEEE Communications Letters,2005, 9(7)：643 - 645.

[13] LAN B T, KAO D, CHIANG M, et al. An axiomatic theory of fairness in network resource allocation[C]//IEEE Infocom. c2010： 1-9.

[14] DOLEV D, FEITELSON D G, HALPERN J Y, et al. No justified complaints： on fair sharing of multiple resources[C]//The 3rd Innovations in Theoretical Computer Science Conference. c2012： 68-75.

[15] GUTMAN A, NISAN A. Fair allocation without trade[C]//The 11th International Conference on Autonomous Agents and Multiagent Systems. c2012： 719-728.

[16] BHATTACHARYA A A, CULLER D, FRIEDMAN E, et al. Hierarchical scheduling for diverse datacenter workloads[C]//The 4th Symposium on Cloud Computing (SOCC’13). c2013：1-15.

[17] WANG W, LIANG B, LI B. Multi-resource fair allocation in heterogeneous cloud computing systems[J]. Parallel and Distributed Systems,2015, 26(10)： 2822-2835.

[18] JOE-WONG C, SEN S, LAN T, et al. Multiresource allocation： fairness-efficiency tradeoffs in a unifying framework[J]. IEEE/ACM Transactions on Networking, 2013, 21(6)： 1785-1798.

[19] PSOMAS C A, SCHWARTZ J. Beyond beyond dominant resource fairness： Indivisible resource allocation in clusters[R]. Technology Report, Berkeley, 2013.

[20] PARKES D C, PROCACCIA A D, SHAH N. Beyond dominant resource fairness： extensions, limitations, and indivisibilities[J]. ACM Transactions on Economics and Computation, 2015, 3(1).

[21] ZELDES Y, G.FEITELSON D. On-line fair allocations based on bottlenecks and global priorities[C]//The 4th ACM/SPEC International Conference on Performance Engineering. c2013： 229-240.

[22] LI W D, LIU X, ZHANG X L, et al. Multi-resource fair allocation with bounded number of tasks in cloud computing systems[J]. Eprint Arxiv, 2014.

[23] LI W, LIU X, ZHANG X, et al. Dynamic fair allocation of multiple resources with bounded number of tasks in cloud computing systems[J]. Multiagent and Grid Systems, 2016, 11(4)： 245-257.

[24] BARBANEL J B, BRAMS S J. Two-person cake-cutting： the optimal number of cuts[J]. Mathematical Inteuigencer, 2011, 36(3)： 23-35.

[25] LI J, XUE J. Egalitarian division under leontief preferences [J]. Economic Theory, 2013, 54(3)： 597-622.

[26] WILES J, REISS C. Google cluster data 2011_2[EB/OL]. https：//code.google.com/p/googleclusterdata/.

Dynamic fair allocation of multi-resources based on shared resource quantity

ZHANG Xiao-lu, LIU Xi, LI Wei-dong, ZHANG Xue-jie
(School of Information Science and Engineering, Yunnan University, Kunming 650091, China)

A dynamic fair allocation of multi-resources was proposed based on shared resource quantity for multi-resoures allocation problem in cloud shared computing system. Firstly, a linear programming model was given based on resource requirements and quantity of shared resource and this model was further proved which satisfies four fairness properties such as DPO, SI, DEF and SP. Secondly, an improved dynamic multi-resources fair allocation algorithm was introduced for the allocation efficiency. Finally, theoretical analysis and experiments demonstrate that this strategy can satisfy the demands as well as maximize the dominant share on the base of approaching fairness and the improved algorithm increases the allocation efficiency in the dynamic system.

cloud computing, multi-resources fairness allocation, dominant share, shared resource quantity

s: The National Natural Science Foundation of China (No.61170222, No.11301466), Scientific Research Foundation of Yunnan Provincial Department of Education (No.2015J007), Natural Science Foundation of Yunnan Province (No.2013FB010)

TP301

A

10.11959/j.issn.1000-436x.2016144

2015-11-19；

2016-04-20

國家自然科學(xué)基金資助項(xiàng)目（No.61170222, No.11301466）；云南省教育廳科學(xué)研究基金資助項(xiàng)目（No.2015J007）；云南省科技廳應(yīng)用基礎(chǔ)研究面上基金資助項(xiàng)目（No.2013FB010）

張瀟璐（1983-），女，山東淄博人，云南大學(xué)博士生，主要研究方向?yàn)橘Y源分配調(diào)度、云計(jì)算能耗、大數(shù)據(jù)處理。

劉曦（1987-），男，云南昆明人，云南大學(xué)博士生，主要研究方向?yàn)橹悄芩惴ā①Y源分配調(diào)度、大數(shù)據(jù)處理。

李偉東（1981-），男，河南鄭州人，博士，云南大學(xué)副教授，主要研究方向?yàn)榻M合優(yōu)化算法、復(fù)雜性分析、分布式計(jì)算。

張學(xué)杰（1965-），男，云南昆明人，云南大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)楦咝阅苡?jì)算、云計(jì)算、大數(shù)據(jù)、分布式計(jì)算。