Analisi esaustiva di DAG task: soluzioni per moderni sistemi real-time embedded

Modern cyber-physical embedded systems integrate several complex functionalities that are subject to tight timing constraints. Unfortunately, traditional sequential task models and uniprocessors solutions can not be applied in this context: a more expressive model becomes necessary. In this scenario, the Directed Acyclic Graph (DAG) is a suitable model to express the complexity and the parallelism of the tasks of these kinds of systems. In recent years, several methods with different settings have been proposed to solve the schedulability problem for applications featuring DAG tasks. However, there are still many open problems left. Besides schedulability, aspects like the freshness of data or reaction to an event are crucial for the performance of those kind of systems. For example, a typical application in the automotive field is composed of sensing the environment, planning, and actuate consequently to the elaborated data. Control end-to-end latency is then decisive, and it can get very complicated in real scenarios. This thesis represents an effort in both directions: (i) the schedulability of a DAG task on a multiprocessor, and (ii) the supervision of end-to-end latency for multi-rate tasks. For the former problem, a survey of the state-of-the-art of the Directed Acyclic Graph task model is presented, with a focus on scheduling tests that are more effective, easy to implement, and adopt. Regarding the latter, a method is proposed to convert a multi-rate DAG task-set with timing constraints into a single-rate DAG that optimizes schedulability, age, and reaction latency.

I moderni sistemi cyber-fisici embedded integrano diverse funzionalità complesse che sono soggette a stringenti vincoli temporali. Purtroppo, i tradizionali modelli di task sequenziali e le soluzioni per uniprocessori non possono essere applicati in questo contesto: diventa necessario un modello più espressivo. In questo scenario, il Directed Acyclic Graph (DAG) è un modello adatto a esprimere la complessità e il parallelismo dei task di questo tipo di sistemi. Negli ultimi anni sono stati proposti diversi metodi, con diverse configurazioni, per risolvere il problema della schedulabilità di applicazioni con DAG tasks. Tuttavia, rimangono ancora molti problemi aperti. Oltre alla schedulabilità, aspetti come la freschezza dei dati o la reazione a un evento sono cruciali per le prestazioni di questo tipo di sistemi. Per esempio, una tipica applicazione nel campo automobilistico è costituita dal rilevamento dell'ambiente, dalla pianificazione e dall'attuazione basata sui dati elaborati. La latenza del controllo end-to-end è quindi decisiva, e può diventare molto complicata in scenari reali. Questa tesi rappresenta uno sforzo in entrambe le direzioni: (i) la schedulabilità di DAG tasks su un multiprocessore, e (ii) la supervisione della latenza end-to-end per task a multi-frequenza. Per il primo problema, viene presentata un'indagine sullo stato dell'arte del modello di task a grafico aciclico diretto, con particolare attenzione ai test più efficaci, facili da implementare e da adottare. Per quanto riguarda il secondo, viene proposto un metodo per convertire un task-set di DAG a multi-frequenza con vincoli temporali in un DAG a singola frequenza che ottimizza la schedulabilità e la latenza end-to-end.