Scheduling for Mixed-Criticality Systems

There is a trend towards consolidating software functions onto fewer processors in different domains such as automotive systems and avionics. Hence applications with different levels of criticality that used to run in isolation now start sharing processors. As a result, there is a need for techniques that allow designing such mixed-criticality (MC) systems and, at the same time, complying with certification requirements in the different domains.

In this research, we study the problem of scheduling MC tasks under the Earliest Deadline First (EDF) scheduling algorithm and propose new approaches to improve scheduling techniques. In particular, we consider that a mix of low-criticality (LO) and high-criticality (HI) tasks are scheduled on one processor. While LO tasks can be modeled by minimum inter-arrival time, deadline, and worst-case execution time (WCET), HI tasks are characterized by two WCET parameters: an optimistic and a conservative one. The system then distinguishes between two operation modes: HI and LO mode. In LO mode, HI tasks require executing for no longer than their optimistic WCETs and are scheduled together with the LO tasks. A switch to HI mode occurs when one HI task executes for longer than its optimistic WCET (but still less than its conservative one).

Similar to other approaches, we consider that LO tasks are immediately discarded in HI mode, which then allows accommodating this increase in HI execution demand. To this end, we will propose exact and approximated tests for mixed-criticality EDF, which increase efficiency and reliability and compare them with the existing approaches. Exact tests give a precise answer about whether a set of MC tasks is feasible or not, whereas approximated tests have less complexity and, hence, a reduced running time making them more suitable for online checks.