💻 computer science

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

This paper presents ReDAG-RT, a user-space global scheduling framework for ROS 2 that enforces rate-priority ordering and per-DAG concurrency bounds to eliminate cross-graph priority inversion, thereby significantly reducing deadline misses and response times for real-time multi-DAG execution without modifying the underlying middleware or operating system.

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

Published 2026-03-20

📖 4 min read☕ Coffee break read

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a busy, high-tech restaurant kitchen. This kitchen is responsible for three critical tasks happening at the same time:

The Chef (Perception): Constantly tasting the soup every 20 seconds to make sure it's perfect.
The Sous-Chef (Planning): Checking the menu and organizing orders every 50 seconds.
The Dishwasher (Control): Washing plates every 100 seconds.

In the world of robotics, these tasks are called DAGs (Directed Acyclic Graphs), which is just a fancy way of saying "a chain of steps that must happen in order."

The Problem: The "First-Come, First-Served" Chaos

The paper explains that the standard software used to run robot brains (called ROS 2) acts like a kitchen manager who has a terrible rule: "Whoever walks into the kitchen first gets to work, regardless of how important their job is."

This is called a FIFO (First-In, First-Out) queue.

Here is what happens in this chaotic kitchen:

The Dishwasher (a slow, low-priority task) walks in first.
The Chef (a fast, high-priority task) walks in a split second later.
Because the Dishwasher was first, the manager lets them start washing plates.
The Chef has to wait.
The Disaster: The soup burns because the Chef was delayed by the Dishwasher. In robotics terms, this is called Priority Inversion. A slow, unimportant task blocked a fast, critical one, causing the robot to miss its "deadline" (like crashing or dropping an object).

The standard ROS 2 system doesn't care about how often a task needs to happen; it only cares about when it arrived. This leads to unpredictable, jittery, and sometimes dangerous robot behavior.

The Solution: ReDAGRT (The "Rate-Priority" Manager)

The authors of this paper built a new system called ReDAGRT. Think of this as hiring a brilliant new kitchen manager who follows a strict rule: "The more often you need to do a job, the higher your priority is."

This is based on a concept called Rate-Monotonic Scheduling.

Here is how ReDAGRT fixes the kitchen:

The Priority List: The manager looks at the tasks.
- The Chef (20-second cycle) gets Priority #1.
- The Sous-Chef (50-second cycle) gets Priority #2.
- The Dishwasher (100-second cycle) gets Priority #3.
The Global Queue: Instead of a messy line, there is one organized waiting room. If the Dishwasher is already working, but the Chef walks in, the manager immediately stops the Dishwasher (preemption) and hands the Chef the spoon.
The Result: The Chef never waits for the Dishwasher. The soup is always tasted on time. The robot moves smoothly and predictably.

Why This Matters

The paper proves that you don't need to rebuild the entire robot or change the operating system (like Linux) to fix this. You just need to upgrade the "middle manager" (the software layer) to be smarter about who gets to work first.

The Key Findings (The "Taste Test"):

Fewer Mistakes: By using this new manager, the robot missed its deadlines (like dropping a cup) 29.7% less often than before.
Faster Reaction: The slowest tasks (the "tail" of the performance) became 42.9% faster.
No More Chaos: Even when the kitchen gets super busy, the system doesn't collapse. It handles the pressure gracefully.

The "Secret Sauce": Asymmetric Limits

The paper also discovered a cool trick. If you have two busy chefs, letting them both run at full speed at the same time causes a traffic jam. But if you limit one chef to do only 2 things at once and let the other do 5, the whole kitchen runs smoother. This "asymmetric" rule reduced interference by 40%.

In a Nutshell

ReDAGRT is a smart traffic cop for robot brains. It stops the slow, boring tasks from blocking the fast, life-saving tasks. It ensures that the robot's "heartbeat" (perception and control) stays steady and safe, even when the robot is doing many things at once. It turns a chaotic, unpredictable kitchen into a well-oiled, precision machine.

1. Problem Statement

Modern robotic systems using ROS 2 typically structure perception, planning, and control pipelines as independent Directed Acyclic Graphs (DAGs) of callbacks. These pipelines share a common execution environment managed by the default ROS 2 executors (SingleThreadedExecutor or MultiThreadedExecutor).

The paper identifies a critical structural deficiency in these default executors:

Lack of Global Priority Ordering: Default executors use a First-In-First-Out (FIFO) or loosely ordered queue without enforcing a global priority hierarchy across different DAGs.
Cross-DAG Priority Inversion: A low-frequency (low-priority) callback from one pipeline can execute before a high-frequency (high-priority) callback from another pipeline simply because it arrived earlier or acquired a worker thread first.
Unbounded Interference: This leads to uncontrolled contention, structural priority inversion, and high response-time variability.
Consequence: Under concurrent workloads, this behavior causes deadline misses and jitter, making ROS 2 unsuitable for time-critical and safety-sensitive Cyber-Physical Systems (CPS) without significant modification.

2. Methodology: ReDAGRT Framework

The authors propose ReDAGRT, a user-space global scheduling framework that operates entirely within the ROS 2 execution layer without modifying the ROS 2 API, the application graph structure, or the Linux kernel scheduler.

Core Architecture

Global Ready Queue: All ready callbacks from all concurrent DAGs are inserted into a single, unified user-space priority queue.
Rate-Monotonic (RM) Ordering: Tasks are assigned static priorities based strictly on their activation periods ( $T_i$ ). Shorter periods (higher frequency) receive strictly higher priorities ( $T_i < T_j \implies P_i > P_j$ ).
Preemptive Dispatch: The scheduler selects the highest-priority ready task. If a newly released task has a higher priority than the currently executing task, preemption occurs immediately.
Dependency Resolution: Before a task enters the global queue, the system verifies that its period has expired and all intra-DAG precedence constraints (dependencies within the same graph) are satisfied.
Per-DAG Concurrency Bounds: The framework enforces limits on the maximum number of simultaneously active callbacks per DAG to prevent one pipeline from monopolizing resources.

Formal Model

Task Model: Defined as a set of DAGs $G = \{G_1, ..., G_m\}$ , where each task $\tau_i$ has a Worst-Case Execution Time (WCET) $C_i$ , period $T_i$ , and deadline $D_i$ (assumed implicit, $D_i = T_i$ ).
Interference Analysis: The paper derives a formal interference bound $I_i$ for a task $\tau_i$ , defined as the sum of WCETs of all higher-priority tasks ($hp(i)$). Unlike default executors, this interference is bounded and analyzable.
Schedulability: The system utilizes classical Rate-Monotonic response-time analysis (RTA) to derive recurrence relations for worst-case response times, ensuring that if $R_i \leq D_i$ , the task is schedulable.

3. Key Contributions

Structural Analysis: Identification and characterization of Cross-DAG Priority Inversion as a fundamental flaw in default ROS 2 executors, proving that FIFO dispatch violates real-time priority semantics across independent pipelines.
Formal Interference Model: Development of a multi-DAG task model grounded in Rate-Monotonic theory, providing mathematical bounds for interference and response-time recurrences in a shared executor environment.
ReDAGRT Implementation: A fully functional, open-source, user-space scheduler that:
- Enforces global Rate-Monotonic priority.
- Supports preemption across DAG boundaries.
- Requires no kernel patches or API changes.
- Includes a timing monitor for real-time metrics (lateness, miss rate).

4. Experimental Results

The framework was evaluated in a ROS 2 Humble environment using synthetic multi-DAG workloads with mixed periods and criticality, comparing ReDAGRT against SingleThreadedExecutor and MultiThreadedExecutor (4 threads).

Deadline Miss Rate:
- ReDAGRT achieved up to a 29.7% reduction in combined deadline miss rate compared to the best-performing baseline configurations under stress.
- Compared to the MultiThreadedExecutor, ReDAGRT showed a 13.7% improvement in miss rate under comparable utilization.
Response Time & Jitter:
- 99th-percentile response time was compressed by 42.9% (reduced from 49ms to 28ms).
- Median response time improved from 21ms to 14ms.
- The Cumulative Distribution Function (CDF) showed a significant leftward shift, indicating tighter tail bounds and improved predictability.
Concurrency Sensitivity:
- Thread Scalability: Performance improved significantly from 4 to 8 threads (reducing miss rate), but saturated at 10 threads due to synchronization overhead.
- Asymmetric Bounds: Using asymmetric per-DAG concurrency bounds (e.g., limiting one DAG more strictly than another) reduced interference by 40.8% compared to symmetric configurations, proving that limiting the "footprint" of specific DAGs is crucial for reducing global contention.
Graceful Degradation: Under tight deadline constraints (overload conditions), ReDAGRT exhibited graceful degradation, whereas default executors suffered catastrophic increases in lateness (e.g., SingleThreadedExecutor lateness increased by two orders of magnitude).

5. Significance and Impact

Deterministic Real-Time ROS 2: ReDAGRT demonstrates that deterministic, analyzable multi-DAG scheduling is achievable entirely within the ROS 2 user-space layer, bridging the gap between standard robotic middleware and safety-critical real-time requirements.
No Kernel Dependency: By solving the scheduling problem at the executor level, it avoids the complexity and maintenance burden of kernel modifications (like PREEMPT_RT patches) or specialized OS configurations.
Safety-Critical Deployment: The framework provides the necessary theoretical foundation (schedulability analysis) and empirical evidence to deploy ROS 2 in safety-critical CPS where deadline misses are unacceptable.
Open Source: The authors have released the full implementation and experimental artifacts, facilitating reproducibility and community adoption.

In conclusion, ReDAGRT transforms the ROS 2 execution model from a best-effort, FIFO-based system into a Rate-Priority, preemptive, and interference-bounded runtime, enabling robust real-time performance for complex, concurrent robotic pipelines.