Seminar details

Abstract: Modern real-time systems tend to be mixed-critical, in the sense that they integrate on the same computational platform applications at different levels of criticality (e.g., safety critical and mission critical). Integration gives the advantages of reduced cost, weight and power consumption, which can be crucial for modern applications like Unmanned Aerial Vehicles (UAVs). On the other hand, this leads to major complications in system design. Moreover, such systems are subject to certification, and different criticality levels needs to be certified at different level of assurance.
Among other aspects, the real-time scheduling of certifiable mixed critical systems has been recognized to be a challenging problem. Traditional techniques require complete isolation between criticality levels or global certification to the highest level of assurance, which leads to resource waste, thus loosing the advantage of integration. This led to a novel wave of research in the real-time community, and many solutions were proposed. Among those, one of the most popular methods used to schedule such systems is Audsley approach. However this method has some limitations, which we discuss in this thesis. These limitations are more pronounced in the case of multiprocessor scheduling. In this case priority-based scheduling looses some important properties. For this reason scheduling algorithms for multiprocessor mixed-critical systems are not as numerous in literature as the single processor ones, and usually are built on restrictive assumptions. This is particularly problematic since industrial real-time systems strive to migrate from single-core to multi-core and many-core platforms.
Therefore we motivate and study a different approach that can overcome these problems.
For this reason we assume a fixed set of jobs as workload model. This model can represent
a hyperperiod of synchronous periodic tasks or servers. These removes some fundamental difficulties of non-synchronous systems (at risk to increase costs in some cases), thus leaving us more space to focus on limitations of Audsley approach and on overcoming the schedulability complications brought about by multiprocessor systems. Fixed job sets permit us to manipulate their priorities by using the novel concept of priority graph (P-DAG), which defines minimal relation between priorities in a schedule. Based on this formalism we propose two priority based algorithms. The first algorithm, Mixed Criticality Earliest Deadline First (MCEDF), is a single processor algorithm that dominates state-of-the-art Audsley approach based algorithm Own Criticality Based Priority (OCBP). The second one is a multiprocessor algorithm, Mixed Criticality Priority Improvement (MCPI), that, given
a global fixed-priority assignment for jobs, can modify it in order to iteratively improve its schedulability for mixed-criticality setting. Our experiments show an increase of schedulable instances up to a maximum of 30% if compared to classical solutions for this category of scheduling problems.
A restriction of practical usability of many mixed-critical and multiprocessor scheduling algorithms is assumption that jobs are independent. In reality they often have precedence constraints. In the thesis we show the mixed-critical variant of the problem formulation and extend the system load metrics to the case of precedence-constraint task graphs. We also show that our proposed methodology and scheduling algorithm MCPI can be extended to the case of dependent jobs without major modification and showing similar performance with respect to the independent jobs case.
Another topic we treated in this thesis is time-triggered scheduling. This class of schedulers is important because they considerably reduce the uncertainty of job execution intervals thus simplifying the safety-critical system certification (where simplicity is a decisive factor). They also simplify any auxiliary timing-based analyses that may be required to validate important extra-functional properties in embedded systems, such as interference on shared buses and caches, peak power dissipation, electromagnetic interference etc..
The trivial method of obtaining a time-triggered schedule is simulation of the worst-case scenario in event-triggered algorithm. However, when applied directly, this method is not efficient for mixed-critical systems, as instead of one worst-case scenario they have multiple corner-case scenarios. For this reason, it was proposed in the literature to treat all scenarios into just a few tables, one per criticality mode. We call this scheduling approach Single Time Table per Mode (STTM) and propose a contribution in this context. In fact we introduce a method that transforms practically any scheduling algorithm into an STTM one, which is again based on a simulation, but it is adapted to ensure safe switching between the scenarios. It works optimally on single core and shows good experimental results for multi-cores. In addition we show that applying it to list scheduling leads to support of task graph (precedence) dependencies, for which our method also shows good experimental results. Finally we studied the problem of the practical realization of mixed critical systems.
This is a challenging task due to a semantic gap between real-time scheduling policies and the various models of computation proposed for programming timing-critical concurrent systems. To overcome this difficulty, we represented both the models of computation and the scheduling policies by timed automata. We believe that using the same formal language for the model of computation and the scheduling techniques is an important step to close the gap between them. Our effort in this direction is a design flow that we propose for multicore mixed critical systems. In this design flow, as the model of computation we propose a network of deterministic multi-periodic synchronous processes. Our approach is demonstrated using a publicly available toolset, an industrial application use case and a multi-core platform. An ongoing work is integration of the proposed design flow with time-triggered variant of lits scheduling.