Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Scheduling analysis of imprecise mixed-criticality real-time tasks
Liu D., Guan N., Spasic J., Chen G., Liu S., Stefanov T., Yi W. IEEE Transactions on Computers67 (7):975-991,2018.Type:Article
Date Reviewed: Nov 12 2018

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.

Reviewer:  José Manuel Palomares Review #: CR146317 (1902-0053)
Bookmark and Share
  Featured Reviewer  
Scheduling (I.2.8 ... )
Real-Time And Embedded Systems (C.3 ... )
Models Of Computation (F.1.1 )
Would you recommend this review?
Other reviews under "Scheduling": Date
A knowledge-based decision support system for the management of parts and tools in FMS
Özbayrak M., Bell R. Decision Support Systems 35(4): 487-515, 2003. Type: Article
Oct 9 2003
Scheduling in the grid application development software project
Dail H., Sievert O., Berman F., Casanova H., YarKhan A., Vadhiyar S., Dongarra J., Liu C., Yang L., Angulo D., Foster I. In Grid resource management. Norwell, MA: Kluwer Academic Publishers, 2004. Type: Book Chapter
May 7 2004
Applying economic scheduling methods to grid environments
Ernemann C., Yahyapour R. In Grid resource management. Norwell, MA: Kluwer Academic Publishers, 2004. Type: Book Chapter
Jun 3 2004

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy