{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:38:29Z","timestamp":1740123509188,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T00:00:00Z","timestamp":1649376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T00:00:00Z","timestamp":1649376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"MCIN\/AEI andEuropean Union NextGenerationEU \/ PRTR","award":["PLEC2021-00760"],"award-info":[{"award-number":["PLEC2021-00760"]}]},{"name":"Universidad Polit\u00e8cnica de Val\u00e8ncia"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In multicore scheduling of hard real-time systems, there is a significant source of unpredictability due to the interference caused by the sharing of hardware resources. This paper deals with the schedulability analysis of multicore systems where the interference caused by the sharing of hardware resources is taken into account. We rely on a task model where this interference is integrated in a general way, without depending on a specific type of hardware resource. There are similar approaches but they consider fixed priorities. The schedulability analysis is provided for dynamic priorities assuming constrained deadlines and based on the demand bound function. We propose two techniques, one more pessimistic than the other but with a lower computational cost. We evaluate the two proposals for different task allocators in terms of the increased estimated utilization. The results show that both bounds are valid for ensuring schedulability although, as expected, one is tighter than the other. The evaluation also serves to compare allocators to see which one produces less interference.<\/jats:p>","DOI":"10.1007\/s11227-022-04446-y","type":"journal-article","created":{"date-parts":[[2022,4,8]],"date-time":"2022-04-08T16:02:45Z","timestamp":1649433765000},"page":"14703-14725","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Schedulability analysis of dynamic priority real-time systems with contention"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2900-8466","authenticated-orcid":false,"given":"Ana","family":"Guasque","sequence":"first","affiliation":[]},{"given":"Jos\u00e9 Mar\u00eda","family":"Aceituno","sequence":"additional","affiliation":[]},{"given":"Patricia","family":"Balbastre","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9","family":"Sim\u00f3","sequence":"additional","affiliation":[]},{"given":"Alfons","family":"Crespo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,8]]},"reference":[{"key":"4446_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.sysarc.2021.102223","volume":"118","author":"JM Aceituno","year":"2021","unstructured":"Aceituno JM, Guasque A, Balbastre P et al (2021) Hardware resources contention-aware scheduling of hard real-time multiprocessor systems. J Syst Archit 118:1\u201311","journal-title":"J Syst Archit"},{"key":"4446_CR2","doi-asserted-by":"crossref","unstructured":"Altmeyer S, Davis RI, Indrusiak L et\u00a0al (2015) A generic and compositional framework for multicore response time analysis. In: Proceedings of the 23rd International Conference on Real Time and Networks Systems, RTNS \u201915, pp 129\u2013138","DOI":"10.1145\/2834848.2834862"},{"issue":"3","key":"4446_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3203407","volume":"17","author":"B Andersson","year":"2018","unstructured":"Andersson B, Kim H, Niz DD et al (2018) Schedulability analysis of tasks with corunner-dependent execution times. ACM Trans Embed Comput Syst 17(3):1\u201329","journal-title":"ACM Trans Embed Comput Syst"},{"key":"4446_CR4","doi-asserted-by":"crossref","unstructured":"Baruah SK, Mok AK, Rosier LE (1990a) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: (1990) Proceedings 11th Real-Time Systems Symposium, pp 182\u2013190","DOI":"10.1109\/REAL.1990.128746"},{"issue":"4","key":"4446_CR5","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01995675","volume":"2","author":"SK Baruah","year":"1990","unstructured":"Baruah SK, Rosier LE, Howell RR (1990) Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Syst 2(4):301\u2013324","journal-title":"Real-Time Syst"},{"key":"4446_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90360-6","volume":"118","author":"SK Baruah","year":"1993","unstructured":"Baruah SK, Howell RR, Rosier LE (1993) Feasibility problems for recurring tasks on one processor. Theor Comput Sci 118:3\u201320","journal-title":"Theor Comput Sci"},{"key":"4446_CR7","doi-asserted-by":"crossref","unstructured":"Choi J, Kang D, Ha S (2016) Conservative Modeling of Shared Resource Contention for Dependent Tasks in Partitioned Multi-core Systems. In: 2016 Design, Automation Test in Europe Conference Exhibition (DATE), pp 181\u2013186","DOI":"10.3850\/9783981537079_0101"},{"key":"4446_CR8","unstructured":"Coffman EG, Garey MR, Johnson DS (1996) Approximation algorithms for bin packing: a survey. PWS Publishing Co"},{"key":"4446_CR9","volume-title":"Bin packing approximation algorithms: survey and classification","author":"EG Coffman Jr","year":"2013","unstructured":"Coffman EG Jr, Csirik J, Galambos G et al (2013) Bin packing approximation algorithms: survey and classification. Springer, New York"},{"key":"4446_CR10","doi-asserted-by":"crossref","unstructured":"Dasari D, Andersson B, Nelis V, et\u00a0al (2011) Response time analysis of cots-based multicores considering the contention on the shared memory bus. In: 2011 IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications, pp 1068\u20131075","DOI":"10.1109\/TrustCom.2011.146"},{"key":"4446_CR11","doi-asserted-by":"crossref","unstructured":"Dasari D, Akesson B, N\u00e9lis V, et\u00a0al (2013) Identifying the sources of unpredictability in cots-based multicore systems. In: 2013 8th IEEE international symposium on industrial embedded systems (SIES), pp 39\u201348","DOI":"10.1109\/SIES.2013.6601469"},{"key":"4446_CR12","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/s11241-017-9285-4","volume":"54","author":"R Davis","year":"2018","unstructured":"Davis R, Altmeyer S, Indrusiak L et al (2018) An extensible framework for multicore response time analysis. Real-Time Syst 54:607\u2013661","journal-title":"Real-Time Syst"},{"key":"4446_CR13","doi-asserted-by":"crossref","unstructured":"Davis RI, Burns A (2009) Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In: 2009 30th IEEE real-time systems symposium, pp 398\u2013409","DOI":"10.1109\/RTSS.2009.31"},{"issue":"4","key":"4446_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1978802.1978814","volume":"43","author":"RI Davis","year":"2011","unstructured":"Davis RI, Burns A (2011) A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surv 43(4):1\u201344","journal-title":"ACM Comput Surv"},{"key":"4446_CR15","unstructured":"Davis RI, Griffin D, Bate I (2021) Schedulability Analysis for Multi-core Systems Accounting for Resource Stress and Sensitivity. In: 33rd Euromicro Conference on Real-Time Systems, ECRTS 2021 Virtual Conference, LIPIcs, vol 196. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 7:1\u20137:26"},{"key":"4446_CR16","unstructured":"Fernandez G, Abella J, Qui\u00f1ones E et al (2014) Contention in Multicore Hardware Shared Resources: Understanding of the State of the Art. In: Falk H (ed) 14th international workshop on worst-case execution time analysis, openaccess series in informatics (OASIcs), vol 39. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Dagstuhl, Germany, pp 31\u201342"},{"issue":"2","key":"4446_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2830555","volume":"48","author":"G Gracioli","year":"2015","unstructured":"Gracioli G, Alhammad A, Mancuso R et al (2015) A survey on cache management mechanisms for real-time embedded systems. ACM Comput Surv 48(2):1\u201336","journal-title":"ACM Comput Surv"},{"key":"4446_CR18","doi-asserted-by":"crossref","unstructured":"Guo Z, Yang K, Yao F et\u00a0al (2020) Inter-task cache interference aware partitioned real-time scheduling, association for computing machinery, p 218-226","DOI":"10.1145\/3341105.3374014"},{"key":"#cr-split#-4446_CR19.1","unstructured":"Hassan M, Pellizzoni R (2020) Analysis of Memory-Contention in Heterogeneous COTS MPSoCs. In: V\u00f6lp M"},{"key":"#cr-split#-4446_CR19.2","unstructured":"(ed) 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020), pp 23:1-23:24"},{"key":"4446_CR20","doi-asserted-by":"crossref","unstructured":"Huang WH, Chen JJ, Reineke J (2016) Mirror: symmetric timing analysis for real-time tasks on multicore platforms with shared resources. In: Proceedings of the 53rd Annual Design Automation Conference, DAC \u201916","DOI":"10.1145\/2897937.2898046"},{"key":"4446_CR21","first-page":"39","volume":"02","author":"N Karuppiah","year":"2016","unstructured":"Karuppiah N (2016) The impact of interference due to resource contention in multicore platform for safety-critical avionics systems. Int J Res Eng Appl Manag (IJREAM) 02:39\u201348","journal-title":"Int J Res Eng Appl Manag (IJREAM)"},{"key":"4446_CR22","doi-asserted-by":"crossref","unstructured":"Kim H, de Niz D, Andersson B et\u00a0al (2014) Bounding memory interference delay in cots-based multi-core systems. In: 2014 IEEE 19th real-time and embedded technology and applications symposium (RTAS), pp 145\u2013154","DOI":"10.1109\/RTAS.2014.6925998"},{"key":"4446_CR23","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/s11241-014-9211-y","volume":"50","author":"K Lampka","year":"2014","unstructured":"Lampka K, Giannopoulou G, Pellizzoni R et al (2014) A formal approach to the wcrt analysis of multicore systems with memory contention under phase-structured task sets. Real-Time Syst 50:736\u2013773","journal-title":"Real-Time Syst"},{"issue":"1","key":"4446_CR24","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/321738.321743","volume":"20","author":"CL Liu","year":"1973","unstructured":"Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46\u201361","journal-title":"J ACM"},{"issue":"3","key":"4446_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3323212","volume":"52","author":"C Maiza","year":"2019","unstructured":"Maiza C, Rihani H, Rivas JM et al (2019) A survey of timing verification techniques for multi-core real-time systems. ACM Comput Surv 52(3):1\u201346","journal-title":"ACM Comput Surv"},{"issue":"2","key":"4446_CR26","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/MDAT.2018.2794204","volume":"35","author":"T Mitra","year":"2018","unstructured":"Mitra T, Teich J, Thiele L (2018) Time-critical systems design: a survey. IEEE Design Test 35(2):8\u201326","journal-title":"IEEE Design Test"},{"key":"4446_CR27","unstructured":"Oh SH, Yang SM (1998) A Modified Least-Laxity-First Scheduling Algorithm for Real-Time Tasks. In: Proceedings Fifth International Conference on Real-Time Computing Systems and Applications (Cat. No.98EX236), pp 31\u201336"},{"issue":"3","key":"4446_CR28","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/BF01088806","volume":"9","author":"Y Oh","year":"1995","unstructured":"Oh Y, Son SH (1995) Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Syst 9(3):207\u2013239","journal-title":"Real-Time Syst"},{"key":"4446_CR29","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s11241-005-0506-x","volume":"30","author":"R Pellizzoni","year":"2005","unstructured":"Pellizzoni R, Lipari G (2005) Feasibility analysis of real-time periodic tasks with offsets. Real-Time Syst 30:105\u2013128","journal-title":"Real-Time Syst"},{"key":"4446_CR30","doi-asserted-by":"crossref","unstructured":"Rihani H, Moy M, Maiza C, et\u00a0al (2016) Response Time Analysis of Synchronous Data Flow Programs on a Many-Core Processor. In: Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS \u201916, p 67-76","DOI":"10.1145\/2997465.2997472"},{"issue":"1","key":"4446_CR31","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF00365519","volume":"11","author":"I Ripoll","year":"1996","unstructured":"Ripoll I, Crespo A, Mok AK (1996) Improvement in feasibility testing for real-time tasks. Real-Time Syst 11(1):19\u201339","journal-title":"Real-Time Syst"},{"key":"4446_CR32","unstructured":"Salmani V, Taghavi\u00a0Zargar S, Naghibzadeh M (2005) A Modified Maximum Urgency First Scheduling Algorithm for Real-Time Tasks. Proc Seventh World Enformatika Conference"},{"key":"4446_CR33","unstructured":"Spuri M (1996) Analysis of deadline scheduled real-time systems. Tech. rep"},{"key":"4446_CR34","doi-asserted-by":"crossref","unstructured":"Xiao J, Altmeyer S, Pimentel A (2017) Schedulability analysis of non-preemptive real-time scheduling for multicore processors with shared caches. In: 2017 IEEE real-time systems symposium (RTSS), pp 199\u2013208","DOI":"10.1109\/RTSS.2017.00026"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04446-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-022-04446-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04446-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T16:46:04Z","timestamp":1658162764000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-022-04446-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,8]]},"references-count":35,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["4446"],"URL":"https:\/\/doi.org\/10.1007\/s11227-022-04446-y","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2022,4,8]]},"assertion":[{"value":"10 March 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}