A Highly Efficient Data Locality Aware Task Scheduler for Cloud-Based Systems.
Abstract
Scheduling on clouds is required so that service providers can meet Quality of Service (QoS) requirements of tenants. Deadline is a major criterion in judging QoS. This work presents a real-time, preemptive, constrained scheduler using queuing theory - PDSonQueue - which enables better meetinhg of QoS requirements. PDSonQueue also shortens a job's completion time and improves system's throughput. PDSonQueue, as a dynamic priority real-time greedy scheduler, builds a queuing-based mathematical model to accurately predict a job's execution and waiting time, where jobs arrive by following a stochastic process and request resources. Our scheduler introduces a novel "Earliest Maximal Waiting Time First (EMWTF)" concept to fine tune job scheduling to guarantee the job being accomplished within the deadline. Deadline constrained jobs are scheduled preemptively from low priority jobs with the intent of maximising the number of jobs completed within the deadlines, while allowing system's resources to be shared by other regular jobs. PDSonQueue integrates an improved Dominant Resource Fairness (DRF) greedy resource allocation approach to capture the essence of tenants' resource allocation and run as many jobs as possible. Our experimental results indicate that PDSonQueue can improve by at least 20% of deadline-based QoS rate, and by at least 30% for throughput. Index Terms-deadline, multi-tenancy, scheduling, queuing theory, resource preemption I. I NTRODUCTION Cloud computing provides a variety of QoS sensitive services to different tenants in a scalable and virtualised manner [1]. E.g., financial applications such as stock trades have strict job deadlines and cloud service consumers are willing to pay for this. In contrast, many scientific jobs are willing to trade a bounded delay for lower costs. The primary challenge is to meet the Service Level Agreements (SLAs) for their job completion deadline [2]. Scheduling mechanisms should differentiate jobs based on their importance or priority [2]. A better scheduling policy should not only enable cloud resources to be better provisioned according to tenants' needs, but also minimise the number of violated SLAs. It also enable