{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T19:59:21Z","timestamp":1762459161657,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,3,10]],"date-time":"2014-03-10T00:00:00Z","timestamp":1394409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006710","name":"Wayne State University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006710","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2014,12,5]]},"abstract":"<jats:p>Recent research in compositional real-time systems has focused on determination of a component's real-time interface parameters. An important objective in interface-parameter determination is minimizing the bandwidth allocated to each component of the system while simultaneously guaranteeing component schedulability. With this goal in mind, in this article, we explore fixed-priority schedulability in compositional setting. First we derive an efficient exact test based on iterative convergence for sporadic task systems scheduled by fixed-priority (e.g., deadline monotonic, rate monotonic) upon an explicit-deadline periodic (EDP) resource. Then we address the time complexity of the exact test by developing a fully-polynomial-time approximation scheme (FPTAS) for allocating bandwidth to components. Our parametric algorithm takes the task system and an accuracy parameter \u03b5 &gt; 0 as input and returns a bandwidth which is guaranteed to be at most a factor (1 + \u03b5) times the optimal minimum bandwidth required to successfully schedule the task system. We perform thorough simulation over synthetically generated task systems to compare the performance of our proposed efficient-exact and the approximate algorithm and observe a significant decrease in runtime and a very small relative error when comparing the approximate algorithm with the exact algorithm and the sufficient algorithm.<\/jats:p>","DOI":"10.1145\/2560038","type":"journal-article","created":{"date-parts":[[2014,3,18]],"date-time":"2014-03-18T12:09:07Z","timestamp":1395144547000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Bandwidth allocation for fixed-priority-scheduled compositional real-time systems"],"prefix":"10.1145","volume":"13","author":[{"given":"Farhana","family":"Dewan","sequence":"first","affiliation":[{"name":"Wayne State University, Detroit, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Fisher","sequence":"additional","affiliation":[{"name":"Wayne State University, Detroit, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,3,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.suscom.2011.05.006"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2008.19"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017753.1017772"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1049\/sej.1993.0034"},{"volume-title":"Proceedings of the 8th IEEE Workshop on Real-Time Operating Systems and Software. 127--132","author":"Audsley N. C.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90360-6"},{"volume-title":"Proceedings of the IEEE Real-Time Systems Symposium. 68--78","author":"Bernat G.","key":"e_1_2_1_7_1"},{"volume-title":"Proceedings of the 15th International Conference on Real-Time Systems. 95--104","year":"2007","author":"Bini Enrico","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009383.1009838"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.66"},{"volume-title":"Proceedings of the 18th IEEE Real-Time Systems Symposium. IEEE Computer Society, 308--319","author":"Deng Z.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2010.28"},{"volume-title":"Bandwidth allocation for fixed-priority-scheduled compositional real-time systems (extended version). Tech. rep","author":"Dewan Farhana","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2012.54"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.17"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2009.46"},{"volume-title":"Proceedings of the IEEE Real-Time Systems Symposium. IEEE Computer Society, 26--35","year":"2002","author":"Feng Xiang","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the 17th International Conference on Real-Time and Network Systems.","year":"2009","author":"Fisher Nathan","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2005.1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-011-9144-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2012.17"},{"volume-title":"Proceedings of the Real-Time Systems Symposium. IEEE Computer Society, 166--171","author":"Lehoczky J.","key":"e_1_2_1_23_1"},{"volume-title":"Proceedings of the Real-Time Systems Symposium. IEEE, 261--270","author":"Lehoczky J.","key":"e_1_2_1_24_1"},{"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","doi-asserted-by":"publisher","DOI":"10.1109\/EMRTS.2003.1212738"},{"volume-title":"Proceedings of the 5th IEEE Workshop on Real-Time Software and Operating Systems. 42--46","year":"1988","author":"Mok A.","key":"e_1_2_1_27_1"},{"volume-title":"Proceedings of the IEEE Conference on Emerging Technologies and Factory Automation (ETFA). 1--4.","author":"Okwudire C.","key":"e_1_2_1_29_1"},{"volume-title":"Readings in Multimedia Computing and Networking","author":"Rajkumar Raj","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2008.28"},{"volume-title":"Proceedings of the IEEE Real-Time Systems Symposium. IEEE Computer Society, 2--13","year":"2003","author":"Shin Insik","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.15"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347383"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/827270.829035"},{"volume-title":"Proceedings of the Real-Time Systems Symposium. 251--258","author":"Sprunt B.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02341920"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.368008"},{"key":"e_1_2_1_39_1","unstructured":"Martijn M. M. H. P. van den Heuvel Pieter J. L. Cuijpers Johan J. Lukkien and Nathan Fisher. 2012. Revised budget allocations for fixed-priority-scheduled periodic resources. CS-report 12-03 Technische Universiteit Eindhoven (TU\/e).  Martijn M. M. H. P. van den Heuvel Pieter J. L. Cuijpers Johan J. Lukkien and Nathan Fisher. 2012. Revised budget allocations for fixed-priority-scheduled periodic resources. CS-report 12-03 Technische Universiteit Eindhoven (TU\/e)."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2560038","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2560038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:10:21Z","timestamp":1750234221000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2560038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,10]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12,5]]}},"alternative-id":["10.1145\/2560038"],"URL":"https:\/\/doi.org\/10.1145\/2560038","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2014,3,10]]},"assertion":[{"value":"2012-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-03-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}