ReDAG-RT: Global Rate-Priority Scheduling for Real-Time Multi-DAG Execution in ROS 2

Md. Mehedi Hasan; Rafid Mostafiz; Bikash Kumar Paul; Md. Abir Hossain; Ziaur Rahman

cs.ROMar 18, 2026

ReDAG-RT: Global Rate-Priority Scheduling for Real-Time Multi-DAG Execution in ROS 2

Authors: Md. Mehedi Hasan, Rafid Mostafiz, Bikash Kumar Paul, Md. Abir Hossain, Ziaur Rahman

Abstract

ROS 2 has become a dominant middleware for robotic systems, where perception, estimation, planning, and control pipelines are structured as directed acyclic graphs of callbacks executed under a shared executor. However, default ROS 2 executors use best-effort dispatch without cross-DAG priority enforcement, leading to callback contention, structural priority inversion, and deadline instability under concurrent workloads. These limitations restrict deployment in time-critical and safety-sensitive cyber-physical systems. This paper presents ReDAGRT, a user-space global scheduling framework for deterministic multi-DAG execution in unmodified ROS 2. The framework introduces a Rate-Priority driven global ready queue that orders callbacks by activation rate, enforces per-DAG concurrency bounds, and mitigates cross-graph priority inversion without modifying the ROS 2 API, executor interface, or underlying operating system scheduler. We formalize a multi-DAG task model for ROS 2 callback pipelines and analyze cross-DAG interference under Rate-Priority scheduling. Response-time recurrences and schedulability conditions are derived within classical Rate-Monotonic theory. Experiments in a ROS 2 Humble environment compare ReDAGRT against SingleThreadedExecutor and MultiThreadedExecutor using synthetic multi-DAG workloads. Results show up to 29.7 percent reduction in deadline miss rate, 42.9 percent reduction in 99th percentile response time, and 13.7 percent improvement over MultiThreadedExecutor under comparable utilization. Asymmetric per-DAG concurrency bounds further reduce interference by 40.8 percent. These results demonstrate that deterministic and analyzable multi-DAG scheduling can be achieved entirely in the ROS 2 user-space execution layer, providing a practical foundation for real-time robotic middleware in safety-critical systems.

Figures & tables

Fig. 1: Cross-DAG priority inversion under the default ROS 2 executor and the ReDAG RT solution. (A) Multiple independent DAGs collapse into a shared FIFO queue with no global priority ordering. (B) Low-frequency callbacks execute before high-frequency ones, causing priority inversion and deadline misses. (C) ReDAG RT enforces Rate-Monotonic ordering via a unified priority queue. (D) Deterministic execution eliminates priority inversion and bounds response times.

Approach	Multi-DAG	Global Queue	Kernel Mod	API Compat	Formal Analysis	Evaluation
Default Execs [ 11 ]	$\times$	$\times$	$\checkmark$	$\checkmark$	$\times$	Baseline
PiCAS [ 17 , 18 ]	$\times$	$\times$	?	?	Chain-level	Real HW
EventsEx [ 21 , 22 ]	Tree	$\times$	$\checkmark$	$\sim$	RTA (restricted)	Sim
ROSRT [ 23 ]	$\checkmark$	OS-level	$\checkmark$	$\checkmark$	$\times$	Autoware
ROSCH [ 24 ]	$\checkmark$	$\times$	?	$\sim$	DAG-sync	Autoware
PREEMPT_RT [ 16 ]	$\checkmark$	Linux	$\times$	$\checkmark$	$\times$	Throughput

TABLE I: Comparison of ROS 2 Real-Time Scheduling Approaches

Fig. 2: ReDAG RT layered user-space scheduling architecture. Periodic DAG workloads $G_{k}=(V_{k},E_{k})$ release tasks upon period expiration. A dependency-aware release stage validates timing and precedence constraints before admitting ready tasks into a unified global Rate-Monotonic priority queue ordered by $\arg\min_{\tau_{i}\in\mathcal{R}}\,T_{i}$ . The ReDAG RT executor performs fixed-priority preemptive arbitration across all DAGs and dispatches to the unmodified Linux execution layer. An integrated Timing Monitor computes $R_{i}$ , $L_{i}$ , and $\mathrm{MR}_{i}$ online, with event-driven re-scheduling closing the control loop.

Executor	Utilization	Miss Rate	Max Lateness ( $\mu$ s)
SingleThreadedExecutor	0.6	0.748	1,764,841
MultiThreadedExecutor (4T)	0.8	0.552	7,153

TABLE II: Baseline ROS 2 Executor Performance

Fig. 3: Effect of thread count on ReDAG RT deadline miss rate. Increasing worker threads reduces interference until saturation near eight threads.

Fig. 4: Sensitivity of ReDAG RT performance to deadline scaling. Moderate deadline relaxation reduces miss rate, while excessive slack increases interference windows.

Fig. 5: Impact of per-DAG concurrency limits on combined deadline miss rate. Asymmetric concurrency bounds significantly reduce cross-DAG interference.

Fig. 6: Cumulative distribution function (CDF) of callback response times comparing default ROS 2 executors and ReDAG RT . A leftward shift indicates reduced latency and tighter tail bounds under rate-priority scheduling.

Scheduler	Median (ms)	95th %ile (ms)	99th %ile (ms)
ROS 2 Default	21	37	49
ReDAG RT	14	22	28

TABLE III: Response Time Percentiles: Default ROS 2 Executors vs. ReDAG RT

System	Configuration	Miss Rate
SingleThreadedExecutor	$U=0.6$	0.748
MultiThreadedExecutor	4 Threads	0.552
ReDAG RT	Best Configuration	0.476
ReDAG RT	Avg. (6 Threads)	0.686

TABLE IV: Comparison Between Default ROS 2 Executors and ReDAG RT

Real-Time Scheduling

Real-time scheduling allocates processors, accelerators, and network resources so tasks meet timing deadlines under workload and resource constraints.

See all 30 papers

Deterministic Execution of ROS 2 Applications via Lingua Franca
Jun 8, 2026Harun Teper, Shaokai Lin, Shulu Li +2Robotics
TU Dortmund University · Dortmund, Germany · University of California, Berkeley +3
OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration
Jun 13, 2026Thanh Nguyen Canh, Thang Tran Viet, Phuc Van Dinh +2Multi-Robot Systems Large Language Model-Based Robot Planning
School of Information Science, Japan Advanced Institute of Science and Technology, Nomi, 923-1211, Ishikawa, Japan. · University of Engineering and Technology, Vietnam National University, 10000, Hanoi, Vietnam. · Department of Robotics, Hanyang University, Ansan, 15588, Gyeonggi, Korea.
RED: Adaptive Real-Time DAG Scheduling for Robotic Inference under Environmental Dynamics
May 21, 2026Zexin Li, Tao Ren, Johnathan Liu +2Efficient Neural Network Inference Real-Time Scheduling
University of California, Riverside, USA · University of Pittsburgh, USA · University of Maryland, Baltimore County, USA +1

Jun 8, 2026J/K move · Enter open · S save

Deterministic Execution of ROS 2 Applications via Lingua Franca

Harun Teper, Shaokai Lin, Shulu Li, Edward A. Lee+1

TU Dortmund University · Dortmund, Germany · University of California, Berkeley+3

Robotics

Open paper AskPDF arXiv

The Robot Operating System 2 (ROS 2) is a widely used middleware for robotic systems, characterized by a publish-subscribe (pub-sub) communication mechanism in which computation is structured as callbacks dispatched by ROS 2 executors. Despite its popularity, the pub-sub pattern in ROS 2 is inherently nondeterministic: the order in which these callbacks run is nondeterministic even within a single executor, and distributed deployments add further nondeterminism from the interleaving of messages across nodes and from network latency. Such nondeterminism often leads to concurrency issues and makes it virtually impossible to analyze for safeness and provide guarantees. We present a framework that is able to convert an unmodified ROS 2 application and run it under Lingua Franca (LF), a coordination language for deterministic execution using logical time, so that the same input always produces the same deterministic execution order. We first describe which ROS 2 features can be executed deterministically under logical time. Such features enable the possibility to establish an automatic conversion framework to extract information from a ROS 2 application and directly convert it into an LF program. The rich features of LF, such as logical-time delays, federated execution across processes, and fault handling, can then be applied to make the ROS 2 application be executed in a deterministic and timing-predictable manner without changing the ROS 2 code. We evaluate the framework on a synthetic example and on the Autoware reference system. We show that the order in which callbacks are executed differs in default ROS 2, while also having end-to-end latencies that vary across executions. In contrast, our LF-controlled ROS 2 system produces a deterministic execution order and consistent end-to-end latencies.

Abstract

Real-Time Scheduling

Explore similar work

Deterministic Execution of ROS 2 Applications via Lingua Franca

OSDAG: Online Scheduling for Efficient Multi-Robot Collaboration

RED: Adaptive Real-Time DAG Scheduling for Robotic Inference under Environmental Dynamics