Provably Efficient Online Nonclairvoyant Adaptive Scheduling

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2008-09, Vol.19 (9), p.1263-1279
Main Authors: He, Yuxiong, Hsu, Wen-Jing, Leiserson, Charles E.
Format: Article
Language:English
Subjects:
Adaptive scheduling
Algorithms
Allocations
Delay
Feedback
Multiple Data Stream Architectures (Multiprocessors)
Multiprogramming
On-line systems
Optimal scheduling
Optimization
Processor scheduling
Processors
Protocols
Quantum computing
Scheduling
Scheduling algorithm
Scheduling and task partitioning
Studies
Workload
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2008.39