嵌入式终端资源分配算法研究(论文)最终版

1、本科毕业设计（论文）题目嵌入式终端资源分配算法的研究学生姓名： 专 业： 指导教师： 完成日期： 诚 信 承 诺 书本人承诺：所呈交的论文是本人在导师指导下进行的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签 名： 日 期： 本论文使用授权说明本人完全了解南通大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容。（保密的论文在解密后应遵守此规定）学生签名： 指导教师签名： 日期： 南通大学毕

2、业设计（论文）摘 要资源分配在各个领域中都有广泛的应用。在嵌入式系统中资源分配的主要任务是将有限的资源合理地分配给用户，其目的是通过这样的分配来提高系统的性能和用户的服务体验。在基于公平的资源分配算法上，介绍了资源分配的研究背景和现状，论述了资源分配的公平准则和公平概念，包括一些具体的方法。除了适用于单资源的最大最小公平，比例公平和效用公平外，重点介绍了适用于多资源的DRF算法在资源分配中的应用。另外也将DRF与其它多资源的公平分配算法进行了比较，显示DRF分配使得用户的支配资源分配趋于均衡，并且DRF也拥有许多的独有属性，这些属性可以让用户更加公平地得到资源分配。因此DRF能够使得系统的整体

3、性能更加优异。关键词：资源分配，公平性，多资源，DRFI南通大学毕业设计（论文）ABSTRACTThe allocation of resources are widely used in all fields. Its main task is to allocate the limited resources to users reasonably in an embedded system. Its purpose is to through such allocation to improve the performance of the system and user se

4、rvice 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, proportional fairness and utility max

5、-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 DRF leads the dominant resour

6、ce 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, Fairness, Multiple resources, DR

7、F目 录摘 要IABSTRACTII目 录III第一章 绪 论11.1本课题研究的背景11.2研究领域现状11.3所做的主要工作2第二章 公平准则和公平概念32.1最大最小公平性32.2效用最大最小公平性42.3比例公平性52.4公平的一般概念6第三章 支配资源的公平性（DRF）83.1引言83.2动机93.3分配特性103.4 DRF113.4.1 举例113.4.2 DRF调度算法133.4.3 加权DRF143.5公平分配策略的替代153.5.1 资产公平153.5.2 CEEI163.5.3 与DRF比较17第四章 总结与展望18 ADDIN NE.Bib参考文献19致 谢21第一章

8、绪 论1.1本课题研究的背景随着21世纪互联网的快速发展，计算机和互联网已经已经成为人们生活中必不可少的元素了。网络上存放着各式各样的资源，人们可以通过网络来观看电视，查看新闻，阅读书籍。尽管网络存储和网络带宽在不断增加，资源的增加速度也越来越快除了一些可复制或重用的资源可以满足人们的需求，仍然有一些总量有限的资源始终达不到人们的需求，例如网络带宽、网络服务等。因此许多研究者针对如何分配稀缺资源是的资源分配系统获得高效益而提出了最初的资源分配算法研究。硬件技术的发展，智能终端已经成为生活中的必需品，它能够同时处理多个任务，给用户更好的服务体验。但是智能终端仍然存在资源不足的情况，例如智能电视，

9、这时一些研究者根据网络的资源分配算法提出了嵌入式终端的资源分配算法。对于智能电视而言，它作为嵌入式终端，它的资源十分有限，例如Sigma Designs 8655平台的基本配置为：CPU主频500M、内存大小256M。然而智能电视需要支持多任务并行，这样必然会引起资源过载，多任务之间竞争资源的状况，从而影响任务的运行和用户的体验。另外，对于弹性应用，可以根据资源分配的数量，调整任务的执行，获得不同的服务质量，例如可伸缩视频解码任务是典型的弹性应用，可以根据资源分配，解码基本层和不同的增强层，获得不同的信噪比、分辨率及帧率。因此，在智能电视中，需要对有限的资源进行合理的分配，使得系统总的服务质量

10、达到最优。但是，系统总的服务质量并不是资源分配的唯一目标，在资源分配过程中，还需要考虑资源分配的公平性，尤其当智能电视系统面临多用户场景时。因此，研究基于公平性的资源分配问题也具有重要意义。 1.2研究领域现状在嵌入式终端的资源分配方面，对于传统的基于效用的资源分配算法许多的研究者已经提出了相关的理论，例如Rajkumar等人提出了一种基于QoS保障的资源分配模型Q-RAM，旨在满足应用最小需求的条件下最大化整体系统效用，并给出了单资源、多QoS维度情况下的资源分配算法。随后，Rajkumar又在该模型的基础上，研究了多资源、单QoS属性约束条件下资源分配问题。Lee等人提出了基于离散QoS指

11、标的资源分配模型，并分别研究了单资源、多QoS约束和多资源、多QoS约束条件下的资源分配问题，给出了基于动态规划的最优解算法和基于本地搜索的近似算法。Khan在研究多会话多媒体系统质量自适应问题时，首次提出多维多选择背包问题（MMKP），以系统效用最大作为优化目标，并给出基于分支限界法的BBLP算法，以求得问题的最优解。对于资源分配我们不能仅仅考虑效用最大化，还需要考虑公平性的问题。仅仅最大化效用而有失公平同样会影响 用户的体验。针对这个问题研究者们又提出了基于公平的资源分配算法理论，例如基于自控理论的公平共享控制，Harada等人提出通过控制理论求解公平的资源分配。基于合作博弈论的公平共享控

12、制，Mastronarde等人提出利用公理性议价理论中卡莱-斯莫罗廷斯基议价解确定公平的资源分配（简称RA_KSBS算法）。基于弹性模型的公平共享控制，Buttazzo等人提出了弹性任务模型，任务的资源利用率被看作线性弹簧，具有弹性系数，并且随着弹性系数动态变化，以避免过载条件。1.3所做的主要工作对于嵌入式资源的分配我们要考虑很多比如单资源、多资源、基于效用还是基于公平，这些都是研究算法所必须要关注的问题。本文研究的主要是基于公平的多资源分配算法，另外还会介绍一些基于公平的单资源分配算法。全文共分为四章，各章节的主要内容安排如下：第一章为绪论，简要介绍了嵌入式终端资源分配算法的研究背景、意义

13、和目前国内外研究现状。第二章定义了公平准则和公平概念，主要介绍了一些对于单资源的公平性分配算法，其中包括了最大最小公平性，效用最大最小公平性，比例公平性。第三章对多资源公平性分配算法进行介绍，提出了支配资源公平性算法。其中包括理论知识、算法实现。另外还与其它的类似算法进行了对比。第四章是总结与展望，对本文的研究内容和创新点进行总结，并对未来的研究方向进行展望。1第二章 公平准则和公平概念在尝试设计一个公平的资源分配策略时，必须首先定义一个公平概念，即确定一个可以通过分配策略来判断公平的标准。如果多个任务争夺一个共享资源，为了解决什么是公平，一些文献提出了许多的公平准则。其中最常见的是最大最小公

14、平性，比例公平性和效用最大最小公平性，如下所诉。2.1最大最小公平性对于一种共享资源，用最大最小公平性策略来分配，那么多个用户之间拥有相等的分配权但是有不同的需求，它必须遵守以下的原则1, 2：l 共享的资源按需求的增长次序来分配l 用户不会得到比他需求更多的资源分配l 所有没有达到资源需求的用户将会得到相等的资源分配最大最小公平性也可以等效的定义为：没有用户可以增加他的资源分配却不减少其他有更少或相等的资源需求的用户的资源分配。在最大最小公平性下不会给予额外的资源，即对于不满足资源需求的用户仅仅增大资源需求不会增加资源分配。在实际的资源分配过程中，由于用户具有不同的权重，所以资源要基于相对应

15、的权重来分配。考虑有N个用户，用户的资源需求为，相对应的权重为。给定R为分配给N的用户的总资源量，满足最大最小公平性的资源分配是唯一的。为了方便起见，在整篇论文中我们用表示用户的资源需求矢量，表示权重矢量。那么满足最大最小公平性的资源分配可以表示为(2.1)其中， 表示用户i的最大最小公平资源分配，的伪代码如下所示，的输入为用户的资源需求矢量、权重矢量以及资源的容量R，输出为资源分配矢量。for each end for;while ()Find source with minimum in ;if () thenRemove source from ;elsefor each if ( )

16、thenend if;end for;end if;end while;return ;2.2效用最大最小公平性效用最大最小公平的概念类似于最大最小公平，在效用最大最小公平下每个用户都关联一个效用函数3，该效用函数通过每个得到公平分配的用户来完成。效用函数表明一个用户得到一定数量的资源分配后的满意度，不同的用户可以有不同的效用函数4。以下是一些常见的例子：l 弹性流如电子邮件、Telnet、FTP应用程序可能有一个凸效用。换句话说，只要分配相对较少的资源效用函数就会快速的增长，而且当它达到某一点是就会饱和。图2.1(a)展示了这种类型的效用函数。l 实时流如视频和音频流有一个最低要求的分配资源

17、。只有当满足这种最低要求时这种类型的流的效用函数才会变大。另一方面，过度的增大资源分配不会显著的使效用函数增大。总之，实时流的效用函数通常有一个阈值点对应最低要求，如图2.1(b)所示。l 自适应速率也有跟实时流类似的效用函数，除了效用分化在最低需求点要求更光滑。换句话说，自适应速率流的效用函数有一个曲线拐点，如图2.1(c)所示。 图2.1注意,对于一组用户i，考虑到资源的总量为R，需求向量为,权重向量为还有每个用户的效用函数，分配向量由效用最大最小公平性表示为： (2.2) 这里每个用户的效用函数都包含在 函数中。最大最小公平性可以看作是一种特殊情况下的效用最大最小公平性，所有的用户都有相

18、同的线性效用函数。2.3比例公平性一些研究者指出最大最小公平性给予资源需求少的用户更多的优先权5。而比例公平性的定义强调资源需求少的用户的优先权更低。比例公平性定义为：假设用户的资源分配为，相应的效用函数为资源分配的对数函数，资源分配的目标是最大化所有用户总的效用。资源分配矢量满足比例公平性准则，当且仅当对于其它任意可行的资源分配矢量，总的比例变化是非正值，也就是说 (2.3) 这里我们指的是一个可行的分配，当且仅当，共享资源总量不超出分配所需要的资源。这公平准则意味着对数效用函数。类似于最大最小公平和效用最大最小公平的情况，比例公平也决定如何分配共享资源，考虑到资源总量为R，需求向量为和权重

19、向量为。换句话说,比例公平也可以表示如下： (2.4)2.4公平的一般概念注意，上述提到的公平标准决定了怎样去根据有竞争关系的用户的需求来分配单个共享资源。因此，为了方便，我们引入了一个符号，它可以表示其中的任何一个公平概念。考虑有N个用户，争夺一个共享资源，总量为R。用户 的权重为，表明用户的相对合法共享的资源。对于一个在差异化服务框架6下的用户，他的权重决定于在64种可能的类型中他自己的用户类型。对于一个在最优网络中的用户，他的权重通常与其他所有的用户一样。用户的需求为。所以考虑到需求向量为，权重向量为，总的可用资源为R，任何的公平概念可以表示如下： (2.5)其中是用户i的资源分配，它是

20、由定义公平的函数F决定的，不同的公平准则有不同的F函数。你可能注意到在（2.2）式中效用函数并没有表示出来。然而，（2.2）式表示出一个可以描述怎样分配的通用符号，只要有确定的需求向量，就可以决定每个用户的资源分配，以便于分配所对应的效用满足于公平定义对应的效用。换句话说，式（2.2）把效用函数融入到了公平概念中。例如，最大最小公平意味着线性效用函数，比例公平使用对数效用函数,在效用最大最小公平，每个用户决定自己的效用函数。唯一的约束条件是相对于分配资源的数量效用函数是非递减函数。使用归一化的需求和分配可以等效的表示任何公平概念。定义用户i归一化的需求为，如下所示：用户i归一化的需求表明了用户

21、的需求占总资源的百分比。定义用户i归一化的资源分配为，如下所示：用户i归一化的分配表明了用户的分配占总资源的百分比。所以，给定归一化的需求向量，权重向量，任何给出的公平概念都可以用下面的式子表示， (2.6) 其中C是影响整个系统的约束条件，后面详细介绍。注意式（2.6）中对于任何变量都没有维度影响，因此，使它适用于有多个异构资源的系统。约束C作为函数F的参数，因为考虑到相同的需求和权向量，在系统中不同的约束会使公平分配不相同。约束C可以用来表示分配所达到的性能水平。例如，遵照最大最小公平原则，即使没有资源分配给用户也可以认为这是一个公平分配，尽管它会导致极差的性能。作为一个简单的例子，约束C

22、可以表示所有用户的效用总和。注意，在式（2.5）中资源总量也可以认为是在分配策略中的一个简单的约束：分配资源的总量不能超过资源R，也就是。所以，式（2.5）仅仅是式（2.6）的一种特殊情况。根据上下文，我们可以使用这两个中的任何一个的公平概念。例如，在本论文，当归一化没有必要时使用式(2.5)，就像考虑缓冲资源一样，而当归一化是必要时用式(2.6)，比如在考虑处理资源时。本章的内容主要介绍了一些对于单资源的公平分配策略，但是在实际当中，终端器件往往都是含有多种资源的，这就需要我们寻找一种新的资源分配策略，下面我们就来介绍一下多资源分配策略。第三章 支配资源的公平性（DRF）3.1引言在所有共享

23、的计算机系统中，都有一个重要的的构建模块，那就是资源的合理分配。迄今为止在已经研究出的分配策略中最受欢迎的是最大最小公平性，在系统中它会最大化用户得到的最小分配。假如每一个用户都有足够的资源需求，这种策略会分配给每个用户一份相等的共享资源。另外，现实中由于用户之间的重要性不同，又进一步的提出了加权的最大最小公平性，这种方法使得用户获得的资源与他的权重成正比。加权的最大最小公平性的魅力在于它的普遍性和它能够提供性能隔离的能力。加权的最大最小公平性模型可以适用于各种各样的资源分配策略，包括基于优先级的分配，基于预留的分配，和基于截止期限的分配7等。另外，加权的最大最小公平性能够确保隔离，换句话说，

24、就是能够保证一个用户收到他的那份资源，而不用考虑其他用户的需求。鉴于这些特征，提出了许多算法以实现不同精确度的（加权的）最大最小公平性，例如轮叫、比例资源共享8和加权公平队列9。这些算法已经被应用于各种不同的资源，例如链路带宽9-14、CPU7, 15, 16、内存和存储。目前在公平分配上已经做了大量地工作和实践，但是到现在为止主要还是集中在单资源类型的环境下。甚至在多资源类型的环境下，用户具有异构的资源需求，典型的资源分配的做法还是使用单类型资源抽象。比如Hadoop和Dryad17, 18，这两种广泛使用的集群计算框架，它们的公平调度器在资源分配时使用插槽，所谓的插槽就是对节点资源按照固定

25、大小进行划分而产生的分区。然而实际上是集群中不同的任务对CPU、内存和IO资源有着不同的需求。这篇文章里，在多种类型的资源环境下我们为有异构需求的用户解决公平分配问题。尤其，我们提出支配资源的公平性（DRF），针对多资源推广最大最小公平性。DRF背后的直观理解是在多资源的环境下一个用户的分配应该由用户的支配份额决定，支配份额是指在已经分配给用户的所有资源中，占据最大份额的一种资源。简单的说，DRF力图最大化所有用户的最小的支配份额。举个例子，假设A用户运行CPU密集的任务，B用户运行内存密集的任务，DRF试图去均衡用户A的CPU分配和用户B的内存分配。在单资源的情况下，DRF退化为最大最小公平

26、性。DRF的优点在于它所满足的特性。在单资源场景下，这些特性由最大最小公平性平凡地满足，但是，在多资源场景下，这些特性都是不寻常的。四个这种类型的特性分别是激励共享、防止策略性操纵、帕累托最优和无嫉妒性。DRF为用户提供激励机制去分配资源，通过保证用户在系统中不会有多余的资源来达到这一目的。此外，DRF是防止策略性操纵的，因为用户不可能通过谎报他的资源需求来获得更多的资源分配。DRF是帕累托最优的，因为在满足其它特性的同时分配所有可用的资源，而不会取代现存的资源分配。最后，DRF是无嫉妒的，没有用户更喜欢其他用户的资源分配。3.2动机虽然早先关于加权最大最小公平性的工作都集中在单一资源的情况，

27、但是云计算和多核处理器的出现提高了对多资源和异构用户请求的环境下分配策略的需求。多资源意味着不同种类型的资源，而不是同一种可互换资源的多个实例。目前已有的集群公平调度器，例如Quincy17和Hadoop公平调度器18, 19都忽视了异构的用户需求和以插槽为粒度的资源分配，其中一个插槽就是一个节点上固定比例的资源。这就导致了分配的效率很低，因为一个插槽对与任务的需求多半是一个不好的匹配。图3.1任务的需求与单位插槽的资源之比的概率分布图3.1量化了Hadoop MapReduce 公平调度器所提供的的公平性和隔离性的水平。该图显示了任务的CPU需求和插槽的CPU 份额之间的比率的概率分布图以及

28、任务的内存需求和插槽的内存份额之间的比率的概率分布图。我们计算插槽内存和CPU的分配通过把总的内存和CPU除以插槽的数量。比值为1相当于任务的需求和插槽的资源完美的匹配，比值小于1相当于任务没有充分地利用插槽资源，比值大于1相当于任务已经过度的使用了他们插槽的资源，这会导致系统起伏不定。图3.1表明绝大部分任务或者没有充分利用插槽资源或者过载地利用插槽资源。修改每台机器的插槽数量并不能解决这个问题，因为这样可能会导致更低的总利用率或者更多的任务因为过载而导致的性能不佳。3.3分配特性现在我们将注意转向为多资源和异构请求的情况设计一个最大最小公平的分配策略。为了说明这个问题，我们假设一个系统，包

29、括9个CPU和18GB的RAM，以及两个用户：用户A的每个运行任务需要<1CPU，4GB RAM>，用户B的每个运行任务需要<3CPUs，1GB RAM>。如何为这种情况建立一个公平的分配策略？一种可能是把每种资源的一半分给每个用户。另一种可能就是均衡每个用户总的资源分配。虽然想出各种各样可能的公平分配很简单，但是仍然不清楚怎样去评价和比较这些分配方案。为了应对这一挑战，我们先从一系列合理的特性开始，我们相信任何多资源的和异构需求的资源分配都应该满足这些特性。然后，用这些属性引导公平分配策略的制定。我们发现以下四个属性是重要的。1、激励共享：相比专享自己的集群分区，通过

30、共享集群每一个用户都应该更好。考虑一个集群具有相同的节点和n个用户，一个用户不能在包含1/n资源的集群分区中分配更多的任务。2、防止策略性操纵：用户不应该能通过谎报资源需求得到益处。用户不能通过欺骗来提高它的分配。3、无嫉妒性：一个用户不应该更喜欢另一个用户的分配。这个特性包含了公平的概念20。4、帕累托最优：不可能在增加一个用户的分配的同时而不降低至少另一个用户的分配。这个特性非常重要，因为它会使得在满足其它特性的同时最大化系统的利用率。我们简单地评价一下防止策略性操纵和共享激励特性，我们相信这两个特性在数据中心环境下特别重要。例如，yahoo的一个Hadoop MapReduce集群对ma

31、p和reduce任务有不同的插槽。一个用户发现Map插槽存在竞争，因此就将他的所有任务都长期地运行在Reduce阶段，手工地执行本来应该在Map阶段执行地工作。另一个大型搜索公司为用户高利用率的作业提供了专门的机器，这个公司马上就发现用户在他们的代码中散布无限循环用于人为地提升利用率级别。此外，任何满足激励共享特性的策略同样也提供性能隔离，因为它保证每个用户的最小分配，（也就是说，一个用户不可能会比拥有1/n集群资源更差），不管其他用户的需求。在单资源的情况下，最大最小公平性满足所有上述特性。然而，在多资源和异构用户需求的情况下，获得这些特性是不简单的。例如，在微观经济学理论中首选的公平分配机

32、制 Competitive Equilibrium from Equal Incomes20-22不是防止策略性操纵的。除了以上特性，我们还考虑了另外四种不错的特性：1、Single resource fairness：对于单个资源，解决方案退化为最大最小公平性。2、Bottleneck fairness：如果一种资源是紧缺的资源，那么解决方案退化为那种资源的最大最小公平性。3、Population monotonicity：当一个用户离开系统，并且放弃他的资源，其余用户的资源分配都不会减少。4、Resource monotonicity：如果更多的资源添加到系统中，现有用户的资源分配都不会减

33、少。3.4 DRF我们提出了支配资源公平性，一种针对多种资源类型的分配策略，满足前一章中的所有四种特征。对于每个用户，DRF会计算分配给用户的每一种资源的占有率，一个用户的所有的占有率中的最大的就是那个用户的支配分配，和支配分配相对应的资源被称作支配资源。不同的用户有不同的支配资源。举个例子，用户运行计算受限任务时用户的支配资源是CPU，而用户运行I/O受限任务时用户的支配资源是带宽。DRF仅仅在用户的支配份额之间使用最大最小公平，即DRF寻求最大化系统中最小的支配份额，然后是第二小的，以此类推。在这一节我们讨论有n个用户和m种资源的计算模型。每个用户都运行单个任务，每个任务的特征是资源需求向

34、量，需求向量指定了这个任务所需要的各种资源的值，比如<1CPU，4GB RAM>。一般来说，任务都有不同的需求。3.4.1 举例考虑一个系统，包括9个CPU和18GB RAM，还有两个用户，其中用户A运行的任务的需求向量为<1CPU，4GB RAM>，用户B运行的任务的需求向量为<3CPUs，1GB RAM>。图3.2用户的资源分配在上述方案中，用户A的每个任务消耗总CPU的和总内存的，所以用户A的支配资源是内存；用户B的每个任务消耗总CPU的和总内存的，所以用户B的支配资源为CPU。DRF会均衡用户的支配分配，如图3.2所示，用户A的三个任务总共消耗了&l

35、t;3CPUs，12GB RAM>，用户B的两个任务总共消耗了<6CPUs，2GB RAM>；在这个分配中，每个用户在结束后都会得到相同的支配分配，用户A获得了的RAM，而用户B获得了的CPU。这个分配可以用下面的数学方法计算出来：和分别是DRF分配给用户A和用户B的任务数目，然后用户A消耗了<CPU，GB RAM>，用户B消耗了<CPU，GB RAM>，在图3.2中用户A和用户B消耗了同等支配资源；用户A的支配占有率为，用户B的支配占有率为。所以DRF分配可以通过求解以下的优化问题来得到： （最大化分配） Subject to （CPU约束） （内存

36、约束） （支配占有率相等）求解以上问题，可以得出以及。因而用户A获得<3CPUs，12GB RAM>，B得到<6CPUs，2GB RAM>。需要注意的是，DRF并不是总需要使用户的支配占有率相等。当一个用户总的需求已经被满足，那么用户就不再需要更多的任务，因此剩余的资源就会分配给其他用户，就好像最大最小公平性。另外，如果一种资源被用完，那么不需要这种资源的用户仍然可以继续接收更多其他类型的资源分配。3.4.2 DRF调度算法算法1表明了DRF调度的伪代码，这个算法会跟踪计算分配给每个用户的总资源和用户的支配分配，。每一步，DRF都会从准备运行任务的用户中挑选出支配分配最

37、低的一个用户。 算法1： /资源总量/ /消耗的资源量，初值为0/ /用户i的支配占有率，初值为0/ /分配给用户i的资源，初值为0/ 找出支配占有率最低的用户 用户下一个任务的需求 if then /更新消耗矢量/ /更新用户i的分配矢量/ else return /资源已满/ end if如果那个用户的任务需求能被满足，即系统中有足够可用的资源，那么用户的任务就会被启动。我们将其一般化，即一个用户拥有不同需求向量的任务，我们用变量来表示用户下一个想要运行加载的任务的需求向量。为了简单化，伪代码没有捕获任务结束事件，在这种情况下，用户会释放任务的资源，DRF会再一次选择拥有最低支配分配的用户

38、去运行他的任务。 调度用户A用户BCPU总量内存总量当前分配主导分配当前分配主导分配用户B<0,0>0<3/9,1/18>1/33/91/18用户A<1/9,4/18>2/9<3/9,1/18>1/34/95/18用户A<2/9,8/18>4/9<3/9,1/18>1/35/99/19用户B<2/9,8/18>4/9<6/9,2/18>2/38/910/18用户A<3/9,12/18>2/3<6/9,2/18>2/3114/18 表一注意3.4.1节的两个简单例子，表一为这个

39、简单的例子阐明了DRF的分配过程。DRF首先选择用户B来运行一个任务，然后用户B的资源占用率变为，用户B的支配占有率变成了max =。接下来DRF选择用户A，因为此时用户A的支配占有率为0。这个将会过程持续进行到不可能再运行任务新的任务，在这种情况下，出现CPU一出现饱和就会停止。在以上分配结束后，用户A会得到<3CPUs, 12GB RAM>，同时用户B会得到<6CPUs，2GB RAM>，也就是说，每一个用户都获得了2/3的支配资源。注意到，在这个例子中，任何资源只要达到饱和，那么分配就会停止。但是一般情况下，尽管有些资源已经饱和了，也有可能继续分配资源给任务，因为

40、有些任务对已经饱和的资源没有需求。3.4.3 加权DRF实际上，许多种情况下，均衡地在用户之间分配资源的策略并不能让人满意。实际上我们可能想要分配更多的资源给运行重要任务的用户，或者给为集群贡献出更多资源的用户。为了达到这个目的，我们提出了加权DRF，一个概括了DRF和加权最大最小公平性的算法。在加权DRF中，每个用户都关联着一个权重向量，其中表示用户对资源的权重。那么用户的支配占有率的定义变成了，其中是用户对资源的占有率。特别的当所有用户的权重都相等的时候，也就是说，在这种情况下，用户的支配占有率就变为。如果所有用户的权重都设置为1，那么加权DRF就退化为DRF。3.5公平分配策略的替代 定

41、义一个公平分配在多资源的系统中不是一个简单的问题，因为公平概念本身就是值得我们去讨论的。在我们的努力下，在使用DRF之前我们考虑过许多分配策略，但只有DRF能满足所有四个属性：激励共享、防止策略性操纵、帕累托最优、无嫉妒性。在本节中，我们将列出两种已经调查过的方案：资产公平性，一种简单而直观的策略，它的目的是为了均衡每个用户得到的总计资源数；以及Competitive Equilibrium from Equal Incomes(CEEI)，这种策略被用在微观经济领域中公平的配置资源。下面我们会将这些策略与DRF进行比较。3.5.1 资产公平资产公平性背后的理念是不同资源的占有率相等，那么它们

42、的价值也相等，比如所有CPUs的1%，所有RAM的1%，以及所有I/O带宽的1%它们的价值相等。资产公平性试图使得每个用户得到的总资源的价值相等。特别地，资产公平性会计算每个用户的总的资源分配，其中是资源分配给用户的量。然后在用户的总占用率上使用最大最小公平性，比如它会多次的为有最小总资源占有率的用户发出任务。考虑第3.4.1节中的例子，系统拥有9个CPU和18GB的 RAM，既然RAM的GB数量是CPU数量的两倍，一个CPU的价值相当于2GB的RAM的价值。假设1GB的RAM的价值为¥1，那么1个CPU的价值为¥2，那么接下来用户A需要为每个任务花费¥6，而用户

43、B需要我每个任务花费¥7。设置和分别为资产公平性算法分配给用户A和用户B的任务数量。然后资产公平分配可以通过求解以下问题来得到： subject to 求解上面这个问题，可以得到，以及,。因此，用户A得到了<2.5 CPUs，10.1GB RAM>，而用户B得到了<6.5CPUs，2.2 GB RAM>。这个分配策略的简单性很吸引人，但它有一个重大的缺陷：它违反了激励共享特性。资产公平性可以导致一个用户获取了小于总资源的1/n的资源，其中n为总的用户数目。3.5.2 CEEI在微观经济理论中，公平分配资源优先选择的方法是Competitive Equilibr

44、ium from Equal Incomes(CEEI)，在CEEI中，每个用户最初接收到所有资源的1/n，接下来每个用户会在一个完全竞争的市场与其他用户交易资源。CEEI的输出同时满足无嫉妒性和帕累托最优。更加精准描述是：CEEI分配是由Nash bargaining solution#给出的，Nash bargaining solution会选择可行的分配策略，使得最大化，其中是用户i获取资源 的方式或功能，为了简化对比，我们将一个用户得到其资源分配的方式简化为就是其支配分配， 。考虑第3.4.1节两用户的例子，回忆一下用户A的支配分配为4x/18 = 2x/9，而用户B的支配分配为3y/

45、9 = y/3。其中为用户A的任务数目，为用户B的任务数目。最大化支配分配的结果就等同于最大化的结果。因此，CEEI的目的在于解决如下的优化问题：subject to 解决以上问题得到，。因而用户A获得了<4.1 CPUs， 16.4 GB RAM>，同时用户B获得了<4.9 CPUs， 1.6GB RAM>。很遗憾，虽然CEEI同时满足无嫉妒性和帕累托最优，但是它不是防止策略操纵的，因此用户可以通过谎报他们的资源需求来提高他们的分配。3.5.3 与DRF比较为了给读者对资产公平和CEEI呈现一个直观的理解，我们在下图中，将三种算法资源分配进行对比。图3.3 资源分配对

46、比我们看DRF使得用户的支配分配趋于均衡，比如，用户A的内存分配和用户B的CPU分配。相比之下，资产公平使得用户的总资源分配的百分比趋于均衡。最后，因为CEEI假设有一个完全竞争性市场，它找到了一个满足市场结清的解决方案，使得当中所有的资源都已经得到分配，遗憾的是这个精确的特性可能会欺骗CEEI：用户可以宣称她需要更多地未充分利用的资源，导致CEEI给予这个用户更多的任务以便于达到市场结清。19第四章 总结与展望我们已经介绍了支配资源公平(DRF)，一个公平的共享模型，概括了对多资源类型的最大最小公平。DRF允许集群调度考虑异构数据中心应用程序的要求，导致了比现存的分配相同的资源片(槽)给所有

47、任务的解决方案更加公平的分配和更高的效用。DRF满足许多可取的属性。特别是，DRF的防止策略性操纵的属性，他能够督促用户更加准确的报告他们的需求。DRF还鼓励用户共享资源。从我们调查了的其他调度器，以及从微观经济文献中选择的公平概念都无法满足所有的这些属性。我们已经通过在Mesos资源管理器中运行来评估DRF，结果表明它能使系统的整体性能优于如今经常使用的基于插槽的公平调度器。对于未来的研究我们也有一些方向。首先，离散任务在集群环境中，一个有意义的问题是如何在不影响公平的情况下减少资源的分散。这个问题类似于bin-packing，但是其中的一个必须尽可能包含更多的任务来满足DRF。第二个方向是

48、当任务有了位置约束是怎样定义公平，如机器的参数设置。鉴于当前多核机器的趋势，第三个研究方向是探索怎样把DRF当作操作系统的调度器。最后，从微观经济的角度来看，一个自然的方向是探究DRF是否是唯一的满足防止策略性操纵的多资源分配方案，还有其他的属性是否也是惟一的。参考文献 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

49、 Internet, and the Telephone NetworkZ. Addison-Wesley Professional, 1997. 3 Cao Z, Zegura E W. Utility max-min: An application-oriented bandwidth allocation schemeC. IEEE, 1999. 4 Shenker S. Fundamental design issues for the future InternetJ. Selected Areas in Communications, IEEE Journal on. 1995,

50、13(7): 1176-1188. 5 Kelly F. Charging and rate control for elastic trafficJ. European transactions on Telecommunications. 1997, 8(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 propor

51、tional-share resource managementR. Technical Memo MIT/LCS/TM-528, MIT Laboratory for Computer Science, 1995. 8 Waldspurger C A, Weihl W E. Lottery scheduling: Flexible proportional-share resource managementC. USENIX Association, 1994. 9 Demers A, Keshav S, Shenker S. Analysis and simulation of a fai

52、r 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. Delay scheduling: a simple technique for achieving locality and fairness in cluster schedulingC. ACM, 2010.12 Foley D K. Resource allocation and the public sectorJ. YALE