Bounded Priority-Aware Locking for Real-Time Kernels
arXiv:2605.27620v1 [cs.OS] 26 May 2026
SHRIRAM RAJA and RICHARD WEST, Department of Computer Science, Boston University, USA 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. CCS Concepts: • Computer systems organization → Real-time operating systems; • Software and its engineering → Process synchronization. Additional Key Words and Phrases: Real-Time Operating Systems, Synchronization ACM Reference Format: Shriram Raja and Richard West. 2018. Bounded Priority-Aware Locking for Real-Time Kernels. J. ACM 37, 4, Article 111 (August 2018), 23 pages. https://doi.org/XXXXXXX.XXXXXXX
1 Introduction Synchronized access to shared resources is a fundamental problem faced by operating systems. It is especially challenging in real-time systems, which must meet strict timing requirements. In general, the worst-case waiting time to exclusively access a shared resource increases with the number of concurrent tasks competing for that resource, which leads to potential deadline misses. Moreover, important tasks might be delayed by those having less importance as a result of priority inversion. A poorly designed locking mechanism only exacerbates these problems, motivating us to consider practical solutions that build upon the state-of-the-art. This paper, therefore, focuses on the design of spinlocks that ensure bounded delay and minimize priority inversion. Although spinlocks are generally applicable to multicore systems, we primarily consider access to non-preemptible shared kernel control paths and data structures, by entry points such as system calls and interrupts in a real-time system. Authors’ Contact Information: Shriram Raja, [email protected]; Richard West, [email protected], Department of Computer Science, Boston University, Boston, Massachusetts, USA. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM 1557-735X/2018/8-ART111 https://doi.org/XXXXXXX.XXXXXXX J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:2
Shriram Raja and Richard West
An unordered spinlock is the simplest mechanism to serialize accesses to a shared resource. Only one task is allowed to change the lock status and access the resource, while all other tasks busy wait until the lock is free. Highly contended resources increase the likelihood of multiple waiters. In such cases, it is not clear which waiter acquires the spinlock on its release, leading to variable and potentially high wait times. In contrast, FIFO-ordered locks have been used to bound the waiting time of lock contenders [7, 19, 23]. When a resource is shared by all cores in an 𝑚-core system, FIFO locks with non-preemptible critical sections provide a worst-case waiting time of 𝑚 − 1 times the worst-case duration of the critical section. Since FIFO locks only consider order of arrival, the average waiting time of tasks of all priorities is the same. Typically, worst-case delay is the only factor considered when determining if all tasks meet their deadlines. However, there is value in improving the average-case performance of higher priority tasks, to allow them to make more progress or finish sooner. Allowing more important tasks to complete earlier, or perform additional work beyond their minimal execution requirements, may lead to improved system-wide quality-of-service. For example, a task that performs a numerical integration might operate at a mandatory worst-case sampling rate to ensure minimal accuracy, with any additional cycles used for over-sampling, to optionally reduce integration error. This is similar to the work on imprecise computations [17, 18]. To that end, we propose the use of a priority-aware lock that provides the same worst-case bound as FIFO but prioritizes among tasks to improve the average case performance of more important tasks. Several priority queue-based locks have previously been proposed [2], which support preemption of waiters and timeouts. However, priority queue-based locks either: (1) require the releasing task to traverse a queue to determine the next lock holder, extending the critical section, or (2) incur queue insertion delays during lock acquisition, which cause unbounded waiting in pathological cases [12]. To avoid queue insertions of waiting tasks at acquisition time, while still ensuring a constant release time, we propose a two-stage Batched Priority Lock (BPL): first, waiting tasks are batched in order of arrival, and then contend to resolve the waiter with the highest priority among those in the same batch. A strictly priority-ordered lock may result in starvation of low priority tasks. However, by first considering the order of lock request, and then the priority, BPL ensures progress of all waiters. Any tasks that make a request for a lock held by the same holder are batched together, allowing precedence to be given to the highest priority waiter in that group when the lock is released. Contributions: We describe the implementation of BPL, and compare against FIFO, strictly priority-ordered, and simple spinlocks. Using simulations for systems up to 64 cores, and implementations of the different locks in our in-house Real-Time Operating System Quest, we determine: (1) the overheads of each lock, (2) their effectiveness at eliminating priority inversions, and (3) the conditions under which BPL proves more advantageous than other locks. The rest of this paper is organized as follows: Section 2 explains the issues with using priorityunaware spinlocks in a multicore real-time system. Section 3 gives an overview of our real-time kernel and lists the desired properties of a kernel lock. The design of the Batched Priority Lock is described in Section 4 and analyzed in Section 5. Section 6 evaluates different lock approaches. Related work is discussed in Section 7, followed by conclusions in Section 8. 2 Resource Sharing in a Multicore RTOS We consider a multi-core real-time system with 𝑚 cores where tasks are scheduled using globally consistent, statically assigned priorities. One instance of priority inversion is said to occur in a realtime system when a task is unable to make progress due to the execution of one lower priority task. Multicore real-time systems with globally consistent priorities suffer from: (1) local priority J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:3
inversion between tasks on the same core, and (2) global priority inversions between tasks on different cores. Unbounded local priority inversion is avoided by ensuring that critical sections are non-preemptible, either by boosting the priority of the lock holder to the highest priority in the system for the duration of the critical section, or by disabling interrupts. However, even nonpreemptible critical sections guarded by a simple spinlock or FIFO-ordered lock may suffer global priority inversion as these locks do not give precedence to higher priority tasks as illustrated by the following example. Regular Execution
Blocking for Shared Resource
Lock Attempt
Lock Acquired
τa
τa
τb
τb
τc
0
1
2
3
4
5
6
t
(a) Priority Inversion due to non-priority-ordered locks: 𝜏𝑎 experiences one instance of priority inversion from 𝑡 = 2 till 𝜏𝑐 completes its critical section
τc
0
Critical Section
1
2
3
4
5
6
t
(b) Priority Inversion avoided with priority-aware lock: 𝜏𝑎 acquires the lock at 𝑡 = 3
Fig. 1. Example of Global Priority Inversion in Multicore Real-Time Systems
Example: Consider a 3-core system shown in Figure 1a. Suppose task 𝜏𝑎 has the highest priority, 𝜏𝑐 the lowest priority, and 𝜏𝑏 the middle priority, with all tasks assigned to different cores. At time 𝑡 = 1, 𝜏𝑏 is in its critical section. 𝜏𝑐 and 𝜏𝑎 attempt to acquire a shared FIFO lock at times 𝑡 = 1 and 𝑡 = 2, respectively. 𝜏𝑏 exits its critical section at time 𝑡 = 3, but since the FIFO lock does not enforce priority ordering, 𝜏𝑐 acquires the lock, resulting in the highest priority task, 𝜏𝑎 , waiting at least the length of another critical section. If a priority-aware lock were used, as shown in Figure 1b, the highest priority task 𝜏𝑎 will acquire the lock at 𝑡 = 2. Extending this situation to a lock contended by 𝑚 tasks running on separate cores of an 𝑚-core system, a FIFO lock will cause the last arriving waiter to be delayed by 𝑚 − 1 other tasks, irrespective of their priority. The challenge, then, is to implement a priority-based lock that reduces the waiting time of the most important tasks, but also ensures a bounded delay for all waiters. There exist several priority-aware locks that use queue data structures to ensure that only the highest priority contender is allowed to acquire the lock when it is released [7, 14, 19, 21]. These locks are broadly classified into two categories: • Release-prioritized locks: this category of locks uses a simple FIFO queue for waiters that attempt to acquire a lock. However, when the lock holder completes its critical section, it traverses the entire queue to identify the highest priority waiter, and passes ownership of the lock to that task. While this approach is simpler to implement, it effectively extends each critical section by the time taken to determine the next highest priority waiter and atomically remove it from the FIFO queue. This extra cost is part of the lock release operation by the current holder. J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:4
Shriram Raja and Richard West
• Acquire-prioritized locks: these use a priority queue to order waiters as they attempt to acquire a lock. The releasing task is then able to quickly identify the next task to take lock ownership, avoiding costly delays being added to its critical section. In effect, all waiters cooperate to identify the highest priority task while the lock is in use. However, complications arise in the organization of the priority queue, which is performed by a collection of concurrent waiters. Huang and Jayanti [12] identify situations where a task fails to enqueue itself into the priority queue due to repeated failed transactions. David et al. [9] conduct a thorough study on synchronization, and show that simple locks are often preferred even in cases of high contention. In contrast, complex locks often incur costs without providing net benefits. We postulate that a lock designed for a real-time operating system must:
• ensure mutual exclusion with minimal overhead, at least in the common case, using widely available hardware instructions, • minimize the waiting time of high priority tasks by bounding priority inversion, and • provide progress guarantees to avoid starvation of low priority tasks. 3 Kernel Latency in a Multicore RTOS Symmetric multiprocessing (SMP) features two or more processors, or cores, which are connected to a shared main memory managed by a single operating system. The trusted kernel component of such an operating system is considered a shared resource that is accessed by tasks on different cores using system calls. These system calls require access to synchronization primitives, to exclusively update shared kernel state or avoid contention on access to operating system resources that must be serialized. Counting semaphores, mutexes, blocking and spinning locks are commonly used synchronization primitives. Such primitives may be used to guard access to the entire kernel (e.g., a big kernel lock) or may be used to implement mutually exclusive access to small regions of kernel code (critical sections) guarded by separate fine-grained locks. Regardless of coarse or finegrained locking, it remains a challenge to avoid unbounded wait time when acquiring access to shared resources, while also giving precedence to higher priority tasks. In this work, we consider Quest RTOS as a case study. Scheduling in Quest is done using the concept of bandwidth preserving sporadic servers [29] implemented using the Virtual CPU (VCPU) abstraction proposed by Danish et al [8]. One or more tasks are assigned to a given VCPU, having an execution budget 𝐶 every period 𝑇 . Each per-core local scheduler selects the highest priority runnable VCPU, having a non-zero budget at the current time. The next task to run using this VCPU is dispatched on the local processor core. The VCPUs are partitioned across cores, but are allowed to migrate for load balancing purposes. On each core, the Rate-Monotonic algorithm [16] is implemented to schedule the VCPUs. Either FIFO or some form of priority-based scheduling is used to select the next task to run on a VCPU shared by more than one task. The Liu-Layland test [16] is used to verify the schedulability of the VCPUs assigned to a core. Hence, Quest can be said to use Semi-Partitioned Fixed-Priority scheduling. Similar to UNIX-like systems, Quest uses segmentation to separate the kernel from user-space. Figure 2 shows the different control paths through the kernel: User Task to User Task (Figure 2a): User-space tasks are interrupted by the local APIC (LAPIC) timer, either due to preemption or the expiration of the corresponding VCPU budget. Further interrupts are disabled before control passes to the handler. The handler first sends an end-ofinterrupt signal to the timer and then acquires the kernel lock. After processing the sleepqueue of the system, the current task is placed in the back of the core-local (per-cpu) run queue and then the scheduler is called. The scheduler chooses the highest priority VCPU with a non-zero budget, J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:5
(a) User to User Task Transition
(b) User to Kernel Task Transition
(c) Kernel to User Task Transition
(d) Kernel to Kernel Task Transition
Fig. 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 next has a kernel task mapped to it. Hence, the kernel task immediately proceeds while still holding the kernel lock and with interrupts disabled. Kernel Task to User Task (Figure 2c): Since kernel tasks run with interrupts disabled, control switches to another task only when a kernel task yields to the scheduler using a vcpu_block() or a sleep() call. If a user-space task is mapped to the next runnable VCPU, the kernel lock is released and interrupts are re-enabled. Kernel Task to Kernel Task (Figure 2d): When switching from one kernel task to another, the interrupts remain disabled and the kernel lock is held throughout, as the flow of control passes from the first kernel task, to the scheduler and finally to the next kernel task. For cases where a user task issues a blocking system call, control will first pass to the kernel, acquiring the kernel lock and disabling interrupts. A subsequent switch to either a kernel or user task from this point is similar to the control flow originating from a kernel task. Quest uses a big kernel lock to enforce mutual exclusion in critical kernel code. This simplifies system design and avoids potential “hold and wait” deadlocks caused by fine-grained locking of different kernel control paths guarded by separate synchronization constructs. While fine-grained locking may improve scalability, it also introduces the following problems: J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:6
Shriram Raja and Richard West
• Formal Verification of Correctness. In their survey on Microsoft platforms that use concurrency [11], Godefroid and Nagappan found that 66% of the 684 respondents dealt with concurrency issues. While this study does not focus on real-time kernels, use of several finegrained locks in the kernel also makes the paths through the kernel more complex. This in turn makes formal verification of system correctness very complicated. • Worst-Case Timing Analysis. When the entire kernel is considered as a single critical section, the worst-case timing analysis of tasks is simplified. In contrast, separate locks within the kernel leads to potentially interleaved, or nested, critical sections, adding to the complexity of worst-case timing analysis. There is a trade-off to be made here between scalability and system complexity. Also, it must be noted that predictability is of higher importance than scalability for a real-time system. In a system with 𝑚 cores, the maximum number of non-preemptible threads that could contend for the kernel lock is limited to 𝑚. Thus, when 𝑚 is generally small, the level of contention is lower. Even if a real-time system were to require many cores, it is possible to split the cores into separate groups, e.g., by using multiple guests running on a paritioning hypervisor [22, 30]. Only one group of cores assigned to a guest would then need to contend for the same lock. This is desirable in mixed-criticality systems as it allows for greater temporal and spatial isolation of tasks of different criticalities. We conclude this section with some factors to consider when designing a kernel lock for a realtime kernel such as Quest and a discussion of the system model. To improve the predictability of the kernel lock, it needs to have awareness of the priority of the task attempting to acquire the lock, i.e., it needs to be aware of the period of the VCPU that the task is mapped to. Note that this paper only considers one-to-one mapping between tasks and VCPUs1 . However, since all tasks mapped to a VCPU will have the same period and budget, i.e., that of the VCPU, this does not have any impact on the working of a predictable kernel lock. In certain cases it might be beneficial to allow tasks waiting for a shared resource to suspend as it allows potentially lower priority tasks to make progress. A spinlock is generally used when the worst-case time required to acquire the lock is smaller than the time taken to suspend the current waiter and switch to a different task. However, since the scheduler is itself in the critical section, and hence is accessed only after acquiring the kernel lock, there is no benefit in allowing suspension of contenders. Thus, a modified spinlock that has priority awareness is sufficient.
Fig. 3. System Model
System Model: Given the aforementioned design requirements, we arrive at the system model shown in Figure 3. We consider a real-time system with 𝑚 homogeneous cores that uses spinlocks to guard the entire kernel. As the scheduler itself is a part of the critical section, a task waiting for, or holding a spinlock on one of the cores cannot be preempted to allow another task to execute 1
We henceforth use tasks and VCPUs interchangeably
J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:7
in its place. Each task is characterized by a priority, 𝑃 , and the index 𝑖 of its current processor core. Task priorities are represented by unsigned integers in the range [𝑃𝑚𝑎𝑥 , 𝑃𝑚𝑖𝑛 ], with a lower number indicating a higher priority level. The core index is a value in the range [0, 𝑚). The system is free to use static or dynamic priorities, under the condition that task priorities are not modified while waiting to acquire a lock, or while executing a critical section. The system requires a consistent notion of priority, with global or semi-partitioned scheduling being allowed, given that task migrations are permitted across lock invocations. 4 Batched Priority Locking (BPL) The Batched Priority Lock (BPL), shown in Algorithms 1, and 2, aims to ensure bounded waiting time, while distinguishing between task priorities among the same group of contenders. The following is a high level overview of the algorithm: 1. Fast Path: A task first checks if there are any other waiters, and if there are none, it attempts to acquire the lock. This fast path enables fast uncontested acquisition. If there are other waiters, or if the lock acquisition fails, the task proceeds to the next step. 2. Batching Stage (𝑠𝑡𝑎𝑔𝑒 _0): All waiters in this stage obtain a batch ID. Waiter(s) with the lowest batch ID, representing those that arrived the earliest, are allowed to proceed to the next stage. Other waiters continue to spin in the same stage. 3. Priority Ordering Stage (𝑠𝑡𝑎𝑔𝑒 _1): Tasks in this stage contend to determine the highest priority level (lowest 𝑃 value). Once they settle on an agreed lowest 𝑃 value, all tasks of that priority proceed to the next stage. 4. Mutual Exclusion Stage: In this final stage, the highest priority task(s) among those that arrived in the earliest batch contend to acquire the lock. The algorithm takes as inputs a pointer to a lock object (𝐿), the priority of a given task (𝑃 ), and the index (𝑖) of its corresponding processor core. 4.1
Attributes of the BPL Object
• 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 records the number of tasks contending for the lock and is initialized to 0. This value is tracked to choose the fast path of the lock in the absence of any contention. • 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 and 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 are key variables used by the tasks in 𝑠𝑡𝑎𝑔𝑒 _0 and 𝑠𝑡𝑎𝑔𝑒 _1. 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 is set to the lowest batch ID of all waiters in 𝑠𝑡𝑎𝑔𝑒 _0, while 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 holds the highest priority level of all waiters in 𝑠𝑡𝑎𝑔𝑒 _1. Both barriers are initialized to -1u, i.e., the highest unsigned integer value. • 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔 is an array holding two bitvectors, used to check if a task on a specific core is contending in a particular stage. For instance, if the 𝑖𝑡ℎ bit of 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[1] is set, it means there is a task on core 𝑖 that is contending in 𝑠𝑡𝑎𝑔𝑒 _1. Initially, both the settling bitvectors are 0. • 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ is initialized to 0 and is split into two bit-fields: the lower 𝑘 bits track the number of tasks in a batch, and the remaining bits denote the batch ID for tasks entering 𝑠𝑡𝑎𝑔𝑒 _0. A batch lasts for the duration of one critical section. Therefore, before a holder releases the lock, it clears the lower 𝑘 bits and adds 2𝑘 to 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ, to start a new batch ID. 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ is reset to zero only when there is no contention for the lock. After reading 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ into a temporary variable, new waiters shift their copy right by 𝑘 bits to get their batch ID. Note that the maximum number of waiters in a single batch is limited by min (𝑚 − 1, 2𝑘 − 1), where 𝑘 is set to ⌈𝑙𝑜𝑔2 (𝑚)⌉ for an 𝑚-core system. • 𝑠𝑡𝑎𝑡𝑢𝑠 is a single bit that is set when the lock is held, and is 0 when the lock is free. Initially the lock status is free. J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:8
4.2
Shriram Raja and Richard West
Explanation of the BPL Algorithm
Consider the example shown in Figure 4: a) The lock is held by 𝜏𝑎 , and the parameters of the lock object are in their initial state as 𝜏𝑎 acquired the lock through the fast path, which is explained in Subsection 4.3. b) 𝜏𝑏 arrives next to contend for the lock. As the lock is already held, it cannot execute the fast path. Hence, it increments 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 , reads 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ to set its local batch variable, and increments the lower field of 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ to 1 to indicate that there is one task in batch 0. Since there are no other tasks in its batch, it is able to set the 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 and 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 to its own batch and priority respectively, proceeding to the final spinlock stage. Note that it sets bit 1 in the 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[0] and 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[1] bitvectors when it enters 𝑠𝑡𝑎𝑔𝑒 _0 and 𝑠𝑡𝑎𝑔𝑒 _1, respectively. However, it resets them when leaving to the next stage and, hence, they are both currently 0. c) Task 𝜏𝑐 next attempts to acquire the lock. It also increments 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 and the lower field of 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ, and then sets bit 2 of 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[0] before entering 𝑠𝑡𝑎𝑔𝑒 _0. d) Since 𝜏𝑐 holds the same batch ID as the 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 (0), it proceeds to 𝑠𝑡𝑎𝑔𝑒 _1, after resetting 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[0]. As its priority is higher than the 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 (recall that lower 𝑃 value implies higher priority), 𝜏𝑐 updates 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 to its own priority and proceeds to the final spinlock stage. Meanwhile, while 𝜏𝑏 is spinning in the 𝑓 𝑖𝑛𝑎𝑙 _𝑠𝑡𝑎𝑔𝑒 , it sees that the 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 no longer holds its own priority level, so it then moves back to 𝑠𝑡𝑎𝑔𝑒 _1. Since both tasks are settled in the right stages, the 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔 bitvectors are reset to 0 at this point. Thus, BPL ensures that within the same batch, higher priority tasks acquire the lock first. e) When 𝜏𝑎 completes its critical section, it increments the batch ID field of 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ and clears the lower field, before resetting the lock status to 0. f) As the lock is free, 𝜏𝑐 successfully sets the status bit, decrements 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 , and enters its critical section. To allow other tasks in its batch to move on to the final stage, the new holder resets the 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 before entering its critical section. It could also be the last task in its batch, necessitating a reset of the 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 . Thus, whenever a task acquires the lock, it resets both the barriers, forcing all the current waiters to reorganize themselves in the stages of the lock. g) As both the barriers are reset, 𝜏𝑏 is pushed back to 𝑠𝑡𝑎𝑔𝑒 _0. At the same time, a new waiter 𝜏𝑑 arrives to contend for the lock. Hence, 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 is incremented to 2. However, note that the lower field of 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ now only holds the number of waiters in batch 1. Both tasks set their corresponding bits in 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[0] and enter 𝑠𝑡𝑎𝑔𝑒 _0. h) Since 𝜏𝑏 belongs to an earlier batch than 𝜏𝑑 , it proceeds on to 𝑠𝑡𝑎𝑔𝑒 _1, while 𝜏𝑑 stays in 𝑠𝑡𝑎𝑔𝑒 _0. As it is settled in its stage, 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[0] is 0, and only bit 1 is set in 𝑠𝑡𝑎𝑔𝑒 _1. Though not shown here, 𝜏𝑏 will then proceed to the final spinlock stage and acquire the lock when 𝜏𝑐 releases it. Thus, BPL enforces FIFO ordering across batches. 4.3
Implementation of the BPL Algorithm
We now discuss the implementation of the BPL algorithm in detail. In addition to common hardware instructions such as the atomic increment (INC), decrement (DEC), store (STORE), set-bit (SET(variable, bit index)) and reset-bit (RESET(variable, bit index)), BPL requires the following atomic transactions:
• test-and-set (TAS(bit)): The TAS instruction returns the value of 𝑏𝑖𝑡 before setting it. • compare-and-swap (CAS(variable, old value, new value)): The CAS instruction compares 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 with 𝑜𝑙𝑑 𝑣𝑎𝑙𝑢𝑒 , and if they are equal, 𝑛𝑒𝑤 𝑣𝑎𝑙𝑢𝑒 is stored in 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 and it returns 𝑇 𝑟𝑢𝑒 . Otherwise, it returns 𝐹 𝑎𝑙𝑠𝑒 . J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels stage_0
stage_1
final_stage
111:9 Critical Section τa
a)
i=0 P=0
τb i=1 P=7 batch = 0
b)
c)
τc
τb
i=2 P=5 batch = 0
i=1 P=7 batch = 0
d)
e)
τb
τc
i=1 P=7 batch = 0
i=2 P=5 batch = 0
τb
τc
i=1 P=7 batch = 0
i=2 P=5 batch = 0
τb i=1 P=7 batch = 0
f)
τa i=0 P=0
τa i=0 P=0
τa i=0 P=0
Lock Object num_waiters = 0 batch_barrier = -1u, priority_barrier = -1u settling[0] = 0, settling[1] = 0 curr_batch = {0,0} status = 1 num_waiters = 1 batch_barrier = 0, priority_barrier = 7 settling[0] = 0, settling[1] = 0 curr_batch = {0,1} status = 1 num_waiters = 2 batch_barrier = 0, priority_barrier = 7 settling[0] = 100b, settling[1] = 0 curr_batch = {0,2} status = 1 num_waiters = 2 batch_barrier = 0, priority_barrier = 5 settling[0] = 0, settling[1] = 0 curr_batch = {0,2} status = 1 num_waiters = 2 batch_barrier = 0, priority_barrier = 5 settling[0] = 0, settling[1] = 0 curr_batch = {1,0} status = 0
τc i=2 P=5
num_waiters = 1 batch_barrier = -1u, priority_barrier = -1u settling[0] = 0, settling[1] = 0 curr_batch = {1,0} status = 1
τb
g)
i=1 P=7 batch = 0
τc
τd
i=2 P=5
num_waiters = 2 batch_barrier = -1u, priority_barrier = -1u settling[0] = 1010b, settling[1] = 0 curr_batch = {1,1} status = 1
i=3 P=4 batch = 1
h)
τd
τb
i=3 P=4 batch = 1
i=1 P=7 batch = 0
τc i=2 P=5
num_waiters = 2 batch_barrier = 0, priority_barrier = -1u settling[0] = 0, settling[1] = 10b curr_batch = {1,1} status = 1
Fig. 4. Batched Priority Locking (BPL) Algorithm Example
J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:10
Shriram Raja and Richard West
• fetch-and-add (FAA(variable, addend)): The FAA instruction returns the value of 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 before adding 𝑎𝑑𝑑𝑒𝑛𝑑 to it. The following is an explanation of Algorithms 1 and 2 from the perspective of task 𝜏 that attempts to first acquire and then eventually release a lock. Fast Path (Lines 2-8): If there are no other waiters, 𝜏 attempts to clear the 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ to 0 using an atomic CAS instruction. If there are any waiters when the batch ID is reset, they could incur significant delays, because lower batch numbers are first used to decide lock precedence. Hence, 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 has to be read before attempting to clear 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ. Additionally, if 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ only denoted the value of the batch ID, it would only be updated when a lock holder releases the lock. In that case, due to pathological interleaving, we could have a scenario where one waiter clears 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ while another waiter has read a non-zero batch ID. This could result in the latter waiting for an indefinite amount of time to acquire the lock. To avoid such a scenario, we split 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ into the batch ID and number of tasks fields. Thus, during the general flow of control through the lock acquisition logic, all waiters first increment 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 and then also modify 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ. Any waiter that attempts to clear 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ reads the two variables in opposite order: reading 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ first in Line 2 and then 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 in Line 3. This ensures that any changes made to either variable are captured when a task attempts to clear it in Line 4. If the value of 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ changes (as a result of another task) between Lines 2 and 4, the CAS instruction fails. Irrespective of the success or failure of the CAS instruction, 𝜏 tries to acquire the lock in Line 5 using an atomic TAS instruction on the 𝑠𝑡𝑎𝑡𝑢𝑠 . If this succeeds, 𝜏 jumps to the end of the lock code (Line 38). If this lock attempt fails, or if there are other waiters, 𝜏 atomically increments 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 (Line 6), and then obtains a batch ID. It first performs an FAA to atomically read and increment 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ, and then right-shifts the value 𝑘 -bits to obtain the batch ID (Line 8). It then proceeds to 𝑠𝑡𝑎𝑔𝑒 _0 in the lock acquisition. stage_0 (Lines 9-18): When 𝜏 enters 𝑠𝑡𝑎𝑔𝑒 _0, it sets the bit corresponding to its core (𝑖) in the 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[0] bitvector. This bitvector is used to ensure that a task that is the first to reach the end of 𝑠𝑡𝑎𝑔𝑒 _0 proceeds to 𝑠𝑡𝑎𝑔𝑒 _1 only when there are no other waiters, or all waiters have settled on a specific value as the lowest batch ID. 𝜏 then reads 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 , which holds the ID of the earliest batch. If 𝜏 belongs to that batch or an earlier batch (Line 11), it performs an atomic CAS transaction. Note that this branch can be further split into tasks in earlier batches (< 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 ) and those in the current batch (= 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 ), and allowing only the tasks in earlier batches to perform the CAS. However, by not splitting them we keep the implementation of the algorithm in x86 assembly simpler. If the CAS transaction succeeds, 𝜏 resets its settling bit (Line 13), else it tries again. If 𝜏 finds that it belongs to a later batch, it resets its settling bit, and continues to check 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 (Line 16). Thus, all waiters will reset their settling bit either after successfully setting 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 to their batch in Line 13, or after finding that they do not fall into the earliest batch in Line 16. Tasks that succeed in the CAS operation check the 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[0] bitvector to ensure that all other waiters have reset their settling bits, i.e., compared themselves with 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 before proceeding to the next stage (Line 17). Line 18 acts as the final step in the barrier, pushing back any tasks that do not have the lowest batch ID but just happened to finish the transaction first. stage_1 (Lines 19-30): When 𝜏 enters 𝑠𝑡𝑎𝑔𝑒 _1 in Line 19, similar to 𝑠𝑡𝑎𝑔𝑒 _0, it first indicates its presence by setting the 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[1] bitvector. As a next step, in addition to reading the value of 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 , which holds the highest priority level of all tasks in 𝑠𝑡𝑎𝑔𝑒 _1, 𝜏 also checks if it still is the lowest batch task (Line 21). If not, 𝜏 clears its settling bit and resets 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 to -1u (unsigned) before jumping back to 𝑠𝑡𝑎𝑔𝑒 _0. The following scenario motivates the need for this check. Consider multiple tasks of the same highest priority spinning in the final stage. One of them acquires the lock, hence it first resets 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 before also resetting 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 . J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:11
Algorithm 1: Batched Priority Lock - Lock Function function lock(struct bpl * L, uint32_t P, uint32_t i) prev = L→curr_batch; 3 if L→num_waiters == 0 then 4 CAS (L→curr_batch, prev, 0); // Fast Path 5 if !TAS (L→status) then goto acqd;
1
2
6 7 8
INC (L→num_waiters); batch = FAA (L→curr_batch, 1); batch = batch >> k; // FIFO / Batching Stage
9 10 11 12 13 14 15 16 17 18
stage_0: SET (L→settling[0], i); read_batch_barrier: prev = L→batch_barrier; if batch ≤ prev then if CAS (L→batch_barrier, prev, batch) then RESET (L→settling[0], i); // control goes to Line 17 else goto read_batch_barrier; else RESET (L→settling[0], i); goto read_batch_barrier; while L→settling[0] != 0 do ; if L→batch_barrier != batch then goto stage_0; // Priority Ordering Stage
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
stage_1: SET (L→settling[1], i); read_priority_barrier: prev = L→priority_barrier; if L→batch_barrier != batch then STORE (L→priority_barrier, -1u); RESET (L→settling[1], i); goto stage_0; if P ≤ prev then if CAS (L→priority_barrier, prev, P) then RESET (L→settling[1], i); // control goes to Line 30 else goto read_priority_barrier; else RESET (L→settling[1], i); goto read_priority_barrier; while L→settling[1] != 0 do ; final_stage: // Spinlock if L→priority_barrier != P then goto stage_1; if L→batch_barrier != batch then STORE (L→priority_barrier, -1u); goto stage_0; if !TAS (L→status) then goto Line 37; else goto final_stage; // Lock Acquired
37 38
DEC (L→num_waiters); acqd: STORE (L→priority_barrier, -1u); STORE (L→batch_barrier, -1u);
J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:12
Shriram Raja and Richard West
Algorithm 2: Batched Priority Lock - Unlock Function function unlock(struct bpl * L) new_val = L→curr_batch; 3 AND(new_val, ((232 - 1) - (2𝑘 - 1))); 4 ADD(new_val, 2𝑘 ); 5 STORE (L→curr_batch, new_val); 6 RESET (L→status, 0);
1
2
One or more of the tasks in the 𝑓 𝑖𝑛𝑎𝑙 _𝑠𝑡𝑎𝑔𝑒 could be at Line 32. As soon as 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 is reset, these tasks will move back to 𝑠𝑡𝑎𝑔𝑒 _1. In 𝑠𝑡𝑎𝑔𝑒 _1, they first read the current 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 value (Line 20). Now, if the check in Line 21 were not present, these tasks would then immediately try to re-enter the 𝑓 𝑖𝑛𝑎𝑙 _𝑠𝑡𝑎𝑔𝑒 by performing a CAS on 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 . However, there could be other tasks in 𝑓 𝑖𝑛𝑎𝑙 _𝑠𝑡𝑎𝑔𝑒 that got pushed all the way back to 𝑠𝑡𝑎𝑔𝑒 _0 because they were in Line 33 when the barriers were reset. To allow these tasks to get equal footing, we perform this additional check. Also, this check protects against the condition where a very fast waiter of a newer batch acquires the lock before a slow waiter that belongs to an older batch. In the next if-else block (Lines 24-29), similar to 𝑠𝑡𝑎𝑔𝑒 _0, the waiting task performs a CAS on 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 if its 𝑃 value is the smallest in magnitude among all tasks in 𝑠𝑡𝑎𝑔𝑒 _1. Tasks that succeed in this CAS then wait until all tasks reset their 𝑠𝑒𝑡𝑡𝑙𝑖𝑛𝑔[1] bit in Line 30. final_stage (Lines 32-38): Only tasks that have the lowest batch value (𝑏𝑎𝑡𝑐ℎ) among all contenders and the highest priority (lowest 𝑃 value) among those of the same batch should be allowed to perform the final bit TAS instruction. Hence, when 𝜏 enters the final stage, before another check of the lock status in Line 35, it also checks 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 (Line 32) and 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 (Line 33). When the lock is freed, the task in the 𝑓 𝑖𝑛𝑎𝑙 _𝑠𝑡𝑎𝑔𝑒 succeeds in the TAS operation. It then decrements the number of waiters, and resets the barriers, allowing the other waiters to contend to determine the next holder. Unlock (Algorithm 2): By including all the ordering logic in the acquiring side of the lock, we simplify the releasing task’s requirements. The unlock operation, shown in Algorithm 2 simply updates the current batch ID and then resets the status bit (Line 6). The batch ID is updated by first reading it into a local variable, resetting the lower 𝑘 bits, incrementing the upper 32 − 𝑘 bits by adding 2𝑘 , and storing it in the lock object, using the atomic STORE instruction. This resets the count of the number of waiters while incrementing the batch ID by 1, assuming a 32-bit wordsize. A CAS is unnecessary here because the number of waiters cannot be more than 𝑚 − 1 and 𝑘 = ⌈𝑙𝑜𝑔2 (𝑚)⌉. 4.4
Discussion
Irrespective of how many times a waiter is pushed back to 𝑠𝑡𝑎𝑔𝑒 _0 or 𝑠𝑡𝑎𝑔𝑒 _1, the batch ID is always the first parameter used to determine the next waiter. Each waiter reads the batch ID only once (in Line 7). When there is contention for the lock, i.e., 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 is non-zero, the batch ID is monotonically non-decreasing. When there is no contention, 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 = 0, and the waiter will immediately acquire the lock. Thus, in both cases, the lock is acquired in a finite number of steps. The settling bitvector in each stage ensures that a fast process that completes a stage early is forced to wait for all other tasks in that stage to also settle. This ensures that the batch order is followed in practice, providing the worst-case bound of FIFO locks. J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:13
While a FIFO lock considers only the order of lock request, and a priority-ordered lock only considers the priority of waiters, BPL considers both. It reaches a middle ground, minimizing priority inversions in the average case while still meeting the worst-case bound of FIFO. In the next section, we analyze the properties of BPL. 5 Analysis of BPL This section analyzes the key properties of BPL, including the asymptotic execution costs of an implementation on an m-core system. 5.1
Progress Guarantees
TheoRem 5.1. A Batched Priority Lock is starvation-free. PRoof. Even though it considers priority among waiters in the same batch, BPL first groups tasks by the window in which they made their lock requests. The previous batch is closed and a new batch is created in Line 5 of Algorithm 1, when a holder increments the batch number just before releasing the lock. Thus, BPL ensures that if a task makes a lock attempt at time 𝑡 , it will not have to wait for any task that makes a lock attempt after 𝑡 + 𝐶𝑆 , where 𝐶𝑆 is the duration of the critical section of the task holding the lock at time 𝑡 . In other words, all tasks that arrive within the same critical section (while the lock is held) will acquire the lock before any tasks that arrive in the next critical section. Therefore, even in cases of high contention, BPL guarantees progress for all waiters. □ Lemma 5.2. The maximum batch size for a Batched Priority Lock in Algorithms 1, and 2 is 𝑚 − 1. PRoof. In an 𝑚-core system that uses spin-based locks to guard non-preemptible critical sections, no more than 𝑚 tasks can contend to acquire a free lock. This is because neither the waiting tasks nor the lock holder are preemptible. One of the 𝑚 contenders will succeed in acquiring the lock through the fast path in Line 5, and hence will not read the batch ID. In the worst-case, up to 𝑚−1 tasks will fetch and increment 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ while waiting for the lock. With 𝑚−1 waiters and 1 holder, a new contender can only arrive after the holder releases the lock. By updating 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ and starting a new batch before releasing the lock, BPL ensures that a batch grows no larger than 𝑚 − 1. □ Lemma 5.3. The total number of tasks across all concurrent batches in the Batched Priority Lock is bounded by 𝑚 − 1. PRoof. Since the maximum number of tasks involved in a single lock cannot exceed 𝑚, irrespective of the number of concurrent batches, the total number of waiters in all of them is also bounded by 𝑚 − 1. □ TheoRem 5.4. In the worst-case, a task using a Batched Priority Lock will wait for no more than 𝑚 − 1 critical sections before entering its critical section. PRoof. In the worst-case, a task 𝜏 attempting to acquire a lock will have to wait for (1) the current holder, (2) tasks in all earlier batches, and (3) all higher priority tasks in its own batch. In Case 1, no waiter can be attempting to acquire the lock on the same core as the current holder, since critical sections are non-preemptible and locks are non-blocking. Cases 2 and 3 represent all other waiters excluding 𝜏 . Since waiters busy-wait and do not block, they must each be on a distinct core. Hence the total number of tasks in Cases 2 and 3 cannot be greater than (𝑚 − 2). Therefore the maximum number of critical sections that 𝜏 will have to wait to acquire the lock is 1, from Case 1, and (𝑚 − 2), from Cases 2 and 3. Thus, the total cannot be greater than (𝑚 − 1). □ J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:14
5.2
Shriram Raja and Richard West
Blocking Delay and Schedulability
BPL guarantees worst-case FIFO-bounded delay as long as a task in a later batch is not able to gain the lock before a task in an earlier batch. This is assured for homogeneous cores, which are assumed to execute stages of the acquisition function at the same rate, or for cores where the disparity in speeds is relatively low. Violations to the FIFO bound would only be possible if a task in a later batch on one core could pass through all stages of the lock acquisition algorithm before any other task in an earlier batch completed Line 9 of Algorithm 1. While the worst-case blocking bound remains identical for FIFO locks and BPL, implying equivalent schedulability analysis in theory, BPL provides superior average-case performance for higher priority tasks within each batch. Under FIFO locks, all tasks experience approximately the same average waiting time, irrespective of priority. In contrast, BPL reduces the average waiting time for higher-priority tasks while increasing it for lower-priority tasks. The cost of implementing BPL is slightly higher than that of a FIFO-ordered lock (as discussed in Section 6.2.1). However, if the reduced delay to higher priority tasks outweighs the implementation costs, then BPL should be seen as preferred to a FIFO lock. 5.3
Implementation
Variants of the instructions used by BPL exist for most popular architectures making the lock approach portable. For example, the x86 architecture features CMPXCHG, XADD, ADD, INC, DEC, BTS, XCHG, MOV, AND, OR, and BTR instructions, some of which may have a LOCK prefix to enforce atomicity. On ARM, the LDREX/STREX instructions along with explicit memory barriers (DMB) can be used to implement BPL. Since shared memory is modified using the CAS instruction in a loop in each stage, in the worst-case it takes a waiter 𝑂(𝑚) time to settle in an appropriate stage in the lock() function. The unlock() function does not contain any loops and hence is executed in constant time. Apart from the lock object, which is globally accessible and hence must be fetched from memory, all other variables are local and stored in registers to minimize memory access overhead. The ticket lock shown in Algorithm 3 is a simple FIFO-ordered lock. It uses two counters: one incremented at request time, and the other at release time. This algorithm enforces each task to be ordered by a unique request value, or a batch number, which is acquired when attempting to access the lock. Algorithm 3: Ticket Lock function lock(struct fl * L) batch = FAA (L→request, 1); 3 check_response: if L→release != batch then 4 goto check_response;
1
2
5 6
function unlock(struct fl * L) INC (L→release);
BPL similarly uses a FIFO ordering among batches in 𝑠𝑡𝑎𝑔𝑒 _0 of Algorithm 1, where more than one task has the same batch number. The ticket lock avoids pathological interleaving of waiters and holders by using two counters: one incremented by the waiters and the other by the holder when releasing the lock. These counters are equivalent to 𝑛𝑢𝑚_𝑤𝑎𝑖𝑡𝑒𝑟𝑠 and 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ in BPL. Assuming a 32-bit architecture, the batch ID is denoted by the upper 32 − 𝑘 bits of 𝑐𝑢𝑟𝑟 _𝑏𝑎𝑡𝑐ℎ. The largest value that can be represented by an unsigned integer variable of size 32 − 𝑘 is 232−𝑘 − 1. J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:15
If the batch ID is incremented beyond this value, it will lead to the variable looping back to 0, which may lead to an arbitrarily long wait time for tasks that hold a higher batch ID. To avoid this issue, Line 4 resets the current batch ID to 0, after ensuring there are no other waiters and the current value is the same as the value read in Line 2. Thus, BPL requires there to be a brief period of no contention for every 232−𝑘 − 1 lock acquisition attempts. For example, if there are 64 cores in the system, and 𝑘 is set to 6, BPL requires there to be a small period of no contention for every 226 − 1 (more than 67 million) lock requests. At this point, all current waiters should complete their critical sections, before new lock requests are made. In a 64-bit system, this requirement is even less restrictive, allowing more than 2.8×1017 requests on a 64-core machine before requiring a no-contention batch ID reset. Thus, we do not consider it to be a practical limitation of the implementation. If multiple tasks in the earliest batch have the same highest priority, all of them will reach the final stage (Line 32). The TAS lock in Line 35 ensures that only one of them succeeds in acquiring the lock. While this choice is made arbitrarily, the worst-case lock delay bound among tasks within the batch remains the same as derived in the previous subsection. Cancellation of a request is not typically required in the case of kernel locks. However, BPL is able to support lock cancellations with minimal changes. Any task that intends to terminate its request simply resets 𝑏𝑎𝑡𝑐ℎ_𝑏𝑎𝑟𝑟𝑖𝑒𝑟 and 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 _𝑏𝑎𝑟𝑟𝑖𝑒𝑟 before exiting the lock() function, triggering a reordering of the remaining waiters. 6 Experimental Evaluation 6.1
Simulation
We use a queuing theory approach to model task requests for a batched priority lock. As will be seen in the evaluations, BPL is compared against FIFO and priority-based locks under simulated conditions. We begin with the machine repairman queuing theory model [15], shown in Figure 5. The model consists of 𝑚 sources of traffic, which require service from a single server. The server handles only one request at a time. Since a request represents a machine requiring repair, a source cannot generate another request until its previous one has been serviced. In our case, due to the nonpreemptible nature of waiters and lock holders, the sources are tasks mapped to 𝑚 cores, and the server is a shared resource (e.g., kernel) guarded by a lock. Most importantly, similar to the sources in the model, tasks running on separate cores cannot request the lock to the shared resource until their previous attempt has completed.
Core1
Shared Wait Queue Resource Core2
R
Corem
Fig. 5. Machine Repairman Queue Model with 𝑚 Sources J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:16
Shriram Raja and Richard West
One approach to modeling request arrivals from each of the 𝑚 sources is to consider them as separate Poisson arrival processes. Each source, 𝐶𝑖 , has an arrival rate, 𝜆𝑖 , with an expected exponentially distributed inter-arrival time, 𝜆1 . For 𝑚 separate Poisson arrivals, one per core, the 𝑖
𝑚
model has an aggregated arrival rate of 𝜆𝑎𝑔𝑔 = ∑ 𝜆𝑖 . If the shared resource is managed by a single 𝑖=1
server also having a Poisson service rate, 𝜇 , then its expected service time is 𝜇1 . Rather than have each core generate independent arrivals, we use a traffic generator that produces concurrent bursts of arrivals. A burst of size 𝑚 implies 𝑚 cores coordinating to generate one lock request each at the same time instant. The generator has an average rate 𝜆𝑏𝑢𝑟𝑠𝑡 . Therefore, the inter-arrival time between consecutive executions of the burst generator is exponentially distributed with a mean value of 𝜆 1 . Each time the generator runs, it produces a burst of arrivals 𝑏𝑢𝑟𝑠𝑡
from a uniform distribution having a specific mean. As a uniform distribution over a range [0, 𝑚] has an expected value of 𝑚/2, it never generates bursts with a mean value greater than this. For compliance with our queuing model, the burst requests are randomly selected from sources that do not already have a request pending. If the number of available sources is less than the generated burst size, all of them are selected. If there are no available sources, the burst generator waits for another interval of time. Thus, the number of sources picked might be less than or equal to the random burst size. The generator then triggers the chosen sources to each submit a lock request. This queuing model is simulated using the SimPy discrete event simulator [5]. The different configurations that are evaluated are as follows:
• Number of Cores (Sources): 8, 16, 32, and 64 sources all having distinct priorities. • Mean Burst Size: chosen in powers of 2, from 22 to 𝑚/2. • Service Rate (𝜇 ): this is kept at 0.01, to represent an average of 1 request serviced every 100 time units. • Burst Arrival Rate (𝜆𝑏𝑢𝑟𝑠𝑡 ): For each core count and mean burst size, 𝜆𝑏𝑢𝑟𝑠𝑡 is varied from 0.01𝜇 to 1.0𝜇 . • Lock Ordering: FIFO (FL) and strict priority ordering (PL) are simulated using the shared resource primitives available in SimPy. A custom class was added to model Batched Priority Lock ordering (BPL). Since our only goal here is to understand the impact of different locking methods, we do not include the fast path, which is an optimization provided for practical performance. We use the weighted mean delay to evaluate the efficacy of each lock ordering. If the mean delay of 𝐶𝑜𝑟𝑒𝑖 is denoted by 𝑑𝑖 and its weight is denoted by 𝑤𝑖 , the weighted mean delay, 𝑑𝑤 is obtained using the following equation: 𝑚
∑ 𝑤𝑖 ⋅ 𝑑 𝑖
𝑑𝑤 =
𝑖=1
𝑚
(1)
∑ 𝑤𝑖
𝑖=1
In our tests, the lowest priority core is assigned a weight of 1, and each higher priority core is assigned a weight one higher than the previous core. Thus, the highest priority core has the weight 𝑚. Each test is run until a total of 𝑚×10000 lock requests are complete. The results obtained are consistent across different core counts. Hence, we show only the results of the 64-core test case with mean burst sizes 8 and 32. The total priority inversions, and weighted mean delay (normalized to that obtained for FIFO ordering), are shown in Figure 6. J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
FL
111:17
BPL
10
1.25 Normalized Weighted Mean Delay
Total Number of Priority Inversions
10 8
7
10 6
10 5
0.75 0.50
0.72 0.75 1.0
0.66 0.83 1.0
0.72 0.93 1.0
1884.29
4856.73
0.99
1.0
1.0
1.0
0.25
0.010 0.050 0.100 0.500 1.000 Burst Arrival Rate (as a factor of Service Rate)
(b) Weighted Mean Delay (mean burst size = 8)
10 8
1.25 Normalized Weighted Mean Delay
Total Number of Priority Inversions
1.00
0.00
0.010 0.050 0.100 0.500 1.000 Burst Arrival Rate (as a factor of Service Rate)
(a) Priority Inversions (mean burst size = 8)
10 7
10 6
10 5
PL
0.010 0.050 0.100 0.500 1.000 Burst Arrival Rate (as a factor of Service Rate)
(c) Priority Inversions (mean burst size = 32)
1.00 0.75 0.50
0.7 0.79 1.0
0.99 0.92 1.0
2.81 0.95 1.0
3007.67
5219.35
0.99
1.0
1.0
1.0
0.25 0.00
0.010 0.050 0.100 0.500 1.000 Burst Arrival Rate (as a factor of Service Rate)
(d) Weighted Mean Delay (mean burst size = 32)
Fig. 6. Comparison of Priority Inversions and Weighted Mean Delay for 64 Cores
Observation 1: For lower mean burst sizes and arrivals, the performance of BPL is close to that of PL. In Figures 6a and 6c, for lower mean burst sizes and arrival rates, the percentage of lock requests experiencing priority inversions under Batched Priority Locking (BPL) is significantly lower than for FIFO ordering (FL), although never as good as for strict priority ordering (PL). This is because, when the arrival rate is low, the inter-arrival time is long enough for most if not all requests generated in each burst to be serviced. Hence, the behavior of BPL is very close to that of PL: all requests in a burst are categorized into a batch, and they are allowed access to the resource in priority order. Observation 2: For higher mean burst sizes and arrivals, the performance of BPL is never worse than that of FL. As the burst arrival rate increases, we see a divergence in the performance of PL and BPL, and a convergence between FL and BPL. Higher arrival rates yield new bursts while requests from one or more previous bursts are still waiting to be serviced. This potentially splits waiters into increased numbers of separate batches, if arrivals span the execution of different critical sections, so the benefits of priority ordering within a given batch are diminished. For very high arrival rates, each batch size approaches 1, and there can be up to 𝑚 − 1 such batches, so BPL degrades to FL. In contrast, at lower burst arrival rates and sizes, a group of tasks may join the same batch, and BPL performs closer to PL in terms of minimizing priority inversions. Note that lower arrival rates do not necessarily imply low contention, as contention also depends on the burst size. Thus, for a J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:18
Shriram Raja and Richard West
mean burst size of 32, even when the arrival rate is only 0.010 times the service rate, an average of 32 tasks contend for the lock at each arrival. Figures 6b and 6d provide insights into the impact of priority inversions on task waiting times. In cases where BPL avoids most priority inversions and performs similarly to PL, the weighted mean delays of the two orderings are comparable. The difference between FL, and the pair of prioritized locks in these cases is proportional to the difference in the priority inversions between them. As the burst arrival rate increases, the normalized weighted mean delay of BPL approaches that of FL. However, PL now suffers badly, because it starves lower priority tasks from making progress altogether. The graphs are capped at a normalized 𝑑𝑤 value of 1.25, but PL reaches values above 5,000 in some cases. This shows the limitations of a strict priority ordering, which attempts to avoid priority inversions in all cases at the cost of potentially unbounded delay for lower priority tasks. These results show that Batched Priority Locking avoids priority inversions as long as progress guarantees are not impacted. BPL generally outperforms FL in terms of minimizing priority inversions and reducing waiting times for higher priority tasks. When there are large bursts of tasks arriving infrequently, they get grouped into the same batch, with BPL performance being similar to that of PL. On the other hand, if batch sizes reduce to 1 task, even under high arrival rates, BPL avoids the unbounded delays of a strictly priority-ordered lock, limiting the worst-case delay to that of FL. 6.2
Evaluation in an RTOS
In this subsection, we implement and evaluate BPL using Quest RTOS running on a Cincoze DX1100 Embedded PC [4]. This platform has a 1.8 GHz Intel Core i7-9700TE CPU with 8 physical cores. BPL is compared to an unordered spinlock (SL) implemented using the TAS lock and FIFO-ordered ticket lock (FL). We omit comparisons with strictly priority-ordered lock as it has already been shown to be unsuitable due to its potential to starve lower priority tasks. We omit comparisons against MCS, and other blocking locks that use queues, because BPL is designed for systems that use global spin-based locks. 6.2.1 Cost of Uncontested Lock Acquisition. The overhead of each lock is evaluated by measuring the time taken to acquire and release it using the rdtsc instruction when there are no contenders. All measurements are performed with interrupts disabled, so as not to skew results and are averaged over 10,000 readings. After excluding the 45 cycle overhead of the rdtsc instruction itself, the observed minimum, median, 99.9th percentile and maximum overhead in clock cycles are shown in Figure 7. 400 Clock Cycles
300 200
Metric Min Median 99.9th Percentile Max
100 0
SL
FL Lock Type
BPL
Fig. 7. Cost of Uncontested Lock Acquisition J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:19
FL
Normalized Weighted Mean Delay
1.2 1.0 0.8 0.98 0.96 0.94 0.94 0.94 0.6 1.0 1.0 1.0 1.0 1.0 1.0 0.99 0.99 0.99 0.4 1.02 0.2 0.0 0.2 0.4 0.6 0.8 1.0 Aggregated Arrival Rate (as a factor of Service Rate) (a) Weighted Mean Delay (equal arrival rates)
BPL 1.2 1.0 0.8 0.91 0.83 0.79 0.75 0.79 0.6 1.0 1.0 1.0 1.0 1.0 0.96 0.99 0.94 0.94 0.4 1.08 0.2 0.0 0.2 0.4 0.6 0.8 1.0 Aggregated Arrival Rate (as a factor of Service Rate)
Normalized Mean Delay of Highest Priority Task
SL
(b) Delay of Highest Priority Task (equal arrival rates)
Normalized Mean Delay of Highest Priority Task
1.2 1.0 0.8 0.9 0.86 0.8 0.75 0.71 0.6 1.0 1.0 1.0 1.0 1.0 1.04 0.98 0.93 0.97 0.4 1.09 0.2 0.0 0.2 0.4 0.6 0.8 1.0 Aggregated Arrival Rate (as a factor of Service Rate)
Normalized Weighted Mean Delay
1.2 1.0 0.8 0.89 0.92 0.87 0.84 0.84 0.6 1.0 1.0 1.0 1.0 1.0 1.0 1.0 0.98 1.0 0.4 0.99 0.2 0.0 0.2 0.4 0.6 0.8 1.0 Aggregated Arrival Rate (as a factor of Service Rate)
(c) Weighted Mean Delay (higher priority tasks have lower arrival rates)
(d) Delay of Highest Priority Task (higher priority tasks have lower arrival rates)
Fig. 8. Comparison of Lock Performance for 8 Cores on an RTOS
For both in the minimum and median cases, BPL incurs ≈ 100 clock cycle increase in overhead over both the simple spinlock and the ticket lock. Even in the 99.9th percentile case, the increase in overhead from the unordered spinlock to BPL is less than 150 cycles. This low overhead shows the effectiveness of the fast path. The maximum time recorded for all the locks occurs at the very first instance of locking and unlocking. This spike in worst-case execution time is due to caching misses and would be avoided when lock operations are performed on a warm cache. Observe from Figure 7, the maximum cost of BPL is only 50 cycles over FL. The overhead of BPL is offset by the gains it achieves in terms of providing bounded delay to all waiters and reduced priority inversions compared to a FIFO lock. BPL’s cost is further mitigated in cases where it applies to a big kernel lock or relatively large critical section. 6.2.2 Working Lock Performance in an RTOS. Next, all three lock implementations in Quest are compared with independent traffic arrival patterns having an aggregated arrival rate, 𝜆𝑎𝑔𝑔 described in Section 6.1. We use independent rather than a bursty arrival process, as this is more generic, and also because it is more difficult to ensure separate tasks on different cores arrive at exactly the same time to contend for a shared resource (here, the kernel). 𝜆𝑎𝑔𝑔 is varied from 0.2𝜇 to 1.0𝜇 for two cases: (1) where tasks on all cores have equal arrival rates, irrespective of priority, and (2) where higher priority tasks have lower arrival rates. All tasks have distinct priorities across the 8 cores of the machine. J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:20
Shriram Raja and Richard West
Note that while we use only 𝑚 tasks and vary their arrival rate, this is equivalent to testing with multiple tasks assigned to each core because we only consider non-preemptible waiters and lock 𝜆𝑎𝑔𝑔
holders. In case (1), the individual task arrival rates, 𝜆𝑖 , are set to 8 , and in case (2), each task’s 𝑟𝑖 ⋅𝜆𝑎𝑔𝑔 arrival rate, 𝜆𝑖 = 36 , where 𝑟𝑖 ∈ [1, 𝑚], with 𝑟𝑖 = 1 for the highest priority task, down to 𝑟𝑖 = 8 for the lowest priority task. In all cases, the length of the critical section is set to 70 𝜇𝑠 (i.e., the service rate is 14 kHz) which is the median time to service a usb_write system call guarded by a kernel lock in Quest. Each task is assigned to a VCPU, with a utilization of 99%, i.e., the VCPU receives an execution budget of 99 time units for every period of 100 time units. A total of 80,000 system call requests are made across all tasks, each attempting to acquire the kernel lock. Figures 8a and 8c show the weighted mean delays, normalized against FIFO locking, for cases (1) and (2), respectively. While BPL generally achieves better performance as the aggregated arrival rate is increased in both cases (1) and (2), it performs particularly well in the latter. Its normalized weighted mean delay is reduced up to 16% in Figure 8c, because BPL is able to give precedence to higher priority arrivals in the same batch. As higher priority arrivals are less frequent, they are more likely to be differentiated from lower priority tasks when they do arrive, using BPL. Thus, while BPL generally outperforms FL, it is particularly effective in cases where a shared resource is accessed less frequently by higher priority tasks. The normalized delays of the highest priority task shown in Figures 8b and 8d more clearly demonstrate the benefits of BPL on a real-time system. It must be noted that, BPL does not have a detrimental impact on the overall delay of all tasks. These results confirm the properties of BPL in a practical system. Note that SL rarely does worse than FL but if we were to go to higher contention rates it would not guarantee bounded delay, similar to PL. 7 Related Work There is a wealth of literature addressing the multiprocessor synchronization problem in real-time systems, including the seminal works by Rajkumar et al. on priority ceiling protocols in the late eighties [27] and early nineties [26]. A thorough summary of the literature is provided by Brandenburg [2]. Several of the recent real-time synchronization approaches either focus on supporting suspension [3], or priority assignment to spinlocks [1]. However, these approaches are not directly applicable to our focus on big kernel locks, because scheduling decisions are made only after acquiring exclusive access to the kernel. Here, we summarize a few relevant locks. The MCS lock [23] follows a simple FIFO-ordered enqueue process, where tasks spin on corelocal memory to avoid cache-related delays. The simplicity of MCS locks has resulted in them being implemented in Linux [6]. Other variants of FIFO locks include those that allow attempts, timeouts or aborts, and are often referred to as trylocks [13, 20, 24, 28]. Markatos [21] proposed a simple priority-ordered lock, where waiters append themselves to a queue, which is traversed by the releasing task to determine the next holder. This attributes more complexity to the lock releasing task, effectively extending its critical section overhead. The CLH lock, independently developed by Craig [7] and Magnusson et al. [19] follows a similar approach to implement FIFO or priority-ordering while providing cache benefits by allowing spinning on core-local memory. Johnson and Harathi presented a prioritized spinlock, where a task attempting to acquire the lock traverses the queue to insert itself according to priority. This approach yields a O(1) release time [14]. In the aforementioned works, there is an increase in complexity to maintain scalability. Huang and Jayanti presented a formal definition for priority mutual exclusion [12], and highlighted some of the issues with previous work. Their algorithm uses as many wait queues as there are priority J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:21
levels in the system, in an approach similar to multi-level queue scheduling. Tasks of equal priority reside in the same wait queue, and the lock releasing task iterates through the heads of each wait queue in priority order to find the next holder. Even though this method is somewhat simpler than previous approaches, it is not applicable to systems with a variable number of priority levels (e.g., when priorities are based on task deadlines). Fuerst [10] proposed a priority lock that operates for a maximum of 64 priority levels. The priority of a task is represented using a 64-bit bitvector, replacing the need to use a priority queue or other data structure such as a heap. After registering itself using the bitvector, a task checks if there are any higher priority waiters. If there are other waiters, the task spins, otherwise it attempts to set itself as the holder using a compareand-exchange operation on a global pointer. BPL ensures a FIFO ordering among tasks of equal priority, and also supports more than 64 priority levels if so desired. The BPL approach differs from others in that it attempts to bound the lock delay, while emphasizing task importance among lock waiters that are clustered in the same batch. BPL exhibits low overheads for uncontended lock acquisition. Similarly, the lock release overheads experience the same O(1) time bound as that proposed by Johnson and Harathi. We consider BPL more beneficial to real-time operating systems guarded by big kernel locks. In such cases, the increase in overhead compared to a simple spinlock is offset by the longer duration of a critical section, compared to when using fine-grained locks. Peters et al. show with empirical analysis that the use of a big kernel lock is suitable in a microkernel [25]. 8 Conclusions This paper describes the design and implementation of the Batched Priority Locking (BPL) algorithm. BPL uses batching to bound the time that any task waits to acquire a spinlock, while also considering the priority of waiters within the same batch to order lock acquisition. Simulation and empirical analysis confirms that BPL reduces priority inversions compared to FIFO-ordered locks, while still retaining the same bounded delay for lock access. In comparison, a strictly priorityordered lock reduces priority inversions at the cost of potentially unbounded delay to lower priority tasks. This is especially prevalent in cases of high lock contention. For real-time systems, locks that enforce bounded wait delays are necessary. BPL has benefits over FIFO when there are quality-of-service gains for reducing delay for higher priority lock contenders. The implementation overheads of BPL are offset by the benefits gained, especially in cases where critical sections are relatively long compared to the cost of the lock acquisition and release. This is because multiple tasks are grouped into the same batch, where they are ordered according to their priority. Only when tasks are partitioned into batch sizes of 1, does the algorithm degrade to FIFO ordering. For short-lived critical sections e.g., to do an atomic increment such as x++, the costs of using BPL reduce the benefits of the locking mechanism. In our case, we see value for accessing a big kernel lock that could have relatively long-lived critical control paths, and BPL minimizes priority inversions in such cases, reducing latency for higher priority tasks. Here, the lower delay for higher priority tasks yields reward in terms of being able to make sure computations meet a minimum (mandatory) level of service, while allowing for optional computations to additionally take place, time permitting, to improve the quality of the result. Imprecise computations [17, 18] is an example that could benefit from BPL, as applied to refinement tasks such as numerical integration, state estimation and so forth. Future work will consider the scalability limits of BPL on a single kernel, versus an alternative approach where large core counts are partitioned across multiple guest systems. For example, a single system with 𝑚 cores contending for a single lock could be compared to a partitioning hypervisor system, hosting 𝑛 guests each with 𝑚/𝑛 cores contending for a shared lock. How to assign tasks to the same guest under such a scenario will also be investigated. J. ACM, Vol. 37, No. 4, Article 111. Publication date: August 2018.
111:22
Shriram Raja and Richard West
References [1] 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 [2] 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 [3] 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 [4] Cincoze. [n. d.]. DX-1100 PC, Cincoze. https://www.cincoze.com/goods_info.php?id=286 [5] SimPy Contributors. [n. d.]. https://simpy.readthedocs.io/ [6] Jonathan Corbet. 2014. MCS locks and qspinlocks. https://lwn.net/Articles/590243/ [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 [8] Matthew Danish, Ye Li, and Richard West. 2011. Virtual-CPU Scheduling in the Quest Operating System. In 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS ’11). IEEE, USA, 169–179. doi:10.1109/ RTAS.2011.24 [9] Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. 2013. Everything You Always Wanted to Know About Synchronization but Were Afraid to Ask. In 2013 24th ACM Symposium on Operating Systems Principles (SOSP). Association for Computing Machinery, New York, NY, USA, 33–48. doi:10.1145/2517349.2522714 [10] Steven Fuerst. 2011. Priority Spin Locks. https://locklessinc.com/articles/priority_locks/ [11] Patrice Godefroid and Nachi Nagappan. 2008. Concurrency at Microsoft - An Exploratory Survey. Technical Report MSRTR-2008-75. Microsoft. 4 pages. https://www.microsoft.com/en-us/research/publication/concurrency-at-microsoftan-exploratory-survey/ [12] Chien-Chung Huang and Prasad Jayanti. 2016. Priority Mutual Exclusion: Specification and Algorithm. In Proceedings of the 30th International Symposium on Distributed Computing (DISC ’16). Springer, Berlin, Heidelberg, 385–398. [13] Prasad Jayanti. 2003. Adaptive and Efficient Abortable Mutual Exclusion. In Proceedings 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 [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 [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 [16] Chung L. Liu and James W. Layland. 1973. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. J. ACM 20, 1 (Jan 1973), 46–61. doi:10.1145/321738.321743 [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 [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 [19] 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 [20] Virendra J. Marathe, Mark Moir, and Nir Shavit. 2006. Composite Abortable Locks. In Proceedings 20th IEEE International Parallel & Distributed Processing Symposium (IPDPS ’06). IEEE, USA, 1–10. doi:10.1109/IPDPS.2006.1639367 [21] 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. [22] José Martins, Adriano Tavares, Marco Solieri, Marko Bertogna, and Sandro Pinto. 2020. Bao: A Lightweight Static Partitioning Hypervisor for Modern Multi-Core Embedded Systems. In Workshop 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 Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 3:1–3:14. doi:10.4230/OASIcs.NGRES.2020.3 [23] 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 [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, Article 111. Publication date: August 2018.
Bounded Priority-Aware Locking for Real-Time Kernels
111:23
2451512.2451549 [25] Sean Peters, Adrian Danis, Kevin Elphinstone, and Gernot Heiser. 2015. For a Microkernel, a Big Lock Is Fine. In 2015 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 [26] Ragunathan Rajkumar. 1990. Real-Time Synchronization Protocols for Shared Memory Multiprocessors. In Proceedings.,10th International Conference on Distributed Computing Systems (ICDCS ’90). IEEE, USA, 116–123. doi:10.1109/ ICDCS.1990.89257 [27] 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 [28] 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 [29] Mark Stanovich, Theodore P. Baker, An-I Wang, and Michael Gonzalez Harbour. 2010. Defects of the POSIX Sporadic Server and How to Correct Them. In 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS ’10). IEEE, USA, 35–45. doi:10.1109/RTAS.2010.34 [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.