Matthias Killat - Lock-free programming for real-time systems - Meeting C++ 2021

Matthias Killat - Lock-free programming for real-time systems - Meeting C++ 2021
Slides: https://slides.meetingcpp.com
Survey: https://survey.meetingcpp.com

Multi-core systems are ubiquitous and allow concurrent algorithms to be used in a broad field of applications, e.g. robotics and autonomous driving. Usually locking strategies are employed to protect shared data. For real-time systems with high availability requirements this can be undesirable, as it may lead to deadlocks and lockouts in case of partial system failure or delayed threads. Lock-free programming offers an alternative by forgoing locks and using specific atomic operations such as compare-exchange to guarantee race-free access to shared data. This makes it impossible for any failing operation to block another operation and can drastically improve responsiveness while also avoiding problems like priority inversion.

C++11 introduced a memory model and a multitude of atomic operations to the language. Arguably the most important of these operations is compare-exchange as it is a major building block of most lock-free algorithms. We show how to use these operations to solve various recurring problems in lock-free programming in several C++ examples. These examples explore data sharing without locks where we distinguish between reading and taking data (i.e. non-destructive and destructive reads). We discuss the ABA-problem as well as torn reads and present some practical solutions to these problems.

A major consideration of lock-free programming is ownership of data and observability of an operation. It is also closely related to memory management since it must be prevented that data which is still used by some concurrent reader is deleted as part of an operation. We show how this can be achieved by essentially managing the memory ourselves.

Finally we show an advanced technique of cooperative concurrency that can be used if an operation involves several observable steps to be completed. Operations using cooperative concurrency are designed in a way that they can be completed by any other thread in case of the original thread being delayed. The difficulty here is to ensure that an incomplete operation is completed by one thread only.