On the Scheduling of Mixed-Criticality Real-Time Task Sets
Authors:
- Dionisio de NizDNDionisio de Niz
- Karthik LakshmananKLKarthik Lakshmanan
- Ragunathan RajkumarRRRagunathan Rajkumar
- 1 December 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10528725,p. 291-300
Abstract
The functional consolidation induced by the cost reduction trends in embedded systems can force tasks of different criticality (e.g. ABS Brakes with DVD) to share a processor and interfere with each other. These systems are known as mixed criticality systems. While traditional temporal isolation techniques prevent all inter-task interference, they waste utilization because they need to reserve for the absolute worst-case execution time (WCET) for all tasks. In many mixed-criticality systems the WCET is not only rare, but at times difficult to calculate, such as the time to localize all possible objects in an obstacle avoidance algorithm. In this situation it is more appropriate to allow the execution time to grow by stealing cycles from lower-criticality tasks. Even more crucial is the fact that temporal isolation techniques can stop a high-criticality task (that was overrunning its nomimal WCET) to allow a low-criticality task to run, making the former miss its deadline. We identify this as the criticality inversion problem. In this paper, we characterize the criticality inversion problem and present a new scheduling scheme called zero-slack scheduling that implements an alternative protection scheme we refer to as asymmetric protection. This protection only prevents interference from lower-criticality to higher-criticality tasks and improves the schedulable utilization. We use an offline algorithm with two parts: a zero-slack calculation algorithm, and a slack analysis algorithm. The zero-slack calculation algorithm minimizes the utilization needed by a task set by reducing the time low-criticality tasks are preempted by high-criticality ones. This algorithm can be used with priority-based preemptive schedulers (e.g. RMS, EDF). The slack analysis algorithm is specific for each priority-based preemptive scheduler and we develop and evaluated the one for RMS. We prove that this algorithm provides the same level of protection against criticality inversion as the best known priority assignment for this purpose, criticality as priority assignment (CAPA). We also prove that zero-slack RM provides the same level of schedulable utilization as RMS when all tasks have equal criticality levels. Finally, we present our implementation of the runtime enforcement mechanisms in Linux/RK to demonstrate its practicality.Keywords
This publication has 15 references indexed in Scilit:
- Schedulability Analysis of Sporadic Tasks with Multiple Criticality Specifications2008
- Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance2007
- EDZL Scheduling Analysis19th Euromicro Conference on Real-Time Systems (ECRTS'07), 2007
- Sustainable Scheduling Analysis2006
- Elastic task model for adaptive rate control2002
- Dual priority scheduling2002
- An extendible approach for analyzing fixed priority hard real-time tasksReal-Time Systems, 1994
- Priority inheritance protocols: an approach to real-time synchronizationIEEE Transactions on Computers, 1990
- Aperiodic task scheduling for Hard-Real-Time systemsReal-Time Systems, 1989
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973