Tardiness Bounds under Global EDF Scheduling on a Multiprocessor
- 4 October 2006
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 330-341
- https://doi.org/10.1109/rtss.2005.39
Abstract
This paper considers the scheduling of soft real-time sporadic task systems under global EDF on an identical multiprocessor. Prior research on global EDF has focussed mostly on hard real-time systems, where, to ensure that all deadlines are met, approximately 50% of the available processing capacity will have to be sacrificed in the worst case. This may be overkill for soft real-time systems that can tolerate bounded tardiness. In this paper, we derive tardiness bounds under preemptive and non-preemptive global EDF on multiprocessors when the total utilization of a task system is not restricted and may equal the number of processors. Our tardiness bounds depend on per-task utilizations and execution costs — the lower these values, the lower the tardiness bounds. As a final remark, we note that global EDF may be superior to partitioned EDF for multiprocessor-based soft real-time systems in that the latter does not offer any scope to improve system utilization even if bounded tardiness can be tolerated.Keywords
This publication has 13 references indexed in Scilit:
- Improved Schedulability Analysis of EDF on Multiprocessor PlatformsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- An EDF-based Scheduling Algorithm for Multiprocessor Soft Real-Time SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Static-priority scheduling on multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Real Time Scheduling Theory: A Historical PerspectiveReal-Time Systems, 2004
- Multiprocessor EDF and deadline monotonic schedulability analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Efficient scheduling of soft real-time applications on multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Priority-Driven Scheduling of Periodic Task Systems on MultiprocessorsReal-Time Systems, 2003
- Deadline-based scheduling of periodic task systems on multiprocessorsInformation Processing Letters, 2002
- On a Real-Time Scheduling ProblemOperations Research, 1978
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973