Nested Locks in the Lock Implementation: The Real-Time Read-Write Semaphores on Linux

Linux is a GP (General Purpose) OS (Operating System) that has gained many features of RT (Real-Time) OS over the last decade. For instance, nowadays Linux has a fully preemptive mode, and a deadline-oriented scheduler [1]. Although many of these features are part of the official Linux kernel, many of them are still part of an external patch set, the PREEMPT-RT [2]. The PREEMP-RT changes the locking methods of Linux to provide the control of unbounded priority inversion, by using the Priority Inheritance Protocol [3] on mutex, and bounds the activation delay for the highest priority task. Indeed, the latency is the main evaluation metric for the PREEMPT-RT Linux: for example, the Red Hat Enterprise Linux for Real-time [4] (based on PREEMPT-RT) shows a max latency of 150 μs on certified hardware. However, due to Linux’s GPOS nature, RT Linux developers are challenged to provide the predictability required for a RTOS, while not causing regressions on the general purpose benchmarks. As a consequence, the implementation of some well known algorithms, like read/write semaphores, has to be done using approaches that were not well explored in academic papers, which is the case of read/write semaphores.