1

Gestione del processore (Scheduler)

Il modello a processi sequenziali

2

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

3

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

4

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

5

Pronto(ready)

Bloccato(blocked)

In esecuzione(running)

Il processore lo staeseguendo

Può proseguire ma è in attesa che lo schedulergli assegni il processore

È in attesa che venga terminata una richiesta effettuata (system call)

Stati di un processo

• Come si passa da uno stato all’altro ?

6

Pronto

Bloccato In esecuzione

Stati di un processo

• Lo scheduler ha deciso di mandare in esecuzione proprio questo processo

7

Pronto

Bloccato In esecuzione

Stati di un processo

• Il processo ha eseguito una SC e il servizio non può essere completato

8

Pronto

Bloccato In esecuzione

Stati di un processo

• Il servizio richiesto è stato completato– es : è arrivata una interruzione dal dispositivo, ...

9

Pronto

Bloccato In esecuzione

Stati di un processo

• Lo scheduler ha deciso di assegnare il processore ad un altro processo

10

Pronto

Bloccato In esecuzione

Stati di un processo

• Le altre due transizioni tipicamente non hanno senso

11

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

12

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 utentiefficienza nell’utilizzo delle risorse della macchina

Lo scheduling ha obiettivi diversi in diversi sistemi (batch, interattivi…)

13

Scheduling Obiettivi principali degli Algoritmi di Scheduling:Fairness (Equità) - processi della stesso tipo devono avere

trattamenti similiBalance (Bilanciamento) - tutte le parti del sistema devono

essere sfruttate (CPU, dispositivi …)Sistemi batchThroughput - massimizzare il numero di job completati in un intervallo di tempoTempo di Turnaround - minimizzare il tempo di permanenza di un job nel sistema

Sistemi interattiviTempo di risposta - minimizzare il tempo di riposta agli eventiProporzionalità - assicurare che il tempo di risposta sia proporzionale alla complessità dell’azione richiesta

14

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

15

Scheduling

Scheduling in sistemi batchSJF (shortest job first)

Scheduling in sistemi interattiviRound RobinCode Multiple

17

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

18

Scheduling Round Robin

Come fissare il quanto di tempodeve 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 interattiviin sistemi reali tipicamente 20-120 ms

19

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)

20

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)

21

Scheduling con Code multiple

Esempio di algoritmo di scheduling a code multiple con 4 classi di priorità

22

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