Mixed-Criticality Scheduling Upon Permitted Failure Probability and Dynamic Priority

Zhishan Guo, Sudharsan Vaidhun, Luca Satinelli, Samsil Arefin, Jun Wang, Kecheng Yang

Abstract

Many safety-critical real-time systems are considered certified when they meet failure probability requirements with respect to the maximum permitted incidences of failure per hour. In this article, the mixed-criticality task model with multiple worst case execution time (WCET) estimations is extended to incorporate such system-level certification restrictions. A new parameter is added to each task, characterizing the distribution of WCET estimations—the likelihood of all jobs of a task finishing their executions within the less pessimistic WCET estimates. Efficient algorithms are derived for scheduling mixed-criticality systems represented using this model for both uniprocessor and multiprocessor platforms for independent tasks. Furthermore, a 0/1 covariance matrix is introduced to represent the failure dependency between tasks. An efficient algorithm is proposed to schedule such failure-dependent tasks. Experimental analyses show our new model and algorithm outperform current state-of-the-art mixed-criticality scheduling algorithms.
BibTeX
@article{guo2022mixed,
  author = {Zhishan Guo and Sudharsan Vaidhun and Luca Satinelli and Samsil Arefin and Jun Wang and Kecheng Yang},
  title = {{Mixed-Criticality Scheduling Upon Permitted Failure Probability and Dynamic Priority}},
  journal = {IEEE TCAD},
  year = {2022},
  doi = {10.1109/tcad.2021.3053232},
}

Loading related content...

Figure