An Elasticity and Deadline-aware Job Scheduling Algorithm

doi:10.3969/j.issn.1006-2475.2019.04.006

Abstract

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

CLC Number:

TP301

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.

References ［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]	TIAN Yun-na, TIAN Yuan, LIU Xue, ZHAO Yan-lin. An Improved Grey Wolf Algorithm for Flexible Job Shop Scheduling Problem [J]. Computer and Modernization, 2022, 0(08): 78-85.
[2]	XU Ming, ZHANG Jian-ming, CHEN Song-hang, CHEN Hao. Multi-objective Optimization Algorithm for Flexible Job Shop Scheduling Problem [J]. Computer and Modernization, 2021, 0(12): 1-6.
[3]	ZHENG Jie , PAN Da-zhi , . Improved Discrete Firefly Optimization Algorithm to Solve Flexible Job Shop Scheduling Problem [J]. Computer and Modernization, 2021, 0(08): 11-15.
[4]	WANG Ke1,2, LI Hui1,2, CHEN Mei1,2, DAI Zhen-yu1,2, ZHU Ming3. A Wavelet Transform-based Feature Extraction Method for Workload Prediction [J]. Computer and Modernization, 2020, 0(05): 1-.
[5]	ZHANG Chun-yan. Improved Multiobjective Evolutionary Algorithm for Solving Flexible Job Shop Scheduling Problem [J]. Computer and Modernization, 2017, 0(9): 79-84.