Design of Mixed-Criticality Applications on Distributed Real-Time Systems

A mixed-criticality system implements applications of different safety-criticality levels onto the same platform. In such cases, the certification standards require that applications of different criticality levels are protected so they cannot influence each other. Otherwise, all tasks have to be developed and certified according to the highest criticality level, dramatically increasing the development costs.

In this thesis we consider mixed-criticality real-time applications implemented on distributed partitioned architectures. Partitioned architectures use temporal and spatial separation mechanisms to ensure that applications of different criticality levels do not interfere with each other. With temporal partitioning, each application is allowed to run only within predefined time slots, allocated on each processor.

The sequence of time slots for all the applications on a processor are grouped within a Major Frame, which is repeated periodically. Each partition can have its own scheduling policy; we have considered non-preemptive static cyclic scheduling and fixed-priority preemptive scheduling policies. We assume that the communication network implements the TTEthernet protocol, which supports Time-Triggered (TT) messages transmitted based on static schedule tables, Rate Constrained (RC) messages with bounded end-to-end delay, and Best-Effort (BE) messages, for which no timing guarantees are provided.

TTEthernet offers spatial separation for mixed-criticality messages through the concept of virtual links, and temporal separation, enforced through schedule tables for TT messages and bandwidth allocation for RC messages. The objective of this thesis is to develop methods and tools for distributed mixed-criticality real-time systems.

At the processor level, we are interested to determine (i) the mapping of tasks to processors, (ii) the assignment of tasks to partitions, (iii) the decomposition of tasks into redundant lower criticality tasks, (iv) the sequence and size of the partition time slots on each processor and (v) the schedule tables, such that all the applications are schedulable and the development and certification costs are minimized.

We have proposed Simulated Annealing and Tabu Search metaheuristics to solve these optimization problems. The proposed algorithms have been evaluated using several benchmarks. At the communication network level, we are interested in the design optimization of TTEthernet networks used to transmit mixed-criticality messages.

Given the set of TT and RC messages, and the topology of the network, we are interested to optimize (i) the packing of messages in frames, (ii) the assignment of frames to virtual links, (iii) the routing of virtual links and (iv) the TT static schedules, such that all frames are schedulable and the worst-case end-to-end delay of the RC messages is minimized.

We have proposed a Tabu Search-based metaheuristic for this optimization problem. The proposed algorithm has been evaluated using several benchmarks. The optimization approaches have also been evaluated using realistic aerospace case studies. In this context, we have shown how to extend the proposed optimization frameworks to also take into account quality of service constraints.

For TTEthernet networks, we have also proposed a topology selection method to reduce the cost of the architecture.