Deterministic Futexes: Addressing WCET and Bounded Interference Concerns
Alexander Zuepke, Robert Kaiser · 2019
Fast User Space Mutexes (Futexes) in Linux are a lightweight mechanism to implement thread synchronization objects like mutexes and condition variables. Since they handle the uncontended case in user space and call the operating system kernel only for suspension and wake-up on contention, futexes are particularly suited for best-effort workloads. Nonetheless, they are widely used to support real-time workloads and are integrated in the Linux real-time patch. This paper studies the suitability of the current futex implementation in Linux for certification according to avionics safety standards. Specifically, the paper details the worst-case execution time (WCET) behavior of futexes and the interference patterns that independent applications may encounter when using futexes. Based on our analysis, we identify some weaknesses in the current futex design in Linux, and we propose and evaluate a futex implementation in the context of PikeOS that is suitable for hard real-time and safety-critical systems which target certification. The proposed solution provides a subset of the functionality of Linux, but reduces WCET complexity and addresses the Freedom of Interference-principle for independent applications requested by safety standards.