Many systems have several criticality levels: the safety-critical level, which is a higher criticality level, including all the tasks in which a deadline failure would provoke catastrophic effects on the system or even on humans; and mission-critical applications, a lower criticality level, which affect the quality of the service, but no safety issues result from a violation of their deadlines. These types of systems are called imprecise mixed-criticality (IMC) models.

This paper presents a study of “the scheduling problem of the IMC model under earliest deadline first with virtual deadline (EDF-VD) scheduling.” The authors provide several analyses on this scheme.

Liu et al. first analyze a schedulability test based on the utilization degree and then describe a speedup test. As there are two criticality levels, two utilization ratios are used (a ratio for each criticality level). The authors show that the speedup factor bound of EDF-VD is 4/3, which is the known value determined by other authors. This speedup factor is obtained with a high-criticality task utilization ratio of 1/3 and a low-criticality task utilization ratio of zero. It means that the high-criticality task consumes up to 1/3 of the time, whereas the low-criticality task consumes no central processing unit (CPU) time. This is the classical mixed-criticality task set.

Next, the authors analyze a demand bound function (DBF) test (instead of the classical utilization-based test). They measure the maximum cumulative utilization of a given task within a certain period. With the DBF test, more generic cases for scheduling IMC tasks and virtual deadlines can be tuned individually in order to achieve schedulability. The virtual deadlines of the high-criticality tasks can be reduced, while schedulability is ensured for both the high- and low-criticality tasks. However, if the scheduler tunes down virtual deadlines, the low-criticality task set may become unschedulable. In order to solve this problem, the authors propose a new deadline tuning algorithm (DTA) that performs better than three other methods (AMC, UTIL, MCF) in terms of average acceptance ratio.

DTA is also compared with another tuning algorithm, EYE. The analysis shows that EYE has a slightly higher acceptance ratio than DTA, although the efficiency ratio of DTA is 1000 times higher than EYE. Finally, practical implementation is discussed in the last section of the paper.

As a summary, the authors provide a thorough analysis of the IMC model under EDF-VD. This very interesting paper is suitable for specialists in the field, not general readers.