{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T15:49:36Z","timestamp":1781797776937,"version":"3.54.5"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,5,22]],"date-time":"2018-05-22T00:00:00Z","timestamp":1526947200000},"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":[[2018,5,31]]},"abstract":"<jats:p>\n            Consider fixed-priority preemptive partitioned scheduling of constrained-deadline sporadic tasks on a multiprocessor. A task generates a sequence of jobs and each job has a deadline that must be met. Assume tasks have Corunner-dependent execution times; i.e., the execution time of a job\n            <jats:italic>J<\/jats:italic>\n            depends on the set of jobs that happen to execute (on other processors) at instants when\n            <jats:italic>J<\/jats:italic>\n            executes. We present a model that describes Corunner-dependent execution times. For this model, we show that exact schedulability testing is co-NP-hard in the strong sense. Facing this complexity, we present a sufficient schedulability test, which has pseudo-polynomial-time complexity if the number of processors is fixed. We ran experiments with synthetic software benchmarks on a quad-core Intel multicore processor with the Linux\/RK operating system and found that for each task, its maximum measured response time was bounded by the upper bound computed by our theory.\n          <\/jats:p>","DOI":"10.1145\/3203407","type":"journal-article","created":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T15:08:42Z","timestamp":1527088122000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Schedulability Analysis of Tasks with Corunner-Dependent Execution Times"],"prefix":"10.1145","volume":"17","author":[{"given":"BJ\u00f6rn","family":"Andersson","sequence":"first","affiliation":[{"name":"Carnegie Mellon University and UC Riverside, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8553-732X","authenticated-orcid":false,"given":"Hyoseung","family":"Kim","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University and UC Riverside, Riverside, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dionisio De","family":"Niz","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University and UC Riverside, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Klein","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University and UC Riverside, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ragunathan (Raj)","family":"Rajkumar","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University and UC Riverside, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Lehoczky","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University and UC Riverside, Pittsburgh, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,5,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1851166.1851172"},{"key":"e_1_2_1_2_1","volume-title":"International Parallel and Distributed Processing Symposium (IPDPS\u201902)","author":"Andersson B.","unstructured":"B. Andersson and J. Jonsson . 2002. Preemptive multiprocessor scheduling anomalies . In International Parallel and Distributed Processing Symposium (IPDPS\u201902) . B. Andersson and J. Jonsson. 2002. Preemptive multiprocessor scheduling anomalies. In International Parallel and Distributed Processing Symposium (IPDPS\u201902)."},{"key":"e_1_2_1_3_1","unstructured":"B. Andersson H. Kim D. de Niz M. Klein R. Rajkumar and J. Lehoczky. 2016. Schedulability Analysis of Tasks with Co-Runner-Dependent Execution Times. Technical Report. Carnegie Mellon University. Retrieved from http:\/\/www.andrew.cmu.edu\/user\/banderss\/papers\/schedanalysiscorunner\/co-runners_long_version.pdf.  B. Andersson H. Kim D. de Niz M. Klein R. Rajkumar and J. Lehoczky. 2016. Schedulability Analysis of Tasks with Co-Runner-Dependent Execution Times. Technical Report. Carnegie Mellon University. Retrieved from http:\/\/www.andrew.cmu.edu\/user\/banderss\/papers\/schedanalysiscorunner\/co-runners_long_version.pdf."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2006.47"},{"key":"e_1_2_1_5_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380356.2380372"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/29.5.390"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2006.31"},{"key":"e_1_2_1_11_1","volume-title":"IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS\u201914)","author":"Kim H.","unstructured":"H. Kim , D. de Niz , B. Andersson , M. Klein , O. Mutlu , and R. Rajkumar . 2014. Bounding memory interference delay in COTS-based multi-core systems . In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS\u201914) . H. Kim, D. de Niz, B. Andersson, M. Klein, O. Mutlu, and R. Rajkumar. 2014. Bounding memory interference delay in COTS-based multi-core systems. In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS\u201914)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2013.19"},{"key":"e_1_2_1_13_1","volume-title":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201904)","author":"Kr\u010d\u00e1l P.","unstructured":"P. Kr\u010d\u00e1l and W. Yi . 2004. Decidable and undecidable problems in schedulability analysis using timed automata . In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201904) . P. Kr\u010d\u00e1l and W. Yi. 2004. Decidable and undecidable problems in schedulability analysis using timed automata. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS\u201904)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629335.1629351"},{"key":"e_1_2_1_15_1","volume-title":"IEEE Real-Time Systems Symposium (RTSS\u201990)","author":"Lehoczky J.","unstructured":"J. Lehoczky , L. Sha , and Y. Ding . 1990. The rate monotonic scheduling algorithm: Exact characterization and average case behavior . In IEEE Real-Time Systems Symposium (RTSS\u201990) . J. Lehoczky, L. Sha, and Y. Ding. 1990. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In IEEE Real-Time Systems Symposium (RTSS\u201990)."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2009.32"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/321738.321743"},{"key":"e_1_2_1_18_1","volume-title":"International Conference on Distributed Computing Systems (ICDCS\u201994)","author":"Liu J.","unstructured":"J. Liu and R. Ha . 1994. Efficient methods of validating timing constraints . In International Conference on Distributed Computing Systems (ICDCS\u201994) . J. Liu and R. Ha. 1994. Efficient methods of validating timing constraints. In International Conference on Distributed Computing Systems (ICDCS\u201994)."},{"key":"e_1_2_1_19_1","volume-title":"IEEE Real-Time Systems Symposium (RTSS\u201999)","author":"Lundqvist T.","unstructured":"T. Lundqvist and P. Stenstr\u00f6m . 1999. Timing anomalies in dynamically scheduled microprocessors . In IEEE Real-Time Systems Symposium (RTSS\u201999) . T. Lundqvist and P. Stenstr\u00f6m. 1999. Timing anomalies in dynamically scheduled microprocessors. In IEEE Real-Time Systems Symposium (RTSS\u201999)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2010.30"},{"key":"e_1_2_1_22_1","volume-title":"IEEE International Conference on Embedded and Real-Time Computing and Applications (RTCSA\u201999)","author":"Norstr\u00f6m C.","unstructured":"C. Norstr\u00f6m , A. Wall , and W. Yi . 1999. Timed automata as task models for event-driven systems . In IEEE International Conference on Embedded and Real-Time Computing and Applications (RTCSA\u201999) . C. Norstr\u00f6m, A. Wall, and W. Yi. 1999. Timed automata as task models for event-driven systems. In IEEE International Conference on Embedded and Real-Time Computing and Applications (RTCSA\u201999)."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2014.20"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"R. Pellizzoni A. Schranzhofer J. J. Chen M. Caccamo and L. Thiele. 2010. Worst case delay analysis for memory interference in multicore systems. In Design Automation and Test in Europe (DATE\u201910).   R. Pellizzoni A. Schranzhofer J. J. Chen M. Caccamo and L. Thiele. 2010. Worst case delay analysis for memory interference in multicore systems. In Design Automation and Test in Europe (DATE\u201910).","DOI":"10.1109\/DATE.2010.5456952"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS.2007.16"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2086696.2086713"},{"key":"e_1_2_1_27_1","volume-title":"International Workshop on Worst-Case Execution Time Analysis (WCET\u201906)","author":"Reineke J.","unstructured":"J. Reineke , B. Wachter , S. Thesing , R. Wilhelm , I. Polian , J. Eisinger , and B. Becker . 2006. A definition and classification of timing anomalies . In International Workshop on Worst-Case Execution Time Analysis (WCET\u201906) . J. Reineke, B. Wachter, S. Thesing, R. Wilhelm, I. Polian, J. Eisinger, and B. Becker. 2006. A definition and classification of timing anomalies. In International Workshop on Worst-Case Execution Time Analysis (WCET\u201906)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629435.1629494"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"S. Schliecker M. Negrean and R. Ernst. 2010. Bounding the shared resource load for the performance analysis of multiprocessor systems. In DATE\u201910.   S. Schliecker M. Negrean and R. Ernst. 2010. Bounding the shared resource load for the performance analysis of multiprocessor systems. In DATE\u201910.","DOI":"10.1109\/DATE.2010.5456951"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2016.271"},{"key":"e_1_2_1_31_1","volume-title":"Design Automation Conference (DAC\u201914)","author":"Shah H.","unstructured":"H. Shah , K. Huang , and A. Knoll . 2014. Timing anomalies in multi-core architectures due to the interference on the shared resources . In Design Automation Conference (DAC\u201914) . H. Shah, K. Huang, and A. Knoll. 2014. Timing anomalies in multi-core architectures due to the interference on the shared resources. In Design Automation Conference (DAC\u201914)."},{"key":"e_1_2_1_32_1","volume-title":"International Symposium on Circuits and Systems (ISCAS\u201900)","author":"Thiele L.","unstructured":"L. Thiele , S. Chakraborty , and M. Naedele . 2000. Real-time calculus for scheduling hard real-time systems . In International Symposium on Circuits and Systems (ISCAS\u201900) . L. Thiele, S. Chakraborty, and M. Naedele. 2000. Real-time calculus for scheduling hard real-time systems. In International Symposium on Circuits and Systems (ISCAS\u201900)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1347375.1347389"},{"key":"e_1_2_1_34_1","volume-title":"Workshop on Operating Systems Platforms for Embedded Real-Time Application (OSPERT\u201915)","author":"Yun H.","unstructured":"H. Yun and P. K. Valsan . 2015. Evaluating the isolation effect of cache partitioning on COTS multicore platforms . In Workshop on Operating Systems Platforms for Embedded Real-Time Application (OSPERT\u201915) . H. Yun and P. K. Valsan. 2015. Evaluating the isolation effect of cache partitioning on COTS multicore platforms. In Workshop on Operating Systems Platforms for Embedded Real-Time Application (OSPERT\u201915)."}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3203407","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3203407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:39:23Z","timestamp":1750210763000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3203407"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,22]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,5,31]]}},"alternative-id":["10.1145\/3203407"],"URL":"https:\/\/doi.org\/10.1145\/3203407","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"value":"1539-9087","type":"print"},{"value":"1558-3465","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,22]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}