{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:43:27Z","timestamp":1761324207373,"version":"3.37.3"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T00:00:00Z","timestamp":1552435200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1409175","CPS 1446631"],"award-info":[{"award-number":["CNS 1409175","CPS 1446631"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1563845","CNS 1717589"],"award-info":[{"award-number":["CNS 1563845","CNS 1717589"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-14-1-0161"],"award-info":[{"award-number":["FA9550-14-1-0161"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-14-1-0499","W911NF-17-1-0294"],"award-info":[{"award-number":["W911NF-14-1-0499","W911NF-17-1-0294"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"name":"General Motors"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGS 1650116"],"award-info":[{"award-number":["DGS 1650116"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s11241-019-09328-w","type":"journal-article","created":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T15:30:01Z","timestamp":1552491001000},"page":"296-348","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Real-time multiprocessor locks with nesting: optimizing the common case"],"prefix":"10.1007","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5800-3533","authenticated-orcid":false,"given":"Catherine E.","family":"Nemitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tanya","family":"Amert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James H.","family":"Anderson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,3,13]]},"reference":[{"key":"9328_CR1","doi-asserted-by":"crossref","unstructured":"Afshar S, Behnam M, Bril R, Nolte T (2014) Flexible spin-lock model for resource sharing in multiprocessor real-time systems. In: Proceedings of the 9th IEEE international symposium on industrial embedded systems, pp 41\u201351. IEEE","DOI":"10.1109\/SIES.2014.6871185"},{"key":"9328_CR2","doi-asserted-by":"crossref","unstructured":"Afshar S, Behnam M, Bril R, Nolte T (2017) An optimal spin-lock priority assignment algorithm for real-time multi-core systems. In: Proceedings of the 23rd IEEE international conference on embedded and real-time computing systems and applications, pp 1\u201311. IEEE","DOI":"10.1109\/RTCSA.2017.8046310"},{"issue":"2","key":"9328_CR3","first-page":"1","volume":"4","author":"S Afshar","year":"2018","unstructured":"Afshar S, Behnam M, Bril R, Nolte T (2018) Per processor spin-based protocols for multiprocessor real-time systems. Leibniz Trans Embed Syst 4(2):1\u201330","journal-title":"Leibniz Trans Embed Syst"},{"issue":"3","key":"9328_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/2544350.2544356","volume":"10","author":"S Afshar","year":"2013","unstructured":"Afshar S, Behnam M, Nolte T (2013) Integrating independently developed real-time applications on a shared multi-core architecture. ACM SIGBED Rev 10(3):49\u201356","journal-title":"ACM SIGBED Rev"},{"issue":"1","key":"9328_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/2752801.2752807","volume":"12","author":"S Afshar","year":"2015","unstructured":"Afshar S, Khalilzad N, Nemati F, Nolte T (2015) Resource sharing among prioritized real-time applications on multiprocessors. ACM SIGBED Rev 12(1):46\u201355","journal-title":"ACM SIGBED Rev"},{"key":"9328_CR6","doi-asserted-by":"crossref","unstructured":"Bacon D, Konuru R, Murthy C, Serrano M (1998) Thin locks: featherweight synchronization for Java. In: ACM SIGPLAN Notices, vol\u00a033, pp 258\u2013268. ACM","DOI":"10.1145\/277652.277734"},{"issue":"1","key":"9328_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF00365393","volume":"3","author":"TP Baker","year":"1991","unstructured":"Baker TP (1991) Stack-based scheduling of realtime processes. Real-Time Syst 3(1):67\u201399","journal-title":"Real-Time Syst"},{"key":"9328_CR8","doi-asserted-by":"crossref","unstructured":"Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: Proceedings of the 28th IEEE real-time systems symposium, pp 119\u2013128. IEEE","DOI":"10.1109\/RTSS.2007.35"},{"key":"9328_CR9","doi-asserted-by":"crossref","unstructured":"Biondi A, Brandenburg B, Wieder A (2016) A blocking bound for nested FIFO spin locks. In: Proceedings of the 37th IEEE real-time systems symposium, pp 291\u2013302. IEEE","DOI":"10.1109\/RTSS.2016.036"},{"key":"9328_CR10","doi-asserted-by":"crossref","unstructured":"Block A, Leontyev H, Brandenburg B, Anderson J (2007) A flexible real-time locking protocol for multiprocessors. In: Proceedings of the 13th IEEE international conference on embedded and real-time computing systems and applications, pp 71\u201380. IEEE","DOI":"10.1109\/RTCSA.2007.8"},{"key":"9328_CR11","unstructured":"Brandenburg B (2011) Scheduling and locking in multiprocessor real-time operating systems. Ph.D. thesis, University of North Carolina, Chapel Hill, NC"},{"key":"9328_CR12","doi-asserted-by":"crossref","unstructured":"Brandenburg B (2014) The FMLP+: an asymptotically optimal real-time locking protocol for suspension-aware analysis. In: Proceedings of the 26th euromicro conference on real-time systems, pp 61\u201371. IEEE","DOI":"10.1109\/ECRTS.2014.26"},{"key":"9328_CR13","unstructured":"Brandenburg B, Anderson J (2007) Feather-trace: a lightweight event tracing toolkit. In: Proceedings of the 3rd international workshop on operating systems platforms for embedded real-time applications, pp 19\u201328"},{"key":"9328_CR14","doi-asserted-by":"crossref","unstructured":"Brandenburg B, Anderson J (2008) A comparison of the M-PCP, D-PCP, and FMLP on LITMUS$$^{{\\text{RT}}}$$. In: Proceedings of the 12th international conference on principles of distributed systems, pp 105\u2013124. Springer","DOI":"10.1007\/978-3-540-92221-6_9"},{"key":"9328_CR15","doi-asserted-by":"crossref","unstructured":"Brandenburg B, Anderson J (2008) An implementation of the PCP, SRP, D-PCP, M-PCP, and FMLP real-time synchronization protocols in LITMUS$$^{{\\text{ RT }}}$$. In: Proceedings of the 14th IEEE international conference on embedded and real-time computing systems and applications, pp 185\u2013194. IEEE","DOI":"10.1109\/RTCSA.2008.13"},{"issue":"1","key":"9328_CR16","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s11241-010-9097-2","volume":"46","author":"B Brandenburg","year":"2010","unstructured":"Brandenburg B, Anderson J (2010) Spin-based reader-writer synchronization for multiprocessor real-time systems. Real-Time Syst 46(1):25\u201387","journal-title":"Real-Time Syst"},{"key":"9328_CR17","doi-asserted-by":"crossref","unstructured":"Brandenburg B, Anderson J (2011) Real-time resource-sharing under clustered scheduling: mutex, reader-writer, and $$k$$-exclusion locks. In: Proceedings of the 9th ACM international conference on embedded software, pp 69\u201378. ACM","DOI":"10.1145\/2038642.2038655"},{"issue":"2","key":"9328_CR18","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10617-012-9090-1","volume":"17","author":"B Brandenburg","year":"2013","unstructured":"Brandenburg B, Anderson J (2013) The OMLP family of optimal multiprocessor real-time locking protocols. Des Autom Embed Syst 17(2):277\u2013342","journal-title":"Des Autom Embed Syst"},{"key":"9328_CR19","doi-asserted-by":"crossref","unstructured":"Burns A, Wellings A (2013) A schedulability compatible multiprocessor resource sharing protocol\u2014MrsP. In: Proceedings of the 25th euromicro conference on real-time systems, pp 282\u2013291. IEEE","DOI":"10.1109\/ECRTS.2013.37"},{"key":"9328_CR20","unstructured":"Chang Y, Davis R, Wellings A (2010) Reducing queue lock pessimism in multiprocessor schedulability analysis. In: Proceedings of the 18th international conference on real-time and network systems, pp 99\u2013108"},{"key":"9328_CR21","unstructured":"Chen C, Tripathi S (1994) Multiprocessor priority ceiling based protocols. Tech. Rep. CS-TR-3252, University of Maryland"},{"issue":"10","key":"9328_CR22","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1145\/362759.362813","volume":"14","author":"P Courtois","year":"1971","unstructured":"Courtois P, Heymans F, Parnas D (1971) Concurrent control with readers and writers. Commun ACM 14(10):667\u2013668","journal-title":"Commun ACM"},{"key":"9328_CR23","unstructured":"Dijkstra E (1978) Two starvation free solutions to a general exclusion problem. EWD 625, Plataanstraat 5, 5671 Al Nuenen, The Netherlands"},{"issue":"2","key":"9328_CR24","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/s11241-012-9170-0","volume":"49","author":"G Elliott","year":"2013","unstructured":"Elliott G, Anderson J (2013) An optimal k-exclusion real-time locking protocol motivated by multi-GPU systems. Real-Time Syst 49(2):140\u2013170","journal-title":"Real-Time Syst"},{"key":"9328_CR25","doi-asserted-by":"crossref","unstructured":"Faggioli D, Lipari G, Cucinotta T (2010) The multiprocessor bandwidth inheritance protocol. In: Proceedings of the 22nd euromicro conference on real-time systems, pp 90\u201399. IEEE","DOI":"10.1109\/ECRTS.2010.19"},{"issue":"6","key":"9328_CR26","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/s11241-012-9162-0","volume":"48","author":"D Faggioli","year":"2012","unstructured":"Faggioli D, Lipari G, Cucinotta T (2012) Analysis and implementation of the multiprocessor bandwidth inheritance protocol. Real-Time Syst 48(6):789\u2013825","journal-title":"Real-Time Syst"},{"key":"9328_CR27","unstructured":"Gai P, Di\u00a0Natale M, Lipari G, Ferrari A, Gabellini C, Marceca P (2003) A comparison of MPCP and MSRP when sharing resources in the Janus multiple-processor on a chip platform. In: Proceedings of the 9th IEEE real-time and embedded technology and applications symposium, pp 189\u2013198. IEEE"},{"key":"9328_CR28","unstructured":"Gai P, Lipari G, Di\u00a0Natale M (2001) Minimizing memory utilization of real-time task sets in single and multi-processor systems-on-a-chip. In: Proceedings of the 22nd IEEE real-time systems symposium, pp 73\u201383. IEEE"},{"key":"9328_CR29","doi-asserted-by":"crossref","unstructured":"Garrido J, Zhao S, Burns A, Wellings A (2017) Supporting nested resources in MrsP. In: Proceedings of the Ada-Europe international conference on reliable software technologies, pp 73\u201386. Springer","DOI":"10.1007\/978-3-319-60588-3_5"},{"issue":"2","key":"9328_CR30","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1147\/sj.72.0074","volume":"7","author":"J Havender","year":"1968","unstructured":"Havender J (1968) Avoiding deadlock in multitasking systems. IBM Syst J 7(2):74\u201384","journal-title":"IBM Syst J"},{"issue":"3","key":"9328_CR31","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M Herlihy","year":"1990","unstructured":"Herlihy M, Wing J (1990) Linearizability: a correctness condition for concurrent objects. ACM Trans Progr Lang Syst 12(3):463\u2013492","journal-title":"ACM Trans Progr Lang Syst"},{"key":"9328_CR32","unstructured":"Huang H, Pillai P, Shin K (2002) Improving wait-free algorithms for interprocess communication in embedded real-time systems. In: Proceedings of the general track of the annual conference on USENIX annual technical conference, pp 303\u2013316. USENIX Association"},{"key":"9328_CR33","doi-asserted-by":"crossref","unstructured":"Jarrett C, Ward B, Anderson J (2015) A contention-sensitive fine-grained locking protocol for multiprocessor real-time systems. In: Proceedings of the 23rd international conference on real-time networks and systems, pp 3\u201312. ACM","DOI":"10.1145\/2834848.2834874"},{"issue":"4","key":"9328_CR34","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/PL00008918","volume":"13","author":"Y Joung","year":"2000","unstructured":"Joung Y (2000) Asynchronous group mutual exclusion. Distrib Comput 13(4):189\u2013206","journal-title":"Distrib Comput"},{"key":"9328_CR35","doi-asserted-by":"crossref","unstructured":"Keane P, Moir M (1999) A simple local-spin group mutual exclusion algorithm. In: Proceedings of the 18th annual ACM symposium on principles of distributed computing, pp 23\u201332. ACM","DOI":"10.1145\/301308.301319"},{"key":"9328_CR36","doi-asserted-by":"crossref","unstructured":"Lakshmanan K, Niz D, Rajkumar R (2009) Coordinated task scheduling, allocation and synchronization on multiprocessors. In: Proceedings of the 30th IEEE real-time systems symposium, pp 469\u2013478. IEEE","DOI":"10.1109\/RTSS.2009.51"},{"issue":"1","key":"9328_CR37","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1145\/103727.103729","volume":"9","author":"J Mellor-Crummey","year":"1991","unstructured":"Mellor-Crummey J, Scott M (1991) Algorithms for scalable synchronization on shared-memory multiprocessors. ACM Trans Comput Syst 9(1):21\u201365","journal-title":"ACM Trans Comput Syst"},{"key":"9328_CR38","doi-asserted-by":"crossref","unstructured":"Nemati F, Behnam M, Nolte T (2011) Independently-developed real-time systems on multi-cores with shared resources. In: Proceedings of the 23rd euromicro conference on real-time systems, pp 251\u2013261. IEEE","DOI":"10.1109\/ECRTS.2011.31"},{"key":"9328_CR39","doi-asserted-by":"crossref","unstructured":"Nemitz C, Amert T, Anderson J (2017) Real-time multiprocessor locks with nesting: optimizing the common case. In: Proceedings of the 25th international conference on real-time networks and systems, pp 38\u201347. ACM","DOI":"10.1145\/3139258.3139262"},{"key":"9328_CR40","unstructured":"Nemitz C, Amert T, Anderson J (2018) Using lock servers to scale real-time locking protocols: chasing ever-increasing core counts. In: Proceedings of the 30th euromicro conference on real-time systems, pp 25:1\u201325:24. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik"},{"key":"9328_CR41","unstructured":"Rajkumar R (1990) Real-time synchronization protocols for shared memory multiprocessors. In: Proceedings of the 10th international conference on distributed computing systems, pp 116\u2013123. IEEE"},{"key":"9328_CR42","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4000-7","volume-title":"Synchronization in real-time systems: a priority inheritance approach","author":"R Rajkumar","year":"1991","unstructured":"Rajkumar R (1991) Synchronization in real-time systems: a priority inheritance approach. Kluwer Academic Publishers, Boston"},{"key":"9328_CR43","unstructured":"Rajkumar R, Sha L, Lehoczky J (1988) Real-time synchronization protocols for multiprocessors. In: Proceedings of the 9th IEEE real-time systems symposium, pp 259\u2013269. IEEE"},{"issue":"9","key":"9328_CR44","doi-asserted-by":"publisher","first-page":"1175","DOI":"10.1109\/12.57058","volume":"39","author":"L Sha","year":"1990","unstructured":"Sha L, Rajkumar R, Lehoczky JP (1990) Priority inheritance protocols: an approach to real-time synchronization. IEEE Trans Comput 39(9):1175\u20131185","journal-title":"IEEE Trans Comput"},{"key":"9328_CR45","unstructured":"SchedCAT: schedulability test collection and toolkit. \n                    http:\/\/www.mpi-sws.org\/bbb\/projects\/schedcat\n                    \n                  . Accessed 31 May 2018"},{"key":"9328_CR46","unstructured":"Takada H, Sakamura K (1995) Real-time scalability of nested spin locks. In: Proceedings of the 2nd IEEE international workshop on real-time computing systems and applications, pp 160\u2013167. IEEE"},{"key":"9328_CR47","unstructured":"Wang C, Takada H, Sakamura K (1996) Priority inheritance spin locks for multiprocessor real-time systems. In: Proceedings of the 2nd IEEE international symposium on parallel architectures, algorithms, and networks, pp 70\u201376. IEEE"},{"key":"9328_CR48","doi-asserted-by":"crossref","unstructured":"Ward B (2015) Relaxing resource-sharing constraints for improved hardware management and schedulability. In: Proceedings of the 36th IEEE real-time systems symposium, pp 153\u2013164. IEEE","DOI":"10.1109\/RTSS.2015.22"},{"key":"9328_CR49","unstructured":"Ward B (2016) Sharing non-processor resources in multiprocessor real-time systems. Ph.D. thesis, University of North Carolina, Chapel Hill, NC"},{"key":"9328_CR50","doi-asserted-by":"crossref","unstructured":"Ward B, Anderson J (2012) Supporting nested locking in multiprocessor real-time systems. In: Proceedings of the 23rd euromicro conference on real-time systems, pp 223\u2013232. IEEE","DOI":"10.1109\/ECRTS.2012.17"},{"key":"9328_CR51","doi-asserted-by":"crossref","unstructured":"Ward B, Anderson J (2013) Fine-grained multiprocessor real-time locking with improved blocking. In: Proceedings of the 21st international conference on real-time networks and systems, pp 67\u201376. ACM","DOI":"10.1145\/2516821.2516843"},{"key":"9328_CR52","doi-asserted-by":"crossref","unstructured":"Ward B, Anderson J (2014) Multi-resource real-time reader\/writer locks for multiprocessors. In: Proceedings of the 28th IEEE international parallel and distributed processing symposium, pp 177\u2013186. IEEE","DOI":"10.1109\/IPDPS.2014.29"},{"key":"9328_CR53","doi-asserted-by":"crossref","unstructured":"Ward B, Elliott G, Anderson J (2012) Replica-request priority donation: a real-time progress mechanism for global locking protocols. In: Proceedings of the 18th IEEE international conference on embedded and real-time computing systems and applications, pp 280\u2013289. IEEE","DOI":"10.1109\/RTCSA.2012.26"},{"key":"9328_CR54","doi-asserted-by":"crossref","unstructured":"Wieder A, Brandenburg B (2013) On spin locks in AUTOSAR: blocking analysis of FIFO, unordered, and priority-ordered spin locks. In: Proceedings of the 34th IEEE real-time systems symposium, pp 45\u201356. IEEE","DOI":"10.1109\/RTSS.2013.13"},{"key":"9328_CR55","doi-asserted-by":"crossref","unstructured":"Wieder A, Brandenburg B (2014) On the complexity of worst-case blocking analysis of nested critical sections. In: Proceedings of the 35th IEEE real-time systems symposium, pp 106\u2013117. IEEE","DOI":"10.1109\/RTSS.2014.34"},{"key":"9328_CR56","doi-asserted-by":"crossref","unstructured":"Yang M, Wieder A, Brandenburg B (2015) Global real-time semaphore protocols: a survey, unified analysis, and comparison. In: Proceedings of the 36th IEEE real-time systems symposium, pp 1\u201312. IEEE","DOI":"10.1109\/RTSS.2015.8"},{"key":"9328_CR57","doi-asserted-by":"crossref","unstructured":"Zhao S, Garrido J, Burns A, Wellings A (2017) New schedulability analysis for MrsP. In: Proceedings of the 23rd IEEE international conference on embedded and real-time computing systems and applications, pp 1\u201310. IEEE","DOI":"10.1109\/RTCSA.2017.8046311"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-019-09328-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11241-019-09328-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-019-09328-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T14:06:34Z","timestamp":1589724394000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11241-019-09328-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,3,13]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9328"],"URL":"https:\/\/doi.org\/10.1007\/s11241-019-09328-w","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"type":"print","value":"0922-6443"},{"type":"electronic","value":"1573-1383"}],"subject":[],"published":{"date-parts":[[2019,3,13]]},"assertion":[{"value":"13 March 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}