Scheduling della CPU

Lo scheduling della CPU risponde alla seguente domanda : "A quale processo in attesa (processo in ready queue ) assegnare la CPU ?".
Prima di iniziare è bene ricordare che per processo si intende un programma in esecuzione e i possibili stati di un processo ,secondo appunto (senza troppa fantasia) il diagramma degli stati di un processo .

Gli algoritmi di scheduling possono essere vari ,ma i criteri da soddisfare nella scelta dell'algoritmo migliore possono essere i seguenti.

• Utilizzo della CPU . La CPU deve essere occupata il più possibile e il carico deve essere bilanciato tra i vari processori per migliorare le prestazioni.
• Throughput . E' la misura del numero di processi eseguiti nell'unita di tempo ; rappresenta la produttività della CPU. Ci possono essere processi con CPU burst lunghi o più corti .Che vuol dire? Ad esempio la CPU può eseguire un processo in un ora,poichè questo processo richiede molta elaborazione, oppure 10 processi in un secondo.
• Turnaround time: E' il tempo necessario ad eseguire un processo. Rappresenta la somma dei tempi passati dal processo nell'ingresso in memoria,nell'attesa nella ready queue,durante l'esecuzione e nelle operazioni di I/O.
• Tempo di attesa :Il tempo di attesa passato nella ready queue.
• Tempo di risposta :E' la misura del tempo che intercorre tra una richiesta e l'ottenimento di una risposta .

Si noti come è necessario aumentare i primi due punti e diminuire gli ultimi tre(infatti sono dei tempi). Di solito si preferisce ottimizzare la varianza piuttosto che i valori medi . Cioè un sistema il cui tempo di risposta sia prevedibile è migliore di un sistema con tempi di risposta migliore in alcuni casi,ma molto variabile.

Un elemento molto importante coinvolto nell'algoritmo di scheduling è il dispatcher,che è l'elemento che si occupa di fare il " lavoro sporco" .Cioè è colui che si occupa dei cambi di contesto; preleva il processo scelto dallo scheduler e passa il controllo della CPU.

Diamo ora un occhiata ai tre algoritmi di scheduling più semplici FCFS,SJF e Round Robin .

FCFS

FCFS è l'acronimo di "First Come First Served" ,tradotto significa che il primo arrivato è il primo ad essere servito .E' sostanzialmente il comportamento di una coda FIFO( per chi già la conoscesse).

E' sicuramente l'algoritmo più semplice,e come è facile intuire dal nome,la CPU viene assegnata al processo che la richiede per primo .Quando la CPU è libera viene assegnata al processo che si trova alla testa della coda . Un aspetto negativo di questo algoritmo è il tempo di attesa che può essere molto lungo( ricordo che il tempo di attesa è il tempo in attesa in ready queue) . Ad esempio ,prendendo in considerazione n processi ,di cui uno (chiamamolo P)ha CPU burst abbastanza grande ed n-1 sono veloci .Nel caso in cui il primo processo ad essere eseguito sia P gli altri processi aspettano per un tempo abbastanza lungo ,quindi il tempo medio di attesa aumenta . Inoltre l'algoritmo FCFS è senza prelazione ,cioè un processo che occupa la CPU non può essere interrotto ,trattenendola fino al momento del rilascio che avviene alla terminazione o alla richiesta di operazioni di I/O(coda di waiting).

Si noti come facendo "passare avanti" i processi con minore CPU burst il tempo medio di attesa diminuirebbe , questa è la logica seguita dal prossimo algoritmo mostrato.

SJF

SJF è l'acronimo di shortest job first . Questo algoritmo associa ad ogni processo la lunghezza della successiva sequenza di operazioni della CPU . Il processo con una minore lunghezza(più breve) di operazioni della CPU sarà quello eseguito per primo . I processi con uguale lunghezza vengono selezionati con logica FCFS. E' possibile dimostrare che questo algoritmo rende minimo il tempo di attesa per un dato insieme di processi . Ma non viene usato nello scheduler della CPU poichè sussiste un problema non di poco conto . E' facile intuirlo , come si fa a conoscere la durata della successiva richiesta della CPU? Non esiste alcun modo per determinarla ,ma in maniera "ingegneristica"  è possibile approssimarla  calcolando la cosidetta media esponenziale .

Sia Tn+1 il valore previsto per la successiva sequenza di operazioni della CPU e tn la lunghezza dell'n-esima sequenza di operazioni della CPU e sia "a" il peso associato ai due valori:

Tn+1=a*(tn)+(1-a)*Tn

tn contiene le informazioni più recenti perchè mi dice cosa è successo precendentemente, ma Tn rappresenta la storia passata ,il paramentro "a" rappresenta il peso sulla storia recente o su quella passata . In particolare "a" è compreso tra 0 e 1. 

Inoltre l'algoritmo SJF può essere con prelazione o senza prelazione . Se infatti dovesse arrivare nella ready queue un processo a cui è associata una sequenza di operazioni minore rispetto al processo che attualmente occupa la CPU,quest'ultimo viene sostituito con il processo a minore sequenza di operazioni .E il processo precedentemente in esecuzione viene posto in ready queue con una sequenza di operazioni che rappresenta il tempo residuo rimanente alla sua terminazione . L'algoritmo senza prelazione permette al processo correntemente in esecuzione di portare a termine la propria sequenza di operazioni . Lo scheduling SJF con prelazione si dice shortest remaining time first.

SJF è un caso particolare dell'algoritmo con priorità in cui si associa una priorità a ciascun processo ;infatti l'algoritmo SJF è un algoritmo con priorità in cui la priorità è l'inverso della lunghezza . Un problema relativo agli algoritmi con priorita è sicuramente la starvation che è la situazione in cui un processo con bassa priorità non viene mai servito ; è un problema serio . Sono stati scoperti addirittura processi con bassa priorità non eseguiti per anni ,è il caso dell IBM 7094 al MIT.

Una soluzione alla starvation è la tecnica dell'aging (invecchiamento) .Si tratta di far aumentare la priorità dei processi che attendono nel sistema da parecchio tempo .

Round Robin

L'algoritmo Round Robin o di scheduling circolare associa ad ogni processo un quanto di tempo( time slicing) che varia generalmente dai 10 ai 100 millisecondi . La ready queue è trattata come una coda circolare con logica FIFO,assegnando la CPU a ciascun processo per il quanto di tempo specificato.  Lo scheduler prende il primo processo dalla ready queue, imposta il timer in modo che invii un interrupt alla scadenza di un quanto di tempo e attiva il dispatcher per eseguire il processo . Le soluzioni possibili sono due : il processo termina la propria esecuzione con durata minore al quanto di tempo (bene :) ),quindi il processo rilascia volontariamente la CPU e lo scheduler passa al processo successivo ,oppure la durata della sequenza di operazioni è piu lunga di un quanto di tempo,in questo caso il timer scade e invia un interrupt al sistema operativo che esegue un cambio di contesto ,lo scheduler seleziona cosi il processo successivo secondo logica FCFS e il processo precedentemente in esecuzione viene messo nella coda circolare  . In questo caso l'algortimo è sicuramente con prelazione ,infatti un processo se non termina entro il suo quanto di tempo viene prelevato dalla CPU e riportato in ready queue.

La scelta del quanto di tempo è fondamentale . Se troppo grande ci si potrebbe portare ad un algoritmo di tipo FCFS ,se troppo piccolo si hanno troppi cambi di contesto e con conseguente overhead e rallentamento dell'esecuzione del processo. 

Si noti infine come con questo algoritmo non sussiste possibilità di starvation.