{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T20:10:55Z","timestamp":1784837455477,"version":"3.55.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2019,11,30]],"date-time":"2019-11-30T00:00:00Z","timestamp":1575072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2019,11,30]]},"abstract":"<jats:p>The current trend in modeling and analyzing real-time systems is toward tighter yet safe timing constraints. Many practical real-time systems can de facto sustain a bounded number of deadline-misses, i.e., they have Weakly-Hard Real-Time (WHRT) constraints rather than hard real-time constraints. Therefore, we strive to provide tight Deadline Miss Models (DMMs) in complement to tight response time bounds for such systems. In this work, we bound the distribution of deadline-misses for task sets running on uniprocessors using the Earliest Deadline First (EDF) scheduling policy. We assume tasks miss their deadlines due to transient overload resulting from sporadic jobs, e.g., interrupt service routines. We use Typical Worst-Case Analysis (TWCA) to tackle the problem in this context. Also, we address the sources of pessimism in computing DMMs, and we discuss the limitations of the proposed analysis. This work is motivated by and validated on a realistic case study inspired by industrial practice (satellite on-board software) and on a set of synthetic test cases. The synthetic experiment is dedicated to extensively study the impact of EDF on DMMs by presenting a comparison between DMMs computed under EDF and Rate Monotonic (RM). The results show the usefulness of this approach for temporarily overloaded systems when EDF scheduling is considered. They also show that EDF is especially useful for WHRT tasks.<\/jats:p>","DOI":"10.1145\/3356865","type":"journal-article","created":{"date-parts":[[2019,12,16]],"date-time":"2019-12-16T13:12:30Z","timestamp":1576501950000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Weakly-hard Real-time Guarantees for Earliest Deadline First Scheduling of Independent Tasks"],"prefix":"10.1145","volume":"18","author":[{"given":"Zain A. H.","family":"Hammadeh","sequence":"first","affiliation":[{"name":"TU Braunschweig, Braunschweig, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sophie","family":"Quinton","sequence":"additional","affiliation":[{"name":"INRIA Grenoble - Rh\u00f4ne-Alpes, Ismier Cedex, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolf","family":"Ernst","sequence":"additional","affiliation":[{"name":"TU Braunschweig, Braunschweig, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,12,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2004.2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2039370.2039396"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.919277"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/882482.883806"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-005-0507-9"},{"key":"e_1_2_1_6_1","volume-title":"The space of EDF deadlines: The exact region and a convex approximation. Real-Time Syst. 41, 1 (1","author":"Bini Enrico","year":"2009","unstructured":"Enrico Bini and Giorgio Buttazzo . 2009. The space of EDF deadlines: The exact region and a convex approximation. Real-Time Syst. 41, 1 (1 Jan. 2009 ), 27--51. DOI:https:\/\/doi.org\/10.1007\/s11241-008-9060-7 10.1007\/s11241-008-9060-7 Enrico Bini and Giorgio Buttazzo. 2009. The space of EDF deadlines: The exact region and a convex approximation. Real-Time Syst. 41, 1 (1 Jan. 2009), 27--51. DOI:https:\/\/doi.org\/10.1007\/s11241-008-9060-7"},{"key":"e_1_2_1_7_1","volume-title":"Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications","author":"Buttazzo Giorgio C.","unstructured":"Giorgio C. Buttazzo . 2011. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications ( 3 rd ed.). Springer Publishing Company, Inc orporated. Giorgio C. Buttazzo. 2011. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (3rd ed.). Springer Publishing Company, Incorporated.","edition":"3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2659787.2659823"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the ARTES Graduate Student Conference.","author":"Cervin Anton","year":"2001","unstructured":"Anton Cervin . 2001 . Analyzing effects of missed deadlines in control systems . In Proceedings of the ARTES Graduate Student Conference. Anton Cervin. 2001. Analyzing effects of missed deadlines in control systems. In Proceedings of the ARTES Graduate Student Conference."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2003.1253607"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SIES.2017.7993392"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the IFIP Congress. North-Holland, 807--813","author":"Dertouzos Michael L.","year":"1974","unstructured":"Michael L. Dertouzos . 1974 . Control robotics: The procedural control of physical processes . In Proceedings of the IFIP Congress. North-Holland, 807--813 . Michael L. Dertouzos. 1974. Control robotics: The procedural control of physical processes. In Proceedings of the IFIP Congress. North-Holland, 807--813."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/827272.829145"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 3rd International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS\u201912)","author":"Diemer Jonas","year":"2012","unstructured":"Jonas Diemer , Philip Axer , and Rolf Ernst . 2012 . Compositional performance analysis in Python with pyCPA . In Proceedings of the 3rd International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS\u201912) . Jonas Diemer, Philip Axer, and Rolf Ernst. 2012. Compositional performance analysis in Python with pyCPA. In Proceedings of the 3rd International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS\u201912)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIE.2015.2504339"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201914)","author":"Guan Nan","year":"2014","unstructured":"Nan Guan and Wang Yi . 2014 . General and efficient response time analysis for EDF scheduling . In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201914) . IEEE, 1--6. DOI:https:\/\/doi.org\/10.7873\/DATE.2014.268 10.7873\/DATE.2014.268 Nan Guan and Wang Yi. 2014. General and efficient response time analysis for EDF scheduling. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201914). IEEE, 1--6. DOI:https:\/\/doi.org\/10.7873\/DATE.2014.268"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.477249"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.23919\/DATE.2017.7927054"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656045.2656059"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 29th Euromicro Conference on Real-Time Systems (ECRTS\u201917)","author":"Hammadeh Zain A. H.","year":"2017","unstructured":"Zain A. H. Hammadeh , Sophie Quinton , Marco Panunzio , Rafik Henia , Laurent Rioux , and Rolf Ernst . 2017 . Budgeting under-specified tasks for weakly-hard real-time systems . In Proceedings of the 29th Euromicro Conference on Real-Time Systems (ECRTS\u201917) . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17:1--17:22. Retrieved from: http:\/\/drops.dagstuhl.de\/opus\/frontdoor.php?source_opus&equals;7163. Zain A. H. Hammadeh, Sophie Quinton, Marco Panunzio, Rafik Henia, Laurent Rioux, and Rolf Ernst. 2017. Budgeting under-specified tasks for weakly-hard real-time systems. In Proceedings of the 29th Euromicro Conference on Real-Time Systems (ECRTS\u201917). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 17:1--17:22. Retrieved from: http:\/\/drops.dagstuhl.de\/opus\/frontdoor.php?source_opus&equals;7163."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1049\/ip-cdt:20045088"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800210113"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2012.67"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(82)90024-4"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the IEEE International Workshop on Factory Communication Systems. IEEE, 23--30","author":"Li Jian","year":"2004","unstructured":"Jian Li , YeQiong Song , and F. Simonot-Lion . 2004. Schedulability analysis for systems under (m,k)-firm constraints . In Proceedings of the IEEE International Workshop on Factory Communication Systems. IEEE, 23--30 . DOI:https:\/\/doi.org\/10.1109\/WFCS. 2004 .1377670 10.1109\/WFCS.2004.1377670 Jian Li, YeQiong Song, and F. Simonot-Lion. 2004. Schedulability analysis for systems under (m,k)-firm constraints. In Proceedings of the IEEE International Workshop on Factory Communication Systems. IEEE, 23--30. DOI:https:\/\/doi.org\/10.1109\/WFCS.2004.1377670"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11572329_14"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-008-9053-6"},{"key":"e_1_2_1_31_1","volume-title":"Silva","author":"Magalh\u00e3es Ant\u00f3nio P.","year":"1993","unstructured":"Ant\u00f3nio P. Magalh\u00e3es , M\u00e1rio Z. Rela , and Jo\u00e3o G . Silva . 1993 . Deadlines in Real-Time Systems. Technical Report.Universidade do Porto, Portugal. Retrieved from: https:\/\/web.fe.up.pt\/ apmag\/Suportehome\/Ficheiros\/drts.pdf. Ant\u00f3nio P. Magalh\u00e3es, M\u00e1rio Z. Rela, and Jo\u00e3o G. Silva. 1993. Deadlines in Real-Time Systems. Technical Report.Universidade do Porto, Portugal. Retrieved from: https:\/\/web.fe.up.pt\/ apmag\/Suportehome\/Ficheiros\/drts.pdf."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.9.2.244"},{"key":"e_1_2_1_33_1","unstructured":"Marco Di Natale. 2017. Beyond the m-k model: Restoring performance considerations in the time abstraction. ESWEEK - Tutorial Slides. Retrieved from https:\/\/team.inria.fr\/spades\/files\/2017\/10\/EMSOFT2017_MDN-1.pdf.  Marco Di Natale. 2017. Beyond the m-k model: Restoring performance considerations in the time abstraction. ESWEEK - Tutorial Slides. Retrieved from https:\/\/team.inria.fr\/spades\/files\/2017\/10\/EMSOFT2017_MDN-1.pdf."},{"key":"e_1_2_1_34_1","volume-title":"Giorgio Buttazzo, and Matteo Secchiari.","author":"Pazzaglia Paolo","year":"2018","unstructured":"Paolo Pazzaglia , Marco Di Natale , Giorgio Buttazzo, and Matteo Secchiari. 2018 . A framework for the co-simulation of engine controls and task scheduling. In Software Engineering and Formal Methods, Antonio Cerone and Marco Roveri (Eds.). Springer International Publishing , Cham, 438--452. Paolo Pazzaglia, Marco Di Natale, Giorgio Buttazzo, and Matteo Secchiari. 2018. A framework for the co-simulation of engine controls and task scheduling. In Software Engineering and Formal Methods, Antonio Cerone and Marco Roveri (Eds.). Springer International Publishing, Cham, 438--452."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1890629.1890640"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/2492708.2492836"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.774906"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2717113"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/TAC.1985.1103952","article-title":"A unified method for evaluating real-time computer controllers and its application","volume":"30","author":"Shin Kang","year":"1985","unstructured":"Kang Shin , C. Krishna , and Yann-Hang Lee . 1985 . A unified method for evaluating real-time computer controllers and its application . IEEE Trans. Automat. Control 30 , 4 (Apr. 1985), 357--366. DOI:https:\/\/doi.org\/10.1109\/TAC.1985.1103952 10.1109\/TAC.1985.1103952 Kang Shin, C. Krishna, and Yann-Hang Lee. 1985. A unified method for evaluating real-time computer controllers and its application. IEEE Trans. Automat. Control 30, 4 (Apr. 1985), 357--366. DOI:https:\/\/doi.org\/10.1109\/TAC.1985.1103952","journal-title":"IEEE Trans. Automat. Control"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2015.20"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126497"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201916)","author":"von der Br\u00fcggen Georg","year":"2016","unstructured":"Georg von der Br\u00fcggen , K. H. Chen , W. H. Huang , and J. J. Chen . 2016. Systems with dynamic real-time guarantees in uncertain and faulty execution environments . In Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201916) . IEEE, 303--314. DOI:https:\/\/doi.org\/10.1109\/RTSS. 2016 .037 10.1109\/RTSS.2016.037 Georg von der Br\u00fcggen, K. H. Chen, W. H. Huang, and J. J. Chen. 2016. Systems with dynamic real-time guarantees in uncertain and faulty execution environments. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS\u201916). IEEE, 303--314. DOI:https:\/\/doi.org\/10.1109\/RTSS.2016.037"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2015.29"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1109\/TC.2009.58","article-title":"Schedulability analysis for real-time systems with EDF scheduling","volume":"58","author":"Zhang Fengxiang","year":"2009","unstructured":"Fengxiang Zhang and Alan Burns . 2009 . Schedulability analysis for real-time systems with EDF scheduling . IEEE Trans. Comput. 58 , 9 (Sept. 2009), 1250--1258. DOI:https:\/\/doi.org\/10.1109\/TC.2009.58 10.1109\/TC.2009.58 Fengxiang Zhang and Alan Burns. 2009. Schedulability analysis for real-time systems with EDF scheduling. IEEE Trans. Comput. 58, 9 (Sept. 2009), 1250--1258. DOI:https:\/\/doi.org\/10.1109\/TC.2009.58","journal-title":"IEEE Trans. Comput."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356865","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3356865","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:22:55Z","timestamp":1750202575000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356865"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,30]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,11,30]]}},"alternative-id":["10.1145\/3356865"],"URL":"https:\/\/doi.org\/10.1145\/3356865","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,30]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}