We consider scheduling an implicit-deadline sporadic task system on a single machine in a mixed-criticality (MC) setting. MC systems arise when multiple functionalities are scheduled upon a shared computing platform. This can force tasks of different importance (i.e. criticality) to share a processor.

Each task generates a (possibly infinite) string of jobs, released with an interarrival separation bounded from below by a task-dependent period. Each job has a relative deadline equal to the length of that period.

In an MC setting, each task has multiple levels of worst-case execution times and its own criticality level. By executing the tasks, we learn what level the system is in, which may change over time. When the system is in level k, all jobs of tasks of level at least k should be scheduled for their level-k execution time, to meet their deadline.

We give an algorithm for scheduling an MC task system, called EDF-VD (Earliest Deadline First with Virtual Deadlines). We give sufficient conditions to check feasibility efficiently for K levels. We show that if a 2-level task system is schedulable on a unit-speed processor, it is correctly scheduled by EDF-VD on a processor of speed 4/3.