pith. sign in

arxiv: 2605.27620 · v1 · pith:QHJLYJ5Cnew · submitted 2026-05-26 · 💻 cs.OS

Bounded Priority-Aware Locking for Real-Time Kernels

Shriram Raja , Richard West This is my paper

Pith reviewed 2026-06-29 13:57 UTC · model grok-4.3

classification 💻 cs.OS
keywords real-time systemsspinlockspriority-aware lockingmulticore kernelsbounded waiting timebatched priority lockRTOS synchronization
0
0 comments X

The pith

Batched Priority Lock groups tasks by request order then grants to the highest priority within each group.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the Batched Priority Lock to let real-time systems favor higher-priority tasks when accessing shared kernel resources without losing the predictability of bounded waiting times. Standard FIFO locks treat all tasks equally in arrival order, while strict priority can starve low-priority ones indefinitely. BPL batches waiting tasks in arrival groups and selects the top priority inside each batch. This matters because multicore real-time kernels need both worst-case guarantees and reasonable performance for critical tasks. Simulations and an 8-core implementation show reduced average delays for high-priority tasks at the cost of modest added complexity.

Core claim

BPL first groups waiting tasks based on the order of their lock requests, and then determines the next lock holder according to priority within the waiting group. This approach achieves the same waiting bound as FIFO locks while reducing average waiting time for higher priority tasks.

What carries the argument

The Batched Priority Lock mechanism that batches lock requests by arrival order and selects the highest-priority waiter inside each batch.

If this is right

  • BPL maintains the same worst-case lock waiting bound as FIFO ordering.
  • Higher priority tasks experience lower average waiting times than under FIFO.
  • Unlike strict priority locking, BPL prevents starvation and unbounded delays.
  • The common-case overhead remains low enough for use in an 8-core real-time operating system.
  • Performance holds in simulations scaling to 64 cores.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar batching could apply to other synchronization primitives beyond spinlocks.
  • The approach may improve overall system schedulability by reducing interference on high-priority tasks.
  • Implementation details like batch size limits could be tuned for specific hardware.

Load-bearing premise

Selecting the highest-priority task within each arrival batch can be performed without introducing additional synchronization delays that break the real-time timing model.

What would settle it

An experiment measuring worst-case lock acquisition latency under heavy contention on a multicore platform where BPL exceeds the FIFO bound.

Figures

Figures reproduced from arXiv: 2605.27620 by Richard West, Shriram Raja.

Figure 1
Figure 1. Figure 1: Example of Global Priority Inversion in Multicore Real-Time Systems [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Scheduler Paths in Quest RTOS and control is switched to the next task in the chosen VCPU. Finally, the kernel lock is released and interrupts are re-enabled as control passes to the user-space. User Task to Kernel Task (Figure 2b): Similar to the previous case, the user task is interrupted, leading to control passing to the LAPIC timer handler. The only difference is, in this case the VCPU chosen to run n… view at source ↗
Figure 3
Figure 3. Figure 3: System Model System Model: Given the aforementioned design requirements, we arrive at the system model shown in [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Batched Priority Locking (BPL) Algorithm Example [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Machine Repairman Queue Model with 𝑚 Sources J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018 [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Comparison of Priority Inversions and Weighted Mean Delay for 64 Cores [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Cost of Uncontested Lock Acquisition J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018 [PITH_FULL_IMAGE:figures/full_fig_p018_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Comparison of Lock Performance for 8 Cores on an RTOS [PITH_FULL_IMAGE:figures/full_fig_p019_8.png] view at source ↗
read the original abstract

A real-time multicore system requires delay bounds on access to shared resources. These resources include the kernel, which has potentially many non-preemptible critical sections guarded by one or more different synchronization primitives. While primitives such as FIFO locks bound the waiting time to enter a critical section, they do not distinguish the importance of individual tasks competing for shared resource access. To address this, we consider a priority-aware spinlock, which reduces the average delay of more important tasks while maintaining a worst-case bound on lock waiting time. We propose a Batched Priority Lock (BPL) that first groups waiting tasks based on the order of their lock requests, and then determines the next lock holder according to priority within the waiting group. We compare BPL to alternative lock approaches, showing that the average waiting time is reduced for higher priority tasks, in simulations up to 64 cores, and for a working implementation on an 8-core machine with a real RTOS. BPL is a compromise between strict priority and FIFO ordering. While strict priorities may lead to starvation and, hence, unbounded lock acquisition delays, BPL has the same waiting bound as FIFO, but with benefits to higher priority tasks. Although its complexity is greater than that of a simple spinlock, its common case execution overhead is shown to be inexpensive in a working system. We believe this is an acceptable cost in systems that require predictability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper proposes the Batched Priority Lock (BPL), a spinlock that groups waiting tasks by arrival order and then grants the lock to the highest-priority task within each group. It claims this yields the same worst-case waiting bound as FIFO locks while reducing average delay for higher-priority tasks, supported by simulations on up to 64 cores and an 8-core implementation on a real RTOS.

Significance. If the batch-internal priority selection can be realized without introducing synchronization delays beyond those of a plain FIFO lock, BPL would offer a practical middle ground between strict priority (risking starvation) and FIFO for real-time kernels. The empirical evaluation on real hardware is a concrete strength; however, the absence of a formal bound derivation or detailed timing analysis for the selection step limits the result's immediate applicability to certified real-time systems.

major comments (2)
  1. [Abstract] Abstract (BPL definition paragraph): the claim that BPL 'has the same waiting bound as FIFO' rests on the unstated assumption that selecting the highest-priority waiter inside an arrival-order batch can be performed with bounded, contention-free latency; no data structures, atomic primitives, or critical-section timing analysis are supplied to substantiate this.
  2. [Abstract] Abstract (simulation and implementation claims): the bounded-wait result is asserted on the basis of simulations to 64 cores and an 8-core RTOS implementation, yet no error bars, outlier exclusion criteria, or worst-case measurement methodology are described, leaving the central empirical support for the FIFO-equivalent bound unexamined.
minor comments (1)
  1. [Abstract] The abstract refers to 'common case execution overhead' without quantifying it relative to a baseline FIFO spinlock or stating the measurement conditions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful and constructive report. We address each major comment below and will make the requested revisions to improve the clarity and rigor of the presentation.

read point-by-point responses

  1. Referee: [Abstract] Abstract (BPL definition paragraph): the claim that BPL 'has the same waiting bound as FIFO' rests on the unstated assumption that selecting the highest-priority waiter inside an arrival-order batch can be performed with bounded, contention-free latency; no data structures, atomic primitives, or critical-section timing analysis are supplied to substantiate this.

    Authors: We agree that the abstract (and the manuscript) does not supply the requested implementation details or timing analysis to substantiate the bounded-latency claim for intra-batch selection. The current text simply asserts the FIFO-equivalent bound without describing the data structures or primitives. We will revise the paper to include a description of the queue and selection mechanism together with a timing analysis demonstrating that the selection step executes with bounded, contention-free latency that does not increase the worst-case waiting bound beyond that of FIFO. revision: yes

  2. Referee: [Abstract] Abstract (simulation and implementation claims): the bounded-wait result is asserted on the basis of simulations to 64 cores and an 8-core RTOS implementation, yet no error bars, outlier exclusion criteria, or worst-case measurement methodology are described, leaving the central empirical support for the FIFO-equivalent bound unexamined.

    Authors: We acknowledge that the reported simulation and implementation results lack the methodological details needed to fully evaluate the bounded-wait claims. In the revised version we will add error bars to the simulation figures, describe the outlier exclusion criteria, and provide a clear account of the worst-case measurement methodology (including number of trials, workload generation, and how maximum observed waits were recorded). revision: yes

Circularity Check

0 steps flagged

No significant circularity; bound claim follows from explicit design definition

full rationale

The paper presents BPL as an algorithmic construction that batches waiters by arrival order then selects the highest-priority task inside each batch. The claim that this yields the same worst-case waiting bound as FIFO is a direct consequence of the batching rule (which preserves arrival-order progress) rather than any fitted parameter, self-citation chain, or equation that reduces the bound to its own inputs. No equations, uniqueness theorems, or prior-author citations are invoked to derive the bound; the result is self-contained against the stated mechanism. The implementation assumption about selection latency is a correctness concern, not a circularity in the derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The contribution rests on standard real-time systems assumptions rather than fitted parameters or newly postulated physical entities.

axioms (2)
  • domain assumption Real-time tasks possess static or known priorities that the lock can inspect at acquisition time.
    Required for the priority selection step inside each batch.
  • domain assumption The kernel critical sections are short and non-preemptible, so lock contention is the dominant source of delay.
    Underpins the claim that bounding lock wait time directly improves predictability.
invented entities (1)
  • Batched Priority Lock (BPL) no independent evidence
    purpose: A synchronization primitive that enforces arrival-order batching followed by intra-batch priority selection.
    Newly defined mechanism whose properties are the central contribution of the paper.

pith-pipeline@v0.9.1-grok · 5774 in / 1358 out tokens · 40422 ms · 2026-06-29T13:57:58.127771+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

30 extracted references · 21 canonical work pages

  1. [1]

    Bril, and Thomas Nolte

    Sara Afshar, Moris Behnam, Reinder J. Bril, and Thomas Nolte. 2017. An Optimal Spin-Lock Priority Assignment Algorithm for Real-Time Multi-core Systems. In 2017 IEEE 23rd International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) . IEEE, USA, 1–11. doi:10.1109/RTCSA.2017.8046310

    work page doi:10.1109/rtcsa.2017.8046310 2017

  2. [2]

    Brandenburg

    Björn B. Brandenburg. 2020. Multiprocessor Real-Time Locking Protocols. Springer Singapore, Singapore, 1–99. doi:10. 1007/978-981-4585-87-3_10-1

    2020

  3. [3]

    Brandenburg and James H

    Björn B. Brandenburg and James H. Anderson. 2010. Optimality Results for Multiprocessor Real-Time Locking. In 2010 31st IEEE Real-Time Systems Symposium . IEEE, USA, 49–60. doi:10.1109/RTSS.2010.17

    work page doi:10.1109/rtss.2010.17 2010

  4. [4]

    Cincoze. [n. d.]. DX-1100 PC, Cincoze. https://www.cincoze.com/goods_info.php?id=286

  5. [5]

    SimPy Contributors. [n. d.]. https://simpy.readthedocs.io/

  6. [6]

    Jonathan Corbet. 2014. MCS locks and qspinlocks. https://lwn.net/Articles/590243/

    2014

  7. [7]

    Travis S. Craig. 1993. Queuing Spin lock Algorithms to Support Timing Predictability. In 1993 Proceedings Real-Time Systems Symposium (RTSS ’93) . IEEE, USA, 148–157. doi:10.1109/REAL.1993.393505

    work page doi:10.1109/real.1993.393505 1993

  8. [8]

    Matthew Danish, Ye Li, and Richard West. 2011. Virtual-CPU Scheduling in the Quest Operating System. In2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS ’11) . IEEE, USA, 169–179. doi:10.1109/ RTAS.2011.24

    2011

  9. [9]

    Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2013. Everything You Always Wanted to Know About Syn- chronization but Were Afraid to Ask. In2013 24th ACM Symposium on Operating Systems Principles (SOSP). Association for Computing Machinery, New York, NY, USA, 33–48. doi:10.1145/2517349.2522714

    work page doi:10.1145/2517349.2522714 2013

  10. [10]

    Steven Fuerst. 2011. Priority Spin Locks. https://locklessinc.com/articles/priority_locks/

    2011

  11. [11]

    2008.Concurrency at Microsoft - An Exploratory Survey

    Patrice Godefroid and Nachi Nagappan. 2008.Concurrency at Microsoft - An Exploratory Survey. Technical Report MSR- TR-2008-75. Microsoft. 4 pages. https://www.microsoft.com/en-us/research/publication/concurrency-at-microsoft- an-exploratory-survey/

    2008

  12. [12]

    Chien-Chung Huang and Prasad Jayanti. 2016. Priority Mutual Exclusion: Specification and Algorithm. InProceedings of the 30th International Symposium on Distributed Computing (DISC ’16) . Springer, Berlin, Heidelberg, 385–398

    2016

  13. [13]

    Prasad Jayanti. 2003. Adaptive and Efficient Abortable Mutual Exclusion. InProceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing (Boston, Massachusetts)(PODC ’03) . Association for Computing Machinery, New York, NY, USA, 295–304. doi:10.1145/872035.872079

    work page doi:10.1145/872035.872079 2003

  14. [14]

    Theodore Johnson and Krishna Harathi. 1997. A Prioritized Multiprocessor Spin Lock.IEEE Transactions on Parallel and Distributed Systems 8, 9 (1997), 926–933. doi:10.1109/71.615438

    work page doi:10.1109/71.615438 1997

  15. [15]

    David G. Kendall. 1953. Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain. The Annals of Mathematical Statistics 24, 3 (1953), 338 – 354. doi:10.1214/aoms/ 1177728975

    work page doi:10.1214/aoms/ 1953

  16. [16]

    Liu and James W

    Chung L. Liu and James W. Layland. 1973. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Envi- ronment. J. ACM 20, 1 (Jan 1973), 46–61. doi:10.1145/321738.321743

    work page doi:10.1145/321738.321743 1973

  17. [17]

    J. W. S. Liu, K. J. Lin, W. K. Shih, A. C. S. Yu, J. Y. Chung, and W. Zhao. 1991. Algorithms for Scheduling Imprecise Computations. Computer 24, 5 (May 1991), 58–68. doi:10.1109/2.76287

    work page doi:10.1109/2.76287 1991

  18. [18]

    Jane W. S. Liu, Wei Kuan Shih, Kwei-Jay Lin, Riccardo Bettati, and Jen-Yao Chung. 1994. Imprecise Computations. Proc. IEEE 82 (1994), 83–94. https://api.semanticscholar.org/CorpusID:267916812

    1994

  19. [19]

    Magnusson, Anders Landin, and Erik Hagersten

    Peter S. Magnusson, Anders Landin, and Erik Hagersten. 1994. Queue Locks on Cache Coherent Multiprocessors. In Proceedings of 8th International Parallel Processing Symposium (IPPS ’94) . IEEE, USA, 165–171. doi:10.1109/IPPS.1994. 288305

    work page doi:10.1109/ipps.1994 1994

  20. [20]

    Marathe, Mark Moir, and Nir Shavit

    Virendra J. Marathe, Mark Moir, and Nir Shavit. 2006. Composite Abortable Locks. InProceedings 20th IEEE Interna- tional Parallel & Distributed Processing Symposium (IPDPS ’06) . IEEE, USA, 1–10. doi:10.1109/IPDPS.2006.1639367

    work page doi:10.1109/ipdps.2006.1639367 2006

  21. [21]

    Markatos

    Evangelos P. Markatos. 1991. Multiprocessor Synchronization Primitives with Priorities. IFAC Proceedings Volumes 24, 2 (1991), 1–6. doi:10.1016/S1474-6670(17)51259-8 IFAC/IFIP Workshop on Real Time Programming, Atlanta, GA, USA, 15-17 May 1991

    work page doi:10.1016/s1474-6670(17)51259-8 1991

  22. [22]

    José Martins, Adriano Tavares, Marco Solieri, Marko Bertogna, and Sandro Pinto. 2020. Bao: A Lightweight Static Par- titioning Hypervisor for Modern Multi-Core Embedded Systems. InWorkshop on Next Generation Real-Time Embedded Systems (NG-RES 2020) (Open Access Series in Informatics (OASIcs), Vol. 77) , Marko Bertogna and Federico Terraneo (Eds.). Schloss...

    work page doi:10.4230/oasics.ng- 2020

  23. [23]

    Mellor-Crummey and Michael L

    John M. Mellor-Crummey and Michael L. Scott. 1991. Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Trans. Comput. Syst. 9, 1 (Feb 1991), 21–65. doi:10.1145/103727.103729

    work page doi:10.1145/103727.103729 1991

  24. [24]

    Jiannan Ouyang and John R. Lange. 2013. Preemptable Ticket Spinlocks: Improving Consolidated Performance in the Cloud. In Proceedings of the 9th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (Houston, Texas, USA)(VEE ’13). Association for Computing Machinery, New York, NY, USA, 191–200. doi:10.1145/ J. ACM, Vol. 37, No. 4, ...

    work page arXiv 2013

  25. [25]

    Sean Peters, Adrian Danis, Kevin Elphinstone, and Gernot Heiser. 2015. For a Microkernel, a Big Lock Is Fine. In2015 6th Asia-Pacific Workshop on Systems (APSys ’15) (Tokyo, Japan). Association for Computing Machinery, New York, NY, USA, Article 3, 7 pages. doi:10.1145/2797022.2797042

    work page doi:10.1145/2797022.2797042 2015

  26. [26]

    Ragunathan Rajkumar. 1990. Real-Time Synchronization Protocols for Shared Memory Multiprocessors. InProceed- ings.,10th International Conference on Distributed Computing Systems (ICDCS ’90) . IEEE, USA, 116–123. doi:10.1109/ ICDCS.1990.89257

    work page arXiv 1990

  27. [27]

    Lehoczky

    Ragunathan Rajkumar, Lui Sha, and John P. Lehoczky. 1988. Real-Time Synchronization Protocols for Multiprocessors. In 1988 9th IEEE International Real-Time Systems Symposium (RTSS ’88) . IEEE, USA, 259–269. doi:10.1109/REAL.1988. 51121

    work page doi:10.1109/real.1988 1988

  28. [28]

    Scott and William N

    Michael L. Scott and William N. Scherer. 2001. Scalable Queue-based Spin Locks with Timeout. In Proceedings of the Eighth ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming (Snowbird, Utah, USA) (PPoPP ’01). Association for Computing Machinery, New York, NY, USA, 44–52. doi:10.1145/379539.379566

    work page doi:10.1145/379539.379566 2001

  29. [29]

    Baker, An-I Wang, and Michael Gonzalez Harbour

    Mark Stanovich, Theodore P. Baker, An-I Wang, and Michael Gonzalez Harbour. 2010. Defects of the POSIX Sporadic Server and How to Correct Them. In2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS ’10). IEEE, USA, 35–45. doi:10.1109/RTAS.2010.34

    work page doi:10.1109/rtas.2010.34 2010

  30. [30]

    Richard West, Ye Li, Eric Missimer, and Matthew Danish. 2016. A Virtualized Separation Kernel for Mixed-Criticality Systems. ACM Trans. Comput. Syst. 34, 3, Article 8 (June 2016), 41 pages. doi:10.1145/2935748 J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018

    work page doi:10.1145/2935748 2016