Le tecniche di scheduling alternative alla priorità fissa per lo scheduling dei processi nei sistemi real-time. L’articolo descrive l’algoritmo di scheduling EDF (Earliest Deadline First) e lo confronta con gli algoritmi tradizionali. Vengono inoltre descritte le principali tecniche di implementazione di EDF per dispositivi a microcontrollore, fornendo esempi relativi al kernel open-source ERIKA Enterprise Basic.
Le tradizionali implementazioni dei sistemi operativi real-time prevedono la possibilità di specificare dei parametri utilizzati per decidere quale sia in ogni istante il task da mettere in esecuzione. La maggior parte dei sistemi operativi in commercio fornisce per ogni task la possibilità di specificare un numero, detto priorità, utilizzato successivamente per decidere quale task mettere in esecuzione. Le priorità vengono in genere assegnate ai task in ordine di “importanza”.
L’algoritmo RM ha tra i suoi vantaggi una facile implementazione ed un facile test di schedulabilità che permette, partendo dai periodi e dai tempi di esecuzione nel caso peggiore, di comprendere se il sistema sarà o meno schedulabile, ovvero se tutti i task riusciranno a terminare entro la fine del periodo loro assegnato. In particolare ricordiamo che, per un sistema composto da N task, denominati t1…tN, con tempi di calcolo C1…CN, e periodi T1…TN, il sistema sarà schedulabile con l’algoritmo Rate Monotonic se una delle seguenti condizioni verrà rispettata:
se i periodi dei task sono armonici (ossia l’uno multiplo dell’altro)
se i periodi dei task non sono armonici. L’algoritmo RM è un algoritmo ottimo tra gli algoritmi a priorità fissa, nel senso che dato un qualsiasi assegnamento di priorità che rende il sistema schedulabile, allora l’assegnamento RM sarà schedulabile. Ma cosa succede quando RM non è in grado di schedulare un dato insieme di task? Consideriamo l’esempio in Figura 1.a. Il sistema in figura è composto da due task, t1 e t2, che hanno i seguenti parametri (Ci,Ti) t1=(4,8) t2=(5,12). Il task t1, seguendo l’algoritmo RM, ha la priorità più alta in quanto possiede il periodo più corto. Come si vede dalla figura, nel caso peggiore il task t2 non riesce a completare in tempo la sua esecuzione, in quanto il task t1 ne effettua preemption al tempo 8, anche se il sistema ha degli istanti in cui non esegue attività di nessun tipo (al tempo 22). Occorre notare che anche invertendo le priorità di t1 e t2 il sistema rimane non schedulabile. Esiste allora un modo per schedulare correttamente tale task set? In generale si. Consideriamo ad esempio la Figura 1.b: in tale figura, il task t1 non effettua preemption sul task t2 al tempo 8, permettendogli così di terminare correttamente. Il motivo per cui t1 non effettua preemption su t2 intuitivamente è dovuto al fatto che al tempo 8 (all’arrivo della seconda istanza di t1) il task t1 deve terminare la propria istanza entro l’istante 16, mentre il task t2 entro l’istante 12. In questo senso, t2 in quel momento è più urgente di t1. Questo modo di eseguire i task concorrenti è stato studiato per la prima volta nel 1973 da Liu e Layland [5], ed è stato denominato EDF, Earliest Deadline First. Secondo la tecnica di scheduling EDF, ad ogni istanza di task, al momento del suo arrivo, viene assegnata una “deadline”, ovvero un tempo assoluto entro cu il task deve terminare la propria esecuzione. La deadline assoluta di una istanza viene calcolata al momento del suo arrivo, come il tempo corrente più il periodo del task. L’algoritmo EDF ha il vantaggio di essere “ottimo” fra tutti gli algoritmi esistenti, nel senso che riesce ad utilizzare fino al 100% del tempo di CPU rispettando tutti i vincoli temporali del sistema. Ovvero, dato un insieme di task periodici caratterizzati da un tempo massimo di esecuzione Ci ed un periodo Ti, il sistema sarà schedulabile con EDF se:
(si noti che tale formula è la stessa di quella che si usa per RM nel caso di periodi armonici). EDF ha inoltre una serie di interessanti proprietà, che verranno descritte brevemente nelle prossime sezioni.
Figura 1. Una schedulazione basata su RM (a) e la corrispondente schedulazione EDF (b)
CONFRONTO FRA ALGORITMI A PRIORITÀ FISSE E ALGORITMI A PRIORITÀ DINAMICHE
Complessità di implementazione
Dal punto di vista della complessità implementativa, EDF è più oneroso di RM, in quanto il sistema operativo deve occuparsi di gestire in modo dinamico il calcolo delle nuove deadline da assegnare a ciascun Job (non necessario in RM in quanto le priorità sono fisse). Inoltre, mentre in RM è possibile implementare una tecnica di accodamento di complessità costante O(1) (tale implementazione può essere effettuata utilizzando una lista per ogni valore di priorità), con EDF è necessario implementare tecniche più complesse che prevedono il mantenimento di una lista di task ordinata di complessità O(log N) o O(N).
Overhead a runtime e numero di preemption
Se da un punto di vista puramente algoritmico EDF può avere alcuni svantaggi di implementazione, la stessa cosa non può essere detta considerando il sistema nel suo complesso. Infatti, l’overhead a tempo di esecuzione di una implementazione EDF dipende anche dal numero dei cambi di contesto che avvengono a causa dell’esecuzione dell’algoritmo di scheduling. In particolare, occorre notare come gli algoritmi a priorità fissa per loro natura impongono delle preemption non necessarie (ad esempio, all’istante 8 di Figura 1.a), che possono essere evitate utilizzando EDF. In generale, in presenza di elevato carico ed alto numero di task, il numero di preemption in algoritmi a priorità fissa cresce notevolmente, in quanto all’arrivo di un task ad alta priorità è molto probabile che il processore sia occupato con un task a bassa priorità (si veda [1] per una descrizione in dettaglio).
Robustezza durante situazioni di sovraccarico
In condizioni di sovraccarico, ovvero quando il processore deve svolgere più compiti del tempo a propria disposizione, gli algoritmi RM e EDF si comportano in modo diverso, ma comunque predicibile. In particolare, nel caso di RM, il sovraccarico può impedire l’esecuzione dei task a bassa priorità (ovvero dei task a periodo più lungo), mentre con EDF è stato dimostrato un fenomeno di “aggiustamento dei periodi”, in cui tutti i task eseguono più lentamente con una frequenza più bassa, pertanto nessun task viene penalizzato rispetto agli altri. Occorre inoltre notare che i task che non rispettano i vincoli temporali utilizzando RM in condizioni di sovraccarico possono non essere i task a più bassa priorità. In generale, un qualsiasi task a priorità non massima corre il rischio di non rispettare i propri vincoli temporali.
Jitter di esecuzione e latenza input-output
Considerando un sistema real-time, possiamo notare come i tempi di terminazione di ciascuna istanza periodica di un task dipenda dal fatto che task a più alta priorità abbiano o meno effettuato preemption sul task considerato. Con Jitter di esecuzione si intende pertanto il massimo intervallo di tempo che intercorre tra la richiesta di esecuzione di una attività periodica (non il suo inizio, che può in generale essere ritardato dalla presenza di task più importanti al momento della richiesta di esecuzione) e la sua terminazione. In generale, si può dire che EDF tende ad avere un Jitter di esecuzione inferiore a RM nel caso di carichi di esecuzione molto alti. Se si considera invece la latenza input-output di un task, ovvero la differenza tra l’istante di inizio di una attività ed il suo istante di fine, EDF si comporta decisamente meglio: infatti, è stato dimostrato che la latenza input-output di EDF è sempre inferiore a quella di RM. In generale, un basso jitter di esecuzione e una bassa latenza di input-output migliorano le performance degli algoritmi di controllo digitale, in quanto il primo indica una misura della prontezza di un sistema di controllo agli stimoli esterni, mentre la seconda influenza il ritardo introdotto dai calcoli che stanno tra l’acquisizione e l’attuazione.
IMPLEMENTAZIONE DI EDF SU SISTEMI A MICROCONTROLLORE
In questa sezione vedremo come un sistema operativo real-time che utilizza EDF, come ERIKA Entreprise Basic, possa essere implementato in modo semplice ed efficiente per sistemi a microcontrollore.
Timer circolare
La prima problematica da risolvere nell’implementazione di uno scheduler EDF su di un microcontrollore è la rappresentazione del tempo, necessaria per esprimere delle deadline assolute. Nei sistemi general purpose, in generale, è possibile usare una rappresentazione del tempo basata sulla struct timespec, definita da POSIX come una struttura contenente due interi a 32 bit per secondi e nanosecondi, con un tempo di vita superiore ai 100 anni. Tale struttura dati è in generale di complessa gestione per un microcontrollore (specialmente per la gestione dei dati a 32 bit), per cui è necessario utilizzare alcune approssimazioni che come vedremo risultano essere molto buone per gli usi più comuni. In particolare, è possibile sfruttare uno dei timer presenti sul proprio microcontrollore, e sul valore di tale timer basare una rappresentazione relativa del tempo, in cui le deadline assolute hanno senso solo per una finestra temporale pari alla metà del tempo di wraparound del timer rispetto al tempo corrente. Ovvero, dati due tempi assoluti, è sempre possibile ordinarli considerando il segno della differenza tra i due tempi (vedere Figura 2). L’utilizzo i tale tecnica, denominata del “timer circolare” ha come vantaggio una semplicità di gestione e memorizzazione dei tempi, in quanto tipicamente i timer hanno una dimensione in bytes pari a quella utilizzata per i registri dei microcontrollori, richiedendo così poche operazioni assembler per implementare la manipolazione del tempo.
Figura 2. Gestione del tempo utilizzando un timer circolare
Implementazione su ERIKA Enterprise
Come esempio di implementazione di sistema real-time che utilizza EDF proponiamo il sistema operativo ERIKA Enterprise, che nella versione 1.4.1 introduce una implementazione dello scheduler EDF implementata utilizzando la tecnica del timer circolare. In particolare, per configurare ERIKA Enterprise all’utilizzo dell’implementazione EDF, occorre specificare all’interno della sezione OS del file OIL la riga “KERNEL = EDF;” che richiede appunto l’utilizzo del kernel EDF. Successivamente, per ogni task, è possibile specificare un parametro RELDEADLINE che permette di indicare la deadline relativa che viene utilizzata per calcolare la deadline assoluta a partire dal tempo corrente. Il sistema internamente utilizzerà uno dei timer a disposizione sul microcontrollore, che verrà configurato come “free running timer” (ovvero, tale timer non genererà interruzioni) con un tempo di vita tale da gestire senza problemi task periodici con periodicità fino ad alcune centinaia di millisecondi con risoluzioni dell’ordine del microsecondo, più che sufficienti per implementare i più comuni algoritmi di controllo industriale. Per quanto riguarda la complessità implementativa dell’algoritmo EDF, si mettano a confronto le due parti di codice relative alla implementazione del test di preemption nella versione a priorità fisse ed in quella a priorità dinamiche, come mostrate nel Listato 1. Di fatto, l’implementazione EDF aggiunge un controllo sulle deadline che può essere ricondotto ad una sottrazione ed una successiva comparazione, ed è pertanto implementabile in modo efficiente anche su piccoli sistemi a microcontrollore. Per fornire un ordine di grandezza riguardo l’overhead di tale implementazione, su un microcontrollore ARM7TDMI, set di istruzioni 32 bit, a 50 MHz, il footprint totale della versione minimale di EDF aggiunge circa 300 bytes di codice (passando da 1716 bytes a 2004 bytes), mentre l’overhead di esecuzione è pari a circa 1 µs (su 5-10 µs totali) per ogni primitiva che effettua un test di preemption.
// C implementation using fixed priority
if (ready != NIL &&
system ceiling < ready prio[ready])
// C implementation using EDF with wraparound timers
if (running == NIL ||
(
ready != NIL &&
(signed)(absdline[running] - absdline[ready]) > 0 &&
system ceiling < EE th ready prio[ready]
)
)
| Listato 1 |
