Risk-Aware Scheduling of Dual Criticality Job Systems Using Demand Distributions
How to Cite
We pose the problem of scheduling Mixed Criticality (MC) job systems when there are only two criticality levels, Lo and Hi -referred to as Dual Criticality job systems- on a single processing platform, when job demands are probabilistic and their distributions are known. The current MC models require that the scheduling policy allocate as little execution time as possible to Lo-criticality jobs if the scenario of execution is of Hi criticality, and drop Lo-criticality jobs entirely as soon as the execution scenario's criticality level can be inferred and is Hi. The work incurred by "incorrectly" scheduling Lo-criticality jobs in cases of Hi realized scenarios might affect the feasibility of Hi criticality jobs; we quantify this work and call it Work Threatening Feasibility (WTF). Our objective is to construct online scheduling policies that minimize the expected WTF for the given instance, and under which the instance is feasible in a probabilistic sense that is consistent with the traditional deterministic definition of MC feasibility.
We develop a probabilistic framework for MC scheduling, where feasibility is defined in terms of (chance) constraints on the probabilities that Lo and Hi jobs meet their deadlines. The probabilities are computed over the set of sample paths, or trajectories, induced by executing the policy, and those paths are dependent upon the set of execution scenarios and the given demand distributions. Our goal is to exploit the information provided by job distributions to compute the minimum expected WTF below which the given instance is not feasible in probability, and to compute a (randomized) "efficiently implementable" scheduling policy that realizes the latter quantity. We model the problem as a Constrained Markov Decision Process (CMDP) over a suitable state space and a finite planning horizon, and show that an optimal (non-stationary) Markov randomized scheduling policy exists. We derive an optimal policy by solving a Linear Program (LP). We also carry out quantitative evaluations on select probabilistic MC instances to demonstrate that our approach potentially outperforms current MC scheduling policies.
- AdaCore. What is do-178b?, 2014. URL: http://www.adacore.com/gnatpro-safety-critical/avionics/do178b/.
- Bader Alahmad, Sathish Gopalakrishnan, Luca Santinelli, and Liliana Cucu-Grosjean.Probabilities for Mixed-Criticality Problems: Bridging the Uncertainty Gap. In The Work in Progress session of the 32nd IEEE Real-time Systems Symposium - RTSS 2011, Wien, Austria, November 2011. URL: https://hal.inria.fr/hal-00646586.
- Eitan Altman. Constrained markov decision processes with total cost criteria: Lagrangian approach and dual linear program. Math. Meth. of OR, 48(3):387-417, 1998. URL: http://dx.doi.org/10.1007/s001860050035
- Eitan Altman. Constrained Markov Decision Processes. Chapman and Hall/CRC, 1999.
- Robert B. Ash. Real Analysis and Probability. Academic Press, 1972.
- Neil C. Audsley, Alan Burns, Mike M. Richardson, Ken Tindell, and Andy J. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284-292, 1993. URL: http://dx.doi.org/10.1049/sej.1993.0034
- Sanjoy Baruah.Mixed criticality schedulability analysis is highly intractable. to appear. URL: http://www.cs.unc.edu/ baruah/Submitted/02cxty.pdf.
- Sanjoy K. Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Haohan Li, Alberto Marchetti-Spaccamela, Nicole Megow, and Leen Stougie. Scheduling real-time mixed-criticality jobs. In Petr Hlinený and Antonín Kucera, editors, Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, volume 6281 of Lecture Notes in Computer Science, pages 90-101. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15155-2_10
- Sanjoy K. Baruah and Zhishan Guo. Scheduling mixed-criticality implicit-deadline sporadic task systems upon a varying-speed processor. In Proceedings of the IEEE 35th IEEE Real-Time Systems Symposium, RTSS 2014, Rome, Italy, December 2-5, 2014, pages 31-40. IEEE Computer Society, 2014. URL: http://dx.doi.org/10.1109/RTSS.2014.15
- Sanjoy K. Baruah, Haohan Li, and Leen Stougie. Towards the design of certifiable mixed-criticality systems. In Marco Caccamo, editor, 16th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2010, Stockholm, Sweden, April 12-15, 2010, pages 13-22. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/RTAS.2010.10
- Sanjoy K. Baruah and Steve Vestal. Schedulability analysis of sporadic tasks with multiple criticality specifications. In 20th Euromicro Conference on Real-Time Systems, ECRTS 2008, 2-4 July 2008, Prague, Czech Republic, Proceedings, pages 147-155. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/ECRTS.2008.26
- Enrico Bini and Giorgio C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. URL: http://dx.doi.org/10.1007/s11241-005-0507-9
- Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artif. Intell., 121(1-2):49-107, 2000. URL: http://dx.doi.org/10.1016/S0004-3702(00)00033-3
- Alan Burns and Robert I. Davis. Mixed criticality systems - a review. Preprint, 2015. URL: http://www-users.cs.york.ac.uk/burns/review.pdf.
- Yao Chen, Qiao Li, Zheng Li, and Huagang Xiong. Efficient schedulability analysis for mixed-criticality systems under deadline-based scheduling. Chinese Journal of Aeronautics, 27(4):856 - 866, 2014. URL: http://dx.doi.org/http://dx.doi.org/10.1016/j.cja.2014.05.003
- José Luis Díaz, Daniel F. García, Kanghee Kim, Chang-Gun Lee, Lucia Lo Bello, José María López, Sang Lyul Min, and Orazio Mirabella. Stochastic analysis of periodic real-time systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), Austin, Texas, USA, December 3-5, 2002, pages 289-300. IEEE Computer Society, 2002. URL: http://dx.doi.org/10.1109/REAL.2002.1181583
- José Luis Díaz and José María López. Probabilistic analysis of the response time in a real-time system. Technical Report, 2001.
- José Luis Díaz and José María López. Safe extensions to the stochastic analysis of real-time systems. Technical Report, 2004.
- José Luis Díaz, José María López, Manuel García Vazquez, Antonio M. Campos, Kanghee Kim, and Lucia Lo Bello. Pessimism in the stochastic analysis of real-time systems: Concept and applications. In Proceedings of the 25th IEEE Real-Time Systems Symposium (RTSS 2004), 5-8 December 2004, Lisbon, Portugal, pages 197-207. IEEE Computer Society, 2004. URL: http://dx.doi.org/10.1109/REAL.2004.41
- Dmitri A. Dolgov and Edmund H. Durfee. Symmetric approximate linear programming for factored mdps with application to constrained problems. Ann. Math. Artif. Intell., 47(3-4):273-293, 2006. URL: http://dx.doi.org/10.1007/s10472-006-9038-x
- Peter Geibel and Fritz Wysotzki. Risk-sensitive reinforcement learning applied to control under constraints. J. Artif. Intell. Res., 24:81-108, 2005. URL: http://dx.doi.org/10.1613/jair.1666
- Zhishan Guo and Sanjoy K. Baruah. Implementing mixed-criticality systems upon a preemptive varying-speed processor.LITES, 1(2):03:1-03:19, 2014. URL: http://dx.doi.org/10.4230/LITES-v001-i002-a003
- Zhishan Guo, Luca Santinelli, and Kecheng Yang.EDF schedulability analysis on mixed-criticality systems with permitted failure probability. In 21st IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2015, Hong Kong, China, August 19-21, 2015, pages 187-196. IEEE Computer Society, 2015. URL: http://dx.doi.org/10.1109/RTCSA.2015.8
- Inc. Gurobi Optimization. Gurobi optimizer reference manual, 2015. URL: http://www.gurobi.com.
- Onésimo Hernández-Lerma. Adaptive Markov control processes. Applied mathematical sciences. Springer, New York, 1989.
- Onésimo Hernández-Lerma and Jean B Lasserre. Discrete-Time Markov Control Processes: Basic Optimality Criteria. Stochastic Modelling and Applied Probability. Springer-Verlag, New York, 1996.
- L. C. M. Kallenberg. Unconstrained and constrained dynamic programming over a finite horizon. Technical Report, 1981.
- L. C. M. Kallenberg. Linear Programming and Finite Markovian Control Problems. Amsterdam : Mathematisch Centrum, 1983.
- Lodewijk C. M. Kallenberg. Survey of linear programming for standard and nonstandard markovian control problems. part I: theory. Math. Meth. of OR, 40(1):1-42, 1994. URL: http://dx.doi.org/10.1007/BF01414028
- Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. J. ACM, 47(4):617-643, 2000. URL: http://dx.doi.org/10.1145/347476.347479
- Kanghee Kim, José Luis Díaz, Lucia Lo Bello, José María López, Chang-Gun Lee, and Sang Lyul Min. An exact stochastic analysis of priority-driven periodic real-time systems and its approximations.IEEE Trans. Computers, 54(11):1460-1466, 2005. URL: http://dx.doi.org/10.1109/TC.2005.174
- Achim Klenke. Probability Theory: A Comprehensive Course. Universitext. Springer, 2 edition, 2014.
- Dorin Maxim and Liliana Cucu-Grosjean. Response time analysis for fixed-priority tasks with multiple probabilistic parameters. In Proceedings of the IEEE 34th Real-Time Systems Symposium, RTSS 2013, Vancouver, BC, Canada, December 3-6, 2013, pages 224-235. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/RTSS.2013.30
- Pascal Poupart, Craig Boutilier, Relu Patrascu, and Dale Schuurmans. Piecewise linear value function approximation for factored mdps. In Rina Dechter, Michael J. Kearns, and Richard S. Sutton, editors, Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, 2002, Edmonton, Alberta, Canada., pages 292-299. AAAI Press / The MIT Press, 2002. URL: http://www.aaai.org/Library/AAAI/2002/aaai02-045.php.
- M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, New York, 5 edition, 2005.
- Martin L. Shooman. Avionics software problem occurrence rates. In Seventh International Symposium on Software Reliability Engineering, ISSRE 1996, White Plains, NY, USA, October 30, 1996-Nov. 2, 1996, pages 55-64. IEEE Computer Society, 1996. URL: http://dx.doi.org/10.1109/ISSRE.1996.558695
- Dario Socci, Peter Poplavko, Saddek Bensalem, and Marius Bozga. Mixed critical earliest deadline first. In 25th Euromicro Conference on Real-Time Systems, ECRTS 2013, Paris, France, July 9-12, 2013, pages 93-102. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.20
- Steve Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the 28th IEEE Real-Time Systems Symposium (RTSS 2007), 3-6 December 2007, Tucson, Arizona, USA, pages 239-243. IEEE Computer Society, 2007. URL: http://dx.doi.org/10.1109/RTSS.2007.47