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

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.