Haibo Zeng
Skip Abstract Section
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.
- Absint. 2014. Stackanalyzer. http://www.absint.com.Google Scholar
- 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.Google Scholar
- Autosar Consortium. 2014. The autosar standard, specification version 4.1. http://www.autosar.org.Google Scholar
- S. Baruah. 2005. The limited-preemption uniprocessor scheduling of sporadic task systems. In Proceedings of the 17th Euromicro Conference on Real-Time Systems. Google ScholarDigital Library
- M. Bertogna, G. Buttazzo, and G. Yao. 2011. Improving feasibility of fixed priority tasks using non-preemptive regions. In Proceedings of the 32nd IEEE Real-Time Systems Symposium. Google ScholarDigital Library
- 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 20th Euromicro Conference on Real-Time Systems. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- A. Burns. 1995. Preemptive priority-based scheduling: An appropriate engineering approach. In Advances in Real-Time System, Prentice-Hall, 225--248. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- J. Chen, A. Harji, and P. Buhr. 2005. Solution space for fixed-priority with preemption threshold. In Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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 22nd IEEE Real-Time Systems Symposium. Google ScholarDigital Library
- R. Ghattas and A. G. Dean. 2007. Preemption threshold scheduling: Stack optimality, enhancements and analysis. In Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium. Google ScholarDigital Library
- 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 27th IEEE International Real-Time Systems Symposium. Google ScholarDigital Library
- 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 4th International Workshop on Software Engineering for Automotive Systems. Google ScholarDigital Library
- W. Lamie. 2013. Preemption-threshold. Express Logic, white paper. http://rtos.com/articles/18833.Google Scholar
- 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. Google ScholarDigital Library
- Mathworks. 2014. The mathworks simulink and stateflow user's manuals. http://www.mathworks.com.Google Scholar
- OSEK. 2006. OSEK/VDX operating systems specification, version 2.2.3. http://www.osek-vdx.org.Google Scholar
- J. Regehr. 2002. Scheduling tasks with mixed preemption relations for robustness to timing faults. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02). Google ScholarDigital Library
- M. Saksena and Y. Wang. 2000. Scalable real-time system design using preemption thresholds. In Proceedings of the 21st IEEE Real-time Systems Symposium (RTSS'00). Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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 6th ACM/IEEE International Conference on Embedded Software. Google ScholarDigital Library
- S. Vestal. 2007. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the 28th IEEE International Real-Time Systems Symposium (RTSS'07). 239--243. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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 32nd IEEE Real-Time Systems Symposium (RTSS'11). Google ScholarDigital Library
- Y. Wang and M. Saksena. 1999. Scheduling fixed-priority tasks with preemption threshold. In Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications. Google ScholarDigital Library
- G. Yao and G. Buttazzo. 2010. Reducing stack with intra-task threshold priorities in real-time systems. In Proceedings of the 10th ACM International Conference on Embedded Software. Google ScholarDigital Library
- G. Yao, G. Buttazzo, and M. Bertogna. 2009. Bounding the maximum length of non-preemptive regions under fixed priority scheduling. In Proceedings of the 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Google ScholarDigital Library
- 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.Google Scholar
- 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. Google ScholarDigital Library
- 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 9th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'13). 227--236.Google Scholar
- 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. Google ScholarDigital Library
Index Terms
- Minimizing Stack and Communication Memory Usage in Real-Time Embedded Applications
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 PapersMulticore 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