research-article

Minimizing Stack and Communication Memory Usage in Real-Time Embedded Applications

Authors:

Marco Di Natale,

Qi ZhuAuthors Info & Claims

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

Article No.: 149, Pages 1 - 25

https://doi.org/10.1145/2632160

Published: 23 July 2014 Publication History

Abstract

In the development of real-time embedded applications, especially those on systems-on-chip, an efficient use of RAM memory is as important as the effective scheduling of the computation resources. The protection of communication and state variables accessed by concurrent tasks must provide real-time schedulability guarantees while using the least amount of memory. Several schemes, including preemption thresholds, have been developed to improve schedulability and save stack space by selectively disabling preemption. However, the design synthesis problem is still open. In this article, we target the assignment of the scheduling parameters to minimize memory usage for systems of practical interest, including designs compliant with automotive standards. We propose algorithms either proven optimal or shown to improve on randomized optimization methods like simulated annealing.

References

[1]

Absint. 2014. Stackanalyzer. http://www.absint.com.

[2]

N. Audsley. 1991. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Tech. rep. YCS 164, Department of Computer Science, University of York, UK.

[3]

Autosar Consortium. 2014. The autosar standard, specification version 4.1. http://www.autosar.org.

[4]

S. Baruah. 2005. The limited-preemption uniprocessor scheduling of sporadic task systems. In Proceedings of the 17^th Euromicro Conference on Real-Time Systems.

Digital Library

[5]

M. Bertogna, G. Buttazzo, and G. Yao. 2011. Improving feasibility of fixed priority tasks using non-preemptive regions. In Proceedings of the 32^nd IEEE Real-Time Systems Symposium.

Digital Library

[6]

M. Bohlin, K. Hanninen, J. Maki-Turja, J. Carlson, and M. Nolin. 2008. Bounding shared-stack usage in systems with offsets and precedences. In Proceedings of the 20^th Euromicro Conference on Real-Time Systems.

Digital Library

[7]

R. J. Bril, J. J. Lukkien, and W. F. Verhaegh. 2009. Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption. Real-Time Syst. 42, 1--3, 63--119.

Digital Library

[8]

A. Burns. 1995. Preemptive priority-based scheduling: An appropriate engineering approach. In Advances in Real-Time System, Prentice-Hall, 225--248.

Digital Library

[9]

G. Buttazzo, M. Bertogna, and G. Yao. 2013. Limited preemptive scheduling for real-time systems: A survey. IEEE Trans. Industr. Inf. 9, 1, 3--15.

[10]

J. Chen and A. Burns. 1997. A fully asynchronous reader/write mechanism for multiprocessor real-time systems. Tech. rep. YCS 288, Department of Computer Science, University of York, UK.

[11]

J. Chen, A. Harji, and P. Buhr. 2005. Solution space for fixed-priority with preemption threshold. In Proceedings of the 11^th IEEE Real Time on Embedded Technology and Applications Symposium.

Digital Library

[12]

M. Di Natale, L. Guo, H. Zeng, and A. Sangiovanni-Vincentelli. 2010. Synthesis of multitask implementations of simulink models with minimum delays. IEEE Trans. Industr. Inf. 6, 4, 637--651.

[13]

A. Ferrari, M. Di Natale, G. Gentile, G. Reggiani, and P. Gai. 2009. Time and memory tradeoffs in the implementation of autosar components. In Proceedings of the Design, Automation, and Test in Europe Conference.

Digital Library

[14]

P. Gai, G. Lipari, and M. Di Natale. 2001. Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. In Proceedings of the 22^nd IEEE Real-Time Systems Symposium.

Digital Library

[15]

R. Ghattas and A. G. Dean. 2007. Preemption threshold scheduling: Stack optimality, enhancements and analysis. In Proceedings of the 13^th IEEE Real Time and Embedded Technology and Applications Symposium.

Digital Library

[16]

K. Hanninen, J. Maki-Turja, M. Bohlin, J. Carlson, and M. Nolin. 2006. Determining maximum stack usage in preemptive shared stack systems. In Proceedings of the 27^th IEEE International Real-Time Systems Symposium.

Digital Library

[17]

H. Kopetz, R. Obermaisser, C. El Salloum, and B. Huber. 2007. Automotive software development for a multi-core system-on-a-chip. In Proceedings of the 4^th International Workshop on Software Engineering for Automotive Systems.

Digital Library

[18]

W. Lamie. 2013. Preemption-threshold. Express Logic, white paper. http://rtos.com/articles/18833.

[19]

R. Long, H. Li, W. Peng, Y. Zhang, and M. Zhao. 2009. An approach to optimize intra-ecu communication based on mapping of autosar runnable entities. In Proceedings of the International Conference on Embedded Software and Systems.

Digital Library

[20]

Mathworks. 2014. The mathworks simulink and stateflow user's manuals. http://www.mathworks.com.

[21]

OSEK. 2006. OSEK/VDX operating systems specification, version 2.2.3. http://www.osek-vdx.org.

[22]

J. Regehr. 2002. Scheduling tasks with mixed preemption relations for robustness to timing faults. In Proceedings of the 23^rd IEEE Real-Time Systems Symposium (RTSS'02).

Digital Library

[23]

M. Saksena and Y. Wang. 2000. Scalable real-time system design using preemption thresholds. In Proceedings of the 21^st IEEE Real-time Systems Symposium (RTSS'00).

Digital Library

[24]

L. Sha, R. Rajkumar, and J. P. Lehoczky. 1990. Priority inheritance protocols: An approach to real-time synchronization. IEEE Trans. Comput. 39, 9, 1175--1185.

Digital Library

[25]

C. Sofronis, S. Tripakis, and P. Caspi. 2006. A memory-optimal buffering protocol for preservation of synchronous semantics under preemptive scheduling. In Proceedings of the 6^th ACM/IEEE International Conference on Embedded Software.

Digital Library

[26]

S. Vestal. 2007. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the 28^th IEEE International Real-Time Systems Symposium (RTSS'07). 239--243.

Digital Library

[27]

G. Wang, M. Di Natale, and A. Sangiovanni-Vincentelli. 2009. Improving the size of communication buffers in synchronous models with time constraints. IEEE Trans. Industr. Inf. 5, 3, 229--240.

[28]

Q. Wang, J. Song, and G. Parmer. 2011. Execution stack management for hard real-time computation in a component-based os. In Proceedings of the 32^nd IEEE Real-Time Systems Symposium (RTSS'11).

Digital Library

[29]

Y. Wang and M. Saksena. 1999. Scheduling fixed-priority tasks with preemption threshold. In Proceedings of the 6^th International Conference on Real-Time Computing Systems and Applications.

Digital Library

[30]

G. Yao and G. Buttazzo. 2010. Reducing stack with intra-task threshold priorities in real-time systems. In Proceedings of the 10^th ACM International Conference on Embedded Software.

Digital Library

[31]

G. Yao, G. Buttazzo, and M. Bertogna. 2009. Bounding the maximum length of non-preemptive regions under fixed priority scheduling. In Proceedings of the 15^th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications.

Digital Library

[32]

H. Zeng and M. Di Natale. 2012. Efficient implementation of autosar components with minimal memory usage. In Proceedings of the IEEE Symposium on Industrial Embedded Systems.

[33]

H. Zeng and M. Di Natale. 2013. An efficient formulation of the real-time feasibility region for design optimization. IEEE Trans. Comput. 62, 4, 644--661.

Digital Library

[34]

Q. Zhao, Z. Gu, and H. Zeng. 2013a. Integration of resource synchronization and preemption-thresholds into edf-based mixed-criticality scheduling algorithm. In Proceedings of the 9^th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'13). 227--236.

[35]

Q. Zhao, Z. Gu, and H. Zeng. 2013b. PT-AMC: Integrating preemption thresholds into mixed-criticality scheduling. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'13). 141--146.

Digital Library

Cited By

Deng XRaja SZhao YZeng H(2024)Priority Assignment for Global Fixed Priority Scheduling on MultiprocessorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337658843:9(2538-2550)Online publication date: 13-Mar-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3376588
Lee JShin SNejati SBriand L(2022)Optimal priority assignment for real-time systems: a coevolution-based approachEmpirical Software Engineering10.1007/s10664-022-10170-127:6Online publication date: 6-Aug-2022
https://dl.acm.org/doi/10.1007/s10664-022-10170-1
Ben Hafaiedh IBen Slimane M(2020)A Parameterized Formal Model for the Analysis of Preemption-Threshold Scheduling in Real-Time SystemsIEEE Access10.1109/ACCESS.2020.29793548(58180-58193)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2979354
Show More Cited By

Index Terms

Minimizing Stack and Communication Memory Usage in Real-Time Embedded Applications
1. Computer systems organization
  1. Embedded and cyber-physical systems
  2. Real-time systems

Recommendations

Minimizing Stack Memory for Partitioned Mixed-criticality Scheduling on Multiprocessor Platforms
A Mixed-Criticality System (MCS) features the integration of multiple subsystems that are subject to different levels of safety certification on a shared hardware platform. In cost-sensitive application domains such as automotive E/E systems, it is ...
Minimizing Stack Memory for Hard Real-Time Applications on Multicore Platforms with Partitioned Fixed-Priority or EDF Scheduling
Special Section on New Physical Design Techniques for the Next Generation Integration Technology and Regular Papers

Multicore processors are increasingly adopted in resource-constrained real-time embedded applications. In the development of such applications, efficient use of RAM memory is as important as the effective scheduling of software tasks. Preemption ...
Perfecting preemption threshold scheduling for object-oriented real-time system design: from the perspective of real-time synchronization

In spite of the proliferation of object-oriented design methodologies in contemporary software development, their application to real-time embedded systems has been limited because of the practitioner's conservative attitude toward handling timing ...

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 5s

Special Issue on Risk and Trust in Embedded Critical Systems, Special Issue on Real-Time, Embedded and Cyber-Physical Systems, Special Issue on Virtual Prototyping of Parallel and Embedded Systems (ViPES)

November 2014

501 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2660459

Editor:
Sandeep K. Shukla
Virginia Tech, USA

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: 23 July 2014

Accepted: 01 September 2013

Revised: 01 June 2013

Received: 01 October 2012

Published in TECS Volume 13, Issue 5s

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
299
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)3

Reflects downloads up to 25 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Deng XRaja SZhao YZeng H(2024)Priority Assignment for Global Fixed Priority Scheduling on MultiprocessorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337658843:9(2538-2550)Online publication date: 13-Mar-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3376588
Lee JShin SNejati SBriand L(2022)Optimal priority assignment for real-time systems: a coevolution-based approachEmpirical Software Engineering10.1007/s10664-022-10170-127:6Online publication date: 6-Aug-2022
https://dl.acm.org/doi/10.1007/s10664-022-10170-1
Ben Hafaiedh IBen Slimane M(2020)A Parameterized Formal Model for the Analysis of Preemption-Threshold Scheduling in Real-Time SystemsIEEE Access10.1109/ACCESS.2020.29793548(58180-58193)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2979354
Li ZHuang CDong XRen C(2020)Resource-efficient cyber-physical systems design: A surveyMicroprocessors and Microsystems10.1016/j.micpro.2020.10318377(103183)Online publication date: Sep-2020
https://doi.org/10.1016/j.micpro.2020.103183
Zhao YZeng HSangiovanni-Vincentelli ASztipanovits JZhu Q(2019)Optimization techniques for time-critical cyber-physical systemsProceedings of the Workshop on Design Automation for CPS and IoT10.1145/3313151.3313168(41-50)Online publication date: 15-Apr-2019
https://dl.acm.org/doi/10.1145/3313151.3313168
Chai HZhang GSun JVajdi AHua JZhou J(2019)A Review of Recent Techniques in Mixed-Criticality SystemsJournal of Circuits, Systems and Computers10.1142/S021812661930007128:07(1930007)Online publication date: 27-Jun-2019
https://doi.org/10.1142/S0218126619300071
Zhao YZeng H(2019)The Concept of Unschedulability Core for Optimizing Real-Time Systems with Fixed-Priority SchedulingIEEE Transactions on Computers10.1109/TC.2018.287883568:6(926-938)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TC.2018.2878835
Zhao YZeng H(2019)The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systemsReal-Time Systems10.1007/s11241-019-09332-055:3(667-707)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s11241-019-09332-0
Zhao YGala VZeng H(2018)A Unified Framework for Period and Priority Optimization in Distributed Hard Real-Time SystemsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.285738037:11(2188-2199)Online publication date: Nov-2018
https://doi.org/10.1109/TCAD.2018.2857380
Dietrich CLohmann D(2018)Semi-Extended Tasks: Efficient Stack Sharing Among Blocking Threads2018 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS.2018.00049(338-349)Online publication date: Dec-2018
https://doi.org/10.1109/RTSS.2018.00049
Show More Cited By

View Options

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.

Figures

Tables

Media

View Issue’s Table of Contents