Mixed-Criticality scheduling of sporadic task systems

We consider the scheduling of mixed-criticality task systems, that is, systems where each task to be scheduled has multiple levels of worst-case execution time estimates. We design a scheduling algorithm, EDF-VD, whose effectiveness we analyze using the processor speedup metric: we show that any 2-level task system that is schedulable on a unit-speed processor is correctly scheduled by EDF-VD using speed φ here φ<1.619 is the golden ratio. We also show how to generalize the algorithm to K>2 criticality levels.We finally consider 2-level instances on m identical machines. We prove speedup bounds for scheduling an independent collection of jobs and for the partitioned scheduling of a 2-level task system. © 2011 Springer-Verlag Berlin Heidelberg.