{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:50:17Z","timestamp":1740124217751,"version":"3.37.3"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T00:00:00Z","timestamp":1612483200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T00:00:00Z","timestamp":1612483200000},"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","CNS 1563845"],"award-info":[{"award-number":["CNS 1409175","CNS 1563845"]}],"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 1717589","CPS 1837337"],"award-info":[{"award-number":["CNS 1717589","CPS 1837337"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-17-1-0294"],"award-info":[{"award-number":["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"}]},{"DOI":"10.13039\/100007890","name":"University of North Carolina at Chapel Hill","doi-asserted-by":"publisher","award":["Dissertation Completion Fellowship"],"award-info":[{"award-number":["Dissertation Completion Fellowship"]}],"id":[{"id":"10.13039\/100007890","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":[[2021,4]]},"DOI":"10.1007\/s11241-020-09361-0","type":"journal-article","created":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T13:21:54Z","timestamp":1612531314000},"page":"190-226","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Concurrency groups: a new way to look at real-time multiprocessor lock nesting"],"prefix":"10.1007","volume":"57","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5800-3533","authenticated-orcid":false,"given":"Catherine E.","family":"Nemitz","sequence":"first","affiliation":[]},{"given":"Tanya","family":"Amert","sequence":"additional","affiliation":[]},{"given":"Manish","family":"Goyal","sequence":"additional","affiliation":[]},{"given":"James H.","family":"Anderson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,5]]},"reference":[{"key":"9361_CR1","unstructured":"AUTOSAR Release 4.4 (2019) Classic platform, specification of operating system. https:\/\/www.autosar.org\/. Accessed 20 May 2019"},{"key":"9361_CR3","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","DOI":"10.1109\/SIES.2014.6871185"},{"key":"9361_CR4","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","DOI":"10.1109\/RTCSA.2017.8046310"},{"key":"9361_CR5","doi-asserted-by":"publisher","DOI":"10.4230\/LITES-v004-i002-a003","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 https:\/\/doi.org\/10.4230\/LITES-v004-i002-a003","journal-title":"Leibniz Trans Embed Syst"},{"key":"9361_CR6","doi-asserted-by":"crossref","unstructured":"Afshar S, Behnam M, Nolte T (2013) Integrating independently developed real-time applications on a shared multi-core architecture. ACM SIGBED Review\u201913","DOI":"10.1145\/2544350.2544356"},{"key":"9361_CR7","doi-asserted-by":"crossref","unstructured":"Afshar S, Khalilzad N, Nemati F, Nolte T (2015) Resource sharing among prioritized real-time applications on multiprocessors. ACM SIGBED Review\u201915","DOI":"10.1145\/2752801.2752807"},{"key":"9361_CR8","doi-asserted-by":"crossref","unstructured":"Bacon D, Konuru R, Murthy C, Serrano M (1998) Thin locks: featherweight synchronization for Java. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation","DOI":"10.1145\/277650.277734"},{"key":"9361_CR9","doi-asserted-by":"crossref","unstructured":"Bandh T, Carle G, Sanneck H (2009) Graph coloring based physical-cell-id assignment for LTE networks. In: Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly","DOI":"10.1145\/1582379.1582406"},{"issue":"1\u20134","key":"9361_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1023\/B:ANOR.0000032574.01332.98","volume":"130","author":"N Barnier","year":"2004","unstructured":"Barnier N, Brisset P (2004) Graph coloring for air traffic flow management. Ann Oper Res 130(1\u20134):163\u2013178","journal-title":"Ann Oper Res"},{"key":"9361_CR11","doi-asserted-by":"crossref","unstructured":"Baruah S (2007) Techniques for multiprocessor global schedulability analysis. In: Proceedings of the 28th IEEE Real-Time Systems Symposium","DOI":"10.1109\/RTSS.2007.35"},{"key":"9361_CR12","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","DOI":"10.1109\/RTSS.2016.036"},{"key":"9361_CR13","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","DOI":"10.1109\/RTCSA.2007.8"},{"key":"9361_CR14","unstructured":"Brandenburg B (2011) Scheduling and locking in multiprocessor real-time operating systems. Ph.D. thesis, University of North Carolina, Chapel Hill, NC"},{"key":"9361_CR15","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","DOI":"10.1109\/ECRTS.2014.26"},{"key":"9361_CR16","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"},{"key":"9361_CR17","doi-asserted-by":"crossref","unstructured":"Brandenburg B, Anderson J (2008a) A comparison of the M-PCP, D-PCP, and FMLP on $$\\text{LITMUS}^{{{\\rm RT}}}$$. In: Proceedings of the 12th International Conference on Principles of Distributed Systems","DOI":"10.1007\/978-3-540-92221-6_9"},{"key":"9361_CR18","doi-asserted-by":"crossref","unstructured":"Brandenburg B, Anderson J (2008b) An implementation of the PCP, SRP, D-PCP, M-PCP, and FMLP real-time synchronization protocols in $$\\text{ LITMUS}^{{{\\rm RT}}}$$. In:\u00a0Proceedings of the 14th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications","DOI":"10.1109\/RTCSA.2008.13"},{"issue":"1","key":"9361_CR19","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":"9361_CR20","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","DOI":"10.1145\/2038642.2038655"},{"issue":"2","key":"9361_CR21","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. Design Autom Embed Syst 17(2):277\u2013342","journal-title":"Design Autom Embed Syst"},{"key":"9361_CR22","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","DOI":"10.1109\/ECRTS.2013.37"},{"issue":"1","key":"9361_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0096-0551(81)90048-5","volume":"6","author":"G Chaitin","year":"1981","unstructured":"Chaitin G, Auslander M, Chandra A, Cocke J, Hopkins M, Markstein P (1981) Register allocation via coloring. Comput Lang 6(1):45\u201357","journal-title":"Comput Lang"},{"key":"9361_CR24","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"},{"key":"9361_CR25","unstructured":"Chen C, Tripathi S (1994) Multiprocessor priority ceiling based protocols. Department of Computer Science, University of Maryland. Technical Report, CS-TR-3252, April"},{"key":"9361_CR26","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":"9361_CR27","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":"9361_CR28","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","DOI":"10.1109\/ECRTS.2010.19"},{"issue":"6","key":"9361_CR29","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":"9361_CR30","unstructured":"Gai P, Di Natale 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"},{"key":"9361_CR31","unstructured":"Gai P, Lipari G, Di Natale 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"},{"key":"9361_CR32","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","DOI":"10.1007\/978-3-319-60588-3_5"},{"key":"9361_CR33","unstructured":"Gurobi Optimization, L.: Gurobi optimizer reference manual (2018). http:\/\/www.gurobi.com"},{"issue":"2","key":"9361_CR34","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"},{"key":"9361_CR35","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","DOI":"10.1145\/2834848.2834874"},{"key":"9361_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","DOI":"10.1109\/RTSS.2009.51"},{"issue":"1\u20132","key":"9361_CR37","first-page":"11","volume":"48","author":"D Marx","year":"2004","unstructured":"Marx D (2004) Graph colouring problems and their applications in scheduling. Period Polytech Electr Eng 48(1\u20132):11\u201316","journal-title":"Period Polytech Electr Eng"},{"issue":"1","key":"9361_CR38","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 of shared-memory multiprocessors. Trans Comput Syst 9(1):21\u201365","journal-title":"Trans Comput Syst"},{"key":"9361_CR39","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","DOI":"10.1109\/ECRTS.2011.31"},{"key":"9361_CR40","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","DOI":"10.1145\/3139258.3139262"},{"key":"9361_CR41","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"},{"issue":"2","key":"9361_CR42","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1007\/s11241-019-09328-w","volume":"55","author":"C Nemitz","year":"2019","unstructured":"Nemitz C, Amert T, Anderson J (2019a) Real-time multiprocessor locks with nesting: optimizing the common case. Real-Time Syst 55(2):296","journal-title":"Real-Time Systems"},{"key":"9361_CR43","doi-asserted-by":"crossref","unstructured":"Nemitz C, Amert T, Goyal M, Anderson J (2019b) Concurrency groups: a new way to look at real-time multiprocessor lock nesting. In: Proceedings of the 27th International Conference on Real-Time Networks and Systems","DOI":"10.1145\/3356401.3356404"},{"key":"9361_CR44","doi-asserted-by":"crossref","unstructured":"Nemitz C, Amert T, Goyal M, Anderson J (2021) Concurrency groups: a new way to look at real-time multiprocessor lock nesting (extended version). http:\/\/www.cs.unc.edu\/~anderson\/papers.html","DOI":"10.1007\/s11241-020-09361-0"},{"key":"9361_CR45","unstructured":"Palladino S (2010) Modelling graph coloring with integer linear programming. https:\/\/manas.tech\/blog\/2010\/09\/16\/modelling-graph-coloring-with-integer-linear-programming.html"},{"key":"9361_CR46","unstructured":"Rajkumar R (1990) Real-time synchronization protocols for shared memory multiprocessors. In: Proceedings of the 10th International Conference on Distributed Computing Systems"},{"key":"9361_CR47","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 Press, Reading, MA"},{"key":"9361_CR48","unstructured":"Rajkumar R, Sha L, Lehoczky J (1988) Real-time synchronization protocols for multiprocessors. In: Proceedings of the 9th IEEE Real-Time Systems Symposium"},{"key":"9361_CR2","unstructured":"SchedCAT: Schedulability test collection and toolkit (2019). https:\/\/github.com\/brandenburg\/schedcat Accessed 02 July 2019"},{"key":"9361_CR49","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"},{"key":"9361_CR50","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"},{"key":"9361_CR51","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","DOI":"10.1109\/RTSS.2015.22"},{"key":"9361_CR52","unstructured":"Ward B (2016) Sharing non-processor resources in multiprocessor real-time systems. Ph.D. thesis, University of North Carolina, Chapel Hill, NC"},{"key":"9361_CR53","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","DOI":"10.1109\/ECRTS.2012.17"},{"key":"9361_CR54","doi-asserted-by":"crossref","unstructured":"Ward B, Anderson J (2013) Fine-grained multiprocessor real-time locking with improved blocking. In:\u00a0Proceedings of the 21st International Conference on Real-Time Networks and Systems","DOI":"10.1145\/2516821.2516843"},{"key":"9361_CR55","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","DOI":"10.1109\/IPDPS.2014.29"},{"key":"9361_CR56","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","DOI":"10.1109\/RTCSA.2012.26"},{"key":"9361_CR57","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:\u00a0Proceedings of the 34th IEEE Real-Time Systems Symposium","DOI":"10.1109\/RTSS.2013.13"},{"key":"9361_CR58","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","DOI":"10.1109\/RTSS.2014.34"},{"key":"9361_CR59","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","DOI":"10.1109\/RTSS.2015.8"},{"key":"9361_CR60","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","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-020-09361-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11241-020-09361-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-020-09361-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,21]],"date-time":"2021-03-21T15:07:31Z","timestamp":1616339251000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11241-020-09361-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,5]]},"references-count":60,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["9361"],"URL":"https:\/\/doi.org\/10.1007\/s11241-020-09361-0","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"type":"print","value":"0922-6443"},{"type":"electronic","value":"1573-1383"}],"subject":[],"published":{"date-parts":[[2021,2,5]]},"assertion":[{"value":"8 December 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}