1

Introduzione al CPU scheduling• Multiprogrammazione:– mantenere più processi in esecuzione– commutare l'esecuzione ad un altro processo in

caso di blocco per I/O– impiegare tempi di attesa in modo produttivo

2

Ciclicità fasi di elaborazione - I/O• L'esecuzione di un processo si alterna in un

ciclo costituito da:– fase di elaborazione (CPU burst)– attesa completamento I/O (I/O burst)

• Tale ciclo prosegue fino alla fine della esecuzione del programma

3

Ciclicità fasi di elaborazione – I/O• Processo CPU-bound:– produce poche sequenze di operazioni di CPU

molto lunghe– produce relativamente poco I/O

• Processo I/O-bound:– produce tante sequenze di operazioni di CPU

molto breve– produce prevalentemente operazioni di I/O

4

Scheduler della CPU• Quando la CPU passa nello stato di inattività, il

SO sceglie un processo dalla coda di pronto per l'esecuzione

• Scheduler della CPU:– gestisce la coda di pronto– seleziona il prossimo processo da mandare in

esecuzione

5

Scheduler della CPU• Coda dei processi pronti:– non è necessariamente una coda FIFO– può essere implementata come:

♦una coda FIFO♦una coda con priorità♦un albero♦una lista concatenata non ordinata

• elementi della coda dei processi pronti sono i process control block

6

Il diritto di prelazione• Lo scheduling della CPU può essere attivato

nelle seguenti circostanze:1.un processo passa dallo stato di esecuzione

allo stato di attesa (richiesta I/O)2.un processo passa dallo stato di esecuzione

allo stato di pronto (interruzione, quanto)3.un processo passa dallo stato di attesa allo

stato di pronto (completamento I/O)4.un processo termina l'esecuzione

7

Il diritto di prelazione• 1. e 4. non richiedono una vera e propria scelta

di scheduling (prossimo processo)• 2. e 3. richiedono una scelta di scheduling

(prossimo processo)• Schemi di scheduling:– con diritto di prelazione (preemptive): lo

scheduling interviene in 1., 2., 3., 4.– senza diritto di prelazione (non preemptive): lo

scheduling interviene in 1., 4.

8

Il diritto di prelazione• Scheduling senza diritto di prelazione– il processo rimane in possesso della CPU fino a

quando non la rilascia♦termine esecuzione♦passaggio nello stato di attesa (I/O)

– non esiste il concetto di quanto di tempo♦ implementazione più semplice♦funziona su architetture sprovviste di timer

9

Il diritto di prelazione• Scheduling con diritto di prelazione– concetto di quanto di tempo– singolo processo non monopolizza la CPU

• Problemi– gestione in mutua esclusione dei dati condivisi

fra due o più processi– se un processo in kernel mode viene interrotto

a metà di una operazione critica (aggiornamento di code di scheduling), il kernel rimane in uno stato inconsistente

– una interruzione interrompe un processo in kernel mode; strutture dati in comune vanno accedute in mutua esclusione

10

Il diritto di prelazione• Scheduling con diritto di prelazione– concetto di quanto di tempo– singolo processo non monopolizza la CPU

• Soluzioni– Nei SO UNIX, il context switch avviene al

termine di una chiamata di sistema♦soluzione semplice♦non scala su più unità di elaborazione

– versioni recenti di Linux (v2.6) introducono i preemption point

♦API per rilasciare volontariamente la CPU♦ il programmatore decide il rilascio

11

Dispatcher• Il componente del CPU scheduler che sceglie il

prossimo processo da mandare in esecuzione• Esegue le seguenti azioni:– context switch– passaggio al modo utente– salto alla locazione della prossima istruzione da

eseguire

• Il dispatcher viene invocato ad ogni context switch– deve essere rapido

12

Algoritmi di scheduling• First Come, First Served (FCFS)• Shortest Job First (SJF)• Priority• Round Robin (RR)• Multilevel Queue (MQ)• Multilevel Feedback Queue (MFQ)

13

First Come, First Served• Si assegna la CPU al processo che l'ha chiesta

per prima• Implementato tramite una coda FIFO• Quando un processo entra nella coda dei

processi pronti:– PCB inserito in fondo alla coda dei processi

pronti

• Quando la CPU torna libera:– estrae dalla coda dei processi pronti il PCB in

cima alla coda e ripristina l'esecuzione del processo corrispondente

14

First Come, First Served

Processo DurataProcesso

P1 24msec

P2 3msec

P3 3msec

P1

P2

P3

24 27 300

P2

P3

P1

0 3 6 30

15

First Come, First Served

• Tatt

(P1,P

2,P

3)=(0+24+27)/3=17msec

• Tatt

(P2,P

3,P

1)=(6+0+3)/3=3msec

• Il tempo di attesa di FCFS non è, in genere, minimo

• Effetto convoglio: se un processo CPU-bound va in esecuzione per primo, gli altri processi devono attendere il rilascio della CPU– riduzione utilizzo CPU– riduzione utilizzo periferiche– invertendo l'ordine di esecuzione migliorerei gli

utilizzi

16

First Come, First Served• Assenza di prelazione: CPU trattenuta fino al

rilascio della CPU– termine esecuzione– richiesta di I/O

• FCFS è problematico nei sistemi time shared– quanto di tempo stride con assenza di

prelazione

17

Shortest Job First• Si associa ad ogni processo la lunghezza della

successiva sequenza di operazioni di CPU• Si assegna la CPU al processo con la

lunghezza più breve• Se due processi hanno sequenze uguali, si

applica il criterio FCFS• Nome più corretto: shortest CPU burst first

18

Shortest Job First• Il tempo di attesa medio per n processi in coda

si può scrivere come:(1) T

att=(T

1+T

2+...+T

n)/n

dove(2) T

j=T

j-1+t

j

essendo:♦T

j-1=tempo attesa job j-1

♦tj=tempo esecuzione job j

19

Shortest Job First• Sostituendo (2) in (1) si ottiene:

(3) Tatt

=((n-1)t1+(n-2)t

2+...+(n-k)t

k+...+t

n-1)/n

• Prendiamo due processi di indici k e k-j (separati di j posizioni): P

k e P

k-j

– k>0, j>0, k-j>0– Il processo che viene prima ha tempo di

esecuzione più grande: tk-j

> tk

• Scambiamo di posto questi due processi (S1)• Calcoliamo il nuovo tempo di attesa medio:

(4) Tatt,S1

=((n-1)t1+...+(n-k+j)t

k+...+(n-k)t

k-j+...+t

n-1)/n

20

Shortest Job First• Calcoliamo la differenza (3)-(4): si elidono tutti i

termini tranne quelli relativi a tk-j

e tk

Tatt

-Tatt,S1

=((n-k+j)tk-j

+(n-k)tk-(n-k+j)t

k-(n-k)t

k-j)/n

Tatt

-Tatt,S1

=j(tk-j

-tk)/n > 0

• Spostando dopo un processo con tempo di esecuzione più grande, si ottiene una riduzione del tempo di attesa

• Reiteriamo S1,S2,...,Sm scambi fino a quando i processi sono ordinati dal più breve al più lungo

– si ottiene sempre un Tatt,Sj

descrescente

– Dopo m scambi, si ottiene l'ordinamento SJF

21

Shortest Job First

Processo DurataProcesso

P1 6msec

P2 8msec

P3 7msec

0

P4 3msec

P4

3

P1

9

P3

16

P2

24

22

Shortest Job First

• Tatt

(P4,P

1,P

3,P

2)=(3+16+9+0/4=7msec

• Tatt

è ottimale

• spostando un processo breve prima di un processo lungo:– il tempo di attesa per il processo breve

diminuisce più di quanto aumenti il tempo di attesa per il processo lungo

– di conseguenza, Tatt

medio diminuisce

• Problema: SJF richiede la durata della successiva richiesta di CPU – non sempre si conosce esattamente, si deve

spesso stimarla

23

Shortest Job First• La lunghezza del CPU burst si stima con la sua

media esponenziale:te

n+1=at

n+(1-a)te

n , a in [0,1]

• a=0: valore recente non ha effetto• a=1: assenza di storia• a=1/2: stesso peso per valore recente e storia

passata (scelta comune)• SJF può essere con e senza prelazione

24

Shortest Job First• Se arriva un processo con CPU burst

successivo più breve rispetto a ciò che resta al processo attualmente in esecuzione:– prelazione: il processo in esecuzione viene

sostituito col nuovo processo– assenza di prelazione: il processo in

esecuzione termina il suo CPU burst

• SJF con prelazione viene chiamato shortest remaining time first

25

Priority• Si associa ad ogni processo una priorità• Si assegna la CPU al processo con priorità più

alta• Se due processi hanno uguale priorità, si

applica il criterio FCFS• SJF è un algoritmo di priorità– la priorità è l'inverso della lunghezza (prevista)

del prossimo CPU burst

26

Priority

Processo DurataProcesso

P1 10msec

P2 1msec

P3 2msec

0

P4 1msec

P2

1

P5

6

P1

16

P3

18

P5 5msec

Priorità

3

1

4

5

2

P4

19

27

Priority

• Tatt

(P2,P

5,P

1,P

3,P

4)=8.2msec

• Le priorità possono essere definite:– internamente: in base a grandezze misurabili

(limiti di tempo, memoria, lunghezza CPU burst)– esternamente: in base a criteri esterni al SO

(importanza del processo)

• Priority scheduling può essere con o senza prelazione

28

Priority• Se arriva un processo con priorità maggiore

rispetto a quella del processo attualmente in esecuzione:– prelazione: il processo in esecuzione viene

sostituito col nuovo processo– assenza di prelazione: il processo in

esecuzione termina il suo CPU burst

• Problema: starvation (attesa indefinita di processi a bassa priorità)

• Soluzione: aging (aumento graduale della priorità)

29

Round Robin• Progettato per sistemi time sharing• FCFS con capacità di prelazione per

commutare fra processi• Ciascun processo riceve una quantità fissa di

tempo di CPU, il quanto di tempo– esecuzione viene interrotta allo scadere del

quanto di tempo– quanto di tempo varia da 10msec a 100msec

• La coda dei processi pronti viene gestita in modalità circolare

• Implementazione tramite coda FIFO– nuovi processi aggiunti in coda– processi appena eseguiti sono riaccodati

30

Round Robin

Processo DurataProcesso

P1 24msec

P2 3msec

P3 3msec

0

P1

4 7 10

P2

P3

P1

14

P1

18

P1

22

P1

26

P1

30

Quanto=4msec

31

Round Robin

• Tatt

(P1,P

2,P

3)=17/3=5.66msec

• RR è sempre con prelazione (per via del quanto di tempo)

• Se ho n processi, quanto di tempo pari a q:– ciascun processo ottiene 1/n del tempo di

elaborazione di CPU in frazioni di al più q unità di tempo

– l'attesa di esecuzione è limitata a (n-1)*q unità di tempo

32

Round Robin• Le prestazioni dell'algoritmo RR dipendono

fortemente dalla dimensione del quanto di tempo

• quanto di tempo piccolo: – RR prende il nome di CPU sharing– overhead del context switching

• quanto di tempo ampio: – RR tende a diventare FCFS

33

Multilevel queue• Distinzione fra più classi di processi– processi interattivi (foreground)– processi in sfondo (background)– processi batch

• Classi di processi hanno requisiti diversi sui tempi di risposta

• Si suddivide la coda dei processi pronti in più code distinte

• Ciascun processo viene associato permanentemente ad una coda

• Ciascuna coda ha il proprio algoritmo di scheduling (RR, FCFS)

34

Multilevel queue• Necessità di uno scheduling fra code: quali

sono le code con priorità più alta di esecuzione?– priorità fissa, con prelazione

• Esempio:1.processi di sistema2.processi interattivi3.processi interattivi di editing4.processi in background5.processi degli studenti

35

Multilevel queue• Ogni coda ha priorità assoluta sulle code di

priorità più bassa• Se un processo a priorità più alta viene

iniziato, si interrompe un eventuale processo in esecuzione a priorità più bassa (Solaris2)

36

Multilevel feedback queue• Variante di multilevel queue• I processi possono spostarsi fra le varie code– cambio di priorità

• Idea: raggruppare i processi con caratteristiche di CPU burst simili nelle stesse code

• Tipicamente:– CPU burst lunghi, priorità bassa– CPU burst brevi, priorità alta

37

Multilevel feedback queue

quanto = 8

quanto = 16

FCFS

38

Multilevel feedback queue• Parametri di MFQ:– numero di code– algoritmo di scheduling per ciascuna coda– criterio usato per spostare un processo in una

coda con priorità maggiore– criterio usato per spostare un processo in una

coda con priorità minore– criterio usato per scegliere la coda in cui

inserire inizialmente un processo

39

Scheduling nei sistemi SMP• Finora sono stati analizzati sistemi basati su

un solo processore• Con più processori, diviene possibile la

condivisione del carico (load sharing) dei processi fra più processori

• Ci concentriamo su sistemi:– Symmetric Multi Processing (SMP): processori

uguali, ciascuno in grado di eseguire codice– Uniform Memory access (UMA): la probabilità di

accedere ad una qualunque locazione in memoria è la stessa per ogni processore

40

Scheduling nei sistemi SMP: tecniche• Due diversi approcci per implementare la coda

di pronto– Coda di pronto per ciascun processore– Una singola coda di pronto acceduta da tutti i

processori

• Processor Affinity– Lo scheduler tende a rischedulare gli stessi

processi sugli stessi processori, per aumentare la probabilità di trovare dati in cache

• Load Balancing– Lo scheduler bilancia l'esecuzione dei processi

in modo tale che la lunghezza delle code di pronto sia grossomodo la stessa sulle CPU

41

Scheduling dei thread• Se un SO è multithreaded, i thread devono

essere schedulati dallo scheduler del kernel• Process Contention Scope:– Scelta di schedulazione dei thread user level– Many-to-One, Many-to-Many– Basato sul concetto di priorità

• System Contention Scope:– Scelta di schedulazione dei thread kernel level– One-to-One (Linux)– Basato su Multilevel Feedback Queue

42

Valutazione algoritmi di scheduling• Come fare a scegliere un dato algoritmo di

CPU scheduling fra i tanti a disposizione?– Occorre valutarli– Ma come?

• Tre passi:– Occorre scegliere degli indici di valutazione

delle prestazioni di un algoritmo– Occorre scegliere degli indici statistici di

misurazione per gli indici di prestazione– Occorre costruire un modello di

rappresentazione dell'algoritmo

43

Indici di prestazione• Utilizzazione CPU– È una probabilità (valori in [0, 1])– È definita come la probabilità di trovare il

sistema occupato in un dato intervallo di osservazione

– In alternativa, è definita come il rapporto fra un intervallo di tempo in cui la CPU è usata (T

occ) ed

un intervallo di tempo di misura(Tmis

)

– 0: sistema completamente scarico– 1: sistema utilizzato al 100% (bene se non ci

sono ulteriori accodamenti)

=T occ

T mis

44

Indici di prestazione

=T occ

T mis

Tmis

To,j

Ti,k T occ=∑ T o , j

45

Indici di prestazione• Throughput– È definito come il numero di processi N

commutati in un intervallo di misura Tmis

– Vorremmo averlo più alto possibile

X=NT mis

46

Indici di prestazione• Tempo di risposta– È definito come l'intervallo temporale che passa fra

la sottomissione del processo e l'inizio della risposta

– Lo vorrei minimo per i processi interattivi

• Tempo di completamento– È definito come l'intervallo temporale che passa fra

la sottomissione del processo ed il suo completamento

– In generale, lo vorremmo più basso possibile

• Tempo di attesa:– È definito come la somma degli intervalli temporali

passati in coda di pronto

– In generale, lo vorremmo più basso possibile

47

Indici statistici• Media campionaria

– È definita come la media aritmetica di n campioni xi

di una grandezza

– In generale, la vorrei più bassa possibile

• Varianza campionaria– È definita come la media dello scarto quadratico fra

n campioni e la loro media campionaria

– Misura la dispersione dei valori attorno alla media

– Lo vorremmo basso per processi interattivi

x=1n∑i=1

n

x i

2=

1n−1∑i=1

n

xi−x 2

48

Modelli rappresentativi• I modelli rappresentativi possono essere i

seguenti– Modello analitico– Modello a reti di code– Modello simulativo– Sistema reale

49

Modello analitico• Si analizza l'algoritmo ed il carico a cui esso è

soggetto• Si cerca di scoprire una relazione in forma

chiusa (formula) che lega la prestazione di un dato algoritmo con il numero di processi

• In un sistema complesso, non sempre si riesce a stabilire la formula

• Nota una formula, la valutazione delle prestazioni è immediata

• Ad esempio, per SJF, il tempo di attesa su n processi è dimostrabilmente minimo:

T att=1n∑i=1

n

n−i t i

50

Modello a reti di code• Lo scheduler è visto come un oggetto servente

a cui è attaccato un oggetto coda di attesa• Una richiesta entra nello scheduler, si accoda

ed aspetta fino a quando non si libera il servente

• Le richieste arrivano con un ritmo aleatorio, con valor medio pari a λ richieste per unità di tempo

• Il servente serve richieste (processi) ad un ritmo aleatorio, con valor medio pari a μ richieste per unità di tempo

• Più componenti possono essere attaccati per formare una rete di code (queueing network)

51

Modello a reti di code

CPU

a

serventecoda

Una coda semplice

λ μ

Una rete di code

CPU DiskInput Output

52

Modello a reti di code• Legge di Little– Sia n il numero medio di elementi in coda– Sia λ il tasso medio di arrivo delle richieste– Sia W il tempo medio speso in coda– Sussiste la seguente relazione generale:

• Esempio:– Se arrivano in media λ=7 processi al secondo– Se la lunghezza media della coda è n=14

processi– Allora il tempo medio di permanenza in coda è

di W=2s

n=W

53

Modello a reti di code• Utilizzazione del servente– È definita come il rapporto fra λ e μ

• In generale, si ha:

=

λ

ρ

λ=μ

1