research-article

Implementation and evaluation of mixed-criticality scheduling approaches for sporadic tasks

Authors:

Huang-Ming Huang,

Christopher Gill,

Chenyang LuAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 13, Issue 4s

Article No.: 126, Pages 1 - 25

https://doi.org/10.1145/2584612

Published: 01 April 2014 Publication History

Abstract

Traditional fixed-priority scheduling analysis for periodic and sporadic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the chosen scheduling policy, and estimates of tasks' worst-case execution times must be conservative in case a task runs longer than is usual. To address the significant underutilization of a system's resources under normal operating conditions that can arise from these assumptions, several mixed-criticality scheduling approaches have been proposed. However, to date, there have been few quantitative comparisons of system schedulability or runtime overhead for the different approaches.

In this article, we present a side-by-side implementation and evaluation of the known mixed-criticality scheduling approaches, for periodic and sporadic mixed-criticality tasks on uniprocessor systems, under a mixed-criticality scheduling model that is common to all these approaches. To make a fair evaluation of mixed-criticality scheduling, we also address previously open issues and propose modifications to improve particular approaches. Our empirical evaluations demonstrate that user-space implementations of mechanisms to enforce different mixed-criticality scheduling approaches can be achieved atop Linux without kernel modification, with reasonably low (but in some cases nontrivial) overhead for mixed-criticality real-time task sets.

References

[1]

James H. Anderson, Sanjoy Baruah, and Björn B. Brandenburg. 2009. Multicore operating-system support for mixed criticality. In Proceedings of the Workshop on Mixed Criticality: Roadmap to Evolving UAV Certification.

[2]

N. Audsley. 1991. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Tech. Rep. University of York, York, UK. November.

[3]

Sanjoy Baruah and Alan Burns. 2011. Implementing mixed criticality systems in Ada. In Proceedings of the Reliable Software Technologies-Ada-Europe 2011.

Digital Library

[4]

Sanjoy Baruah, Alan Burns, and R. I. Davis. 2011. Response-time analysis for mixed criticality systems. In Proceedings of the Real-Time Systems Symposium. 34--43.

Digital Library

[5]

Sanjoy Baruah, Haohan Li, and Chapel Hill. 2010. Towards the design of certifiable mixed-criticality systems. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium. IEEE Press, 13--22.

Digital Library

[6]

Sanjoy Baruah and Steve Vestal. 2008. Schedulability analysis of sporadic tasks with multiple criticality specifications. In Proceedings of the Euromicro Conference on Real-Time Systems. IEEE Press, 147--155.

Digital Library

[7]

Andrea Bastoni and B. Brandenburg. 2010. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability. In Proceedings of the 6th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications, 33--44.

[8]

Enrico Bini and Giorgio C. Buttazzo. 2005. Measuring the performance of schedulability tests. Real-Time Syst. 30, 1--2, 129--154.

Digital Library

[9]

Alan Burns. 2011. Timing faults and mixed criticality systems. In Dependable and Historic Computing, Lloyd and Jones, Eds., Lecture Notes in Computer Science, vol. 6875, Springer, 147--166.

Digital Library

[10]

Dionisio de Niz, Karthik Lakshmanan, and Ragunathan Rajkumar. 2009. On the scheduling of mixed-criticality real-time task sets. In Proceedings of the Real-Time Systems Symposium. IEEE Press, 291--300.

Digital Library

[11]

N. Fisher, T. P. Baker, and S. Baruah. 2006. Algorithms for determining the demand-based load of a sporadic task system. In Proceedings of RTCSA, 135--146.

Digital Library

[12]

Nan Guan, Pontus Ekberg, Martin Stigge, and Wang Yi. 2011. Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In Proceedings of the Real-Time Systems Symposium, 13--23.

Digital Library

[13]

Huang-Ming Huang, Christopher Gill, and Chenyang Lu. 2012. Implementation and evaluation of mixed-criticality scheduling approaches for periodic tasks. In Proceedings of the Real-Time and Embedded Technology and Applications Symposium, 23--32.

Digital Library

[14]

M. Joseph and P. Pandya. 1986. Finding response times in a real-time system. Comput. J. 29, 5, 390--395.

[15]

Karthik Lakshmanan, Dionisio de Niz, Ragunathan Rajkumar, and Gabriel Moreno. 2010. Resource allocation in distributed mixed-criticality cyber-physical systems. In Proceedings of the International Conference on Distributed Computing Systems. IEEE Press, 169--178.

Digital Library

[16]

Haohan Li and Sanjoy Baruah. 2010a. An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In Proceedings of the Real-Time Systems Symposium. IEEE Press, 183--192.

Digital Library

[17]

Haohan Li and Sanjoy Baruah. 2010b. Load-based schedulability analysis of certifiable mixed-criticality systems. In Proceedings of the 10th ACM International Conference on Embedded Software. ACM, New York, 99--108.

Digital Library

[18]

Jane W. S. W. Liu. 2000. Real-Time Systems 1st Ed. Prentice-Hall, Upper Saddle River, N.J.

[19]

Rodolfo Pellizzoni, Patrick Meredith, Min-Young Nam, Mu Sun, Marco Caccamo, and Lui Sha. 2009. Handling mixed-criticality in SoC-based real-time embedded systems. In Proceedings of the 7th ACM International Conference on Embedded Software. ACM, Press, New York, 235.

Digital Library

[20]

Steven Rostedt and Darren V. Hart. 2007. Internals of the RT patch. In Proceedings of the Linux Symposium.

[21]

Lui Sha, John P. Lehoczky, and Ragunathan Rajkumar. 1986. Solutions for some practical problems. In Proceedings of the Real-Time Systems Symposium. IEEE Press, 181--191.

[22]

Steve Vestal. 2007. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the Real-Time Systems Symposium. IEEE Press, 239--243.

Digital Library

Cited By

Zhang YZheng HGu Z(2023)Energy-Aware Adaptive Mixed-Criticality Scheduling with Semi-Clairvoyance and Graceful DegradationACM Transactions on Embedded Computing Systems10.1145/363274923:1(1-20)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3632749
Chang WChen NZhao SDai X(2023)Evolvement of Scheduling Theories for Autonomous VehiclesMachine Learning and Optimization Techniques for Automotive Cyber-Physical Systems10.1007/978-3-031-28016-0_2(43-80)Online publication date: 27-Mar-2023
https://doi.org/10.1007/978-3-031-28016-0_2
Chen NZhao SGray IBurns AJi SChang W(2022)MSRP-FT: Reliable Resource Sharing on Multiprocessor Mixed-Criticality Systems2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS54340.2022.00024(201-213)Online publication date: May-2022
https://doi.org/10.1109/RTAS54340.2022.00024
Show More Cited By

Index Terms

Implementation and evaluation of mixed-criticality scheduling approaches for sporadic tasks

Recommendations

Corrections to and Discussion of “Implementation and Evaluation of Mixed-criticality Scheduling Approaches for Sporadic Tasks”
Special Issue on Embedded Computing for IoT, Special Issue on Big Data and Regular Papers

The AMC-IA mixed-criticality scheduling analysis was proposed as an improvement to the AMC-MAX adaptive mixed-criticality scheduling analysis. However, we have identified several necessary corrections to the AMC-IA analysis. In this article, we motivate ...
Implementation and Evaluation of Mixed-Criticality Scheduling Approaches for Periodic Tasks
RTAS '12: Proceedings of the 2012 IEEE 18th Real Time and Embedded Technology and Applications Symposium

Traditional fixed-priority scheduling analysis for periodic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the scheduling policy, and ...
Mixed-criticality scheduling in real-time multiprocessor systems
FRUCT '18: Proceedings of the 18th Conference of Open Innovations Association FRUCT

The relevance and popularity of mixed-criticality real-time systems precipitously increase in many industrial domains. Today, mixed-criticality systems are increasingly being implemented on multicore platforms. So, one of the most actual and important ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 13, Issue 4s

Special Issue on Real-Time and Embedded Technology and Applications, Domain-Specific Multicore Computing, Cross-Layer Dependable Embedded Systems, and Application of Concurrency to System Design (ACSD'13)

July 2014

571 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2601432

Editors:
Sandeep K. Shukla
Virginia Tech, USA
,
Josep Carmona
Universitat Politècnica de Catalunya, Spain
,
Mihai Teodor Lazarescu
Politecnico di Torino, Italy
,
Marta Pietkiewicz-koutny
Newcastle University, UK

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 April 2014

Accepted: 01 March 2013

Revised: 01 February 2013

Received: 01 July 2012

Published in TECS Volume 13, Issue 4s

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Division of Computer and Network Systems

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
343
Total Downloads

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

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YZheng HGu Z(2023)Energy-Aware Adaptive Mixed-Criticality Scheduling with Semi-Clairvoyance and Graceful DegradationACM Transactions on Embedded Computing Systems10.1145/363274923:1(1-20)Online publication date: 13-Nov-2023
https://dl.acm.org/doi/10.1145/3632749
Chang WChen NZhao SDai X(2023)Evolvement of Scheduling Theories for Autonomous VehiclesMachine Learning and Optimization Techniques for Automotive Cyber-Physical Systems10.1007/978-3-031-28016-0_2(43-80)Online publication date: 27-Mar-2023
https://doi.org/10.1007/978-3-031-28016-0_2
Chen NZhao SGray IBurns AJi SChang W(2022)MSRP-FT: Reliable Resource Sharing on Multiprocessor Mixed-Criticality Systems2022 IEEE 28th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS54340.2022.00024(201-213)Online publication date: May-2022
https://doi.org/10.1109/RTAS54340.2022.00024
Pavic IDzapo H(2021)Framework for Evaluation of Schedulability Tests for Mixed-Criticality Systems2021 44th International Convention on Information, Communication and Electronic Technology (MIPRO)10.23919/MIPRO52101.2021.9596794(886-891)Online publication date: 27-Sep-2021
https://doi.org/10.23919/MIPRO52101.2021.9596794
Hussain IAwan MSouto PBletsas KAkesson BTovar EErmont JSong YGill C(2019)Response time analysis of multiframe mixed-criticality systemsProceedings of the 27th International Conference on Real-Time Networks and Systems10.1145/3356401.3356405(8-18)Online publication date: 6-Nov-2019
https://dl.acm.org/doi/10.1145/3356401.3356405
Hu BThiele LHuang PHuang KGriesbeck CKnoll A(2019)FFOBReal-Time Systems10.1007/s11241-018-9323-x55:3(471-513)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s11241-018-9323-x
Li TZhang TYu GZhang YSong J(2018)TA-MCF: Thermal-Aware Fluid Scheduling for Mixed-Criticality SystemJournal of Circuits, Systems and Computers10.1142/S021812661950029428:02(1950029)Online publication date: 12-Nov-2018
https://doi.org/10.1142/S0218126619500294
Sha SWen WRen SQuan G(2018)M-Oscillating: Performance Maximization on Temperature-Constrained Multi-Core ProcessorsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.283547429:11(2528-2539)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1109/TPDS.2018.2835474
Awan MBletsas KSouto PAkesson BTovar E(2018)Mixed-Criticality Scheduling with Dynamic Memory Bandwidth Regulation2018 IEEE 24th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)10.1109/RTCSA.2018.00022(111-117)Online publication date: Aug-2018
https://doi.org/10.1109/RTCSA.2018.00022
Chen TPhan L(2018)SafeMC: A System for the Design and Evaluation of Mode-Change Protocols2018 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2018.00021(105-116)Online publication date: Apr-2018
https://doi.org/10.1109/RTAS.2018.00021
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents