当前位置:首页 >> 信息与通信 >>

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


本科毕业设计(论文)
题 目 嵌入式终端资源分配算法的研究

学生姓名: 专 业: 指导教师: 完成日期:

诚 信 承 诺 书
本人承诺:所呈交的论文是本人在导师指导下进行的研究成果。除了文 中特别加以标注和致谢的地方外,论文中不包含其他人已发表或撰写过的研 究成果。参与同一工作的其他同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。

签 名:

日 期:

本论文使用授权说明
本人完全了解南通大学有关保留、使用学位论文的规定,即:学校有权 保留论文及送交论文复印件,允许论文被查阅和借阅;学校可以公布论文的 全部或部分内容。 (保密的论文在解密后应遵守此规定)

学生签名:

指导教师签名:

日期:

南通大学毕业设计(论文)





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

关键词:资源分配,公平性,多资源,DRF

I

南通大学毕业设计(论文)

ABSTRACT
The allocation of resources are widely used in all fields. It’s main task is to allocate the limited resources to users reasonably in an embedded system. It’s purpose is to through such allocation to improve the performance 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, proportional 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 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, Fairness, Multiple resources, DRF

II

南通大学毕业设计(论文)






要 .................................................................... I

ABSTRACT ............................................................... II
目 录 ................................................................... III 论 .............................................................. 1

第一章 绪

1.1 本课题研究的背景 ...................................................... 1 1.2 研究领域现状 .......................................................... 1 1.3 所做的主要工作 ........................................................ 2 第二章 公平准则和公平概念 ................................................... 3 2.1 最大最小公平性 ........................................................ 3 2.2 效用最大最小公平性 .................................................... 4 2.3 比例公平性 ............................................................ 5 2.4 公平的一般概念 ........................................................ 6 第三章 支配资源的公平性(DRF) .............................................. 8 3.1 引言 .................................................................. 8 3.2 动机 .................................................................. 9 3.3 分配特性 ............................................................. 10 3.4 DRF ................................................................. 11 3.4.1 举例 ............................................................ 11 3.4.2 DRF 调度算法 .................................................... 13 3.4.3 加权 DRF ........................................................ 14 3.5 公平分配策略的替代 ................................................... 15 3.5.1 资产公平 ........................................................ 15 3.5.2 CEEI ............................................................ 16 3.5.3 与 DRF 比较 ..................................................... 16 第四章 总结与展望 .......................................................... 18 ADDIN NE.Bib 参考文献 ...................................................... 19 致 谢 ................................................................... 21

III

南通大学毕业设计(论文)

第一章 1.1 本课题研究的背景





随着 21 世纪互联网的快速发展,计算机和互联网已经已经成为人们生活中必不可少 的元素了。网络上存放着各式各样的资源,人们可以通过网络来观看电视,查看新闻,阅 读书籍。尽管网络存储和网络带宽在不断增加,资源的增加速度也越来越快除了一些可复 制或重用的资源可以满足人们的需求,仍然有一些总量有限的资源始终达不到人们的需 求,例如网络带宽、网络服务等。因此许多研究者针对如何分配稀缺资源是的资源分配系 统获得高效益而提出了最初的资源分配算法研究。 硬件技术的发展,智能终端已经成为生活中的必需品,它能够同时处理多个任务,给 用户更好的服务体验。但是智能终端仍然存在资源不足的情况,例如智能电视,这时一些 研究者根据网络的资源分配算法提出了嵌入式终端的资源分配算法。对于智能电视而言, 它作为嵌入式终端, 它的资源十分有限, 例如 Sigma Designs 8655 平台的基本配置为: CPU 主频 500M、内存大小 256M。然而智能电视需要支持多任务并行,这样必然会引起资源过 载,多任务之间竞争资源的状况,从而影响任务的运行和用户的体验。另外,对于弹性应 用,可以根据资源分配的数量,调整任务的执行,获得不同的服务质量,例如可伸缩视频 解码任务是典型的弹性应用,可以根据资源分配,解码基本层和不同的增强层,获得不同 的信噪比、分辨率及帧率。因此,在智能电视中,需要对有限的资源进行合理的分配,使 得系统总的服务质量达到最优。但是,系统总的服务质量并不是资源分配的唯一目标,在 资源分配过程中, 还需要考虑资源分配的公平性, 尤其当智能电视系统面临多用户场景时。 因此,研究基于公平性的资源分配问题也具有重要意义。

1.2 研究领域现状
在嵌入式终端的资源分配方面,对于传统的基于效用的资源分配算法许多的研究者已 经提出了相关的理论,例如 Rajkumar 等人提出了一种基于 QoS 保障的资源分配模型 Q-RAM,旨在满足应用最小需求的条件下最大化整体系统效用,并给出了单资源、多 QoS 维度情况下的资源分配算法。随后, Rajkumar 又在该模型的基础上,研究了多资源、单 QoS 属性约束条件下资源分配问题。Lee 等人提出了基于离散 QoS 指标的资源分配模型, 并分别研究了单资源、多 QoS 约束和多资源、多 QoS 约束条件下的资源分配问题,给出 了基于动态规划的最优解算法和基于本地搜索的近似算法。 Khan 在研究多会话多媒体系统 质量自适应问题时,首次提出多维多选择背包问题(MMKP) ,以系统效用最大作为优化
1

南通大学毕业设计(论文)

目标,并给出基于分支限界法的 BBLP 算法,以求得问题的最优解。 对于资源分配我们不能仅仅考虑效用最大化,还需要考虑公平性的问题。仅仅最大化 效用而有失公平同样会影响 用户的体验。针对这个问题研究者们又提出了基于公平的资 源分配算法理论,例如基于自控理论的公平共享控制,Harada 等人提出通过控制理论求解 公平的资源分配。基于合作博弈论的公平共享控制,Mastronarde 等人提出利用公理性议价 理论中卡莱-斯莫罗廷斯基议价解确定公平的资源分配(简称 RA_KSBS 算法) 。基于弹性 模型的公平共享控制,Buttazzo 等人提出了弹性任务模型,任务的资源利用率被看作线性 弹簧,具有弹性系数,并且随着弹性系数动态变化,以避免过载条件。

1.3 所做的主要工作
对于嵌入式资源的分配我们要考虑很多比如单资源、 多资源、 基于效用还是基于公平, 这些都是研究算法所必须要关注的问题。本文研究的主要是基于公平的多资源分配算法, 另外还会介绍一些基于公平的单资源分配算法。 全文共分为四章,各章节的主要内容安排如下: 第一章为绪论,简要介绍了嵌入式终端资源分配算法的研究背景、意义和目前国内外 研究现状。 第二章定义了公平准则和公平概念,主要介绍了一些对于单资源的公平性分配算法, 其中包括了最大最小公平性,效用最大最小公平性,比例公平性。 第三章对多资源公平性分配算法进行介绍,提出了支配资源公平性算法。其中包括理 论知识、算法实现。另外还与其它的类似算法进行了对比。 第四章是总结与展望,对本文的研究内容和创新点进行总结,并对未来的研究方向进 行展望。

2

南通大学毕业设计(论文)

第二章

公平准则和公平概念

在尝试设计一个公平的资源分配策略时,必须首先定义一个公平概念,即确定一个可 以通过分配策略来判断公平的标准。如果多个任务争夺一个共享资源,为了解决什么是公 平,一些文献提出了许多的公平准则。其中最常见的是最大最小公平性,比例公平性和效 用最大最小公平性,如下所诉。

2.1 最大最小公平性
对于一种共享资源,用最大最小公平性策略来分配,那么多个用户之间拥有相等的分 配权但是有不同的需求,它必须遵守以下的原则[1, 2]: ? 共享的资源按需求的增长次序来分配 ? 用户不会得到比他需求更多的资源分配 ? 所有没有达到资源需求的用户将会得到相等的资源分配 最大最小公平性也可以等效的定义为:没有用户可以增加他的资源分配却不减少其他 有更少或相等的资源需求的用户的资源分配。在最大最小公平性下不会给予额外的资源, 即对于不满足资源需求的用户仅仅增大资源需求不会增加资源分配。 在实际的资源分配过程中,由于用户具有不同的权重,所以资源要基于相对应的权重 来分配。考虑有 N 个用户,用户 i 的资源需求为 d i ,相对应的权重为 wi 。给定 R 为分配给 N 的用户的总资源量,满足最大最小公平性的资源分配是唯一的。为了方便起见,在整篇 论文中我们用 ?d i ? 表示用户的资源需求矢量,?wi ? 表示权重矢量。那么满足最大最小公平性 的资源分配可以表示为

?ai ? ? FMMF ?R, ?di ?, ?wi ??

(2.1)

其中, a i 表示用户 i 的最大最小公平资源分配, FMMF 的伪代码如下所示, FMMF 的输 入为用户的资源需求矢量 ?d i ? 、权重矢量 ?wi ? 以及资源的容量 R,输出为资源分配矢量 ?ai ? 。
FMMF ?R, d , w? : N ? Length?d ?; Source? ? 1,2,?, N ?;
Resource ? R;

3

南通大学毕业设计(论文)

Weight ? ?i ?1 w?i ?
N

for each i,1 ? i ? N

d n ?i ? ? d ?i ? w?i ?;
end for; while ( Source ? ? ) Find source i with minimum d n in Source ; if ( dn ?i ? ? Resource Weight )
a?i ? ? d ?i ?;

then

Remove source i from Source ;

Resource? Resource? a?i ?;
Weight ? Weight ? w?i ?

else for each j ,1 ? j ? N if ( j ? Source ) then

a? j ? ? w? j ?? Resource Weight;
end if; end for;
Source? ? ;

end if; end while; return a ;

2.2 效用最大最小公平性
效用最大最小公平的概念类似于最大最小公平,在效用最大最小公平下每个用户都关 联一个效用函数[3],该效用函数通过每个得到公平分配的用户来完成。效用函数表明一个 用户得到一定数量的资源分配后的满意度,不同的用户可以有不同的效用函数[4]。以下是 一些常见的例子:
4

南通大学毕业设计(论文)

? 弹性流如电子邮件、Telnet、FTP 应用程序可能有一个凸效用。换句话说,只要分 配相对较少的资源效用函数就会快速的增长,而且当它达到某一点是就会饱和。 图 2.1(a)展示了这种类型的效用函数。 ? 实时流如视频和音频流有一个最低要求的分配资源。只有当满足这种最低要求时 这种类型的流的效用函数才会变大。另一方面,过度的增大资源分配不会显著的 使效用函数增大。总之,实时流的效用函数通常有一个阈值点对应最低要求,如 图 2.1(b)所示。 ? 自适应速率也有跟实时流类似的效用函数,除了效用分化在最低需求点要求更光 滑。换句话说,自适应速率流的效用函数有一个曲线拐点,如图 2.1(c)所示。

1

效 用

1

效 用

1

效 用

0 0 1

0 0 1

0 0 1

资 源

资 源

资 源

a

b

c

图 2.1 注意,对于一组用户 i,考虑到资源的总量为 R,需求向量为 ?d i ? ,权重向量为 ?wi ? 还有每 个用户的效用函数,分配向量 ?ai ? 由效用最大最小公平性表示为:

?ai ? ? FUMMF ?R; ?di ?; ?wi ??
这里每个用户的效用函数都包含在 FUMMF 函数中。

(2.2)

最大最小公平性可以看作是一种特殊情况下的效用最大最小公平性,所有的用户都有 相同的线性效用函数。

2.3 比例公平性
一些研究者指出最大最小公平性给予资源需求少的用户更多的优先权[5]。而比例公平
5

南通大学毕业设计(论文)

性的定义强调资源需求少的用户的优先权更低。 比例公平性定义为:假设用户 i 的资源分配为 a i ,相应的效用函数为资源分配的对数 函数,资源分配的目标是最大化所有用户总的效用 ?i ?1 log ai 。
N

资源分配矢量 ?ai ? 满足比例公平性准则,当且仅当对于其它任意可行的资源分配矢量

?ai?? ,总的比例变化是非正值,也就是说

?
i ?1

N

ai? ? ai ?0 ai

(2.3)

这里我们指的是一个可行的分配, 当且仅当, 共享资源总量不超出分配所需要的资源。 这公平准则意味着对数效用函数。 类似于最大最小公平和效用最大最小公平的情况,比例公平也决定如何分配共享资 源,考虑到资源总量为 R,需求向量为 ?d i ?和权重向量为 ?wi ? 。换句话说,比例公平也可以 表示如下:

?ai ? ? FPF ?R; ?di ?; ?wi ??
2.4 公平的一般概念

(2.4)

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

?ai ? ? F ?R; ?di ?; ?wi ??

(2.5)

其中 a i 是用户 i 的资源分配,它是由定义公平的函数 F 决定的,不同的公平准则有不 同的 F 函数。 你可能注意到在(2.2)式中效用函数并没有表示出来。然而, (2.2)式表示出一个可 以描述怎样分配的通用符号,只要有确定的需求向量,就可以决定每个用户的资源分配, 以便于分配所对应的效用满足于公平定义对应的效用。换句话说,式(2.2)把效用函数融
6

南通大学毕业设计(论文)

入到了公平概念中。例如,最大最小公平意味着线性效用函数,比例公平使用对数效用函 数,在效用最大最小公平,每个用户决定自己的效用函数。唯一的约束条件是相对于分配资 源的数量效用函数是非递减函数。 使用归一化的需求和分配可以等效的表示任何公平概念。定义用户 i 归一化的需求为
~ d i ,如下所示:

~ d di ? i R
用户 i 归一化的需求表明了用户的需求占总资源的百分比。定义用户 i 归一化的资源分配
~ ,如下所示: 为a i

~ ? ai a i R
用户 i 归一化的分配表明了用户的分配占总资源的百分比。 所以,给定归一化的需求向量 d i ,权重向量 ?wi ? ,任何给出的公平概念都可以用下面 的式子表示,

?~ ?

~ ~ ? ? F ?C; ?d ?a ; ?wi ?? i i?

(2.6)

其中 C 是影响整个系统的约束条件,后面详细介绍。注意式(2.6)中对于任何变量都 没有维度影响,因此,使它适用于有多个异构资源的系统。 约束 C 作为函数 F 的参数,因为考虑到相同的需求和权向量,在系统中不同的约束会 使公平分配不相同。约束 C 可以用来表示分配所达到的性能水平。例如,遵照最大最小公 平原则,即使没有资源分配给用户也可以认为这是一个公平分配,尽管它会导致极差的性 能。作为一个简单的例子,约束 C 可以表示所有用户的效用总和。 注意,在式(2.5)中资源总量也可以认为是在分配策略中的一个简单的约束:分配资 源的总量不能超过资源 R,也就是 ?i ai ? R 。所以,式(2.5)仅仅是式(2.6)的一种特 殊情况。根据上下文,我们可以使用这两个中的任何一个的公平概念。例如,在本论文, 当归一化没有必要时使用式(2.5),就像考虑缓冲资源一样,而当归一化是必要时用式(2.6), 比如在考虑处理资源时。 本章的内容主要介绍了一些对于单资源的公平分配策略,但是在实际当中,终端器件 往往都是含有多种资源的,这就需要我们寻找一种新的资源分配策略,下面我们就来介绍 一下多资源分配策略。

7

南通大学毕业设计(论文)

第三章
3.1 引言

支配资源的公平性(DRF)

在所有共享的计算机系统中,都有一个重要的的构建模块,那就是资源的合理分配。 迄今为止在已经研究出的分配策略中最受欢迎的是最大最小公平性,在系统中它会最大化 用户得到的最小分配。假如每一个用户都有足够的资源需求,这种策略会分配给每个用户 一份相等的共享资源。另外,现实中由于用户之间的重要性不同,又进一步的提出了加权 的最大最小公平性,这种方法使得用户获得的资源与他的权重成正比。 加权的最大最小公平性的魅力在于它的普遍性和它能够提供性能隔离的能力。加权的 最大最小公平性模型可以适用于各种各样的资源分配策略,包括基于优先级的分配,基于 预留的分配,和基于截止期限的分配[7]等。另外,加权的最大最小公平性能够确保隔离, 换句话说,就是能够保证一个用户收到他的那份资源,而不用考虑其他用户的需求。 鉴于这些特征,提出了许多算法以实现不同精确度的(加权的)最大最小公平性,例 如轮叫、比例资源共享[8]和加权公平队列[9]。这些算法已经被应用于各种不同的资源,例 如链路带宽[9-14]、CPU[7, 15, 16]、内存和存储。 目前在公平分配上已经做了大量地工作和实践,但是到现在为止主要还是集中在单资 源类型的环境下。甚至在多资源类型的环境下,用户具有异构的资源需求,典型的资源分 配的做法还是使用单类型资源抽象。比如 Hadoop 和 Dryad[17,
18]

,这两种广泛使用的集群

计算框架,它们的公平调度器在资源分配时使用插槽,所谓的插槽就是对节点资源按照固 定大小进行划分而产生的分区。然而实际上是集群中不同的任务对 CPU、内存和 IO 资源 有着不同的需求。 这篇文章里,在多种类型的资源环境下我们为有异构需求的用户解决公平分配问题。 尤其,我们提出支配资源的公平性(DRF) ,针对多资源推广最大最小公平性。DRF 背后 的直观理解是在多资源的环境下一个用户的分配应该由用户的支配份额决定,支配份额是 指在已经分配给用户的所有资源中,占据最大份额的一种资源。简单的说,DRF 力图最大 化所有用户的最小的支配份额。举个例子,假设 A 用户运行 CPU 密集的任务,B 用户运 行内存密集的任务,DRF 试图去均衡用户 A 的 CPU 分配和用户 B 的内存分配。在单资源 的情况下,DRF 退化为最大最小公平性。 DRF 的优点在于它所满足的特性。在单资源场景下,这些特性由最大最小公平性平凡 地满足,但是,在多资源场景下,这些特性都是不寻常的。四个这种类型的特性分别是激 励共享、 防止策略性操纵、 帕累托最优和无嫉妒性。 DRF 为用户提供激励机制去分配资源,
8

南通大学毕业设计(论文)

通过保证用户在系统中不会有多余的资源来达到这一目的。此外,DRF 是防止策略性操纵 的, 因为用户不可能通过谎报他的资源需求来获得更多的资源分配。 DRF 是帕累托最优的, 因为在满足其它特性的同时分配所有可用的资源, 而不会取代现存的资源分配。 最后, DRF 是无嫉妒的,没有用户更喜欢其他用户的资源分配。

3.2 动机
虽然早先关于加权最大最小公平性的工作都集中在单一资源的情况,但是云计算和多 核处理器的出现提高了对多资源和异构用户请求的环境下分配策略的需求。多资源意味着 不同种类型的资源,而不是同一种可互换资源的多个实例。 目前已有的集群公平调度器,例如 Quincy[17]和 Hadoop 公平调度器[18, 19]都忽视了异构 的用户需求和以插槽为粒度的资源分配,其中一个插槽就是一个节点上固定比例的资源。 这就导致了分配的效率很低,因为一个插槽对与任务的需求多半是一个不好的匹配。

1.0

集群任务需求

0.5

内存需求 CPU需求 0.0 0 1 2

插槽比

图 3.1 任务的需求与单位插槽的资源之比的概率分布 图 3.1 量化了 Hadoop MapReduce 公平调度器所提供的的公平性和隔离性的水平。该 图显示了任务的 CPU 需求和插槽的 CPU 份额之间的比率的概率分布图以及任务的内存需 求和插槽的内存份额之间的比率的概率分布图。 我们计算插槽内存和 CPU 的分配通过把总 的内存和 CPU 除以插槽的数量。 比值为 1 相当于任务的需求和插槽的资源完美的匹配, 比
9

南通大学毕业设计(论文)

值小于 1 相当于任务没有充分地利用插槽资源,比值大于 1 相当于任务已经过度的使用了 他们插槽的资源,这会导致系统起伏不定。图 3.1 表明绝大部分任务或者没有充分利用插 槽资源或者过载地利用插槽资源。修改每台机器的插槽数量并不能解决这个问题,因为这 样可能会导致更低的总利用率或者更多的任务因为过载而导致的性能不佳。

3.3 分配特性
现在我们将注意转向为多资源和异构请求的情况设计一个最大最小公平的分配策略。 为了说明这个问题,我们假设一个系统,包括 9 个 CPU 和 18GB 的 RAM,以及两个用户: 用户 A 的每个运行任务需要<1CPU,4GB RAM>,用户 B 的每个运行任务需要<3CPUs, 1GB RAM>。如何为这种情况建立一个公平的分配策略? 一种可能是把每种资源的一半分给每个用户。另一种可能就是均衡每个用户总的资源 分配。虽然想出各种各样可能的公平分配很简单,但是仍然不清楚怎样去评价和比较这些 分配方案。 为了应对这一挑战,我们先从一系列合理的特性开始,我们相信任何多资源的和异构 需求的资源分配都应该满足这些特性。然后,用这些属性引导公平分配策略的制定。我们 发现以下四个属性是重要的。 1、激励共享:相比专享自己的集群分区,通过共享集群每一个用户都应该更好。考 虑一个集群具有相同的节点和 n 个用户,一个用户不能在包含 1/n 资源的集群分区中分配 更多的任务。 2、防止策略性操纵:用户不应该能通过谎报资源需求得到益处。用户不能通过欺骗 来提高它的分配。 3、无嫉妒性:一个用户不应该更喜欢另一个用户的分配。这个特性包含了公平的概 念[20]。 4、帕累托最优:不可能在增加一个用户的分配的同时而不降低至少另一个用户的分 配。这个特性非常重要,因为它会使得在满足其它特性的同时最大化系统的利用率。 我们简单地评价一下防止策略性操纵和共享激励特性,我们相信这两个特性在数据中 心环境下特别重要。例如,yahoo 的一个 Hadoop MapReduce 集群对 map 和 reduce 任务有 不同的插槽。一个用户发现 Map 插槽存在竞争,因此就将他的所有任务都长期地运行在 Reduce 阶段,手工地执行本来应该在 Map 阶段执行地工作。另一个大型搜索公司为用户 高利用率的作业提供了专门的机器,这个公司马上就发现用户在他们的代码中散布无限循 环用于人为地提升利用率级别。
10

南通大学毕业设计(论文)

此外,任何满足激励共享特性的策略同样也提供性能隔离,因为它保证每个用户的最 小分配, (也就是说,一个用户不可能会比拥有 1/n 集群资源更差) ,不管其他用户的需求。 在单资源的情况下,最大最小公平性满足所有上述特性。然而,在多资源和异构用户 需求的情况下,获得这些特性是不简单的。例如,在微观经济学理论中首选的公平分配机 制 Competitive Equilibrium from Equal Incomes[20-22]不是防止策略性操纵的。 除了以上特性,我们还考虑了另外四种不错的特性: 1、Single resource fairness:对于单个资源,解决方案退化为最大最小公平性。 2、Bottleneck fairness:如果一种资源是紧缺的资源,那么解决方案退化为那种资源的 最大最小公平性。 3、Population monotonicity:当一个用户离开系统,并且放弃他的资源,其余用户的资 源分配都不会减少。 4、Resource monotonicity:如果更多的资源添加到系统中,现有用户的资源分配都不 会减少。

3.4 DRF
我们提出了支配资源公平性,一种针对多种资源类型的分配策略,满足前一章中的所 有四种特征。对于每个用户,DRF 会计算分配给用户的每一种资源的占有率,一个用户的 所有的占有率中的最大的就是那个用户的支配分配,和支配分配相对应的资源被称作支配 资源。不同的用户有不同的支配资源。举个例子,用户运行计算受限任务时用户的支配资 源是 CPU,而用户运行 I/O 受限任务时用户的支配资源是带宽。DRF 仅仅在用户的支配份 额之间使用最大最小公平,即 DRF 寻求最大化系统中最小的支配份额,然后是第二小的, 以此类推。 在这一节我们讨论有 n 个用户和 m 种资源的计算模型。每个用户都运行单个任务,每 个任务的特征是资源需求向量,需求向量指定了这个任务所需要的各种资源的值,比如 <1CPU,4GB RAM>。一般来说,任务都有不同的需求。 3.4.1 举例 考虑一个系统,包括 9 个 CPU 和 18GB RAM,还有两个用户,其中用户 A 运行的任 务的需求向量为 <1CPU,4GB RAM>,用户 B 运行的任务的需求向量为 <3CPUs , 1GB RAM>。

11

南通大学毕业设计(论文)

用户 A
1.00

用户 B
12GB

3CPUs

0.75

0.50

0.25

0.00 0

6CPUs
1

2GB
2

9CPUs

18GB RAM

图 3.2 用户的资源分配 在上述方案中,用户 A 的每个任务消耗总 CPU 的 1 9 和总内存的 2 9 ,所以用户 A 的 支配资源是内存;用户 B 的每个任务消耗总 CPU 的 1 3 和总内存的 1 18 ,所以用户 B 的支 配资源为 CPU。DRF 会均衡用户的支配分配,如图 3.2 所示,用户 A 的三个任务总共消耗 了<3CPUs,12GB RAM>,用户 B 的两个任务总共消耗了<6CPUs,2GB RAM>;在这个分 配中,每个用户在结束后都会得到相同的支配分配,用户 A 获得了 2 3 的 RAM,而用户 B 获得了 2 3 的 CPU。 这个分配可以用下面的数学方法计算出来:x 和 y 分别是 DRF 分配给用户 A 和用户 B 的任务数目,然后用户 A 消耗了< x CPU, 4 x GB RAM>,用户 B 消耗了< 3 y CPU, y GB RAM>,在图 3.2 中用户 A 和用户 B 消耗了同等支配资源;用户 A 的支配占有率为 4 x 18 , 用户 B 的支配占有率为 3 y 9 。所以 DRF 分配可以通过求解以下的优化问题来得到:

max(x, y )
Subject to

(最大化分配)

x ? 3y ? 9

(CPU 约束)
12

南通大学毕业设计(论文)

4 x ? y ? 18

(内存约束) (支配占有率相等)

2x y ? 9 3

求解以上问题,可以得出 x ? 3 以及 y ? 2 。因而用户 A 获得<3CPUs,12GB RAM>,B 得到<6CPUs,2GB RAM>。 需要注意的是,DRF 并不是总需要使用户的支配占有率相等。当一个用户总的需求已 经被满足,那么用户就不再需要更多的任务,因此剩余的资源就会分配给其他用户,就好 像最大最小公平性。另外,如果一种资源被用完,那么不需要这种资源的用户仍然可以继 续接收更多其他类型的资源分配。

3.4.2 DRF 调度算法
算法 1 表明了 DRF 调度的伪代码, 这个算法会跟踪计算分配给每个用户的总资源和用 户的支配分配, si 。每一步,DRF 都会从准备运行任务的用户中挑选出支配分配最低的一 个用户。 算法 1:

R ? r1 ,?, rm
C ? c1 ,?, cm

//资源总量// //消耗的资源量,初值为 0// //用户 i 的支配占有率,初值为 0// //分配给用户 i 的资源,初值为 0//

si (i ? 1? n)

U i ? ui ,1 ,? , ui ,m (i ? 1? n)

找出支配占有率 si 最低的用户 i
Di ? 用户 i 下一个任务的需求

if C ? Di ? R then
C ? C ? Di U i ? U i ? Di

//更新消耗矢量// //更新用户 i 的分配矢量//

si ? maxm ui, j rj ? j ?1?
else return end if //资源已满//

13

南通大学毕业设计(论文)

如果那个用户的任务需求能被满足,即系统中有足够可用的资源,那么用户的任务就会被 启动。我们将其一般化,即一个用户拥有不同需求向量的任务,我们用变量 Di 来表示用户

i 下一个想要运行加载的任务的需求向量。为了简单化,伪代码没有捕获任务结束事件,
在这种情况下,用户会释放任务的资源,DRF 会再一次选择拥有最低支配分配的用户去运 行他的任务。 调度 用户 B 用户 A 用户 A 用户 B 用户 A 用户 A 当前分配 <0,0> <1/9,4/18> <2/9,8/18> <2/9,8/18> <3/9,12/18> 主导分配 0 2/9 4/9 4/9 2/3 用户 B 当前分配 <3/9,1/18> <3/9,1/18> <3/9,1/18> <6/9,2/18> <6/9,2/18> 表一 注意 3.4.1 节的两个简单例子,表一为这个简单的例子阐明了 DRF 的分配过程。DRF 首先选择用户 B 来运行一个任务,然后用户 B 的资源占用率变为 3 9,1 18 ,用户 B 的 支配占有率变成了 max 3 9,1 18 = 1 3 。接下来 DRF 选择用户 A,因为此时用户 A 的支 配占有率为 0。这个将会过程持续进行到不可能再运行任务新的任务,在这种情况下,出 现 CPU 一出现饱和就会停止。 在以上分配结束后, 用户 A 会得到<3CPUs, 12GB RAM>, 同时用户 B 会得到<6CPUs, 2GB RAM>,也就是说,每一个用户都获得了 2/3 的支配资源。 注意到,在这个例子中,任何资源只要达到饱和,那么分配就会停止。但是一般情况 下,尽管有些资源已经饱和了,也有可能继续分配资源给任务, ,因为有些任务对已经饱 和的资源没有需求。 3.4.3 加权 DRF 实际上,许多种情况下,均衡地在用户之间分配资源的策略并不能让人满意。实际上 我们可能想要分配更多的资源给运行重要任务的用户,或者给为集群贡献出更多资源的用 户。为了达到这个目的,我们提出了加权 DRF,一个概括了 DRF 和加权最大最小公平性 的算法。 在加权 DRF 中,每个用户 i 都关联着一个权重向量 Wi ? ? Wi1 ,Wi 2 ,?,Wim ?,其中 W ij 表
14

主导分配 1/3 1/3 1/3 2/3 2/3 3/9 4/9 5/9 8/9 1 1/18 5/18 9/19 10/18 14/18

CPU 总量

内存总量

南通大学毕业设计(论文)

示用户 i 对资源 j 的权重。 那么用户 i 的支配占有率的定义变成了 Si ? max? 其中 U ij Uij Wij ?, 是用户 i 对资源 j 的占有率。特别的当所有用户 i 的权重都相等的时候,也就是说 wij ? wi ,

?1 ?

j ? m? ,在这种情况下,用户 i 的支配占有率就变为 wi ? w j 。如果所有用户的权重都设

置为 1,那么加权 DRF 就退化为 DRF。

3.5 公平分配策略的替代
定义一个公平分配在多资源的系统中不是一个简单的问题,因为公平概念本身就是值 得我们去讨论的。在我们的努力下,在使用 DRF 之前我们考虑过许多分配策略,但只有 DRF 能满足所有四个属性:激励共享、防止策略性操纵、帕累托最优、无嫉妒性。 在本节中,我们将列出两种已经调查过的方案:资产公平性,一种简单而直观的策略, 它的目的是为了均衡每个用户得到的总计资源数;以及 Competitive Equilibrium from Equal Incomes(CEEI),这种策略被用在微观经济领域中公平的配置资源。下面我们会将这些策略 与 DRF 进行比较。 3.5.1 资产公平 资产公平性背后的理念是不同资源的占有率相等,那么它们的价值也相等,比如所有 CPUs 的 1%,所有 RAM 的 1%,以及所有 I/O 带宽的 1%它们的价值相等。资产公平性试 图使得每个用户得到的总资源的价值相等。特别地,资产公平性会计算每个用户 i 的总的 资源分配 xi ? ? j Si , j ,其中 Si , j 是资源 j 分配给用户 i 的量。然后在用户的总占用率上使用 最大最小公平性,比如它会多次的为有最小总资源占有率的用户发出任务。 考虑第 3.4.1 节中的例子,系统拥有 9 个 CPU 和 18GB 的 RAM,既然 RAM 的 GB 数 量是 CPU 数量的两倍,一个 CPU 的价值相当于 2GB 的 RAM 的价值。假设 1GB 的 RAM 的价值为?1,那么 1 个 CPU 的价值为?2,那么接下来用户 A 需要为每个任务花费?6,而 用户 B 需要我每个任务花费?7。设置 x 和 y 分别为资产公平性算法分配给用户 A 和用户 B 的任务数量。然后资产公平分配可以通过求解以下问题来得到:
max?x, y ?

subject to
x ? 3y ? 9 4 x ? y ? 18
6x ? 7 y
15

南通大学毕业设计(论文)

求解上面这个问题, 可以得到 x ? 2.52 , 以及 y ? 2.16 ,。 因此, 用户 A 得到了<2.5 CPUs, 10.1GB RAM>,而用户 B 得到了<6.5CPUs,2.2 GB RAM>。 这个分配策略的简单性很吸引人,但它有一个重大的缺陷:它违反了激励共享特性。 资产公平性可以导致一个用户获取了小于总资源的 1/n 的资源,其中 n 为总的用户数目。 3.5.2 CEEI 在微观经济理论中,公平分配资源优先选择的方法是 Competitive Equilibrium from Equal Incomes(CEEI),在 CEEI 中,每个用户最初接收到所有资源的 1/n,接下来每个用户 会在一个完全竞争的市场与其他用户交易资源。CEEI 的输出同时满足无嫉妒性和帕累托 最优。 更加精准描述是:CEEI 分配是由 Nash bargaining solution#给出的,Nash bargaining solution 会选择可行的分配策略,使得 ?i ui ?ai ? 最大化,其中 ui ?ai ? 是用户 i 获取资源 a i 的 方式或功能,为了简化对比,我们将一个用户得到其资源分配的方式简化为就是其支配分 配, S i 。 考虑第 3.4.1 节两用户的例子,回忆一下用户 A 的支配分配为 4x/18 = 2x/9,而用户 B 的支配分配为 3y/9 = y/3。其中 x 为用户 A 的任务数目, y 为用户 B 的任务数目。最大化 支配分配的结果就等同于最大化 x ? y 的结果。因此,CEEI 的目的在于解决如下的优化问 题:
max?x, y ?

subject to
x ? 3y ? 9 4 x ? y ? 18

解决以上问题得到 x ? 45 11, y ? 18 11 。因而用户 A 获得了<4.1 CPUs, 16.4 GB RAM>,同时用户 B 获得了<4.9 CPUs, 1.6GB RAM>。 很遗憾,虽然 CEEI 同时满足无嫉妒性和帕累托最优,但是它不是防止策略操纵的, 因此用户可以通过谎报他们的资源需求来提高他们的分配。 3.5.3 与 DRF 比较 为了给读者对资产公平和 CEEI 呈现一个直观的理解,我们在下图中,将三种算法资 源分配进行对比。
16

南通大学毕业设计(论文)

用户 A

用户 B

1.00

1.00

1.00

0.75

0.75

0.75

0.50

0.50

0.50

0.25

0.25

0.25

0.00 0.0 0.5 1.0

0.00 0.0 0.5 1.0

0.00 0.0 0.5 1.0

(a)DRF

(b)Asset Fairness

(c)CEEI

图 3.3 资源分配对比 我们看 DRF 使得用户的支配分配趋于均衡, 比如, 用户 A 的内存分配和用户 B 的 CPU 分配。相比之下,资产公平使得用户的总资源分配的百分比趋于均衡。最后,因为 CEEI 假设有一个完全竞争性市场,它找到了一个满足市场结清的解决方案,使得当中所有的资 源都已经得到分配,遗憾的是这个精确的特性可能会欺骗 CEEI:用户可以宣称她需要更 多地未充分利用的资源,导致 CEEI 给予这个用户更多的任务以便于达到市场结清。

17

南通大学毕业设计(论文)

第四章

总结与展望

我们已经介绍了支配资源公平(DRF),一个公平的共享模型,概括了对多资源类型的 最大最小公平。DRF 允许集群调度考虑异构数据中心应用程序的要求,导致了比现存的分 配相同的资源片(槽)给所有任务的解决方案更加公平的分配和更高的效用。DRF 满足许多 可取的属性。特别是,DRF 的防止策略性操纵的属性,他能够督促用户更加准确的报告他 们的需求。DRF 还鼓励用户共享资源。从我们调查了的其他调度器,以及从微观经济文献 中选择的公平概念都无法满足所有的这些属性。 我们已经通过在 Mesos 资源管理器中运行来评估 DRF, 结果表明它能使系统的整体性 能优于如今经常使用的基于插槽的公平调度器。 对于未来的研究我们也有一些方向。首先,离散任务在集群环境中,一个有意义的问 题是如何在不影响公平的情况下减少资源的分散。这个问题类似于 bin-packing,但是其中 的一个必须尽可能包含更多的任务来满足 DRF。 第二个方向是当任务有了位置约束是怎样 定义公平,如机器的参数设置。鉴于当前多核机器的趋势,第三个研究方向是探索怎样把 DRF 当作操作系统的调度器。最后,从微观经济的角度来看,一个自然的方向是探究 DRF 是否是唯一的满足防止策略性操纵的多资源分配方案,还有其他的属性是否也是惟一的。

18

南通大学毕业设计(论文)

参考文献
[1] Bertsekas D, Gallager R. Data Networks, 2 nd[Z]. Prentice Hall, 1991. [2] Kesahv S, Keshav S, Keshav S. Engineering Approach to Computer Networking: ATM Networks, the Internet, and the Telephone Network[Z]. Addison-Wesley Professional, 1997. [3] Cao Z, Zegura E W. Utility max-min: An application-oriented bandwidth allocation scheme[C]. IEEE, 1999. [4] Shenker S. Fundamental design issues for the future Internet[J]. Selected Areas in Communications, IEEE Journal on. 1995, 13(7): 1176-1188. [5] Kelly F. Charging and rate control for elastic traffic[J]. European transactions on Telecommunications. 1997, 8(1): 33-37. [6] Blake S, Black D, Carlson M, et al. An architecture for differentiated services[J]. 1998. [7] Waldspurger C A, Weihl W E. Stride scheduling: Deterministic proportional-share resource management[R]. 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 management[C]. USENIX Association, 1994. [9] Demers A, Keshav S, Shenker S. Analysis and simulation of a fair queueing algorithm[C]. ACM, 1989. [10] Isard M, Prabhakaran V, Currey J, et al. Quincy: fair scheduling for distributed computing clusters[C]. ACM, 2009. [11] Zaharia M, Borthakur D, Sen Sarma J, et al. Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling[C]. ACM, 2010. [12] Foley D K. Resource allocation and the public sector[J]. YALE ECON ESSAYS, VOL 7, NO 1, PP 45-98, SPRING 1967. 7 FIG, 13 REF. 1967. [13] Varian H R. Equity, envy, and efficiency[J]. Journal of economic theory. 1974, 9(1): 63-91. [14] Moulin H. Fair division and collective welfare[M]. MIT press, 2004. [15] Young H P. Equity: in theory and practice[M]. Princeton University Press, 1995. [16] Nash Jr J F. The bargaining problem[J]. Econometrica: Journal of the Econometric Society. 1950: 155-162. [17] Bennett J C, Zhang H. WF 2 Q: Worst-case fair weighted fair queueing[C]. IEEE, 1996. [18] Goyal P, Vin H M, Chen H. Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks[C]. ACM, 1996. [19] Parekh A K, Gallager R G. A generalized processor sharing approach to flow control in integrated services networks: the single-node case[J]. IEEE/ACM Transactions on Networking (ToN). 1993, 1(3): 344-357. [20] Shreedhar M, Varghese G. Efficient fair queuing using deficit round-robin[J]. Networking, IEEE/ACM Transactions on. 1996, 4(3): 375-385. [21] Stoica I, Shenker S, Zhang H. Core-stateless fair queueing: Achieving approximately fair bandwidth
19

南通大学毕业设计(论文)

allocations in high speed networks[M]. ACM, 1998. [22] Caprita B, Chan W C, Nieh J, et al. Group Ratio Round-Robin: O (1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems.[C]. 2005. [23] Stoica I, Abdel-Wahab H, Jeffay K, et al. A proportional share resource allocation algorithm for real-time, time-shared systems[C]. IEEE, 1996.

20

南通大学毕业设计(论文)





在本科生学习阶段即将结束之际,我首先向我的导师表示诚挚的感谢,从论文的选题、 撰写、修改到定稿,都凝聚了他们的心血。陈老师半年来的悉心指导和帮助让我终身难忘, 他渊博的学识、睿智深邃的研究风格、认真负责的态度和爽朗乐观的性格,是我永远学习 的榜样。陈老师学识渊博、谦虚谨慎、工作勤恳,给我留下了深刻的印象。陈老师的人格 魅力、学术修养、勤奋的作风和坚持的精神使我受益匪浅。我所取得的每一点成绩,都与 他们的精心指导息息相关。借此机会,老师表示最衷心的感谢和敬意! 最后,感谢这样一段话“目标的坚定是性格中最必要的力量源泉之一,也是成功的利 器之一。没有它,天才也会在矛盾无定的迷径中,徒劳无功。 ” (查士德婓尔)

21


相关文章:
毕业论文 基于QT的嵌入式终端应用
毕业论文 基于QT的嵌入式终端应用_IT/计算机_专业资料...的桌面计算,定制非常方便并且支持大多数嵌 入式系统...(2)联网成为必然趋势 为适应嵌入式分布处理结构和...
嵌入式论文
3 嵌入式系统 4.精简系统内核、算法,降低功耗和软...X 终端、I/O 系统等 5.嵌入式系统的图形用户接口...占用资源少、高性能、高可靠性、便于移植、 可配置...
嵌入式系统及其应用论文
嵌入式系统及其应用论文_工学_高等教育_教育专区。嵌入...的各个领域,如信息家、工业控制、通信和智能终端。...4)系统内核、算法精简化,降低系统功耗和软硬件成本 ...
arm嵌入式.经典论文
arm嵌入式.经典论文_计算机软件及应用_IT/计算机_...4.嵌入式系统的应用 以往的家庭智能终端绝大多数是...负责嵌入式系统的全部软、硬件资源分配、调度 工作...
嵌入式小论文(嵌入式在智能家居中的应用)
嵌入式系统课程小论文嵌入式系统设计》 课程小...4.嵌入式系统的应用 以往的家庭智能终端绝大多数是...负责嵌入式系统的全部软、硬件资源分配、调度工作,...
嵌入式方向本科毕业论文题目_图文
嵌入式方向本科毕业论文题目_工学_高等教育_教育专区...参数监测终端设计 基于GPRS的远程心电监护终端设计 ...网格环境中的任务调度算法研究 基于密罐技术的入侵...
浅谈嵌入式计算
计算机概论课论文 浅谈嵌入式计算摘要:本文综述了嵌入...工程 应用等方面进行深层次的开发研究,也需要传统...该系统由前台移动终端、后 台同步服务器组成,移动...
嵌入式期末论文
嵌入式期末论文_工学_高等教育_教育专区。嵌入式...请详细分析程序,解释算法计算过程和程序的功能,并...3.运行与中断源相对应的终端服务程序。首先清除中断...
嵌入式Linux论文(历史发展分类及应用)
嵌入式Linux论文(历史发展分类及应用)_计算机软件及应用...无所不在的网络和无所不在的计算( everything ...在 WINDOWS 下的超级终端配置也是这样。 MINICOM ...
基于嵌入式系统的寄存器分配的混合进化算法的解决方案...
基于嵌入式系统的寄存器分配的混合进化算法的解决方案大学毕业论文外文文献翻译及原文_高等教育_教育专区。毕业设计(论文) 外文文献翻译 文献、资料中文题目:基于嵌入式...
更多相关标签: