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

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

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

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

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

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

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

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

1 引言

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

h

2) 激勵(lì)共享

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

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

3) 動(dòng)態(tài)無(wú)嫉妒性

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

4) 防止策略性操作

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

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

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

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

i i

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

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

h則有根據(jù)h

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

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

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

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

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

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

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

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

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

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

證明 考慮以下2種情況。

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

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

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

5 DMFA-SRQ算法

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

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

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

3) 根據(jù)式(4)線性規(guī)劃方程組中前2個(gè)約束條件以及引理 1，當(dāng)系統(tǒng)中有k個(gè)用戶(hù)時(shí)，每個(gè)用戶(hù)i被分配執(zhí)行的任務(wù)數(shù)為，即從而最終得到用戶(hù)i在資源 j上的分配方案。DMFA-SRQ算法的操作過(guò)程如算法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個(gè)用戶(hù)時(shí)，本文提出的DMFA-SRQ 算法利用二分法思想確定vτ，并得到和最終分配方案(,… ,xk)，算法的運(yùn)行時(shí)間取k決于求解vτ值的迭代次數(shù)，因此，該算法的時(shí)間復(fù)雜度為Ο ( klogk)。當(dāng)系統(tǒng)中共有n個(gè)用戶(hù)時(shí)，整體算法運(yùn)行時(shí)間為

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

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

圖2 用戶(hù)資源需求分布

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

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

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

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

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

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

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

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

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

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

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

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

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

3) 資源利用率最大化

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

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

圖7 CPU資源利用率

圖8 Memory資源利用率

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

本文針對(duì)云計(jì)算共享系統(tǒng)中虛擬化資源分配的公平性問(wèn)題，基于用戶(hù)資源需求和共享資源量，提出基于共享資源量的動(dòng)態(tài)多資源公平分配策略。該策略建立一個(gè)線性規(guī)劃模型來(lái)實(shí)現(xiàn)對(duì)占優(yōu)資源的盡可能公平分配，并證明該模型滿(mǎn)足公平分配的4個(gè)重要屬性：動(dòng)態(tài)帕累托最優(yōu)、激勵(lì)共享、動(dòng)態(tài)無(wú)嫉妒性、防止策略性操作，此外，本文還提出基于共享資源量的動(dòng)態(tài)多資源公平分配算法來(lái)改進(jìn)算法運(yùn)行效率。而且，本文所提出的策略和算法不僅可以應(yīng)用于云共享系統(tǒng)資源的動(dò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策略能夠有效地保證動(dòng)態(tài)情形下多用戶(hù)多資源分配的公平性和資源利用率。但由于云計(jì)算環(huán)境的異構(gòu)性以及資源分布在多服務(wù)器等復(fù)雜情況，還可能面臨更為復(fù)雜的多資源分配問(wèn)題，因此，對(duì)異構(gòu)環(huán)境下的動(dòng)態(tài)多用戶(hù)多資源公平分配問(wèn)題將是下一步的研究工作。

[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

國(guó)家自然科學(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ì)算。