Gestione del processore
(Scheduler)
Il modello a processi sequenziali
1
Introduzione
• Nei computer attuali, ci sono molte attività
attive contemporaneamente (sia di SO che
di utente)
– es : stampa in corso + Word + cd player …
• Tutto il software che gira su un calcolatore è
organizzato come un insieme di processi
sequenziali cooperanti
2
Cos’è un processo ?
• Un processo è un programma in esecuzione
completo del suo stato (spazio di indirizzamento,
registri, file aperti…)
• Come si crea un processo ?
– Richiedendo al SO l’esecuzione di una o più chiamate
di sistema
• Esempi di attivazione :
– l’invocazione di un comando, il doppio click su
un’icona, il lancio di un eseguibile …
– inizializzazione del sistema
3
Terminazione di un processo
• Un processo termina :
– Quando esegue una istruzione di terminazione
– Quando effettua una operazione illecita
• es. cerca di accedere alla memoria privata di altri
processi
– Quando c’è un errore che non gli permette di
proseguire (es. overflow, etc)
• In tutti questi casi il processore ricomincia
automaticamente ad eseguire il sistema
operativo
4
Stati di un processo
In esecuzione
(running)
Bloccato
(blocked)
È in attesa che
venga terminata
una richiesta
effettuata
(system call)
Pronto
(ready)
Il processore lo sta
eseguendo
Può proseguire ma è in attesa che lo scheduler
gli assegni il processore
• Come si passa da uno stato all’altro ?
5
Stati di un processo
In esecuzione
Bloccato
Pronto
• Lo scheduler ha deciso di mandare in
esecuzione proprio questo processo
6
Stati di un processo
In esecuzione
Bloccato
Pronto
• Il processo ha eseguito una SC e il servizio
non può essere completato
7
Stati di un processo
In esecuzione
Bloccato
Pronto
• Il servizio richiesto è stato completato
– es : è arrivata una interruzione dal dispositivo, ...
8
Stati di un processo
In esecuzione
Bloccato
Pronto
• Lo scheduler ha deciso di assegnare il
processore ad un altro processo
9
Stati di un processo
In esecuzione
Bloccato
Pronto
• Le altre due transizioni tipicamente non
hanno senso
1
Implementazione di processi
• Le informazioni relative a tutti i processi
attivi ad un dato istante sono mantenute
nella Tabella dei processi, che contiene tutte
le informazioni sul processo
– valore dei registri
– stato (pronto, bloccato …)
– informazioni relative ai file che il processo sta
utilizzando
1
Scheduling
Lo scheduler si occupa di decidere quale fra i processi
pronti può essere mandato in esecuzione
L’algoritmo di scheduling ha impatto su:
prestazioni percepite dagli utenti
efficienza nell’utilizzo delle risorse della macchina
Lo scheduling ha obiettivi diversi in diversi sistemi
(batch, interattivi…)
1
Scheduling
Obiettivi principali degli Algoritmi di Scheduling:
Fairness (Equità) - processi della stesso tipo devono avere
trattamenti simili
Balance (Bilanciamento) - tutte le parti del sistema devono
essere sfruttate (CPU, dispositivi …)
Sistemi batch
Throughput - massimizzare il numero di job completati in un
intervallo di tempo
Tempo di Turnaround - minimizzare il tempo di permanenza di un job
nel sistema
Sistemi interattivi
Tempo di risposta - minimizzare il tempo di riposta agli eventi
Proporzionalità - assicurare che il tempo di risposta sia proporzionale
alla complessità dell’azione richiesta
1
Scheduling
Scheduling senza prerilascio (non preemptive)
lo scheduler interviene solo quando un processo viene
creato, termina o si blocca su una SC
Scheduling con prerilascio (preempitive)
lo scheduler può intervenire ogni volta che è necessario
per ottenere gli obiettivi perseguiti
• quando diventa pronto un processo a più alta priorità
rispetto a quello in esecuzione
• quando il processo in esecuzione ha sfruttato la CPU per
un tempo abbastanza lungo
1
Scheduling
Scheduling in sistemi batch
SJF (shortest job first)
Scheduling in sistemi interattivi
Round Robin
Code Multiple
1
Scheduling nei sistemi Interattivi
Scheduling Round Robin
(a) lista dei processi pronti
(b) lista dei pronti dopo che B ha usato il suo quanto
(quantum) di tempo
1
Scheduling Round Robin
Come fissare il quanto di tempo
deve essere abbastanza lungo da ammortizzare il costo di un
context switch (ordine 1 ms)
deve essere abbastanza breve da permettere una risposta
veloce agli utenti interattivi
in sistemi reali tipicamente 20-120 ms
1
Scheduling con priorità
Ogni processo ha una priorità
Ogni volta va in esecuzione il processo a priorità
più elevata
Punti chiave :
come assegnare le priorità (statiche, dinamiche…)
come evitare attesa indefinita della CPU nei processi a
priorità più bassa (Starvation)
1
Scheduling con priorità
Molte strategie per il calcolo della priorità
Tipicamente :
priorità dinamica (es. più elevata per i processi che passano
da bloccato a pronto)
legata alla percentuale f del quanto di tempo che è stato
consumato l’ultima volta che il processo è andato in
esecuzione (es. proporzionale a 1/ f )
decrescente nel tempo per i processi che rimangono pronti
(es. per impedire l’attesa indefinita-starvation)
2
Scheduling con Code multiple
Esempio di algoritmo di scheduling a code multiple
con 4 classi di priorità
2
Scheduling con Code multiple
Scheduling Round Robin all’interno della classe
con priorità più elevata
I processi che usano tutto il quanto di tempo più di
un certo numero di volte vengono passati alla classe
inferiore
2