16 Jul 2023, 8:46 AM

6. Scheduling della CPU

Con scheduling, si intende l'assegnazione di un'attività nel tempo. Esso è necessario per regolare

l'ammissione dei processi nella memoria
l'ammissione dei processi nella CPU

È importante ricordare che possono esserci $N$ processi nello stato pronto, $1$ processo in esecuzione e $M$ processi in attesa in RAM.

Tipi di scheduler

Come accennato in 4. Gestione dei processi e threads#Scheduling, ci sono più tipi di scheduler:

Scheduler a lungo termine (o job scheduler)
- Seleziona quali processi devono essere portati nella ready queue.
- O(s) ⇒ può essere lento, visto che è invocato raramente
- Controlla il grado di multiprogrammazione (il massimo numero di processi in memoria) e il mix di processi di tipo
  - I/O-bound
    - molto I/O, molti brevi burst di CPU
  - CPU-bound
    - molti calcoli, pochi lunghi burst di CPU
- Può essere addirittura assente, esso è usato principalmente in sistemi con risorse limitate
Scheduler a breve termine (o CPU scheduler)
- Seleziona quale processo deve essere eseguito dalla CPU
- O(ms) ⇒ deve essere veloce, visto che è invocato più spesso
  - Esempio: 100 ms per processo, 10 ms per scheduling
  - 10/(110) = 9% del tempo di CPU sprecato per scheduling
Scheduler a medio termine
- La RAM fisica ha uno spazio limitato, quindi si può estendere e creare così una memoria virtuale sul disco, che funge da RAM. Questa parte del disco viene chiamata backing store. La CPU comunque comunica solo con la RAM fisica, e se un processo è nel backing store, devo prima passarlo nella RAM tramite uno swap-in, e successivamente con uno swap-out lo posso rimettere nel backing store.
- Riassumendo, lo scheduler a medio termine è presente nei S.O. con memoria virtuale (che è una parte del disco che viene usata temporaneamente come RAM) e si occupa della rimozione forzata (swapping) di un processo dalla CPU
  - Un processo, alla fine di un burst di CPU può essere infatti posto nel disco, in una coda diversa da quella di ready, per essere poi recuperato in seguito
  - Serve per ridurre il grado di multiprogrammazione

Dispatcher

L'operazione più critica è quella fatta dal dispatcher, ovvero assegna la CPU ad un certo processo e fa passare il processo da ready a running. Come avviene nel dettaglio?

Cambio di contesto: viene salvato il PCB del processo che esce e viene caricato il PCB (precedentemente registrato) del processo che entra
Passaggio alla modalità utente
Salto all'istruzione da eseguire del processo appena arrivato nella CPU

Ovviamente per fare questo, è presente una latenza di dispatch, ossia il tempo necessario al dispatcher per fermare un processo e farne ripartire un altro. E ovviamente deve essere la più bassa possibile.

Prelazione

Ottimizzare lo short-term scheduler è fondamentale per massimizzare l'utilizzo della CPU, pertanto sono state studiate molte tecniche e algoritmi per migliorare le prestazioni.
Dal punto di vista della CPU, ogni processo può essere visto come una serie di CPU burst e I/O burst (dove per burst si intende un intervallo di utilizzo necessario al completamento della task). A partire da questi, si definisce una prima classificazione delle politiche di scheduling, in base alla prelazione(preemption), ossia al rilascio forzato della CPU.

Scheduling con prelazione (preemptive): un processo che detiene la CPU può essere forzato a rilasciarla prima del termine del burst. Un esempio può essere il pronto soccorso. Mentre mi stanno curando il braccio rotto, arriva il vecchio con un arresto cardiaco. I medici paccano me e vanno dal vecchio che sta per morire. Ovviamente la prelazione rende il tutto più complicato.
Scheduling senza prelazione (non-preemptive): un processo che detiene la CPU non può essere forzato a rilasciarla prima del termine del burst.

Metriche di scheduling

Per valutare un algoritmo di scheduling si utilizzano apposite metriche di scheduling:

Utilizzo della CPU: percentuale di utilizzo media della CPU, l’obiettivo è tenere la CPU occupata il più possibile
Throughput: numero di processi completati nell'unità di tempo
Turnaround time (tempo di completamento): tempo totale dall'inizio del processo al termine. Comprende il waiting time.
- Turnaround = ExitTime - ArrivalTime o anche Turnaround = WaitingTime + Tempo di esecuzione (CPUburst)
Waiting time: tempo speso dal processo nella ready queue, è influenzato dall’algoritmo di scheduling.
Response time: tempo compreso tra l'arrivo del processo nella ready queue e la sua prima esecuzione (quando ottengo la CPU), il primo dispatch. Quando clicco l'icona di un programma mi aspetto una reazione a breve, di solito sotto i 100 ms, sennò, in media, l'utente non è contento.

Nota: Negli algoritmi non-preemptive, tempo di attesa e di risposta sono uguali. Inoltre, l'obiettivo è massimizzare l'utilizzo della CPU e il throughput, e minimizzare il tempo di turnaround, il tempo di attesa e il tempo di risposta. A seconda del sistema si può decidere di bilanciare tali metriche o focalizzarsi sulla minimizzazione/massimizzazione di una o più. Ad esempio, nei sistemi interattivi si preferisce minimizzare la varianza del tempo di risposta piuttosto che la media.

Algoritmi di scheduling

Di seguito sono riportati i principali algoritmi di scheduling:

First Come First Served (FCFS)

È un algoritmo di base, semplice da implementare e leggero. La coda dei processi funziona come una FIFO, si eseguono quindi i processi in ordine di arrivo.
Svantaggi:

Ha bassi tempi di risposta ma un waiting time medio molto lungo.
Soggetto all' "effetto convoglio": l'esecuzione di processi corti è ritardata da processi più lunghi.
È suscettibile a come i processi arrivano.
Essendo non pre-emptive, è un algoritmo problematico per i sistemi a time sharing e per i sistemi interattivi.

Esempio

Sono dati i seguenti tre processi, con i relativi tempi di arrivo e CPU burst.

Processo	Tempo di arrivo	CPU burst
$P_{1}$	$0$	$24$
$P_{2}$	$2$	$3$
$P_{3}$	$4$	$3$

Per capirci meglio, ecco quello che accade:

Tempo	$0 - 24$	$24 - 27$	$27 - 30$
$P_{1}$	X
$P_{2}$		X
$P_{3}$			X

Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo.

Processo	$T_{R}$	$T_{W}$	$T_{T}$
$P_{1}$	$0$	$0$	$24$
$P_{2}$	$22$	$22$	$25$
$P_{3}$	$23$	$23$	$26$

Analizziamo $P_{1}$ :

È arrivato per primo, non subirà alcun rallentamento.
Avrà response time $0$ , waiting time $0$ e tempo di completamento $24$ .

Analizziamo $P_{2}$ :

È arrivato secondo, subirà un rallentamento a causa di $P_{1}$
Avrà response time (ovvero la differenza tra quando inizia la sua esecuzione per la prima volta e quando è arrivato nella coda) pari a $24 - 2$ (deve aspettare che finisca $P_{1}$ .
Avrà waiting time (tempo speso dal processo nella ready queue) pari a $22$ , in questo caso come il response time.
Avrà turnaround time (tempo trascorso dall'inizio del processo al termine) pari a WaitingTime + Tempo di esecuzione (CPUburst) = $22 + 3 = 25$ .

Analizziamo $P_{3}$ :

È arrivato terzo, subirà un rallentamento a causa di $P_{1}$ e $P_{2}$
Avrà response time (ovvero la differenza tra quando inizia la sua esecuzione per la prima volta e quando è arrivato nella coda) pari a $27 - 4 = 23$ (deve aspettare che finisca $P_{1}$ e $P_{2}$ .
Avrà waiting time (tempo speso dal processo nella ready queue) pari a $23$ , in questo caso come il response time.
Avrà turnaround time (tempo trascorso dall'inizio del processo al termine) pari a WaitingTime + Tempo di esecuzione (CPUburst) = $23 + 3 = 26$ .

Il tempo di attesa medio è pari a $\frac{0 + 22 + 23}{3} = 15$

Esempio 2

Sono dati i seguenti tre processi, con i relativi tempi di arrivo e CPU burst.

Processo	Tempo di arrivo	CPU burst
$P_{1}$	$4$	$24$
$P_{2}$	$0$	$3$
$P_{3}$	$2$	$3$

Per capirci meglio, ecco quello che accade:

Tempo	$0 - 3$	$3 - 6$	$6 - 30$
$P_{1}$			X
$P_{2}$	X
$P_{3}$		X

Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo.

Processo	$T_{R}$	$T_{W}$	$T_{T}$
$P_{1}$	$6 - 4 = 2$	$2$	$2 + 24 = 26$
$P_{2}$	$0$	$0$	$3$
$P_{3}$	$1$	$1$	$1 + 3 = 4$

Il tempo di attesa medio è pari a $\frac{2 + 0 + 1}{3} = 1$

Shortest Job First (SJF)

Esegue i processi in ready queue partendo da quello con prossimo CPU-burst minore.
Può essere sia preemptive, sia non-preemptive.
- Nel caso di preemptive, se arriva un processo con CPU burst più breve del tempo rimanente a quello di esecuzione, quest'ultimo viene rimosso per fare spazio a quello appena arrivato. In questo caso l’algoritmo si chiama Shortest-Remaining-Time-First (SRTF).
L'algoritmo è ottimo per la minimizzazione di waiting time medio e quindi di turnaround (vedi algoritmi greedy)
Problema di starvation: un processo con CPU burst molto lungo potrebbe non arrivare mai alla CPU
È difficile stimare il burst di un processo. Per ovviare al problema si stima il prossimo burst di CPU tramite media esponenziale. La formula è la seguente:

T_{n + 1} = α \cdot t_{n} + (1 - α) \cdot T_{n}

dove $T_{n + 1}$ è il valore stimato per il prossimo burst, $T_{n}$ è la media dei burst passati e $t_{n}$ la durata dell'ultimo burst registrato, $α$ è un valore compreso tra 0 e 1. In questo modo si ottiene una buona stima del prossimo burst di CPU.

Esempio 1 - non-preemptive

Sono dati i seguenti quattro processi, con i relativi tempi di arrivo e CPU burst.

Processo	Tempo di arrivo	CPU burst
$P_{1}$	$0$	$7$
$P_{2}$	$2$	$4$
$P_{3}$	$4$	$1$
$P_{4}$	$5$	$4$

Per capirci meglio, ecco quello che accade:

Tempo	$0 - 7$	$7 - 8$	$8 - 12$	$12 - 16$
$P_{1}$	X
$P_{2}$			X
$P_{3}$		X
$P_{4}$				X

Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo.

Processo	$T_{R}$	$T_{W}$	$T_{T}$
$P_{1}$	$0$	$0$	$7$
$P_{2}$	$8 - 2 = 6$	$6$	$6 + 4 = 10$
$P_{3}$	$7 - 4 = 3$	$3$	$3 + 1 = 4$
$P_{4}$	$12 - 5 = 7$	$7$	$7 + 4 = 11$

Quindi quello che succede è che una volta che un processo termina, viene eseguito quello con CPU burst minore. Essendo però non-preemptive, se entra un processo con CPU burst minore quello in esecuzione non viene killato.

Esempio 2 - preemptive

I dati sono uguali al precedente esempio.

Processo	Tempo di arrivo	CPU burst
$P_{1}$	$0$	$7$
$P_{2}$	$2$	$4$
$P_{3}$	$4$	$1$
$P_{4}$	$5$	$4$

Per capirci meglio, ecco quello che accade:

Tempo	$0 - 2$	$2 - 4$	$4 - 5$	$5 - 7$	$7 - 11$	$11 - 16$
$P_{1}$	X					X
$P_{2}$		X		X
$P_{3}$			X
$P_{4}$					X

Più precisamente:

A $t = 2$ entra $P_{2}$ che ha CPU burst < $P_{1}$ ( $4 < 5$ ).
A $t = 4$ entra $P_{3}$ che ha CPU burst < $P_{2}$ ( $1 < 2$ ).
A $t = 5$ $P_{3}$ finisce. In questo momento appare anche $P_{4}$ con CPU burst pari a $4$ . Ma dato che $P_{2}$ ha CPU burst < $P_{4}$ < $P_{1}$ ( $2 < 4 < 5$ ), entra lui.
A $t = 7$ $P_{2}$ finisce. Dato che $P_{4}$ ha CPU burst < $P_{1}$ ( $4 < 5$ ), entra lui.
A $t = 11$ $P_{4}$ finisce ed entra $P_{1}$ .

Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo.

Processo	$T_{R}$	$T_{W}$	$T_{T}$
$P_{1}$	$0$	$11 - 2 = 9$	$9 + 7 = 16$
$P_{2}$	$0$	$1$	$1 + 4 = 5$
$P_{3}$	$0$	$0$	$0 + 1 = 1$
$P_{4}$	$2$	$2$	$2 + 4 = 6$

In questo caso, per i processi $P_{1}$ e $P_{2}$ , il tempo di risposta non coincide col tempo di attesa. Essi coincidono solo quando un processo, una volta iniziata la sua esecuzione, non torna più nella coda dei processi ad aspettare (algoritmi non-preemptive), cosa che nel SJF preemptive raramente accade ( $P_{3}$ e $P_{4}$ ).

Come prima, quando un processo termina, viene eseguito quello con CPU burst minore. Essendo però preemptive, se entra un processo con CPU burst minore quello in esecuzione viene killato, e viene fatto entrare il nuovo processo.

Scheduling a priorità

Con lo SJF è stato introdotto lo scheduling a priorità (inversamente proporzionale al burst di CPU), in cui viene associata una priorità a ogni processo.

la CPU viene assegnata al processo con priorità più alta
la priorità di un processo viene assegnata in base a fattori interni al SO (per limiti di tempo o memoria) o esterni al SO(come ad esempio dall'amministratore di sistema, soldi pagati per l’utilizzo del computer).

Può essere sia preemptive, sia non-preemptive. In Linux si utilizza il comando “nice” per cambiare la priorità.
Esempio: SJF è uno scheduling a priorità (priorità = 1/lunghezza del burst successivo). Più piccolo è il burst, più alta la priorità

L'implementazione base dello scheduling a priorità richiede una serie di code FCFS, ciascuna per ogni priorità specificata, questo comporta dei problemi tipici.
Primo tra tutti la starvation: alcuni processi non saranno mai eseguiti (o comunque con tempi di risposta troppo lunghi) poichè altri processi con priorità più alta li precedono costantemente. Per ovviare a tale problema si utilizza la tecnica di aging, tramite la quale la priorità viene periodicamente aggiornata e aumenta col passare del tempo in ready queue.

Esempio

Ecco un esempio di un generico algoritmo di scheduling a priorità.
Sono dati i seguenti cinque processi, con i relativi tempi di arrivo, priorità e CPU burst. In questo caso più è basso il numero della priorità, più la priorità è alta.

Processo	Tempo di arrivo	Priorità	CPU burst
$P_{1}$	$1$	$3$	$10$
$P_{2}$	$0$	$1$	$1$
$P_{3}$	$2$	$3$	$2$
$P_{4}$	$0$	$4$	$1$
$P_{5}$	$1$	$2$	$5$

Per capirci meglio, ecco quello che accade:

Tempo	$0 - 1$	$1 - 6$	$6 - 16$	$16 - 18$	$18 - 19$
$P_{1}$			X
$P_{2}$	X
$P_{3}$				X
$P_{4}$					X
$P_{5}$		X

Più precisamente:

Ogni volta che un processo termina la sua esecuzione, viene preso quello con priorità più alta.
Se due processi hanno la stessa priorità, viene preso in ordine quello con pedice minore (quello che accade a $P_{1}$ e $P_{3}$ a $t = 6$ )

Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo.

Processo	$T_{R}$	$T_{W}$	$T_{T}$
$P_{1}$	$6 - 1 = 5$	$5$	$5 + 10 = 15$
$P_{2}$	$0$	$0$	$0 + 1 = 1$
$P_{3}$	$16 - 2 = 14$	$14$	$2 + 14 = 16$
$P_{4}$	$18 - 0 = 18$	$18$	$18 + 1 = 19$
$P_{5}$	$0$	$0$	$0 + 5 = 5$

Vediamo ora due algoritmi di scheduling a prorità, uno preemptive ed uno non-preemptive.

Highest Response Ratio First (HRRN)

Algoritmo a priorità non pre-emptive, sviluppato come variante dello SJF. Per ogni processo la priorità viene calcolata come $$P = 1 + \frac {\text{Waiting Time}} {\text{BurstTime}}$$ ed è aggiornata al termine di ogni processo. Si supera con HRRN il favoritismo per i job corti, dato che sono favoriti i processi che completano in poco tempo (come SJF) oppure quelli che hanno atteso molto. La stima del CPU burst è fatta con la media esponenziale come per SJF.

Esempio

Sono dati i seguenti cinque processi, con i relativi tempi di arrivo e CPU burst. In questo caso più è alto il numero della priorità, più la priorità è alta.

Processo	Tempo di arrivo	CPU burst
$P_{1}$	$1$	$10$
$P_{2}$	$0$	$2$
$P_{3}$	$2$	$2$
$P_{4}$	$2$	$1$
$P_{5}$	$1$	$5$

Per capirci meglio, ecco quello che accade:

Tempo	$0 - 2$	$2 - 7$	$7 - 8$	$8 - 10$	$10 - 19$
$P_{1}$					X
$P_{2}$	X
$P_{3}$				X
$P_{4}$			X
$P_{5}$		X

Come detto sopra, al termine di ogni processo la priorità di ogni altro processo viene ricalcolata come $P = 1 + \frac{Waiting Time}{BurstTime}$ .
Costruiamoci quindi la tabella con le varie priorità.

Processo	$t = 0$	$t = 2$	$t = 7$	$t = 8$
$P_{1}$	-	$1 + \frac{1}{10} = \frac{11}{10}$	$1 + \frac{7 - 1}{10} = \frac{16}{10}$	$1 + \frac{8 - 1}{10} = \frac{17}{10}$
$P_{2}$	$1 + \frac{0}{2} = 1$	-	-	-
$P_{3}$	-	$1 + \frac{0}{2} = 1$	$1 + \frac{7 - 2}{2} = \frac{7}{2}$	$1 + \frac{8 - 2}{2} = 4$
$P_{4}$	-	$1 + \frac{0}{1} = 1$	$1 + \frac{7 - 2}{1} = 6$	-
$P_{5}$	-	$1 + \frac{1}{5} = \frac{6}{5}$	-	-

Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo.

Processo	$T_{R}$	$T_{W}$	$T_{T}$
$P_{1}$	$10 - 1 = 9$	$9$	$9 + 10 = 19$
$P_{2}$	$0$	$0$	$0 + 2$
$P_{3}$	$8 - 2 = 6$	$6$	$6 + 2 = 8$
$P_{4}$	$7 - 2 = 5$	$5$	$5 + 1 = 6$
$P_{5}$	$2 - 1 = 1$	$1$	$1 + 5 = 6$

Round Robin (RR)

Algortmo pre-emptive, che cerca di distribuire il tempo della CPU il più equamente possibile fra i processi. Viene definita un'unità (quanto, va dai 10 ai 100 ms), che è il tempo massimo di esecuzione di un processo prima che venga rimesso nella ready queue, gestita come una coda circolare.
Dunque, se ci sono $n$ processi nella coda e il quanto è $q$ :

ogni processo ottiene $\frac{1}{n}$ del tempo di CPU in blocchi di $q$ unità di tempo alla volta
nessun processo attende più di $(n - 1) \cdot q$ unità di tempo

Circolarmente viene fornito un quanto di tempo a disposizione per i processi, inserendo ad inizio coda di solito i processi appena arrivati, per minimizzare i tempi di risposta.

Il problema principale si basa sulla scelta del quanto di tempo:

se $q$ è troppo grande RR diventa praticamente un FCFS
se $q$ è troppo piccolo l'overhead del cambio di contesto degrada le prestazioni. È meglio quindi avere $q$ maggiore del tempo di context switch.

Allora qual è un valore ragionevole di $q$ ? Bisogna fare in modo che l' $80 %$ dei burst di CPU siano $< q$ .

In generale con RR, rispetto a SJF, si ha un tempo di turnaround medio maggiore/uguale, ma un tempo di risposta minore/uguale.

Esempio

Sono dati i seguenti quattro processi, con i relativi tempi di arrivo e CPU burst. Inoltre definiamo la lunghezza del quanto $q = 2$ .

Processo	Tempo di arrivo	CPU burst
$P_{1}$	$0$	$5$
$P_{2}$	$0$	$1$
$P_{3}$	$0$	$7$
$P_{4}$	$0$	$2$

Per capirci meglio, ecco quello che accade:

Tempo ( $q = 2$ )	$0 - 2$	$2 - 3$	$3 - 5$	$5 - 7$	$7 - 9$	$9 - 11$	$11 - 12$	$12 - 15$
In esecuzione	$P_{1}$	$P_{2}$	$P_{3}$	$P_{4}$	$P_{1}$	$P_{3}$	$P_{1}$	$P_{3}$
Nella ready queue	$P_{2}$	$P_{3}$	$P_{4}$	$P_{1}$	$P_{3}$	$P_{1}$	$P_{3}$
	$P_{3}$	$P_{4}$	$P_{1}$	$P_{3}$
	$P_{4}$	$P_{1}$

Calcoliamo ora il tempo di risposta (response time), di attesa (waiting time), e di completamento (turnaround time) di ogni processo.

Processo	$T_{R}$	$T_{W}$	$T_{T}$
$P_{1}$	$0$	$(7 - 2) + (11 - 9) = 7$	$7 + 5 = 12$
$P_{2}$	$2$	$2$	$2 + 1 = 3$
$P_{3}$	$3$	$3 + (9 - 5) + (12 - 11) = 8$	$7 + 7 = 15$
$P_{4}$	$5$	$5$	$5 + 2 = 7$

Code multilivello

Anzichè utilizzare un unico algoritmo ed un'unica queue, è possibile adottare un algoritmo più generale che preveda $N$ code, ognuna con una specifica priorità e algoritmo di scheduling.
Esempio:

Una coda per job in foreground (interattivi) gestiti con RR
Una coda per job in background (batch) gestiti con FCFS

E’ un meccanismo più generale, ma anche più complesso. Diventa così necessario un algoritmo di scheduling fra le code. Vediamone due, uno semplice e uno più complesso.

Scheduling a priorità fissa (più semplice)
- ogni coda ha una sua priorità fissa (un processo viene inserito in una coda a seconda della sua priorità)
- servo prima tutti i job di sistema, poi quelli in foreground, poi quelli in background
- Si può ovviamente incorrere in starvation dei processi a bassa priorità
Scheduling basato su time slice (più complesso)
- Ogni coda ottiene un quanto del tempo di CPU che può usare per schedulare i suoi processi (le code con priorità più alta ottengono una percentuale di utilizzo maggiore)
- Esempio
  - 80% per job di foreground con RR
  - 20% per job di background con FCF

Code multilivello con feedback

In entrambe queste tecniche, la coda di un processo è fissa, non c'è modo per un processo di cambiare coda e di conseguenza priorità. Si ottiene con uno scheduler multilivello con feedback una struttura più flessibile. I processi possono cambiare code, salendo o scendendo di priorità, in base a specifici eventi. Ad esempio, un processo in una coda con RR che non finisce la sua esecuzione nel quanto di tempo assegnatogli, può essere degradato ad una coda con priorità minore e diverso scheduling. Tale strategia può essere inoltre usata per implementare l'aging, aumentanto il waiting time, il processo può essere spostato a code con priorità maggiore. Questo modello rimane tuttavia più complesso a causa dell'ulteriore livello di scheduling aggiunto.

Esempio:
Abbiamo 3 code:

Coda $Q_{0}$ : RR con quanto 8 ms
Coda $Q_{1}$ : RR con quanto 16 ms
Coda $Q_{2}$ : FCFS
La CPU serve nell’ordine $Q_{0}$ , $Q_{1}$ , $Q_{2}$

Coda multilivello.png|700

Vediamone il funzionamento:

Un job “nuovo” entra in $Q_{0}$ . Quando ottiene la CPU, riceve 8 ms di quanto. Se non finisce entro il quanto, viene prelazionato e degradato (spostato) alla coda $Q 1$
Se $Q_{0}$ è vuota, si seleziona un job di $Q 1$ che riceve 16 ms di quanto. Se non finisce viene prelazionato e messo in $Q_{2}$ . Se $Q_{0}$ e $Q_{1}$ sono vuote, viene selezionato un job in $Q_{2}$ con FCFS.

Le politiche di scheduling fino ad ora sono state orientate ai processi, mentre con FFS si schedulano utenti o gruppi di processi. Ad esempio si possono schedulare tutti i processi di una specifica applicazione. L'obiettivo è quello di fornire a ciascun gruppo di processi/utente la stessa percentuale di utilizzo di CPU.

Valutare un algoritmo di scheduling

In quanto differenti sistemi richiedono differenti prestazioni, è opportuno applicare delle tecniche per valutare gli algoritmi di scheduling in differenti contesti.

Modello deterministico

Si definisce un workflow (insieme di processi con determinate caratteristiche) e lo si testa su carta con gli algoritmi descritti. Semplice e rapido, ma accurato solo per il workflow specifico, cioè definisce le prestazioni di ogni algoritmo per “quello” specifico carico.

Modello a reti di code

Si stimano matematicamente intensità e probabilità dei burst. Il modello è descritto come un rete di server, ognuno con una coda e rappresentante una CPU o un dispositivo di I/O. Si usano formule matematiche che permettono di ricavare utilizzo, throughput medio, tempi di attesa, ecc. Relativamente semplice ed adattabile, spesso produce risultati poco realistici.

Simulazione

Si simula lo scheduler con un apposito software e dei grandi dataset. I risultati sono molto precisi, ma l'esecuzione è lenta ed è un modello molto costoso.

Implementazione su macchina

È il metodo più preciso e l'unico che permette di avere dei risultati sicuri. Si implementa l'algoritmo in un SO e si misurano le prestazioni con un reale carico di lavoro.

6. Scheduling della CPU

Tipi di scheduler

Dispatcher

Prelazione

Metriche di scheduling

Algoritmi di scheduling

First Come First Served (FCFS)

Esempio

Esempio 2

Shortest Job First (SJF)

Esempio 1 - non-preemptive

Esempio 2 - preemptive

Scheduling a priorità

Esempio

Highest Response Ratio First (HRRN)

Esempio

Round Robin (RR)

Esempio

Code multilivello

Code multilivello con feedback

Fair Share Scheduling (FFS)

Valutare un algoritmo di scheduling

Modello deterministico

Modello a reti di code

Simulazione

Implementazione su macchina