Sanjoy Baruah
Abstract
Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the rest of the functionality is non-safety-critical and does not need to be certified, or is certified to lower levels of assurance. The certification-cognizant runtime scheduling of such mixed-criticality systems is considered. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is presented: this algorithm can schedule systems for which any number of criticality levels are defined. Efficient implementations of EDF-VD, as well as associated schedulability tests for determining whether a task system can be correctly scheduled using EDF-VD, are presented. For up to 13 criticality levels, analyses of EDF-VD, based on metrics such as processor speedup factor and utilization bounds, are derived, and conditions under which EDF-VD is optimal with respect to these metrics are identified. Finally, two extensions of EDF-VD are discussed that enhance its applicability. The extensions are aimed at scheduling a wider range of task sets, while preserving the favorable worst-case resource usage guarantees of the basic algorithm.
- K. Albers and F. Slomka. 2004. An event stream driven approximation for the analysis of real-time systems. In Proceedings of the 16th Euromicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA, 187--195. Google Scholar
Digital Library
- J. Barhorst, T. Belote, P. Binns, J. Hoffman, J. Paunicka, P. Sarathy, J. S. P. Stanfill, D. Stuart, and R. Urzi. 2009. A research agenda for mixed-criticality systems. White paper. http://www.cse.wustl.edu/∼cdgill/CPSWEEK09_MCAR/.Google Scholar
- S. K. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, and L. Stougie. 2012. Scheduling real-time mixed-criticality jobs. IEEE Trans. Comput. 61, 8, 1140--1152. Google ScholarDigital Library
- S. K. Baruah, R. R. Howell, and L. E. Rosier. 1993. Feasibility problems for recurring tasks on one processor. Theor. Comput. Sci. 118, 1, 3--20. Google ScholarDigital Library
- S. K. Baruah, H. Li, and L. Stougie. 2010a. Mixed-Criticality scheduling: Improved resource-augmentation results. In Proceedings of the ISCA International Conference on Computers and their Applications. ISCA, Los Alamitos, CA, 217--223.Google Scholar
- S. K. Baruah, H. Li, and L. Stougie. 2010b. Towards the design of certifiable mixed-criticality systems. In Proceedings of the 16th IEEE Real-Time Technology and Applications Symposium. IEEE, Los Alamitos, CA, 13--22. Google ScholarDigital Library
- P. Belotti, J. Lee, L. Liberti, F. Margot, and A. Wächter. 2009. Branching and bounds tightening techniques for non-convex MINLP. Optimi. Meth. Softw. 24, 4--5, 597--634. Google ScholarDigital Library
- S. Boyd and L. Vandenberghe. 2009. Convex Optimization. Cambridge University Press, Cambridge, UK. Google ScholarDigital Library
- A. Burns and R. I. Davis. 2013. Mixed criticality systems - A Review. http://www-users.cs.york.ac.uk/∼burns/review.pdf.Google Scholar
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to Algorithms 3rd Ed. MIT Press, Cambridge, MA. Google ScholarDigital Library
- M. L. Dertouzos. 1974. Control robotics: The procedural control of physical processes. In Proceedings of the International Federation for Information Processing Congress. North-Holland, Amsterdam, 807--813.Google Scholar
- A. Easwaran. 2013. Demand-based scheduling of mixed-criticality sporadic tasks on one processor. In Proceedings of 34th IEEE Real-Time Systems Symposium. IEEE, Los Alamitos, CA, 78--87. Google ScholarDigital Library
- P. Ekberg and W. Yi. 2012. Bounding and shaping the demand of mixed-criticality sporadic tasks. In Proceedings of 24th Euromicro Conference on Real-Time Systems. IEEE, Los Alamitos, CA, 135--144. Google ScholarDigital Library
- P. Ekberg and W. Yi. 2014. Bounding and shaping the demand of generalized mixed-criticality sporadic task systems. Real-Time Systems 50, 1, 48--86. Google ScholarDigital Library
- N. Guan, P. Ekberg, M. Stigge, and W. Yi. 2011. Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In Proceedings of the 32nd IEEE Real-Time Systems Symposium. IEEE, Los Alamitos, CA, 13--23. Google ScholarDigital Library
- J. Y.-T. Leung and J. Whitehead. 1982. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perf. Eval. 2, 4, 237--250.Google ScholarCross Ref
- H. Li and S. K. Baruah. 2010. An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In Proceedings of the 31st IEEE Real-Time Systems Symposium. IEEE, Los Alamitos, CA, 183--192. Google ScholarDigital Library
- C. L. Liu and J. W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20, 1, 46--61. Google ScholarDigital Library
- A. K. Mok. 1983. Fundamental design problems of distributed systems for the hard real-time environment. Ph.D. dissertation. Laboratory for Computer Science, Massachusetts Institute of Technology. (Available Technical Report No. MIT/LCS/TR-297.) Google ScholarDigital Library
- A. K. Mok. 1988. Task management techniques for enforcing ED scheduling on periodic task set. In Proceedings of the 5th IEEE Workshop on Real-Time Software and Operating Systems. USENIX Association, Washington, DC, 42--46.Google Scholar
- P. J. Prisaznuk. 1992. Integrated modular avionics. In Proceedings of the IEEE National Aerospace and Electronics Conference, Vol. 1. IEEE, Los Alamitos, CA, 39--45.Google Scholar
- H. Su and D. Zhu. 2013. An elastic mixed-criticality task model and its scheduling algorithm. In Proceedings of the Conference on Design, Automation & Test in Europe. EDA Consortium, San Jose, CA, 147--152. 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 Real-Time Systems Symposium. IEEE, Los Alamitos, CA, 239--243. Google ScholarDigital Library
- R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. B. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, et al. 2008. The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst. 7, 3, 36. Google ScholarDigital Library
Index Terms
- Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems
Recommendations
The Preemptive Uniprocessor Scheduling of Mixed-Criticality Implicit-Deadline Sporadic Task Systems
ECRTS '12: Proceedings of the 2012 24th Euromicro Conference on Real-Time SystemsSystems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification, the rest of ...
Effective and Efficient Scheduling of Certifiable Mixed-Criticality Sporadic Task Systems
RTSS '11: Proceedings of the 2011 IEEE 32nd Real-Time Systems SymposiumAn increasing trend in embedded system design is to integrate components with different levels of criticality into a shared hardware platform for better cost and power efficiency. Such mixed-criticality systems are subject to certifications at different ...
On the Scheduling of Mixed-Criticality Real-Time Task Sets
RTSS '09: Proceedings of the 2009 30th IEEE Real-Time Systems SymposiumThe functional consolidation induced by the cost reduction trends in embedded systems can force tasks of different criticality (e.g. ABS Brakes with DVD) to share a processor and interfere with each other. These systems are known as mixed criticality ...
Comments