云计算资源提供商可以将云计算资源动态地提供给用户使用，由于其可靠性和方便的特点，目前大量的企业和个人都倾向于将计算和存储任务提交到云平台上执行.如何提高资源利用率，无论从高效或者降低成本的角度来说，对于用户和资源提供商都是当前关注的重点.资源共享方式[1]，是一种非常有效的提高资源利用率的方法，系统通过云计算虚拟化技术将计算资源整合，实现资源共享功能，如Mesos[2]和Hadoop Yarn[3]等.在资源共享系统中，如何保证在用户间公平高效地分配资源是需要解决的关键问题.
目前，对于多种资源分配机制的公平性和高效性主要由经济学中一些属性来定义.
1) 激励共享[4].系统中所有用户在共享情形下由机制分配的资源量不小于其在独自占有资源情形下获得的资源量.
2) 帕累托最优[4].系统中任意一个用户在分配机制中获得比原来更多资源时，至少有另外一个用户将受到损失.
3) 无嫉妒[5].系统中没有任何用户嫉妒其他用户所分配的任意一种资源.
4) 可信[5].系统中任何谎报任务资源需求的用户将不会获得更多的资源.
目前，占优资源公平分配机制(dominant resource fairness, DRF)[6]被广泛用于Mesos和Hadoop Yarn等云计算系统中.DRF计算用户任务所需的每种资源累计分配量占系统中该资源总量的比值，所有资源中比值最大的那种资源为占优资源(dominant resource, DR),与其相对应的比值为占优份额(dominant share，DS).DRF机制的基本思想是使所有用户中占优资源份额最小的用户所分得的资源尽可能大.该机制能够在多资源并存情形下保证分配的公平.然而，DRF机制是基于资源由第三方提供分配，在实际资源共享系统中，每个用户对资源的共享量可能不同，共享资源多的往往期望得到更多的资源.
文献[7]针对动态情形下资源分配公平性和效率做出了改进，允许用户随时进入系统但不离开系统，假设每个用户的任务数是无限的，并未考虑实际环境中用户任务数是有限的情形；文献[8]在DRF机制的基础上提出了一种解决动态情形下资源分配的机制，即动态占优资源公平分配机制(dynamic dominant resource fairness mechanism, DDRF)，并给出了求解DDRF机制的一种线性多项式时间算法，该算法在动态资源分配中有很好的效果，但未考虑异构云计算环境下资源分配的问题；文献[9]针对系统中具有多个异构虚拟机的资源分配问题提出了面向异构云计算系统占优资源公平分配机制(dynamic dominant resource fairness mechanism in heterogeneous cloud computing system, DRFH)，该机制利用全局占优资源份额公平[9]的概念对具有异构虚拟机的云计算资源系统进行资源分配，该机制假设用户任务数没有上限，并未考虑用户具有有限任务数的情形；针对用户有限任务数的资源分配问题，文献[10]提出了一种资源分配机制，考虑了在动态情形下用户具有有限个任务数需求的资源分配问题；文献[11]提出了多种启发式资源分配算法，在异构资源分配情形下取得了较好效果，但算法未考虑资源共享情形下用户具有多组资源需求的情形.针对用户具有多组资源需求的动态资源分配情形，文献[12]设计了一种启发式算法，提出了资源共享公平概念,解决了用户具有多组任务需求的问题，但是该文并未考虑系统具有多个异构的虚拟机，用户在不同时刻每个任务所需资源不同的情形.
综上，在多种共享虚拟资源分配的问题上，目前的研究已经取得了许多积极的成果，但是在考虑用户共享资源[1-2]，用户在不同时刻有不同的任务需求和有限的任务数情形下，用户贡献资源与分配资源的公平性问题上仍然面临挑战.本文研究一种公平的多资源动态分配机制，旨在解决用户在不同时刻具有多组有限时变任务需求情形下云计算资源共享系统的资源分配问题.本文具体包括2方面研究:
1) 多资源动态分配机制设计.动态情形下，用户可提出多组有限时变多资源的任务需求，较其他分配机制，可使得用户在多组时变需求情形下，满足共享资源量与分配的资源量公平性，为云计算资源动态分配问题提出了更现实的解决方案.
2) 多资源分配算法设计.结合字典序最优[13]的概念，提出了合理的资源分配模型以满足动态云计算资源分配场景，设计了启发式的资源分配算法，解决了共享资源系统中共享公平性问题.
理论和实验表明：本文提出的方法解决了云计算共享资源系统中用户多组时变任务需求的多资源公平分配问题.
1 问题描述及模型定义
1.1 问题描述
在云计算资源共享系统[12]中，用户将服务器资源共享到云计算虚拟机集群中，用户有任务需求时，系统再将资源分配给用户以达到更高的资源利用率.用户任务的资源请求是由具有不同资源配置的虚拟机进行响应.用户任务的资源分配过程为虚拟机资源调度过程.
假定云计算资源共享系统中共有m种云计算资源，如CPU、内存、硬盘等.云计算虚拟机集群中包含K个虚拟机，虚拟机的集合为S={1,2,…,K}.其中，第k个虚拟机的资源容量为向量
云计算虚拟机集群中资源总量为向量
令U={1,2,…,n}表示云计算用户的集合.所有虚拟机中的云计算资源均为用户按照一定比例贡献的，我们称之为资源共享.为了方便起见,令ωi表示第i个用户在云计算资源共享系统中对每种资源的共享比例，当系统有n个用户时，有
根据文献[12],令用户i在第k个虚拟机中资源贡献为向量
为用户i在所有虚拟机中的资源贡献向量.
文献[13]假定用户需求的任务数在不同时刻是有限的，用户i在时刻t需求任务数上限为Bi(t).与文献[13]不同的是，本文假定每个用户在不同时刻的任务资源需求是不相同的.令:
αi(t)=(αi1(t),αi2(t),…,αim(t))，
为用户i在时刻t的每个任务所需资源向量，其中αij(t)表示用户i在时刻t的每个任务对第j种资源的需求量.对于任意一个用户i∈U，令i在时刻t的最大任务资源需求为向量
Di(t)=(Di1(t),Di2(t),…,Dim(t))，
其中,Dij(t)=αij(t)·Bi(t)表示在时刻t用户i的任务对第j种资源的最大需求量.方便起见，对于任意用户i∈U和任意资源j(1≤j≤m)，令Dij(t)>0，任务执行时长为单位时长.
令
为第k个虚拟机在时刻t分配给用户i的资源向量，其中
为第k个虚拟机在时刻t分配给用户i的第j种资源量.
为用户i在时刻t所有虚拟机分配到的资源向量.
为系统在时刻t分配给所有用户的资源向量.当
∀t,k∈S,1≤j≤m成立时，我们称分配U(t)可行.
对任意用户i∈U在时刻t的资源分配向量U(t)已知情形下，用户i在时刻t在虚拟机k上能执行的最大任务数为
(1)
用户i在时刻t能执行的最大任务数为
(2)
对于任意用户i和虚拟机k，若对于任意可行的分配
且存在至少一种资源s，有
有
(3)
成立，则称
为不浪费分配，即减少任何种资源的分配，用户i在虚拟机k上能执行的最大任务数将减少.对于云计算资源共享系统中任一个虚拟机k∈S,若都是不浪费分配，则称Ui(t)为不浪费分配.同理，系统中所有用户i∈U，若Ui(t)都是不浪费分配，则称U(t)为不浪费分配.若不特别指出，本文研究的云计算资源分配是不浪费的情形.
根据文献[14]可知,用户完成的任务数跟其任务需求中的占优资源有关，令:
(4)
为任意一个用户i∈U，在时刻t每个任务中资源需求量占总资源容量比例最大值，我们定义用户i到时刻t为止的累计带权全局占优资源份额为
(5)
其中:
为用户i到时刻t为止在虚拟机k上所分得的累计带权的全局占优资源份额.为了方便起见，我们将累计带权的全局占优资源份额简称为累计全局占优资源份额.
1.2 资源共享公平定义
在云计算资源共享系统中，在时刻t系统的任意虚拟机k上分配给用户i的任意一种资源j(1≤j≤m)的资源量可能不等于用户的贡献资源量
相反，在不共享资源的系统中，因为没有资源竞争，所以时刻t用户i分配到资源量为
根据文献[12]，定义用户i的第j种资源在t时刻第k个虚拟机上的共享系数为
(6)
在时刻t用户i的第j种资源在所有虚拟机全局共享系数为
(7)
根据文献[14],由于在多种资源分配中，用户分得的资源所能执行的任务数由其占优资源决定，定义用户i在时刻t的全局共享系数为
(8)
在共享资源情形中，βi>1表示i用户完成的任务数比不共享资源情形多，称为共享受益;βi<1表示表示i用户完成的任务数比不共享资源情形少，称为共享缺损;βi=1表示i用户完成的任务数与不共享资源情形相同.为了使用户在共享资源的情形下执行的任务数不小于不共享情形，必有βi≥1.
1.3 资源动态分配公平性质
在云计算资源共享系统中，资源分配的公平性是非常关键的.只有当每个系统中用户能够公平分配到资源时，多资源共享分配才可行.文献[4]中引入了4个重要属性：激励共享、帕累托最优、无嫉妒、可信.下面结合本文所研究用户具有时变有限任务资源需求的情形，将上述公平性进行描述.
1.3.1 激励共享
系统中对于任意一个用户i∈U.在任意一个时刻t有βi(t)≥1.即系统中所有用户在共享情形下获得资源量不小于其在独自占有资源情形获得资源量，则认为该机制满足激励共享属性.
1.3.2 帕累托最优
系统中若时刻t存在一种可行资源分配方案U(t),若存在另一种可行资源分配方案U′(t)，对于任意一个用户i∈U，若有Ni(U′(t))>Ni(U(t))成立，那么将存在至少另一个用户h≠i,使得
成立.
1.3.3 无嫉妒
若用户i∈U到时刻t由分配机制分配的资源为向量Ui(t).首先，当用户完成累计任务数达到其累计需求任务数上限，即:
则用户i不会嫉妒其他用户.
其次，当用户完成累计任务数小于其累计需求任务数上限时，即:
用户h≠i在时刻t由分配机制分配的资源为Uh(t),当至少存在一种资源j(1≤j≤m),到时刻t为止用户i累计分配的第j种资源与共享权重之比不比用户h所分配的少，即:
满足时，称资源分配机制满足无嫉妒属性.
1.3.4 可信
用户不能通过谎报资源需求来获得执行任务所需要的更多资源.令系统中的用户i∈U在时刻t谎报的每个任务的资源需求为向量
且
其他系统用户提交真实需求，此时用户i获得资源量为
完成任务数为
令所有用户都不谎报真实资源需求情形下用户i获得资源量为Ui(t),完成任务数为Ni(Ui(t))，有
成立.
2 TV-DRF机制设计
本文设计一种针对用户在不同时刻提出有限时变资源需求的无浪费资源公平 (time varied-DRF, TV-DRF) 分配机制.由于资源的有限性，如何设计分配机制使资源能够公平地分配是一个难点，根据文献[13]，字典序最大最小公平分配策略是一种较好的满足任务数和资源数都有限情形下的分配策略:
令G(t)=(G1(t),G2(t),…,Gn(t))为时刻t系统中所有用户累计全局占优资源份额向量.根据文献[13]，结合本文我们得出累计全局占优资源份额向量满足字典序最大最小最优的定义：
定义1. 若对于任意可行的累计全局占优资源份额向量
当G(t)与G′(t)按照递增排序排列为向量Gτ(t)与
其中Gτ(t)按照字典序大于
时, 则称向量G(t)为字典序最大最小最优(lexicographically max-min optimal, LMM-optimal),简称字典序最优.例如，对于2个累计全局占优资源份额向量
G(t)=(1.0,0.2,0.6)，
G′(t)=(0.6,0.3,0.4)，
按递增排列为
Gτ(t)按照字典序小于
所以G(t)不是字典序最优.TV-DRF机制形式化表述为
max Gτ(t),
(9)
βi(t)≥1,∀t,i∈U.
Gτ(t)表示在分配Ui(t)已知情形下任意时刻t累计全局占优资源份额向量的递增排序.式(9)目标函数是指当所分配资源使用户累计全局累计占优资源份额向量G(t)满足字典序最优.式(9)第1个约束条件表示在时刻t所有用户在任意1台虚拟机分得的资源量不能超过该虚拟机的资源总量，第2个约束条件是指分配机制保证所有用户不发生共享缺损.
因为用户i在时刻t的最大需求任务数具有上限值为Bi(t)，所以根据式(5)可得用户i在时刻t累计全局累计占优资源份额最大值为
根据文献[13],在时刻t对于任意一个非负数G(t)>0,令A(G(t))=(G1(t),G2(t),…,Gn(t))为用户累计全局占优资源份额向量，其中:
引理1. 在时刻t存在一个非负数
使
为字典序最优.
证明. 令
为字典序最优的累计全局占优资源份额向量，其中:
假设有一个用户k∈U在时刻t的累计全局占优资源份额为
则有
且
令用户h,h≠k在时刻t的累计全局占优资源份额为
根据式(5)可知，则至少存在一个时刻s∈[0,t]，对于用户k,有
我们在时刻s使用户h释放足够小的资源给用户k，从而构造一个新的可行累计全局占优资源份额向量
其中:
由于G′(t)为一个可行的累计全局占优资源份额向量，可得:
且有:
这与
为字典序最优累计全局占优资源份额向量矛盾, 即在时刻t存在一个非负数
使
为字典序最优.
证毕.
引理2. 若用户k到时刻t分配资源所完成累计任务数小于时刻t累计提交任务需求上限，即:
成立时，字典序最优累计全局占优资源份额向量G*(t)中用户k累计全局占优资源份额大于或等于所有用户累计全局占优资源份额,即:
证明. 因为
则至少存在一个时刻
假设存在一个用户h≠k满足
则根据引理1可以在时刻s使用户h释放足够小的资源给用户k构造一个可行的累计全局占优资源份额向量G′(t)满足:
且
这与G*(t)为字典序最优累计全局占优资源份额向量矛盾.
证毕.
引理3. 如果有一个用户i∈U在时刻t由TV-DRF机制分配的资源可执行的任务数小于任务数需求上限，即
则此时所有虚拟机中至少有一种资源被消耗完.
证明. 假设在时刻t当
时，所有虚拟机没有任何一种资源被消耗完,则至少存在一个虚拟机k,在不减少k上其他用户分配资源条件下，可以使用户i执行更多的任务，从而得到相应的时刻t的分配资源向量为
其中:
其中:
根据式(5)，我们可以得到时刻t新的累计全局占优资源份额向量
其中:
由式(5)可得:
而
所以
字典序大于
与G*(t)是字典序最优矛盾.这就是说在时刻t当
时,所有虚拟机中至少有一种资源被消耗完.
证毕.
定理1. 当系统中有n个用户、K个虚拟机时，TV-DRF机制所满足激励共享属性.
证明. 若到任意时刻t为止，使任意一个用户i∈U分得的累计资源量为其独有的资源量时，有βi(t)=1.这就是说在任意时刻t,对于任意一个用户i∈U而言，有使βi(t)≥1的分配是存在.从而有，到任意t时刻为止,TV-DRF机制使所有用户全局共享系数均大于等于1的分配也是存在的，即βi(t)≥1,∀t,i∈U.所以TV-DRF机制满足激励共享属性.
证毕.
定理2. 当系统中有n个用户、K个虚拟机时， TV-DRF机制满足帕累托最优属性.
证明. 若假设TV-DRF机制在时刻t所得分配U(t)不满足帕累托最优属性，即U(t)不满足帕累托最优属性.存在其他可行分配至少存在一个用户i∈U存在一个足够小的正数δ，使：
且不会使其他用户最大可执行任务减少，相应地，根据式(5)可得新的时刻t累计全局累计占优资源份额向量为
其中，
且
显然字典序大于Gτ(t),这与G(t)为字典序最大最小最优矛盾，所以TV-DRF机制满足帕累托最优属性.
证毕.
定理3. 当系统中有n个用户、K个虚拟机时，TV-DRF机制满足无嫉妒属性.
证明. 首先，对于系统任意一个用户i∈U若在时刻t有
则用户i在时刻t将不嫉妒其他用户.若在时刻t有:
由引理2可得有
假设如果用户i在时刻t嫉妒用户h,h≠i.根据无嫉妒定义，用户h到时刻t分得的所有种资源累计量与共享权重之比都大于用户i到时刻t分得的所有种资源累计量与共享权重之比
根据式(4)可得:
根据式(5)可得:
根据引理2可知，
即:
上式矛盾，所以TV-DRF机制满足无嫉妒属性.
证毕.
定理4. 当系统中有n个用户、K个虚拟机时，TV-DRF机制满足可信性.
证明. 令
为在时刻t用户i谎报单个任务资源需求且除了用户i外其他用户都提交真实任务资源需求
情形下, TV-DRF机制所得的资源分配向量.U(t)为在时刻t所有用户都没有谎报需求情形下，TV-DRF机制所得的资源分配向量，对应的用户字典序最优累计全局占优资源份额向量为G*(t),在时刻t用户所能完成的任务数为
若到时刻t为止用户i累计完成任务数达到提交任务数上限，即:
则用户i在任何时刻谎报资源需求也不会增加其效用.所以，我们考虑用户i累计完成任务数没有达到提交任务数上限情形，即：
根据引理2可得:
(10)
根据式(1)～(5),TV-DRF机制所得用户i在时刻t谎报资源需求时字典序最优全局累计占优资源份额向量为
相应地,用户在时刻t分配资源为
时，所能完成任务数向量为
根据式(1)(2)可知，若用户i在时刻t谎报资源需求时，获得的资源比诚实情形下多,则用户i至少在某一个虚拟机k∈S上分得的资源比诚实情形下多：
(11)
根据式(5)可知, 当用户i在时刻t谎报资源需求时,在虚拟机k上的累计全局占优资源份额比诚实情形下多：
根据式(5)可得:
(12)
由引理3可知当时所有虚拟机中至少存在一种资源
被消耗完，在虚拟机k上有
若用户i谎报资源需求时，根据式(9)第1个约束条件可得所有用户在虚拟机k上累计获得的第j种资源量小于等于
根据式(11)，用户i在时刻t谎报需求时在虚拟机k上获得的第j种资源比诚实情形下多：
所以一定存在至少一个用户h≠i,当i在时刻t谎报需求时,在虚拟机k上获得的第j种资源比i诚实报告需求时少：
(13)
因为当用户i在时刻t谎报需求时，其他用户是诚实的，即
根据式(13)有:
结合上式，根据式(2)及用户完成任务数不超过上限有:
(14)
根据式(5)可得
从而有:
(15)
因为根据式(14)有
即:
根据引理2有:
(16)
结合式(10)(12)(15)(16)可得:
上式矛盾，所以TV-DRF机制满足可信属性.
证毕.
3 TV-DRF算法
本文结合第3节TV-DRF机制与文献[9，12]的启发式算法设计一个动态资源调度算法，即基于云计算资源共享系统多虚拟机情形下用户提交多组有限的时变任务需求的动态多资源公平分配的启发式算法TV-DRF (time varied-DRF)算法.
考虑到在云计算资源共享系统在具有多个虚拟机情形下，不同用户提交的每个任务资源需求可能不相同，所以有必要根据用户提交的任务资源需求选择最适合运行的虚拟机，以满足更高的资源利用率.根据文献[9],我们定义系统中在时刻t第k台虚拟机剩余资源量为
其中
为第k个虚拟机中第j种资源在时刻t的剩余量.在时刻t用户i每个任务需求的资源量为αi(t)=(αi1(t),αi2(t),…,αim(t))，其中αir(t)为用户i在时刻t每个任务中对第j种资源的需求.根据文献[9]我们定义以下启发式公式来衡量用户任务资源需求与虚拟机的匹配度，以完成用户任务和虚拟机的匹配:
(17)
其中，
表示L1范数，当H(i,k)t越小，说明用户i在时刻t的任务需求与第k个虚拟机剩余的资源容量越匹配，我们选取具有最小匹配度的虚拟机分配任务资源给用户i.TV-DRF算法的主要思想有3个方面：
1) 当系统中有n个用户、K台虚拟机时，根据系统中任意用户i∈U在不同时刻的每个任务的资源需求αi(t)，每轮按照式(17)，选择最匹配的服务器k给用户i分配执行一个任务所需资源，并更新用户i的累计全局占优资源份额Gi(t)和全局共享系数βi(t),从小到大排序并选取用户中具有最小共享系数用户
若βi(t)<1，则寻找最匹配的虚拟机分配执行一个的任务资源给用户i，并更新系统资源分配状态.
2) 依次执行上面步骤，若系统中所有用户最小全局共享系数βi(t)≥1，则说明系统所有用户都不再共享缺损.选取所有用户中具有最小累计占优资源份额的用户：
并为用户g分配执行一个任务所需资源，更新系统资源分配状态.
3) 执行步骤1、步骤2，当系统中的某种资源j,1≤j≤m分配完毕时，或者所有用户任务执行完毕时，资源分配结束.
算法1. TV-DRF算法.
输入:用户任务资源需求Di(t),1≤i≤n、虚拟机k∈S资源总量
用户贡献资源权重向量
虚拟机k∈S剩余资源量*
输出:资源分配向量U(t).
① 初始化：
所有用户在时刻在虚拟机k∈S上的资源分配累计量*
任意一个用户i∈U,时刻t在虚拟机k∈S上的分配资源量 *
任意一个用户i∈U,时刻t在虚拟机k∈S上的分配累计资源量 *
βi(t)←0；*任意一个用户i∈U,时刻t全局共享系数*
G(t)=(G1(t),G2(t),…,Gn(t))←0；*时刻t所有用户累计全局占优资源份额向量*
② While 用户任务没有完成,∀i∈U
③ For i=1 to n
④
⑤ If βj(t)<1
⑥ alloc(j)；
⑦ Else
⑧ For i=1 to n
⑨
⑩ alloc(g)；
EndFor
EndIf
EndFor
EndWhile
分配函数alloc(user):
Di(t)←用户i下一个任务中资源需求
For k=1 to K
If Di(t)+Ck(t)≤Rk
Ck(t)=Ck(t)+Di(t)；
For r=1 to m
EndFor
Else
等待用户i完成正在执行任务；
Ck(t)=Ck(t)-Di(t)；
EndIf
EndFor
举例说明TV-DRF算法的资源分配.假设云计算资源共享系统含有2台共享虚拟机，每台虚拟机资源量为50核CPU,50 GB内存，由A,B这2个用户等比例提供，即
用户A，B的所有虚拟机共享资源量之和为SA=SB=(50,50).在时刻t1,用户A有15个任务需求，每个任务所需资源量为(1CPU,2 GB)；用户B有80个任务需求，每个任务所需资源量为(1CPU,1 GB).在时刻t2，用户A有60个任务需求，每个任务所需资源量为(1CPU,1 GB)；用户B有40个任务需求,每个任务所需资源量为(2CPU,1 GB).假设用户A，B任务执行时长相同.
在时刻t1，由于用户A需要完成的任务数少，TV-DRF算法将2台虚拟机资源分配给用户A执行15个任务所需资源后将余下资源分给用户B，用户B分得70个任务所需资源，此时资源耗尽.根据全局共享系数定义可得βA(t1)=1，βB(t1)=1.4.在时刻t2开始时，根据2个用户第2个时刻资源需求及时刻t1分配可知，用户A全局共享系数为0.23，用户B全局共享系数为0.7,优先分配资源给用户A，分配资源(35CPU,35 GB)给用户A，使得用户A全局共享系数不小于用户B.此时按照共享系数最小用户优先分配资源的方式分配，当用户A，B分别分得(50CPU,50 GB)和(40CPU,20 GB)资源时,2个用户共享系数已等于1.此时按照累计全局占优资源份额最小的用户最大的方式分配最终得βA(t2)=1.125，βB(t2)=1.
4 实验及分析
本文采用来自阿里巴巴集群数据集[15]12 951个任务运行所需的CPU和Memory资源作为本文实验中用户资源需求.数据集中每个用户以Job的形式提交多组任务资源需求，每个Job包含多组任务需求，每组任务由多个具有相同资源需求的实例组成,实验从该数据集中随机选取5，20，100个用户，用户资源需求如图1和图2所示，图1，2中纵坐标表示用户每个实例需要CPU数，横坐标表示每个实例需要内存数，实心圆的面积与用户任务数成正比，任务数越多则圆的面积越大.本文实验模拟服务器配置如表1所示，其中服务器台数为每个用户所具有的服务器资源.本文假设用户共享资源后虚拟机数与物理服务器数量相同.
Fig.1 20 users demand distribution
图1 20个用户需求分布
Fig. 2 100 users demand distribution
图2 100个用户需求分布
Table1 Cluster Server Configuration
表1 集群服务器配置
User NumberPer User Own MachinesCPU Capacity∕coreMemory Capacity∕GB512504020125040100120040
本文实验平台配置为:CPU为Intel i5-3230 M,12 GB内存，500 GB硬盘，实验配置如下：
1) 由于一个用户可以提出多组时变任务需求，本文将数据集batch_task文件中每组task看作为一个用户在一个时刻的任务资源需求.
2) 实验假设每个用户共享到集群中每一台虚拟机的每一种资源比例相同.
3) 将数据集中batch_task文件的create_timestamp认为是用户任务需求的提交时间,任务执行时长为单位时长.
4) 通过用户任务实例队列方式，对资源配置进行模拟，即每个用户有一个任务实例队列，需求提交事件看做是实例到达事件发生，此时TV-DRF算法对用户共享资源进行分配.
本文通过实验比较TV-DRF算法与用户在资源不共享的分配情形下中，5用户最小用户累计占优资源份额和20,100用户情形下资源利用率，执行100次取平均来评估TV-DRF算法性能.
1) 使用户累计占优资源份额满足字典序最优
从图3可以看出，由于TV-DRF算法目标是使用户累计占优资源份额满足最大、最小，因为用户不共享情形下分得的资源为其自有资源.所以，TV-DRF算法与用户不共享资源情形相比，最小的累计占优资源份额，随着时间的推移，差距越来越大.这说明TV-DRF算法保证了分配过程中累计占优资源最小的用户能分配最多的资源，也就是该用户完成任务数最大.与不共享算法相比，保证了用户完成的累计任务数尽可能多.
Fig. 3 Cumulative dominant share
图3 累计占优资源份额
Fig. 4 CPU utilization (20 users)
图4 CPU利用率(用户数20)
2) 高资源利用率
本文将TV-DRF算法下的资源利用率与用户在不共享资源的条件下系统的资源率进行比较.图4～7分别表示在用户数为20和用户数为100情形下系统的资源利用率.可以看出TV-DRF算法在任意时刻的系统资源利用率都高于用户在不共享资源条件下系统的资源利用率.
Fig. 5 Memory utilization (20 users)
图5 Memory利用率(用户数20)
Fig. 6 CPU utilization (100 users)
图6 CPU利用率(用户数100)
Fig. 7 Memory utilization (100 users)
图7 Memory利用率(用户数100)
总之，TV-DRF算法在满足公平性，使所有分配用户能够完成较多任务的同时，具有很高的资源利用率.
5 结束语
本文针对云计算资源共享系统中用户有限多组时变任务资源需求的分配问题，提出了一种基于资源共享公平的多资源公平分配机制.该机制根据用户不同时刻的有限时变任务需求和用户共享资源量建立规划模型，证明了在这种机制下用户所得分配满足4个公平属性：激励共享、帕累托最优、无嫉妒、可信.最后，实验基于用户累计占优资源份额，资源利用率与不共享资源算法进行对比，进一步说明TV-DRF算法能在保证用户满足累计占优资源份额字典序最优的同时，有较高资源利用率.但是，由于在算法执行过程中需要判断用户共享缺损，累计资源分配量等因素，使得算法在用户数和虚拟机数较多时分配执行速度不占优势.所以如何有效地使任务和虚拟机得到更优化的分配，以提高分配速度将是下一步研究重点.
[1]Zhang Xiaolu, Liu Xi, Li Weidong, et al. Dynamic fair allocation of multi-resources based on shared resource quantity[J]. Journal on Communications,2016, 37(7): 151-160 (in Chinese)(张潇璐, 刘曦, 李伟东, 等. 基于共享资源量的动态多资源公平分配策略[J]. 通信学报, 2016, 37(7): 151-160)
[2]Apache Software Foundation. Apache Mesos: Mesos[EB/OL]. [2018-08-21]. http://mesos.apache.org/
[3]Apache Software Foundation. Apache Hadoop Yarn: Yarn[EB/OL]. [2018-08-21]. http://hadoop.apache.org/
[4]Poullie P,Bocek T, Stiller B. A survey of the state-of-the-art in fair multi-resource allocations for data centers[J].IEEE Transactions on Network and Service Mangagement, 2018, 15(1): 169-183
[5]Li Jin, Xue Jingyi. Egalitarian division under leontief preferences[J]. Economic Theory, 2013, 54(3): 597-622
[6]Ghodsi A, Zaharia M, Hindman B, et al. Dominant resource fairness: Fair allocation of multiple resource types[C] //Proc of the 8th USENIX Conf on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2011: 323-336
[7]Kash I, Procaccia A D, Shah N. No agent left behind: Dynamic fair division of multiple resources[J]. Journal of Artificial Intelligence Research, 2014, 51: 579-603
[8]Li Weidong, Liu Xi, Zhang Xiaolu, et al. A further analysis of the dynamic dominant resource fairness mechanism[C] //Proc of the 11th Int Conf on Frontiers in Algorithmics. Berlin: Springer, 2017: 163-174
[9]Wang Wei, Liang Ben, Li Baochun. Multi-resource fair allocation in heterogeneous cloud computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(10): 2822-2835
[10]Li Weidong, Liu Xi, Zhang Xiaolu, et al. Dynamic fair allocation of multiple resources with bounded number of tasks in cloud computing systems[J].Multiagent Grid Systems, 2016, 11(4): 245-257
[11]Liu Xi, Zhang Xiaolu, Li Weidong, et al. Swarm optimiza-tion algorithms applied to multi-resource fair allocation in heterogeneous cloud computing systems[J]. Computing, 2017, 99(12): 1231-1255
[12]Tang Shanjiang, Niu Zhaojie, He Bingsheng, et al. Long-term multi-resource fairness for pay-as-you use computing systems[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(5): 1147-1160
[13]Li Weidong, Liu Xi, Zhang Xiaolu, et al. Multi-resource fair allocation with bounded number of tasks in cloud computing systems[C] //Proc of the 2017 National Conf of Theoretical Computer Science. Berlin: Springer, 2017: 3-17
[14]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): Article No.3
[15]Alibaba Group. Alibaba clustrdata 2017[EB/OL].[2018-08-21].https://github.com/alibaba/clusterdata/
