Article

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

Authors:

Theodore P. Baker,

Michele CirineiAuthors Info & Claims

OPODIS'07: Proceedings of the 11th international conference on Principles of distributed systems

Pages 62 - 75

Published: 17 December 2007 Publication History

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-deadline-first (EDF). The contribution is to establish an upper bound on the computational complexity of this problem, for which no algorithm has yet been described. The compute time and storage complexity of the algorithm, which performs an exhaustive search of a very large state space, make it practical only for tasks sets with very small integer periods. However, as a research tool, it can provide a clearer picture than has been previously available of the real success rates of global preemptive priority scheduling policies and low-complexity sufficient tests of schedulability.

References

[1]

Andersson, B., Baruah, S., Jonsson, J.: Static-priority scheduling on multiprocessors. In: Proc. 22nd IEEE Real-Time Systems Symposium, London, UK, pp. 193-202 (2001).

Digital Library

Google Scholar

[2]

Baker, T.P.: An analysis of EDF scheduling on a multiprocessor. IEEE Trans. on Parallel and Distributed Systems 15(8), 760-768 (2005).

Digital Library

Google Scholar

[3]

Baker, T.P.: An analysis of fixed-priority scheduling on a multiprocessor. Real Time Systems (2005).

Digital Library

Google Scholar

[4]

Baker, T.P., Cirinei, M.: A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline tasks. In: Proc. 27th IEEE Real-Time Systems Symposium, Rio de Janeiro, Brazil, IEEE Computer Society Press, Los Alamitos (2006).

Digital Library

Google Scholar

[5]

Baker, T.P., Fisher, N., Baruah, S.: Algorithms for determining the load of a sporadic task system. Technical Report TR-051201, Department of Computer Science, Florida State University, Tallahassee, FL (December 2005).

Google Scholar

[6]

Bemrtogna, M., Cirinei, M., Lipari, G.: Improved schedulability analysis of EDF on multiprocessor platforms. In: Proc. 17th Euromicro Conference on Real-Time Systems, Palma de Mallorca, Spain, pp. 209-218 (July 2005).

Digital Library

Google Scholar

[7]

Bertogna, M., Cirinei, M., Lipari, G.: New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors. In: Proc. 9th International Conf. on Principles of Distributed Systems, Pisa, Italy (December 2005).

Digital Library

Google Scholar

[8]

Cho, S., Lee, S.-K., Han, A., Lin, K.-J.: Efficient real-time scheduling algorithms for multiprocessor systems. IEICE Trans. Communications E85-B(12), 2859-2867 (December 2002).

Google Scholar

[9]

Cirinei, M., Baker, T.P.: EDZL scheduling analysis. In: Proc. EuroMicro Conference on Real-Time Systems, Pisa, Italy (to appear, July 2007).

Digital Library

Google Scholar

[10]

Goossens, J., Funk, S., Baruah, S.: Priority-driven scheduling of periodic task systems on multiprocessors. Real Time Systems 25(2-3), 187-205 (2003).

Digital Library

Google Scholar

[11]

Ha, R., Liu, J.W.S.: Validating timing constraints in multiprocessor and distributed real-time systems. In: Proc. 14th IEEE International Conf. Distributed Computing Systems, Poznan, Poland, pp. 162-171. IEEE Computer Society Press, Los Alamitos (1994).

Google Scholar

[12]

Johnson, H.H., Maddison, M.S.: Deadline scheduling for a real-time multiprocessor. In: Proc. Eurocomp Conference, pp. 139-153 (1974).

Google Scholar

[13]

Piao, X., Han, S., Kim, H., Park, M., Cho, Y., Cho, S.: Predictability of earliest deadline zero laxity algorithm for multiprocessor real time systems. In: Proc. 9th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing, Gjeongju, Korea, IEEE Computer Society Press, Los Alamitos (April 2006).

Digital Library

Google Scholar

[14]

Srinivasan, A., Baruah, S.: Deadline-based scheduling of periodic task systems on multiprocessors. Information Processing Letters 84, 93-98 (2002).

Digital Library

Google Scholar

Cited By

View all

Zhou QLi JLi G(2021)Excluding Parallel Execution to Improve Global Fixed Priority Response Time AnalysisACM Transactions on Embedded Computing Systems10.1145/347703520:5s(1-24)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3477035
Sun YDi Natale MHaddad HWainwright RChbeir R(2018)Assessing the pessimism of current multicore global fixed-priority schedulability analysisProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167195(575-583)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167195
Andersson BRaravi GPlantec ASinghoff FFaucou SPinho L(2016)Scheduling Constrained-Deadline Parallel Tasks on Two-type Heterogeneous MultiprocessorsProceedings of the 24th International Conference on Real-Time Networks and Systems10.1145/2997465.2997482(247-256)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2997465.2997482
Show More Cited By

Recommendations

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-...
An analysis of global edf schedulability for arbitrary-deadline sporadic task systems

Recent results on the global multiprocessor edf scheduling of sporadic task systems are, for the most part, applicable only to task systems in which each task's relative deadline parameter is constrained to be no larger than its minimum inter-arrival ...
LLF Schedulability Analysis on Multiprocessor Platforms
RTSS '10: Proceedings of the 2010 31st IEEE Real-Time Systems Symposium

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

OPODIS'07: Proceedings of the 11th international conference on Principles of distributed systems

December 2007

457 pages

ISBN:354077095X

Editors:
Eduardo Tovar
Polytechnic Institute of Porto, ISEP, Department of Computer Engineering, Porto, Portugal
,
Philippas Tsigas
Chalmers University of Technology, Department of Computer Science & Engineering, Göteborg, Sweden
,
Hacène Fouchal
GRIMAAG, Université des Antilles et de Guyane, Guadeloupe, France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 December 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
2
Total Downloads

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

Reflects downloads up to 28 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhou QLi JLi G(2021)Excluding Parallel Execution to Improve Global Fixed Priority Response Time AnalysisACM Transactions on Embedded Computing Systems10.1145/347703520:5s(1-24)Online publication date: 17-Sep-2021
https://dl.acm.org/doi/10.1145/3477035
Sun YDi Natale MHaddad HWainwright RChbeir R(2018)Assessing the pessimism of current multicore global fixed-priority schedulability analysisProceedings of the 33rd Annual ACM Symposium on Applied Computing10.1145/3167132.3167195(575-583)Online publication date: 9-Apr-2018
https://dl.acm.org/doi/10.1145/3167132.3167195
Andersson BRaravi GPlantec ASinghoff FFaucou SPinho L(2016)Scheduling Constrained-Deadline Parallel Tasks on Two-type Heterogeneous MultiprocessorsProceedings of the 24th International Conference on Real-Time Networks and Systems10.1145/2997465.2997482(247-256)Online publication date: 19-Oct-2016
https://dl.acm.org/doi/10.1145/2997465.2997482
Davis RBertogna MBonifaci V(2016)On the compatibility of exact schedulability tests for global fixed priority pre-emptive scheduling with Audsley's optimal priority assignment algorithmReal-Time Systems10.1007/s11241-015-9241-052:1(113-122)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1007/s11241-015-9241-0
Burmyakov ABini ETovar EForget J(2015)An exact schedulability test for global FP using state space pruningProceedings of the 23rd International Conference on Real Time and Networks Systems10.1145/2834848.2834877(225-234)Online publication date: 4-Nov-2015
https://dl.acm.org/doi/10.1145/2834848.2834877
Huang WChen JForget J(2015)Response time bounds for sporadic arbitrary-deadline tasks under global fixed-priority scheduling on multiprocessorsProceedings of the 23rd International Conference on Real Time and Networks Systems10.1145/2834848.2834849(215-224)Online publication date: 4-Nov-2015
https://dl.acm.org/doi/10.1145/2834848.2834849
Sun YLipari GJan MBen Hedia BGoossens JMaiza C(2014)A Weak Simulation Relation for Real-Time Schedulability Analysis of Global Fixed Priority Scheduling Using Linear Hybrid AutomataProceedings of the 22nd International Conference on Real-Time Networks and Systems10.1145/2659787.2659814(35-44)Online publication date: 8-Oct-2014
https://dl.acm.org/doi/10.1145/2659787.2659814
Nelis VYomsi PGoossens JAuguin Mde Simone RDavis RGrolleau E(2013)Feasibility intervals for homogeneous multicores, asynchronous periodic tasks, and FJP schedulersProceedings of the 21st International conference on Real-Time Networks and Systems10.1145/2516821.2516848(277-286)Online publication date: 16-Oct-2013
https://dl.acm.org/doi/10.1145/2516821.2516848
de Oliveira RCarminati AStarke R(2013)On using adversary simulators to evaluate global fixed-priority and FPZL scheduling of multiprocessorsJournal of Systems and Software10.1016/j.jss.2012.09.00286:2(403-411)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.jss.2012.09.002
de Oliveira RCarminati AStarke ROssowski SLecca P(2012)On using adversary simulators to obtain tight lower bounds for response timesProceedings of the 27th Annual ACM Symposium on Applied Computing10.1145/2245276.2232029(1573-1579)Online publication date: 26-Mar-2012
https://dl.acm.org/doi/10.1145/2245276.2232029
Show More Cited By

Abstract

References

Cited By

Recommendations