## 2 Related Work  
Since Vestal's first mixed criticality model formalization [14], MCSs have attracted particular attention that has materialized in a set of scheduling algorithms that can be classified based on their scheduling points (i.e., the moments in time when scheduling decisions are made) into three categories: event-driven, time-triggered, and hierarchical scheduling approaches.  
An extensive survey on scheduling in MCSs [9] shows that, until recently, the scheduling problem was mainly focused on event-driven scheduling algorithms, despite the fact that there are also important endeavors regarding time-triggered and hybrid approaches. In event-driven schedulers, the scheduling points are defined by task completion and task arrival events. Examples of event-driven schedulers were introduced in [15; 16; 17; 18; 19]. A popular event-driven scheduling algorithm in MCSs is Earliest Deadline First with Virtual Deadlines (EDF-VD) for two criticality levels (Hi--high criticality and Lo--low criticality) [13]. The algorithm computes a virtual deadline for every Hi-criticality task if the system is in Lo mode. In Hi mode, Hi-criticality tasks are scheduled according to their real deadlines. This is done in order to balance the schedulability on different criticality levels, which results in better schedulability and run-time performance.  
Due to their predictability, time-triggered approaches have become increasingly popular in the last couple of years, but the relevant works are still limited and much more could be expected in the future. Time-triggered schedulers make their scheduling decisions at predetermined points in time. Few papers tackling MC scheduling in time-triggered environments appeared only in the last decade [6; 10; 12; 20; 21]. In [20], a heuristic for constructing scheduling tables in a time-triggered environment was presented. The algorithm relies on backtracking to guide the search in a tree-based structure, and it consists of two heuristics: one for constructing the scheduling tables and the other for backtracking. Another method for constructing scheduling tables based on priority ordering is described in [10]. The technique incorporates \"mode-change\", which increases flexibility and system performance. In [21], a time-triggered scheduling algorithm for both independent and dependent MC jobs on an identical multiprocessor platform is proposed. Two separate scheduling tables are constructed for each processor to schedule dual-criticality tasks. Furthermore, the schedule is global, which means that jobs can be preempted in one processor and resume their execution in another processor. While the algorithms mentioned before are focused on predictability, the main goal of the algorithm proposed in [6] is to provide a low-jitter periodic schedule for mixed criticality messages in a time-triggered non-preemptive environment. Additionally, the algorithm introduced in [12] is meant to reduce the energy consumption. However, none of the algorithms mentioned above are focused on guaranteeing jitterless execution in a mixed criticality system, for all the active tasks, regardless of the system criticality mode. This is obviously a requirement for many safety-critical systems and represents the gap we aim to fill in this paper.  
Hierarchical approaches combine both scheduling tables and event-driven scheduling methods, but the research on such systems is still in its preliminary stage. A hierarchical algorithm was introduced in [22] for scheduling MC real-time tasks on multiprocessor platforms. The method provides temporal isolation among tasks of different criticalities while allowing slack to be redistributed across different criticality levels. The same algorithm was implemented and tested on a standard real-time operating system (RTOS) in [23]. The experimental results showed that RTOS-related overheads are maintained at acceptable levels and the system is robust with respect to breaches of optimistic execution time assumptions.