More Like this

1. Leibniz International Proceedings in Informatics (LIPIcs):35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

   https://doi.org/10.4230/LIPIcs.ECRTS.2023.16  

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

   Papadopoulos, Alessandro V. (Ed.)

   Real-time locking protocols are typically designed to reduce any priority-inversion blocking (pi-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 fixed-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 first such protocols. Specifically, protocols are presented for mutual exclusion, reader-writer synchronization, and k-exclusion that are optimal under first-in-first-out (FIFO) scheduling when schedulability analysis treats suspension times as computation. Experiments are presented that demonstrate the effectiveness of these protocols. 

   more » « less
2. 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
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. Tardiness Bounds for Fixed-Priority Global Scheduling without Intra-Task Precedence Constraints

   Voronov, Sergey; Anderson, James H; Yang, Kecheng (October 2018, Proceedings of the 26th International Conference on Real-Time Networks and Systems)

   Fixed-priority multicore schedulers are often preferable to dynamic-priority ones because they entail less overhead, are easier to im-plement, and enable certain tasks to be favored over others. Underglobal fixed-priority (G-FP) scheduling, as applied to the standardsporadic task model, response times for low-priority tasks may beunbounded, even if total task-system utilization is low. In this paper,it is shown that this negative result can be circumvented if differentjobs of the same task are allowed to execute in parallel. In particu-lar, a response-time bound is presented for task systems that allowintra-task parallelism. This bound merely requires that total utiliza-tion does not exceed the overall processing capacity—individualtask utilizations need not be further restricted. This result impliesthat G-FP is optimal for scheduling soft real-time tasks that requirebounded tardiness, if intra-task parallelism is allowed 

   more » « less
5. Reducing Response-Time Bounds via Global Fixed Preemption Point EDF-like Scheduling

   Goh, Joseph; Anderson, J. H. (August 2023, Proceedings of the 29th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications)

   The fixed preemption point (FPP) model has been studied as an alternative to fully preemptive and non-preemptive models, as restricting preemptions to specific, predictable locations within a task’s execution can simplify overhead analysis without disallowing preemptions entirely. Prior work has produced response-time analyses for global Earliest Deadline First (G-EDF) scheduling under the FPP model. However, scheduling decisions based solely on task deadlines may be too coarsegrained and may not lead to the lowest response times. In this paper, we propose global FPP EDF-like (G-FPP-EL) scheduling, which assigns a priority point in time for each non-preemptive region of a task. We adapt compliant-vector analysis (CVA) to our model and present general response-time bounds for G-FPPEL schedulers. We then demonstrate that it is possible to design G-FPP-EL schedulers acheiving response-time bounds optimal under CVA and argue that such schedulers should replace global FPP EDF. 

   more » « less