License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECRTS.2020.11
URN: urn:nbn:de:0030-drops-123746
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12374/
Go to the corresponding LIPIcs Volume Portal

Zuepke, Alexander

Turning Futexes Inside-Out: Efficient and Deterministic User Space Synchronization Primitives for Real-Time Systems with IPCP

pdf-format:
LIPIcs-ECRTS-2020-11.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{zuepke:LIPIcs:2020:12374,
  author =	{Alexander Zuepke},
  title =	{{Turning Futexes Inside-Out: Efficient and Deterministic User Space Synchronization Primitives for Real-Time Systems with IPCP}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{Marcus V{\"o}lp},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12374},
  URN =		{urn:nbn:de:0030-drops-123746},
  doi =		{10.4230/LIPIcs.ECRTS.2020.11},
  annote =	{Keywords: Futex, Immediate Priority Ceiling Protocol, Critical Section, Monitor}
}

Keywords: Futex, Immediate Priority Ceiling Protocol, Critical Section, Monitor
Collection: 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)
Issue Date: 2020
Date of publication: 30.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI