基于排队网络的多优先级MapReduce作业调度算法

摘要：

MapReduce是一个能够对大规模数据进行分布式处理的框架,目前被各个领域广泛应用.在提供MapReduce服务的集群中,如何保证不同优先级用户的截止时间限定是MapReduce作业调度问题的一个挑战.针对这一问题,提出了一个基于排队网络的多优先级作业调度算法(MPSA).首先分析和归纳了基于MapReduce模型的算法,提出了三种常见模式,采用Jackson排队网络对基于MapReduce模型的算法建立了数学模型,应用该网络模型可以求出不同优先级队列对资源的需求;随后使用AR(1)模型进行预测,使算法可以动态地适应不同的用户访问量;利用二分查找算法,分步计算出不同优先级在map阶段和reduce阶段分配的槽位数;最后实现了在MapReduce模型中应用的实时调度算法.实验结果表明,与传统的FIFO和公平调度算法相比,本文提出的算法在用户到达率和任务规模变化的情况下,可以更加有效地满足不同优先级用户的截止时间限定.

关键词：云计算、排队网络、MapReduce、调度算法

所属期刊栏目：36

分类号：TP312(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61300195;辽宁省教育厅科学研究一般资助项目L2013099;中央高校基本科研业务费资助项目N110323009

在线出版日期：2015-01-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：2286-2295