This paper is concerned with the problem of scheduling sporadic mixed-criticality tasks in uniprocessor systems. In these systems, tasks may not have fixed periods but minimum inter-arrival times. Further, they may have different criticality levels that determine the importance of the results computed. The system is required to complete the execution of higher critical tasks in preference to others in case of resource constraints.

This paper proposes a new model of real-time tasks, the model-switching directed real-time (MSDRT) task model. The behavior of each task is described by a directed graph that captures system criticality (in terms of node coloring) in addition to the other standard features, execution budget, period, and deadline. Each graph describes a finite number of modes, and mode switching happens via special edges that are distinguished from the standard edges that model job creation. Every path in the task graph represents a particular job arrival sequence for the task. There are as many graphs as there are tasks and it is assumed that all the tasks switch their modes simultaneously. Based upon the model, the paper presents, and proves correct, a sufficient condition for earliest deadline first (EDF) scheduling of a set of tasks described by MSDRT.

The proposed model generalizes the known DRT model of sporadic real-time tasks. The sufficient condition for EDF scheduling generalizes the condition developed for the DRT task model and builds on the results from the authors’ work on mixed-criticality task sets. As is customary in this area, the sufficient condition is based upon the demand bound function computation; the paper synthesizes the two earlier works in this area.

The paper is well written though not accessible to beginners in the area. A thorough understanding of the earlier works in this area is essential for appreciating the derivation of the sufficient condition in the paper. An informal and intuitive summary of the approach could have helped. Also, a formal semantics of MSDRT would have made the description complete.

The paper is recommended for specialists in the area.