{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:44:05Z","timestamp":1778496245449,"version":"3.51.4"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,5,6]],"date-time":"2015-05-06T00:00:00Z","timestamp":1430870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1016954, CNS 1115284, CNS 1218693, CNS 1409175"],"award-info":[{"award-number":["CNS 1016954, CNS 1115284, CNS 1218693, CNS 1409175"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-09-1-0535"],"award-info":[{"award-number":["W911NF-09-1-0535"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,5,6]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2699435","type":"journal-article","created":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T16:30:57Z","timestamp":1431361857000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":74,"title":["Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems"],"prefix":"10.1145","volume":"62","author":[{"given":"Sanjoy","family":"Baruah","sequence":"first","affiliation":[{"name":"University of North Carolina, Chapel Hill, NC"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincenzo","family":"Bonifaci","sequence":"additional","affiliation":[{"name":"IASI -- Consiglio Nazionale delle Ricerche, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianlorenzo","family":"D'angelo","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute (GSSI), L'Aquila, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haohan","family":"Li","sequence":"additional","affiliation":[{"name":"University of North Carolina"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[{"name":"Sapienza Universit\u00e0 di Roma, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suzanne","family":"Van Der Ster","sequence":"additional","affiliation":[{"name":"Vrije Universiteit Amsterdam, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[{"name":"Vrije Universiteit Amsterdam &amp; CWI, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,5,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009383.1009837"},{"key":"e_1_2_1_2_1","unstructured":"J. Barhorst T. Belote P. Binns J. Hoffman J. Paunicka P. Sarathy J. S. P. Stanfill D. Stuart and R. Urzi. 2009. A research agenda for mixed-criticality systems. White paper. http:\/\/www.cse.wustl.edu\/&sim;cdgill\/CPSWEEK09&lowbar;MCAR\/.  J. Barhorst T. Belote P. Binns J. Hoffman J. Paunicka P. Sarathy J. S. P. Stanfill D. Stuart and R. Urzi. 2009. A research agenda for mixed-criticality systems. White paper. http:\/\/www.cse.wustl.edu\/&sim;cdgill\/CPSWEEK09&lowbar;MCAR\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2011.142"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90360-6"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ISCA International Conference on Computers and their Applications. ISCA","author":"Baruah S. K.","unstructured":"S. K. Baruah , H. Li , and L. Stougie . 2010a. Mixed-Criticality scheduling: Improved resource-augmentation results . In Proceedings of the ISCA International Conference on Computers and their Applications. ISCA , Los Alamitos, CA, 217--223. S. K. Baruah, H. Li, and L. Stougie. 2010a. Mixed-Criticality scheduling: Improved resource-augmentation results. In Proceedings of the ISCA International Conference on Computers and their Applications. ISCA, Los Alamitos, CA, 217--223."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2010.10"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556780903087124"},{"key":"e_1_2_1_8_1","unstructured":"S. Boyd and L. Vandenberghe. 2009. Convex Optimization. Cambridge University Press Cambridge UK.   S. Boyd and L. Vandenberghe. 2009. Convex Optimization. Cambridge University Press Cambridge UK."},{"key":"e_1_2_1_9_1","unstructured":"A. Burns and R. I. Davis. 2013. Mixed criticality systems - A Review. http:\/\/www-users.cs.york.ac.uk\/&sim;burns\/review.pdf.  A. Burns and R. I. Davis. 2013. Mixed criticality systems - A Review. http:\/\/www-users.cs.york.ac.uk\/&sim;burns\/review.pdf."},{"key":"e_1_2_1_10_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms 3rd Ed. MIT Press Cambridge MA.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms 3rd Ed. MIT Press Cambridge MA."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Federation for Information Processing Congress. North-Holland","author":"Dertouzos M. L.","year":"1974","unstructured":"M. L. Dertouzos . 1974 . Control robotics: The procedural control of physical processes . In Proceedings of the International Federation for Information Processing Congress. North-Holland , Amsterdam, 807--813. M. L. Dertouzos. 1974. Control robotics: The procedural control of physical processes. In Proceedings of the International Federation for Information Processing Congress. North-Holland, Amsterdam, 807--813."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2013.16"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2012.24"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-013-9187-z"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2011.10"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(82)90024-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2010.18"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 5th IEEE Workshop on Real-Time Software and Operating Systems. USENIX Association","author":"Mok A. K.","year":"1988","unstructured":"A. K. Mok . 1988 . Task management techniques for enforcing ED scheduling on periodic task set . In Proceedings of the 5th IEEE Workshop on Real-Time Software and Operating Systems. USENIX Association , Washington, DC, 42--46. A. K. Mok. 1988. Task management techniques for enforcing ED scheduling on periodic task set. In Proceedings of the 5th IEEE Workshop on Real-Time Software and Operating Systems. USENIX Association, Washington, DC, 42--46."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the IEEE National Aerospace and Electronics Conference","volume":"1","author":"Prisaznuk P. J.","year":"1992","unstructured":"P. J. Prisaznuk . 1992 . Integrated modular avionics . In Proceedings of the IEEE National Aerospace and Electronics Conference , Vol. 1 . IEEE, Los Alamitos, CA, 39--45. P. J. Prisaznuk. 1992. Integrated modular avionics. In Proceedings of the IEEE National Aerospace and Electronics Conference, Vol. 1. IEEE, Los Alamitos, CA, 39--45."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Conference on Design, Automation & Test in Europe. EDA Consortium","author":"Su H.","unstructured":"H. Su and D. Zhu . 2013. An elastic mixed-criticality task model and its scheduling algorithm . In Proceedings of the Conference on Design, Automation & Test in Europe. EDA Consortium , San Jose, CA, 147--152. H. Su and D. Zhu. 2013. An elastic mixed-criticality task model and its scheduling algorithm. In Proceedings of the Conference on Design, Automation & Test in Europe. EDA Consortium, San Jose, CA, 147--152."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.35"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699435","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699435","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:58Z","timestamp":1750227418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699435"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,6]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,5,6]]}},"alternative-id":["10.1145\/2699435"],"URL":"https:\/\/doi.org\/10.1145\/2699435","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,6]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}