一种mapreduce实时调度算法设计及实现①-计算机系统应用.pdf

2013 年 第 22 卷 第 8 期 计 算 机 系 统 应 用 ① 一种MapReduce 实时调度算法设计及实现 1 1,2 1 1 1,2 刘 吉 , 陈香兰 , 代 栋 , 孙明明 , 周学海 1( 中国科学技术大学 计算机科学与技术学院, 合肥 230027) 2( 中国科学技术大学 苏州研究院, 苏州 215123) 摘 要: MapReduce 是云计算中重要的批数据处理框架, 多任务共享MapReduce 机群并满足任务实时性要求是调 度算法急需解决的问题. 提出两阶段实时调度算法, 将调度划分为任务间调度和任务内调度. 对于任务间调度, 使用抽样法和经验值法确定子任务执行时间, 利用该参数建立资源分配模型, 动态确定任务优先级进行调度; 对 于子任务使用延迟调度策略进行调度, 保证计算的本地性. 实验结果显示, 两阶段实时调度算法相比公平调度算 法和 FIFO 算法, 在保证吞吐量的同时能够满足任务实时性要求. 关键词: MapRuduce; 实时调度; 抽样法; 延迟调度 Design and Implementation of a Real-time Scheduling Algorithm for MapReduce 1 1,2 1 1 1,2 LIU Ji , CHEN Xiang-Lan , DAI Dong , SUN Ming-Ming , ZHOU Xue-Hai 1(College of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China) 2(Suzhou Institute for Advanced Study, University of Scienceand Technology of China, Suzhou 215123, China ) Abstract: MapReduce is a popular batch data processing framework in cloud computing field. Sharing MapReduce cluster and meeting the deadlines of jobs is a key problem to be solved. This paper proposes a two phase real-time scheduling algorithm which separate scheduling into job scheduling and task scheduling.It uses sampling method to estimate the task excuting time so that the scheduler can make a decision on how many slots should be assigned to the job and how to calculate the jobs priority. Using dela y-scheduling scheme in task scheduling, thecomputing localityproblem can be solved well. Experiments result shows that the scheduling algorithm implemented in this paper satisfies the jobs real-time requirement as well as t