{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T13:50:00Z","timestamp":1773841800730,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,12,1]],"date-time":"2024-12-01T00:00:00Z","timestamp":1733011200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"vor","delay-in-days":9,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN 2022TS4Y3N - EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data"],"award-info":[{"award-number":["PRIN 2022TS4Y3N - EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007514","name":"Universit\u00e0 di Pisa","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007514","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Soft real-time multiprocessor systems need scheduling policies introducing small overheads and for which it is possible to give guarantees on tardiness (i.e., the maximum delay that might arise with respect to job deadlines) in order to assess their feasibility in specific applications. For these reasons, lightweight policies such as Global Earliest Deadline First, and First-in First-out are preferred. Much effort has been spent in literature to provide efficiently computable tardiness bounds for periodic task systems scheduled on multiprocessors, but still, no exact bounds are known and results are given for specific classes of instances. In this paper, we use a work-conserving policy to schedule uniform instances, namely synchronous and periodic task systems in which tasks have the same period length and the same job length. We analytically derive a tight bound on the maximum tardiness and we give the exact length of the schedule hyper-period, showing that the latter can be computed in time linear in the number of processors. This result provides a lower bound to tardiness for the more general class of instances and is intended to close the gap with the upper bound from below.<\/jats:p>","DOI":"10.1007\/s11241-024-09432-6","type":"journal-article","created":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T13:09:43Z","timestamp":1733836183000},"page":"537-569","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Characterizing global work-conserving scheduling tardiness with uniform instances on multiprocessors"],"prefix":"10.1007","volume":"60","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4117-5312","authenticated-orcid":false,"given":"Giovanni","family":"Buzzega","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuela","family":"Montangero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,10]]},"reference":[{"key":"9432_CR1","doi-asserted-by":"publisher","unstructured":"Ahmed S, Anderson JH (2021) Tight tardiness bounds for pseudo-harmonic tasks under global-edf-like schedulers. In: 33rd Euromicro conference on real-time systems, ECRTS 2021, July 5\u20139, 2021, Virtual Conference. https:\/\/doi.org\/10.4230\/LIPIcs.ECRTS.2021.11","DOI":"10.4230\/LIPIcs.ECRTS.2021.11"},{"issue":"6","key":"9432_CR2","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/j.sysarc.2013.02.001","volume":"59","author":"S Anssi","year":"2013","unstructured":"Anssi S, Kuntz S, G\u00e9rard S, Terrier F (2013) On the gap between schedulability tests and an automotive task model. J Syst Architect 59(6):341\u2013350. https:\/\/doi.org\/10.1016\/j.sysarc.2013.02.001","journal-title":"J Syst Architect"},{"key":"9432_CR3","doi-asserted-by":"publisher","unstructured":"Buzzega G, Nocetti G, Montangero M (2023) Characterizing G-EDF scheduling tardiness with uniform instances on multiprocessors. In: ACM Proceedings of the 31st international conference on real-time networks and systems, RTNS 2023, Dortmund, Germany, June 7\u20138, 2023, pp 45\u201355. https:\/\/doi.org\/10.1145\/3575757.3593641","DOI":"10.1145\/3575757.3593641"},{"key":"9432_CR4","doi-asserted-by":"publisher","unstructured":"Chen C, Mohan S, Pellizzoni R, Bobba RB, Kiyavash N (2019) A novel side-channel in real-time schedulers. In: 25th IEEE real-time and embedded technology and applications symposium, RTAS 2019, Montreal, QC, Canada, April 16\u201318, 2019, pp 90\u2013102. https:\/\/doi.org\/10.1109\/RTAS.2019.00016","DOI":"10.1109\/RTAS.2019.00016"},{"issue":"2","key":"9432_CR5","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s11241-007-9042-1","volume":"38","author":"UC Devi","year":"2008","unstructured":"Devi UC, Anderson JH (2008) Tardiness bounds under global EDF scheduling on a multiprocessor. Real Time Syst 38(2):133\u2013189. https:\/\/doi.org\/10.1007\/s11241-007-9042-1","journal-title":"Real Time Syst"},{"issue":"12","key":"9432_CR6","doi-asserted-by":"publisher","first-page":"2867","DOI":"10.1109\/TPDS.2021.3081019","volume":"32","author":"Z Dong","year":"2021","unstructured":"Dong Z, Yang K, Fisher N, Liu C (2021) Tardiness bounds for sporadic gang tasks under preemptive global EDF scheduling. IEEE Trans Parallel Distrib Syst 32(12):2867\u20132879. https:\/\/doi.org\/10.1109\/TPDS.2021.3081019","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"9432_CR7","doi-asserted-by":"publisher","unstructured":"Erickson J (2014) Tardiness bounds and overload in soft real-time systems. PhD thesis, University of North Carolina, Chapel Hill, USA. https:\/\/doi.org\/10.17615\/fvp3-q039","DOI":"10.17615\/fvp3-q039"},{"key":"9432_CR8","doi-asserted-by":"publisher","unstructured":"Erickson JP, Devi U, Baruah SK (2010a) Improved tardiness bounds for global EDF. In: 22nd Euromicro conference on real-time systems, ECRTS 2010, Brussels, Belgium, July 6\u20139, 2010, pp 14\u201323. https:\/\/doi.org\/10.1109\/ECRTS.2010.25","DOI":"10.1109\/ECRTS.2010.25"},{"key":"9432_CR10","doi-asserted-by":"publisher","unstructured":"Erickson J, Guan N, Baruah SK (2010b) Tardiness bounds for global EDF with deadlines different from periods. In: Principles of distributed systems\u201414th international conference, OPODIS 2010, Tozeur, Tunisia, December 14\u201317, 2010. Proceedings, pp 286\u2013301. https:\/\/doi.org\/10.1007\/978-3-642-17653-1_22","DOI":"10.1007\/978-3-642-17653-1_22"},{"issue":"1","key":"9432_CR9","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s11241-013-9190-4","volume":"50","author":"JP Erickson","year":"2014","unstructured":"Erickson JP, Anderson JH, Ward BC (2014) Fair lateness scheduling: reducing maximum lateness in g-edf-like scheduling. Real Time Syst 50(1):5\u201347. https:\/\/doi.org\/10.1007\/s11241-013-9190-4","journal-title":"Real Time Syst"},{"key":"9432_CR11","doi-asserted-by":"publisher","unstructured":"Fu Y, Kottenstette N, Chen Y, Lu C, Koutsoukos XD, Wang H (2010) Feedback thermal control for real-time systems. In: 16th IEEE real-time and embedded technology and applications symposium, RTAS 2010, Stockholm, Sweden, April 12\u201315, 2010, pp 111\u2013120. https:\/\/doi.org\/10.1109\/RTAS.2010.9","DOI":"10.1109\/RTAS.2010.9"},{"key":"9432_CR12","doi-asserted-by":"publisher","unstructured":"Goh J, Anderson JH (2023) Reducing response-time bounds via global fixed preemption point edf-like scheduling. In: 29th IEEE international conference on embedded and real-time computing systems and applications, RTCSA 2023, Niigata, Japan, August 30\u2013Sept. 1, 2023, pp 117\u2013126. https:\/\/doi.org\/10.1109\/RTCSA58653.2023.00023","DOI":"10.1109\/RTCSA58653.2023.00023"},{"issue":"5","key":"9432_CR13","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/s11241-011-9127-8","volume":"47","author":"S Kato","year":"2011","unstructured":"Kato S, Ishikawa Y, Rajkumar R (2011) Cpu scheduling and memory management for interactive real-time applications. Real-Time Syst 47(5):454\u2013488. https:\/\/doi.org\/10.1007\/s11241-011-9127-8","journal-title":"Real-Time Syst"},{"key":"9432_CR15","doi-asserted-by":"publisher","unstructured":"Leoncini M, Montangero M, Valente P (2017) A branch-and-bound algorithm to compute a tighter bound to tardiness for preemptive global EDF scheduler. In: ACM Proceedings of the 25th international conference on real-time networks and systems, RTNS 2017, Grenoble, France, October 04\u201306, 2017, pp 128\u2013137. https:\/\/doi.org\/10.1145\/3139258.3139277","DOI":"10.1145\/3139258.3139277"},{"issue":"2","key":"9432_CR14","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s11241-018-9319-6","volume":"55","author":"M Leoncini","year":"2019","unstructured":"Leoncini M, Montangero M, Valente P (2019) A parallel branch-and-bound algorithm to compute a tighter tardiness bound for preemptive global EDF. Real Time Syst 55(2):349\u2013386. https:\/\/doi.org\/10.1007\/s11241-018-9319-6","journal-title":"Real Time Syst"},{"key":"9432_CR17","doi-asserted-by":"publisher","unstructured":"Leontyev H, Anderson JH (2007) Tardiness bounds for FIFO scheduling on multiprocessors. In: 19th Euromicro conference on real-time systems, ECRTS\u201907, 4\u20136 July 2007, Pisa, Italy, Proceedings, p 71. https:\/\/doi.org\/10.1109\/ECRTS.2007.33","DOI":"10.1109\/ECRTS.2007.33"},{"key":"9432_CR18","doi-asserted-by":"publisher","unstructured":"Leontyev H, Anderson JH (2008) A unified hard\/soft real-time schedulability test for global EDF multiprocessor scheduling. In: Proceedings of the 29th IEEE real-time systems symposium, RTSS 2008, Barcelona, Spain, 30 November\u20133 December 2008, pp 375\u2013384. https:\/\/doi.org\/10.1109\/RTSS.2008.15","DOI":"10.1109\/RTSS.2008.15"},{"issue":"1\u20133","key":"9432_CR16","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/s11241-009-9089-2","volume":"44","author":"H Leontyev","year":"2009","unstructured":"Leontyev H, Anderson JH (2009) Generalized tardiness bounds for global multiprocessor scheduling. Real-Time Syst 44(1\u20133):26\u201371. https:\/\/doi.org\/10.1007\/s11241-009-9089-2","journal-title":"Real-Time Syst"},{"key":"9432_CR19","doi-asserted-by":"publisher","unstructured":"Li H, Sweeney J, Ramamritham K, Grupen R, Shenoy P (2003) Real-time support for mobile robotics. In: The 9th IEEE real-time and embedded technology and applications symposium, 2003. Proceedings, pp 10\u201318. https:\/\/doi.org\/10.1109\/RTTAS.2003.1203032","DOI":"10.1109\/RTTAS.2003.1203032"},{"key":"9432_CR20","doi-asserted-by":"publisher","unstructured":"Mills AF, Anderson JH (2010) A stochastic framework for multiprocessor soft real-time scheduling. In: 2010 16th IEEE real-time and embedded technology and applications symposium. https:\/\/doi.org\/10.1109\/rtas.2010.33","DOI":"10.1109\/rtas.2010.33"},{"key":"9432_CR21","doi-asserted-by":"publisher","unstructured":"Mills AF, Anderson JH (2011) A multiprocessor server-based scheduler for soft real-time tasks with stochastic execution demand. In: 2011 IEEE 17th international conference on embedded and real-time computing systems and applications. https:\/\/doi.org\/10.1109\/rtcsa.2011.30","DOI":"10.1109\/rtcsa.2011.30"},{"key":"9432_CR22","doi-asserted-by":"publisher","unstructured":"Shih C, Gopalakrishnan S, Ganti P, Caccamo M, Sha L (2003) Scheduling real-time dwells using tasks with synthetic periods. In: Proceedings of the 24th IEEE real-time systems symposium (RTSS 2003), 3\u20135 December 2003, Cancun, Mexico, pp 210\u2013219. https:\/\/doi.org\/10.1109\/REAL.2003.1253268","DOI":"10.1109\/REAL.2003.1253268"},{"issue":"4","key":"9432_CR23","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/s11241-015-9237-9","volume":"52","author":"P Valente","year":"2016","unstructured":"Valente P (2016) Using a lag-balance property to tighten tardiness bounds for global EDF. Real Time Syst 52(4):486\u2013561. https:\/\/doi.org\/10.1007\/s11241-015-9237-9","journal-title":"Real Time Syst"},{"key":"9432_CR24","doi-asserted-by":"publisher","unstructured":"Voronov S, Anderson JH, Yang K (2018) Tardiness bounds for fixed-priority global scheduling without intra-task precedence constraints. In: Proceedings of the 26th international conference on real-time networks and systems, RTNS 2018, Chasseneuil-du-Poitou, France, October 10\u201312, 2018, pp 8\u201318. https:\/\/doi.org\/10.1145\/3273905.3273913","DOI":"10.1145\/3273905.3273913"},{"issue":"7","key":"9432_CR25","doi-asserted-by":"publisher","first-page":"1247","DOI":"10.1109\/tc.2016.2640961","volume":"66","author":"H Yun","year":"2017","unstructured":"Yun H, Ali W, Gondi S, Biswas S (2017) Bwlock: a dynamic memory access control framework for soft real-time applications on multicore platforms. IEEE Trans Comput 66(7):1247\u20131252. https:\/\/doi.org\/10.1109\/tc.2016.2640961","journal-title":"IEEE Trans Comput"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-024-09432-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-024-09432-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-024-09432-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,12]],"date-time":"2024-12-12T15:06:46Z","timestamp":1734016006000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-024-09432-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9432"],"URL":"https:\/\/doi.org\/10.1007\/s11241-024-09432-6","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12]]},"assertion":[{"value":"25 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}