Scheduling della CPU
•
•
•
•
•
Concetti di base
Criteri di scheduling
Algoritmi di scheduling
Scheduling in sistemi con più processori
Valutazione degli algoritmi
Sistemi operativi
5.1
Concetti di base
•
•
•
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 di
CPU ed attese di I/O.
Distribuzione dei burst di CPU
 Istogramma burst di CPU
Sistemi operativi
5.2
Scheduler della CPU
•
•
•
•
Seleziona uno dei processi in memoria che sono pronti ad essere
eseguiti ed alloca la CPU a questo processo.
Le decisioni dello scheduling di CPU hanno luogo quando un
processo:
1. Passa da stato running a stato waiting.
2. Passa da stato running a stato ready.
3. Passa da stato waiting a stato ready.
4. Termina.
Se lo scheduling è solo nelle condizioni 1 e 4, si dice che lo
schema di scheduling è non–preemptive (senza prelazione).
Altrimenti si ha uno schema preemptive.
Sistemi operativi
5.3
Dispatcher
•
•
Il modulo dispatcher da il controllo della CPU al processo
selezionato dallo scheduler a breve termine; questo comporta:
– Context switch
– Passaggio a modo utente
– Salto alla posizione corretta del programma utente per
riavviarne l’esecuzione
Latenza di dispatch – è il tempo che impiega il dispatcher per
fermare un processo e avviare l’esecuzione di un altro.
Sistemi operativi
5.4
Criteri di Scheduling
•
•
Utilizzo di CPU – la CPU deve essere più attiva possibile
•
Tempo di turnaround – tempo impiegato per l’esecuzioned di
un determinato processo
•
Tempo di attesa – tempo durante il quale un processo si è
trovato nella coda ready
•
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 limitato dalla velocità
del dispositivo di output
Throughput – numero di processi che completano la loro
esecuzione per unità di tempo
Sistemi operativi
5.5
Criteri di ottimizzazione
•
•
•
•
•
Max utilizzo di CPU
Max throughput
Min tempo di turnaround
Min tempo di attesa
Min tempo di risposta
Sistemi operativi
5.6
Scheduling First–Come, First–Served (FCFS)
•
•
Esempio:
Processo
Burst Time
P1
24
P2
3
P3
3
Supponendo che i processi arrivino nel seguente ordine: P1, P2, P3
llo schema di Gantt è il seguente:
P1
P2
0
•
•
24
Tempi di attesa P1 = 0; P2 = 24; P3 = 27
Tempo di attesa medio: (0 + 24 + 27)/3 = 17
Sistemi operativi
5.7
P3
27
30
Scheduling FCFS
Se l’ordine di arrivo è il seguente:
P2, P3, P1.
•
Lo schema di Gantt è il seguente:
P2
0
•
•
•
P3
3
P1
6
30
Tempi di attesa: P1 = 6; P2 = 0; P3 = 3
Tempo di attesa medio: (6 + 0 + 3)/3 = 3
Molto migliore del caso precedente, in cui si aveva un effetto
convoglio: i processi piccoli attendono che un grande processo
liberi la CPU
Sistemi operativi
5.8
Scheduling Shortest–Job–First (SJF)
•
•
•
Si associa a ciascun processo la lunghezza del suo successivo
burst di CPU. SI impiegano queste lunghezze per assegnare alla
CPU il processo con il burst più breve.
Due schemi:
– nonpreemptive – una volta che la CPU viene assegnata al
processo, non può essere assegnata ad un altro processo
fino a che quello corrente non termina il burst di CPU.
– preemptive – se arriva un nuovo processo con burst di CPU
minore del tempo rimasto per il processo corrente, il nuovo
processo viene sostituito all’altro. Questo schema è noto
come Shortest–Remaining–Time–First (SRTF).
SJF è ottimale – rende minimo il tempo medio di attesa per un
dato insieme di processi.
Sistemi operativi
5.9
Esempio di SJF nonpreemptive
•
Processo
Tempo di arrivo
Burst Time
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
tempo medio di attesa = (0 + 6 + 3 + 7)/4 - 4
Sistemi operativi
5.10
16
Esempio di SJF Preemptive
•
Tempo di arrivo
Burst Time
P1
0.0
7
P2
2.0
4
P3
4.0
1
P4
5.0
4
SJF (preemptive)
P1
0
•
Processo
P2
2
P3
4
P2
5
P4
7
P1
11
tempo medio di attesa = (9 + 1 + 0 +2)/4 - 3
Sistemi operativi
5.11
16
Predizione della lunghezza del busrt di CPU successivo
•
•
Può soltanto stimare la lunghezza.
Può essere stimato utilizzando la lunghezza dei burst di CPU
precedenti, impiegando una media esponenziale.
1) tn lunghezza dell’n-mo burst di CPU
2) n+1 valore stimato per il CPU–burst successivo
3) , 0    1
4) n+1 =  tn + (1-  )n
Sistemi operativi
5.12
Esempi di media esponenziale
•
 =0
– n+1 = n
– La storia recente non è presa in considerazione.
•
 =1
– n+1 = tn
– Viene preso in considerazione solo l’ultimo burst di CPU.
•
•
Espandendo la formula si ottiene:
n+1 =  tn+(1 - )  tn -1 + …
+(1 -  )j  tn -1 + …
+(1 -  )n=1 tn 0
Dato che sia  che (1 - ) sono minori o uguali a 1, ciascun
termine successivo ha minor peso del suo predecessore.
Sistemi operativi
5.13
Scheduling a priorità
•
•
•
Un valore di priorità (intero) è associato con ciascun processo.
La CPU è allocata al processo con la più grande priorità (intero
più basso  priorità più alta).
– preemptive
– nonpreemptive
SJF è uno scheduling a priorità dove la priorità è il successivo
tempo di burst stimato.
•
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.
Sistemi operativi
5.14
Round Robin (RR)
•
•
•
Ciascun processo prende una piccola unità di tempo di CPU
(quanto di tempo), generalmente 10-100 millisecondi. Dopo che
questo tempo è trascorso, il processo è forzato a rilasciare la
CPU e aggiunto alla fine della coda dei processi pronti (ready
queue).
Se ci sono n processi nella ready queue e il quanto di tempo è q,
ciascun processo prende 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.
Performance
– q grande  FIFO
– q piccolo  q deve essere grande rispetto al tempo di
context switch, altrimenti l’overhead è troppo alto.
Sistemi operativi
5.15
Esempio: RR con quanto di tempo = 20
•
Burst Time
P1
53
P2
17
P3
68
P4
24
Lo schema di Gantt è:
P1
0
•
Processo
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 migliore risposta.
Sistemi operativi
5.16
Un quanto di tempo minore incrementa i context switch
Sistemi operativi
5.17
Tempo di turnaround varia con il quanto di tempo
Sistemi operativi
5.18
Scheduling con code multiple
•
•
•
La ready queue è suddivisa in code separate:
foreground (interattiva)
background (batch)
Ciascuna coda ha il proprio algoritmo di scheduling,
foreground – RR
background – FCFS
Inoltre è 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 prende un certo
tempo di CPU che può suddividere fra i propri
processi. Ad esempio
 80% per foreground in RR
 20% per background in FCFS
Sistemi operativi
5.19
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
Sistemi operativi
5.20
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 FCFS. Quando
prende possesso della CPU il job riceve 8 millisecondi. Se non termina in 8
millisecondi il job è spostato alla coda Q1.
– Nella coda Q1 il job è ancora servito FCFS e riceve ancora 16 millisecondi.
Se ancora non ha terminato, viene mosso nella coda Q2.
Sistemi operativi
5.21
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.
Simulazioni
Realizzazione
Sistemi operativi
5.22