ABSTRACT
Mixed-criticality is a significant recent trend in the embedded system industry, where common computing platforms are utilized to host functionalities of varying criticality levels. To date, most scheduling techniques have focused on the timing aspect of this problem, while functional safety (i.e. fault-tolerance) is often neglected.
This paper presents design methodologies to guarantee both safety and schedulability for real-time mixed-criticality systems on identical multicores. Assuming hardware/software transient errors, we model safety requirements on different criticality levels explicitly according to safety standards; based on this, we further propose fault-tolerant mixed-criticality scheduling techniques with task replication and re-execution to enhance system safety. To cope with runtime urgencies where critical tasks do not succeed after a certain number of trials, our techniques can perform system reconfigurations (task killing or service degradation) in those situations to reallocate system resources to the critical tasks. Due to explicit modeling of safety, we can quantify the impact of task killing and service degradation on system feasibility (safety and schedulability), enabling a rigorous design. To this end, we derive analysis techniques when reconfigurations are triggered either globally (synchronously) on all cores or locally (asynchronously) on each core. To our best knowledge, this is the first work on fault-tolerant mixed-criticality scheduling on multicores, matching theoretical insights with industrial safety standards. Our proposed techniques are validated with an industrial application and extensive simulations.
- Genetic Algorithm. http://ch.mathworks.com/help/gads/genetic-algorithm.html.Google Scholar
- ISO---26262 Road Vehicles - Functional Safety.Google Scholar
- RTCA/DO-178B, Software Considerations in Airborne Systems and Equipment Certification, 1992.Google Scholar
- Safeadapt, 2016. http://www.safeadapt.eu/.Google Scholar
- Authors removed due to blind review. Towards the Design of Fault-Tolerant Mixed-Criticality Systems on Multicores. https://www.dropbox.com/s/u67yyko4lncfsp8/report.pdf?dl=0.Google Scholar
- S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, S. Van Der Ster, and L. Stougie. The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In Real-Time Systems (ECRTS), 2012 24th Euromicro Conference on, pages 145--154. IEEE, 2012. Google ScholarDigital Library
- S. Baruah, B. Chattopadhyay, H. Li, and I. Shin. Mixed-criticality scheduling on multiprocessors. Real-Time Systems, 50(1):142--177, 2014. Google ScholarDigital Library
- S. Baruah and S. Vestal. Schedulability analysis of sporadic tasks with multiple criticality specifications. In Real-Time Systems, 2008. ECRTS'08. Euromicro Conference on, pages 147--155. IEEE, 2008. Google ScholarDigital Library
- V. Bonifaci, G. D'Angelo, A. Marchetti-Spaccamela, S. van der Ster, and L. Stougie. Mixed-criticality scheduling of sporadic task systems. eraerts, page 204, 2011.Google Scholar
- S. Brown. Overview of iec 61508. design of electrical/electronic/programmable electronic safety-related systems. Computing & Control Engineering Journal, 11(1):6--12, 2000.Google ScholarCross Ref
- A. Burns and R. Davis. Mixed criticality systems-a review. Department of Computer Science, University of York, Tech. Rep, 2016.Google Scholar
- A. Burns, R. Davis, et al. Mixed criticality on controller area network. In Real-Time Systems (ECRTS), 2013 25th Euromicro Conference on, pages 125--134. IEEE, 2013. Google ScholarDigital Library
- A. Burns, J. Harbin, and L. Indrusiak. A wormhole noc protocol for mixed criticality systems. In Real-Time Systems Symposium (RTSS), 2014 IEEE, pages 184--195. IEEE, 2014.Google ScholarCross Ref
- P. Ekberg and W. Yi. Outstanding paper award: Bounding and shaping the demand of mixed-criticality sporadic tasks. In Real-Time Systems (ECRTS), 2012 24th Euromicro Conference on, pages 135--144. IEEE, 2012. Google ScholarDigital Library
- Mixed Criticality Systems, 2012. Report from the Workshop on Mixed Criticality Systems, Brussels, Belgium.Google Scholar
- G. G0iannopoulou, N. Stoimenov, P. Huang, and L. Thiele. Scheduling of mixed-criticality applications on resource-sharing multicore systems. In International Conference on Embedded Software (EMSOFT), pages 17:1--17:15, Montreal, Oct 2013. Google ScholarDigital Library
- G. Giannopoulou, N. Stoimenov, P. Huang, and L. Thiele. Mapping mixed-criticality applications on multi-core architectures. In Design, Automation and Test in Europe Conference and Exhibition (DATE), 2014, pages 1--6, March 2014. Google ScholarDigital Library
- P. Graydon and I. Bate. Safety assurance driven problem formulation for mixed-criticality scheduling. 2013.Google Scholar
- J. Huang, A. Raabe, K. Huang, C. Buckl, and A. Knoll. A framework for reliability-aware design exploration on mpsoc based systems. Design Automation for Embedded Systems, 16(4):189--220, 2012. Google ScholarDigital Library
- P. Huang, G. Giannopoulou, R. Ahmed, D. B. Bartolini, and L. Thiele. An isolation scheduling model for multicores. In Proc. of the IEEE Real-Time Systems Symposium (RTSS), San Antonio, Texas, USA, Dec 2015. Google ScholarDigital Library
- P. Huang, H. Yang, and L. Thiele. On the scheduling of fault-tolerant mixed-criticality systems. Technical report, Computer Engineering and Networks Laboratory, ETH Zurich, 2014.Google Scholar
- S.-h. Kang, H. Yang, S. Kim, I. Bacivarov, S. Ha, and L. Thiele. Static mapping of mixed-critical applications for fault-tolerant mpsocs. In Proceedings of the 51st Annual Design Automation Conference, DAC '14, pages 31:1--31:6, New York, NY, USA, 2014. ACM. Google ScholarDigital Library
- H. Li and S. Baruah. Load-based schedulability analysis of certifiable mixed-criticality systems. In Proceedings of the tenth ACM international conference on Embedded software, pages 99--108. ACM, 2010. Google ScholarDigital Library
- D. McNulty, L. Olson, and M. Peloquin. A comparison of scheduling algorithms for multiprocessors, 2010.Google Scholar
- M. S. Mollison, J. P. Erickson, J. H. Anderson, S. K. Baruah, J. Scoredos, et al. Mixed-criticality real-time scheduling for multicore systems. In Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on, pages 1864--1871. IEEE, 2010. Google ScholarDigital Library
- T. Park and S. Kim. Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems. In Proceedings of the ninth ACM international conference on Embedded software, pages 253--262. ACM, 2011. Google ScholarDigital Library
- F. Santy, L. George, P. Thierry, and J. Goossens. Relaxing mixed-criticality scheduling strictness for task sets scheduled with fp. In Real-Time Systems (ECRTS), 2012 24th Euromicro Conference on, pages 155--165. IEEE, 2012. Google ScholarDigital Library
- L. Sha. Resilient mixed-criticality systems. CrossTalk: The Journal of Defense Software, 2009.Google Scholar
- S. Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Real-Time Systems Symposium, 2007. RTSS 2007. 28th IEEE International, pages 239--243. IEEE, 2007. Google ScholarDigital Library
- H. Yun, G. Yao, R. Pellizzoni, M. Caccamo, and L. Sha. Memory access control in multiprocessor for real-time systems with mixed criticality. In Real-Time Systems (ECRTS), 2012 24th Euromicro Conference on, pages 299--308. IEEE, 2012. Google ScholarDigital Library
- M. Zeller, C. Prehofer, D. Krefft, and G. Weiss. Towards runtime adaptation in autosar. ACM SIGBED Review, 10(4):17--20, 2013. Google ScholarDigital Library
Recommendations
Optimization of Fault-Tolerant Mixed-Criticality Multi-Core Systems with Enhanced WCRT Analysis
This article proposes a novel optimization technique of fault-tolerant mixed-criticality multi-core systems with worst-case response time (WCRT) guarantees. Typically, in fault-tolerant multi-core systems, tasks can be replicated or re-executed in order ...
On the Scheduling of Fault-Tolerant Mixed-Criticality Systems
DAC '14: Proceedings of the 51st Annual Design Automation ConferenceWe consider in this paper fault-tolerant mixed-criticality scheduling, where heterogeneous safety guarantees must be provided to functionalities (tasks) of varying criticalities (importances). We model explicitly the safety requirements for tasks of ...
Fault Tolerant Scheduling of Mixed Criticality Real-time Tasks under Error Bursts
AbstractDependability is an important requirement in hard real-time applications due to the potentially catastrophic consequences of failures. In these systems, fault tolerance mechanisms like temporal redundancy are adopted to improve reliability. Most ...
Comments