Scheduling of mixed-criticality sporadic task systems with multiple levels

There is an increasing trend in embedded systems towards implementing multiple functionalities upon a single shared computing platform. This can force tasks of dif-ferent criticality to share a processor and interfere with each other. We focus on the scheduling of sporadic task systems [3] in these mixed-criticality (MC) systems. The mixed-criticality model that we follow has first been proposed and analyzed, for inde-pendent collection of jobs, by Baruah et al. [1]. The model has been extended to task systems by Li and Baruah [5]. The results presented here appear in Baruah et al. [2]. We first describe the model and give some notation. Then, we describe an algorithm (called EDF-VD) to preemptively schedule MC task systems on a single machine. We give a sufficient condition for schedulability by EDF-VD and derive a speed-up guarantee. The model. Given an integer K ≥ 1, A K-level MC sporadic task system τ consists of a finite collection (τ1,..., τn) of MC sporadic tasks. An MC sporadic task τi of a K-level system is characterized by a criticality level χi ∈ {1, 2,...,K} and a pair (ci, di) ∈ Qχi+×Q+, where: ci = (ci(1), ci(2),..., ci(K)) is a vector of worst-case execution times (WCET), we assume that ci(1) ≤ ci(2) ≤... ≤ ci(χi) and ci(χi) = ci(χi + 1) =... = ci(K); di is the relative deadline of the jobs of τi. We consider impicit-deadlin