6 schedulingCPU
6 schedulingCPU
6 schedulingCPU
1
Scheduling della CPU
2
Coda dei processi pronti (ready queue):
PCBi PCBj PCBk
primo
ultimo
3
Terminologia: CPU burst & I/O burst
Ogni processo alterna:
• CPU burst: fasi in cui viene impiegata soltanto la CPU senza I/O
• I/O burst: fasi in cui il processo effettua input/output da/verso una
risorsa(dispositivo) del sistema
(burst = raffica)
4
Terminologia:
Processi I/O bound & CPU bound
• A seconda delle caratteristiche dei programmi eseguiti
dai processi, e` possibile classificare i processi in:
r Processi I/O bound:
bound prevalenza di attivita` di I/O
èMolti CPU burst di breve durata, intervallati da I/O
burst di lunga durata.
r Processi CPU bound:
bound prevalenza di attivita`
computazione:
èCPU burst di lunga durata, intervallati da pochi I/O
burst di breve durata.
5
Terminologia:
Pre-emption
Gli algoritmi di scheduling si possono classificare in due
categorie:
r senza prelazione (non pre-emptive): la CPU rimane
allocata al processo running finchè esso non si sospende
volontariamente (ad esempio, per I/O), o non termina.
r con prelazione (pre-emptive ): il processo running può
essere prelazionato, cioè: il S.O. può sottrargli la CPU per
assegnarla ad un nuovo processo.
6
Politiche & Meccanismi
Scheduler = POLITICHE
Dispatcher = MECCANISMI
7
Criteri di Scheduling
Per analizzare e confrontare i diversi algoritmi di scheduling,
vengono considerati alcuni parametri:
r Utilizzo della CPU:esprime la percentuale media di utilizzo della CPU
nell’unita` di tempo.
r Throughput (del sistema): esprime il numero di processi completati
nell’unità di tempo.
r Tempo di Attesa (di un processo): tempo totale trascorso nella ready
queue.
r Turnaround (di un processo): è l’intervallo di tempo tra la sottomissione
del job e il suo completamento.
r Tempo di Risposta (di un processo): intervallo di tempo tra la
sottomissione e l’inizio della prima risposta (a differenza del turnaround,
non dipende dalla velocità dei dispositivi di I/O)
8
Criteri di Scheduling
In generale:
• devono essere massimizzati:
massimizzati
r Utilizzo della CPU (al massimo: 100%)
r Throughput
r Tempo di Attesa
9
Criteri di Scheduling
Non è possibile rispettare tutti i criteri
contemporaneamente.
10
Algoritmo di scheduling FCFS
• First-Come-First-Served: la coda dei processi pronti
viene gestita in modo FIFO:
• i processi sono schedulati secondo l’ordine di arrivo
nella coda
• algoritmo non pre-emptive
Esempio: tre processi [Pa, Pb, Pc] (diagramma di Gantt)
Pa Pb Pc
t
0 32 36 43
11
Algoritmo di scheduling FCFS
Esempio: se cambiassimo l’ordine di scheduling:
[Pb, Pc, Pa]
Pb Pc Pa
t
0 4 11 43
12
Problemi dell’algoritmo FCFS
Non è possibile influire sull’ordine dei processi:
13
Algoritmo di scheduling FCFS:
Esempio: [P1, P2,effetto
P3, P4]convoglio
• P1 e` CPU bound; P2,P3,P4 sono I/O bound
• P1 effettua I/O nell'intervallo [t1,t2]
P4
P3
P2
P1
t1 t2
CPU inattiva
Sistemi Operativi L-A - Scheduling della CPU 14
14
Algoritmo di scheduling SJF
(Shortest Job First)
Per risolvere i problemi dell’algoritmo FCFS:
r per ogni processo nella ready queue, viene stimata la lunghezza
del prossimo CPU-burst
r viene schedulato il processo con il CPU burst più piccolo
(Shortest Job First)
Pb Pc Pa
t
0 4 11 43
Ø si può dimostrare che il tempo di attesa è ottimale
Sistemi Operativi L-A - Scheduling della CPU 15
15
Algoritmo di scheduling SJF
(Shortest Job First)
SJF può essere:
r non pre-emptive
r pre-emptive: (Shortest Remaining Time First,
SRTF) se nella coda arriva un processo (Q) con CPU
burst minore del CPU burst rimasto al processo running
(P) è pre-emption: scambio tra P e Q.
Problema:
r è difficile stimare la lunghezza del prossimo CPU burst
di un processo (di solito: uso del passato per predire il
futuro)
16
Scheduling con Priorità
Ad ogni processo viene assegnata una priorità:
r lo scheduler seleziona il processo pronto con priorità
massima
r processi con uguale priorità vengono trattati in modo
FCFS
Priorità: possono essere definite
• internamente: il S.O. attribuisce ad ogni processo una
priorità in base a politiche interne
• esternamente: criteri esterni al S.O (es: nice in Unix).
17
Scheduling con Priorità
18
Scheduling con priorità
Problema: starvation dei processi.
Starvation: si verifica quando uno o più processi di priorità bassa
vengono lasciati indefinitamente nella coda dei processi
pronti, perchè vi è sempre almeno un processo pronto di
priorità più alta.
Soluzione: invecchiamento (aging) dei processi:
• ad esempio:
• la priorità cresce dinamicamente con il tempo di attesa
del processo.
• la priorità decresce con il tempo di CPU gia` utilizzato
19
Algoritmo di Scheduling Round Robin
É tipicamente usato in sistemi Time Sharing:
• La ready queue viene gestita come una coda FIFO circolare (v.
FCFS)
• ad ogni processo viene allocata la CPU per un intervallo di
tempo costante ∆t (time slice o, quanto di tempo):
• il processo usa la CPU per ∆t (oppure si blocca prima)
• allo scadere del quanto di tempo: prelazione della CPU e re-
inserimento in coda
20
Round Robin
• L’obiettivo principale è la minimizzazione del tempo
di risposta:
Ø adeguato per sistemi interattivi
21
Round Robin
Problemi:
Problemi
• dimensionamento del quanto di tempo
r ∆t piccolo (ma non troppo: ∆t>>Tcontext switch )
ü tempi di risposta ridotti, ma
ü alta frequenza di context switch => overhead
r ∆t grande:
ü overhead di context switch ridotto, ma
ü tempi di risposta più alti
• trattamento equo dei processi: processi di S.O. e
processi utente sono trattati allo stesso modo:
Ø possibilità di degrado delle prestazioni del S.O.
22
Approcci misti
23
Scheduling in Unix
Obiettivo: privilegiare i processi interattivi
Scheduling MLFQ:
r più livelli di priorità (circa 160): più grande è il
valore, più bassa è la priorità.
r Viene definito un valore di riferimento pzero:
– Priorità ≥ pzero: processi di utente ordinari.
– Priorità < pzero: processi di sistema (ad es. Esecuzione di
system call), non possono essere interrotti da segnali (kill).
r Ad ogni livello è associata una coda, gestita con Round
Robin (quanto di tempo: 0,1 s)
24
Scheduling in Unix
r Aggiornamento dinamico delle priorità: ad ogni
secondo viene ricalcolata la priorità di ogni processo.
r La priorità di un processo decresce al crescere del
tempo di CPU già utilizzato
Ø feedback negativo.
Ø di solito, processi interattivi usano poco la CPU: in questo
modo vengono favoriti.
25