{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T13:25:04Z","timestamp":1758893104771,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,12]],"date-time":"2020-07-12T00:00:00Z","timestamp":1594512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARTEMIS joint undertaking under the ALMARVI project","award":["621439"],"award-info":[{"award-number":["621439"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>\n            (\n            <jats:italic>m<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-firm real-time tasks require meeting the deadline of at least\n            <jats:italic>m<\/jats:italic>\n            jobs out of any\n            <jats:italic>k<\/jats:italic>\n            consecutive jobs. When compared to hard real-time tasks, (\n            <jats:italic>m<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )$-firm tasks open up the possibility of tighter resource-dimensioning in implementations. Firmness analysis verifies the satisfaction of (\n            <jats:italic>m<\/jats:italic>\n            ,\n            <jats:italic>k<\/jats:italic>\n            )-firmness conditions. Scheduling policies under which a set of periodic tasks runs on a resource influence the number of deadline missed jobs. Therefore, the nature of the firmness analysis problem depends on scheduling policies. In this work, we present Firmness Analysis (FAn) methods for three common scheduling policies\u2014synchronous and asynchronous Static Priority Preemptive (SPP) policies and Time Division Multiple Access (TDMA). We first introduce the Balloon and Rake problem\u2014the problem of striking the maximum number of balloons in a balloon line with a rake. We show that the common core of firmness analysis problems can be abstracted as the Balloon and Rake problem. Next, we prove that the Finite Point method is a solution to the Balloon and Rake problem. We illustrate how existing FAn methods for the TDMA and asynchronous SPP policies can be adapted to use the same solution framework for the Balloon and Rake problem. Using the solution of the Balloon and Rake problem, we adapt the existing FAn methods to synchronous SPP scheduling policies. The scalability of the FAn methods is compared with that of a timed-automata approach, a brute-force approach, and a Mixed Integer Linear Programing method. The FAn methods scale substantially better to firmness analysis problem instances with a large\n            <jats:italic>k<\/jats:italic>\n            and a high number of tasks.\n          <\/jats:p>","DOI":"10.1145\/3398328","type":"journal-article","created":{"date-parts":[[2020,7,7]],"date-time":"2020-07-07T12:39:02Z","timestamp":1594125542000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Firmness Analysis of Real-time Tasks"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8600-4536","authenticated-orcid":false,"given":"Amir","family":"Behrouzian","sequence":"first","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4662-4209","authenticated-orcid":false,"given":"Hadi Alizadeh","family":"Ara","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2629-3249","authenticated-orcid":false,"given":"Marc","family":"Geilen","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dip","family":"Goswami","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Twan","family":"Basten","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology 8 ESI, TNO, Eindhoven, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2015.7108439"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90010-8"},{"volume-title":"Proceedings of the International Symposium on On-Line Testing and Robust System Design (IOLTS\u201918)","author":"Behrouzian A. R. B.","key":"e_1_2_1_3_1"},{"volume-title":"Proceedings of the Real-Time and Embedded Technology and Applcations Symposium (RTAS\u201918)","author":"Behrouzian A. R. B.","key":"e_1_2_1_4_1"},{"volume-title":"Proceedings of the International Symposium on Industrial Embedded Systems (SIES\u201916)","author":"Behrouzian A. R. B.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","unstructured":"G. Bernat. 1998. Specification and Analysis of Weakly Hard Real-time Systems. Universitat de les Illes Balears Spain.  G. Bernat. 1998. Specification and Analysis of Weakly Hard Real-time Systems. Universitat de les Illes Balears Spain."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.919277"},{"volume-title":"Proceedings of the 23rd International Conference on Real Time and Networks Systems.","author":"Bund T.","key":"e_1_2_1_8_1"},{"volume-title":"Hard Real-time Computing Systems: Predictable Scheduling Algorithms and Applications","author":"Buttazzo G.","key":"e_1_2_1_9_1"},{"volume-title":"Proceedings of the International Conference on Concurrency Theory. Springer.","author":"Cassez F.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS\u201908)","author":"Coutinho M.","key":"e_1_2_1_11_1"},{"volume-title":"IFAC Proceedings.","author":"Ben Ga\u00c3\u0155d M. E. M.","key":"e_1_2_1_12_1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2014.2301795"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.477249"},{"volume-title":"Proceedings of the International Conference on Embedded Software (EMSOFT\u201914)","author":"Hammadeh Z. A. H.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the Software Engineering Conference (MySEC\u201915)","author":"Ismail H.","key":"e_1_2_1_16_1"},{"volume-title":"Proceedings of the International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT\u201911)","author":"Kong Y.","key":"e_1_2_1_17_1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-5316(82)90024-4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"volume-title":"Proceedings of the International Conference on Fieldbus Systems and Their Applications.","author":"Ning J.","key":"e_1_2_1_20_1"},{"volume-title":"Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS\u201918)","author":"Pazzaglia P.","key":"e_1_2_1_21_1"},{"volume-title":"Proceedings of the 51st Annual Conference on Design Automation. ACM.","author":"Quinton S.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3126497"},{"volume-title":"Proceedings of the International Symposium on Industrial Embedded Systems (SIES\u201916)","author":"Tobuschat S.","key":"e_1_2_1_24_1"},{"volume-title":"Proceedings of the European Control Conference (ECC\u201916)","author":"van Horssen E.","key":"e_1_2_1_25_1"},{"volume-title":"Proceedings of the 27th Euromicro Conference on Real-Time Systems (ECRTS\u201915)","author":"Xu W.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2017.2679195"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3398328","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3398328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:53Z","timestamp":1750199933000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3398328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,12]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3398328"],"URL":"https:\/\/doi.org\/10.1145\/3398328","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2020,7,12]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}