1

1

Lo scheduling

Un processo durante la sua evoluzione è o running o in attesa di un evento. Nel secondo caso l’evento atteso consiste nella disponibilità di una risorsa (CPU , I/O, struttura dati, ecc.) di cui il processo attende l’allocazione.

Se un processo è in attesa di un evento, il suo PCB è in una coda da cui sarà rimosso quando l’evento si verifica.

Queste code sono dette code di scheduling ed è dettoschedulatore o scheduler il segmento del S.O. che effettua la selezione del processo in coda a cui allocare la risorsa e algoritmo di scheduling l’algoritmo che esso implementa

2

Tipici schedulatori

• lo schedulatore a breve termine o scheduler della CPU

• lo schedulatore a medio termine o schedulatore di swap

(swapper)

• lo schedulatore a lungo termine o schedulatore di job

• lo schedulatore del disco, della stampante, ecc.

2

3

5

Obiettivi di un algoritmo di scheduling

Un algoritmo di scheduling persegue uno o più obiettivi quali:• imparzialità: ad es. garantire ad ogni processo la sua giusta

quota di tempo di CPU, e lo stesso trattamento• efficienza: ad es. tenere la CPU impegnata al 100% del

tempo• tempo di risposta: ad es. minimizzare il tempo di risposta

per gli utenti interattivi• turnaroud: minimizzare il tempo che gli utenti batch

devono attendere per ricevere i risultati dei propri job• throughput: massimizzare il numero di job elaborati per ora• tempo medio di attesa: minimizzare il tempo medio che un

processo deve attendere per accedere ad una risorsa

6

Il prerilascio

• Le decisioni dello scheduling di CPU hanno luogo quando unprocesso: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 prerilascio).

• Altrimenti si ha uno schema preemptive.

• Il rilascio forzato implica necessariamente che sia possibile salvare lo stato di avanzamento del processo sulla risorsa in modo da permettere successivamente la sua ripresa.

4

7

Il dispatcher

• Il modulo dispatcher dà 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.

8

Scheduling first come - first served (FCFS)

• tipico algoritmo di scheduling non preemptive

• ha il vantaggio della semplicità

• può dar luogo a tempi medi di attesa in coda molto lunghi.

• consente la gestione efficiente di una risorsa

• può essere indicato per lo scheduling di processi in attesa di risorse usualmente disponibili

• non può essere utilizzato come algoritmo di scheduling della CPU in sistemi time sharing

• nello scheduling della CPU può dar luogo all’effetto convoy.

5

9

Scheduling First–Come, First–Served (FCFS)

• Esempio: Processo Burst TimeP1 24P2 3P3 3

• Supponendo che i processi arrivino nel seguente ordine: P1, P2, P3 l lo schema di Gantt è il seguente:

• Tempi di attesa P1 = 0; P2 = 24; P3 = 27• Tempo di attesa medio: (0 + 24 + 27)/3 = 17

P1 P2 P3

24 27 300

10

Scheduling FCFS

Se l’ordine di arrivo è il seguente:P2, P3, P1.

• Lo schema di Gantt è il seguente:

• 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 poteva avere

un effetto convoglio: i processi piccoli attendono che un grande processo liberi la CPU

P1P3P2

63 300

6

11

Scheduling Roud Robin (RR)

Tipico algoritmo di scheduling della CPU per sistemi time_sharing

Nasce dalla trasformazione preemptive del FCFS mediante l’impiego di un timer

Le prestazioni dell’algoritmo sono dipendenti dalla durata del periodo del timer che definisce il quanto di tempo di massimo utilizzo della risorsa o time slice (valori tipici da 10 a 100 msec)

Aumentando il time slice tende a trasformarsi in FCFS, mentre diminuendolo aumentano i salvataggi e ripristini di stato dei processi e quindi l’overhead del S.O..

12

Esempio: RR con quanto di tempo = 20

Processo Burst TimeP1 53P2 17P3 68P4 24

• Lo schema di Gantt è:

• In genere si ha un tempo medio di turnaround maggiore rispetto a SJF, tuttavia si ha una migliore risposta.

P1

P2

P3

P4

P1

P3

P4

P1

P3

P3

0 20 37 57 77 97 117 121 134 154 162

7

13

Un quanto di tempo minore incrementa i context switch

14

Tempo di turnaround varia con il quanto ditempo

Il tempo di completamento medio non migliora con l’aumento del quanto.

Può migliorare se la maggior parte dei processi termina in un solo quanto di tempo.

8

15

Scheduling a priorità

Si parla di scheduling a priorità quando la scelta del processo tra i processi in attesa è fatta in funzione di una priorità chepuò essere sia statica che dinamica.

Per impedire che processi prioritari facciano uso indefinito di una risorsa (starvation) uno scheduling a priorità è sempre preemptive.

Es. di priorità statica: la priorità di un processo è definita a priori in funzione della sua importanza

Es di priorità dinamica: la priorità di un processo dipende dalla frazione di tempo, rapportata alla slice, di ultimo utilizzo della risorsa per cui attende

16

Scheduling a code multiple

Algoritmi di scheduling a priorità che utilizzano per i processi tante code di attesa quanti sono i livelli di priorità previsti.

Ad ogni coda è associato un quanto di tempo di utilizzo massimo della risorsa gestita decrescente al crescere della priorità.

I processi sono assegnati permanentemente ad una coda (es. coda foreground o background).

9

17

Scheduling con code multiple

• La ready queue è suddivisa in code separate:es. foreground (interattiva)

background (batch)• Ciascuna coda ha il proprio algoritmo di

scheduling, foreground – RRbackground – 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

18

Code multiple con feedback

• Un processo può spostarsi fra le varie code giacché la sua priorità può variare dinamicamente.– Tipicamente la priorità aumenta se è piccola la frazione di slice

spesa per utilizzare in precedenza la risorsa e diminuisce se è stata utilizzata l’intera slice. La priorità può anche aumentare con l’aumentare dell’attesa in coda (aging).

• Lo scheduler con code multiple con feedback è definito daiseguenti 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

10

19

Esempio di code multiple con feedback

• Tre code: Q0 – quanto di tempo di 8 millisecondi. Q1 – quanto di tempo di16 millisecondi. Q2 – FCFS

• Scheduling– Un nuovo job viene immesso 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.

20

Scheduling Shortest–Job–First (SJF)

• Si associa a ciascun processo la lunghezza del suosuccessivo 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 quellocorrente non termina il burst di CPU.

– preemptive – se arriva un nuovo processo con burst di CPU minoredel tempo rimasto per il processo corrente, il nuovo processo vienesostituito 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.

11

21

Processo Tempo di arrivo Burst TimeP1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4

• SJF (non-preemptive)

• tempo medio di attesa = (0 + 6 + 3 + 7)/4 = 4

Esempio di SJF nonpreemptive

P1 P3 P2

73 160

P4

8 12

22

Processo Tempo di arrivo Burst TimeP1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4

• SJF (preemptive)

• tempo medio di attesa = (9 + 1 + 0 +2)/4 = 3

P1 P3P2

42 110

P4

5 7

P2 P1

16

Esempio di SJF preemptive

12

23

Scheduling Shortest–Job–First (SJF)

• SJF nasce come algoritmo di scheduling a lungo termine

• E’ l’algoritmo ottimale per minimizzare il tempo medio di attesa di assegnazione di una risorsa

• Richiede di conoscere a priori per quanto tempo una risorsa sarà impiegata dal processo una volta che la ha ottenuta. Poiché questo di solito non è noto, si basa su una sua stima.

• Nel caso dello scheduler a lungo termine il tempo è quello stimato dall’utente.

• Nel caso di scheduling di un processo può essere stimato con una media esponenziale che tiene conto dei tempi di utilizzo precedenti

24

Scheduling shortest job (process) first SJF

Media esponenziale:

τn+1 = tnα + τn(1-α)

− τn+1, τn tempi stimati

- tn tempo effettivo

− α coefficiente 0<= α <= 1

Algoritmo pesante ma semplice da implementare per α = 1/2

13

25

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-j + …+(1 - α )n+1 τ0

• Dato che sia α che (1 - α) sono minori o uguali a 1, ciascun terminesuccessivo ha minor peso del suo predecessore. Più vecchia èl’osservazione, meno conta nella media.

26

Esempio: lo scheduling della CPU in UNIX

Lo scheduling si basa su una struttura di code a più livelli di priorità. C’è prerilascio ogni secondo.

La priorità di un processo in stato utente varia nel tempo mentre quella in stato kernel viene ridefinita in funzione dell’evento quando il processo va in attesa .

Il ricalcolo della priorità in stato utente tende a privilegiare i processi che in tempi recenti hanno effettuato CPU burst brevi.

Modalità di ricalcolo: Ogni secondo un daemon divide per due il contatore di utlizzi recente della CPU il cui valore definisce la nuova priorità e quindi la nuova posizione dei processi nellecode. Il contatore di utilizzo viene incrementato di 1 ogni 20msec quando il processo è running.

14

27

Scheduling garantito

Divide il tempo di utilizzo di una risorsa tra gli n processi presentiLa priorità di un processo in attesa dipende dall’utilizzo complessivo precedente della risorsa rapportato a 1/n

Scheduling a lotteria

Ad un processo sono assegnati uno o più ticket. Lo scheduler estrae un ticket per selezionare il processo in attesa

28

Real-Time Systems

• Control of laboratory experiments• Process control plants• Robotics• Air traffic control• Telecommunications• Military command and control systems

15

29

Characteristics of Real-Time Operating Systems

• Deterministic– Operations are performed at fixed,

predetermined times or within predetermined time intervals

– Concerned with how long the operating system delays before acknowledging an interrupt

30

Characteristics of Real-Time Operating Systems

• Responsiveness– How long, after acknowledgment, it takes the

operating system to service the interrupt– Includes amount of time to begin execution of

the interrupt– Includes the amount of time to perform the

interrupt

16

31

Characteristics of Real-Time Operating Systems

• User control– User specifies priority– Specify paging– What processes must always reside in main

memory– Disks algorithms to use– Rights of processes

32

Characteristics of Real-Time Operating Systems

• Reliability– Degradation of performance may have

catastrophic consequences– Attempt either to correct the problem or

minimize its effects while continuing to run– Most critical, high priority tasks execute

17

33

Features of Real-Time Operating Systems

• Fast context switch• Small size• Ability to respond to external interrupts

quickly• Multitasking with interprocess

communication tools such as semaphores, signals, and events

• Files that accumulate data at a fast rate

34

Features of Real-Time Operating Systems

• Use of special sequential files that can accumulate data at a fast rate

• Preemptive scheduling base on priority• Minimization of intervals during which

interrupts are disabled• Delay tasks for fixed amount of time• Special alarms and timeouts

18

35

Scheduling of a Real-Time Process

36

Scheduling of aReal-Time Process

19

37

Scheduling of a Real-Time Process

38

Scheduling of a Real-Time Process

20

39

Lo scheduling nei sistemi Real Time

E’ essenzialmente lo scheduling della CPU.Lo scheduler deve garantire che al manifestarsi di un evento un processo termini entro un tempo massimo predefinito.L’evento può essere sia periodico che aperiodicoAffinché un sistema possa gestire eventi multipli periodici deve essere schedulabile ossia:

m

Σ Ci/Pi <= 1i=1

dove m sono gli eventi, Pi il periodo dell’evento i-esimo e Ci i secondi di CPU richiesti per gestirlo

40

Periodic Task Timing Diagram

21

41

Algoritmi di scheduling real time per eventi periodici

Algoritmo rate monotonic

Ciascun processo ha una priorità pari alla frequenza di attivazione e lo scheduler assegna sempre la CPU al più prioritario applicando il prerilascio se necessario.

Algoritmo earliest deadline first

Il scheduler sceglie il processo la cui successiva attivazione (deadline) è la più prossima nel tempo.

Algoritmo laxity

Lo scheduler sceglie il processo la cui elaborazione termina più vicina al suo tempo limite massimo per terminare.