Schedulazione della CPU
Schedulazione della CPU
Alternare la CPU tra processi per rendere
il computer più produttivo
NEW
END
READY
RUN
WAIT
Schedulazione
Processi e Thread
Schedulazione della CPU
1 Processore
1 Processo
Più processi in memoria
Un processo è eseguito fino a quando non deve attendere
Durante tale tempo la CPU è assegnata ad un altro processo
Schedulazione
La schedulazione è un’attività fondamentale del S.O.
Tutte le risorse sono schedulate
CPU è una risorsa fondamentale
Ciclo picco ed I/O
CPU
Esecuzione di un processo:
I/O
La durata dei picchi di CPU hanno un andamento
Esponenziale o IperEsponenziale
Ciclo picco ed I/O
I/O Bound
CPU Bound
Molti picchi di CPU brevi
Pochi picchi di CPU lunghi
Scelta degli algoritmi di Schedulazione
Schedulazione della CPU
Short Term Scheduler gestisce una coda di PCB
• FIFO
• A Priorità
• Ad Albero
• Lista Linkata
Schedulazione della CPU
1. Processo passa da esecuzione in attesa
2. Processo passa da esecuzione in ready
3. Processo passa da attesa in ready
4. Processo termina
1 e 4 ----------
2 e 3 ----------
Esecuzione nuovo processo
possibilità di scelta
Nonpreempitive
e
Preempitive
Preempitive
•
Dati condivisi
•
Progettazione del Kernel
• Interrupt
Schedulazione della CPU
Dispatcher: carica il processo in CPU
• Cambio di contesto
• passaggio alla modalità utente
• scelta dell’indirizzo corrente del programma
Latenza del Dispatcher
Criteri di Valutazione
• Utilizzo della CPU
• Throughput (freq. di completamento)
• Turnaround time (tempo di completamento)
• Tempo di attesa (tempo nella coda di ready)
• Tempo di risposta (tempo tra richiesta e risposta)
Obiettivo
Massimizzare CPU ed il Throughput
Minimizzare turnaround time, tempo di attesa e di risposta
Ottimizzare il valor medio, minimo o massimo
Es: buon servizio agli utenti  minimizzare il tempo
max di risposta
Minimizzare la varianza del tempo di risposta
FIRST-COME, FIRST-SERVED (FCFS)
Tempo di attesa medio lungo (nonpreemptive)
P1
P2
0
24
P3
27
30
(0 + 24 + 27)/3 = 17 ms
P2
0
P3
3
P1
6
30
(0 + 3 + 6)/3 = 3 ms
1 processo CPU-bound e 3 processi I/O-bound (convoy effect)
SHORT-JOB-FIRST (SJF)
Processi con picco di CPU successivo più breve
P1 
P2 
P3 
P4 
P4
0
6
8
7
3
P1
3
P3
9
P2
16
24
(0 + 3+9+16)/4 = 7 ms
FCFS
P1
0
P2
6
P3
14
P4
21
(0 + 6+14+21)/4 = 10.25 ms
24
SHORT-JOB-FIRST (SJF)
Come si conosce la durata del picco successivo?
n+1 = tn + (1- ) n
0≤≤1
Media esponenziale ( = ½)
SHORT-JOB-FIRST (SJF)
Preemptive e nonpreemptive
P1
P2
0
1
P1  8
P2  4
P3  9
(arrivo a t=0)
( “” “ t=1)
( “” “ t=2)
P4  5
(
P4
5
“”
“ t=3)
P1
10
P3
17
26
(9 + 0+15+2)/4 = 6.5 ms
Nonpreemptive
P1
0
P2
8
P4
12
P3
17
(0 + 7+15+9)/4 = 7.75 ms
26
Schedulazione a priorità
CPU allocata al processo con priorità più alta
SJF caso particolare con priorità = (tempo picco CPU)
Schedulazione a Priorità
P1  10 (pri=3)
P2  1 (pri=1)
P3  2 (pri=4)
P4  1
P5  5
P2
0
P5
1
(pri=5)
(pri=2)
P1
6
P3
16
P4
18
(6 + 0+16+18+1)/5 = 8.2 ms
19
Schedulazione a Priorità
Interne ed Esterne
Memoria
Files
Fattori Esterni
Preemptive e nonpreempitive
Starvation (aging)
Round Robin
FCFS Circolare
Preemptive
Time Slice [10,100] ms
P1  24
P2  3
P3  3
P1
0
P2
4
Time Slice = 4 ms
P3
7
P1
10
(0 + 4+7+6)/3 = 5.66 ms
30
Round Robin
Dimensione del Time Slice
Time Slice grande
RR  FCFS
Time Slice piccolo
Condivisione Processore
Time Slice + Cambio di contesto
Code a più livelli
Foreground e
Background
(con priorità)
In generale si possono avere più code
Con algoritmi differenti
Schedulazione tra code
(Preemptive a priorità fissa)
(A divisione di tempo)
Code a più livelli
Variante con Retroazione
Processi si muovono tra code
(es: se usa troppa CPU mosso in coda a priorità
più bassa)
Schedulazione su Multiprocessore
Processori omogenei
Suddivisione del carico
Una coda per
Ogni processore
Una coda per tutti
I processori
AMP
SMP