Static-priority scheduling on multiprocessors
Top Cited Papers
- 25 August 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 193-202
- https://doi.org/10.1109/real.2001.990610
Abstract
The preemptive scheduling of systems of periodic tasks on a platform comprised of several identical processors is considered. A scheduling algorithm is proposed for static-priority scheduling of such systems; this algorithm is a simple extension of the uniprocessor rate-monotonic scheduling algorithm. It is proven that this algorithm successfully schedules any periodic task system with a worst-case utilization no more than a third the capacity of the multiprocessor platform. It is also shown that no static-priority multiprocessor scheduling algorithm (partitioned or global) can guarantee schedulability for a periodic task set with a utilization higher than one half the capacity of the multiprocessor platform.Keywords
This publication has 13 references indexed in Scilit:
- Static-priority scheduling on multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Minimum and maximum utilization bounds for multiprocessor RM schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor AssignmentReal-Time Systems, 1998
- 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
- On-line scheduling to maximize task completionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- On the competitiveness of on-line real-time task schedulingReal-Time Systems, 1992
- On the complexity of fixed-priority scheduling of periodic, real-time tasksPerformance Evaluation, 1982
- On a Real-Time Scheduling ProblemOperations Research, 1978
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973