Scheduling della CPU!
5.2!
Capitolo 5: Scheduling della CPU!
Criteri di Scheduling!
Algoritmi di Scheduling!
Cenni Scheduling per sistemi multprocessore !!
Modelli Asimmetrico e Simmetrico!
Concetti di Base!
Massimizzare l’utilizzo della CPU mediante multiprogrammazione!
CPU–I/O Burst Cycle !
Processo alterna cicli di CPU ad attese di I/O!
Distribuzione dei cicli di CPU (CPU-burst)!
Alternanza di Sequenze di CPU- e I/O-Burst!
5.5!
Istogramma dei CPU-burst!
5.6!
Scheduling!
Scheduler a lungo termine !
Decide quali tra i job richiesti vanno selezionati per essere schedulati!
Decide il grado di multiprogrammazione e crea il giusto mix di programmi !
Scheduler a breve termine!
Decide quale processo pronto attivare!
Il vero e proprio schedulatore della CPU!
Scheduler a medio termine!
Controlla lo swap in and swap out dei processi!
Fa il tuning del grado di multiprogrammazione!
Può liberare memoria per altri processi !
Schedulatore della CPU!
Sceglie tra i processi pronti quello da eseguire e assegna la CPU!
La Schedulazione della CPU avviene quando un processo:!
1.!Passa da attivo in stato di attesa!
2.!Passa da attivo a stato di pronto!
3.!Passa da stato di attesa a stato di pronto!
4.!Termina!
Scheduling secondo 1 e 4 e’ non-preemptive (senza prelazione)!
Se si schedula secondo 2 e 3, preemptive (con prelazione)!
Dispatcher!
Il Dispatcher passa il controllo della CPU al processo selezionato dallo schedulatore a breve termine: !
Cambia il contesto (context switch)!
Passa in modalità utente!
Salta alla locazione giusta da cui il processo schedulato deve ripartire!
Latenza di Dispatch latency – tempo necessario al dispatcher
per fermare un processo e farne ripartire un altro!
5.9!
Criteri di Scheduling!
Utilizzo/efficienza della CPU!
CPU quasi sempre occupata!
Throughput – # di processi completati per unità di tempo!
Tempo di Turnaround – tempo necessario per completare un particolare processo!
Tempo di attesa – tempo trascorso dal processo nella coda di dei processi in stato di pronto!
Tempo di risposta – tempo trascorso dal momento in cui una richiesta viene sottoposta al sistema fino al momento in cui una prima risposta appare in output, tempo necessario a servire una sottorichiesta
(importante in ambienti time-sharing)!
5.10!
Criteri di Ottimizzazione!
Massimizza uso di CPU!
Massimizza throughput!
Minimizza turnaround!
Minimizza tempo d’attesa !
Minimizza tempo di risposta!
Politiche di Scheduling!
FCFS – serve le richieste nell’ordine di arrivo!
SJF – preferisce processi brevi !
Round robin – alterna in maniera ordinata!
Highest Response Ratio Next – cerca di bilanciare tra processi brevi limitando i tempi di attesa!
First-Come, First-Served (FCFS) Scheduling (in ordine di arrivo)!
! ! Process !Burst Time !!
! !P
1!24!
! ! P
2!3!
! ! P
3 !3
!
I processi arrivano nell’ordine: P
1, P
2, P
3al tempo 0!
Il diagramma di Gantt per la schedulazione:
!
!
Tempo di attesa: P
1= 0; P
2= 24; P
3= 27!
Tempo medio di attesa: (0 + 24 + 27)/3 = 17!
P
1! P
2! P
3!
24! 27! 30!
0!
5.13!
FCFS Scheduling (Cont.)!
Consideriamo ora l’ordine di arrivo!
! ! P
2, P
3, P
1!
Il diagramma di Gantt diventa:
!
Tempi di attesa: P
1= 6; P
2= 0
;P
3= 3!
Tempo medio di attesa: (6 + 0 + 3)/3 = 3!
Miglioramento significativo!
Evitato l’effetto convoglio: processi brevi dopo processi lunghi!
P
1! P
3!
P
2!
6!
3! 30!
0!
5.14!
Shortest-Job-First (SJF) Scheduling!
Scegli il processo con il più piccolo CPU burst!
Schemi possibili: !
Non-preemptive – una volta assegnata la CPU ad un processo attendi fino a completamento del CPU burst!
preemptive – se un nuovo processo arriva con CPU burst più breve del tempo rimanente al CPU burst del processo in esecuzione, prelaziona!
Schema noto come: Shortest-Remaining-Time-First (SRTF)!
SJF ottimizza (minimizza) il tempo medio di attesa!
! !Process !Arrival Time !Burst Time!
! !P
1!0 !7!
! ! P
2 !2 !4!
! ! P
3!4 !1!
! ! P
4!5 !4!
SJF (non-preemptive)!
Tempo media di attesa = (0 + 6 + 3 + 7)/4 = 4
!Esempio di SJF Non-Preemptive!
P
1! P
3! P
2!
7!
3! 16!
0!
P
4!
8! 12!
Esempio di SJF Preemptive (SRTF) !
! !Process !Arrival Time !Burst Time!
! !P
1!0 !7!
! ! P
2 !2 !4!
! ! P
3!4 !1!
! ! P
4!5 !4!
SJF (preemptive)!
Tempo medio di attesa = (9 + 1 + 0 +2)/4 = 3
!P
1! P
2! P
3!
4!
2! 11!
0!
P
4!
5! 7!
P
2! P
1!
16!
5.17!
SJF Preemptive e non-preemptive !
! !Process !Arrival Time !Burst Time!
! !P
1!0 !7!
! ! P
2 !2 !4!
! ! P
3!4 !1!
! ! P
4!5 !4!
SJF (preemptive) – tempo di attesa media = 3!
SJF non preemptive – tempo di attesa media = 4!
P
1! P
2! P
3!
4!
2! 11!
0!
P
4!
5! 7!
P
2! P
1!
16!
P
1! P
3! P
2!
7!
3! 16!
0!
P
4!
8! 12!
5.18!
La Lunghezza dei CPU Burst!
Possiamo solo stimare tale lunghezza!
Possibilità: usa le lunghezza dei precedenti CPU burst!
Es.: media esponenziale!
!
!
€
1. t
n= lunghezza effettiva dell'n
moCPU burst 2. τ
n +1= valore atteso del prossimo CPU burst 3. α, 0 ≤ α ≤ 1
4. Definisci :
€
τ
n +1= α t
n+ 1− ( α ) τ
n.
Previsione della lunghezza di CPU Burst! Es.: Media Esponenziale!
α =0!
τ
n+1= τ
n!
La storia (recente) non ha valore!
α =1!
τ
n+1= α t
n!
Solo il precedente CPU burst ha valore!
Se espandiamo la formula otteniamo:!
τ
n+1= α t
n+(1 - α) τ
n!
= α t
n+(1 - α) (α t
n-1+ (1 - α) τ
n-1)!
= α t
n+(1 - α) α t
n-1+ (1 - α)
2τ
n-1!
= α t
n+(1 - α) α t
n-1+ (1 - α)
2α t
n-2+(1 - α)
3τ
n-2!
… = α t
n+(1 - α) α t
n-1+… (1 - α)
kα t
n-k+ …(1 - α)
n+1τ
0!
Nota che α e (1 - α) sono ≤ 1, quindi ogni termine nella formula pesa meno del precedente!
€
τ
n +1= α t
n+ 1− ( α ) τ
n.
5.21!
Scheduling a Priorità!
Ogni processo ha associato un valore di priorità (intero)!
La CPU è allocata al processo con priorità più alta (spesso numeri piccoli indicano priorità alta)!
Preemptive!
Non-preemptive!
SJF è uno sceduling a priorità definita dal tempo (previsto) di CPU burst.!
Problemi: Starvation – processi con priorità bassa potrebbero essere “dimenticati”!
Soluzione: Aging – incrementare la priorità dei processi in funzione del tempo trascorso in stato di pronto!
5.22!
Highest Response Ratio Next!
w : tempo speso dal processo in stato di pronto dall’ultima schedulazione!
s : tempo totale necessario al processo (sottorichiesta) per arrivare a terminazione (risposta)!
R = (w+s)/s!
Lo scheduling HRRN sceglie il processo con max R!
Processi brevi hanno “priorità” !
Implementa una sorta di “aging” implicito!
!
!
Round Robin (RR)!
Ogni processo riceve la CPU per un breve intervallo (time quantum), tipicamente 10-100 millisecondi. Passato tale quanto di tempo, il processo ritorna alla fine della coda dei processi in stato di pronto.!
Con n processi nella coda e un quanto di tempo = q, ogni processo riceve 1/n di CPU time in blocchi di q unità per volta.
Nessun processo attende più di (n-1)q unità.!
Performance!
q grande ⇒ FIFO!
q piccolo ⇒ q deve esser maggiore del tempo di context switch, per evitare un overhead eccessivo!
Es.: RR con quanto di tempo = 20!
! !Process !Burst Time!
! !P
1 !53!
! ! P
2 !17!
! ! P
3 !68!
! ! P
4 !24!
Il diagramma di Gantt:
!
In genere, rispetto a SJF, il tempo di turnaround è più alto, ma risulta migliore il tempo di risposta!
P
1! P
2!P
3!P
4!P
1!P
3!P
4!P
1!P
3!P
3!0! 20! 37! 57! 77! 97! 117! 121! 134! 154! 162!
5.25!
Tempo di Context Switch!
5.26!
Turnaround Time (medio) dipende da q!
Code Multilivello!
La coda dei processi pronti divisa in code separate:!
es.: foreground (interactive) e background (batch)!
Ogni coda è gestita dal proprio algoritmo di scheduling!
foreground – RR!
background – FCFS!
Scheduling tra le code!
Scheduling a priorità fissa; (es. prima tutti i processi in foreground quindi quelli in background). Rischio di starvation.!
Time slice – ogni coda ha assegnata una percentuale di tempo di CPU in cui può schedulare i propri processi;!
es.: 80% ai processi foreground con RR!
–
20% ai processi background con FCFS !
Code Multilivello!
5.29!
Code Multilivello con retroazione!
Processi possono cambiare coda; !
Possibilità di implementare tecniche di aging!
Parametri critici:!
numero di code!
Algoritmo di scheduling usato in ciascuna coda!
Criterio di promozione dei processi tra le code!
Criterio di declassamento dei processi tra le code!
Criterio di assegnazione di un processo ad una coda in funzione del servizio richiesto!
5.30!
Es.: Code Multilivello con retroazione!
Tre code: !
Q
0– RR con q=8 milliseconds!
Q
1– RR con q=16 milliseconds!
Q
2– FCFS!
Scheduling!
Ogni nuovo job è ammesso alla coda Q
0servita con RR.
Quando attivo, il processo ha 8 milliseconds per completare.
Se non completa passa alla coda Q
1.!
In Q
1i job sono schedulati con criterio RR con q=16. Se tale quanto non risulta sufficiente, il processo passa in Q
2.!
In Q
2schedulazione secondo FCFS!
Code multilivello con retroazione! Esempi: Unix classico!
Code Multilivello con retroazione!
Priorità ricalcolate ad ogni intervallo!
I i = [t i , t i+1 ] (es. ogni secondo)!
!T i : uso CPU nell’ultimo intervallo I i ! Stima l’uso medio della CPU come!
!T = (T+ T i )/2!
Calcola la priorità (base definisce le classi di processi)!
!P(i) = base + T + nice!
Processi che usano molta CPU vengono penalizzati!
P(i) piccolo -> priorità alta!
5.33!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!Base = 60 T = (T + T
i)/2 P = base + T!
5.34!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60!
Base = 60 T = (T + T
i)/2 P = base + T!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
!
!
Base = 60 T = (T + T
i)/2 P = base + T!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60
!
0!
Base = 60 T = (T + T
i)/2 P = base + T!
5.37!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60 105 45!
0!
60 0 !
P
2! Base = 60 T = (T + T
i)/2 P = base + T!
5.38!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60 105 45!
0!
60 0 !
P
2!
3.0! 0
!
60! 0
!
Base = 60 T = (T + T
i)/2 P = base + T!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60 105 45!
0!
60 0 !
P
2!
3.0! 0 82 22!
60 90 30!
0 60 0!
P
3! Base = 60 T = (T + T
i)/2 P = base + T!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60 105 45!
0!
60 0 !
P
2!
3.0! 0 82 22!
60 90 30!
0 60 0!
P
3!
3.1! 82 22! 90 30! 60 6! P
1!
Base = 60 T = (T + T
i)/2 P = base + T!
5.41!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60 105 45!
0!
60 0 !
P
2!
3.0! 0 82 22!
60 90 30!
0 60 0!
P
3!
3.1! 82 22! 90 30! 60 6! P
1!
4.0! 54
!
30! 6!
Base = 60 T = (T + T
i)/2 P = base + T!
5.42!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60 105 45!
0!
60 0 !
P
2!
3.0! 0 82 22!
60 90 30!
0 60 0!
P
3!
3.1! 82 22! 90 30! 60 6! P
1!
4.0! 54 98 38!
0 75 15!
0 63 3!
P
3! Base = 60 T = (T + T
i)/2 P = base + T!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60 105 45!
0!
60 0 !
P
2!
3.0! 0 82 22!
60 90 30!
0 60 0!
P
3!
3.1! 82 22! 90 30! 60 6! P
1!
4.0! 54 98 38!
0 75 15!
0 63 3!
P
3! Base = 60 T = (T + T
i)/2 P = base + T!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60 90 30!
P
1!
2.0! 60 105 45!
0!
60 0 !
P
2!
3.0! 0 82 22!
60 90 30!
0 60 0!
P
3!
3.1! 82 22! 90 30! 60 6! P
1!
4.0! 54 98 38!
0 75 15!
6 63 3!
P
3!
Base = 60 T = (T + T
i)/2 P = base + T!
5.45!
! !Process! Arrival Time Burst Time Distribution!
! !P
1!0 ! 4 s = 240 tick!
! ! P
2 !1.5 ! 2 s = 120 tick!
! ! P
3!2.7 ! (0.1 CPU – 0.8s I/O)-cycle!
! ! P
4!4.5 ! 2 s = 240 tick !
Tempo! P
1P T!
P
2P T!
P
3P T!
P
4P T!
Processo Schedulato!
0.0! 60 0! P
1!1.0! 60
90 30!
P
1! 2.0! 60
105 45!
0!
60 0 !
P
2! 3.0! 0
82 22!
60
90 30!
0
60 0!
P
3! 3.1! 82 22! 90 30! 60 6! P
1! 4.0! 54
98 38!
0
75 15!
0
63 3!
P
3! 4.1! 98 38! 75 15! 63 9! P
2! 5.0! 0
79 19!
54
94 34!
0
64 4!
0
60 0!
P
4! Base = 60 T = (T + T
i)/2 P = base + T!
5.46!
Esempi: Linux!
Code Multilivello!
Processi con più alta priorità hanno quanto di tempo maggiore!
Priorità 0-99 (real time proc) 100-139 (normal proc’s) !
Es: Quantum = (140-Priority)x20 (o x5 se Priority >119)!
Priorità ricalcolate quando il proc passa da Attivi ad Expired!
Attivi!
priorità! Lista dei task!
0!
1!
139!
140!
priorità! Lista dei task!
0!
1!
139!
140!
Expired!
99! 99!
Sistemi Multi-Processore!
!
CPU scheduling deve bilanciare il carico e le condivisioni tra i vari processori!
!
Multiprogrammazione asimmetrica: un solo processore accede alle strutture dati di sistema e gestisce la suddivisione per tutti!
Multiprogrammazione Simmetrica: ogni processore fa scheduling autonomamente; !
Multiple-Processor Scheduling!
Multiprocessing Simmetrico: ogni processore schedula autonomamente;!
Alternative: !
Coda comune!
Code separate!
Affinità di processo: meglio evitare che un processo passi da un processore all’altro!
Affinità forte: no switching !
Affinità debole: no switching preferito ma non garantito!
Bilanciamento del carico (in contrasto con l’affinità di processo) !
Migrazione guidata (push) - un processo speciale ribilancia!
Migrazione spontanea (pull) – se una coda si svuota, il
! !processore sposta processi da una coda piena !
5.49!
Multicore Processors!
!
Processori multipli sullo stesso chip!
Ogni core ha il suo insieme di registri!
Risparmio energetico e più veloce!
!!
Multi-threading!
I Core possono schedulare diversi processi/thread!
Multi-Thread gestito in hardware!
Quad core, dual thread = (virtualmente) 8 processori!
