Fast on Average, Predictable in the Worst Case: Exploring Real-Time Futexes in LITMUSRT

Abstract—This paper explores the problem of how to improve the average-case performance of real-time locking protocols, preferably without significantly deteriorating worst-case perfor-mance. Motivated by the futex implementation in Linux, where uncontended locks under the Priority Inheritance Protocol (PIP) do not incur kernel-switching overheads, we extend this concept to more sophisticated protocols; namely the PCP, the MPCP and the FMLP+. We identify the challenges involved in implementing futexes in these protocols and present the design and evaluation of their implementation under LITMUSRT, a real-time extension of the Linux kernel. Our evaluation shows that the average-case locking overhead is improved by up to 87 % for some scenarios, but it does come at a price in the worst case overhead. I