{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T16:30:32Z","timestamp":1774801832819,"version":"3.50.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"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":[[2013,8]]},"abstract":"<jats:p>Schedulability analysis of hierarchical real-time embedded systems involves defining interfaces that represent the underlying system faithfully and then compositionally analyzing those interfaces. Whereas commonly used abstractions, such as periodic and sporadic tasks and their interfaces, are simple and well studied, results for more complex and expressive abstractions and interfaces based on task graphs and automata are limited. One contributory factor may be the hardness of compositional schedulability analysis with task graphs and automata. Recently, conditional task models, such as the recurring branching task model, have been introduced with the goal of reaching a middle ground in the trade-off between expressivity and ease of analysis. Consequently, techniques for compositional analysis with conditional models have also been proposed, and each offer different advantages. In this work, we revisit those techniques, compare their advantages using an automotive case study, and identify limitations that would need to be addressed before adopting these techniques for use with real-world problems.<\/jats:p>","DOI":"10.1145\/2501626.2501629","type":"journal-article","created":{"date-parts":[[2013,9,11]],"date-time":"2013-09-11T06:54:48Z","timestamp":1378882488000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A comparison of compositional schedulability analysis techniques for hierarchical real-time systems"],"prefix":"10.1145","volume":"13","author":[{"given":"Madhukar","family":"Anand","sequence":"first","affiliation":[{"name":"Cisco Systems, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Fischmeister","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Insup","family":"Lee","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,9,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1017753.1017772"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISORC.2008.47"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/EMWRTS.1998.685078"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/827270.829061"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01995675"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2006.22"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE'03)","author":"Chakraborty S.","unstructured":"Chakraborty , S. , Kunzli , S. , and Thiele , L . 2003. A general framework for analysing system properties in platform-based embedded system designs . In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'03) . IEEE Computer Society, Washington, DC. Chakraborty, S., Kunzli, S., and Thiele, L. 2003. A general framework for analysing system properties in platform-based embedded system designs. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'03). IEEE Computer Society, Washington, DC."},{"key":"e_1_2_1_9_1","unstructured":"Company F. M. 1988. ETX-I final report vol 1. Tech. rep. Ford.  Company F. M. 1988. ETX-I final report vol 1. Tech. rep. Ford."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2005.25"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.17"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium (RTSS). IEEE Computer Society","author":"Feng X. A.","unstructured":"Feng , X. A. and Mok , A. K . 2002. A model of hierarchical real-time virtual resources . In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). IEEE Computer Society , Los Alamitos, CA. Feng, X. A. and Mok, A. K. 2002. A model of hierarchical real-time virtual resources. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS). IEEE Computer Society, Los Alamitos, CA."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176887.1176907"},{"key":"e_1_2_1_14_1","volume-title":"Master's thesis","author":"Iercan D.","unstructured":"Iercan , D. 2005. Master's thesis , Politehnica University of Timisoara . Iercan, D. 2005. Master's thesis, Politehnica University of Timisoara."},{"key":"e_1_2_1_15_1","volume-title":"A solution to an automotive control system benchmark. Tech. rep. Research report 4\/1994","author":"Kopetz H.","unstructured":"Kopetz , H. 1994. A solution to an automotive control system benchmark. Tech. rep. Research report 4\/1994 , Institut fur Technische Informatik, TU Wien . Kopetz, H. 1994. A solution to an automotive control system benchmark. Tech. rep. Research report 4\/1994, Institut fur Technische Informatik, TU Wien."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium. 166--171","author":"Lehoczky J.","unstructured":"Lehoczky , J. , Sha , L. , and Ding , Y . 1989. The rate monotonic scheduling algorithm: exact characterization and average case behavior . In Proceedings of the IEEE Real-Time Systems Symposium. 166--171 . Lehoczky, J., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm: exact characterization and average case behavior. In Proceedings of the IEEE Real-Time Systems Symposium. 166--171."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 15th Euromicro Conference on Real-Time Systems (ECRTS). 151--158","author":"Lipari G.","unstructured":"Lipari , G. and Bini , E . 2003. Resource partitioning among real-time applications . In Proceedings of the 15th Euromicro Conference on Real-Time Systems (ECRTS). 151--158 . Lipari, G. and Bini, E. 2003. Resource partitioning among real-time applications. In Proceedings of the 15th Euromicro Conference on Real-Time Systems (ECRTS). 151--158."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2005.43"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775913"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008177218257"},{"key":"e_1_2_1_22_1","volume-title":"SAE Handbook 1994 Ed","unstructured":"SAE. 1994. SAE Handbook 1994 Ed . Society of Automotive Engineers (SAE) . SAE. 1994. SAE Handbook 1994 Ed. Society of Automotive Engineers (SAE)."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Euromicro Conference on Real-Time Systems.","author":"Saewong S.","unstructured":"Saewong , S. , Rajkumar , R. , Lehoczky , J. , and Klein , M . 2002. Analysis of hierarchical fixed-priority scheduling . In Proceedings of the Euromicro Conference on Real-Time Systems. Saewong, S., Rajkumar, R., Lehoczky, J., and Klein, M. 2002. Analysis of hierarchical fixed-priority scheduling. In Proceedings of the Euromicro Conference on Real-Time Systems."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the IEEE Real-Time Systems Symposium. 2--13","author":"Shin I.","unstructured":"Shin , I. and Lee , I . 2003. Periodic resource model for compositional real-time guarantees . In Proceedings of the IEEE Real-Time Systems Symposium. 2--13 . Shin, I. and Lee, I. 2003. Periodic resource model for compositional real-time guarantees. In Proceedings of the IEEE Real-Time Systems Symposium. 2--13."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2004.15"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the International Symposium on Circuits and Systems (ISCAS). 101--104","author":"Thiele L.","unstructured":"Thiele , L. , Chakraborty , S. , and Naedele , M . 2000. Real-time calculus for scheduling hard real-time systems . In Proceedings of the International Symposium on Circuits and Systems (ISCAS). 101--104 . Thiele, L., Chakraborty, S., and Naedele, M. 2000. Real-time calculus for scheduling hard real-time systems. In Proceedings of the International Symposium on Circuits and Systems (ISCAS). 101--104."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176887.1176894"},{"key":"e_1_2_1_28_1","unstructured":"Tindell K. and Burns A. 1997. Guaranteed message latencies for distributed safety critical hard real-time networks. Tech. rep. YCS 94-229 Department of Computer Science University of York York U.K.  Tindell K. and Burns A. 1997. Guaranteed message latencies for distributed safety critical hard real-time networks. Tech. rep. YCS 94-229 Department of Computer Science University of York York U.K."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2501626.2501629","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2501626.2501629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:48Z","timestamp":1750231728000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2501626.2501629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1145\/2501626.2501629"],"URL":"https:\/\/doi.org\/10.1145\/2501626.2501629","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-09-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}