Schedulazione dei processi

Schedulazione dei processi

La componente del S.O. che opera i cambiamenti di stato di un processo è lo schedulatore. Lo schedulatore implementa le politiche di gestione dei processi. Ci sono diversi tipi di schedulazione che sono eseguiti con frequenza crescente, passando dalla schedulazione a lungo termine a quella a medio termine, per finire a quella a breve termine.

Una buona politica di schedulazione mira a:

• Massimizzare la percentuale di utilizzo della CPU.
• Massimizzare il throughput (portata, capacità di lavorazione) del sistema. Il throughput è misurato come il numero di processi completati nell’unità di tempo.
• Minimizzare il sovraccarico del processore.
• Minimizzare il tempo di turnaround. Il tempo di turnaround (tempo di circolazione) è il tempo che passa tra la sottomissione di un processo e la sua fine.
• Minimizzare il tempo di risposta dei processi interattivi. È il tempo impiegato dal processo a fornire il primo output.
• Prevenire la situazione di starvation (inedia). È la situazione per la quale un processo non viene mai eseguito. Anche i processi a bassa priorità prima o poi devono essere completati.

Algoritmi di schedulazione

Gli algoritmi di schedulazione possono essere classificati secondo due categorie:

• Schedulazione senza prelascio (non preemptive scheduling), cioè un processo running non può essere interrotto durante l’esecuzione. Dopo aver ottenuto il processore, il processo prosegue nell’esecuzione sino alla fine o sino a quando si interrompe per fare un’operazione di input/output o per un’altra ragione.
• Schedulazione con prelascio (preemptive scheduling), cioè un processo running può essere interrotto e portato nello stato ready per lasciare il posto ad altri processi. Questo avviene sia per l’arrivo di un nuovo processo ad elevata priorità, sia per l’intervento dell’orologio di sistema (TIMER) allo scadere del quanto di tempo assegnato a un processo.

Schedulazione FCFS

FCFS (First Come First Served, primo arrivato primo servito) è una politica di schedulazione senza prelascio, secondo la quale i processi sono eseguiti nell’ordine di arrivo.

Un nuovo processo è inserito in una coda di processi ready gestita in modalità FIFO (FIRST IN FIRST OUT). Quando un processo ottiene la CPU continua nell’esecuzione sino alla fine o finché si deve fermare in attesa di un evento. L’evento atteso, quando si presenta, causa il trasferimento di un processo dalla coda dei processi waiting nella coda dei processi ready.

Questo tipo di schedulazione usa l’ordine di arrivo come unico criterio per scegliere il processo da eseguire. Le conseguenze sono:

• Se un processo molto breve arriva subito dopo una serie di processi lunghi, attenderà molto tempo prima di essere eseguito.
• Discrimina i processi I/O bound perché i CPU-bound occupano la CPU. (P1, P2, P3, P4).

Schedulazione a priorità

Ci sono 2 situazioni che possono causare il prelascio del processo in esecuzione:

• Quando arriva un nuovo processo a priorità più elevata.
• Quando un evento causa lo spostamento di un processo a priorità più elevata dalla coda dei processi waiting a quella dei processi ready.

La priorità dei processi è controllata ogni volta che la coda dei processi ready viene aggiornata.

Schedulazione Round Robin

L’uso delle priorità porta a ritenere che ci siano processi più importanti di altri. La schedulazione Round Robin, all’opposto, considera tutti i processi egualmente importanti.

Il Round Robin è un algoritmo di schedulazione primo arrivato – primo servito con prelascio, tipico dei sistemi time sharing. È definito un intervallo temporale indicato con il termine di quantum oppure time slice, che rappresenta la quantità massima di tempo di CPU concessa a un processo. Se il processo non rilascia la CPU entro questo tempo, è interrotto e posto in coda fra i processi ready.