Scheduler

Da Wikipedia, l'enciclopedia libera.

Schema di uno Scheduler

Lo scheduler è un componente fondamentale dei sistemi operativi multitasking, cioè quelli in grado di eseguire più processi (task) contemporaneamente.

Lo scheduler si occupa di fare avanzare un processo interrompendone temporaneamente un altro, realizzando così un cambiamento di contesto (context switch). Generalmente computer con un processore sono in grado di eseguire un programma per volta, quindi per poter far convivere più task è necessario usare lo scheduler. Esistono vari algoritmi di scheduling che permettono di scegliere nella maniera più efficiente possibile quale task far proseguire: ad esempio il kernel linux dalla versione 2.4 ha uno scheduler O(1), ossia a tempo costante.

[modifica] Scheduling della CPU

Lo scheduling è un'operazione molto importante per il corretto ed efficiente funzionamento del calcolatore. Infatti non solo consente di eseguire più programmi contemporaneamente, almeno in apparenza, ma consente anche di migliorare l'utilizzo del processore. Ad esempio, quando è necessario eseguire un'operazione di I/O, il processore non può proseguire l'elaborazione del processo attualmente in esecuzione fino al completamento della stessa. Dato che le operazioni di I/O sono molto più lente del processore sarebbe un'inutile spreco di risorse se il processore rimanesse bloccato fino al completamento delle stesse. Per evitare questo le operazioni di I/O vengono gestite unicamente dal Sistema operativo che, nel frattempo, dà il controllo del processore ad un altro processo. Si è in grado così di massimizzare l'uso di tutte le risorse. È importante la distinzione tra scheduling con diritto di prelazione (scheduling preemptive) e scheduling senza diritto di prelazione (scheduling non-preemptive o scheduling cooperative). Nel primo caso lo scheduler può sottrarre il possesso del processore al processo anche quando questo potrebbe proseguire nella propria esecuzione. Nel secondo caso, invece, lo scheduler deve attendere che il processo termini o che cambi il suo stato da quello di esecuzione a quello di attesa o di pronto, a seguito, ad esempio, di una richiesta di I/O oppure a causa di un segnale di interruzione (interrupt).

Esistono vari algoritmi di scheduling che tengono conto di varie esigenze e che possono essere più indicati in alcuni contesti piuttosto che in altri. La scelta dell'algoritmo da usare dipende da cinque principali criteri:

Utilizzo del processore: la CPU (ovvero il processore) deve essere attivo il più possibile, ovvero devono essere ridotti al minimo i possibili tempi morti.
Produttività: il numero di processi completati in una determinata quantità di tempo.
Tempo di completamento: il tempo che intercorre tra la sottomissione di un processo ed il completamento della sua esecuzione.
Tempo d'attesa: il tempo in cui un processo pronto per l'esecuzione rimane in attesa della CPU.
Tempo di risposta: il tempo che trascorre tra la sottomissione del processo e l'ottenimento della prima risposta.

Per analizzare gli algoritmi che verranno successivamente presentati verrà utilizzato il criterio del tempo d'attesa medio dei processi presi in considerazione.

[modifica] SJF

L'algoritmo SJF, shortest job first, prevede che venga eseguito sempre il processo con il tempo di esecuzione più breve tra quelli in attesa. Prendiamo ad esempio che siano stati sottomessi contemporaneamente i seguenti processi, con la rispettiva durata di esecuzione in millisecondi:

p1 10

p2 2

p3 6

p4 4

I processi vengono eseguiti nel seguente ordine: p2 -> p4 -> p3 -> p1

Non tenendo in considerazione il tempo necessario per il context switch, il processo p2 non attende nulla, perché entra subito in esecuzione, p4 attende 2 millisecondi, perché entra in esecuzione subito dopo p2, quindi p3 attende 6 millisecondi e p1 ne attende 12. Il tempo medio d'attesa è pari a (0+2+6+12)/4= 5 millisecondi.

Per correttezza il seguente algoritmo dovrebbe essere nominato shortest next CPU burst in quanto viene considerato la lunghezza della successiva operazione di CPU e non quella totale, tuttavia è spesso indicato con SJF.

Si può dimostrare che questo algoritmo è ottimale, in quanto consente di ottenere sempre il valore più basso di tempo d'attesa medio. Sfortunatamente non è possibile applicarlo, in quanto non è possibile conoscere anticipatamente quanto durerà l'esecuzione del processo. Tuttavia si può provare a predirlo, in quanto è probabile che sia simile ai precedenti.

Una tecnica comunemente usata è quella di utilizzare la seguente formula ricorsiva

$T n + 1 = a t n + (1 - a) T n$

$t n$ è la durata dell'n-esima operazione di CPU, $T n + 1$ la durata prevista per la successiva, e a, compreso tra 0 ed 1, è il peso che deve essere assegnato al passato del processo. In genere il valore assegnato ad a è 1/2. Questo consente di avere una discreta approssimazione del comportamento del processo e consente comunque di ottenere un discreto risultato.

L'algoritmo SJF può essere sia con prelazione sia senza. Nel primo caso viene definito anche shortest remaining time first, e si differenzia per il fatto che, quando viene sottomesso un nuovo processo la cui durata è minore del tempo necessario al processo in esecuzione per portare a terminare la propria sessione, lo scheduler provvede a sostituire i processi.

[modifica] FCFS

L'algoritmo FCFS, first come first served, esegue i processi nello stesso ordine in cui essi vengono sottomessi al sistema. Il primo processo ad essere eseguito è esattamente quello che per primo richiede l'uso della CPU. Quelli successivi vengono serviti non appena questo ha terminato la propria esecuzione, e così avviene successivamente per tutti gli altri posti in coda. Questo tipo di algoritmo è molto semplice da implementare ma solitamente è anche poco efficiente, almeno considerando il tempo medio d'attesa.

Infatti, prendiamo ad esempio la sottomissione nell'ordine dei seguenti processi con la medesima durata espressa in millisecondi:

p1 10

p2 4

p3 2

Verranno eseguiti nello stesso ordine: p1 -> p2 -> p3

Il processo p1 non attende nulla, perché entra immediatamente in esecuzione. Il processo p2 attende 10 millisecondi, e p3 14. Il tempo medio d'attesa quindi è (0+10+14)/3=8 millisecondi. Si ha allora un effetto convoglio, caratterizzato dal fatto che più processi brevi attendono la terminazione di un unico processo più corposo. Un risultato decisamente diverso da quello ottenibile, in forma teorica, dall'algoritmo ottimale SJF pari a (0+2+6)/3=8/3 millisecondi solamente.

[modifica] RR

L'algoritmo di scheduling RR, round robin, è un particolare algoritmo di tipo preemptive che esegue i processi nell'ordine d'arrivo, come il FCFS, ma esegue la prelazione del processo in esecuzione, ponendolo alla fine della coda dei processi in attesa, qualora l'esecuzione duri più del quanto di tempo stabilito, e facendo proseguire l'esecuzione al successivo processo in attesa.

Ad esempio nell'ipotesi che vi siano i seguenti processi in coda con relativa durata in millisecondi, e quanto di tempo stabilito di 20 ms:

p1 30

p2 15

p3 60

p4 45

Verranno eseguiti nel seguente ordine:

p1 (interrotto dopo 20 ms, ne rimangono altri 10) ->

p2 (termina la propria esecuzione perché dura meno di 20 ms) ->

p3 (interrotto dopo 20 ms, ne rimangono altri 40) ->

p4 (interrotto dopo 20 ms, ne rimangono altri 25) ->

p1 (termina la propria esecuzione perché necessitava di meno di 20 ms) ->

p3 (interrotto dopo 20 ms, ne rimangono altri 20) ->

p4 (interrotto dopo 20 ms, ne rimangono altri 5) ->

p3 (termina la propria esecuzione perché necessitava di esattamente 20 ms) ->

p4 (termina la propria esecuzione)

Le prestazioni di quest'algoritmo sono dunque influenzate dal tempo medio d'attesa sebbene consenta a tutti i processi di ottenere il controllo della CPU ed evita quindi il problema dell'attesa indefinita (starvation).

È inoltre da tenere in considerazione l'impatto dovuto ai frequenti context switch effettuati. È necessario quindi calcolare correttamente la durata ottimale del quanto di tempo per far si che l'incidenza dei cambi di contesto sia abbastanza limitata come anche i tempi di attesa. Si può stabilire che, per un funzionamento ottimale, le sequenze di operazioni di CPU dovrebbero essere più brevi del quanto di tempo stabilito in circa l'80 per cento dei casi.

[modifica] Multilevel Feedback

Non potendo stimare con precisione il tempo di esecuzione di un processo nel momento in cui entrerà nel sistema, vi è la possibilità di stimare il tempo trascorso. viene introdotto il concetto di Feedback secondo il quale si penalizzano i processi che hanno speso più tempo nel sistea. lo scheduling multilevel Feedback è uno scheduling basato su quanto di tempo ed utilizza un meccanismo di priorità dinamica. Quando un processo entra nel sistema si accoda nella coda a più alta priorità, dopo la prima esecuzione esso ritorna in stato di pronto andando però nella coda a priorità subito più bassa della precedente e così via sino ad arrivare alla coda dei processi pronti con priorità più bassa.

Ogni coda è gestita attraverso l'algoritmo di Round Robin, tutte tranne l'ultima che è servita tramite FCFS. caratteristiche:

Favorisce processi più corti
Con alcuni accorgimenti è possibile evitare condizioni di Starvation

[modifica] Voci correlate

[modifica] Bibliografia

Sistemi operativi, concetti ed esempi (A. Silbershatz, P. Baer Galvin, G. Gagne, 2003, editore Pearson Educational, ISBN 8871921402). Sistemi operativi, Gestione dei processi, gestione della memoria, I/O.
Architettura dei Sistemi di Elaborazione, volume 1 (F. Baiardi, A. Tomasi e Marco Vanneschi, 1988, editore Franco Angeli, ISBN 882042746X). Fondamenti, firmware, architetture parallele . [1]
Architettura dei Sistemi di Elaborazione, volume 2 (F. Baiardi, A. Tomasi, Marco Vanneschi, 1987, editore Franco Angeli, ISBN 882042746X) Sistemi operativi, multiprocessore e distribuiti. [2]