  Systems in many safety-critical application domains are subject to
certification requirements. In such a system, there are typically different
applications providing functionalities that have varying degrees of
criticality. Consequently, the certification requirements for functionalities
at these different criticality levels are also varying, with very high levels
of assurance required for a highly critical functionality, whereas relatively
low levels of assurance required for a less critical functionality. Considering
the timing assurance given to various applications in the form of guaranteed
budgets within deadlines, a theory of real-time scheduling for such
multi-criticality systems has been under development in the recent past. In
particular, an algorithm called Earliest Deadline First with Virtual Deadlines
(EDF-VD) has shown a lot of promise for systems with two criticality levels,
especially in terms of practical performance demonstrated through experiment
results. In this paper we design a new schedulability test for EDF-VD that
extend these performance benefits to multi-criticality systems. We propose a
new test based on demand bound functions and also present a novel virtual
deadline assignment strategy. Through extensive experiments we show that the
proposed technique significantly outperforms existing strategies for a variety
of generic real-time systems.
