{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T13:19:15Z","timestamp":1774099155566,"version":"3.50.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T00:00:00Z","timestamp":1717200000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T00:00:00Z","timestamp":1717632000000},"content-version":"vor","delay-in-days":5,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hong Kong Polytechnic University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper considers the real-time scheduling of a parallel task with reclaiming computing resources, which can be utilized for soft real-time tasks or switching to low-energy mode to save energy. Existing works allocate a <jats:italic>rectangular<\/jats:italic> piece of computing resources based on the worst-case characterizations of the task to guarantee the deadline, which inherently incurs severe resource wasting due to coarse-grained resource allocation. To address this resource-wasting problem, this paper proposes the <jats:italic>ladder-like<\/jats:italic> resource allocation (i.e., a series of rectangular pieces of computing resources). To characterize the ladder-like resource allocation, we present two concepts called <jats:italic>resource distribution<\/jats:italic> and <jats:italic>allocation vector<\/jats:italic>, which serve as the interfaces between hard and soft real-time tasks. For the former, we derive schedulability tests under the given two interfaces; for the latter, we discuss the methods of determining the two interfaces to reclaim computing resources. This paper is the first work to fully explore the concept of ladder-like resource allocation and its potential consequences on computing resources, soft real-time tasks, and energy. Experiments demonstrate that the proposed approach can effectively reclaim more computing resources than existing approaches while maintaining hard real-time guarantees.<\/jats:p>","DOI":"10.1007\/s11241-024-09421-9","type":"journal-article","created":{"date-parts":[[2024,6,6]],"date-time":"2024-06-06T20:17:31Z","timestamp":1717705051000},"page":"291-327","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Real-time scheduling for parallel tasks with resource reclamation"],"prefix":"10.1007","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5067-8571","authenticated-orcid":false,"given":"Qingqiang","family":"He","sequence":"first","affiliation":[]},{"given":"Yongzheng","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Xu","family":"Jiang","sequence":"additional","affiliation":[]},{"given":"Mingsong","family":"Lv","sequence":"additional","affiliation":[]},{"given":"Jinkyu","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Nan","family":"Guan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,6,6]]},"reference":[{"key":"9421_CR1","unstructured":"Agrawal K, Baruah S (2018) A measurement-based model for parallel real-time tasks. In: 30th Euromicro conference on real-time systems (ECRTS 2018), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"9421_CR2","doi-asserted-by":"crossref","unstructured":"Baruah S (2015a) The federated scheduling of constrained-deadline sporadic DAG task systems. In: 2015 design, automation & test in Europe conference & exhibition (DATE), IEEE, pp 1323\u20131328","DOI":"10.7873\/DATE.2015.0200"},{"key":"9421_CR3","doi-asserted-by":"crossref","unstructured":"Baruah S (2015b) Federated scheduling of sporadic DAG task systems. In: 2015 IEEE international parallel and distributed processing symposium, IEEE, pp 179\u2013186","DOI":"10.1109\/IPDPS.2015.33"},{"key":"9421_CR4","doi-asserted-by":"crossref","unstructured":"Baruah S (2015c) The federated scheduling of systems of conditional sporadic DAG tasks. In: Proceedings of the 12th international conference on embedded software, IEEE Press, pp 1\u201310","DOI":"10.1109\/EMSOFT.2015.7318254"},{"key":"9421_CR5","doi-asserted-by":"crossref","unstructured":"Baruah S (2015d) The federated scheduling of systems of conditional sporadic DAG tasks. In: 2015 international conference on embedded software (EMSOFT), IEEE, pp 1\u201310","DOI":"10.1109\/EMSOFT.2015.7318254"},{"key":"9421_CR6","doi-asserted-by":"crossref","unstructured":"Baruah S (2018) Resource-efficient execution of conditional parallel real-time tasks. In: European conference on parallel processing, Springer, pp 218\u2013231","DOI":"10.1007\/978-3-319-96983-1_16"},{"key":"9421_CR7","doi-asserted-by":"crossref","unstructured":"Baruah S, Bonifaci V, Marchetti-Spaccamela A (2015) The global EDF scheduling of systems of conditional sporadic DAG tasks. In: 2015 27th Euromicro conference on real-time systems, IEEE, pp 222\u2013231","DOI":"10.1109\/ECRTS.2015.27"},{"key":"9421_CR8","doi-asserted-by":"crossref","unstructured":"Bernat G, Colin A, Petters SM (2002) WCET analysis of probabilistic hard real-time systems. In: 23rd IEEE real-time systems symposium, 2002. RTSS 2002., IEEE, pp 279\u2013288","DOI":"10.1109\/REAL.2002.1181582"},{"key":"9421_CR9","doi-asserted-by":"crossref","unstructured":"Bi R, He Q, Sun J, et\u00a0al (2022) Response time analysis for prioritized DAG task with mutually exclusive vertices. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 460\u2013473","DOI":"10.1109\/RTSS55097.2022.00046"},{"issue":"1\u20132","key":"9421_CR10","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/s11241-005-0507-9","volume":"30","author":"E Bini","year":"2005","unstructured":"Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-time Syst 30(1\u20132):129\u2013154","journal-title":"Real-time Syst"},{"key":"9421_CR11","doi-asserted-by":"crossref","unstructured":"Casini D, Biondi A, Nelissen G, et\u00a0al (2018) Partitioned fixed-priority scheduling of parallel tasks without preemptions. In: 2018 IEEE real-time systems symposium (RTSS), IEEE, pp 421\u2013433","DOI":"10.1109\/RTSS.2018.00056"},{"issue":"5s","key":"9421_CR12","first-page":"1","volume":"18","author":"P Chen","year":"2019","unstructured":"Chen P, Liu W, Jiang X et al (2019) Timing-anomaly free dynamic scheduling of conditional DAG tasks on multi-core systems. ACM Trans Embedded Comput Syst (TECS) 18(5s):1\u201319","journal-title":"ACM Trans Embedded Comput Syst (TECS)"},{"issue":"7","key":"9421_CR13","doi-asserted-by":"publisher","first-page":"1381","DOI":"10.1109\/TCAD.2020.3015440","volume":"40","author":"P Chen","year":"2020","unstructured":"Chen P, Liu W, Chen H et al (2020) Reduced worst-case communication latency using single-cycle multihop traversal network-on-chip. IEEE Trans Comput Aided Design Integr Circuits Syst 40(7):1381\u20131394","journal-title":"IEEE Trans Comput Aided Design Integr Circuits Syst"},{"key":"9421_CR14","doi-asserted-by":"crossref","unstructured":"Cordeiro D, Mouni\u00e9 G, Perarnau S, et\u00a0al (2010) Random graph generation for scheduling simulations. In: 3rd international ICST conference on simulation tools and techniques (SIMUTools 2010), ICST, p\u00a010","DOI":"10.4108\/ICST.SIMUTOOLS2010.8667"},{"key":"9421_CR15","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1007\/s11241-018-9318-7","volume":"55","author":"Z Dong","year":"2019","unstructured":"Dong Z, Liu C (2019) Analysis techniques for supporting hard real-time sporadic gang task systems. Real-Time Syst 55:641\u2013666","journal-title":"Real-Time Syst"},{"key":"9421_CR16","doi-asserted-by":"crossref","unstructured":"Edgar S, Burns A (2001) Statistical analysis of WCET for scheduling. In: Proceedings 22nd IEEE real-time systems symposium (RTSS 2001)(Cat. No. 01PR1420), IEEE, pp 215\u2013224","DOI":"10.1109\/REAL.2001.990614"},{"key":"9421_CR17","doi-asserted-by":"crossref","unstructured":"Fonseca J, Nelissen G, Nelis V, et\u00a0al (2016) Response time analysis of sporadic DAG tasks under partitioned scheduling. In: 2016 11th IEEE symposium on industrial embedded systems (SIES), IEEE, pp 1\u201310","DOI":"10.1109\/SIES.2016.7509443"},{"issue":"2","key":"9421_CR18","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17(2):416\u2013429","journal-title":"SIAM J Appl Math"},{"issue":"11","key":"9421_CR19","doi-asserted-by":"publisher","first-page":"2567","DOI":"10.1109\/TPDS.2019.2916696","volume":"30","author":"M Han","year":"2019","unstructured":"Han M, Guan N, Sun J et al (2019) Response time bounds for typed DAG parallel tasks on heterogeneous multi-cores. IEEE Trans Parallel Distrib Syst 30(11):2567\u20132581","journal-title":"IEEE Trans Parallel Distrib Syst"},{"issue":"10","key":"9421_CR20","doi-asserted-by":"publisher","first-page":"2283","DOI":"10.1109\/TPDS.2019.2910525","volume":"30","author":"Q He","year":"2019","unstructured":"He Q, Jiang X, Guan N et al (2019) Intra-task priority assignment in real-time scheduling of DAG tasks on multi-cores. IEEE Trans Parallel Distrib Syst 30(10):2283\u20132295","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"9421_CR25","unstructured":"He Q, Lv M, Guan N (2021) Response time bounds for DAG tasks with arbitrary intra-task priority assignment. In: 33rd Euromicro conference on real-time systems (ECRTS 2021), Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"9421_CR23","doi-asserted-by":"crossref","unstructured":"He Q, Guan N, Lv M, et\u00a0al (2022) Bounding the response time of DAG tasks using long paths. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 474\u2013486","DOI":"10.1109\/RTSS55097.2022.00047"},{"key":"9421_CR24","doi-asserted-by":"crossref","unstructured":"He Q, Guan N, Lv M, et\u00a0al (2023a) On the degree of parallelism in real-time scheduling of DAG tasks. In: 2023 design, automation & Test in Europe conference & exhibition (DATE), IEEE, pp 1\u20136","DOI":"10.23919\/DATE56975.2023.10137259"},{"key":"9421_CR21","first-page":"1","volume":"2023","author":"Q He","year":"2023","unstructured":"He Q, Guan N, Lv M et al (2023b) The shape of a DAG: bounding the response time using long paths. Real-Time Syst 2023:1\u201340","journal-title":"Real-Time Syst"},{"issue":"10","key":"9421_CR22","doi-asserted-by":"publisher","first-page":"3196","DOI":"10.1109\/TCAD.2023.3241221","volume":"42","author":"Q He","year":"2023","unstructured":"He Q, Sun J, Guan N et al (2023c) Real-time scheduling of conditional DAG tasks with intra-task priority assignment. IEEE Trans Comput Aided Design Integr Circuits Syst 42(10):3196\u20133209. https:\/\/doi.org\/10.1109\/TCAD.2023.3241221","journal-title":"IEEE Trans Comput Aided Design Integr Circuits Syst"},{"key":"9421_CR29","doi-asserted-by":"crossref","unstructured":"Jiang X, Long X, Guan N, et\u00a0al (2016) On the decomposition-based global EDF scheduling of parallel real-time tasks. In: 2016 IEEE real-time systems symposium (RTSS), IEEE, pp 237\u2013246","DOI":"10.1109\/RTSS.2016.031"},{"key":"9421_CR28","doi-asserted-by":"crossref","unstructured":"Jiang X, Guan N, Long X, et\u00a0al (2017) Semi-federated scheduling of parallel real-time tasks on multiprocessors. In: 2017 IEEE real-time systems symposium (RTSS), IEEE, pp 80\u201391","DOI":"10.1109\/RTSS.2017.00015"},{"key":"9421_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2020.101742","volume":"108","author":"X Jiang","year":"2020","unstructured":"Jiang X, Guan N, Long X et al (2020) Real-time scheduling of parallel tasks with tight deadlines. J Syst Archit 108:101742","journal-title":"J Syst Archit"},{"key":"9421_CR27","doi-asserted-by":"crossref","unstructured":"Jiang X, Guan N, Liang H, et\u00a0al (2021) Virtually-federated scheduling of parallel real-time tasks. In: 2021 IEEE real-time systems symposium (RTSS), IEEE, pp 482\u2013494","DOI":"10.1109\/RTSS52674.2021.00050"},{"key":"9421_CR30","doi-asserted-by":"crossref","unstructured":"Lakshmanan K, Kato S, Rajkumar R (2010) Scheduling parallel real-time tasks on multi-core processors. In: 2010 31st IEEE real-time systems symposium, IEEE, pp 259\u2013268","DOI":"10.1109\/RTSS.2010.42"},{"key":"9421_CR31","doi-asserted-by":"crossref","unstructured":"Lee S, Lee S, Lee J (2022) Response time analysis for real-time global gang scheduling. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 92\u2013104","DOI":"10.1109\/RTSS55097.2022.00018"},{"key":"9421_CR32","doi-asserted-by":"crossref","unstructured":"Li J, Agrawal K, Lu C, et\u00a0al (2013) Analysis of global EDF for parallel tasks. In: 2013 25th Euromicro conference on real-time systems, IEEE, pp 3\u201313","DOI":"10.1109\/ECRTS.2013.12"},{"key":"9421_CR34","doi-asserted-by":"crossref","unstructured":"Li J, Chen JJ, Agrawal K, et\u00a0al (2014) Analysis of federated and global scheduling for parallel real-time tasks. In: 2014 26th Euromicro conference on real-time systems, IEEE, pp 85\u201396","DOI":"10.1109\/ECRTS.2014.23"},{"key":"9421_CR35","doi-asserted-by":"crossref","unstructured":"Li R, Guan N, Jiang X, et\u00a0al (2022) Worst-case time disparity analysis of message synchronization in ros. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 40\u201352","DOI":"10.1109\/RTSS55097.2022.00014"},{"key":"9421_CR33","doi-asserted-by":"crossref","unstructured":"Liang H, Jiang X, Guan N, et\u00a0al (2023) Response time analysis and optimization of DAG tasks exploiting mutually exclusive execution. In: 2023 60th ACM\/IEEE design automation conference (DAC), IEEE, pp 1\u20136","DOI":"10.1109\/DAC56929.2023.10247927"},{"key":"9421_CR36","doi-asserted-by":"crossref","unstructured":"Lv M, Peng X, Xie W, et\u00a0al (2022) Task allocation for real-time earth observation service with leo satellites. In: 2022 IEEE real-time systems symposium (RTSS), IEEE, pp 14\u201326","DOI":"10.1109\/RTSS55097.2022.00012"},{"key":"9421_CR38","doi-asserted-by":"crossref","unstructured":"Melani A, Bertogna M, Bonifaci V, et\u00a0al (2015) Response-time analysis of conditional DAG tasks in multiprocessor systems. In: 2015 27th Euromicro conference on real-time systems, IEEE, pp 211\u2013221","DOI":"10.1109\/ECRTS.2015.26"},{"issue":"2","key":"9421_CR37","first-page":"339","volume":"66","author":"A Melani","year":"2016","unstructured":"Melani A, Bertogna M, Bonifaci V et al (2016) Schedulability analysis of conditional parallel task graphs in multicore systems. IEEE Trans Comput 66(2):339\u2013353","journal-title":"IEEE Trans Comput"},{"key":"9421_CR39","doi-asserted-by":"crossref","unstructured":"Qamhieh M, Fauberteau F, George L, et\u00a0al (2013) Global EDF scheduling of directed acyclic graphs on multiprocessor systems. In: Proceedings of the 21st international conference on real-time networks and systems, pp 287\u2013296","DOI":"10.1145\/2516821.2516836"},{"key":"9421_CR43","doi-asserted-by":"crossref","unstructured":"Sun J, Guan N, Wang Y, et\u00a0al (2017) Real-time scheduling and analysis of OpenMP task systems with tied tasks. In: 2017 IEEE real-time systems symposium (RTSS), IEEE, pp 92\u2013103","DOI":"10.1109\/RTSS.2017.00016"},{"key":"9421_CR40","doi-asserted-by":"crossref","unstructured":"Sun J, Chi Y, Xu T, et\u00a0al (2020) On the volume calculation for conditional DAG tasks: hardness and algorithms. In: 2020 design, automation & test in Europe conference & exhibition (DATE), IEEE, pp 204\u2013209","DOI":"10.23919\/DATE48585.2020.9116559"},{"key":"9421_CR42","doi-asserted-by":"crossref","unstructured":"Sun J, Guan N, Guo Z, et\u00a0al (2021) Calculating worst-case response time bounds for OpenMP programs with loop structures. In: 2021 IEEE real-time systems symposium, IEEE, pp 123\u2013135","DOI":"10.1109\/RTSS52674.2021.00022"},{"key":"9421_CR41","doi-asserted-by":"crossref","unstructured":"Sun J, Duan K, Li X, et\u00a0al (2023) Real-time scheduling of autonomous driving system with guaranteed timing correctness. In: 2023 IEEE 29th real-time and embedded technology and applications symposium (RTAS), IEEE, pp 185\u2013197","DOI":"10.1109\/RTAS58335.2023.00022"},{"key":"9421_CR44","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-981-287-251-7_29","volume-title":"Handbook of real-time computing","author":"Y Tang","year":"2022","unstructured":"Tang Y, Guan N, Yi W (2022) Real-time task models. Handbook of real-time computing. Springer, Cham, pp 469\u2013487"},{"key":"9421_CR45","doi-asserted-by":"crossref","unstructured":"Ueter N, Von Der\u00a0Br\u00fcggen G, Chen JJ, et\u00a0al (2018) Reservation-based federated scheduling for parallel real-time tasks. In: 2018 IEEE real-time systems symposium (RTSS), IEEE, pp 482\u2013494","DOI":"10.1109\/RTSS.2018.00061"},{"key":"9421_CR46","first-page":"1","volume":"2022","author":"P Voudouris","year":"2022","unstructured":"Voudouris P, Stenstr\u00f6m P, Pathan R (2022) Bounding the execution time of parallel applications on unrelated multiprocessors. Real-Time Syst 2022:1\u201344","journal-title":"Real-Time Syst"},{"key":"9421_CR47","doi-asserted-by":"crossref","unstructured":"Zhao S, Dai X, Bate I, et\u00a0al (2020) DAG scheduling and analysis on multiprocessor systems: Exploitation of parallelism and dependency. In: 2020 IEEE real-time systems symposium (RTSS), IEEE, pp 128\u2013140","DOI":"10.1109\/RTSS49844.2020.00022"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-024-09421-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-024-09421-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-024-09421-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,13]],"date-time":"2024-07-13T16:14:39Z","timestamp":1720887279000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-024-09421-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9421"],"URL":"https:\/\/doi.org\/10.1007\/s11241-024-09421-9","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6]]},"assertion":[{"value":"6 May 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose. The authors have no conflict of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}