Article

A Necessary and Sometimes Sufficient Condition for the Feasibility of Sets of Sporadic Hard-Deadline Tasks

Authors:

Theodore P. Baker,

Michele CirineiAuthors Info & Claims

RTSS '06: Proceedings of the 27th IEEE International Real-Time Systems Symposium

Pages 178 - 190

https://doi.org/10.1109/RTSS.2006.7

Published: 05 December 2006 Publication History

Publisher Site

Abstract

This report describes a necessary condition for feasibility of scheduling a set of sporadic hard-deadline tasks on identical multiprocessor platforms, which is also a sufficient condition if there is only a single processor. The key contribution is the characterization of the maximum, over all time intervals of a given length, of the amount of computation that must be completed to meet all deadlines, and a method of computing this function efficiently to any desired degree of accuracy. Empirical data are provided to verify that the new infeasibility test can be computed efficiently and is an improvement over previously known checks for infeasibility.

Cited By

View all

(2017)Time-Reversibility for Real-Time Scheduling on Multiprocessor SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.253361528:1(230-243)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2533615
Lee JShin I(2014)Demand-based schedulability analysis for real-time multi-core schedulingJournal of Systems and Software10.5555/2747476.274753089:C(99-108)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.5555/2747476.2747530
Lee JEaswaran AShin I(2014)Contention-free executions for real-time multiprocessor schedulingACM Transactions on Embedded Computing Systems10.1145/249453013:2s(1-25)Online publication date: 27-Jan-2014
https://dl.acm.org/doi/10.1145/2494530
Show More Cited By

Index Terms

Recommendations

The Global Limited Preemptive Earliest Deadline First Feasibility of Sporadic Real-Time Tasks
AGILE '14: Proceedings of the 2014 Agile Conference

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 ...
Brute-force determination of multiprocessor schedulability for sets of sporadic hard-deadline tasks
OPODIS'07: Proceedings of the 11th international conference on Principles of distributed systems

This report describes a necessary and sufficient test for the schedulability of a set of sporadic hard-deadline tasks on a multiprocessor platform, using any of a variety of scheduling policies including global fixed task-priority and earliest-deadline-...
Brute-Force Determination of Multiprocessor Schedulability for Sets of Sporadic Hard-Deadline Tasks
Principles of Distributed Systems
Abstract
This report describes a necessary and sufficient test for the schedulability of a set of sporadic hard-deadline tasks on a multiprocessor platform, using any of a variety of scheduling policies including global fixed task-priority and earliest-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

RTSS '06: Proceedings of the 27th IEEE International Real-Time Systems Symposium

December 2006

466 pages

ISBN:0769527612

Publisher

IEEE Computer Society

United States

Publication History

Published: 05 December 2006

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

(2017)Time-Reversibility for Real-Time Scheduling on Multiprocessor SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.253361528:1(230-243)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TPDS.2016.2533615
Lee JShin I(2014)Demand-based schedulability analysis for real-time multi-core schedulingJournal of Systems and Software10.5555/2747476.274753089:C(99-108)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.5555/2747476.2747530
Lee JEaswaran AShin I(2014)Contention-free executions for real-time multiprocessor schedulingACM Transactions on Embedded Computing Systems10.1145/249453013:2s(1-25)Online publication date: 27-Jan-2014
https://dl.acm.org/doi/10.1145/2494530
Davis RBurns A(2011)A survey of hard real-time scheduling for multiprocessor systemsACM Computing Surveys10.1145/1978802.197881443:4(1-44)Online publication date: 18-Oct-2011
https://dl.acm.org/doi/10.1145/1978802.1978814
Lee JEaswaran AShin ILee I(2011)Zero-laxity based real-time multiprocessor schedulingJournal of Systems and Software10.1016/j.jss.2011.07.00284:12(2324-2333)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1016/j.jss.2011.07.002
Baker TBaruah S(2009)An analysis of global edf schedulability for arbitrary-deadline sporadic task systemsReal-Time Systems10.1007/s11241-009-9075-843:1(3-24)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1007/s11241-009-9075-8
Fisher NBaruah S(2009)The feasibility of general task systems with precedence constraints on multiprocessor platformsReal-Time Systems10.1007/s11241-008-9054-541:1(1-26)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1007/s11241-008-9054-5
Baker TCirinei MBertogna M(2008)EDZL scheduling analysisReal-Time Systems10.1007/s11241-008-9061-640:3(264-289)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1007/s11241-008-9061-6
Baker TCirinei M(2007)Brute-force determination of multiprocessor schedulability for sets of sporadic hard-deadline tasksProceedings of the 11th international conference on Principles of distributed systems10.5555/1782394.1782399(62-75)Online publication date: 17-Dec-2007
https://dl.acm.org/doi/10.5555/1782394.1782399
Baker TCirinei M(2007)Brute-Force Determination of Multiprocessor Schedulability for Sets of Sporadic Hard-Deadline TasksPrinciples of Distributed Systems10.1007/978-3-540-77096-1_5(62-75)Online publication date: 17-Dec-2007
https://dl.acm.org/doi/10.1007/978-3-540-77096-1_5

Abstract

Cited By

Index Terms

Recommendations

The Global Limited Preemptive Earliest Deadline First Feasibility of Sporadic Real-Time Tasks

Brute-force determination of multiprocessor schedulability for sets of sporadic hard-deadline tasks

Brute-Force Determination of Multiprocessor Schedulability for Sets of Sporadic Hard-Deadline Tasks

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations