Sistemi in tempo reale: EDF, priorità monotona e tempo di risposta
Compiti periodici, condizione di utilizzo dimostrata, EDF ottimo, limite di Liu e Layland, analisi del tempo di risposta con esempio, inversione ed ereditarietà della priorità, RTOS.
In un sistema in tempo reale un risultato giusto ma in ritardo è sbagliato: il comando dei freni di un’auto, il controllo di un motore, un pacemaker devono rispondere entro una scadenza. Non conta la velocità media, ma la garanzia nel caso peggiore. In questa lezione vediamo il modello dei compiti periodici, la pianificazione EDF con la dimostrazione della condizione necessaria, la priorità monotona con il suo limite e l’analisi esatta del tempo di risposta svolta su un esempio, l’inversione di priorità e i sistemi operativi per il tempo reale.
Il modello dei compiti periodici
Si distinguono sistemi hard, dove mancare una scadenza è un guasto (controllo di volo, airbag), e soft, dove degrada solo la qualità (riproduzione video). Molti compiti di controllo sono periodici (lezione sull’implementazione di Controlli digitali): il compito 
si attiva ogni 
, richiede al più 
di calcolo (il tempo di esecuzione nel caso peggiore) e deve finire prima dell’attivazione successiva. Il suo fattore di utilizzo è 
, e l’utilizzo totale 
.
Prima la scadenza più vicina
L’algoritmo EDF (earliest deadline first) esegue in ogni istante il compito pronto con la scadenza più vicina, con prelazione.
Teorema. Su un processore, un insieme di compiti periodici con scadenza uguale al periodo è pianificabile con un qualunque algoritmo solo se 
; con EDF la condizione è anche sufficiente.
Dimostrazione della necessità. Si consideri l’intervallo 
, dove 
è il minimo comune multiplo dei periodi. Il compito si attiva 
volte e richiede in tutto 
di calcolo, che deve essere svolto entro . La richiesta totale è 
, e il processore ne offre al più : serve 
, cioè . ∎
La sufficienza per EDF (Liu e Layland, 1973) si dimostra mostrando che, se una scadenza fosse mancata, nell’intervallo precedente il processore sarebbe stato sempre occupato da compiti con scadenze non successive, e la loro richiesta supererebbe la lunghezza dell’intervallo, cioè 
. EDF è quindi ottimo: usa il processore fino al 100 %.
Priorità monotona e tempo di risposta
Molti sistemi usano invece priorità fisse, più semplici e prevedibili in caso di sovraccarico: con la regola monotona sul periodo (RMS, rate monotonic) il compito con periodo più breve ha priorità più alta. Liu e Layland hanno dimostrato che RMS garantisce le scadenze se
![\[ U \le n\left(2^{1/n} - 1\right) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-e15564ac5f32edc6ebfb13338a7988dd_l3.png "Rendered by QuickLaTeX.com")
dove 
è il numero di compiti: 0,83 per due, 0,78 per tre, e tende a 
. La condizione è solo sufficiente; per una risposta esatta si calcola il tempo di risposta nel caso peggiore, che si ha quando tutti i compiti si attivano insieme. Per il compito 
, con i compiti più prioritari 
:
![\[ R_i = C_i + \sum_{j}\left\lceil\frac{R_i}{T_j}\right\rceil C_j \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-5bca40fbeedd58f9e9bb0696127bdf0a_l3.png "Rendered by QuickLaTeX.com")
perché durante 
ogni compito più prioritario si attiva 
volte e ogni volta lo interrompe per 
. L’equazione si risolve per iterazione partendo da 
, finché il valore non si ferma; il compito rispetta la scadenza se 
.
Esempio. Tre compiti 
: 
, 
, 
, con 
, sopra il limite di 0,78: il test sufficiente non conclude. Tempo di risposta di 
: si parte da 
; poi 
; poi 
; poi 
; poi 
; poi 
, fermo. 
: l’insieme è pianificabile, come mostra la figura.
L’inversione di priorità
Un compito ad alta priorità H aspetta un lock tenuto da un compito a bassa priorità L. Se nel frattempo si attiva un compito a priorità media M, che non usa il lock, M interrompe L, e H resta bloccato per tutto il tempo di M: un compito meno importante ritarda indirettamente il più importante, per un tempo senza limite se i compiti medi sono tanti. È l’inversione di priorità. Nel 1997 la sonda Mars Pathfinder si riavviava di continuo per questo motivo, finché da Terra non fu attivata l’opzione di ereditarietà della priorità: mentre L tiene un lock richiesto da H, L eredita temporaneamente la priorità di H, M non può interromperlo, e il blocco di H dura al più quanto la sezione critica di L. Il protocollo del tetto di priorità fa di più, e impedisce anche gli stalli tra lock.
I sistemi operativi per il tempo reale
Un sistema operativo in tempo reale (RTOS) offre scheduler a priorità con prelazione, latenze di interruzione piccole e soprattutto limitate, strumenti di sincronizzazione con ereditarietà della priorità e allocazione di memoria prevedibile. Sui microcontrollori si usano kernel piccolissimi come FreeRTOS o Zephyr, di pochi kilobyte; nei sistemi più grandi Linux con le estensioni PREEMPT_RT, che rendono interrompibile quasi tutto il kernel e portano le latenze nel caso peggiore a decine di microsecondi. Il tempo di esecuzione nel caso peggiore va misurato o calcolato con strumenti di analisi, tenendo conto delle cache e delle interruzioni: è spesso la parte più difficile del progetto.
