Nei titoli e nei testi troverete qualche rimando cinematografico (ebbene si, sono un cinefilo). Se non vi interessano fate finta di non vederli, già che non sono fondamentali per la comprensione dei post...

Di questo blog ho mandato avanti, fino a Settembre 2018, anche una versione in Spagnolo. Potete trovarla su El arte de la programación en C. Buona lettura.

mercoledì 25 gennaio 2023

Edge of Real-Time
considerazioni sulla programmazione real-time - pt.1

William Cage: Lei è americano?
Sergente Farrell: No, sono del Kentucky.

Il bel Edge of Tomorrow è un film sul tempo, dove passato, presente e futuro si accavallano ed entrano in un loop infinito (ma quasi senza paradossi, notevole...), e mi offre un bello spunto per parlare della programmazione real-time, un tipo di programmazione dove il tempo gioca un ruolo fondamentale (N.B.: si parla di tempo di esecuzione, non del tempo necessario allo sviluppo di una applicazione: quello è la croce di molti programmatori, ma è tutta un'altra storia... ah ah ah).

...grazie al real-time riesco a fare anche questo...

Veniamo al dunque: cosa è una applicazione real-time? Prima di dirlo farò una piccola premessa: in questa parte sto per ripetere concetti stra-conosciuti a chi mastica già l'argomento, ripetendo spiegazioni che usano quasi le stesse frasi (al limite del plagio) e che potete trovare in mille altre pagine sull'argomento: il fatto è che non posso parlare di real-time senza introdurlo, ed è impossibile farlo senza che sembri una copia di una descrizione già vista (giuro: ho trovato articoli sul real-time che sembrano fatti col copia-e-incolla, ma è inevitabile: sono quatto argomenti ben precisi e sintetici, ed è difficile descriverli in maniera molto originale). Indi per cui: chi vuole può saltare tutta l'introduzione, anzi può andare direttamente al "Ciao, e al prossimo post!". Saluti e baci.

E torniamo al dunque:

"una applicazione real-time è una applicazione che esegue le sue attività con dei tempi garantiti"

Questa frase è del sottoscritto, l'ho sfornata proprio ora, ma magari l'ho copiata: il subconscio gioca brutti scherzi e ho letto molta (forse troppa) roba su questo argomento. La frase qua sopra nasconde già una insidia: "ma allora un sistema veloce è un sistema real-time!". La risposta è NO: una applicazione veloce, ben scritta con un linguaggio adatto (in C, no? Se no che ci stiamo a fare qui?) e che gira su un computer molto veloce dotato di un buon sistema operativo (Linux, ovviamente...) potrebbe dare l'impressione di essere real-time con la sua grande velocità di risposta, ma in realtà non garantisce SEMPRE la velocità che ti aspetti, quindi non è veramente real-time. La parte importante della frase qui sopra è "tempi garantiti", magari lunghi, ma garantiti.

Il caso che ho appena descritto come sbagliato offre lo spunto per il passo successivo: una applicazione real-time non è solo una applicazione, ma è un vero e proprio sistema composto da Sistema Operativo + Software + Hardware:

  1. Sistema Operativo: deve essere di tipo real-time (RTOS per gli amici).
  2. Software: deve essere scritto rispettando lo "stile real-time" previsto dal RTOS prescelto, usando un linguaggio adatto (tipicamente il C, ma se ne usano anche altri).
  3. Hardware: deve essere adatto alle esigenze del RTOS prescelto.

Devo evidenziare una caratteristica della tabellina qua sopra: tutti i punti elencati sono condizioni necessarie ma non sufficienti, nel senso che o sono rispettati tutti e tre o non potremo ottenere prestazioni real-time.

(...ho saltato un caso particolare che non è argomento di questa trattazione: è possibile realizzare sistemi con prestazioni real-time anche programmando Hardware senza sistema operativo (programmazione "bare-metal"), in C o addirittura in Assembler, ma anche questa è un altra storia...)

Ci manca solo un ultimo punto da descrivere: esiste un solo tipo di real-time? No, ce ne sono due, Hard e Soft (più un terzo, il Firm, che praticamente corrisponde col Soft, quindi lo saltiamo):

  • Hard real-time: è, in realtà, l'unico che può fregiarsi del titolo real-time: un sistema di questo tipo garantisce i tempi previsti SEMPRE. In gergo del settore: "non tollera il fallimento di nessuna deadline" dove per deadline si intende il limite temporale massimo oltre il quale una attività DEVE essere completata, pena il degrado irrimediabile del sistema controllato (provate a pensare a una centrale nucleare controllata da un sistema non real-time... bum!).
  • Soft real-time: si comporta, NORMALMENTE, come un vero sistema real-time, ma tollera il fallimento di QUALCHE deadline sporadica, con un degrado di funzionamento statisticamente accettabile.

E adesso non ci sta male una breve panoramica (non esaustiva e, perlopiù, soggettiva: metterò solo quelli che mi piacciono) dei sistemi operativi, di tipo RTOS, disponibili e raccomandabili per realizzare sistemi Hard real-time:

  • QNX - Proprietario, POSIX-compliant. È un vero e proprio UNIX real-time, basato su un microkernel real-time.
  • LynxOS - Proprietario, POSIX-compliant. Anche questo è un vero e proprio UNIX real-time, basato su un kernel monolitico real-time.
  • VxWorks - Proprietario, POSIX-compliant. Molto completo, basato su un kernel monolitico real-time.
  • RT-Linux - Open source, POSIX-compliant. È, in parole povere, un microkernel real-time su cui gira un Linux standard come processo a bassa priorità.
  • RTAI-Linux - Open source, POSIX-compliant. È, come RT-Linux, un microkernel real-time su cui gira un Linux standard come processo a bassa priorità.
  • NuttX - Open source, POSIX-compliant. Molto compatto e, quindi, adatto anche a sistemi embedded semplici. Basato su un microkernel real-time.

E, fuori dalla lista (perché non è un sistema operativo completo), aggiungerei anche il buon FreeRTOS, un RTOS compattissimo e leggerissimo (è quasi solo uno scheduler) studiato ad-hoc per sistemi embedded semplici che non necessitano di tutte le funzionalità avanzate fornite dai sistemi POSIX. È una ottima alternativa (ma non è l'unica) alla programmazione embedded "bare-metal", quella senza sistema operativo.

Una parentesi a parte la merita il Linux standard, che, dal kernel 2.6 in avanti, ha delle estensioni real-time che si possono attivare ed usare congiuntamente a una scheduling-policy dello scheduler di tipo SCHED_FIFO o SCHED_RR (al posto di quella di default, che è SCHED_OTHER, come già citato nel mio articolo sulla sched_yield(2)). In questa maniera Linux standard può eseguire egregiamente attività di tipo Soft real-time. Meglio che niente, no?

E un'altra parentesi bisogna spenderla sulle prestazioni assolute di questi RTOS: anche se nella introduzione dell'articolo ho ricalcato sul fatto che il real-time è "rispetto dei tempi" e non necessariamente velocità, tutti gli RTOS descritti sopra sono anche velocissimi, perché, essendo progettati per adempiere ai compiti più svariati, devono per forza tentare di fornire "tempi garantiti" anche quando si ha bisogno di risposte velocissime (avionica, centrali nucleari, ecc.). Quindi, ad esempio, QNX e compagni hanno tempi di latenza per le interruzioni e tempi di context-switch dell'ordine dei microsecondi (!). Invece Linux standard in modo soft real-time può fornire prestazioni dell'ordine dei millisecondi (e anche in questo caso: meglio che niente, no?).

Per oggi può bastare, abbiamo analizzato il punto 1 della prima tabella (lo ammetto, ho descritto cose abbastanza semplici da reperire qui e là, ma almeno qua le trovate tutte insieme...). Nella seconda parte (che non necessariamente sarà il prossimo articolo...) parleremo del punto 2 della tabella, il Software in stile real-time, che è un argomento un pelino più complicato. E, ancora una volta, non trattenete il respiro nell'attesa!

Ciao, e al prossimo post!

venerdì 16 dicembre 2022

A History of Sched_yield
considerazioni sull'uso della sched_yield(2) su Linux

Joey: Richie, io sono qui per fare pace... dimmi che devo fare per mettere le cose a posto.
Richie: Una cosa la potresti fare, credo... potresti morire, Joey.

Questo articolo ha un argomento spinoso, esattamente come l'argomento trattato nel bellissimo A History of Violence del Maestro David Cronenberg, caratterizzato da una trama ambigua che è una sequenza di pacifiche e tranquillizzanti scene familiari intervallata da improvvisi momenti di iper-violenza. Qui mi tocca tornare su un argomento che ho trattato solo di striscio, l'uso della system-call sched_yeld(2), che ho usato in un esempio di un mio vecchio articolo e, con l'intenzione di essere il più possibile preciso, sono costretto a rivedere un po' l'esempio, dato che quello proposto lì non era valido universalmente, anzi era valido solo per usi particolari. Mi fascio la testa...

...sched_yield, o non sched_yield, questo è il dilemma...

La spinta alla scrittura di questo articolo mi è venuta leggendo un bell'articolo, questo: To sched_yield() Or Not To sched_yield()? (che ho citato nella didascalia qua sopra, ah ah ah). L'articolo in questione, oltre ad alcune interessanti note teoriche, contiene anche un bel benchmark realizzato su una vera macchina multiprocessore (perfetta per test di multiprocessing e/o multithreading reali), nientepopodimeno che un Cray con 256 CPU (con Linux, ovviamente: vi siete mai chiesto perché i super-computer usano quasi sempre Linux, qualche volta UNIX, e quasi mai Windows? Beh, chiedetevelo...). Visto che io non ho a disposizione un mostro del genere non vi proporrò nessun benchmark, quello del'articolo citato è più che sufficiente per mostrare che usare la sched_yield(2) non sempre è una buona idea. Per chi non lo ricordasse la sched_yield(2) fa questo:

sched_yield - cede il processore

sched_yield() fa sì che il thread chiamante rinunci alla CPU. Il thread viene
spostato alla fine della coda per la sua priorità statica e un nuovo thread
viene eseguito.

E veniamo al dunque: il mio vecchio articolo (in due puntate) parlava più che altro di sleep (se avete voglia potete rileggerlo) e qui vi farò un breve riassunto della solo parte che ci interessa oggi. E allora: avevo proposto una funzione di sleep in millisecondi che, in maniera intelligente, decideva se usare nanosleep(2), usleep(3) o sched_yield(2), in base alle esigenze e disponibilità. Vai col codice!

// Sleep() - una sleep in ms
void Sleep(unsigned int milliseconds)
{
// testa il tempo di sleep per intercettare il valore 0
if (milliseconds > 0) {
// usa nanosleep() o usleep()
#if (_POSIX_C_SOURCE >= 199309L)
struct timespec ts;
ts.tv_sec = milliseconds / 1000;
ts.tv_nsec = ( milliseconds % 1000) * 1000000;
nanosleep(&ts, NULL);
#else
usleep(milliseconds * 1000);
#endif
}
else {
// usa sched_yield() come alternativa Linux alla Sleep(0) di Windows
sched_yield();
}
}

Quindi avevo applicato questa nuova Sleep() a un semplicissimo programma con due thread usandola come sleep di un loop infinito (il codice ve lo risparmio, comunque è consultabile nel vecchio articolo). Grazie a questo codice avevo realizzato un piccolo benchmark per provare la famigerata Sleep(0) (di origine Windows) e l'effetto reale che si otteneva cambiando il valore di sleep del loop: nella tabella seguente ci sono i risultati originali (con una macchina Linux con un i7 con 4 core e 8 thread). Per i casi inferiori al millisecondo avevo modificato il codice per usare direttamente la obsoleta (ma in questo caso comoda) usleep(3), e i dati si riferiscono all'uso di CPU e al numero "i" di cicli effettuati dai thread:

senza sleep i = 5314563827 CPU = 100%
Sleep(0) i = 18863299 CPU = 100% (esegue sched_yield())
Sleep(10) t=10ms i = 900 CPU = 1/2%
Sleep(1) t=1ms i = 9000 CPU = 1/2%
usleep(100) t=100us i = 62970 CPU = 1/2%
usleep(10) t=10us i = 145000 CPU = 1/2%
usleep(1) t=1us i = 170000 CPU = 1/2%
usleep(0) t=0us i = 170000 CPU = 1/2% (test con usleep(0))

Ora, citerò direttamente il vecchio articolo, che diceva:

Il primo caso ci mostra perché qui conviene usare la sleep: i nostri due thread funzionano bene (i due contatori avanzano simultaneamente), e la attività è gestita dal thread-scheduler (facile in questo caso: un thread dell'applicazione su un thread della CPU), ma comunque, se non lavorano volontariamente in maniera cooperativa (o gentile, se preferite) e non rilasciano ogni tanto la CPU, finiscono col mangiarsela tutta (due degli otto CPU-thread, nel mio caso), e in un sistema multi-process non è una buona cosa, no?.

Esaminiamo, ora, il secondo caso che ci dimostra che la famosa Sleep(0)/sched_yield() di cui abbiamo parlato nell'altro articolo non da proprio dei gran risultati: i thread lavorano meno (guardare il counter) ma la CPU va lo stesso al 100%.

Il terzo e il quarto caso ci mostrano che, usando valori dell'ordine di grandezza del time-slice del sistema, la CPU lavora poco e il comportamento è lineare (fino a 1 ms).

I casi successivi mantengono il rispetto della CPU ma il comportamento diventa irregolare (i counter non aumentano proporzionalmente alla riduzione della sleep). Conclusione: in questa tipo di architettura Software (che è un buon riferimento, essendo abbastanza comune) è conveniente usare dei tempi paragonabili al time-slice del sistema, ossia tra 1 e 10 ms.

L'ultimo caso l'ho aggiunto solo per curiosità, per confermare quanto detto nell'altro articolo: usleep(0) non è equivalente a Sleep(0) (magari qualcuno non ci credeva...) e applica il tempo di sleep minimo possibile, che è di 1 us.

E torniamo al presente: come si può ben notare la sched_yield(2) non dava dei gran risultati, però l'avevo lasciata ugualmente nel codice della nuova Sleep() a mo' di "funziona male, ma se proprio volete usarla...". In realtà più che funzionare male è una di quelle system-call che o si usano bene o non si usano (avevamo visto qualcosa di simile nei miei 2 articoli sulla funzione pthread_cancel(3), ricordate?), quindi ci vuole molta cautela e, alla fine della fiera, è possibile che non si debba mai usare, a parte casi particolarissimi (e questo, scusate l'OT, mi risulta vero anche per la Sleep(0) di Windows). Del resto è ben scritto anche nel manuale della sched_yield(2):

Chiamate strategiche a sched_yield() possono migliorare le prestazioni dando ad
altri thread o processi la possibilità di funzionare quando risorse (fortemente)
contese (e.g.: dei mutex) sono state rilasciate dal chiamante. Evitate di
chiamare sched_yield() inutilmente o in modo inappropriato (ad esempio, quando
le risorse necessarie ad altri thread schedulabili sono ancora in possesso del
chiamante), poiché ciò comporterà inutili commutazioni di contesto, con
conseguente peggioramento delle prestazioni del sistema.

e, soprattutto, in questo paragrafo (sempre nel manuale):

sched_yield() è destinato all'uso con politiche di schedulazione in tempo reale
(ad esempio, SCHED_FIFO o SCHED_RR). L'uso di sched_yield() con politiche di
schedulazione non deterministiche come SCHED_OTHER non è specificato e molto
probabilmente significa che il progetto dell applicazione non è corretto.

E, solo come curiosità, vi segnalo anche una nota dal manuale Red Hat Enterprise Linux for Real Time che indica che anche in ambito real-time la sched_yield(2) è da usare con parsimonia (per i processi, ma per i thread il discorso dovrebbe essere simile):

La funzione sched_yield è stata originariamente progettata per indurre un
processore a selezionare un processo diverso da quello in esecuzione. Questo
tipo di richiesta è incline a fallire quando viene emessa da un'applicazione
mal scritta.
Quando la funzione sched_yield() viene utilizzata all'interno di processi con
priorità in tempo reale, può presentare un comportamento inaspettato. Il processo
che ha chiamato sched_yield viene spostato in coda alla coda dei processi in
esecuzione con quella priorità. Quando questo accade in una situazione in cui non
ci sono altri processi in esecuzione con la stessa priorità, il processo che ha
chiamato sched_yield continua la sua esecuzione. Se la priorità di questo processo
è alta, può potenzialmente creare un busy loop, rendendo la macchina inutilizzabile.
In generale, non utilizzare sched_yield su processi in tempo reale.

Ebbene si, il codice che proposi non era realmente universale, perché la sched_yield(2) si dovrebbe usare (con molta cautela) solo quando Linux usa uno scheduler di tipo real-time (SCHED_FIFO o SCHED_RR), e questo è un caso particolare, visto che il caso normale (il default) di Linux è l'uso dello scheduler  SCHED_OTHER. E quindi? Beh, devo aggiornare l'esempio, che ora si presenta così:

// Sleep() - una sleep in ms
void Sleep(unsigned int milliseconds)
{
// check se il tempo di sleep è zero
if (milliseconds == 0)
milliseconds = 1; // forza 1ms

#if (_POSIX_C_SOURCE >= 199309L)
// uso nanosleep(2)
struct timespec ts;
ts.tv_sec = milliseconds / 1000;
ts.tv_nsec = (milliseconds % 1000) * 1000000L;
nanosleep(&ts, NULL);
#else
// uso usleep(3) - NOTA: POSIX.1-2001 dichiara questa funzione come obsoleta
usleep(milliseconds * 1000);
#endif
}

Volendo si potrebbe migliorare questo codice forzando l'uso della sched_yield(2) quando i milliseconds sono 0 e lo scheduler (che si può ottenere usando sched_getscheduler(2)) è SCHED_FIFO o SCHED_RR, ma, essendo questo un caso molto particolare (e da usare con le molle) non mi sembrava il caso di farlo. Notare che ho forzato l'uso di una sleep minima di 1 ms coerentemente con i risultati del mio benchmark qui sopra, dove è dimostrato che un valore ottimale di sleep minima è quello dell'ordine di grandezza del time-slice del sistema.

E per oggi può bastare, ho messo i puntini sulle i, anche se mi è costato un poco ammettere di non avere, a suo tempo, fornito un esempio veramente rigoroso. Eh si, Errare Humanum Est...

Ciao, e al prossimo post!