(:title Riassunto del libro di SO - Capitolo 6: Schedulazione della CPU:)
:: Riassunto del libro di SO - Capitolo 6: Schedulazione della CPU ::
Torna alla pagina di Sistemi Operativi
In genere, schedulazione dei thread e dei processi sono sinonimi perché funzionano allo stesso modo. Se c'è qualcosa di specifico ai thread verrà segnato.
6.1 Concetti di base
Sistemi a singolo processore = eseguono 1 solo processo per volta => se un processo deve attendere, avendo la multiprogrammazione pesco un altro processo e faccio andare quello.
6.1.1 Il ciclo di picco di CPU e di I/O
Processo: picco di utilizzo della CPU, seguito da un picco di utilizzo di I/O, seguito da un picco di utilizzo della CPU etc.
Processo CPU-bound = pochi picchi di CPU, lunghi.
Processo I/O-bound = molti picchi di CPU, brevi.
Importante per scegliere quale processo schedulare
6.1.2 Lo schedulatore della CPU
CPU inattiva => lo schedulatore a breve termine sceglie un altro processo dalla coda dei processi pronti.
Ocio: vedremo che la coda non è necessariamente FIFO. Gli elementi della coda in genere sono i PCB dei processi.
6.1.3 Schedulazione con sospensione dell'esecuzione dei processi
Lo schedulatore interviene quando:
- richiesta di I/O da parte del processo attuale
- lo stato del processo passa da esecuzione a pronto (eg per via di un interrupt)
- lo stato del processo passa da attesa a pronto (eg fine di un I/O)
- quando un processo termina
Situazioni 1 e 4 = non c'è scelta: devo prendere un nuovo processo dalla coda dei processi pronti, se ne esiste uno.
Situazioni 2 e 3 = posso invece scegliere.
Schema di schedulazione cooperativa o non preemptive = una volta che la CPU è allocata ad un processo, questo non la molla finché non incappa in 1 o 4 => si può usare anche su macchine senza temporizzatore.
Schema di schedulazione preemptive = viene sospesa l'esecuzione.
Problemi della schedulazione preemptive:
- se un processo viene preemptivato mentre usa dati condivisi, li può lasciare in uno stato inconsistente => capitolo 7
- il processo chiama il kernel, e il kernel modifica dati condivisi per conto del processo => quel processo viene interrotto => un altro processo interpella il kernel per accedere agli stessi dati = CAOS
Per evitare il secondo caso, molti SO proibiscono al kernel di essere interrotto => anche se causa un calo di performance nell'esecuzione parallela di più processi (multiprocessing).
6.1.4 Caricamento del processo sulla CPU
Dispatcher = dà il controllo della CPU al processo scelto:
- cambio di contesto
- passaggio alla modalità utente
- salto alla corretta locazione contenuta nel Program Counter
Il dispatcher deve essere il più veloce possibile
6.2 Criteri di schedulazione
Posso scegliere quale processo schedulare in base a diversi criteri, che caratterizzeranno gli algoritmi usati:
- Utilizzo della CPU = voglio tenere la CPU più impegnata possibile
- Throughput = frequenza di completamento = completamento di processi nell'unità di tempo
- Tempo di completamento = quanto ci mette in media il singolo processo dall'immissione nel sistema alla terminazione
- Tempo di attesa = tempo passato dal processo nelle code
- Tempo di risposta = tempo necessario per far cominciare il processo a rispondere ad un evento processo.
Per i sistemi interattivi, è importante avere varianza nel tempo di risposta bassa.
6.3 Gli algoritmi di schedulazione
6.3.1 La schedulazione First Come First Served (FCFS)
Il processo che arriva per primo è il primo ad essere servito => una coda FIFO.
Facile da gestire MA il tempo d'attesa in genere è lungo, e dipende dall'ordine di arrivo.
Se c'è un processo ciccione, avviene l'effetto convoglio: lui ci mette tanto e gli altri ritardano tutti.
FCFS non è preemptive: se un processo ha la CPU, se la tiene.
6.3.2 Schedulazione Shortest Job First (SJF)
Il nome corretto sarebbe shortest next CPU burst first, ovvero: viene schedulato il processo che ha il più breve picco futuro di uso della CPU => non dipende dal tempo totale del processo, ma dal tempo che passerà prima di avere un picco della CPU.
Questo algoritmo è ottimale => minor tempo di attesa.
Problema = conoscere la lunghezza del prossimo picco di CPU!
In un sistema a lotti si può usare il tempo limite impostato dall'utente per quel job. Ma negli schedulatori a breve termine non c'è modo per conoscere la lunghezza del prossimo picco di CPU.
Però, si può tentare di prevederla => media esponenziale delle lunghezze misurate dei picchi precedenti.
Si usa la seguente formula:
τn+1 = ατn + (1 - α)τn
Torna alla pagina di Sistemi Operativi