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.
| Table of contents |
|
|
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, da il controllo del processore ad un altro processo. Si è in grado così di massimizzare l'uso di tutte le risorse.
E' importante la distinzione tra scheduling con diritto di prelazione (scheduling preemptive) e scheduling senza diritto di prelazione (scheduling non-preemptive).
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 essere più indicati in alcuni contesti piuttosto che in altri. La scelta dell'algoritmo da usare dipende da cinque principali criteri:
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 seguienti 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 p5 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 sucessiva 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
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 sucessivi vengono serviti non appena questo ha terminato la propria esecuzione, e così avviene sucessivamente 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.
Un risultato decisamente diverso da quello ottenibile, in forma teorica, dall'algoritmo ottimale SJF pari a (0+2+4)/3=2 millisecondi solamente.
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 sucessivo 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)
Quest'algoritmo non è particolarmente efficiente considerando il tempo medio d'attesa, ma in compenso consente a tutti i processi di ottenere il controllo della CPU ed evita quindi il problema dell'attesa indefinita (starvation).
E' inoltre da tenere in considerazione l'impatto dovuto ai frequenti context switch effettuati. E' necessario quindi calcolare correttamente la durata ottimale del quanto di tempo per far si che l'incidenza dei cambi di contesto sia abbastanza limitata.
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.Scheduling della CPU
Per analizzare gli algoritmi che verranno sucessivamente presentati verrà utilizzato il criterio del tempo d'attesa medio dei processi presi in considerazione.SJF
è la durata dell'n-esima operazione di CPU, la durata prevista per la sucessiva, 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. FCFS
RR
