Effective and Efficient Scheduling of Certifiable Mixed-Criticality Sporadic Task Systems

Citations Over TimeTop 10% of 2011 papers

Abstract

An increasing trend in embedded system design is to integrate components with different levels of criticality into a shared hardware platform for better cost and power efficiency. Such mixed-criticality systems are subject to certifications at different levels of rigorousness, for validating the correctness of different subsystems on various confidence levels. The real-time scheduling of certifiable mixed-criticality systems has been recognized to be a challenging problem, where using traditional scheduling techniques may result in unacceptable resource waste. In this paper we present an algorithm called PLRS to schedule certifiable mixed-criticality sporadic tasks systems. PLRS uses fixed-job-priority scheduling, and assigns job priorities by exploring and balancing the asymmetric effects between the workload on different criticality levels. Comparing with the state-of-the-art algorithm by Li and Baruah for such systems, which we refer to as LB, PLRS is both more effective and more efficient: (i) The schedulability test of PLRS not only theoretically dominates, but also on average significantly outperforms LB's. (ii) The run-time complexity of PLRS is polynomial (quadratic in the number of tasks), which is much more efficient than the pseudo-polynomial run-time complexity of LB.

Related Papers

• → Mixed criticality systems with weakly-hard constraints(2015)52 cited
• → Utilization-Based Scheduling of Flexible Mixed-Criticality Real-Time Tasks(2017)40 cited
• → A semi-partitioned model for mixed criticality systems(2019)14 cited
• → Mixed-criticality design of a satellite software system(2014)8 cited
• → Utilization-Based Scheduling of Flexible Mixed-Criticality Real-Time Tasks(2017)1 cited