Thread Carefully: Preventing Starvation in the ROS 2 Multi-Threaded Executor

The Robot Operating System 2 (ROS 2) is a widely-used collection of tools and libraries for building robot applications. It is designed to be flexible and easy to use when creating complex robot systems with many interacting components.
Since its alpha version release in 2015, ROS 2 provides two options in a multi-threading operating system, namely the single-threaded executor and the multi-threaded executor. The single-threaded executor is starvation-free by design (i.e., every task is eventually executed) even in over-utilized systems, since the set of eligible task instances (called wait set) is only refilled once all task instances in the wait set are executed. The multi-threaded executor extends this mechanism to multiple threads that manage the wait set collaboratively. While intuitively this extension preserves the starvation-free property, and analyses for the multi-threaded executor even build upon this assumption, the multi-threaded executor has not been shown to be starvation-free.
In this work, we examine the mechanism of the multi-threaded executor in ROS 2 and demonstrate that it is prone to starvation, i.e., some tasks may never be executed even in under-utilized systems. This indicates risks for multi-threaded executors in the current ROS 2 design and further leads to counterexamples to the state-of-the-art response-time analyses by Jiang et al. (RTSS 2022) and Sobhani et al. (RTAS 2023). We propose a minimal change in the software architecture of the ROS 2 multi-threaded executor to enable starvation- and deadlock-free behavior. We empirically test that we prevent starvation in concrete ROS 2 system configurations, and show that our solution incurs a negligible overhead using the Autoware reference benchmark. Moreover, we prove that our solution is starvation- and deadlock-free using formal proofs and model checking.