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.
Determina quale programma caricare nella coda dei processi pronti del sistema.
Pertanto controlla il grado di multiprogrammazione del sistema.
Ogni volta che un processo termina, lo scheduler di lungo termine dovrà sceglierne uno nuovo da caricare. La decisione è fatta secondo uno o più criteri:
Caso tipico: al fine di aumentare l’efficienza d’utilizzo delle risorse, lo scheduler di lungo termine tenta di mantenere nel sistema un numero comparabile di processi CPU-bound e I/O bound.
Rappresenta quella funzione del SO che ha il compito di trasferire temporaneamente processi (o parte di essi) dalla memoria centrale alla memoria di massa (swap-out) e viceversa (swap-in).
Viene utilizzato:
Il suo obiettivo è quello di migliorare l’efficienza nell’utilizzo della risorsa memoria.
Conosciuto anche con il nome di Dispatcher, è lo scheduler che viene attivato più frequentemente nel sistema.
Ha il compito di scegliere a quale tra i processi pronti assegnare la CPU.
Lo scheduler di breve termine viene invocato all’occorenza di un evento che comporta la sospensione del processo in esecuzione. Tra gli eventi si possono annoverare:
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:
Tempo di turnaround: è l’intervallo di tempo che trascorre dall’istante in cui un processo è sottomesso al sistema e l’istante della sua terminazione. Tiene conto del tempo effettivo di esecuzione e del tempo speso in attesa delle risorse (CPU inclusa). E’ un parametro significativo per i processi batch.
Tempo di risposta: per un processo interattivo, indica il tempo che trascorre dall’istante della sottomissione di una richiesta fino all’istante in cui la risposta inizia ad essere ricevuta, anche se il processo potrebbe continuare l’esecuzione.
Deadlines: nel caso in cui si possa specificare il termine di completamento di un processo (deadline), la disciplina di scheduling ha l’obiettivo di massimizzare la percentuale di scadenze raggiunte.
Throughput: misura la produttività di un sistema in termini di numero di processi terminati per unità di tempo. Questo parametro dipende fortemente dalla lunghezza media di un processo ma è anche influenzato dalla particolare politica adottata per la schedulazione.
Utilizzo della CPU: rappresenta la percentuale di tempo per cui il processore risulta occupato.
Fairness: salvo contrarie indicazioni da parte dell’utente, tutti i processi dovrebbero essere trattati allo stesso modo e nessuno di essi dovrebbe potersi trovare in situazioni di attesa indefinita.
Naturalmente NO!
I parametri prima definiti sono interdipendenti ed alcuni sono persino in contrasto tra loro.
Ad esempio fornire un tempo di risposta minimo richiede un algoritmo che esegue un context switch molto frequente. Ciò accresce l’overhead del sistema, abbassando notevolmente il throughput.
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“.
Lo Scheduler può scegliere i processi in base alla loro priorità.
Le priorità possono essere:
I processi tipicamente sono raggrupati in classi di priorità: l’algoritmo di scheduling dovrà scegliere un processo pronto che appartiene alla classe di priorità più alta.
L’utilizzo di un algoritmo di scheduling a priorità può indurre situazioni di attesa indefinita di processi a priorità più bassa (starvation).
Per far fronte a siffatte situazioni si utilizzano schemi di priorità dinamiche (es. aumento graduale della priorità dei processi che si trovano in attesa nel sistema da lungo tempo (Aging)).
Lo scheduler di breve termine può essere
Nonpreemptive
Preemptive
Per illustrare i vari algoritmi ci riferiremo al seguente esempio:
Parametri utilizzati:
Quando il processo cessa la sua esecuzione, viene scelto il processo che attende da più tempo.
FinishTime TA=3, TB= 9, TC=13, TD=18, TE=20
Tournaround TrA=3, TrB= 7, TrC=9, TrD=12, TrE=12
TrA/TsA=1, TrB/TsB=1.17, TrC/TsC=2.25
TrD/TsD=2.40, TrE/TsE=6.00
Il processo E spende nel sistema un tempo che è 6 volte quello di esecuzione.
Un processo con tempo di esecuzione corto può aspettare un tempo molto lungo prima di essere eseguito.
Favorisce i processi CPU-bound.
Un processo CPU-bound e molti processi I/O bound.
Via via che fluiscono i processi nel sistema si può riscontrare come il processo CPU-bound occupi la CPU (i processi I/O occupano la CPU per un periodo breve a favore del processo CPU-bound).
L’effetto è che tutti i processi attendono che un lungo processo liberi la CPU, causando una riduzione dell’utilizzo della CPU stessa e dei dispositivi rispetto alla situazione che si avrebbe se si eseguissero per primi i processi più brevi.
Nasce dalla trasformazione preemptive del FCFS mediante l’impiego di un timer.
Le prestazioni dell’algoritmo sono dipendenti dalla durata del periodo del timer che definisce il quanto di tempo di massimo utilizzo della risorsa o time slice (valori tipici da 10 a 100 msec).
Aumentando il time slice tende a trasformarsi in FCFS, mentre diminuendolo aumentano i salvataggi e ripristini di stato dei processi e quindi l’overhead del S.O.
TA=4, TB= 18, TC=17, TD=20, TE=15
TrA=4, TrB= 16, TrC=13, TrD=14, TrE=7
TrA/TsA=1.33, TrB/TsB=2.67, TrC/TsC=3.25
TrD/TsD=2.80, TrE/TsE=3.50
Con il round-robin il processo E dimezza il suo ritardo relativo.
A. Il quanto di tempo q dovrebbe essere leggermente superiore del tempo s richiesto per una tipica interazione.
B. Se inferiore, la maggior parte dei processi richiederà almeno due quanti di tempo!
Può avere sia uno schema non-preemptive sia preemptive (chiamato Short Remaining Time).
Vengono selezionati i Processi con il minor tempo di esecuzione stimato.
Uno scheduling progettato al fine di rendere minimo il tempo medio di attesa per un dato insieme di processi
…al costo di rendere i tempi di risposta medi più lunghi (specialmente per i processi lunghi).
TA=3, TB= 9, TC=15, TD=20, TE=11
TrA=3, TrB= 7, TrC=11, TrD=14, TrE=3
TrA/TsA=1, TrB/TsB=1.17, TrC/TsC=2.75
TrD/TsD=2.80, TrE/TsE=1.50
Possibilità di starvation per i processi più lunghi (ad es., il processo D).
SPN richiede di conoscere, o almeno stimare, il tempo di servizio di ciascun processo.
In un sistema batch, questa stima potrebbe essere richiesta al programmatore, o effettuata dal SO su basi statistiche (in base alle esecuzioni passate del job).
In un sistema interattivo, il SO può stimare il tempo di servizio (n+1)-mo di ciascun processo come media dei “burst” di esecuzione passati (da 1 a n):
dove:
Questa stima da ugual peso ad ogni Ti.
… e se la stima del tempo di esecuzione è non corretta, l’algoritmo può andare in crisi.
Un’alternativa è dare un peso maggiore ai Ti più recenti, in quanto più rappresentativi del comportamento futuro del processo.
A tal scopo, viene utilizzata una stima basta su media esponenziale:
E’ la versione Preemptive dell’alg. Shortest Process Next.
La prelazione della CPU avviene quando entra in coda un nuovo processo con tempo di servizio inferiore al tempo di servizio rimanente al processo running.
Nell’esempio tutti i processi più piccoli non hanno ritardo.
TrA/TsA=1, TrB/TsB=2.17, TrC/TsC=1
TrD/TsD=2.80, TrE/TsE=1
Come per SPN, c’è il problema della stima del tempo di servizio.
Ci può essere starvation per i processi lunghi.
Prestazioni comparabili al Round Robin:
Motivazioni
Lo scheduling è di tipo preemptive basato su quanto di tempo, code multiple, e priorità
… è utilizzato un meccanismo di priorità dinamico (se un processo usa “troppo” tempo di CPU, viene spostato in una coda con priorità minore).
Mantiene i processi con prevalenza di I/O e i processi interattivi nelle code a priorità più elevata.
E’ caratterizzato da i seguenti parametri:
Costituisce il più generale criterio di scheduling della CPU, che nella fase di progettazione si può adeguare a un sistema specifico.
E’ anche l’algoritmo più complesso da implementare.
Favorisce i processi più corti.
Il tempo di tournaround dei processi lunghi può crescere sensibilmente. Può esserci anche starvation per particolari condizioni di carico.
Per minimizzare la probabilità del verificarsi di situazioni di starvation viene adottato il seguente schema:
Per evitare completamente la starvation si può anche permettere ad un processo contenuto nella coda RQn di transitare nuovamente nella coda RQ0.
1. Introduzione ai Sistemi Operativi
5. Scheduling nei sistemi mono-processore
6. Threads, SMP
8. Scheduling Multiprocessore e Real-Time
9. Gestione dei processi nei sistemi operativi Unix/Linux e Window...
10. Introduzione alla Programmazione Concorrente
11. Sincronizzazione nel modello ad ambiente globale
12. Problemi di cooperazione nel modello ad ambiente globale
14. Sincronizzazione nel modello ad ambiente locale
15. Deadlock
16. Programmazione Multithread
18. Memoria Virtuale
20. Il File System
21. Primitive di sincronizzazione nel kernel Linux
22. Esercitazione: System call per la gestione dei processi
23. Esercitazione: Inteprocess Communication e Shared Memory
24. Esercitazione: System Call per la gestione dei semafori in Linu...
25. Esercitazione: Problema dei Produttori e dei Consumatori
26. Posix Threads
P. Ancilotti, M.Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap.2)
Dispense fornite tratte dallo Stallings
Testi di Approfondimento
W. Stallings, “Operating Systems : Internals and Design Principles (6th Edition) ”, Pearson Education (Cap. 9)
A. Silbershatz, G. Gagne, "Sistemi Operativi" (sesta edizione), Addison-Wesley