Mixed-Criticality Systems: Running Safety-Critical and Best-Effort Software on One Platform

A modern car, aircraft or industrial robot no longer has one computer per function. Economic pressure on size, weight, power and cost (SWaP-C) pushes designers to consolidate many functions onto fewer, more powerful multicore processors. Those functions rarely share the same importance. A flight-control law, a brake controller or a safety interlock sits next to logging, diagnostics, infotainment and connectivity. A system that runs components of different criticality (different levels of assurance against failure) on a shared platform is called a mixed-criticality system.

The engineering challenge is twofold. Low-criticality software must not be able to compromise high-criticality software. And the platform should not be sized as if every component needed the most pessimistic, most heavily certified timing assumptions. This article covers the theory that began with Vestal’s 2007 model, the main scheduling results, the criticisms the research community has raised, and the architectural mechanisms (partitioning, hypervisors and reservations) used in practice.

Criticality, assurance and why it differs from priority

Safety standards assign each function a level based on the consequences of its failure. That level determines how rigorously the software must be developed and verified, including how its timing is established.

Giving the most critical tasks the highest priorities seems natural, but it can waste a lot of capacity. A short-period, low-criticality task may need a high priority to meet its deadline, while a high-criticality task with a long deadline can tolerate being preempted. Scheduling by criticality instead of by timing parameters is sometimes called criticality inversion, and the worked example below shows it failing. Our article on hard, firm and soft deadlines covers the related, but distinct, notion of how strict a deadline is.

Vestal’s model: one task, several WCETs

In 2007, Steve Vestal (Honeywell) observed that the WCET of a piece of code is not a single number. It depends on how much confidence you need. A measurement-based estimate with a modest margin may be adequate for DAL C, while DAL A may demand a sound static analysis with far more pessimistic assumptions (see WCET analysis methods). Vestal proposed that each task τ_i carry a criticality level L_i and a vector of WCET estimates C_i(L), one per level, non-decreasing in L.

In the widely studied dual-criticality case:

• Every task has C_i(LO), the optimistic estimate that is believed with LO-level assurance.
• HI-criticality tasks also have C_i(HI) ≥ C_i(LO), certified with HI-level assurance.
• The system must meet all deadlines if every task stays within C(LO), and must meet all HI deadlines if HI tasks run up to C(HI).

Vestal showed that a modified response-time analysis, combined with Audsley’s priority-assignment algorithm, schedules task sets that neither deadline-monotonic nor criticality-monotonic priorities can.

Adaptive Mixed Criticality (AMC)

Baruah, Burns and Davis (2011) went further with Adaptive Mixed Criticality. The system starts in LO mode with all tasks running. A run-time monitor checks every HI task’s execution against its C(LO) budget. If a HI task exceeds that budget, the system switches to HI mode, and LO tasks are no longer guaranteed (in the basic model, they are dropped). The system can return to LO mode, for example at an idle instant.

AMC-rtb analysis

For fixed-priority scheduling, the AMC-rtb test extends classic response-time analysis with three equations. hp(i) is the set of higher-priority tasks, and hpH/hpL restrict it to HI and LO tasks:

LO mode (all tasks):
  R_i(LO) = C_i(LO) + Σ_{j ∈ hp(i)}  ⌈R_i(LO) / T_j⌉ · C_j(LO)

HI mode (HI tasks only):
  R_i(HI) = C_i(HI) + Σ_{j ∈ hpH(i)} ⌈R_i(HI) / T_j⌉ · C_j(HI)
                    + Σ_{k ∈ hpL(i)} ⌈R_i(LO) / T_k⌉ · C_k(LO)

The last term captures the key insight. LO tasks can only interfere until the mode switch, which must happen before R_i(LO), so their interference is frozen at that point. The more precise AMC-max test examines each possible switch time and dominates AMC-rtb, at higher computational cost.

A worked example

Consider three implicit-deadline tasks (D = T):

from math import ceil

# (name, criticality, T = D, C_LO, C_HI), in priority order (highest first)
tasks = [("tau1", "LO", 10, 3, 3),
         ("tau2", "HI", 20, 4, 8),
         ("tau3", "HI", 50, 6, 14)]

def fixpoint(base, interference, limit):
    R = base
    while True:
        R_next = base + interference(R)
        if R_next == R or R_next > limit:
            return R_next
        R = R_next

def amc_rtb(tasks):
    ok = True
    for i, (name, crit, T, c_lo, c_hi) in enumerate(tasks):
        hp = tasks[:i]
        r_lo = fixpoint(c_lo, lambda R: sum(ceil(R / t[2]) * t[3] for t in hp), T)
        ok &= r_lo <= T
        if crit == "HI":
            lo_part = sum(ceil(r_lo / t[2]) * t[3] for t in hp if t[1] == "LO")
            r_hi = fixpoint(c_hi + lo_part,
                            lambda R: sum(ceil(R / t[2]) * t[4] for t in hp if t[1] == "HI"), T)
            ok &= r_hi <= T
            print(name, "R_LO =", r_lo, "R_HI =", r_hi)
    return ok

print(amc_rtb(tasks))   # tau2: 7 / 11, tau3: 16 / 36  -> True

Compare the outcomes of four approaches on the same task set:

You can reproduce the LO-mode response times with our schedulability calculator by entering the C(LO) values.

EDF with Virtual Deadlines (EDF-VD)

Under EDF, the equivalent technique shortens HI tasks’ deadlines in LO mode, so that they run “ahead of schedule” and keep slack in reserve for a possible switch. In HI mode, the real deadlines are restored and LO tasks are dropped. For implicit-deadline dual-criticality task sets, Baruah et al. (2012) give a simple test. Let U_LO(LO) be the LO tasks’ utilization, and U_HI(LO) and U_HI(HI) the HI tasks’ utilization at each WCET level:

if U_LO(LO) + U_HI(HI) ≤ 1:
    schedulable with plain EDF (no virtual deadlines needed)
else:
    x = U_HI(LO) / (1 − U_LO(LO))          # deadline scaling factor
    schedulable if  x · U_LO(LO) + U_HI(HI) ≤ 1,
    using virtual deadlines  x · T_i  for HI tasks in LO mode

EDF-VD has a proven speedup factor of 4/3, which is optimal for this problem. Our RM vs EDF comparison explains the general trade-offs between fixed priority and EDF that also apply here.

Critiques and more realistic models

The research model has drawn well-founded criticism from practitioners. Ernst and Di Natale’s 2016 article “Mixed Criticality Systems—A History of Misconceptions?” argued that certification standards don’t assign different WCETs to the same task. They also argued that abandoning lower-criticality functions is rarely acceptable, since “low criticality” often still means “important to the customer,” and that the separation the standards require is primarily about isolation, not about sharing slack.

The community has responded with refinements:

• Graceful degradation instead of dropping: LO tasks continue with longer periods, reduced budgets or lower quality of service in HI mode.
• Bounded overload and fast recovery: analyses of how quickly the system returns to LO mode.
• More than two levels, and models where criticality applies to deadlines or to fault tolerance as well as execution time.

Burns and Davis’s continuously updated review “Mixed Criticality Systems: A Review” (University of York) is the standard map of this literature.

Architectures: partitioning, hypervisors and reservations

Time and space partitioning

Industrial mixed-criticality systems are dominated by partitioning. In Integrated Modular Avionics, ARINC 653 defines partitions, each with its own memory space and fixed time windows in a cyclic major frame. A partition at DAL E cannot touch the memory of, or steal time from, a DAL A partition. ISO 26262 expresses the same requirement as freedom from interference in space, time and communication.

Hypervisors and separation kernels

On modern SoCs, partitioning is often implemented with hypervisors or separation kernels. Commercial options include PikeOS, LynxSecure, INTEGRITY Multivisor and QNX Hypervisor. Open-source options include Jailhouse, Bao and Xen, along with the formally verified seL4 microkernel, whose MCS extensions add scheduling contexts with budgets. Static-partitioning hypervisors such as Jailhouse and Bao assign whole cores to each guest, avoiding scheduling interference altogether. Xen’s RTDS scheduler instead provides per-vCPU budget/period reservations:

# Xen RTDS: give every vCPU of the "control" domain 4 ms every 10 ms
xl sched-rtds -d control -v all -p 10000 -b 4000   # values in microseconds
xl sched-rtds -d control                            # show current parameters

Reservations and contracts

Budget-enforcing reservations are the general mechanism behind all of these. Each component gets a guaranteed and enforced share of CPU time, so it can be analyzed and certified independently. This was the premise of contract-based scheduling and of the FRESCOR project, described on its project overview page. FRESCOR aimed to let applications with different timing requirements share a platform with guaranteed temporal isolation. Subsequent EU research projects, such as MultiPARTES, DREAMS and PROXIMA, focused explicitly on mixed-criticality platforms.

The multicore complication

On multicore processors, a partition’s CPU time is not enough. A low-criticality partition hammering the memory controller can slow a high-criticality one on another core. Avionics guidance (CAST-32A, now EASA AMC 20-193 and FAA AC 20-193) therefore asks applicants to identify and mitigate interference channels. Mitigations include cache partitioning, memory-bandwidth regulation and coordinated scheduling; see our article on multicore real-time scheduling. A UAV autopilot sharing a processor with a companion computer is a typical example (see timing in flight control).

Frequently asked questions

Is a mixed-criticality system the same as a partitioned system?

Not exactly. A partitioned system is one way to build a mixed-criticality system, by isolating components so that their criticalities don’t interact. Mixed-criticality scheduling research goes further and lets components share resources dynamically, with guarantees that depend on criticality. Most certified products today rely mainly on partitioning.

Why would a task have two different WCETs?

Because WCET values come from analysis methods with different levels of confidence. A measurement-based high-water mark plus margin might be acceptable for low assurance. A sound static analysis, which is usually much larger, is required for high assurance. Vestal’s model uses both values.

Do certification authorities accept dropping low-criticality tasks?

Only if the system-level safety assessment shows that losing those functions is acceptable in the relevant situation. Many functions classed as low criticality still carry operational or customer requirements, so graceful degradation is usually preferred to outright abandonment.

What is the difference between AMC-rtb and AMC-max?

Both analyze fixed-priority Adaptive Mixed Criticality. AMC-rtb bounds LO-task interference using the LO-mode response time, which is simple and fast. AMC-max considers every possible time of the criticality switch and takes the worst. It accepts more task sets but needs more computation.

Can Linux be used in a mixed-criticality system?

Yes, typically as the low-criticality guest beside an RTOS or bare-metal partition on a hypervisor, or on separate cores of a heterogeneous SoC. Using Linux for high-criticality functions is an active research and qualification topic (for example in the ELISA project), not established practice. See our RTOS comparison for platform options.

References and further reading

1. S. Vestal, “Preemptive Scheduling of Multi-Criticality Systems with Varying Degrees of Execution Time Assurance,” Proc. IEEE Real-Time Systems Symposium (RTSS), 2007.
2. S. Baruah, A. Burns and R. I. Davis, “Response-Time Analysis for Mixed Criticality Systems,” Proc. IEEE RTSS, 2011.
3. S. Baruah, V. Bonifaci, G. D’Angelo, H. Li, A. Marchetti-Spaccamela, S. van der Ster and L. Stougie, “The Preemptive Uniprocessor Scheduling of Mixed-Criticality Implicit-Deadline Sporadic Task Systems,” Proc. ECRTS, 2012.
4. R. Ernst and M. Di Natale, “Mixed Criticality Systems—A History of Misconceptions?,” IEEE Design & Test, 33(5), 2016.
5. A. Burns and R. I. Davis, “Mixed Criticality Systems: A Review,” University of York (regularly updated technical report).
6. Mixed criticality — Wikipedia
7. ARINC 653 — Wikipedia