A MapReduce Task Scheduling Algorithm for Deadline-Constraint in Homogeneous Environment

The current works about task scheduling with deadline-constraint in homogeneous environment rarely take the differences of Map and Reduce task and data locality into account in the same scheduler. To address this problem, we introduce a scheduling algorithm that Map and Reduce are regarded as two separated stages of scheduling problem in homogeneous environment. For the sake of realizing this algorithm, five aspects that are average execution time of map/reduce tasks, map/reduce stage deadline, remaining time of map/reduce stage, job´s priority and data locality must be taken into consider. Compared with other real-time scheduling algorithm, we propose several methods which are one-to-one sampling, estimating requirements of resource and compromised task-data matching strategy to solve above five aspects. The experimental results show the sampling method can get accurate map/reduce task execution time and the proposed scheduling algorithm not only satisfies the job´s real-time requirement but also improves the throughput of cluster.