Turning Futexes Inside-Out: Efficient and Deterministic User Space Synchronization Primitives for Real-Time Systems with IPCP
Turning Futexes Inside-Out: Efficient and Deterministic User Space Synchronization Primitives for Real-Time Systems with IPCP
复制标题
彻底颠覆 Futexes：使用 IPCP 为实时系统提供高效且确定性的用户空间同步原语
DOI：
10.4230/lipics.ecrts.2020.11
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Alexander Zuepke
中科院分区：
文献类型：
--
作者：
Alexander Zuepke
在Linux和其他操作系统中，futexes（快速用户空间互斥锁）是实现POSIX同步机制（如阻塞互斥锁、条件变量和信号量）的底层同步原语。Futexes允许通过避免在快速路径上的系统调用来实现具有优异性能的互斥锁。但是，futexes基本上仅限于可表示为32位变量上的原子操作的同步机制。在操作系统内核级别，futex实现需要复杂的机制来查找内部等待队列，这使得它们容易受到确定性问题的影响。在本文中，我们提出了futexes的另一种设计，通过将等待队列管理的复杂性从操作系统内核完全转移到用户空间，即我们将futexes“从内到外”。“由内到外futexes”的启用机制是立即优先级上限协议（IPCP）的有效实现，用于在用户空间中实现非抢占式临界区，用于互斥的自旋锁，以及用于挂起或唤醒线程的交织服务。该设计允许我们在用户空间中实现通用线程同步机制，并将确定性问题移出内核，同时保持线程的性能属性。该方法适用于多处理器实时系统，每个处理器上都有分区固定优先级调度。我们在实时操作系统（RTOS）中对互斥锁和条件变量的实现进行了评估。在32位ARM平台上的实验结果表明，该方法是可行的，开销由底层同步原语驱动。
In Linux and other operating systems, futexes (fast user space mutexes) are the underlying synchronization primitives to implement POSIX synchronization mechanisms, such as blocking mutexes, condition variables, and semaphores. Futexes allow one to implement mutexes with excellent performance by avoiding system calls in the fast path. However, futexes are fundamentally limited to synchronization mechanisms that are expressible as atomic operations on 32-bit variables. At operating system kernel level, futex implementations require complex mechanisms to look up internal wait queues making them susceptible to determinism issues. In this paper, we present an alternative design for futexes by completely moving the complexity of wait queue management from the operating system kernel into user space, i.e. we turn futexes “inside out”. The enabling mechanisms for “inside-out futexes” are an efficient implementation of the immediate priority ceiling protocol (IPCP) to achieve non-preemptive critical sections in user space, spinlocks for mutual exclusion, and interwoven services to suspend or wake up threads. The design allows us to implement common thread synchronization mechanisms in user space and to move determinism concerns out of the kernel while keeping the performance properties of futexes. The presented approach is suitable for multi-processor real-time systems with partitioned fixed-priority (P-FP) scheduling on each processor. We evaluate the approach with an implementation for mutexes and condition variables in a real-time operating system (RTOS). Experimental results on 32-bit ARM platforms show that the approach is feasible, and overheads are driven by low-level synchronization primitives.