Online Adaptive Fault Tolerant based Feedback Control Scheduling Algorithm for Multiprocessor Embedded Systems

Sintesi Tecnica: Algoritmo di Scheduling per il Controllo Feedback Adattivo Online e Tollerante ai Guasti per Sistemi Embedded Multiprocessore

Problematica
Il documento affronta le sfide inerenti al co-design tra controllo e scheduling per sistemi embedded multiprocessore che operano in ambienti aperti e imprevedibili. Gli algoritmi di scheduling tradizionali, come il Rate Monotonic (RM) e l'Early Deadline First (EDF), si basano su ipotesi di loop aperto dove la mappatura dei task e il tempo di esecuzione peggiore (Worst Case Execution Time - WCET) sono predefiniti. Tuttavia, negli scenari reali, i tempi di esecuzione sia per i task di sicurezza critica (Safety Critical - SC) che per quelli non-SC variano a causa dell'incertezza ambientale, portando a potenziali mancate scadenze (deadline miss) e a un sotto o sovra-utilizzo delle risorse. Inoltre, gli esistenti algoritmi di scheduling basati su controllo feedback (Feedback Control Scheduling Algorithms - FCSA) spesso non forniscono soluzioni ottimali sotto fluttuazioni dinamiche del carico, e gli attuali design di tolleranza ai guasti (Fault Tolerance - FT) separano frequentemente le preoccupazioni, assumendo mappature fisse che non tengono conto dei guasti di sistema. Gli autori identificano una lacuna nella letteratura riguardante un approccio unificato che integri l'adattamento online, la tolleranza ai guasti e il controllo feedback per sistemi multiprocessore al fine di garantire la Qualità del Servizio (QoS) e l'osservanza delle scadenze.

Metodologia
La metodologia proposta introduce un Algoritmo di Scheduling per il Controllo Feedback Adattivo Online e Tollerante ai Guasti progettato per una piattaforma hardware distribuita a memoria condivisa. L'architettura del sistema consiste in nodi multiprocessore dove ogni nodo contiene due core: uno dedicato ai task SC e l'altro ai task non-SC. L'algoritmo di scheduling opera sopra un Sistema Operativo Real-Time (RTOS) utilizzando la preempzione a priorità fissa.

Il nucleo della metodologia prevede un sistema di controllo a ciclo chiuso con i seguenti componenti:

1. Modello di Sistema: Il sistema multiprocessore è modellato come un sistema non lineare, a molteplici ingressi e molteplici uscite (MIMO). Gli ingressi di controllo sono i periodi dei task (frequenze di campionamento) e la variabile di uscita è l'utilizzo della CPU misurato.
2. Design del Controller: Gli autori impiegano un Controller Adattivo Online composto da due elementi principali:
   • Stimatore del Modello tramite Minimi Quadrati Ricorsivi (RLS): Questo componente utilizza un fattore di dimenticanza esponenziale per identificare online i parametri variabili nel tempo del modello di sistema. Aggiorna i coefficienti del modello per adattarsi alle mutevoli condizioni di runtime e alle deviazioni dei tempi di esecuzione.
   • Controller Ottimale Lineare Quadratico (LQ): Questo controller minimizza una funzione di costo quadratica per seguire un comando di riferimento (utilizzo della CPU desiderato) penalizzando al contempo le grandi variazioni negli input di controllo. La funzione di costo bilancia l'accuratezza del tracciamento rispetto all'entità degli aggiustamenti di controllo.
3. Integrazione della Tolleranza ai Guasti: Il design incorpora meccanismi di tolleranza ai guasti (come concetti di replica attiva, ri-esecuzione o checkpointing menzionati nello sfondo) per garantire che i task SC rispettino le scadenze anche in presenza di guasti transitori o permanenti. Il controller mira a mantenere l'utilizzo della CPU entro un limite di schedulabilità nonostante tali guasti.

Contributi Chiave

• Integrazione Novativa: Il documento presenta una metodologia che integra l'adattamento online, la tolleranza ai guasti e lo scheduling feedback specificamente per sistemi embedded multiprocessore, sostenendo che questo sia il primo lavoro ad affrontare questi tre elementi insieme in questo contesto.
• Meccanismo Adattivo: A differenza dei design FCSA statici o non adattivi, l'algoritmo proposto utilizza uno stimatore basato su RLS per aggiornare dinamicamente il modello di sistema, permettendogli di gestire le fluttuazioni dinamiche del carico e le variazioni dei tempi di esecuzione senza conoscere preventivamente i reali tempi di esecuzione dei task.
• Strategia di Controllo Robusta: L'uso di un controller LQ consente di ottimizzare le prestazioni della CPU e l'utilizzo delle risorse mantenendo il sistema su un set-point di utilizzo desiderato, evitando così il sovraccarico e minimizzando i rapporti di mancata scadenza.

Risultati Sperimentali
Gli autori hanno validato la metodologia attraverso tre esperimenti focalizzati sul controllo dell'utilizzo della CPU:

1. Scenario di Sotto-utilizzo: Partendo con tempi di esecuzione effettivi pari al 30% dei valori stimati (sotto-utilizzato), il controller ha aumentato con successo le frequenze dei task, facendo convergere l'utilizzo della CPU di entrambi i processori verso il set-point desiderato di 0.8123.
2. Scenario di Sovra-utilizzo: Con i tempi di esecuzione effettivi impostati a sette volte i valori stimati (grave sovra-utilizzo), il controller ha diminuito le frequenze dei task. Nonostante le oscillazioni iniziali causate dalle imprecisioni della stima del modello, il sistema è rapidamente convergente al set-point di 0.8123.
3. Robustezza a Carichi Dinamici: Il sistema è stato sottoposto a cambiamenti dinamici del carico in intervalli specifici (al 300°, 400° e 800° step di campionamento). Il controller adattivo online ha mantenuto l'utilizzo al set-point con oscillazioni minime, dimostrando robustezza contro improvvise fluttuazioni del carico.

I risultati indicano che il sistema rimane stabile anche quando i tempi di esecuzione effettivi sono significativamente più alti delle stime (fino a un fattore di 7), a condizione che i task rispettino le loro scadenze. Tuttavia, gli autori osservano che se i tempi di esecuzione superano questa soglia, il sistema diventa instabile, portando a oscillazioni e mancate scadenze.

Significatività e Rivendicazioni
Il documento sostiene che la metodologia proposta offre un approccio superiore per il co-design controllo-scheduling in sistemi embedded multiprocessore fornendo la QoS in termini di prestazioni della CPU e utilizzo delle risorse. La significatività risiede nella capacità di mantenere la stabilità del sistema e rispettare le scadenze per i task di sicurezza critica in presenza di guasti e cambiamenti di carico dinamici, obiettivi che i metodi tradizionali a loop aperto o non adattivi faticano a raggiungere.

Gli autori concludono che, sebbene il sistema dimostri una migliore stabilità e l'uso delle risorse, l'implementazione pratica di tali sistemi di controllo basati su scheduling feedback rimane una questione "quasi completamente aperta". Suggeriscono che il lavoro futuro potrebbe concentrarsi sullo sviluppo di modelli di utilizzo della CPU più avanzati e di controller online ibridi per migliorare ulteriormente le prestazioni complessive del sistema. Il documento non pretende di risolvere tutti i problemi di scheduling real-time, ma posiziona il suo approccio adattivo e tollerante ai guasti come un passo significativo avanti nella gestione delle incertezze degli ambienti embedded moderni.