Article

New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors

Authors:

Marko Bertogna,

Michele Cirinei,

Giuseppe LipariAuthors Info & Claims

OPODIS'05: Proceedings of the 9th international conference on Principles of Distributed Systems

Pages 306 - 321

https://doi.org/10.1007/11795490_24

Published: 12 December 2005 Publication History

Publisher Site

Abstract

In this paper, we address the problem of schedulability analysis of a set of real-time periodic (or sporadic) tasks on multiprocessor hardware platforms, under fixed priority global scheduling. In a multiprocessor system with M processors, a global scheduler consists of a single queue of ready tasks for all processors, and the scheduler selects the first M tasks to execute on the M processors. We allow preemption and migration of tasks between processors.

This paper presents two different contributions. First, we derive a sufficient schedulability test for periodic and sporadic task system scheduled with fixed priority when priorities are assigned according to Deadline Monotonic. This test is efficient when dealing with heavy tasks (i.e. tasks with high utilization). Then, we develop an independent analysis for preperiod deadline systems. This leads to a new schedulability test with density and utilization bounds that are tighter than the existing ones.

References

[1]

Baruah, S., Cohen, N., Plaxton, C., Varvel, D.: Proportionate progress: A notion of fairness in resource allocation. Algorithmica 6 (1996).

Google Scholar

[2]

Dhall, S.K., Liu, C.L.: On a real-time scheduling problem. Operations Research 26 (1978).

Google Scholar

[3]

Andersson, B., Baruah, S., Jonsson, J.: Static-priority scheduling on multiprocessors. In IEEE, ed.: Proceedings of the IEEE Real-Time Systems Symposium. (2001).

Digital Library

Google Scholar

[4]

Baker, T.: Multiprocessor EDF and deadline monotonic schedulability analysis. In: Proceedings of the 24th IEEE International Real-Time Systems Symposium, RTSS'03. (2003).

Digital Library

Google Scholar

[5]

Bertogna, M., Cirinei, M., Lipari, G.: Improved schedulability analysis of EDF on multiprocessor platforms. In: Proceedings of the IEEE Euromicro Conference on Real Time Systems, Mallorca, Spain, IEEE (2005).

Digital Library

Google Scholar

[6]

Andersson, B.: Static-priority scheduling on multiprocessors. PhD thesis, Department of Computer Engineering, Chalmer University of Technology, Goteborg, Sweden (2003).

Google Scholar

[7]

Baker, T.: An analysis of deadline-monotonic schedulability on a multiprocessor. FSU computer science technical report, Department of Computer Science, Florida State University, Tallahassee, Florida (2003) available at http://www.cs.fsu.edu/research/reports.

Google Scholar

[8]

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

Digital Library

Google Scholar

[9]

Baruah, S.K.: Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors. IEEE Trans. Computers 53(6) (2004) 781-784.

Digital Library

Google Scholar

[10]

Srinivasan, A., Baruah, S.K.: Deadline-based scheduling of periodic task systems on multiprocessors. Inf. Process. Lett. 84(2) (2002) 93-98.

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
Han DLi GZhou QLi JYang YHu X(2021)An Efficient Execution Framework of Two-Part Execution Scenario AnalysisACM Transactions on Design Automation of Electronic Systems10.1145/346547427:1(1-24)Online publication date: 13-Sep-2021
https://dl.acm.org/doi/10.1145/3465474
Thekkilakattil ADavis RDobrin RPunnekkat SBertogna MForget J(2015)Multiprocessor fixed priority scheduling with limited preemptionsProceedings of the 23rd International Conference on Real Time and Networks Systems10.1145/2834848.2834855(13-22)Online publication date: 4-Nov-2015
https://dl.acm.org/doi/10.1145/2834848.2834855
Show More Cited By

New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors

Recommendations

Global deadline-monotonic scheduling of arbitrary-deadline sporadic task systems
OPODIS'07: Proceedings of the 11th international conference on Principles of distributed systems

The multiprocessor Deadline-Monotonic scheduling of sporadic task systems is studied. A new sufficient schedulability test is presented and proved correct. It is shown that this test offers non-trivial quantitative guarantees, including a processor ...
Exact schedulability tests for real-time scheduling of periodic tasks on unrelated multiprocessor platforms

In this paper, we study the global scheduling of periodic task systems on unrelated multiprocessor platforms. We first show two general properties which are well known for uniprocessor platforms and which are also true for unrelated multiprocessor ...
Flexible tardiness bounds for sporadic real-time task systems on multiprocessors
IPDPS'06: Proceedings of the 20th international conference on Parallel and distributed processing

The earliest-deadline-first (EDF) scheduling of a sporadic real-time task system on a multiprocessor may require that the total utilization of the task system, U_sum, not exceed (m+1)/2 on m processors if every deadline needs to be met. In recent work, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

OPODIS'05: Proceedings of the 9th international conference on Principles of Distributed Systems

December 2005

442 pages

ISBN:3540363211

Editors:
James H. Anderson
Department of Computer Science, University of North Carolina at Chapel Hill
,
Giuseppe Prencipe
Department of Computer Science, Università di Pisa, Italy
,
Roger Wattenhofer
Department of Computer Science, ETH Zurich, Zurich, Switzerland

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 December 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 24 Nov 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
Han DLi GZhou QLi JYang YHu X(2021)An Efficient Execution Framework of Two-Part Execution Scenario AnalysisACM Transactions on Design Automation of Electronic Systems10.1145/346547427:1(1-24)Online publication date: 13-Sep-2021
https://dl.acm.org/doi/10.1145/3465474
Thekkilakattil ADavis RDobrin RPunnekkat SBertogna MForget J(2015)Multiprocessor fixed priority scheduling with limited preemptionsProceedings of the 23rd International Conference on Real Time and Networks Systems10.1145/2834848.2834855(13-22)Online publication date: 4-Nov-2015
https://dl.acm.org/doi/10.1145/2834848.2834855
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
Davis RBurns AMarinho JNelis VPetters SBertogna M(2015)Global and Partitioned Multiprocessor Fixed Priority Scheduling with Deferred PreemptionACM Transactions on Embedded Computing Systems10.1145/273995414:3(1-28)Online publication date: 21-Apr-2015
https://dl.acm.org/doi/10.1145/2739954
Kim JKim HLakshmanan KRajkumar RLu CKumar PStoleru R(2013)Parallel scheduling for cyber-physical systemsProceedings of the ACM/IEEE 4th International Conference on Cyber-Physical Systems10.1145/2502524.2502530(31-40)Online publication date: 8-Apr-2013
https://dl.acm.org/doi/10.1145/2502524.2502530
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
Bertogna MBaruah S(2011)Tests for global EDF schedulability analysisJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2010.09.00457:5(487-497)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.sysarc.2010.09.004
Faggioli DBertogna MChecconi FShin SOssowski SSchumacher MPalakal MHung C(2010)Sporadic Server revisitedProceedings of the 2010 ACM Symposium on Applied Computing10.1145/1774088.1774160(340-345)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1774088.1774160
Baker T(2010)What to make of multicore processors for reliable real-time systems?Proceedings of the 15th Ada-Europe international conference on Reliable Software Technologies10.1007/978-3-642-13550-7_1(1-18)Online publication date: 14-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13550-7_1
Show More Cited By

Abstract

References

Cited By

Recommendations

Global deadline-monotonic scheduling of arbitrary-deadline sporadic task systems

Exact schedulability tests for real-time scheduling of periodic tasks on unrelated multiprocessor platforms

Flexible tardiness bounds for sporadic real-time task systems on multiprocessors

Comments

Information

Published In

Sponsors

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