面向用户效用的排队模型,在云计算环境中资源分配

文摘

资源分配是服务器最重要的研究课题之一。在云环境中,有大量不同种类的硬件资源,多种服务通常运行在云服务器的虚拟机。此外,云环境是商业化和经济因素也应该被考虑。为了处理商业化和虚拟化的云环境,我们提出了一个面向用户的效用的队列任务调度模型。首先,我们在云环境作为建模的任务调度// 1排队系统。其次,我们分类效用时间效用和成本效用,建立了一个线性规划模型为他们两人总效用最大化。最后,我们提出了一个面向实用的算法,使总效用最大化。大量实验验证提出模型的有效性。

1。介绍

云服务提供商通常提供不同的计算资源具有不同性能和不同的价格,和用户资源的性能和成本的要求也有很大的不同。所以如何分配现有资源为用户以最大化系统利用率是一个最重要的目标对资源配置和调度任务(1),在云计算也是一个研究热点。

传统的资源分配模型主要集中在响应或运行时间,整个系统的节能,任务调度的公平性和不考虑用户效用2]。然而,用户在云环境的实用程序服务或资源的使用价值,它描述了用户提出的服务感到满意或资源,占据和使用它们3,4]。为了最大化所有用户的总效用在云环境中,有必要分析和模型用户效用,然后优化它获得最大(5]。建模的用户效用是非常复杂的,它需要一个正式的描述考虑很多因素,比如任务的处理时间(通过6),完成任务的比率(7),完成和未完成的任务的成本8),和并行加速9]。

在一个云服务器,请求的用户,称为任务,随机,和一个好的描述这些任务是泊松分布假设。同时,商业化云环境的约束下,云服务器的实用程序变得更为重要。在这篇文章中,我们正式和量化任务调度问题的基于排队理论,效用分为时间效用和成本效用,提出了一种线性规划方法的总效用最大化。本文的贡献如下:(我)我们建模的任务调度排队模型和分析相关功能的排队模型。(2)我们分类效用时间效用和成本效用,建立了一个线性规划方法对他们每个人总效用最大化。(3)我们提出了一个面向效用和成本为基础的调度算法获得最大的效用。(iv)我们与大量的实验验证了该模型的有效性。

剩下的纸是组织如下。节2我们回顾相关工作大约在云计算资源分配和任务调度。节3在云环境中,我们形式化任务排队论的基础上,定义一个随机随机任务的任务模型,描述我们建议的用户效用模型,并设计一个面向实用的时间成本调度算法。实验和结论给出了部分4和5,分别。

2。相关的工作

在集群系统提供云服务,是一种常见的协议在研究者的时刻,当任务进入系统,符合泊松分布,两个未来的任务之间的时间间隔和服务时间是指数分布的任务。在这种情况下,启发式任务调度算法,如遗传算法和蚁群算法,比传统的调度算法有更好的适应性。然而,启发式算法的赤字,他们有复杂的问题解决过程,所以他们只能应用于小型集群系统。云系统的巨大的基础设施通常有许多类型的任务,大量的任务,和各种硬件资源,使启发式算法不合适。

有很多关于资源分配和任务调度的研究在云环境中,特别是对于MapReduce编程模式(10]。程等。11)提出了一个近似算法来估计剩余时间(时间结束)MapReduce任务的环境和算法将任务剩余时间。陈等人。12)提出了一种自适应任务调度算法,该算法计算正在运行的进程(从头到总运行时间)上的时间比当前任务的节点根据其历史数据。的优势(12),它可以动态地计算剩余时间的任务和更适合异构云环境11]。此外,莫伊兹et al。13)设计了一个中间件的数据存储系统来提高性能和容错能力。

传统的任务调度算法主要关注整个系统的效率。然而,一些研究人员任务调度中引入经济模型,基本思想是优化资源配置,调整用户的需求和资源配置价格机制(14]。徐et al。15伯杰]提出了一种基于模型的任务调度算法。考虑实际商业化和虚拟化的云计算,算法是基于伯杰社会分配模式,增加了额外的成本约束优化目标。根据CloudSim实验平台,他们的算法是有效和公平的运行时不同的用户的任务。此外,对资源的多样性在云环境中,更多的研究者认为,多样性将随着时间的推移增加硬件资源的更新。为了缓解这一现象,确保服务质量,杨和李16)发现,虽然是独立同分布的资源,减少资源需要三倍数量的最小响应时间可能使整个系统使用更少的总响应时间和更少的能量。

随机调度的研究始于1966年,罗斯科夫(17)提出了一种贪婪优化算法基于任务的权重和预计完成时间,总时间的比率。如果所有任务都有同样的重量,那么该算法成为了预计处理时间最短的算法。莫尔et al。18]证明了最优近似与随机调度任务完成时间。他们开始松弛的线性规划,研究了整数线性规划的问题与齐次系统的任务,并得到了一个近似解线性规划的下限。基于上述研究,Megow et al。19)提出了一个更好的和更好的近似最优解。此外,Scharbrodt et al。20.]研究了随机安排独立的任务。他们分析了调度的问题任务机器随机,并随机均匀环境下调度最糟糕的性能从理论上说,和他们的结果是最好的相关工作。

上述算法关注用户的响应或运行时间的要求,整个系统的节能和公平的任务,而不考虑用户效用。然而,实用的用户在云服务系统是很重要的。为了最大化所有用户的总效用在云环境中,我们首先分析和模型的用户效用,然后得到最大优化的解决方案。

此外,南et al。21)研究如何优化资源配置多媒体云基于排队模型,和他们的目标是最小化响应时间和资源成本。然而,在本文中,我们处理商业化和虚拟化的云环境,和我们的目标是最大化效用。肖et al。22)提出了一个系统,使用虚拟化技术动态分配数据中心资源。他们的目标是减少使用考虑到应用程序的服务器的数量需求和效用,而在本文中,我们的目标是最大化系统总效用下特定的云环境。

3所示。提出的模型

3.1。排队模型的任务

在本文中,我们描述的任务的随机性排队论模型,模型如图1。该模型由一个服务器,多个调度器,和几个计算资源。当用户提交的任务,服务器分析,安排不同的调度器并将它们添加到相应的本地任务队列调度器。最后,每个调度程序安排其本地任务可用的计算资源。在图1,是一个任务队列中的等待时间,运行时间。

3.2。随机建模的任务

在下面,我们将分析的等待时间、运行时间、队列长度的建议模型。

定义1。如果任务调度器的平均到达率的平均服务率任务调度器,然后服务强度是 服务强度描述调度器的忙碌。当接近零,任务的等待时间短,和调度器有很多空闲时间;当方法一,任务调度器有更少的空闲时间,因此会漫长的等待时间。一般来说,平均到达率应该等于或小于平均服务率,否则将会有越来越多的等待任务调度器。

定义2。如果我们表示预期的任务调度器的长度预期的任务在排队长度,预计总时间(包括等待时间和运行时间)的任务和预期的任务在排队等待时间,然后我们有以下方程根据排队论(17]: 此外,让是数量的任务的可能性随时调度器;然后,我们有以下方程: 如果,然后是所有虚拟机处于空闲状态的可能性。

3.3。模型的用户效用

3.3.1。时间的效用的任务

从图我们可以看出1的总时间,用户需要从提交请求的结果包括等待时间和运行时间。在这里,由虚拟机虚拟资源管理计算资源。让总时间;然后,我们有

在(4),运行时间是使用的和时间吗和剩余时间;也就是说, 为了计算任务的时间要求,系统需要计算剩余时间和时间表对于不同的任务到不同的虚拟机。

分析剩下的时间,我们分类任务集和节点集。根据统计计算,我们可以得到平均执行任务在节点;也就是说, ,然后剩下的时间在是 在哪里任务和总数量吗是完成任务的数量。对于计算密集型任务,总输入数据和吗是已经处理过的输入数据。虚拟机资源调度程序调度任务根据他们的剩余时间,保证准时完成所有任务。

一个任务可以在一个虚拟机或执行并行虚拟机,而被分成子任务。我们表示子任务设置为。虽然这些子任务执行在不同的虚拟机,尤其是不同的物理节点,沟通成本增加,我们使用加速度量并行性能 在哪里在一个节点一个任务的时候,一个任务的时候在吗节点。为了确保,所有子任务并行运行,总时间的任务 在哪里子任务的时间吗在和是所有子任务的最大时间。

3.3.2。成本效用的任务

在本文中,我们假设节点的成本率正比于CPU和I / O速度、和任务的不同类型使用不同的能量,不同的带宽,不同的资源使用情况。所以不同的任务有不同的成本率。

定义3。让任务的成本矩阵在节点,然后总成本的一个任务是节点的产品成本和运行时间;也就是说, 在哪里单位成本的任务在节点和子任务的时间吗在节点。

3.3.3。规范化和优化用户的效用

定义4。让时间效用函数让成本效用函数;然后,总效用 在哪里,和。
在(10),时间效用和成本效用是在0和1之间和时间效用和成本效用的权重,分别。
面向实用的任务调度的目的是最大化总效用,和约束预计时间的任务,预期成本,完成速度,加速等等。在这篇文章中,我们将用户任务在时间敏感和成本敏感。
时间敏感的用户任务,改变任务的运行时间会影响时间的效用,和它的定义如下。

定义5。时间的实用新型敏感用户任务被定义为以下方程: 约束是 在哪里所有任务的子任务的集合,其目的是总效用最大化。

对成本敏感的用户任务,改变任务的运行成本将影响成本效用,和它的定义如下。

定义6。本实用新型成本敏感的用户任务被定义为以下方程: 约束是

在这两个定义5和6,他们的目标是最大化的总效用,但差异的计算和。根据上述定义,我们提出一个基于面向效用和成本的调度算法。算法的详细信息如下:(1)分析用户类型为每个用户并选择计算方程和。(2)初始化参数的约束,,,,,,。(3)计算和对于每个调度程序根据(1)(3)。(4)在步骤(3)的结果,标签调度程序等待时间最小。(5)输入一些数据调度器和设置这些任务的优先级最高。(6)执行上述任务,并记录运行时间和成本(见伪代码1)。(7)预测运行时间、成本和相应的效用的任务和步骤6的结果的时间和成本,和标记的调度器最大效用。(8)计划任务调度器的最大效用,并优化用户效用(见伪代码2)。(9)等到所有任务完成,并记录运行时间,成本,和相应的效用。

4所示。实验

4.1。实验装置

我们做实验在两个硬件配置和配置表1。两个硬件配置上运行CentOS5.8 Hadoop-1.0.1。

总有20个计算节点在我们的实验环境,并且每个计算节点启动一个虚拟计算节点。我们开始10调度器,每个调度程序管理2虚拟节点(计算节点)。我们在实验中使用的应用程序是WordCount。

根据(1)(3),我们计算服务强度,预计数量的任务调度器排队长度的期望值,预计完成时间的任务和预期的排队等待时间。图2描述了预期的等待时间在每个调度程序。从图中,我们可以看到从调度器的等待时间1,3,5,7满意(14)和(23),因此我们可以复制和执行子任务(数据大小1 KB)。如果用户的任务是时间敏感,那么我们在节点上运行的任务以更快的速度;如果用户成本敏感,那么我们在成本较低的节点上运行的任务。

4.2。实验时间敏感的用户效用模型

为了选择时间效用和成本效用函数的参数,我们首先正常化,得到以下方程。图3描述了以下两个方程的曲线:

基于运行时间和率、总时间、成本、和公用事业从调度器1,3,5,7,我们集和在(10)。的约束下(12)(19),我们计算总效用。在图4,预测时间的效用,预计成本效用,预计总效用,实际的总效用,是我们得到的总效用通过重新安排任务上面的1、3、5、7调度器。

在图4调度程序1,,,,都是最低的;调度器3,是最高的,是低得多,是最高的;调度器5和7,虽然他们高于调度器,他们低于调度程序3。根据效用最大化的原则,我们应该选择调度器调度程序3。然而,为了进一步提高总效用,我们应用该算法部分3.3.3。通过重新安排任务在排队,得到实际的总效用每个调度程序。在调度器5和7中,远高于的调度程序3。

4.3。实验成本敏感的用户效用模型

为了选择时间效用和成本效用函数的参数对成本敏感的用户任务,我们也正常化并得到以下两个方程。图5描述了以下两个方程的曲线:

从图6我们可以看到,预测的总效用调度器5中是最高的,如果我们安排任务调度器5,我们将实际的总效用最高。如果用户任务有不同的时间和成本要求,我们可以选择不同的计算节点来执行它们,使总效用最大。此外,重新安排任务后,所有任务有更高的实际总效用比预期效用和实际的总效用,验证了算法的有效性。

4.4。比较实验

在这个实验中,我们选择了10个模拟任务和敏敏和极大极小算法相比,我们的算法。敏敏算法安排最快的计算节点每次最低任务,和极大极小算法计划最快的计算节点每次最大任务。我们实现了两种算法对时间敏感和成本敏感的用户任务和MaxUtility-Time和MaxUtility-Cost表示它们。实验结果图7。

在图7,MaxUtility-Time和MaxUtility-Cost算法的总效用高于其他两种算法,也稳定;敏敏和极大极小算法有较低的总效用,和它们的值波动。敏敏和极大极小算法只考虑任务的运行时间和忽略需求的时间和成本,这使得他们可以得到更低的总效用和波动。特别是,当运行任务8,9,10,总效用极大极小算法的快速下降。原因是它安排长时间运行的任务与高性能计算节点,使效用非常低。

5。结论

在本文中,我们介绍了公用事业到云环境中,量化用户服务的满意度作为工具,并提出了面向实用的队列任务调度模型。我们分类效用在时间和成本效用,改期任务根据他们的剩余时间和最小化总效用的约束。通过该模型,我们可以安排剩余任务动态获得最大的效用。我们通过大量的实验验证了我们的模型。

利益冲突

作者宣称没有利益冲突有关的出版。

引用

1. a . Beloglazov和r . Buyya节能资源管理在虚拟化的云数据中心,”学报第十届IEEE / ACM国际研讨会上集群,云计算和网格计算IEEE,页826 - 831年,墨尔本,澳大利亚,2010年5月。视图:出版商的网站|谷歌学术搜索
2. c . s .杨和r . Buyya”,服务水平协议建立集群资源配置:处理处罚来增强效用,”《IEEE国际会议上集群计算集群(05)美国大众,页1 - 10,伯灵顿,2005年9月。视图:出版商的网站|谷歌学术搜索
3. j·n·席尔瓦、l . Veiga和p·费雷拉,“效用计算基础设施启发式对资源的分配,”学报第六届国际研讨会对网格计算的中间件(MGC ' 08)ACM,页93 - 100年,鲁汶,比利时,2008年12月。视图:出版商的网站|谷歌学术搜索
4. 李歌和y”上进行资源分配和调度OFDM-based无线宽带网络,”IEEE通讯杂志,43卷,不。12日,第134 - 127页,2005年。视图:出版商的网站|谷歌学术搜索
5. t . t . Huu和j . Montagnat”虚拟资源分配workflow-based应用程序分布在云基础设施,”学报第十届IEEE / ACM国际研讨会上集群,云计算和网格计算(CCGrid 10)IEEE,页612 - 617年,墨尔本,澳大利亚,2010年5月。视图:出版商的网站|谷歌学术搜索
6. 雅科夫y”,动态资源分配时间相关的资源平台和方法,“美国专利申请10/314,198 [P], 2002。视图:谷歌学术搜索
7. g ., A . v . Vasilakos y,和n .熊”的博弈论的方法为云计算服务公平的资源分配,”《华尔街日报》的超级计算,54卷,不。2、252 - 269年,2010页。视图:出版商的网站|谷歌学术搜索
8. d . Lopez-Perez x, a . v . Vasilakos和h . Claussen“功率最小化干扰缓解在OFDMA毫微微蜂窝网络资源分配,”IEEE在选定地区通讯》杂志上,32卷,不。2、333 - 344年,2014页。视图:出版商的网站|谷歌学术搜索
9. 王x和j·f·马丁内斯,“换:一个以市场为基础的方法在多核架构,可伸缩的动态multi-resource分配”诉讼21 IEEE国际研讨会的高性能计算机体系结构(HPCA 15)IEEE,页113 - 125年,伯林盖姆,加州,美国,2015年2月。视图:出版商的网站|谷歌学术搜索
10. l . Thomas r . Syama”调查MapReduce的调度算法”,国际期刊的计算机应用程序,卷95,不。23日,第四,2014页。视图:出版商的网站|谷歌学术搜索
11. j . d . Cheng饶、郭y、x周”改善与自适应任务的MapReduce异构环境下的性能调优,”第15届国际中间件研讨会论文集(中间件的14)ACM,页97 - 108年,波尔多,法国,2014年12月。视图:出版商的网站|谷歌学术搜索
12. 问:陈,d, m .郭邓,和s .郭”mapreduce SAMR:自适应调度算法在异构环境下,”学报第十届IEEE计算机和信息技术国际会议(CIT 10)IEEE,页2736 - 2743年,布拉德福德,英国,2010年7月。视图:出版商的网站|谷歌学术搜索
13. d·莫伊兹T.-T.-L。l . Bouge Trieu, g . Antoniu“MapReduce计算,优化中间数据管理”学报第一国际研讨会在云计算平台上(CloudCP 11)页37-50 ACM,奥地利萨尔斯堡,2011年4月。视图:出版商的网站|谷歌学术搜索
14. r . Buyya d·艾布拉姆森,j .头晕和h .袜子”经济模型在网格计算资源管理和调度,“并发计算实践和经验,14卷,不。13 - 15,1507 - 1542年,2002页。视图:出版商的网站|谷歌学术搜索
15. 胡赵b, c, e和b·胡”作业调度算法基于伯格模型在云环境中,“工程软件的进步,42卷,不。7,419 - 425年,2011页。视图:出版商的网站|谷歌学术搜索
16. 杨和h。美国李”,使用数学建模提供异构云计算环境中,“电脑,44卷,不。8篇文章ID 5740825、55 - 62、2011页。视图:出版商的网站|谷歌学术搜索
17. m·h·罗斯科夫”与随机服务时间安排”,管理科学,12卷,不。9日,第713 - 707页,1966年。视图:出版商的网站|谷歌学术搜索
18. r·h·莫尔,a·s·舒尔茨和m .会继续光顾“近似随机调度:LP-based优先政策的力量,”ACM的杂志,46卷,不。6,924 - 942年,1999页。视图:出版商的网站|谷歌学术搜索
19. n . Megow m会继续光顾,t . Vredeveld”网上随机调度模型和算法”,运筹学的数学没有,卷。31日。3、513 - 525年,2006页。视图:出版商的网站|谷歌学术搜索
20. m . Scharbrodt t Schickinger, A·斯蒂格”一个新的完成时间调度平均情况分析,“ACM的杂志,53卷,不。1,第146 - 121页,2006。视图:出版商的网站|谷歌学术搜索
21. x Nan, y, l .关”最佳资源配置多媒体云基于排队模型,”学报》第三届IEEE国际研讨会上多媒体信号处理(MMSP 11),页1 - 6,杭州,中国,2011年11月。视图:出版商的网站|谷歌学术搜索
22. 肖z, w .歌,问:陈,“动态资源分配为云计算环境中,使用虚拟机”IEEE并行和分布式系统,24卷,不。6,1107 - 1117年,2013页。视图:出版商的网站|谷歌学术搜索

版权

版权©2015张哲和李应。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。