On-line scheduling on uniform multiprocessors
- 1 January 2001
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 35, 183-192
- https://doi.org/10.1109/real.2001.990609
Abstract
Each processor in a uniform multiprocessor machine is characterized by a speed or computing capacity, with the interpretation that a job executing on a processor with speed s for t time units completes (s/spl times/t) units of execution. The on-line scheduling of hard-real-time systems, in which all jobs must complete by specified deadlines, on uniform multiprocessor machines is considered It is known that online algorithms tend to perform very poorly in scheduling such hard-real-time systems on multiprocessors; resource-augmentation techniques are presented here that permit online algorithms to perform better than may be expected given the inherent limitations. Results derived here are applied to the scheduling of periodic task systems on uniform multiprocessor machines.Keywords
This publication has 9 references indexed in Scilit:
- Optimal reward-based scheduling of periodic real-time tasksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On-line scheduling of real-time tasksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Early-release fair schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Architecture and design of AlphaServer GS320ACM SIGPLAN Notices, 2000
- Optimal time-critical scheduling via resource augmentation (extended abstract)Published by Association for Computing Machinery (ACM) ,1997
- Proportionate progress: A notion of fairness in resource allocationAlgorithmica, 1996
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a SurveyPublished by Elsevier ,1979
- A Level Algorithm for Preemptive SchedulingJournal of the ACM, 1977
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973