Sartomiki.net

Generalità
Lo scheduling della CPU è alla base di tutti i sistemi che supportano la multiprogrammazione, che si ottiene dando a ciascun processo in esecuzione il totale controllo della CPU in un determinato lasso di tempo. Grazie ad uno scheduling dei processi/thread efficiente si possono ottenere prestazioni ottime.
In un sistema monoprocessore si può eseguire al massimo un processo alla volta, mentre gli altri processi in esecuzione devono essere memorizzati in una coda, in attesa del proprio turno. Per rendere efficiente il sistema è necessario sfruttare al meglio i tempi di attesa, in modo che non sia "tempo perso". Lo scheduling ha proprio questo scopo.
Lo scheduling si basa sull'analisi comportamentale dei processi. L'esecuzione di un processo si basa su di un ciclo di elaborazione, composto da una sequenza di operazioni, seguita da una sequenza di richieste di I/O (molto più onerose in termini di tempo, ma non implicano l'uso della CPU).
I programmi si possono dividere in due categorie:
-CPU bound, che necessitano principalmente di operazioni di calcolo per la CPU
-I/O bound, che necessitano principalmente di operazioni di I/O

Scheduler a breve termine
Ogni volta che la CPU passa in uno stato di inattività, il SO sostituisce il processo attivo con uno dei processi in coda. Questa parte del sistema operativo viene detta scheduler della CPU o scheduler a breve termine.
Gli eventi base che uno scheduler della CPU deve considerare sono:
-un processo attende il verificarsi di un evento, cioè il processo passa in uno stato di wait o attende operazioni di I/O.
-un processo passa dallo stato di esecuzione allo stato pronto (quando si verifica un segnale di interrupt).
-un processo passa dallo stato di attesa allo stato pronto (quando termina un'operazione di I/O).
-un processo termina la propria esecuzione.
Esistono diversi tipi di scheduler:
-nonpreemptive (senza diritto di prelazione) non interrompono l'azione di un processo fino al termine della sua esecuzione o in caso di passaggio in uno stato di attesa. Questo schema è stato utilizzato da Microsoft 3.x.
-cooperative (cooperativo) è simile al nonpreemptive, ma non necessita di strutture ausiliarie come timer. Questo schema è stato utilizzato da Mac OS.
-preemptive (con diritto di prelazione) è in grado di interrompere e riprendere l'azione di un processo anche quando non si trova in uno stato di wait. Il problema si pone nel momento in cui ci sono più processi che condividono parti di memoria, poiché si potrebbe scrivere o leggere dati non coerenti. Per evitare gravi problemi è necessario che le procedure di interrupt o i processi che modificano file di sistema non debbano essere interrotti, in modo da evitare ulteriori problemi Questo schema è stato introdotto a partire da Windows 95, ed è stato adottato anche da Mac OS X.

Dispatcher
Un altro elemento coinvolto nello scheduling è il dispatcher, che ha lo scopo di passare effettivamente il controllo della CPU ai processi scelti dallo scheduler. Questo modulo effettua le seguenti operazioni:
-effettuare il context switching.
-passa alla modalità utente.
-riavvia il processo a partire dalla giusta operazione.
Poiché il dispatcher è utilizzato molto di frequente, queste operazioni devono essere eseguite in modo rapido. Il tempo che il dispatcher impiega è detto latenza di dispatch.

Criteri di scheduling
Per gestire la coda dei processi in attesa lo scheduler della CPU deve tenere conto di diversi fattori:
-utilizzo della CPU, la CPU deve essere attiva il più possibile.
-produttività, la CPU deve produrre il maggior numero di risultati nell'unità di tempo.
-tempo di completamento, ogni processo deve impiegare il minor tempo di esecuzione totale possibile.
-tempo d'attesa, ogni processo deve stare il meno tempo possibile in attesa.
-tempo di risposta, è importante che i tempi di attesa per i processi interattivi siano abbastanza piccoli da consentire un tempo di risposta ai comandi esterni praticamente immediato.
Gli algoritmi di scheduling tendono ad aumentare al massimo la produttività della CPU, e ridurre al minimo i tempi di completamento, attesa e risposta. Per alcuni sistemi è importante considerare anche la varianza dei tempi di risposta, in modo tale da prevedere questo tempo.

Algoritmi di scheduling
I principali algoritmi di scheduling sono:
-in ordine di arrivo (FCFS), con questo algoritmo la CPU viene assegnata al processo che la richiede per primo. La coda risulta essere di tipo FIFO. Il tempo medio di attesa è abbastanza lungo e varia a seconda dell'arrivo dei processi. L'algoritmo FCFS è senza prelazione e causa l'effetto convoglio, in cui tutti i processi attendono i processi più lenti.
-brevità (SJF), con questo algoritmo la CPU viene assegnata al processo che eseguirà un minor numero di operazioni sulla CPU, prima di tornare inattivo o terminare. Nel caso in cui due o più processi debbano eseguire lo stesso numero di operazioni, si utilizza l'algoritmo FCFS. E' possibile dimostrare che questo algoritmo è ottimo, in quanto il tempo medio di attesa viene minimizzato. Il problema principale sta nel conoscere esattamente la durata futura di un processo. Questa operazione è possibile solo nei sistemi con scheduling a lungo termine, che prevedono che sia l'utente stesso a dichiarare la lunghezza del processo stesso. Un processo viene rimesso in coda nel caso in cui non riesca a completare nel tempo dichiarato l'intera serie di operazioni. Nei sistemi a breve termine è possibile stimare il numero di operazioni, con il calcolo della media esponenziale delle effettive lunghezze delle precedenti sequenze di operazioni della CPU. L'algoritmo SJF può essere implementato sia con prelazione che senza.
-priorità, con questo algoritmo la CPU viene assegnata al processo con la priorità maggiore. L'algoritmo SJF è un caso particolare di questa classe di algoritmi, che prende come priorità il numero di istruzioni successive. Le classi di priorità sono indicate con un intervallo di valori. Non è ancora stato stabilito se associare la priorità massima al valore 0 oppure al valore massimo. Le priorità interne sono quantità misurabili, che si definiscono secondo criteri interni al sistema (tempo, requisiti di memoria, numero di file aperti, lunghezza operazioni I/O,..); al contrario le priorità esterne seguono criteri esterni al sistema (importanza del processo, tipo,…). Gli algoritmi a priorità possono essere implementati con o senza prelazione. Un problema importante degli algoritmi a priorità è la starvation (attesa indefinita). Per risolvere questo processo si può attribuire ai processi con bassa priorità un fattore di invecchiamento, che permette di acquisire priorità con il passare del tempo.
-circolare (round robin, RR), con questo algoritmo la CPU viene assegnata a turno ad ogni processo per una certa quantità di tempo. E' in un certo senso l'implementazione con prelazione dell'algoritmo FCFS, in quanto la coda è gestita in modo FIFO. Se al termine del quanto di tempo il processo non ha finito la propria esecuzione, viene effettuato un context switching.  Le prestazioni dipendono principalmente dalla dimensione del quanto di tempo e dal tempo di context switching. Il tempo di completamento medio diminuisce se la maggior parte dei processi termina la successiva sequenza di operazioni della CPU in un solo quanto di tempo.
-code multiple, con questo algoritmo non si gestisce una sola coda di processi ma diverse. Ogni coda può avere il proprio algoritmo di scheduling. Nei sistemi reali è possibile assegnare una coda ai processi in background (algoritmo FCFS), e una coda ai processi in foreground (algoritmo RR). E' necessario stabilire uno scheduling tra code, in modo da scegliere quale dei processi in testa alle code è da eseguire.
-code multiple con retroazione, con questo algoritmo si gestisce uno scheduler a code multiple, dove i processi possono passare da una coda al'altra. In questo modo è possibile spostare i processi che usano troppo tempo di elaborazione della CPU in coda a più bassa priorità e viceversa. Normalmente questo algoritmo è il più generale e personalizzabile anche se chiede la definizione di metodi aggiuntivi (algoritmi di gestione per ciascuna coda, criterio di promozione o declassamento, criterio di ingresso, numero di code…).

Scheduling multiprocessore
Se sono disponibili più CPU il problema dello scheduling si complica. Si sono sperimentate diverse tecniche di gestione e anche in questo caso la soluzione migliore varia a seconda dell'architettura e dell'utilizzo della stessa. Si definiscono sistemi omogenei, i sistemi che hanno CPU multiple uguali tra loro.
Nel caso in cui si affidino tutte le decisioni, le operazioni di I/O e le altre attività del sistema ad un solo processore (master server) si parla di multielaborazione asimmetrica ed è previsto che gli altri processori si occupino solo del codice utente.
Nel caso, invece, che ogni processore provveda al proprio scheduling si parla di multielaborazione simmetrica (SMP), che permette di avere una coda comune dei processi tra tutte le CPU oppure code separate. L'accesso concorrente di più processori a una coda comune rende delicato il ruolo dello scheduler, che non deve rendere possibile che due processori scelgano di eseguire lo stesso processo contemporaneamente.
Un concetto importante per definire una tecnica di scheduling ottimale è il fatto che ogni processore è munito di una propria cache di dati, che permette di migliorare notevolmente le prestazioni di I/O. E' importante quindi che i processi in esecuzione su una CPU continuino la loro esecuzione su quella CPU anche dopo un context switching. Questo crea una certa predilezione per un processore (processor affinity). Si parla di predilezione debole se questa condizione non è obbligata; si parla invece di predilezione forte nel caso in cui, come nei sistemi UNIX, ci siano chiamate di sistema che forzino la predilezione.
Nei sistemi SMP è importante che il carico di lavoro sia distribuito in modo equo tra tutti i processori. Questo processo si chiama bilanciamento del carico. Nei sistemi a coda comune è spesso superfluo, in quanto i processori reperiscono in modo automatico i nuovi processi dalla coda, nel momento in cui non stanno lavorando a pieno carico.
Negli attuali sistemi SMP non è raro trovare code indipendenti. Il bilanciamento del carico può seguire due approcci non indipendenti:
-migrazione guidata (pus). Un processo apposito controlla il carico delle varie code e lo sposta dal processore con più lavoro a quello con meno lavoro.
-migrazione spontanea (pull). Un processore inattivo sottrae un processo da un processore saturo.
Molto spesso il bilanciamento del carico annulla i benefici derivati dalla predilezione del processore.
Sovente i sistemi SMP consentono l'esecuzione di numerosi thread contemporaneamente su CPU diverse. Questo è possibile grazie alla tecnologia iperthread (processori intel) o multithread simmetrico (SMT).
Per utilizzare SMT si creano più processori logici basati su uno stesso processore fisico. Ciascun processore logico è dotato di una propria architettura logica e sovrintende autonomamente alle proprie interruzioni. Tutti i processori logici di uno stesso processore fisico condividono le risorse come il BUS, la cache e le risorse. SMT è implementato a livello hardware e non a livello software, quindi questa opzione può essere sfruttata o meno dagli OS.

Scheduling thread
Il sistema pianifica l'esecuzione dei thread in kernel mode. I thread di livello utente sono gestiti attraverso una libreria di sistema: ne consegue che il kernel non è consapevole della loro esistenza. Per eseguire i thread a livello utente è necessario che essi siano associati ad un thread in kernel mode.
Per i thread in user mode, sia nel caso che si tratti di modello molti a uno e di modello molti a molti, l'associazione avviene per mezzo di un processo kernel leggero (LWP). In questo caso si parla di competizione ristretta al processo (PCS), in quanto la contesa per utilizzare la CPU avviene tra thread dello stesso processo. In questo caso la decisione avviene attraverso l'analisi della priorità stabilita dall'utente.
La competizione allargata al sistema (SCS) avviene tra processi kernel diversi.