Thumbnail
Access Restriction
Subscribed

Author Baruah, Sanjoy ♦ Bonifaci, Vincenzo ♦ Dangelo, Gianlorenzo ♦ Li, Haohan ♦ Marchetti-Spaccamela, Alberto ♦ Van Der Ster, Suzanne ♦ Stougie, Leen
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Mixed criticality ♦ Preemptive scheduling ♦ Sporadic task system
Abstract Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the rest of the functionality is non-safety-critical and does not need to be certified, or is certified to lower levels of assurance. The certification-cognizant runtime scheduling of such mixed-criticality systems is considered. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is presented: this algorithm can schedule systems for which any number of criticality levels are defined. Efficient implementations of EDF-VD, as well as associated schedulability tests for determining whether a task system can be correctly scheduled using EDF-VD, are presented. For up to 13 criticality levels, analyses of EDF-VD, based on metrics such as processor speedup factor and utilization bounds, are derived, and conditions under which EDF-VD is optimal with respect to these metrics are identified. Finally, two extensions of EDF-VD are discussed that enhance its applicability. The extensions are aimed at scheduling a wider range of task sets, while preserving the favorable worst-case resource usage guarantees of the basic algorithm.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-05-06
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 2
Page Count 33
Starting Page 1
Ending Page 33


Open content in new tab

   Open content in new tab
Source: ACM Digital Library