{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:16:51Z","timestamp":1763468211901,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2014,10,6]],"date-time":"2014-10-06T00:00:00Z","timestamp":1412553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Carnegie Mellon University. DM-0000627"},{"name":"Department of Defense under contract no. FA8721-05-C-0003 with Carnegie Mellon University for the operation of the Software Engineering Institute"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2014,12,15]]},"abstract":"<jats:p>Traditional hard real-time scheduling algorithms require the use of the worst-case execution times to guarantee that deadlines will be met. Unfortunately, many algorithms with parameters derived from sensing the physical world suffer large variations in execution time, leading to pessimistic overall utilization, such as visual recognition tasks. In this article, we present ZS-QRAM, a scheduling approach that enables the use of flexible execution times and application-derived utility to tasks in order to maximize total system utility. In particular, we provide a detailed description of the algorithm, the formal proofs for its temporal protection, and a detailed, evaluation. Our evaluation uses the Utility Degradation Resilience (UDR) showing that ZS-QRAM is able to obtain 4\u00d7 as much UDR as ZSRM, a previous overbooking approach, and almost 2\u00d7 as much UDR as Rate-Monotonic with Period Transformation (RM\/TP). We then evaluate a Linux kernel module implementation of our scheduler on an Unmanned Air Vehicle (UAV) platform. We show that, by using our approach, we are able to keep the tasks that render the most utility by degrading lower-utility ones even in the presence of highly dynamic execution times.<\/jats:p>","DOI":"10.1145\/2660497","type":"journal-article","created":{"date-parts":[[2014,10,7]],"date-time":"2014-10-07T12:57:47Z","timestamp":1412686667000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Utility-Based Resource Overbooking for Cyber-Physical Systems"],"prefix":"10.1145","volume":"13","author":[{"given":"Dionisio","family":"De Niz","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lutz","family":"Wrage","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anthony","family":"Rowe","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ragunathan (Raj)","family":"Rajkumar","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,10,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2010.10"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2008.26"},{"volume-title":"Proceedings of the IEEE 19th Real-Time Systems Symposium (RTSS'98)","author":"Buttazzo G.","key":"e_1_2_1_3_1","unstructured":"G. Buttazzo , G. Lipari , and L. Abeni . 1998. Elastic task model for adaptive rate control . In Proceedings of the IEEE 19th Real-Time Systems Symposium (RTSS'98) . 286. G. Buttazzo, G. Lipari, and L. Abeni. 1998. Elastic task model for adaptive rate control. In Proceedings of the IEEE 19th Real-Time Systems Symposium (RTSS'98). 286."},{"volume-title":"Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS'95)","author":"Buttazzo G.","key":"e_1_2_1_4_1","unstructured":"G. Buttazzo , M. Spuri , and F. Sensini . 1995. Value vs deadline scheduling in overload conditions . In Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS'95) . 90. G. Buttazzo, M. Spuri, and F. Sensini. 1995. Value vs deadline scheduling in overload conditions. In Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS'95). 90."},{"key":"e_1_2_1_5_1","article-title":"Efficient real-time scheduling algorithms for multiprocessor systems. IEICE","author":"Cho S.","year":"2002","unstructured":"S. Cho , S.-K. Lee , A. Han , and K.-J. Lin . 2002 . Efficient real-time scheduling algorithms for multiprocessor systems. IEICE Trans. Comm. E85-B, 2859--2867. S. Cho, S.-K. Lee, A. Han, and K.-J. Lin. 2002. Efficient real-time scheduling algorithms for multiprocessor systems. IEICE Trans. Comm. E85-B, 2859--2867.","journal-title":"Trans. Comm. E85-B, 2859--2867."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2007.14"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.46"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCPS.2012.18"},{"key":"e_1_2_1_9_1","unstructured":"DRONE-RK. 2013. Drone-rk. http:\/\/www.drone-rk.org\/.  DRONE-RK. 2013. Drone-rk. http:\/\/www.drone-rk.org\/."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2012.16"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/29.5.390"},{"key":"e_1_2_1_12_1","unstructured":"S. Kato R. Rajkumar and Y. Ishikawa. 2009. A loadable real-time scheduler suite for multicore platforms. http:\/\/ertl.jp\/~shinpei\/papers\/techrep09.pdf.  S. Kato R. Rajkumar and Y. Ishikawa. 2009. A loadable real-time scheduler suite for multicore platforms. http:\/\/ertl.jp\/~shinpei\/papers\/techrep09.pdf."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2010.91"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1890629.1890665"},{"volume-title":"Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium (RTAS'99)","author":"Oikawa S.","key":"e_1_2_1_16_1","unstructured":"S. Oikawa and R. Rajkumar . 1999. Portable rk: A portable resource kernel for guaranteed and enforced timing behavior . In Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium (RTAS'99) . 111. S. Oikawa and R. Rajkumar. 1999. Portable rk: A portable resource kernel for guaranteed and enforced timing behavior. In Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium (RTAS'99). 111."},{"key":"e_1_2_1_17_1","unstructured":"Parrot. 2011. Parrot ar drone. http:\/\/ardrone.parrot.com\/.  Parrot. 2011. Parrot ar drone. http:\/\/ardrone.parrot.com\/."},{"volume-title":"Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS'97)","author":"Rajkumar R.","key":"e_1_2_1_18_1","unstructured":"R. Rajkumar , C. Lee , J. Lehoczky , and D. Siewiorek . 1997. A resource allocation model for qos management . In Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS'97) . 298. R. Rajkumar, C. Lee, J. Lehoczky, and D. Siewiorek. 1997. A resource allocation model for qos management. In Proceedings of the 18th IEEE Real-Time Systems Symposium (RTSS'97). 298."},{"volume-title":"Proceedings of the 10th IEEE Real-Time Technology and Applications Symposium (RTAS'04)","author":"Shih C.-S.","key":"e_1_2_1_19_1","unstructured":"C.-S. Shih , P. Ganti , and L. Sha . 2004. Schedulability and fairness for computation tasks in surveillance radar systems . In Proceedings of the 10th IEEE Real-Time Technology and Applications Symposium (RTAS'04) . C.-S. Shih, P. Ganti, and L. Sha. 2004. Schedulability and fairness for computation tasks in surveillance radar systems. In Proceedings of the 10th IEEE Real-Time Technology and Applications Symposium (RTAS'04)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.35"},{"key":"e_1_2_1_21_1","unstructured":"ZS-QRAM. 2013. ZS-QRAM documentation. http:\/\/andrew.cmu.edu\/dionisio\/projects.html.  ZS-QRAM. 2013. ZS-QRAM documentation. http:\/\/andrew.cmu.edu\/dionisio\/projects.html."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660497","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2660497","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:11:54Z","timestamp":1750227114000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2660497"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10,6]]},"references-count":21,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2014,12,15]]}},"alternative-id":["10.1145\/2660497"],"URL":"https:\/\/doi.org\/10.1145\/2660497","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2014,10,6]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-10-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}