Necessary Feasibility Analysis for Mixed-Criticality Real-Time Embedded Systems

Hoon Sung Chwa, Hyeongboo Baek, Jinkyu Lee

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


As multiple software components with different safety-criticality levels are integrated on a shared computing platform, a real-time embedded system becomes a mixed-criticality (MC) system, which should provide timing guarantees at all different levels of assurance to software components with different criticality levels. In the real-time systems community, the concept of an MC system is regarded as a promising, emerging solution to solve an inherent challenge of real-time systems: pessimistic reservation of computing resources, which yields a low resource-utilization for the sake of guaranteeing timing requirements. Since a timing guarantee should be provided before a real-time system starts to operate, its feasibility has been extensively studied for single-criticality systems; however, the same cannot be said for MC systems. In this article, we develop necessary feasibility tests for MC real-time embedded systems, which is the first study that yields non-trivial results for MC necessary feasibility on both uniprocessor and multiprocessor platforms. To this end, we investigate characteristics of MC necessary feasibility conditions, and identify new challenges posed by the characteristics. By addressing those challenges, we develop two collective necessary feasibility tests and their simplified versions, which are able to exploit a tradeoff between capability in finding infeasible task sets and time-complexity. The simulation results demonstrate that the proposed tests find a number of additional infeasible task sets for both uniprocessor and multiprocessor platforms, which have been proven neither feasible nor infeasible by any existing studies.

Original languageEnglish
Pages (from-to)1520-1537
Number of pages18
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number7
StatePublished - 1 Jul 2022


  • Real-time embedded systems
  • mixed-criticality systems
  • necessary feasibility analysis
  • timing guarantees
  • uniprocessor and multiprocessor platforms


Dive into the research topics of 'Necessary Feasibility Analysis for Mixed-Criticality Real-Time Embedded Systems'. Together they form a unique fingerprint.

Cite this