Vol. 1 No. 2 (2014)
Regular Papers

Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor

Zhishan Guo
University of North Carolina, Chapel Hill, NC, USA
Sanjoy K. Baruah
University of North Carolina, Chapel Hill, NC, USA

Published 2014-11-17


  • Mixed criticalities,
  • Varying-speed processor,
  • Preemptive uniprocessor scheduling,

How to Cite

Guo, Z. and Baruah, S.K. 2014. Implementing Mixed-criticality Systems Upon a Preemptive Varying-speed Processor. Leibniz Transactions on Embedded Systems. 1, 2 (Nov. 2014), 03:1–03:19. DOI:https://doi.org/10.4230/LITES-v001-i002-a003.


A mixed criticality (MC) workload consists of components of varying degrees of importance (or "criticalities"); the more critical components typically need to have their correctness validated to greater levels of assurance than the less critical ones. The problem of executing such a MC workload upon a preemptive processor whose effective speed may vary during run-time, in a manner that is not completely known prior to run-time, is considered.

Such a processor is modeled as being characterized by several execution speeds: a normal speed and several levels of degraded speed. Under normal circumstances it will execute at or above its normal speed; conditions during run-time may cause it to execute slower. It is desired that all components of the MC workload execute correctly under normal circumstances. If the processor speed degrades, it should nevertheless remain the case that the more critical components execute correctly (although the less critical ones need not do so).

In this work, we derive an optimal algorithm for scheduling MC workloads upon such platforms; achieving optimality does not require that the processor be able to monitor its own run-time speed. For the sub-case of the general problem where there are only two criticality levels defined, we additionally provide an implementation that is asymptotically optimal in terms of run-time efficiency.


  1. Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, and Baruch Schieber. Non-preemptive min-sum scheduling with resource augmentation. In 48th Annual IEEE Symp. on Foundations of Computer Science (FOCS’07), October 20–23, 2007, Providence, RI, USA, pages 614–624. IEEE Computer Society, 2007. doi:10.1109/FOCS.2007.46.
  2. Sanjoy Baruah and Zhishan Guo. Mixed-criticality scheduling upon varying-speed processors. In IEEE 34th Real-Time Systems Symp. (RTSS’13), Vancouver, BC, Canada, December 3–6, 2013, pages 68–77. IEEE, 2013. doi:10.1109/RTSS.2013.15.
  3. Sanjoy K. Baruah, Vincenzo Bonifaci, Gianlorenzo D’Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow, and Leen Stougie. Scheduling real-time mixed-criticality jobs. IEEE Trans. Computers, 61(8):1140–1152, 2012. doi:10.1109/TC.2011.142.
  4. Sanjoy K. Baruah, Vincenzo Bonifaci, Gianlorenzo D’Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Suzanne van der Ster, and Leen Stougie. The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems. In 24th Euromicro Conf. on Real-Time Systems (ECRTS’12), Pisa, Italy, July 11–13, 2012, pages 145–154. IEEE Computer Society, 2012. doi:10.1109/ECRTS.2012.42.
  5. Alan Burns and Robert Davis. Mixed-criticality systems: A review. Unpublished manuscript, 4th edition, July 31, 2014. URL: http://www-users.cs.york.ac.uk/~burns/review.pdf.
  6. Giorgio C. Buttazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Springer US, 2nd edition, 2005. doi:10.1007/978-1-4614-0676-1.
  7. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  8. Zhishan Guo and Sanjoy Baruah. Mixed-criticality scheduling upon non-monitored varying-speed processors. In 8th IEEE Int’l Symp. on Industrial Embedded Systems (SIES’13), Porto, Portugal, June 19–21, 2013, pages 161–167. IEEE, 2013. doi:10.1109/SIES.2013.6601488.
  9. Narendra Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4):373–396, 1984. doi:10.1007/BF02579150.
  10. L. G. Khachiyan. A polynomial algorithm in linear programming. Dokklady Akademiia Nauk SSSR, 244:1093–1096, 1979.
  11. Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, and Peter Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1977. doi:10.1016/S0167-5060(08)70743-X.
  12. C. L. Liu and James W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM, 20(1):46–61, 1973. doi:10.1145/321738.321743.
  13. Aloysius 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. URL: http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-297.pdf.
  14. Aloysius Mok. Task management techniques for enforcing ED scheduling on a periodic task set. In 5th IEEE Workshop on Real-Time Software and Operating Systems, pages 42–46,Washington D. C., May 1988.
  15. Steve Vestal. Preemptive scheduling of multicriticality systems with varying degrees of execution time assurance. In 28th IEEE Real-Time Systems Symp. (RTSS’07), December 3–6, 2007, Tucson, Arizona, USA, pages 239–243. IEEE Computer Society, 2007. doi:10.1109/RTSS.2007.35.
  16. Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David B. Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Tulika Mitra, Frank Mueller, Isabelle Puaut, Peter P. Puschner, Jan Staschulat, and Per Stenström. The worst-case execution-time problem – overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst., 7(3), 2008. doi:10.1145/1347375.1347389.