Seminar Room Part 1, ground floor (Building IMAG)
26 June 2019 - 14h00
Schedulability in Mixed- criticality Systems (Phd Defense)
by Rany Kahil from Verimag, Université Grenoble Alpes
Abstract: Real-time safety-critical systems must complete their tasks within a given time limit.
Failure to successfully perform their operations, or missing a deadline, can have se-
vere consequences such as destruction of property and/or loss of life. Examples of such
systems include automotive systems, drones and avionics among others. Safety guar-
antees must be provided before these systems can be deemed usable. This is usually
done through certification performed by a third party, a certification authority. Safety
evaluation and certification are complicated and costly even for smaller systems.
One answer to these difficulties is the isolation of the critical functionality. Execut-
ing tasks of different criticalities on separate platforms prevents non-critical tasks from
interfering with critical ones, provides a higher guaranty of safety and simplifies the
certification process limiting it to only the critical functions. But this separation, in
turn, introduces undesirable results portrayed by an inefficient resource utilization, an
increase in the cost, weight, size and energy consumption which can put a system in a
competitive disadvantage.
To overcome the drawbacks of isolation, Mixed Criticality (MC) systems can be used.
These systems allow functionalities with different criticalities to execute on the same
platform. In 2007, Vestal proposed a model to represent MC-systems where tasks have
multiple Worst Case Execution Times (WCETs), one for each criticality level. In addi-
tion, correctness conditions for scheduling policies were formally defined, allowing lower
criticality jobs to miss deadlines or be even dropped in cases of failure or emergency
situations. The introduction of multiple WCETs and different conditions for correct-
ness increased the difficulty of the scheduling problem for MC-systems. Conventional
scheduling policies and schedulability tests proved inadequate and the need for new
algorithms arose. Since then, a lot of work has been done in this field.
In this thesis, we contribute to the study of schedulability in MC-systems. The workload
of a system is represented as a set of jobs that can describe the execution over the hyper-
period of tasks or over a duration in time. This model allows us to study the viability
of simulation-based correctness tests in MC-systems. We show that simulation tests can
still be used in mixed-criticality systems, but in this case, the schedulability of the worst
case scenario is no longer sufficient to guarantee the schedulability of the system even for
the fixed priority scheduling case. We show that scheduling policies are not predictable
in general, and define the concept of weak-predictability for MC-systems. We prove
that a specific class of fixed priority policies are weakly predictable and propose two simulation-based correctness tests that work for weakly-predictable policies. We also
demonstrate that contrary to what was believed, testing for correctness can not be done
only through a linear number of preemptions.
The majority of the related work focuses on systems of two criticality levels due to the
difficulty of the problem. But for automotive and airborne systems, industrial standards
define four or five criticality levels, which motivated us to propose a scheduling algorithm
that schedules mixed-criticality systems with theoretically any number of criticality lev-
els. We show experimentally that it has higher success rates compared to the state of
the art.
We illustrate how our scheduling algorithm, or any algorithm that generates a single
time-triggered table for each criticality mode, can be used as a recovery strategy to
ensure the safety of the system in case of certain failures. To do so, we representing
the system as a set of synchronized timed-automata components, where the scheduling
algorithm is modeled as a timed-automaton that acts as a part of the Fault Detection
Isolation and Recovery (FDIR) component in the system.
Finally, we propose a high level concurrency language and a model for designing an
MC-system with coarse grained multi-core interference.
