Scheduling of MCS

Provided by: TUKL


Criticality is a designation of the level of assurance against failure needed for a system component. A mixed criticality system (MCS) is one that has two or more distinct levels (for example safety critical, mission critical and low-critical). A key aspect of Mixed-Criticality Systems is that task's worst-case execution time (WCET), period and/or deadline become dependent on the criticality level of the tasks. Based on the requirement of the application, a task may execute in multiple criticality levels. A system starts in the lowest criticality mode (i.e. the mode with all tasks from all criticality levels). If all jobs of a task behave according to this mode then the task stays in that mode. But if any/some job attempts to execute for a longer time, or more frequently or with a shorter deadline, than is acceptable in that mode then a criticality mode change occurs. Ultimately the system may change to the highest criticality mode.


From the perspective of implementation, separation is the primary concern of mixed-criticality systems. Tasks from different components must not be allowed to interfere with each other. After concerns of partitioning comes the need to use resources efficiently. This is facilitated by noting that the task parameters are not independent, in particular the worst-case computation/execution time estimate will be derived by a process dictated by the criticality level. The higher the criticality level, the more conservative the verification process and hence the greater will be the WCET. This assumption was the heart of the first paper on mixed-criticality [1]. Although it is reasonable to assume confidence increases (i.e. uncertainty decreases) with larger estimates of worst-case execution time, this may not be universally true [2].


The variation of the tasks' parameters, while execution, creates difficulties in guaranteeing schedulability. Vestal in 2007 [1] showed that neither rate-monotonic nor deadline-monotonic priority assignment was optimal for mixed-criticality systems; however Audsley's optimal priority assignment algorithm [3] was found to be applicable. Baruah and Vestal [4] generalized Vestal's model by using a sporadic task model and by assessing fixed job-priority scheduling and dynamic priority scheduling. It contains the important result that Earliest Deadline First (EDF) does not dominate Fixed Priority (FP) when criticality levels are introduced, and that there are feasible systems that cannot be scheduled by EDF.


In FP scheduling, response time analysis based algorithms are often used to guarantee schedulability (e.g. [5]). Since the problem, in general, is not easy to solve, other approaches are also used. For example, Slack stealing [6] was used to use the slack from lower criticality tasks to service higher criticality tasks and Period transformation [7] was utilized to assign the priority such that in the worst-case, the deadlines and the criticalities are respected.


Similarly, dynamic priority scheduling is also a viable solution for mixed-criticality systems. Usually deadline tightening algorithms (e.g. [8]) are used to specify a closer deadline for high criticality tasks such that the remaining slack is enough to execute lower criticality tasks. In the worst case, the lower criticality tasks are rejected. These algorithms can be applied when the system is running or before the system starts executing, i.e. offline.


Resource sharing is also an important aspect of mixed-criticality systems. In [9], Stack Resource Protocol was extended for mixed-criticality systems. Priority and Criticality Inheritance Protocol [10] was defined as an extension of Priority Inheritance Protocol and Highest Locker Criticality Priority Ceiling Protocol [11] was defined by inclusion of criticality levels in Priority Ceiling Protocol.


In compositional hierarchical scheduling, virtual processors are assigned a budget. These virtual processors execute single/multiple criticality tasks with either FP or EDF scheduling approaches. The supply bound function and the demand bound functions are then derived, a simple comparison of which provides guarantees if the given taskset is schedulable with the defined set of budgets. Since pure compositional scheduling suffers a loss of performance in mixed-criticality systems [12], a number of non-compositional strategies are developed to circumvent this performance loss. For example, flattening of hierarchy components [12] was proposed in which multiple budgets were assigned to each partition. Other non-compositional strategies employ complex priority resolution algorithms which are run offline (e.g. [13]) to generate offline scheduling table or define an upper bound for each criticality level by using a simple online scheduler which uses barriers to synchronize the end of partitions (e.g. [14]).



[1] S. Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proc. of the IEEE Real-Time Systems Symposium (RTSS), pages 239–243, 2007

[2] P. Graydon and I. Bate. Safety assurance driven problem formulation for mixed-criticality scheduling. In Proc. WMC, RTSS, pages 19–24, 2013

[3] N.C. Audsley. On priority assignment in fixed priority scheduling. Information Processing Letters, 79(1):39–44, 2001

[4] S.K. Baruah and S. Vestal. Schedulability analysis of sporadic tasks with multiple criticality specifications. In ECRTS, pages 147–155, 2008

[5] Q. Zhao, Z. Gu, and H. Zeng. PT-AMC: Integrating preemption thresholds into mixed-criticality scheduling. In Proc. DATE, pages 141–146, 2013

[6] Niz, L. Wrage, A. Rowe, and R. Rajkumar. Utility-based resource overbooking for cyber-physical systems. In Proc. RTCSA, 2013

[7] S. Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proc. of the IEEE Real-Time Systems Symposium (RTSS), pages 239–243, 2007

[8] C. Yao, L. Qiao, L. Zheng, and X. Huagang. Efficient schedulability analysis for mixed-criticality systems under deadline-based scheduling. Chinese Journal of Aeronautics, 2014

[9] Q. Zhao, Z. Gu, and H. Zeng. Integration of resource synchronization and preemption-thresholds into EDF-based mixed-criticality scheduling algorithm. In Proc. RTCSA, 2013

[10] K. Lakshmanan, D. de Niz, and R. Rajkumar. Mixed-criticality task synchronization in zero-slack scheduling. In IEEE RTAS, pages 47–56, 2011

[11] Q. Zhao, Z. Gu, and H. Zeng. HLC-PCP: A resource synchronization protocol for certifiable mixed criticality scheduling. Embedded Systems Letters, IEEE, 6(1), 2014

[12] A. Lackorzynski, A. Warg, M. Voelp, and H. Haertig. Flattening hierarchical scheduling. In Proc. ACM EMSOFT, pages 93–102, 2012

[13] D. Tamas-Selicean and P. Pop. Design optimisation of mixed criticality real-time applications on cost-constrained partitioned architectures. In Real-Time Systems Symposium (RTSS), pages 24–33, 2011

[14] G. Giannopoulou, N. Stoimenov, P. Huang, and L. Thiele. Scheduling of mixed-criticality applications on resource-sharing multicore systems. In Proc. Int. Conference on Embedded Software (EMSOFT), Montreal, 2013

[15] Mixed Criticality Systems - A Review (6th Edition), Alan Burns and Robert I. Davis, July 2015