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

1. Il Problema: Inversione di Priorità e Interferenza Cross-DAG in ROS 2

I sistemi robotici moderni basati su ROS 2 (Robot Operating System 2) gestiscono pipeline di elaborazione complesse (percezione, localizzazione, pianificazione, controllo) strutturate come Grafici Diretti Aciclici (DAG) di callback. Questi DAG vengono eseguiti all'interno di un unico "executor" condiviso.

Il documento identifica una limitazione fondamentale negli executor predefiniti di ROS 2 (SingleThreadedExecutor e MultiThreadedExecutor):

• Mancanza di ordinamento globale: I callback vengono gestiti in code FIFO (First-In-First-Out) o con ordinamenti deboli, senza una politica di priorità basata sul tasso di attivazione (rate) tra DAG diversi.
• Inversione di priorità Cross-DAG: Un callback a bassa frequenza (es. pianificazione lenta) può essere eseguito prima di un callback ad alta frequenza (es. controllo critico) se arriva prima nella coda o acquisisce un thread per primo. Questo fenomeno, definito inversione di priorità cross-DAG, viola i principi classici della pianificazione real-time (Rate-Monotonic).
• Interferenza non controllata: In assenza di una gerarchia di priorità unificata, i DAG indipendenti competono per le risorse dell'executor in modo non deterministico, causando variabilità nei tempi di risposta, jitter elevato e mancate scadenze (deadline misses), specialmente sotto carichi di lavoro concorrenti.

2. Metodologia: ReDAGRT e Architettura di Scheduling

Il paper propone ReDAGRT, un framework di scheduling globale a livello di spazio utente (user-space) che risolve questi problemi senza modificare l'API di ROS 2, l'interfaccia dell'executor o il scheduler del kernel Linux.

Componenti Chiave dell'Architettura:

1. Modello di Task Multi-DAG: Il carico di lavoro è modellato come una collezione di DAG indipendenti ($G_k$), dove ogni nodo è un callback con parametri temporali (periodo $T_i$, WCET $C_i$, scadenza $D_i$).
2. Coda Pronta Globale Unificata: Tutti i callback pronti per l'esecuzione, indipendentemente dal DAG di appartenenza, vengono inseriti in un'unica coda di priorità globale.
3. Scheduling Rate-Monotonic (RM): La priorità è assegnata staticamente in base al periodo di attivazione: i task con periodi più brevi (frequenze più alte) ricevono priorità più elevate ($T_i < T_j \Rightarrow P_i > P_j$).
4. Scheduling Preemptivo: L'executor ReDAGRT implementa uno scheduling preemptivo a priorità fissa. Se un task ad alta priorità diventa pronto, preme il task attualmente in esecuzione (se di priorità inferiore).
5. Vincoli di Concorrenza per DAG: Viene introdotta una limitazione strutturale sul numero massimo di callback attivi simultaneamente per ogni DAG, per controllare l'interferenza.
6. Analisi dei Tempi di Risposta: Il framework deriva ricorrenze formali per il calcolo del tempo di risposta peggiore (Worst-Case Response Time - WCRT) e condizioni di schedulabilità basate sulla teoria classica di Rate-Monotonic, adattate per gestire le dipendenze intra-DAG.

3. Contributi Principali

Il paper presenta tre contributi fondamentali:

• Analisi Strutturale: Identifica e caratterizza l'inversione di priorità cross-DAG come una carenza strutturale fondamentale del modello di esecuzione predefinito di ROS 2, derivante dall'assenza di arbitrato globale delle priorità.
• Modello di Interferenza Formale: Sviluppa un modello matematico che quantifica l'interferenza tra DAG. Dimostra che sotto ReDAGRT l'interferenza diventa limitata e analizzabile, a differenza del modello predefinito dove è non controllata. Vengono derivati limiti di interferenza e condizioni di schedulabilità.
• Design e Valutazione di ReDAGRT: Implementa un framework di scheduling Rate-Monotonic globale che opera interamente nello spazio utente di ROS 2. Il codice è open-source e compatibile con l'API esistente, permettendo l'analisi formale dei tempi di risposta per carichi di lavoro multi-DAG misti.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti in un ambiente ROS 2 Humble con carichi di lavoro sintetici multi-DAG, confrontando ReDAGRT con gli executor predefiniti.

Risultati Chiave:

• Riduzione delle Manca Scadenze (Miss Rate): ReDAGRT ha ottenuto una riduzione fino al 29,7% del tasso combinato di mancate scadenze rispetto agli executor di base.
• Miglioramento dei Tempi di Risposta: C'è stata una compressione del 42,9% nel tempo di risposta al 99° percentile (da 49 ms a 28 ms), indicando una maggiore prevedibilità e stabilità temporale.
• Vantaggio su MultiThreadedExecutor: Rispetto al MultiThreadedExecutor (configurato con 4 thread), ReDAGRT ha mostrato una riduzione del 13,7% nel tasso di mancate scadenze a parità di utilizzo della CPU.
• Effetto dei Vincoli di Concorrenza: L'uso di vincoli di concorrenza asimmetrici tra i DAG (es. limitare un DAG più di un altro) ha ridotto l'interferenza del 40,8% rispetto alle configurazioni simmetriche, validando l'importanza del controllo dell'interferenza.
• Scalabilità: Le prestazioni migliorano aumentando il numero di thread fino a 8, oltre il quale si osserva una saturazione dovuta al sovraccarico di sincronizzazione.

5. Significato e Impatto

Il lavoro di ReDAGRT è significativo per diversi motivi:

• Real-Time Deterministico in ROS 2: Dimostra che è possibile ottenere un comportamento temporale deterministico e analizzabile in ROS 2 senza richiedere modifiche al kernel o all'architettura dell'API, rendendolo adatto per sistemi cyber-fisici critici per la sicurezza (CPS).
• Fondamento Teorico: Fornisce una base teorica solida (basata sulla teoria Rate-Monotonic) per l'analisi della schedulabilità in ambienti robotici complessi con pipeline concorrenti, colmando il divario tra la teoria dei sistemi real-time e l'implementazione pratica nei middleware robotici.
• Soluzione Pratica: Offre una soluzione immediatamente utilizzabile per sviluppatori robotici che necessitano di garantire scadenze temporali in sistemi multi-DAG, eliminando l'incertezza temporale intrinseca degli executor predefiniti.

In sintesi, ReDAGRT trasforma l'executor di ROS 2 da un meccanismo "best-effort" a un runtime consapevole della schedulabilità, risolvendo il problema dell'inversione di priorità tra pipeline indipendenti e garantendo prestazioni temporali prevedibili essenziali per la robotica di sicurezza.