Provably Efficient Online Nonclairvoyant Adaptive Scheduling

Citations Over TimeTop 10% of 2008 papers

Abstract

Multiprocessor scheduling in a shared multiprogramming environment can be structured in two levels, where a kernel-level job scheduler allots processors to jobs and a user-level thread scheduler maps the ready threads of a job onto the allotted processors. We present two provably-efficient two-level scheduling schemes called G-RAD and S-RAD respectively. Both schemes use the same job scheduler RAD for the processor allotments that ensures fair allocation under all levels of workload. In G-RAD, RAD is combined with a greedy thread scheduler suitable for centralized scheduling; in S-RAD, RAD is combined with a work-stealing thread scheduler more suitable for distributed settings. Both G-RAD and S-RAD are non-clairvoyant. Moreover, they provide effective control over the scheduling overhead and ensure efficient utilization of processors. We also analyze the competitiveness of both G-RAD and S-RAD with respect to an optimal clairvoyant scheduler. In terms of makespan, both schemes can achieve O(1)-competitiveness for any set of jobs with arbitrary release time. In terms of mean response time, both schemes are O(1)-competitive for arbitrary batched jobs. To the best of our knowledge, G-RAD and S-RAD are the first non-clairvoyant scheduling algorithms that guarantee provable efficiency, fairness and minimal overhead.

Related Papers

• → MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling(1994)64 cited
• → Hybrid Scheduling and Dual Queue Scheduling(2009)18 cited
• → Analysis of Process Scheduling Algorithm for Multiprocessor System(2018)3 cited
• → On-line Scheduling in Real-Time Multiprocessor Systems(2008)
• Task Scheduling in Multiprocessor Real-Time Systems(2001)