TY - GEN
T1 - The global limited preemptive earliest deadline first feasibility of sporadic Real-Time tasks
AU - Thekkilakattil, Abhilash
AU - Baruah, Sanjoy
AU - Dobrin, Radu
AU - Punnekkat, Sasikumar
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/10/21
Y1 - 2014/10/21
N2 - The feasibility of preemptive and non-preemptive scheduling has been well investigated on uniprocessor and multiprocessor platforms under both Fixed Priority Scheduling (FPS) and Earliest Deadline First (EDF) paradigms. While feasibility of limited preemptive scheduling under FPS has been addressed on both uniprocssor and multiprocessor platforms, under EDF it has been investigated only on uniprocessors, and a similar analysis for multiprocessor platforms is still missing. In this paper, we introduce global Limited Preemptive Earliest Deadline First (g-LP-EDF) scheduling, and propose the associated feasibility analysis to complete the above described feasibility analysis spectrum. Specifically, we derive a sufficient condition that guarantees g-LP-EDF feasibility of sporadic real-time tasks which directly provides a global Non-Preemptive Earliest Deadline First (g-NP-EDF) feasibility test. We then study the interplay between g-LP-EDF feasibility and processor speed, in order to quantify the sub-optimality of g-NP-EDF in terms of the minimum speed-up required to guarantee g-NP-EDF feasibility of all feasible task sets. The results presented in this paper complement our previous results on uniprocessors, and provide a unified result on the sub-optimality of non-preemptive EDF on both uniprocessor and multiprocessor platforms.
AB - The feasibility of preemptive and non-preemptive scheduling has been well investigated on uniprocessor and multiprocessor platforms under both Fixed Priority Scheduling (FPS) and Earliest Deadline First (EDF) paradigms. While feasibility of limited preemptive scheduling under FPS has been addressed on both uniprocssor and multiprocessor platforms, under EDF it has been investigated only on uniprocessors, and a similar analysis for multiprocessor platforms is still missing. In this paper, we introduce global Limited Preemptive Earliest Deadline First (g-LP-EDF) scheduling, and propose the associated feasibility analysis to complete the above described feasibility analysis spectrum. Specifically, we derive a sufficient condition that guarantees g-LP-EDF feasibility of sporadic real-time tasks which directly provides a global Non-Preemptive Earliest Deadline First (g-NP-EDF) feasibility test. We then study the interplay between g-LP-EDF feasibility and processor speed, in order to quantify the sub-optimality of g-NP-EDF in terms of the minimum speed-up required to guarantee g-NP-EDF feasibility of all feasible task sets. The results presented in this paper complement our previous results on uniprocessors, and provide a unified result on the sub-optimality of non-preemptive EDF on both uniprocessor and multiprocessor platforms.
KW - Global Limited Preemptive EDF
KW - Global Non-preemptive EDF
KW - Multiprocessor Scheduling
KW - Resource Augmentation
UR - https://www.scopus.com/pages/publications/84910026054
U2 - 10.1109/ECRTS.2014.21
DO - 10.1109/ECRTS.2014.21
M3 - Conference contribution
AN - SCOPUS:84910026054
T3 - Proceedings - Euromicro Conference on Real-Time Systems
SP - 301
EP - 310
BT - Proceedings - Euromicro Conference on Real-Time Systems
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 26th Euromicro Conference on Real-Time Systems, ECRTS 2014
Y2 - 8 July 2014 through 11 July 2014
ER -