嵌入式終端資源分配算法研究(論文)最終版資料

1、PAGE 南通大學(xué)畢業(yè)設(shè)計(jì)（論文）PAGE II本科畢業(yè)設(shè)計(jì)（論文）題目嵌入式終端資源分配算法的研究學(xué)生姓名： 專 業(yè)： 指導(dǎo)教師： 完成日期： 誠 信 承 諾 書本人承諾：所呈交的論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究成果。除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已發(fā)表或撰寫過的研究成果。參與同一工作的其他同志對(duì)本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意。 簽 名： 日 期： 本論文使用授權(quán)說明本人完全了解南通大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留論文及送交論文復(fù)印件，允許論文被查閱和借閱；學(xué)?？梢怨颊撐牡娜炕虿糠謨?nèi)容。（保密的論文在解密后應(yīng)遵守此規(guī)定

2、）學(xué)生簽名： 指導(dǎo)教師簽名： 日期： 南通大學(xué)畢業(yè)設(shè)計(jì)（論文）PAGE I摘 要資源分配在各個(gè)領(lǐng)域中都有廣泛的應(yīng)用。在嵌入式系統(tǒng)中資源分配的主要任務(wù)是將有限的資源合理地分配給用戶，其目的是通過這樣的分配來提高系統(tǒng)的性能和用戶的服務(wù)體驗(yàn)。在基于公平的資源分配算法上，介紹了資源分配的研究背景和現(xiàn)狀，論述了資源分配的公平準(zhǔn)則和公平概念，包括一些具體的方法。除了適用于單資源的最大最小公平，比例公平和效用公平外，重點(diǎn)介紹了適用于多資源的DRF算法在資源分配中的應(yīng)用。另外也將DRF與其它多資源的公平分配算法進(jìn)行了比較，顯示DRF分配使得用戶的支配資源分配趨于均衡，并且DRF也擁有許多的獨(dú)有屬性，這些屬性可

3、以讓用戶更加公平地得到資源分配。因此DRF能夠使得系統(tǒng)的整體性能更加優(yōu)異。關(guān)鍵詞：資源分配，公平性，多資源，DRF南通大學(xué)畢業(yè)設(shè)計(jì)（論文）南通大學(xué)畢業(yè)設(shè)計(jì)（論文）ABSTRACTThe allocation of resources are widely used in all fields. Its main task is to allocate the limited resourcesto users reasonably in an embedded system. Its purpose is to through such allocation to improve the pe

4、rformance of the system and user service experience.Based on the fairness, the paper introduces the research background and the present situation of resource allocation,and discusses the fairness criteria and notions of fairness, including some specific methods. Other than max-min fairness, proporti

5、onal fairness and utility max-min fairness that apply to a single resource, the paper focused on introducing the dominant resource fairness which applies to multiple resources. The DRF also will be compared with other fair algorithm that apply to multiple resources. According to the conclusion ,the

6、DRF leads the dominant resource that the users receive to tends to equilibrium, and DRF also has many unique properties, these properties allows users receive resource more equitable. Therefore DRF can lead the performance of the whole system more excellent.Keywords: The allocation of resources, Fai

7、rness, Multiple resources, DRFPAGE III目 錄 TOC o 1-3 h z u HYPERLINK l _Toc14690 摘 要 PAGEREF _Toc14690 I HYPERLINK l _Toc29465 ABSTRACT PAGEREF _Toc29465 II HYPERLINK l _Toc7763 目 錄 PAGEREF _Toc7763 III HYPERLINK l _Toc25719 第一章 緒 論 PAGEREF _Toc25719 1 HYPERLINK l _Toc1990 1.1本課題研究的背景 PAGEREF _Toc199

8、0 1 HYPERLINK l _Toc5399 1.2研究領(lǐng)域現(xiàn)狀 PAGEREF _Toc5399 1 HYPERLINK l _Toc15898 1.3所做的主要工作 PAGEREF _Toc15898 2 HYPERLINK l _Toc27677 第二章 公平準(zhǔn)則和公平概念 PAGEREF _Toc27677 3 HYPERLINK l _Toc21276 2.1最大最小公平性 PAGEREF _Toc21276 3 HYPERLINK l _Toc18039 2.2效用最大最小公平性 PAGEREF _Toc18039 4 HYPERLINK l _Toc16656 2.3比例公平

9、性 PAGEREF _Toc16656 5 HYPERLINK l _Toc10810 2.4公平的一般概念 PAGEREF _Toc10810 6 HYPERLINK l _Toc7947 第三章 支配資源的公平性（DRF） PAGEREF _Toc7947 8 HYPERLINK l _Toc15895 3.1引言 PAGEREF _Toc15895 8 HYPERLINK l _Toc32043 3.2動(dòng)機(jī) PAGEREF _Toc32043 9 HYPERLINK l _Toc27959 3.3分配特性 PAGEREF _Toc27959 10 HYPERLINK l _Toc2032

10、9 3.4 DRF PAGEREF _Toc20329 11 HYPERLINK l _Toc9027 3.4.1 舉例 PAGEREF _Toc9027 11 HYPERLINK l _Toc17430 3.4.2 DRF調(diào)度算法 PAGEREF _Toc17430 13 HYPERLINK l _Toc10597 3.4.3 加權(quán)DRF PAGEREF _Toc10597 14 HYPERLINK l _Toc2896 3.5公平分配策略的替代 PAGEREF _Toc2896 15 HYPERLINK l _Toc13436 3.5.1 資產(chǎn)公平 PAGEREF _Toc13436 15

11、 HYPERLINK l _Toc32482 3.5.2 CEEI PAGEREF _Toc32482 16 HYPERLINK l _Toc30179 3.5.3 與DRF比較 PAGEREF _Toc30179 17 HYPERLINK l _Toc22132 第四章 總結(jié)與展望 PAGEREF _Toc22132 18 HYPERLINK l _Toc19319 ADDIN NE.Bib參考文獻(xiàn) PAGEREF _Toc19319 19 HYPERLINK l _Toc12793 致 謝 PAGEREF _Toc12793 21PAGE 1第一章 緒 論1.1本課題研究的背景隨著21世紀(jì)

12、互聯(lián)網(wǎng)的快速發(fā)展，計(jì)算機(jī)和互聯(lián)網(wǎng)已經(jīng)已經(jīng)成為人們生活中必不可少的元素了。網(wǎng)絡(luò)上存放著各式各樣的資源，人們可以通過網(wǎng)絡(luò)來觀看電視，查看新聞，閱讀書籍。盡管網(wǎng)絡(luò)存儲(chǔ)和網(wǎng)絡(luò)帶寬在不斷增加，資源的增加速度也越來越快除了一些可復(fù)制或重用的資源可以滿足人們的需求，仍然有一些總量有限的資源始終達(dá)不到人們的需求，例如網(wǎng)絡(luò)帶寬、網(wǎng)絡(luò)服務(wù)等。因此許多研究者針對(duì)如何分配稀缺資源是的資源分配系統(tǒng)獲得高效益而提出了最初的資源分配算法研究。硬件技術(shù)的發(fā)展，智能終端已經(jīng)成為生活中的必需品，它能夠同時(shí)處理多個(gè)任務(wù)，給用戶更好的服務(wù)體驗(yàn)。但是智能終端仍然存在資源不足的情況，例如智能電視，這時(shí)一些研究者根據(jù)網(wǎng)絡(luò)的資源分配算法提出

13、了嵌入式終端的資源分配算法。對(duì)于智能電視而言，它作為嵌入式終端，它的資源十分有限，例如Sigma Designs 8655平臺(tái)的基本配置為：CPU主頻500M、內(nèi)存大小256M。然而智能電視需要支持多任務(wù)并行，這樣必然會(huì)引起資源過載，多任務(wù)之間競(jìng)爭(zhēng)資源的狀況，從而影響任務(wù)的運(yùn)行和用戶的體驗(yàn)。另外，對(duì)于彈性應(yīng)用，可以根據(jù)資源分配的數(shù)量，調(diào)整任務(wù)的執(zhí)行，獲得不同的服務(wù)質(zhì)量，例如可伸縮視頻解碼任務(wù)是典型的彈性應(yīng)用，可以根據(jù)資源分配，解碼基本層和不同的增強(qiáng)層，獲得不同的信噪比、分辨率及幀率。因此，在智能電視中，需要對(duì)有限的資源進(jìn)行合理的分配，使得系統(tǒng)總的服務(wù)質(zhì)量達(dá)到最優(yōu)。但是，系統(tǒng)總的服務(wù)質(zhì)量并不是資

14、源分配的唯一目標(biāo)，在資源分配過程中，還需要考慮資源分配的公平性，尤其當(dāng)智能電視系統(tǒng)面臨多用戶場(chǎng)景時(shí)。因此，研究基于公平性的資源分配問題也具有重要意義。 1.2研究領(lǐng)域現(xiàn)狀在嵌入式終端的資源分配方面，對(duì)于傳統(tǒng)的基于效用的資源分配算法許多的研究者已經(jīng)提出了相關(guān)的理論，例如Rajkumar等人提出了一種基于QoS保障的資源分配模型Q-RAM，旨在滿足應(yīng)用最小需求的條件下最大化整體系統(tǒng)效用，并給出了單資源、多QoS維度情況下的資源分配算法。隨后，Rajkumar又在該模型的基礎(chǔ)上，研究了多資源、單QoS屬性約束條件下資源分配問題。Lee等人提出了基于離散QoS指標(biāo)的資源分配模型，并分別研究了單資源、多

15、QoS約束和多資源、多QoS約束條件下的資源分配問題，給出了基于動(dòng)態(tài)規(guī)劃的最優(yōu)解算法和基于本地搜索的近似算法。Khan在研究多會(huì)話多媒體系統(tǒng)質(zhì)量自適應(yīng)問題時(shí)，首次提出多維多選擇背包問題（MMKP），以系統(tǒng)效用最大作為優(yōu)化目標(biāo)，并給出基于分支限界法的BBLP算法，以求得問題的最優(yōu)解。對(duì)于資源分配我們不能僅僅考慮效用最大化，還需要考慮公平性的問題。僅僅最大化效用而有失公平同樣會(huì)影響 用戶的體驗(yàn)。針對(duì)這個(gè)問題研究者們又提出了基于公平的資源分配算法理論，例如基于自控理論的公平共享控制，Harada等人提出通過控制理論求解公平的資源分配?；诤献鞑┺恼摰墓焦蚕砜刂?，Mastronarde等人提出利用公

16、理性議價(jià)理論中卡萊-斯莫羅廷斯基議價(jià)解確定公平的資源分配（簡(jiǎn)稱RA_KSBS算法）?；趶椥阅Ｐ偷墓焦蚕砜刂?，Buttazzo等人提出了彈性任務(wù)模型，任務(wù)的資源利用率被看作線性彈簧，具有彈性系數(shù)，并且隨著彈性系數(shù)動(dòng)態(tài)變化，以避免過載條件。1.3所做的主要工作對(duì)于嵌入式資源的分配我們要考慮很多比如單資源、多資源、基于效用還是基于公平，這些都是研究算法所必須要關(guān)注的問題。本文研究的主要是基于公平的多資源分配算法，另外還會(huì)介紹一些基于公平的單資源分配算法。全文共分為四章，各章節(jié)的主要內(nèi)容安排如下：第一章為緒論，簡(jiǎn)要介紹了嵌入式終端資源分配算法的研究背景、意義和目前國內(nèi)外研究現(xiàn)狀。第二章定義了公平準(zhǔn)

17、則和公平概念，主要介紹了一些對(duì)于單資源的公平性分配算法，其中包括了最大最小公平性，效用最大最小公平性，比例公平性。第三章對(duì)多資源公平性分配算法進(jìn)行介紹，提出了支配資源公平性算法。其中包括理論知識(shí)、算法實(shí)現(xiàn)。另外還與其它的類似算法進(jìn)行了對(duì)比。第四章是總結(jié)與展望，對(duì)本文的研究?jī)?nèi)容和創(chuàng)新點(diǎn)進(jìn)行總結(jié)，并對(duì)未來的研究方向進(jìn)行展望。PAGE 19PAGE 20第二章 公平準(zhǔn)則和公平概念在嘗試設(shè)計(jì)一個(gè)公平的資源分配策略時(shí)，必須首先定義一個(gè)公平概念，即確定一個(gè)可以通過分配策略來判斷公平的標(biāo)準(zhǔn)。如果多個(gè)任務(wù)爭(zhēng)奪一個(gè)共享資源，為了解決什么是公平，一些文獻(xiàn)提出了許多的公平準(zhǔn)則。其中最常見的是最大最小公平性，比例公平

18、性和效用最大最小公平性，如下所訴。2.1最大最小公平性對(duì)于一種共享資源，用最大最小公平性策略來分配，那么多個(gè)用戶之間擁有相等的分配權(quán)但是有不同的需求，它必須遵守以下的原則 ADDIN NE.Ref.D7BA4176-5496-4CBF-B8B8-145766A92E9D1, 2：共享的資源按需求的增長(zhǎng)次序來分配用戶不會(huì)得到比他需求更多的資源分配所有沒有達(dá)到資源需求的用戶將會(huì)得到相等的資源分配最大最小公平性也可以等效的定義為：沒有用戶可以增加他的資源分配卻不減少其他有更少或相等的資源需求的用戶的資源分配。在最大最小公平性下不會(huì)給予額外的資源，即對(duì)于不滿足資源需求的用戶僅僅增大資源需求不會(huì)增加資源

19、分配。在實(shí)際的資源分配過程中，由于用戶具有不同的權(quán)重，所以資源要基于相對(duì)應(yīng)的權(quán)重來分配?？紤]有N個(gè)用戶，用戶的資源需求為，相對(duì)應(yīng)的權(quán)重為。給定R為分配給N的用戶的總資源量，滿足最大最小公平性的資源分配是唯一的。為了方便起見，在整篇論文中我們用表示用戶的資源需求矢量，表示權(quán)重矢量。那么滿足最大最小公平性的資源分配可以表示為(2.1)其中， 表示用戶i的最大最小公平資源分配，的偽代碼如下所示，的輸入為用戶的資源需求矢量、權(quán)重矢量以及資源的容量R，輸出為資源分配矢量。for each end for;while ()Find source with minimum in ;if () thenRem

20、ove source from ;elsefor each if ( ) thenend if;end for;end if;end while;return ;2.2效用最大最小公平性效用最大最小公平的概念類似于最大最小公平，在效用最大最小公平下每個(gè)用戶都關(guān)聯(lián)一個(gè)效用函數(shù) ADDIN NE.Ref.0A07622A-8821-41DD-A7C4-E10CCAB497453，該效用函數(shù)通過每個(gè)得到公平分配的用戶來完成。效用函數(shù)表明一個(gè)用戶得到一定數(shù)量的資源分配后的滿意度，不同的用戶可以有不同的效用函數(shù) ADDIN NE.Ref.760D7464-0760-4422-B285-57CD9FC7F

21、98A4。以下是一些常見的例子：彈性流如電子郵件、Telnet、FTP應(yīng)用程序可能有一個(gè)凸效用。換句話說，只要分配相對(duì)較少的資源效用函數(shù)就會(huì)快速的增長(zhǎng)，而且當(dāng)它達(dá)到某一點(diǎn)是就會(huì)飽和。圖2.1(a)展示了這種類型的效用函數(shù)。實(shí)時(shí)流如視頻和音頻流有一個(gè)最低要求的分配資源。只有當(dāng)滿足這種最低要求時(shí)這種類型的流的效用函數(shù)才會(huì)變大。另一方面，過度的增大資源分配不會(huì)顯著的使效用函數(shù)增大。總之，實(shí)時(shí)流的效用函數(shù)通常有一個(gè)閾值點(diǎn)對(duì)應(yīng)最低要求，如圖2.1(b)所示。自適應(yīng)速率也有跟實(shí)時(shí)流類似的效用函數(shù)，除了效用分化在最低需求點(diǎn)要求更光滑。換句話說，自適應(yīng)速率流的效用函數(shù)有一個(gè)曲線拐點(diǎn)，如圖2.1(c)所示。 圖

22、2.1注意,對(duì)于一組用戶i，考慮到資源的總量為R，需求向量為,權(quán)重向量為還有每個(gè)用戶的效用函數(shù)，分配向量由效用最大最小公平性表示為： (2.2) 這里每個(gè)用戶的效用函數(shù)都包含在 函數(shù)中。最大最小公平性可以看作是一種特殊情況下的效用最大最小公平性，所有的用戶都有相同的線性效用函數(shù)。2.3比例公平性一些研究者指出最大最小公平性給予資源需求少的用戶更多的優(yōu)先權(quán) ADDIN NE.Ref.18CC6A08-5F97-4A61-AAE1-9B7F35E035C85。而比例公平性的定義強(qiáng)調(diào)資源需求少的用戶的優(yōu)先權(quán)更低。比例公平性定義為：假設(shè)用戶的資源分配為，相應(yīng)的效用函數(shù)為資源分配的對(duì)數(shù)函數(shù)，資源分配的目

23、標(biāo)是最大化所有用戶總的效用。資源分配矢量滿足比例公平性準(zhǔn)則，當(dāng)且僅當(dāng)對(duì)于其它任意可行的資源分配矢量，總的比例變化是非正值，也就是說 (2.3) 這里我們指的是一個(gè)可行的分配，當(dāng)且僅當(dāng)，共享資源總量不超出分配所需要的資源。這公平準(zhǔn)則意味著對(duì)數(shù)效用函數(shù)。類似于最大最小公平和效用最大最小公平的情況，比例公平也決定如何分配共享資源，考慮到資源總量為R，需求向量為和權(quán)重向量為。換句話說,比例公平也可以表示如下： (2.4)2.4公平的一般概念注意，上述提到的公平標(biāo)準(zhǔn)決定了怎樣去根據(jù)有競(jìng)爭(zhēng)關(guān)系的用戶的需求來分配單個(gè)共享資源。因此，為了方便，我們引入了一個(gè)符號(hào)，它可以表示其中的任何一個(gè)公平概念?？紤]有N個(gè)用

24、戶，爭(zhēng)奪一個(gè)共享資源，總量為R。用戶 的權(quán)重為，表明用戶的相對(duì)合法共享的資源。對(duì)于一個(gè)在差異化服務(wù)框架 ADDIN NE.Ref.4226CEB2-FDF2-44D9-AC5B-8CFB667C56E06下的用戶，他的權(quán)重決定于在64種可能的類型中他自己的用戶類型。對(duì)于一個(gè)在最優(yōu)網(wǎng)絡(luò)中的用戶，他的權(quán)重通常與其他所有的用戶一樣。用戶的需求為。所以考慮到需求向量為，權(quán)重向量為，總的可用資源為R，任何的公平概念可以表示如下： (2.5)其中是用戶i的資源分配，它是由定義公平的函數(shù)F決定的，不同的公平準(zhǔn)則有不同的F函數(shù)。你可能注意到在（2.2）式中效用函數(shù)并沒有表示出來。然而，（2.2）式表示出一個(gè)可

25、以描述怎樣分配的通用符號(hào)，只要有確定的需求向量，就可以決定每個(gè)用戶的資源分配，以便于分配所對(duì)應(yīng)的效用滿足于公平定義對(duì)應(yīng)的效用。換句話說，式（2.2）把效用函數(shù)融入到了公平概念中。例如，最大最小公平意味著線性效用函數(shù)，比例公平使用對(duì)數(shù)效用函數(shù),在效用最大最小公平，每個(gè)用戶決定自己的效用函數(shù)。唯一的約束條件是相對(duì)于分配資源的數(shù)量效用函數(shù)是非遞減函數(shù)。使用歸一化的需求和分配可以等效的表示任何公平概念。定義用戶i歸一化的需求為，如下所示：用戶i歸一化的需求表明了用戶的需求占總資源的百分比。定義用戶i歸一化的資源分配為，如下所示：用戶i歸一化的分配表明了用戶的分配占總資源的百分比。所以，給定歸一化的需求

26、向量，權(quán)重向量，任何給出的公平概念都可以用下面的式子表示， (2.6) 其中C是影響整個(gè)系統(tǒng)的約束條件，后面詳細(xì)介紹。注意式（2.6）中對(duì)于任何變量都沒有維度影響，因此，使它適用于有多個(gè)異構(gòu)資源的系統(tǒng)。約束C作為函數(shù)F的參數(shù)，因?yàn)榭紤]到相同的需求和權(quán)向量，在系統(tǒng)中不同的約束會(huì)使公平分配不相同。約束C可以用來表示分配所達(dá)到的性能水平。例如，遵照最大最小公平原則，即使沒有資源分配給用戶也可以認(rèn)為這是一個(gè)公平分配，盡管它會(huì)導(dǎo)致極差的性能。作為一個(gè)簡(jiǎn)單的例子，約束C可以表示所有用戶的效用總和。注意，在式（2.5）中資源總量也可以認(rèn)為是在分配策略中的一個(gè)簡(jiǎn)單的約束：分配資源的總量不能超過資源R，也就是。

27、所以，式（2.5）僅僅是式（2.6）的一種特殊情況。根據(jù)上下文，我們可以使用這兩個(gè)中的任何一個(gè)的公平概念。例如，在本論文，當(dāng)歸一化沒有必要時(shí)使用式(2.5)，就像考慮緩沖資源一樣，而當(dāng)歸一化是必要時(shí)用式(2.6)，比如在考慮處理資源時(shí)。本章的內(nèi)容主要介紹了一些對(duì)于單資源的公平分配策略，但是在實(shí)際當(dāng)中，終端器件往往都是含有多種資源的，這就需要我們尋找一種新的資源分配策略，下面我們就來介紹一下多資源分配策略。第三章 支配資源的公平性（DRF）3.1引言在所有共享的計(jì)算機(jī)系統(tǒng)中，都有一個(gè)重要的的構(gòu)建模塊，那就是資源的合理分配。迄今為止在已經(jīng)研究出的分配策略中最受歡迎的是最大最小公平性，在系統(tǒng)中它會(huì)最

28、大化用戶得到的最小分配。假如每一個(gè)用戶都有足夠的資源需求，這種策略會(huì)分配給每個(gè)用戶一份相等的共享資源。另外，現(xiàn)實(shí)中由于用戶之間的重要性不同，又進(jìn)一步的提出了加權(quán)的最大最小公平性，這種方法使得用戶獲得的資源與他的權(quán)重成正比。加權(quán)的最大最小公平性的魅力在于它的普遍性和它能夠提供性能隔離的能力。加權(quán)的最大最小公平性模型可以適用于各種各樣的資源分配策略，包括基于優(yōu)先級(jí)的分配，基于預(yù)留的分配，和基于截止期限的分配 ADDIN NE.Ref.B992876D-876B-40EC-A5DA-18C1C315A4807等。另外，加權(quán)的最大最小公平性能夠確保隔離，換句話說，就是能夠保證一個(gè)用戶收到他的那份資源，

29、而不用考慮其他用戶的需求。鑒于這些特征，提出了許多算法以實(shí)現(xiàn)不同精確度的（加權(quán)的）最大最小公平性，例如輪叫、比例資源共享 ADDIN NE.Ref.AF43CF05-B2EA-4D91-B593-7A4B649889DF8和加權(quán)公平隊(duì)列 ADDIN NE.Ref.0EF586F4-4B17-449A-83CF-EA59EA41B1399。這些算法已經(jīng)被應(yīng)用于各種不同的資源，例如鏈路帶寬 ADDIN NE.Ref.735CE369-62A2-4FB2-B083-B0749E2904019-14、CPU ADDIN NE.Ref.2E259432-F994-45D6-8684-3ABED7BE0E

30、857, 15, 16、內(nèi)存和存儲(chǔ)。目前在公平分配上已經(jīng)做了大量地工作和實(shí)踐，但是到現(xiàn)在為止主要還是集中在單資源類型的環(huán)境下。甚至在多資源類型的環(huán)境下，用戶具有異構(gòu)的資源需求，典型的資源分配的做法還是使用單類型資源抽象。比如Hadoop和Dryad ADDIN NE.Ref.2249C974-290D-4D8D-B1B4-56DD212ED43917, 18，這兩種廣泛使用的集群計(jì)算框架，它們的公平調(diào)度器在資源分配時(shí)使用插槽，所謂的插槽就是對(duì)節(jié)點(diǎn)資源按照固定大小進(jìn)行劃分而產(chǎn)生的分區(qū)。然而實(shí)際上是集群中不同的任務(wù)對(duì)CPU、內(nèi)存和IO資源有著不同的需求。這篇文章里，在多種類型的資源環(huán)境下我們?yōu)橛挟?/p>

31、構(gòu)需求的用戶解決公平分配問題。尤其，我們提出支配資源的公平性（DRF），針對(duì)多資源推廣最大最小公平性。DRF背后的直觀理解是在多資源的環(huán)境下一個(gè)用戶的分配應(yīng)該由用戶的支配份額決定，支配份額是指在已經(jīng)分配給用戶的所有資源中，占據(jù)最大份額的一種資源。簡(jiǎn)單的說，DRF力圖最大化所有用戶的最小的支配份額。舉個(gè)例子，假設(shè)A用戶運(yùn)行CPU密集的任務(wù)，B用戶運(yùn)行內(nèi)存密集的任務(wù)，DRF試圖去均衡用戶A的CPU分配和用戶B的內(nèi)存分配。在單資源的情況下，DRF退化為最大最小公平性。DRF的優(yōu)點(diǎn)在于它所滿足的特性。在單資源場(chǎng)景下，這些特性由最大最小公平性平凡地滿足，但是，在多資源場(chǎng)景下，這些特性都是不尋常的。四個(gè)這

32、種類型的特性分別是激勵(lì)共享、防止策略性操縱、帕累托最優(yōu)和無嫉妒性。DRF為用戶提供激勵(lì)機(jī)制去分配資源，通過保證用戶在系統(tǒng)中不會(huì)有多余的資源來達(dá)到這一目的。此外，DRF是防止策略性操縱的，因?yàn)橛脩舨豢赡芡ㄟ^謊報(bào)他的資源需求來獲得更多的資源分配。DRF是帕累托最優(yōu)的，因?yàn)樵跐M足其它特性的同時(shí)分配所有可用的資源，而不會(huì)取代現(xiàn)存的資源分配。最后，DRF是無嫉妒的，沒有用戶更喜歡其他用戶的資源分配。3.2動(dòng)機(jī)雖然早先關(guān)于加權(quán)最大最小公平性的工作都集中在單一資源的情況，但是云計(jì)算和多核處理器的出現(xiàn)提高了對(duì)多資源和異構(gòu)用戶請(qǐng)求的環(huán)境下分配策略的需求。多資源意味著不同種類型的資源，而不是同一種可互換資源的多個(gè)

33、實(shí)例。目前已有的集群公平調(diào)度器，例如Quincy ADDIN NE.Ref.DEFD1216-71B1-4809-BBE3-E5A1C91C3FF017和Hadoop公平調(diào)度器 ADDIN NE.Ref.4730EF63-57BD-4306-A2A5-0BF538C6E3AD18, 19都忽視了異構(gòu)的用戶需求和以插槽為粒度的資源分配，其中一個(gè)插槽就是一個(gè)節(jié)點(diǎn)上固定比例的資源。這就導(dǎo)致了分配的效率很低，因?yàn)橐粋€(gè)插槽對(duì)與任務(wù)的需求多半是一個(gè)不好的匹配。圖3.1任務(wù)的需求與單位插槽的資源之比的概率分布圖3.1量化了Hadoop MapReduce 公平調(diào)度器所提供的的公平性和隔離性的水平。該圖顯示了

34、任務(wù)的CPU需求和插槽的CPU 份額之間的比率的概率分布圖以及任務(wù)的內(nèi)存需求和插槽的內(nèi)存份額之間的比率的概率分布圖。我們計(jì)算插槽內(nèi)存和CPU的分配通過把總的內(nèi)存和CPU除以插槽的數(shù)量。比值為1相當(dāng)于任務(wù)的需求和插槽的資源完美的匹配，比值小于1相當(dāng)于任務(wù)沒有充分地利用插槽資源，比值大于1相當(dāng)于任務(wù)已經(jīng)過度的使用了他們插槽的資源，這會(huì)導(dǎo)致系統(tǒng)起伏不定。圖3.1表明絕大部分任務(wù)或者沒有充分利用插槽資源或者過載地利用插槽資源。修改每臺(tái)機(jī)器的插槽數(shù)量并不能解決這個(gè)問題，因?yàn)檫@樣可能會(huì)導(dǎo)致更低的總利用率或者更多的任務(wù)因?yàn)檫^載而導(dǎo)致的性能不佳。3.3分配特性現(xiàn)在我們將注意轉(zhuǎn)向?yàn)槎噘Y源和異構(gòu)請(qǐng)求的情況設(shè)計(jì)一個(gè)

35、最大最小公平的分配策略。為了說明這個(gè)問題，我們假設(shè)一個(gè)系統(tǒng)，包括9個(gè)CPU和18GB的RAM，以及兩個(gè)用戶：用戶A的每個(gè)運(yùn)行任務(wù)需要，用戶B的每個(gè)運(yùn)行任務(wù)需要。如何為這種情況建立一個(gè)公平的分配策略？一種可能是把每種資源的一半分給每個(gè)用戶。另一種可能就是均衡每個(gè)用戶總的資源分配。雖然想出各種各樣可能的公平分配很簡(jiǎn)單，但是仍然不清楚怎樣去評(píng)價(jià)和比較這些分配方案。為了應(yīng)對(duì)這一挑戰(zhàn)，我們先從一系列合理的特性開始，我們相信任何多資源的和異構(gòu)需求的資源分配都應(yīng)該滿足這些特性。然后，用這些屬性引導(dǎo)公平分配策略的制定。我們發(fā)現(xiàn)以下四個(gè)屬性是重要的。1、激勵(lì)共享：相比專享自己的集群分區(qū)，通過共享集群每一個(gè)用戶都

36、應(yīng)該更好?？紤]一個(gè)集群具有相同的節(jié)點(diǎn)和n個(gè)用戶，一個(gè)用戶不能在包含1/n資源的集群分區(qū)中分配更多的任務(wù)。2、防止策略性操縱：用戶不應(yīng)該能通過謊報(bào)資源需求得到益處。用戶不能通過欺騙來提高它的分配。3、無嫉妒性：一個(gè)用戶不應(yīng)該更喜歡另一個(gè)用戶的分配。這個(gè)特性包含了公平的概念 ADDIN NE.Ref.1AA5652C-51FC-4F67-8A31-1771FC2F776220。4、帕累托最優(yōu)：不可能在增加一個(gè)用戶的分配的同時(shí)而不降低至少另一個(gè)用戶的分配。這個(gè)特性非常重要，因?yàn)樗鼤?huì)使得在滿足其它特性的同時(shí)最大化系統(tǒng)的利用率。我們簡(jiǎn)單地評(píng)價(jià)一下防止策略性操縱和共享激勵(lì)特性，我們相信這兩個(gè)特性在數(shù)據(jù)中心

37、環(huán)境下特別重要。例如，yahoo的一個(gè)Hadoop MapReduce集群對(duì)map和reduce任務(wù)有不同的插槽。一個(gè)用戶發(fā)現(xiàn)Map插槽存在競(jìng)爭(zhēng)，因此就將他的所有任務(wù)都長(zhǎng)期地運(yùn)行在Reduce階段，手工地執(zhí)行本來應(yīng)該在Map階段執(zhí)行地工作。另一個(gè)大型搜索公司為用戶高利用率的作業(yè)提供了專門的機(jī)器，這個(gè)公司馬上就發(fā)現(xiàn)用戶在他們的代碼中散布無限循環(huán)用于人為地提升利用率級(jí)別。此外，任何滿足激勵(lì)共享特性的策略同樣也提供性能隔離，因?yàn)樗ＷC每個(gè)用戶的最小分配，（也就是說，一個(gè)用戶不可能會(huì)比擁有1/n集群資源更差），不管其他用戶的需求。在單資源的情況下，最大最小公平性滿足所有上述特性。然而，在多資源和異構(gòu)用

38、戶需求的情況下，獲得這些特性是不簡(jiǎn)單的。例如，在微觀經(jīng)濟(jì)學(xué)理論中首選的公平分配機(jī)制 Competitive Equilibrium from Equal Incomes ADDIN NE.Ref.3E8F1351-A663-458C-B960-7328F98CF09420-22不是防止策略性操縱的。除了以上特性，我們還考慮了另外四種不錯(cuò)的特性：1、Single resource fairness：對(duì)于單個(gè)資源，解決方案退化為最大最小公平性。2、Bottleneck fairness：如果一種資源是緊缺的資源，那么解決方案退化為那種資源的最大最小公平性。3、Population monotoni

39、city：當(dāng)一個(gè)用戶離開系統(tǒng)，并且放棄他的資源，其余用戶的資源分配都不會(huì)減少。4、Resource monotonicity：如果更多的資源添加到系統(tǒng)中，現(xiàn)有用戶的資源分配都不會(huì)減少。3.4 DRF我們提出了支配資源公平性，一種針對(duì)多種資源類型的分配策略，滿足前一章中的所有四種特征。對(duì)于每個(gè)用戶，DRF會(huì)計(jì)算分配給用戶的每一種資源的占有率，一個(gè)用戶的所有的占有率中的最大的就是那個(gè)用戶的支配分配，和支配分配相對(duì)應(yīng)的資源被稱作支配資源。不同的用戶有不同的支配資源。舉個(gè)例子，用戶運(yùn)行計(jì)算受限任務(wù)時(shí)用戶的支配資源是CPU，而用戶運(yùn)行I/O受限任務(wù)時(shí)用戶的支配資源是帶寬。DRF僅僅在用戶的支配份額之間使

40、用最大最小公平，即DRF尋求最大化系統(tǒng)中最小的支配份額，然后是第二小的，以此類推。在這一節(jié)我們討論有n個(gè)用戶和m種資源的計(jì)算模型。每個(gè)用戶都運(yùn)行單個(gè)任務(wù)，每個(gè)任務(wù)的特征是資源需求向量，需求向量指定了這個(gè)任務(wù)所需要的各種資源的值，比如。一般來說，任務(wù)都有不同的需求。3.4.1 舉例考慮一個(gè)系統(tǒng)，包括9個(gè)CPU和18GB RAM，還有兩個(gè)用戶，其中用戶A運(yùn)行的任務(wù)的需求向量為，用戶B運(yùn)行的任務(wù)的需求向量為。圖3.2用戶的資源分配在上述方案中，用戶A的每個(gè)任務(wù)消耗總CPU的和總內(nèi)存的，所以用戶A的支配資源是內(nèi)存；用戶B的每個(gè)任務(wù)消耗總CPU的和總內(nèi)存的，所以用戶B的支配資源為CPU。DRF會(huì)均衡用戶

41、的支配分配，如圖3.2所示，用戶A的三個(gè)任務(wù)總共消耗了，用戶B的兩個(gè)任務(wù)總共消耗了；在這個(gè)分配中，每個(gè)用戶在結(jié)束后都會(huì)得到相同的支配分配，用戶A獲得了的RAM，而用戶B獲得了的CPU。這個(gè)分配可以用下面的數(shù)學(xué)方法計(jì)算出來：和分別是DRF分配給用戶A和用戶B的任務(wù)數(shù)目，然后用戶A消耗了，用戶B消耗了，在圖3.2中用戶A和用戶B消耗了同等支配資源；用戶A的支配占有率為，用戶B的支配占有率為。所以DRF分配可以通過求解以下的優(yōu)化問題來得到： （最大化分配） Subject to （CPU約束） （內(nèi)存約束） （支配占有率相等）求解以上問題，可以得出以及。因而用戶A獲得，B得到。需要注意的是，DRF并

42、不是總需要使用戶的支配占有率相等。當(dāng)一個(gè)用戶總的需求已經(jīng)被滿足，那么用戶就不再需要更多的任務(wù)，因此剩余的資源就會(huì)分配給其他用戶，就好像最大最小公平性。另外，如果一種資源被用完，那么不需要這種資源的用戶仍然可以繼續(xù)接收更多其他類型的資源分配。3.4.2 DRF調(diào)度算法算法1表明了DRF調(diào)度的偽代碼，這個(gè)算法會(huì)跟蹤計(jì)算分配給每個(gè)用戶的總資源和用戶的支配分配，。每一步，DRF都會(huì)從準(zhǔn)備運(yùn)行任務(wù)的用戶中挑選出支配分配最低的一個(gè)用戶。 算法1： /資源總量/ /消耗的資源量，初值為0/ /用戶i的支配占有率，初值為0/ /分配給用戶i的資源，初值為0/ 找出支配占有率最低的用戶 用戶下一個(gè)任務(wù)的需求 i

43、f then /更新消耗矢量/ /更新用戶i的分配矢量/ else return /資源已滿/ end if如果那個(gè)用戶的任務(wù)需求能被滿足，即系統(tǒng)中有足夠可用的資源，那么用戶的任務(wù)就會(huì)被啟動(dòng)。我們將其一般化，即一個(gè)用戶擁有不同需求向量的任務(wù)，我們用變量來表示用戶下一個(gè)想要運(yùn)行加載的任務(wù)的需求向量。為了簡(jiǎn)單化，偽代碼沒有捕獲任務(wù)結(jié)束事件，在這種情況下，用戶會(huì)釋放任務(wù)的資源，DRF會(huì)再一次選擇擁有最低支配分配的用戶去運(yùn)行他的任務(wù)。 調(diào)度用戶A用戶BCPU總量?jī)?nèi)存總量當(dāng)前分配主導(dǎo)分配當(dāng)前分配主導(dǎo)分配用戶B01/33/91/18用戶A2/91/34/95/18用戶A4/91/35/99/19用戶B4/

44、92/38/910/18用戶A2/32/3114/18 表一注意3.4.1節(jié)的兩個(gè)簡(jiǎn)單例子，表一為這個(gè)簡(jiǎn)單的例子闡明了DRF的分配過程。DRF首先選擇用戶B來運(yùn)行一個(gè)任務(wù)，然后用戶B的資源占用率變?yōu)?，用戶B的支配占有率變成了max =。接下來DRF選擇用戶A，因?yàn)榇藭r(shí)用戶A的支配占有率為0。這個(gè)將會(huì)過程持續(xù)進(jìn)行到不可能再運(yùn)行任務(wù)新的任務(wù)，在這種情況下，出現(xiàn)CPU一出現(xiàn)飽和就會(huì)停止。在以上分配結(jié)束后，用戶A會(huì)得到，同時(shí)用戶B會(huì)得到，也就是說，每一個(gè)用戶都獲得了2/3的支配資源。注意到，在這個(gè)例子中，任何資源只要達(dá)到飽和，那么分配就會(huì)停止。但是一般情況下，盡管有些資源已經(jīng)飽和了，也有可能繼續(xù)分配資

45、源給任務(wù)，因?yàn)橛行┤蝿?wù)對(duì)已經(jīng)飽和的資源沒有需求。3.4.3 加權(quán)DRF實(shí)際上，許多種情況下，均衡地在用戶之間分配資源的策略并不能讓人滿意。實(shí)際上我們可能想要分配更多的資源給運(yùn)行重要任務(wù)的用戶，或者給為集群貢獻(xiàn)出更多資源的用戶。為了達(dá)到這個(gè)目的，我們提出了加權(quán)DRF，一個(gè)概括了DRF和加權(quán)最大最小公平性的算法。在加權(quán)DRF中，每個(gè)用戶都關(guān)聯(lián)著一個(gè)權(quán)重向量，其中表示用戶對(duì)資源的權(quán)重。那么用戶的支配占有率的定義變成了，其中是用戶對(duì)資源的占有率。特別的當(dāng)所有用戶的權(quán)重都相等的時(shí)候，也就是說，在這種情況下，用戶的支配占有率就變?yōu)椤Ｈ绻杏脩舻臋?quán)重都設(shè)置為1，那么加權(quán)DRF就退化為DRF。3.5公平分配

46、策略的替代 定義一個(gè)公平分配在多資源的系統(tǒng)中不是一個(gè)簡(jiǎn)單的問題，因?yàn)楣礁拍畋旧砭褪侵档梦覀內(nèi)ビ懻摰?。在我們的努力下，在使用DRF之前我們考慮過許多分配策略，但只有DRF能滿足所有四個(gè)屬性：激勵(lì)共享、防止策略性操縱、帕累托最優(yōu)、無嫉妒性。在本節(jié)中，我們將列出兩種已經(jīng)調(diào)查過的方案：資產(chǎn)公平性，一種簡(jiǎn)單而直觀的策略，它的目的是為了均衡每個(gè)用戶得到的總計(jì)資源數(shù)；以及Competitive Equilibrium from Equal Incomes(CEEI)，這種策略被用在微觀經(jīng)濟(jì)領(lǐng)域中公平的配置資源。下面我們會(huì)將這些策略與DRF進(jìn)行比較。3.5.1 資產(chǎn)公平資產(chǎn)公平性背后的理念是不同資源的占有率

47、相等，那么它們的價(jià)值也相等，比如所有CPUs的1%，所有RAM的1%，以及所有I/O帶寬的1%它們的價(jià)值相等。資產(chǎn)公平性試圖使得每個(gè)用戶得到的總資源的價(jià)值相等。特別地，資產(chǎn)公平性會(huì)計(jì)算每個(gè)用戶的總的資源分配HYPERLINK /uploads/img/201312/12213416_Uy5A.png，其中是資源分配給用戶的量。然后在用戶的總占用率上使用最大最小公平性，比如它會(huì)多次的為有最小總資源占有率的用戶發(fā)出任務(wù)?？紤]第3.4.1節(jié)中的例子，系統(tǒng)擁有9個(gè)CPU和18GB的 RAM，既然RAM的GB數(shù)量是CPU數(shù)量的兩倍，一個(gè)CPU的價(jià)值相當(dāng)于2GB的RAM的價(jià)值。假設(shè)1GB的RAM的價(jià)值為1

48、，那么1個(gè)CPU的價(jià)值為2，那么接下來用戶A需要為每個(gè)任務(wù)花費(fèi)6，而用戶B需要我每個(gè)任務(wù)花費(fèi)7。設(shè)置和分別為資產(chǎn)公平性算法分配給用戶A和用戶B的任務(wù)數(shù)量。然后資產(chǎn)公平分配可以通過求解以下問題來得到： subject to 求解上面這個(gè)問題，可以得到，以及,。因此，用戶A得到了，而用戶B得到了。這個(gè)分配策略的簡(jiǎn)單性很吸引人，但它有一個(gè)重大的缺陷：它違反了激勵(lì)共享特性。資產(chǎn)公平性可以導(dǎo)致一個(gè)用戶獲取了小于總資源的1/n的資源，其中n為總的用戶數(shù)目。3.5.2 CEEI在微觀經(jīng)濟(jì)理論中，公平分配資源優(yōu)先選擇的方法是Competitive Equilibrium from Equal Incomes(

49、CEEI)，在CEEI中，每個(gè)用戶最初接收到所有資源的1/n，接下來每個(gè)用戶會(huì)在一個(gè)完全競(jìng)爭(zhēng)的市場(chǎng)與其他用戶交易資源。CEEI的輸出同時(shí)滿足無嫉妒性和帕累托最優(yōu)。更加精準(zhǔn)描述是：CEEI分配是由Nash bargaining solution ADDIN NE.Ref.ECF667CE-39E6-44E3-BB11-4ED2B9FEA303#給出的，Nash bargaining solution會(huì)選擇可行的分配策略，使得HYPERLINK /uploads/img/201312/12213416_sGW8.png最大化，其中HYPERLINK /uploads/img/201312/1221

50、3416_dKgV.png是用戶i獲取資源HYPERLINK /uploads/img/201312/12213416_ihHy.png 的方式或功能，為了簡(jiǎn)化對(duì)比，我們將一個(gè)用戶得到其資源分配的方式簡(jiǎn)化為就是其支配分配，HYPERLINK /uploads/img/201312/12213417_IQQp.png ?？紤]第3.4.1節(jié)兩用戶的例子，回憶一下用戶A的支配分配為4x/18 = 2x/9，而用戶B的支配分配為3y/9 = y/3。其中為用戶A的任務(wù)數(shù)目，為用戶B的任務(wù)數(shù)目。最大化支配分配的結(jié)果就等同于最大化的結(jié)果。因此，CEEI的目的在于解決如下的優(yōu)化問題：subject to 解

51、決以上問題得到，。因而用戶A獲得了，同時(shí)用戶B獲得了。很遺憾，雖然CEEI同時(shí)滿足無嫉妒性和帕累托最優(yōu)，但是它不是防止策略操縱的，因此用戶可以通過謊報(bào)他們的資源需求來提高他們的分配。3.5.3 與DRF比較為了給讀者對(duì)資產(chǎn)公平和CEEI呈現(xiàn)一個(gè)直觀的理解，我們?cè)谙聢D中，將三種算法資源分配進(jìn)行對(duì)比。圖3.3 資源分配對(duì)比我們看DRF使得用戶的支配分配趨于均衡，比如，用戶A的內(nèi)存分配和用戶B的CPU分配。相比之下，資產(chǎn)公平使得用戶的總資源分配的百分比趨于均衡。最后，因?yàn)镃EEI假設(shè)有一個(gè)完全競(jìng)爭(zhēng)性市場(chǎng)，它找到了一個(gè)滿足市場(chǎng)結(jié)清的解決方案，使得當(dāng)中所有的資源都已經(jīng)得到分配，遺憾的是這個(gè)精確的特性可能

52、會(huì)欺騙CEEI：用戶可以宣稱她需要更多地未充分利用的資源，導(dǎo)致CEEI給予這個(gè)用戶更多的任務(wù)以便于達(dá)到市場(chǎng)結(jié)清。第四章 總結(jié)與展望我們已經(jīng)介紹了支配資源公平(DRF)，一個(gè)公平的共享模型，概括了對(duì)多資源類型的最大最小公平。DRF允許集群調(diào)度考慮異構(gòu)數(shù)據(jù)中心應(yīng)用程序的要求，導(dǎo)致了比現(xiàn)存的分配相同的資源片(槽)給所有任務(wù)的解決方案更加公平的分配和更高的效用。DRF滿足許多可取的屬性。特別是，DRF的防止策略性操縱的屬性，他能夠督促用戶更加準(zhǔn)確的報(bào)告他們的需求。DRF還鼓勵(lì)用戶共享資源。從我們調(diào)查了的其他調(diào)度器，以及從微觀經(jīng)濟(jì)文獻(xiàn)中選擇的公平概念都無法滿足所有的這些屬性。我們已經(jīng)通過在Mesos資源

53、管理器中運(yùn)行來評(píng)估DRF，結(jié)果表明它能使系統(tǒng)的整體性能優(yōu)于如今經(jīng)常使用的基于插槽的公平調(diào)度器。對(duì)于未來的研究我們也有一些方向。首先，離散任務(wù)在集群環(huán)境中，一個(gè)有意義的問題是如何在不影響公平的情況下減少資源的分散。這個(gè)問題類似于bin-packing，但是其中的一個(gè)必須盡可能包含更多的任務(wù)來滿足DRF。第二個(gè)方向是當(dāng)任務(wù)有了位置約束是怎樣定義公平，如機(jī)器的參數(shù)設(shè)置。鑒于當(dāng)前多核機(jī)器的趨勢(shì)，第三個(gè)研究方向是探索怎樣把DRF當(dāng)作操作系統(tǒng)的調(diào)度器。最后，從微觀經(jīng)濟(jì)的角度來看，一個(gè)自然的方向是探究DRF是否是唯一的滿足防止策略性操縱的多資源分配方案，還有其他的屬性是否也是惟一的。 ADDIN NE.Bi

54、b參考文獻(xiàn) 1 Bertsekas D, Gallager R. Data Networks, 2 ndZ. Prentice Hall, 1991. 2 Kesahv S, Keshav S, Keshav S. Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone NetworkZ. Addison-Wesley Professional, 1997. 3 Cao Z, Zegura E W. Utility max-min: An application-ori

55、ented bandwidth allocation schemeC. IEEE, 1999. 4 Shenker S. Fundamental design issues for the future InternetJ. Selected Areas in Communications, IEEE Journal on. 1995, 13(7): 1176-1188. 5 Kelly F. Charging and rate control for elastic trafficJ. European transactions on Telecommunications. 1997, 8(

56、1): 33-37. 6 Blake S, Black D, Carlson M, et al. An architecture for differentiated servicesJ. 1998. 7 Waldspurger C A, Weihl W E. Stride scheduling: Deterministic proportional-share resource managementR. Technical Memo MIT/LCS/TM-528, MIT Laboratory for Computer Science, 1995. 8 Waldspurger C A, We

57、ihl W E. Lottery scheduling: Flexible proportional-share resource managementC. USENIX Association, 1994. 9 Demers A, Keshav S, Shenker S. Analysis and simulation of a fair queueing algorithmC. ACM, 1989.10 Isard M, Prabhakaran V, Currey J, et al. Quincy: fair scheduling for distributed computing clustersC. ACM, 2009.11 Zaharia M, Borthakur D, Sen Sarma J, et al. De