More Like this

1. Optimal Multiprocessor Locking Protocols under FIFO Scheduling

   Ahmed, Shareef; Anderson, James H. (July 2023, Proceedings of the 35th Euromicro Conference on Real-Time Systems)

   Real-time locking protocols are typically designed to reduce any priority-inversion blocking (pi9 blocking) a task may incur while waiting to access a shared resource. For the multiprocessor case, a number of such protocols have been developed that ensure asymptotically optimal pi-blocking bounds under job-level fxed-priority scheduling. Unfortunately, no optimal multiprocessor real-time locking protocols are known that ensure tight pi-blocking bounds under any scheduler. This paper presents the frst such protocols. Specifcally, protocols are presented for mutual exclusion, reader-writer synchronization, and k-exclusion that are optimal under frst-in-frst-out (FIFO) scheduling when schedulability analysis treats suspension times as computation. Experiments are presented that demonstrate the efectiveness of these protocols. 

   more » « less
2. Open Problem Resolved: The "Two" in Existing Multiprocessor PI-Blocking Bounds Is Fundamental

   https://doi.org/10.4230/LIPICS.ECRTS.2024.11  

   Ahmed, Shareef; Anderson, James H (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Pellizzoni, Rodolfo (Ed.)

   The goal of a real-time locking protocol is to reduce any priority-inversion blocking (pi-blocking) a task may incur while waiting to access a shared resource. For mutual-exclusion sharing on an m-processor platform, the best existing lower bound on per-task pi-blocking under suspension-oblivious analysis is a (trivial) lower bound of (m-1) request lengths under any job-level fixed-priority (JLFP) scheduler. Surprisingly, most asymptotically optimal locking protocols achieve a per-task pi-blocking upper bound of (2m-1) request lengths under JLFP scheduling, even though a range of very different mechanisms are used in these protocols. This paper closes the gap between these existing lower and upper bounds by establishing a lower bound of (2m-2) request lengths under global fixed-priority (G-FP) and global earliest-deadline-first (G-EDF) scheduling. This paper also shows that worst-case per-task pi-blocking can be arbitrarily close to (2m-1) request lengths for locking protocols that satisfy a certain property that is met by most (if not all) existing locking protocols. These results imply that most known asymptotically optimal locking protocols are almost truly optimal (not just asymptotic) under G-FP and G-EDF scheduling. 

   more » « less
3. Real-Time Multiprocessor Locks with Nesting: Optimizing the Common Case

   Nemitz, C; Amert, T; Anderson, J (April 2019, Real-Time Systems, special issue of outstanding papers from the 25th International Conference on Real-Time Networks and Systems (RTNS 2017))

   In prior work on multiprocessor real-time locking protocols, only protocols within the RNLP family support unrestricted lock nesting while guaranteeing asymptotically optimal priority-inversion blocking bounds. However, these protocols support nesting at the expense of increasing the cost of processing non-nested lock requests, which tend to be the common case in practice. To remedy this situation, a newfast-path mechanism is presented herein that extends prior RNLP variants by ensuring that non-nested requests are processed efficiently. This mechanism yields overhead and blocking costs for such requests that are nearly identical to those seen in the most efficient single-resource locking protocols. In experiments, the proposed fast-path mechanism enabled observed blocking times for non-nested requests that were up to 17 times lower than under an existing RNLP variant. 

   more » « less
4. Concurrency groups: a new way to look at real-time multiprocessor lock nesting

   https://doi.org/10.1145/3356401.3356404  

   Nemitz, Catherine E.; Amert, Tanya; Goyal, Manish; Anderson, James H. (November 2019, Proceedings of the 27th International Conference on Real-Time Networks and Systems)

   When designing a real-time multiprocessor locking protocol, the allowance of lock nesting creates complications that can kill parallelism. Such protocols are typically designed by focusing on the arbitration of resource requests that should be prohibited from executing concurrently. This paper proposes "concurrency groups," a new concept that reflects an alternative point of view that focuses instead on requests that can be allowed to execute concurrently. A concurrency group is simply a group of lock requests, determined offline, that can safely execute together. This paper's main contribution is the CGLP, a new real-time multiprocessor locking protocol that supports lock nesting through the use of concurrency groups. The CGLP is able to reap runtime parallelism benefits that have eluded prior protocols by investing effort offline in the construction of concurrency groups. A schedulability study is presented to quantify these benefits, as well as an efficient approach to determining such groups using an Integer Linear Program (ILP) solver. 

   more » « less
5. Concurrency Groups: A New Way to Look at Real-Time Multiprocessor Lock Nesting

   Nemitz, Catherine E; Amert, Tanya; Goyal, Manish; Anderson, James H (November 2019, Proceedings of the 27th International Conference on Real-Time Networks and Systems)

   When designing a real-time multiprocessor locking protocol, the allowance of lock nesting creates complications that can kill parallelism. Such protocols are typically designed by focusing on the arbitration of resource requests that should be prohibited from executing concurrently. This paper proposes “concurrency groups,” a new concept that reflects an alternative point of view that focuses instead on requests that can be allowed to execute concurrently. A concurrency group is simply a group of lock requests, determined offline, that can safely execute together. This paper’s main contribution is the CGLP, a new real-time multiprocessor locking protocol that supports lock nesting through the use of concurrency groups. The CGLP is able to reap runtime parallelism benefits that have eluded prior protocols by investing effort offline in the construction of concurrency groups. A schedulability study is presented to quantify these benefits, as well as an efficient approach to determining such groups using an Integer Linear Program (ILP) solver. 

   more » « less