QoC-oriented efficient schedule synthesis for mixed-criticality cyber-physical systems

Cyber-physical systems (CPS) are characterized by a tight interaction between computational resources and physical systems. Such systems typically consist of a mix of time-critical real-time tasks and safety-critical control tasks. Time-critical applications are normally associated with hard real-time constraints which need to be guaranteed by the system. On the other hand, control applications are not strictly related to deadlines but rather to quality of control (QoC). Traditional scheduling policies such as Deadline Monotonic can guarantee timing constraints, however, they do not allow for QoC optimized schedules. Optimizing overall QoC while guaranteeing all deadlines constitutes a challenging scheduling problem which is increasingly attracting attention. In this paper, we present an efficient schedule synthesis algorithm for such mixed-criticality systems. The proposed algorithm has a polynomial complexity and ensures all hard real-time constraints while maximizing overall QoC for all control applications.