Antonino Mazzeo » 10.Scheduling dei processi

Lo schedulatore (o scheduler) è quella parte del S.O. preposta all’assegnazione di risorse a favore dei processi
La selezione di un processo in una coda può avvenire mediante differenti criteri, a seconda dell’algoritmo di scheduling che implementa uno schedulatore
Tipologie di Scheduler
- lo schedulatore a breve termine o scheduler della CPU
- lo schedulatore a medio termine o schedulatore di swap (swapper)
- lo schedulatore a lungo termine o schedulatore di job

Schedulatore di lungo termine

L’obiettivo dell’algoritmo di scheduling del Dispatcher è quello di allocare il processore in maniera tale da ottimizzare uno o più aspetti del comportamento del sistema
I criteri più utilizzati sono:
- User-oriented. Si riferiscono al comportamento del sistema così come percepiti dall’utente o da un processo (ad es. tempo di risposta)
- - Tempo di turnaround, Tempo di risposta, Deadlines
- System-oriented. L’obiettivo è quello di utilizzare in modo efficiente il processore (ad es. il throughput)
- - Throughput, Utilizzo della CPU, Fairness
Il progetto e l’implementazione di una politica di scheduling implica sempre un compromesso tra vari requisiti contrastanti. La scelta dovrà essere fatta tenendo conto “per cosa dovrà essere utilizzato il sistema”

I processi tipicamente sono raggrupati in classi di priorità
- l’algoritmo sceglie il processo pronto appartenente alla classe di priorità più alta
- - Problema della starvation, a cui si fa fronte utilizzando schemi di priorità dinamiche (es. Aging).
Lo scheduler di breve termine può essere
- Nonpreemptive: non può interrompere un processo in esecuzione
- Preemptive: può interrompere un processo in esecuzione
First-Come-First-Served (FCFS)
- Quando il processo cessa la sua esecuzione, viene scelto il processo che attende da più tempo
Round-Robin
- Nasce dalla trasformazione preemptive del FCFS mediante l’impiego di un timer

Shortest Process Next
- Vengono selezionati i Processi con il minor tempo di esecuzione stimato
- In genere viene utilizzata una stima basata su media esponenziale come illustrato nell’immagine:
Shortest Remaining Time
- E’ la versione Preemptive dell’alg. Shortest Process Next
- Anche in questo caso c’è il problema della stima del tempo di esecuzione

Valore stimato

Feedback
- Favorisce i processi più corti
- Utile se non si hanno indicazioni sulla lunghezza relativa dei vari processi (nel qual caso non è possibile utilizzare gli algoritmi SPN, SRT)
Multilevel Feedback
- Lo scheduling è di tipo preemptive basato su quanto di tempo
- …è utilizzato un meccanismo di priorità dinamico (se un processo usa “troppo” tempo di eleborazione CPU, viene spostato in una coda con prioirtà minore)
- - Quando un processo entra nel sistema si pone nella coda a più alta priorità (RQ0)
- - Dopo la prima prelazione il processo ritorna nello stato di ready nella coda RQ1
- - …così via fino ad arrivare alla coda a minima priorità (RQn)