Scheduling della CPU
 Concetti fondamentali
 Criteri di scheduling
 Algoritmi di scheduling
 Valutazione degli algoritmi
Operating System Concepts
6.1
Silberschatz, Galvin and Gagne 2002
Concetti fondamentali
 Il
massimo impiego della CPU è
ottenuto con la multiprogrammazione.
 Ciclo di CPU–I/O burst — L’esecuzione
di un processo consiste di cicli di
esecuzione da parte della CPU ed
attese di I/O.
Distribuzione dei burst di CPU
Operating System Concepts
6.2
Silberschatz, Galvin and Gagne 2002
Scheduler della CPU
 Sceglie, fra i processi in memoria pronti ad essere
eseguiti, un processo cui allocare la CPU.
 Lo scheduler della CPU deve prendere una decisione
quando un processo…
1. …passa da stato running a stato waiting (richiesta di I/O
o attesa terminazione di un processo figlio);
2. …passa da stato running a stato ready (interrupt);
2. …passa da stato waiting a stato ready (completamento
di un I/O);
3. …termina.
 Se lo scheduling viene effettuato solo nei casi 1 e 4, si
dice che lo schema di scheduling è non–preemptive
(senza prelazione; es. Windows).
 Altrimenti si ha uno schema preemptive.
Operating System Concepts
6.3
Silberschatz, Galvin and Gagne 2002
Dispatcher
 Il modulo dispatcher passa il controllo della CPU al
processo selezionato dallo scheduler a breve termine; il
dispatcher effettua:
 Context switch
 Passaggio a modo utente
 Salto alla posizione corretta del programma utente per
riavviarne l’esecuzione
 Latenza di dispatch — è il tempo impiegato dal dispatcher
per sospendere un processo e avviare una nuova
esecuzione.
Operating System Concepts
6.4
Silberschatz, Galvin and Gagne 2002
Criteri di scheduling
 Utilizzo di CPU — la CPU deve essere più attiva possibile.
 Throughput — numero di processi che completano la loro
esecuzione nell’unità di tempo.
 Tempo di turnaround — tempo impiegato per l’esecuzione
di un determinato processo.
 Tempo di attesa — tempo speso dal processo in attesa
nella ready queue.
 Tempo di risposta — tempo che intercorre tra la
sottomissione di una richiesta e la prima risposta prodotta.
In un sistema time–sharing il tempo di turnaround può
essere influenzato dalla velocità del dispositivo di output.
Operating System Concepts
6.5
Silberschatz, Galvin and Gagne 2002
Criteri di ottimizzazione
 Massimo utilizzo di CPU
 Massimo throughput
 Minimo tempo di turnaround
 Minimo tempo di attesa
 Minimo tempo di risposta
Operating System Concepts
6.6
Silberschatz, Galvin and Gagne 2002
Scheduling First–Come–First–Served (FCFS)
ESEMPIO 1
Processo Tempo di burst
P1
24
P2
3
P3
3
 I processi arrivano al sistema nell’ordine: P1 , P2 , P3.
Il diagramma di Gantt per lo scheduling FCFS è:
P1
P2
0
24
P3
27
30
 Tempi di attesa: P1 = 0; P2 = 24; P3 = 27.
 Tempo medio di attesa = (0 + 24 + 27)/3 = 17.
Operating System Concepts
6.7
Silberschatz, Galvin and Gagne 2002
Scheduling FCFS
Se l’ordine di arrivo è
P2 , P3 , P1,
il diagramma di Gantt risulta…
P2
0
P3
3
P1
6
30
 Tempi di attesa: P1 = 6; P2 = 0; P3 = 3.
 Tempo medio di attesa = (6 + 0 + 3)/3 = 3.
 Non si verifica l’effetto convoglio, per cui processi di
breve durata devono attendere che un processo
molto lungo liberi la CPU.
Operating System Concepts
6.8
Silberschatz, Galvin and Gagne 2002
Scheduling Shortest–Job–First (SJF)
 Si associa a ciascun processo la lunghezza del suo burst
di CPU successivo. Si opera lo scheduling in base alla
brevità dei CPU burst.
 Due schemi:
 non–preemptive — una volta che la CPU è stata allocata
al processo, non gli può essere prelazionata fino al termine
del CPU burst corrente;
 preemptive — se arriva un nuovo processo con burst di
CPU minore del tempo rimasto per il processo corrente, il
nuovo processo prelaziona la CPU. Questo schema è noto
come Shortest–Remaining–Time–First (SRTF).
 SJF è ottimale — rende minimo il tempo medio di attesa
per un dato insieme di processi.
Operating System Concepts
6.9
Silberschatz, Galvin and Gagne 2002
Scheduling SJF non–preemptive
ESEMPIO 2
Processo Tempo di arrivo Tempo di burst
P1
0.0
7
P2
2.0
4
P3
4.0
1
P4
5.0
4
 SJF (non–preemptive):
P1
0
3
P3
7
P2
8
P4
12
16
 Tempo medio di attesa = (0 + 6 + 3 + 7)/4 = 4.
Operating System Concepts
6.10
Silberschatz, Galvin and Gagne 2002
Scheduling SJF preemptive
ESEMPIO 3
Processo Tempo di arrivo Tempo di burst
P1
0.0
7
P2
2.0
4
P3
4.0
1
P4
5.0
4
 SJF (preemptive):
P1
0
P2
2
P3
4
P2
5
P4
7
P1
11
16
 Tempo medio di attesa = (9 + 1 + 0 +2)/4 = 3.
Operating System Concepts
6.11
Silberschatz, Galvin and Gagne 2002
Predizione della lunghezza del CPU burst successivo
 Può essere stimato utilizzando la lunghezza dei burst di
CPU precedenti, impiegando una media esponenziale.
1. t n  lunghezza dell' n  esimo CPU burst
2.  n 1  valore stimato del prossimo CPU burst
3.  , 0    1
4. Si definisca :
 n1   tn  1    n .
Operating System Concepts
6.12
Silberschatz, Galvin and Gagne 2002
Esempi di media esponenziale
  =0
 n+1 = n
 La storia recente non è presa in considerazione.
  =1
 n+1 = tn
 Viene considerato soltanto l’ultimo CPU burst.
 Espandendo la formula si ottiene:
n+1 =  tn+(1-)  tn-1 + … + (1- )j  tn-j + … +(1- )n+1 0
 Poiché  e (1- ) sono entrambi minori o uguali ad 1,
ciascun termine ha minor peso del suo predecessore.
Operating System Concepts
6.13
Silberschatz, Galvin and Gagne 2002
Scheduling a priorità
 Un valore di priorità (intero) è associato a ciascun processo.
 La CPU viene allocata al processo con la priorità più alta
(intero più basso  priorità più alta).
 preemptive
 non–preemptive
 SJF è uno
scheduling a priorità dove la priorità è
rappresentata dal successivo tempo di burst.
 Problema  Starvation (blocco indefinito) — i processi a
bassa priorità potrebbero non venir mai eseguiti.
 Soluzione  Aging (invecchiamento) — aumento graduale
della priorità dei processi che si trovano in attesa nel
sistema da lungo tempo.
Operating System Concepts
6.14
Silberschatz, Galvin and Gagne 2002
Scheduling Round Robin (RR)
 A ciascun processo viene allocata una piccola unità di
tempo di CPU (quanto di tempo), generalmente 10–100
millisecondi. Dopo un quanto di tempo, il processo è
forzato a rilasciare la CPU e accodato alla ready queue.
 Se ci sono n processi nella ready queue ed il quanto di
tempo è q, ciascun processo occupa 1/n del tempo di
CPU in frazioni di, al più, q unità di tempo. Nessun
processo attende per più di (n -1)q unità di tempo.
 Prestazioni:
 q grande  FIFO
 q piccolo  q deve essere grande rispetto al tempo di
context switch, altrimenti l’overhead è troppo alto.
Operating System Concepts
6.15
Silberschatz, Galvin and Gagne 2002
Scheduling RR con quanto = 20
ESEMPIO 4
Processo
Tempo di burst
P1
53
P2
17
P3
68
P4
24
 Il diagramma di Gantt è:
P1
0
P2
20
37
P3
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
 In genere si ha un tempo medio di turnaround maggiore
rispetto a SJF, tuttavia si ha una miglior tempo di risposta.
Operating System Concepts
6.16
Silberschatz, Galvin and Gagne 2002
Quanto di tempo VS context switch
Un quanto di tempo minore incrementa il numero di context switch
Operating System Concepts
6.17
Silberschatz, Galvin and Gagne 2002
Quanto di tempo e tempo di turnaround
Empiricamente: il
quanto di tempo
deve essere > o =
dell’80% dei CPU
burst.
Variazione del tempo di turnaround in funzione
della lunghezza del quanto di tempo
Operating System Concepts
6.18
Silberschatz, Galvin and Gagne 2002
Scheduling con code multiple
 La ready queue è suddivisa in code separate:
 foreground (interattiva)
 background (batch)
 Ciascuna coda ha il suo proprio algoritmo di scheduling:
 foreground – RR
 background – FCFS
 È necessario uno scheduling tra code.
 Scheduling a priorità fissa ; es. serve
tutti i processi in foreground poi in
background. Rischio di starvation.
 Time slice : ciascuna coda occupa un
certo tempo di CPU che suddivide fra
i propri processi. Ad esempio:
 80% per foreground in RR
 20% per background in FCFS
Operating System Concepts
6.19
Silberschatz, Galvin and Gagne 2002
Code multiple con feedback
 Un processo può spostarsi fra le varie code; l’aging può
essere implementato in questo modo.
 Lo scheduler con code multiple con feedback è definito
dai seguenti parametri:
 Numero di code
 Algoritmi di scheduling per ciascuna coda
 Metodo impiegato per determinare quando spostare un
processo in una coda a priorità maggiore
 Metodo impiegato per determinare quando spostare un
processo in una coda a priorità minore
 Metodo impiegato per determinare in quale coda deve
essere posto un processo quando richiede un servizio
Operating System Concepts
6.20
Silberschatz, Galvin and Gagne 2002
Esempio di code multiple con feedback
 Tre code: Q0 – quanto di tempo di 8 millisecondi; Q1 – quanto di
tempo di 16 millisecondi; Q2 – FCFS.
 Scheduling:
 Un nuovo job viene immeso nella coda Q0 che è servita RR. Quando
prende possesso della CPU il job riceve 8 millisecondi. Se non termina,
viene spostato nella coda Q1.
 Nella coda Q1 il job è ancora servito RR e riceve ulteriori 16
millisecondi. Se ancora non ha terminato, viene mosso nella coda Q2.
Operating System Concepts
6.21
Silberschatz, Galvin and Gagne 2002
Valutazione degli algoritmi
 Modellazione deterministica — prende in considerazione
un carico di lavoro predeterminato e definisce le
prestazioni di ciascun algoritmo per tale carico di lavoro.
 Modelli di code — modelli statistici del comportamento
del sistema.
 Simulazioni.
Valutazione di scheduler di CPU tramite simulazione
Operating System Concepts
6.22
Silberschatz, Galvin and Gagne 2002