Sanjoy Baruah
ABSTRACT
In modern embedded platforms, safety-critical functionalities that must be certified correct to very high levels of assurance may co-exist with less critical software that is not subject to certification requirements. One seeks to satisfy two, sometimes contradictory, goals upon such mixed-criticality platforms: (i) certify the safety-critical functionalities under very conservative assumptions, and (ii) achieve high resource utilization during run-time, when actual behavior does not live up to the pessimistic assumptions under which certification was made. This paper makes two contributions: (i) it surveys different fixed-priority scheduling algorithms that have been proposed, that seek to balance these two requirements, and (ii) it completes prior work that performs a comparative evaluation of these different fixed-priority scheduling algorithms. It particularly focuses upon the period transformation technique for dual-criticality scheduling, since this technique has received relatively less attention in prior work.
- L. Abeni and G. Buttazzo. Integrating multimedia applications in hard real-time systems. In Proceedings of the Real-Time Systems Symposium, pages 3--13, Madrid, Spain, December 1998. IEEE Computer Society Press. Google Scholar
Digital Library
- N. Audsley. On priority assignment in fixed priority scheduling. Information Processing Letters, 79(1):39--44, 2001. Google ScholarDigital Library
- N. C. Audsley. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical report, The University of York, England, 1991.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 Proceedings of the 2012 24th Euromicro Conference on Real-Time Systems, ECRTS '12, Pisa (Italy), 2012. IEEE Computer Society. Google ScholarDigital Library
- S. Baruah, A. Burns, and R. Davis. Response-time analysis for mixed criticality systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Vienna, Austria, 2011. IEEE Computer Society Press. Google ScholarDigital Library
- S. Baruah and S. Vestal. Schedulability analysis of sporadic tasks with multiple criticality specifications. In Proceedings of the EuroMicro Conference on Real-Time Systems, Prague, Czech Republic, July 2008. IEEE Computer Society Press. Google ScholarDigital Library
- G. Buttazzo. Rate-monotonic vs. EDF: Judgement day. Real-Time Systems: The International Journal of Time-Critical Computing, 29(1):5--26, 2005. Google ScholarDigital Library
- D. de Niz, K. Lakshmanan, and R. R. Rajkumar. On the scheduling of mixed-criticality real-time task sets. In Proceedings of the Real-Time Systems Symposium, pages 291--300, Washington, DC, 2009. IEEE Computer Society Press. Google ScholarDigital Library
- N. Guan, P. Ekberg, M. Stigge, and W. Yi. Effective and efficient scheduling for certifiable mixed criticality sporadic task systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), Vienna, Austria, 2011. IEEE Computer Society Press. Google ScholarDigital Library
- H.-M. Huang, C. Gill, and C. Lu. Implementation and evaluation of mixed-criticality scheduling algorithms for periodic tasks. In Proceedings of the 2012 IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS '12, Beijing (China), 2012. IEEE Computer Society. Google ScholarDigital Library
- T.-W. Kuo and A. K. Mok. Load adjustment in adaptive real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, pages 160--171, 1991.Google ScholarCross Ref
- J. Y.-T. Leung and J. Whitehead. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 2:237--250, 1982.Google ScholarCross Ref
- C. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1):46--61, 1973. Google ScholarDigital Library
- A. Mok. Fundamental Design Problems of Distributed Systems for The Hard-Real-Time Environment. PhD thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, 1983. Available as Technical Report No. MIT/LCS/TR-297. Google ScholarDigital Library
- P. J. Prisaznuk. Integrated modular avionics. In Proceedings of the IEEE 1992 National Aerospace and Electronics Conference (NAECON 1992), volume 1, pages 39--45, May 1992.Google ScholarCross Ref
- L. Sha, J. Lehoczky, and R. Rajkumar. Solutions for some practical problems in prioritized preemptive scheduling. In Proceedings of the Real-Time Systems Symposium. IEEE Computer Society Press, Dec. 1986.Google Scholar
- S. Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the Real-Time Systems Symposium, pages 239--243, Tucson, AZ, December 2007. IEEE Computer Society Press. Google ScholarDigital Library
- A. Wellings, M. Richardson, A. Burns, N. Audsley, and K. Tindell. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8:284--292, 1993.Google ScholarCross Ref
Recommendations
Multiprocessor fixed-priority scheduling with restricted interprocessor migrations
Real-Time Systems (Euromicro RTS-03)The priority-driven scheduling of periodic and sporadic task systems upon identical multiprocessor platforms is considered, under the restrictions that (i) each job may be assigned exactly one priority throughout its lifetime, and (ii) each job may ...
Mixed-criticality scheduling on multiprocessors
The scheduling of mixed-criticality implicit-deadline sporadic task systems on identical multiprocessor platforms is considered. Two approaches, one for global and another for partitioned scheduling, are described. Theoretical analyses and simulation ...
Generalizing fixed-priority scheduling for better schedulability in mixed-criticality systems
The design of mixed-criticality systems is often subject to mandatory certification and has been drawing considerable attention over the past few years. This letter studies fixed-priority scheduling of mixed-criticality systems on a uniprocessor ...
Comments