Come funziona lo scheduling nei sistemi real-time?

Gli eventi a cui un sistema real-time deve poter reagire possono essere classificati in:

1. periodici, che si verificano ad intervalli di tempo regolari;
2. aperiodici, che si verificano in modo imprevedibile.

Nel caso di eventi periodici, se esistono m eventi e se l’evento i arriva con periodo Pi e richiede Ci secondi di tempo di CPU per essere gestito, il carico può essere gestito solo se la sommatoria da i=1 a m del rapporto Ci/Pi è minore uguale ad 1.

Un sistema real-time che rispetta questo vincolo è detto schedulabile. Gli algoritmi di scheduling real time possono essere distinti in:

1. statici: la decisione di schedulazione è presa prima che il sistema inizi l’esecuzione dei processi. Questi metodi richiedono che le informazioni complete circa il lavoro da fare e le scadenze da rispettare siano disponibili in anticipo rispetto all’esecuzione dei processi
2. dinamici: la decisione di schedulazione è presa durante l’esecuzione dei processi. Non hanno restrizioni circa la conoscenza anticipata sui tempi di esecuzione e le scadenze da rispettare.

Nel seguito verranno analizzate alcune politiche di scheduling real time, facendo riferimento al particolare contesto delle applicazioni multimediali. Infatti, i sistemi operativi che supportano applicazioni multimediali, differiscono da quelli tradizionali per tre aspetti principali:

• la schedulazione dei processi
• il file system
• la schedulazione del disco

Schedulazione di processi omogenei

La schedulazione di processi omogenei è la situazione che si presenta quando più processi con uguali richieste e vincoli temporali devono essere serviti in modo efficiente dalla politica di scheduling. Ad esempio, una tale situazione si presenta per un server video che deve supportare la visualizzazione di un numero fisso di video tutti caratterizzati dalla stessa frequenza dei frame (frame rate), risoluzione video, frequenza di trasmissione dati, etc.
In questa situazione una semplice ma efficace politica di scheduling è il round-robin. Infatti, tutti i processi sono ugualmente importanti, hanno la stessa quantità di lavoro da svolgere e si bloccano quando hanno terminato l’elaborazione del frame corrente. L’algoritmo di schedulazione può essere ottimizzato aggiungendo un meccanismo di temporizzazione per assicurare che ogni processo sia eseguito alla frequenza corretta.

Schedulazione generale in tempo reale

Il semplice modello precedente si presente raramente nella pratica. Un modello più realistico prevede la presenza di più processi che competono per l’uso della CPU, ciascuno con il proprio carico di lavoro e le proprie scadenze temporali. Nel seguito supporremo che il sistema conosca la frequenza con cui eseguire ciascun processo, quanto lavoro debba compiere ogni processo e la successiva scadenza temporale.
Come esempio di ambiente in cui lavori uno schedulatore multimediale in tempo reale si considerino i tre processi A, B e C. Il processo A viene eseguito ogni 30ms e ogni frame richiede 10ms di tempo di CPU. In assenza di competizione sarebbe eseguito nei periodi A1, A2, A3, ecc, ciascuno 30ms dopo il precedente. Ogni periodo di CPU gestisce un frame e ha una scadenza, cioè deve terminare prima che inizi il successivo. I processi B e C in sono eseguiti rispettivamente 25 e 50 volte al secondo, con tempi di calcolo di 15ms e 5ms.
Il problema diventa quello di schedulare A, B e C per essere certi che rispettino ciascuno le proprie scadenze temporali. Prima di cercare un algoritmo di schedulazione, è necessario valutare se questo insieme di processi sia effettivamente schedulabile. A questo fine è possibile utilizzare l’Eq. (1), che nel caso dei processi A, B e C dell’esempio produce: 10/30+15/40+5/50 = 0.808 del tempo di CPU, ed il sistema dei processi è quindi schedulabile.
Esistono sistemi in tempo reale in cui i processi possono subire o meno prelazione. Nei sistemi multimediali i processi sono generalmente prelazionabili: un processo la cui scadenza temporale sia a rischio può interrompere il processo in esecuzione prima che esso completi l’elaborazione del proprio frame; quando ha terminato, il processo precedente può continuare.