1

1

6 CPU Scheduling

• La gestione della CPU (soltanto) può rendere la multi-programmazione più efficiente della mono-programmazione

• Infatti, la multiprogrammazione permette di ottenere l’utilizzazione massima della CPU

• Vedremo:– concetti base, criteri e algoritmi di scheduling, e

valutazione degli algoritmi

2

6.1 Concetti Fondamentali dello Scheduling della CPU

• Ciclo CPU–I/O Burst: l’esecuzione deiprocessi consiste di un ciclo di esecuzione di CPU e attesa di I/O

3

6.1 Concetti Fondamentali• Durata dei CPU burst

2

4

6.1.2 CPU Scheduler

• Selezione tra i processi in memoria quale eseguire.

• Quando si applica scheduling della CPU? 1. Passaggio running ⇒ wait (chi è il prossimo?)2. Passaggio running ⇒ ready (gli si porta via la

CPU, un altro diventa running)3. Passaggio waiting ⇒ ready (gli si può dare la

CPU?)4. Passaggio running ⇒ terminated (chi è il

prossimo?)

5

6.1.2 CPU Scheduler• In 2 e 4 si è obbligati ad intervenire, in 1 e 3

si può anche non intervenire:– in 1 non si fa nulla e non si porta via,– in 3 si lascia ready

• Preemptive scheduling =:= si fa schedulingin 1, 2, 3 e 4

• Non-preemptive scheduling =:= solo 1 e 4, mai 2 e 3– il processo running deve rilasciarla

volontariamente. Sicuri?

6

6.1.2 CPU Scheduler

• Preemptive Scheduling– superiore perché non si fida del processo– più equo nel controllare l'accesso alle risorse– più difficile da realizzare perché il processo può

essere nel kernel e non deve lasciarlo in stati illegali

– rendere non preemtabile (quasi) tutto il kernel(Unix) non va bene per real-time e multiprocessori

3

7

6.1.4 Dispatcher

• =:= modulo che effettua la commutazione di contesto; esegue– context switching– passaggio a user mode– salto alla corretta locazione del programma da

far ripartire• Dispatch latency =:= tempo impiegato per

effettuare la commutazione

8

6.2 Criteri di ottimizzazione dello Scheduling

1. Utilizzo della CPU2. Throughput =:= numero di processi

completati in media (nell’unità di tempo) - misura di lungo termine!

3. Turnaround time =:= tempo (medio) di completamento di un job, dalla sottomissione all’emissione dei risultati

4. Tempo di attesa =:= somma del tempo passato in RQ

9

6.2 Criteri di ottimizzazione dello Scheduling

5. Tempo di risposta =:= tempo che intercorre da quando si verifica l’evento che permette ad un processo di eseguire a quando il processo comincia ad eseguire

• Massimizzare 1 e 2, minimizzare 3, 4 e 5• Valori medi; minimizzare la varianza anche

a detrimento del valore medio

4

10

6.3 Algoritmi di Scheduling6.3.1 First Come First Served (FCFS)

• Implementazione semplice, con coda FIFO:– linkando il PCB alla fine della coda, per

inserire in RQ– assegnare la CPU al primo, quando la CPU

diventa libera• È una politica (algoritmo) non pre-emptive• Il tempo di attesa del completamento del

CPU burst è spesso lungo.

11

6.3.1 FCFS

• Supponiamo tre processi che arrivano assieme a t=0

• Process Burst TimeP1 24P2 3P3 3

• Suppose that the processes arrive in the order: P1 , P2 , P3

12

6.3.1 FCFS

• Il diagramma di Gantt per questa sequenza è:

• Waiting time per P1 = 0; P2 = 24; P3 = 27• Average waiting time: (0 + 24 + 27)/3 = 17

P1 P2 P3

24 27 300

5

13

6.3.1 FCFS

Se l’ordine di arrivo fosse P2 , P3 , P1 .• Il diagramma di Gantt per questa sequenza è:

• Waiting time per P1 = 6; P2 = 0; P3 = 3• Average waiting time: (6 + 0 + 3)/3 = 3• Molto meglio del caso precedente

P1P3P2

63 300

14

6.3.1 FCFS

• Caratteristiche:– il tempo di attesa è basato sui job CPU bound– la utilizzazione della CPU può essere bassa (se

non sono tutti CPU bound)– produce una bassa utilizzazione dei dispositivi

di I/O– Va malissimo per i sistemi time-sharing perché

non garantisce affatto interattività– Va ancora peggio per i sistemi real-time, perché

non è pre-emptive

15

6.3.1 FCFS

• Cattivo comportamento dinamico– Ad es. se si hanno 1 processo CPU bound e 2

processi I/O bound si forma un "convoglio":– CPUA, I/OB, I/OC, idle (perché il CPUA non

ha ancora terminato I/O); mentre CPUA esegue, anche l’I/O è idle!; e così via

• È adatta solo per un mix di job CPU bound

6

16

6.3.2 Shortest Job First (SJF)

• Si esamina la durata del prossimo burst di CPU di ciascun processo e si assegna la CPU a chi ha il prossimo burst di durata minima

• Si dovrebbe chiamare Shortest Next CPU Burst.

• Può essere usato in modo pre-emptiveoppure non pre-emptive

17

Process Arrival Time Burst TimeP1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4

• SJF (non-preemptive)

• Average waiting time = (0 + 6 + 3 + 7)/4 = 4

Esempio di SJF Non-Preemptive

P1 P3 P2

73 160

P4

8 12

18

Esempio di SJF PreemptiveProcess Arrival Time Burst Time

P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4

• SJF (preemptive)

• Average waiting time = (9 + 1 + 0 +2)/4 = 3

P1 P3P2

42 110

P4

5 7

P2 P1

16

7

19

6.3.2 SJF

• Si dimostra che SJF è ottimo: spostando uno breve prima di uno lungo si migliora l’attesa del breve più di quanto si peggiori l’attesa del lungo

⇒ il tempo medio diminuisce!• Ottimo: nessun algoritmo può produrre un

tempo medio minore

20

Come si applica SJF?• È facile essere ottimi quando si conosce il futuro• La durata del prossimo burst di CPU non è

calcolabile• Nel caso di Long Term Scheduling (sistemi batch,

coda dei job sottomessi ma non ancora caricati) si usa il tempo limite dichiarato dall’utente nelle job control card

⇒ l’utente deve stimare "giusto" perché il job viene terminato di forza se il tempo scade

21

Come si applica SJF?

• Nel caso di CPU scheduling si può solo approssimare (stimare) il prossimo CPU burst

• Una stima: Media esponenziale dei precedenti burst– ricordare tutti i burst precedenti– pesare poco i burst "vecchi"– pesare molto i burst "recenti"

8

22

Come si applica SJF?• Sia τn i vari burst passati e τn+1 la predizione del

valore del prossimo, e 0≤α≤1; alloraτn+1 = α tn + (1- α) τn

• dove tn contiene la info più recente, mentre τncontiene il passato e α determina il peso relativo

• Espandendo si vede meglio come il passato pesa sempre meno più è "vecchio"

τn+1 = αtn + (1-α)αtn-1 +...+ (1-α)jαtn-j +...+ (1-α)n+1τ0 = αtn + (1-α)τn

23

Come si applica SJF?

• Se α=0 → τn+1 = τn : conta solo la storia passata e quindi solo τ0, cioè la stima iniziale (a caso? costante per tutti?)

• Se α=1 → τn+1 = tn : conta solo l’ultimo burst

• In genere α = 1/2.

24

Come si applica SJF ?

• Pre-emptive: se arriva un processo in RQ con next CPU burst più breve di quanto rimane al processo che sta girando, si da subito la CPU al nuovo arrivato

• quello pre-emptive è detto anche Shortest Remaining Time First (SRTF)

• può produrre tempo medio minore del non pre-emptive

9

25

6.3.3 Scheduling a Priorità

• Un valore di priorità è associato ad ogni processo• La CPU è allocata al processo con la priorità più

elevata• Certi sistemi codificano priorità alta con valori

piccoli, altri con valori alti. Noi assumiamo priorità alta con valori piccoli

• SJF è uno scheduling a priorità; τ e la priorità

26

6.3.3 Scheduling a Priorità• FCFS va bene per quelli a uguale priorità• Tipi di priorità:

– interne: calcolate dal SO sulla base di quantità caratteristiche del comportamento del processo

– esterne: assegnate dall’esterno del SO

• Può essere sia pre-emptive che non pre-emptive• Ha il problema della starvation.

– Una soluzione è basata sull’invecchiamento (aging): incrementare gradualmente la priorità del processo in RQ.

27

6.3.4 Round Robin Scheduling (RR)

• =:= FCFS + pre-emption ogni quanto di tempo– il processo pre-empted va in fondo alla RQ,

come se fosse appena arrivato• È particolarmente adatto per Time Sharing• La RQ è vista come una coda circolare →

girotondo

10

28

6.3.4 RR

• Implementazione:– scheduler sceglie il primo in coda– lancia un timer = quanto di tempo– passa la CPU al processo scelto (dispatch)

• Se il processo ha un CPU burst minore del quanto di tempo, rilascia la CPU volontariamente

29

6.3.4 RR

• Se il burst è maggiore del quanto di tempo, allora– interrupt di timer– SO prende il controllo– toglie la CPU al processo running e lo mette in

fondo alla RQ– prende il primo processo in RQ e ...– gli passa la CPU

30

RR with Time Quantum = 20Process Burst Time

P1 53P2 17P3 68P4 24

• Il diagramma di Gantt:

Tipicamente, si ha turnaround mediomaggiore di SJF, ma migliore risposta.

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

11

31

6.3.4 RR• Il tempo medio di attesa può non essere buono• n processi: quanto di q msec:

– ogni proc riceve 1/n di CPU in pezzi di q msec– ogni proc attende al più (n-1)q msec per avere il prossimo

quanto di q msec

• Il comportamento dipende molto dal valore del quanto– q tendente a ∞ → uguale a FCFS– q tendente a zero viene chiamato processor sharing: ogni

processo ha il suo processore di velocità 1/n. – Es. CDC: 10 set di registri, una istruzione per ogni set in

RR. Con la memoria lenta, ogni processore è circa veloce uguale

32

6.3.4 RR• Overhead del context switch:

– Quanto >> tempo del context switch– Es. Se quanto=10*tempo di context switch →

10% della CPU è sprecato

33

6.3.4 RR

• Tempo di turnarounddipende dal quanto

12

34

6.3.4 RR

• Non migliora se si aumenta il quanto, anche se può essere migliorato quando la maggior parte dei processi ha un burst minore del quanto

• Se il quanto è troppo grande diventa un FCFS, e non va bene per il time sharing

• Regola pratica: 80% dei CPU burstdovrebbe essere minore del quanto

35

6.3.5 Scheduling a Code Multiple (MQS)

• Quando i processi sono facilmente divisibili in classi differenti; Es.:– foreground (interattivi)– background (batch)

• Partizionare la RQ:– in molteplici code– inserire i processi in una delle code, sulla base

delle proprietà del processo– gestire ogni coda con lo scheduling appropriato

per le proprietà della classe dei processi

36

6.3.5 Scheduling a Code Multiple (MQS)

– assegnare la CPU alle code:• con uno scheduling a priorità, in genere fissa• oppure a quanti di tempo fa le code (non uguali)

• Pre-emption fra le code!

13

37

6.3.6 Scheduling a Code Multilivellocon FeedBack (retroazione) (MFQS)

• In MQS un processo è assegnato permanentemente a una coda

• in MFQS un processo può essere spostato nelle code per:– adattarsi alla lunghezza del CPU burst del

processo– gestire ogni coda con lo scheduling adatto al

processo con quel burst

38

6.3.6 Scheduling a Code Multilivellocon FeedBack (retroazione) (MFQS)

• Nell’esempio della figura:– RR nella prima e seconda coda, ma se un

processo non finisce nel suo quanto, viene passato alla coda successiva;

– la terza coda viene gestita in FCFS• Pre-emption fra le code

39

MFQS in generale• È uno scheduling definito dai seguenti parametri:

– numero delle code– scheduling di ogni coda– quando declassare un processo– quando promuovere un processo– in che coda inserire un processo quando arriva

(dall’esterno oppure da un I/O burst)• È l’algoritmo (famiglia di algoritmi) più generale• È l'algoritmo più complesso

14

40

6.4 Scheduling di Multiprocessori• Ancora più complesso, e tanto meno con

soluzione ottima• Occorre distinguere il caso di multiprocessori

omogenei da quello dei multiprocessorieterogenei

• Nel caso di multiprocessori omogenei si può puntare a realizzare load sharing, con una RQ comune:– ogni processore è self-scheduling, prelevando da

RQ il nuovo processo

41

6.4 Scheduling di Multiprocessori

• Problemi:→ difficile la programmazione dell’accesso a RQ

(non devono prendere lo stesso processo, ad es.!)– un processore può fare girare lo scheduler, a cui

si rivolgono tutti gli altri processori quando devono fare dispatch

→ architettura master-slave

42

6.5 Hard Real Time Scheduling

• Hard Real Time: quando un job viene sottomesso (diventa ready o viene creato) chiede di essere messo in grado di terminare o fare I/O entro un certo tempo dal momento in cui diventa ready

• Il SO lo accetta solo se può impegnarsi, altrimenti lo rifiuta

• Se viene rifiutato occorre cambiare la configurazione del sistema!

15

43

6.5 Hard Real Time Scheduling

• Se viene accettato, gli vengono riservate tutte le risorse necessarie: memoria e quota di CPU

→ prenotazione delle risorse• Scheduling a priorità fisse oppure a Shortest

Deadline First– Il SO deve conoscere quanto tempo impiega al

max a svolgere le sue funzioni. Impossibile quando si usa memoria secondaria o memoria virtuale (vedremo)

44

6.5 Hard Real Time Scheduling

– Sistemi per real time hard sono basati su hardware specializzato, senza memoria secondaria, e il software è specializzato per applicazioni critiche in tempo

• Applicazioni– militari– controllo di processi industriali– apparati telecom

• Importanza crescente

45

6.5 Soft Real Time Scheduling

• Comunque per processi critici in tempo, che devono avere priorità più alta– allocazione delle risorse non equa– ritardi più grandi– starvation

• Applicazioni– multimedia– grafica interattiva

16

46

6.5 Soft Real Time Scheduling

• Scheduler e Dispatcher da progettare con cura– niente aging sui processi real-time– latenza di dispatching più bassa possibile– fare subito pre-emption, anche se si è nel

kernel.• Occorrono soluzioni sofisticate

47

6.5 Soft Real Time Scheduling• Syscall pre-emptabili

– introdurre numerosi punti di pre-emption (es. modifiche del kernel dello Unix)

– fare pre-emption nel kernel, però:• proteggere le sezioni critiche (vedi Cap. 6)• pre-emptare anche le sezioni critiche, sperando che

non servano al processo nuovo

– inversione della priorità: un processo a priorità bassa eredita la priorità del processo ad alta che deve entrare nella sezione critica occupata da li (solo per il tempo di uscire dalla sezione critica)

48

6.5 Soft Real Time Scheduling

• Fase di conflitto costituita da• 1. Pre-emption dei processi nel kernel (caso

multiprocessore)• 2. I processi a bassa priorità rilasciano le

risorse necessarie all’entrante• 3. I processi a bassa priorità abbandonano la

CPU• 4. Segue il dispatching normale

17

49

6.5 Soft Real Time Scheduling

• I conflitti possono sorgere anche dopo che il processo entrante ha avuto la CPU, e occorre inversione di priorità

• Caso Solaris 2.x: 100msec senza pre-emption, 2msec con pre-emption

50

6.5 Soft Real Time Scheduling

51

6.6 Valutazione degli Algoritmi

• Quale è quello giusto?• Primo problema: definire i criteri da

ottimizzare• Come valutare:

– Modellazione deterministica– Modelli a reti di code– Simulazione– Implementazione

18

52

6.6.1 Modellazione deterministica

• Appartiene alla classe delle valutazioni analitiche: usare l’algoritmo + carico del sistema per produrre:– formula, oppure– numero

che esprimano la prestazione dell’algoritmo• È un procedimento deterministico: si

calcola il comportamento con un carico di lavoro preciso

53

6.6.1 Modellazione deterministica

• Vantaggi:– semplice, produce numeri esatti, permette

confronti• Svantaggi:

– troppo specifico e legato al carico usato come esempio

– troppa informazione necessaria per descrivere un carico di lavoro reale

54

6.6.2 Modelli a Reti di Code

• Descrizione probabilistica dei burst di CPU e I/O:– misura delle distribuzioni, approssimazione o

stima con una formula matematica• Tipicamente sono distribuzioni

esponenziali, caratterizzate dal valore mediano.

• Analogo procedimento per i tempi di arrivo dei processi

19

55

6.6.2 Modelli a Reti di Code• Dalle due distribuzioni si può calcolare il valore

medio di throughput, tempo di attesa, ecc.• Il problema è descritto da una rete di servitori

con coda di processi in attesa (CPU, dispositivi di I/O)

• Dai tassi di arrivo e dai tassi di servizio si calcola:– utilizzazione, lunghezza media delle code, attesa

media, tasso di arrivo al server successivo nella rete

56

6.6.2 Modelli a Reti di Code

• Sia n la lunghezza media della coda, W il tempo di attesa medio, λ il tasso di arrivo medio; se il sistema è stabile, nel tempo che un processo lascia la coda (W) la coda si è riformata, quindi

n = λ * Wdetta anche Formula di Little

• Notare bene: vale per ogni tipo di scheduling

57

6.6.2 Modelli a Reti di Code

• Vantaggi:– descrive caratteristiche generali dell’algoritmo– permette confronti fra algoritmi

• Svantaggi:– pochi algoritmi e distribuzioni possono essere

trattati matematicamente– le distribuzioni di arrivi e di servizio usate (che

si sanno trattare) sono spesso non reali– i risultati sono approssimati e quindi discutibili

20

58

6.6.3 Simulazione• =:= programmare un modello del sistema• Contiene una simulazione del tempo, fa

evolvere lo stato del sistema, raccoglie statistiche delle varie code e uso dei componenti

• Problema: i dati per guidare il modello– generatore di numeri casuali con distribuzioni

definite matematicamente– generatore di numeri casuali con distribuzione

misurate empiricamente

59

6.6.3 Simulazione

• Le distribuzioni degli eventi non descrivono le eventuali relazioni temporali fra gli eventi

• La simulazione guidata da distribuzionepuò essere inaccurata

• Nastri di Traccia: monitor di un sistema e raccolta degli istanti in cui avvengono gli eventi → il trace tape fornisce input alla simulazione

60

6.6.3 Simulazione

• Svantaggi della simulazione:– ore di tempo di calcolo– la precisione dipende dal tempo di calcolo– i trace tape occupano una grande quantità di

spazio– lo sviluppo del simulatore è molto costoso

21

61

6.6.4 Implementazione

• L’unico modo con precisione assoluta è implementare l’algoritmo di scheduling, provarlo in un SO con carico di lavoro reale e misurare le prestazioni

⇒ solo svantaggio è il costo!– codifica– modifica del SO– reazioni degli utenti in un ambiente sperimentale– misure

62

6.6.4 Implementazione

• Il carico di lavoro cambia nel tempo, anche per effetto dello scheduling: gli utenti tentano di usarlo a loro vantaggio "imbrogliando".

• Ad es. aggiramento di un MFQS facendo I/O "fasulli"