一种作业弹性与截止时间感知的作业调度算法

doi:10.3969/j.issn.1006-2475.2019.04.006

摘要/Abstract

摘要： 针对采用MapReduce模型的大数据分析作业的调度问题进行深入研究，并分析现有任务调度算法的缺陷，现有算法没有考虑资源分配对于作业截止时间的影响，也未考虑不同类型作业截止时间的敏感性问题。因作业的完成时间随着分配资源的不同而改变，故称之为弹性作业，截止时间敏感性是指不同类型作业对截止时间要求的严格程度不同。针对以上问题，提出一种截止时间感知的弹性作业调度算法（DA）。该算法将作业依据截止时间敏感程度进行分类，在基于作业整体执行时间预测的基础上，通过调控不同的资源分配策略来改变作业完成时间，同时结合用户对于截止时间的需求及作业预执行的收益来提前规划作业的资源分配及调度次序使得整体收益最大化。将算法在仿真拥有210个物理节点的集群中进行实验，实验表明该算法满足了截止时间的限制并使得作业整体收益值平均提高了2.37倍。

关键词: 弹性作业, 截止时间感知, 执行时间预测, 调度算法

Abstract: We make an in-depth study of big data analysis jobs using the MapReduce model, and analyze the defects of the existing job scheduling algorithms. Most of the existing algorithms do not take into account these problems: the impact of resource allocation on job deadline and deadline sensitivity for different types of jobs. It is elastic jobs because the completion time of it that varies with the allocation of resource, deadline sensitivity means that different types of jobs have various degrees of strictness to deadlines. To solve above problems, we propose a flexible job scheduling algorithm based on deadline-aware(DA). The algorithm classifies jobs according to the sensitivity of deadline, based on the prediction of the overall execution time of jobs, by regulating different resource allocation strategies to change the completion time, combines with the users’ demand of deadline and the benefits of job pre-execution to planning the resource allocation and scheduling order of jobs in advance, for the sake of maximizing the overall benefits. We implement DA according to simulation experiment, and evaluate it on a 210 machine cluster using production workloads. The experiment shows that the algorithm satisfies the deadline and the overall yield increases by 2.37 times in average.

Key words: flexible job, deadline-aware, execution time prediction, scheduler algorithm

中图分类号:

TP301

黄春秋，陈志，荣垂田. 一种作业弹性与截止时间感知的作业调度算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2019.04.006.

HUANG Chun-qiu， CHEN Zhi， RONG Chui-tian . An Elasticity and Deadline-aware Job Scheduling Algorithm[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2019.04.006.

参考文献［23］

［1］	ZAHARIA M, BORTHAKUR D J, SARMA S, et al. Delay scheduling: A simple technique for achieving locality and fairness incluster scheduling［C］// Proceedings of the 5th European Conference on Computer systems. 2010:265-278.
［2］	ZAHARIA M, KONWINSKI A, JOSEPHA D, et al. Improving MapReduce performance in heterogeneous environments［C］// Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation. 2008:29-42.
［3］	HUANG Z, BALASUBRAMANIAN B, WANG M, et al. Need for speed: CORA scheduler for optimizing completion-times in the cloud［C］// IEEE Conference on Computer Communications. 2015:891-899.
［4］	SHAKKOTTAI S, SRIKANT R. Scheduling real-time traffic with deadlines over a wireless channel［C］// Proceedings of the 2nd ACM International Workshop on Wireless Mobile Multimedia(WOWMOM’99). 1999:35-42.
［5］	JOHNSSON K, COX D. An adaptive cross-layer scheduler for improved QoS support of multiclass data services on wireless systems［J］. IEEE Journal on Selected Areas in Communications, 2005,23(2):334-343.
［6］	TIAN C, ZHOU H, HE Y, et al. A dynamic MapReduce scheduler for heterogeneous workloads［C］// IEEE the 8th International Conference on Grid and Cooperative Computing. 2009:218-224.
［7］	杨浩,滕飞,李天瑞,等. Hadoop平台中空闲时间调度器的设计与实现［J］. 计算机工程与科学, 2013,35(10):125-130.
［8］	张永,贺言君. Hadoop平台下基于截止时间限制的动态调度算法的研究［J］. 计算机应用研究, 2016,33(2):544-548.
［9］	李曌,滕飞,李天瑞,等. 一种Hadoop中基于作业类别和截止时间的调度算法［J］. 计算机科学, 2015,42(6):28-31.
［10］	TENG F, YANG H, LI T R, et al. Scheduling real-time workflow on MapReduce-based cloud［C］// IEEE the 3rd International Conference on Innovative Computing Technology. 2013:117-122.
［11］	TANG Z, ZHOU J, LI K, et al. MTSD: A task scheduling algorithm for MapReduce base on deadline constraints［C］// IEEE Parallel and Distributed Processing Symposium Workshops & Phd Forum. 2012:2012-2018.
［12］	CHEN C H, LIN J W, KUO S Y. Deadline-constrained MapReduce scheduling based on graph modeling［C］// IEEE International Conference on Cloud Computing. 2014:416-423.
［13］	KC K, ANYANWU K. Scheduling Hadoop jobs to meet deadlines［C］// IEEE the 2nd International Conference on Cloud Computing Technology and Science. 2011:388-392.
［14］	VARGA M, PETRESCU-NITA A, POP F. Deadline scheduling algorithm for sustainable computing in Hadoop environment［J］. Computers & Security, 2018,76:354-366.
［15］	CHENG D, RAO J, JIANG C, et al. Resource and deadline-aware job scheduling in dynamic Hadoop clusters［C］// Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium(IPDPS’15). 2015:956-965.
［16］	ULLAH I, CHOI J, RYOU Y, et al. Hadoop preemptive deadline constraint scheduler［C］// IEEE International Conference on Cyber-enabled Distributed Computing & Knowledge Discovery. 2014:201-208.
［17］	HOU X F, KUMARA T K, THOMAS J P. Dynamic deadline-constraint scheduler for Hadoop YARN［C］// 2017 IEEE SmartWorld Ubiquitous Intelligence and Computing, Advanced and Trusted Computed, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People and Smart City Innovation. 2017.
［18］	FARCASANU A C, POP F, NITA M C, et al. Starvation avoidance with deadline constraints in Hadoop environments［C］// 2017 IEEE 31st International Conference on Advanced Information Networking and Applications (AINA). 2017.
［19］	YANG Y, XU J, WANG F, et al. A MapReduce task scheduling algorithm for deadline-constraint in homogeneous environment［C］// IEEE 2014 2nd International Conference on Advanced Cloud & Big Data. 2015:208-212.
［20］	PERRET Q, CHARLEMAGNE G, SOTIRIADIS S, et al. A deadline scheduler for jobs in distributed systems［C］// Proceedings of the 2013 27th International Conference on Advanced Information Networking and Applications Workshops. 2013:757-764.
［21］	AGARWAL S, KANDULA S, BRUNO N, et al. Re-optimizing data-parallel computing［C］// Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation(NSDI’12). 2012:21.
［22］	JALAPARTI V, BODIK P, MENACHE I, et al. Network-aware scheduling for data-parallel jobs: Plan when you can［J］. ACM SIGCOMM Computer Communication Review, 2016,45(5):407-420.
［23］	CHEN Y P, GANAPATHI A, GRIFFITH R, et al. The case for evaluating MapReduce performance using workload suites［C］// IEEE the 19th Annual International Symposium on Modelling, Analysis, and Simulation of Computer and Telecommunication Systems, 2011:390-399.

[1]	王可1,2，李晖1,2，陈梅1,2，戴震宇1,2，朱明3. 一种面向工作负载预测的基于小波变换的特征提取方法[J]. 计算机与现代化, 2020, 0(05): 1-.
[2]	张良玉1，王义1，张育贵2，刘志超1，杨梅1. FlexRay动态段消息调度优化算法[J]. 计算机与现代化, 2018, 0(05): 11-.
[3]	张志国. 基于工业以太网的高速列车通信网络仿真[J]. 计算机与现代化, 2017, 0(9): 1-6.
[4]	孙亚南，潘中强. IEEE 802.16中支持QoS的有效带宽分配机制[J]. 计算机与现代化, 2016, 0(9): 25-29+34.
[5]	田丽迎，王宇，姜雪婷. 基于云计算的软件测试中的调度问题研究[J]. 计算机与现代化, 2016, 0(10): 61-66.
[6]	黄国兵1，蔺元2，金勇1. 基于现场适应性策略的自动抄表任务调度算法[J]. 计算机与现代化, 2015, 0(11): 36-39+46.
[7]	魏成巍，裴毅，刘东升，王卫平. 基于PSO的多无人机协同任务目标分配方法[J]. 计算机与现代化, 2015, 0(11): 32-35.
[8]	王俊松;郝永生. 气象环境下的云计算调度算法[J]. 计算机与现代化, 2013, 1(11): 68-73.
[9]	王耀棱;李少鹏;何兴恒;樊红伟;郭松林. 基于拼接方法的中考监考教师派遣问题的研究[J]. 计算机与现代化, 2012, 1(6): 34-36,4.
[10]	任海铭;朱江. 多参数综合调度算法[J]. 计算机与现代化, 2012, 208(12): 16-18.
[11]	周松泉. 一种改进的集群动态负载均衡算法[J]. 计算机与现代化, 2012, 1(1): 135-139.
[12]	李玉玲;杜洪;樊滨温. 一种适用于多业务场景的HSDPA分组调度算法[J]. 计算机与现代化, 2011, 193(9): 19-21,2.