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:

1. richiesta di I/O da parte del processo attuale
2. lo stato del processo passa da esecuzione a pronto (eg per via di un interrupt)
3. lo stato del processo passa da attesa a pronto (eg fine di un I/O)
4. 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. Il tempo di latenza del dispatch è la somma del tempo effettivo che serve per cambiare il contesto. Il cambio fisico di contesto può essere anche molto breve, ma possono esserci altri eventi che ritardano l'ingresso in CPU di un processo. Vedi sotto per i sistemi soft realtime.

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

α è il coefficiente di oblio: mi dice quanto far pesare la storia recente, e quanto quella passata. n è il numero di picco.
* α = 0 => la storia recente non ha peso

• α = 0 => conta solo la storia recente
• α = 1/2 => metà e metà

Può essere sia preemptive che non preemptive. Se arriva un nuovo processo con un prossimo picco di CPU breve, allora, se SJF è preemptive, quello attuale viene preemptivato.

SJF preemptive = schedulazione shortest remaining time first = il processo con il più breve tempo rimanente va per primo.

6.3.3 Schedulazione a priorità

SJF è un caso speciale della schedulazione a priorità => dà la priorità ad un certo parametro, nel suo caso la durata del prossimo picco di CPU.

In generale, si assegna la priorità ad un processo, e chi ha la priorità maggiore va per primo.

Ocio: in alcuni SO, numero alto = priorità alta; in altri è il contrario.

La priorità si può decidere in base a diversi criteri, eg limiti di tempo del processo, files aperti, ma anche quanto ha pagato l'utente cui il processo appartien.

Può essere sia preemptive che non preemptive.

Problema: la starvation = un processo a priorità bassa può aspettare indefinitamente perché processi a più alta priorità gli passano sempre davanti.
Per ovviare: aging = un processo a bassa priorità invecchiando aumenta, così prima o poi verrà eseguito.

6.3.4 Schedulazione Round-Robin (RR)

Simile a FCFS ma con preemption.

Quanto di tempo = time slice = un processo può usare la CPU al max per un quanto di tempo. La coda è FIFO.

Se un processo sta ancora usando la CPU quando scade il quanto, viene preemptivato. Se invece la lascia prima per un I/O, tanto meglio per gli altri.
Spesso il tempo medio di attesa è lungo.

Prestazioni di RR = dipendono dalla dimensione del quanto:

• quanto grande => RR = FCFS
• quanto piccolo => ai processi appare un processore con 1/n potenza, dove n è il numero di processi = condivisione del processore realizzato però in HW => ma se è in SW, c'è anche l'overhead dei cambi di contesto
• regola empirica: regolo il quanto di tempo in modo che l'80% dei picchi venga realizzato entro il quanto.

6.3.5 Schedulazione con coda a più livelli (C+L)

Usata nei casi in cui posso classificare i processi in gruppi distinti.
Ad esempio, processi in foreground (primo piano) e background (sullo sfondo) => quelli in primo piano hanno bisogno di tempi di risposta più brevi => schedulati prima rispetto agli altri.

C+L:

• molte code separate
• un processo appartiene per sempre ad una coda
• ogni coda ha il suo algo di schedulazione interno
• ci deve essere schedulazione tra le code (di solito, priorità invariabile preemptive)

Per schedulare tra le code, posso scegliere diversi modi:

• non eseguo niente della coda bassa se ho ancora processi nella coda alta
• ogni coda ha tot tempo, scaduto il quale cambio coda. Le code alte hanno più tempo di quelle basse.

Ocio: come detto sopra, ogni coda poi schedula i suoi processi con l'algo che preferisce.

Il vantaggio è che l'overhead di schedulazione è basso, ma non è flessibile.

6.3.6 Schedulazione con coda a più livelli con retroazione (C+LR)

Come la C+L, ma permette ai processi di muoversi tra le code.
Divido i processi in base alle loro caratteristiche di uso della CPU: se uno ha picchi lunghi, lo spedisco in una coda più bassa => i processi interattivi e I/O-bound stanno in alto.

Inoltre, un processo che passa troppo tempo in code basse viene promosso a code più alte => prevenzione della starvation.

Gli schedulatori C+LR sono definiti in base a queste caratteristiche:

• numero di code
• algo di schedulazione per ciascuna coda
• metodo per far salire o scendere processi tra le code
• metodo per stabilire la coda iniziale in cui si trova un processo appena creato

È il più complesso, ma il più adattabile a tante situazioni.

6.4 Schedulazione su sistemi multiprocessore

Parleremo di sistemi omogenei, dove cioè tutti i processori sono equivalenti in quanto a funzionalità.

Load sharing = suddivisione del carico:

• una coda per processore
• una coda comune, e il processo va nel primo processore libero

Multiprocessamento asimmetrico: un processore gestisce le code, gli altri solo il codice utente.
Multiprocessamento simmetrico = SMP: ogni processore guarda la coda comune e prende da lì i processi => far sì che i 2 processori non scelgano lo stesso processo.

6.5 Schedulazione per sistemi in tempo reale

Hard realtime = completare un'operazione entro un tempo garantito => occorre riservare le risorse in anticipo, e occorre sapere esattamente quanto tempo ci mette il sistema per gestire le funzioni richieste.
È impossibile da realizzare in sistemi con memoria secondaria o virtuale, perché impredicibili (capitoli 9 ~ 14).

In molti casi, i processi sono periodici:

• tempo fisso di elaborazione: t
• scadenza: d
• periodo: p
• frequenza: 1/p

Lo schedulatore assegna priorità in base a uno di questi fattori. Il controllo dell'ammissione stabilisce se le richieste che un processo fa possono essere soddisfatte: se non è possibile, il processo viene rifiutato.

Schedulazione a frequenza monotòna = un processo ha una priorità inversamente proporzionale al suo periodo => quelli che usano la CPU più frequentemente sono privilegiati. È preemptive.
È anche ottimo, ma la CPU non è sempre sfruttata bene.

Schedulazione a scadenza più urgente = EDF (earliest deadline first). Scadenza breve = priorità alta. Il processo deve dichiarare la sua scadenza.
Valido anche per processi non periodici, e sfrutta la CPU al massimo (escludendo i cambi di contesto).

Soft realtime = i processi sono divisi in critici e non, e quelli critici hanno la priorità sugli altri => va bene per multimedia etc. in sistemi che non sanno garantire l'hard realtime.

Proprietà:

1. la schedulazione è a priorità = i processi a priorità alta NON la abbassano mai, mentre possono alzarla i processi con priorità bassa (per evitare la starvation)
2. il tempo di dispatch deve essere il più basso possibile

La proprietà 1 si ottiene facilmente.
La proprietà 2 no, perché molte volte il kernel è impiegato in chiamate I/O lente, in quanto le periferiche stesse sono lente => occorre poter interrompere il kernel => proteggere tutte le strutture dati del kernel con meccanismi di sincronizzazione.

Infatti, se si assume che il kernel non sia mai interrotto, allora le sue strutture dati le tocca solo lui, e non c'è problema. Ma in questo caso può essere interrotto da processi => occorre provvedere.
Richiamo a quanto detto prima nel paragrafo 6.1.3:
Il kernel è impegnato in una chiamata di sistema da parte di un processo, la quale modifica dati del kernel; viene preemptivato; passa il controllo ad un'altro processo il quale vuole modificare gli stessi dati => o risolvo impedendo che il kernel possa essere preemptivato, o sincronizzo anche le strutture dati del kernel.
Nel caso del soft realtime, la sincronizzazione è obbligatoria.

Inversione di priorità: un processo a priorità bassa usa delle risorse condivise. Arriva un processo ad alta priorità e vuole usarle anche lui => deve aspettare che il processo a bassa priorità finisca.

Per evitare questa situazione, si usa l'ereditarietà della priorità: se un processo vuole usare risorse usate anche da un processo ad alta priorità, prende temporaneamente la priorità del processo ad alta priorità, così si spiccia.

6.6 Schedulazione dei thread

Nei SO che li supportano, sono i kernel thread, e non i processi, ad essere schedulati. I thread user level non sono noti al kernel, e deve essere la libreria a mapparli su kernel thread (mappatura diretta) o su LWP (mappatura indiretta).

6.6.1 Visibilità della competizione

Contention scope = come i thread competono per l'accesso alle risorse.

Process contention scope = il SO sceglie quale processo schedulare. All'interno del processo, i thread competono tra di loro.
System contention scope = i thread competono a livello di SO.

Il SCScope è usato quindi quando ho mappature uno a uno: un thread utente compete con gli altri thread utenti anche di altri processi.
PCS è usato con le mappature molti a molti e molti a uno, in cui la libreria di thread sceglie chi mappare eg. sull'LWP disponibile.

6.6.2 Schedulazione di Pthread

...

6.7 Esempi di SO

...

6.8 Schedulazione dei thread in Java

...

6.9 Valutazione degli algoritmi di schedulazione

Quale algo scelgo per il mio sistema? Sopra ho visto i differenti algo, ognuno con le sue caratteristiche => decidere quale è il più adatto al mio sistema, tramite la valutazione.

6.9.1 Modellazione deterministica

Valutazione analitica = uso un algo e il carico del sistema per produrre una formula che valuti le prestazioni dell'algo per quel carico.

Modellazione deterministica = un tipo di valutazione analitica.
Semplice, veloce, precisa => richiede però info esatte sul carico.

6.9.2 Modelli a reti di code

In molti sistemi i carichi variano di ora in ora => stabilisco la media dei picchi di CPU e di I/O => probabilità di un picco in un dato momento.

Occorre anche la distribuzione dei tempi di arrivo dei processi nel sistema.

Se ho la media dei picchi e la distribuzione dei tempi di arrivo so calcolare utilizo, throughput e tempo di attesa medio per gli algo di schedulazione.

Sistema = fornitore di servizi, in generale => ogni servizio ha una coda:

 n = lugnhezza media della coda
 W = tempo medio di attesa in coda
 λ = frequenza media di arrivo in coda
 => nel tempo W, arriveranno in coda λ * W nuovi processi
 => formula di Little: n = λ * W

La formula di Little è valida per ogni algoritmo. La posso usare per ogni coda del mio sistema e farmi un'idea generale. Il problema è che si tratta di un'approssimazione => poco accurata.

6.9.3 Simulazioni

Creo un modello del mio sistema, e simulo le varie richieste.

Che dati uso da dare in pasto alla simulazione:

• valori casuali per numero processi, picchi di CPU, I/O, tempi di arrivo dei processi etc.
• uso i dati rilevati in un sistema vero.

Meglio usare dati veri. Cmq è un processo costoso: ore di calcoli.

6.9.4 Implementazione

Le simulazioni intrinsecamente sono poco accurate => implemento il mio algo di scheduler e vedo come si comporta nella realtà.

Problema:

• costo dell'implementazione in un SO reale
• insoddisfazione degli utenti: uso il SO per esperimenti e non per lavoro
• gli utenti possono adattarsi allo scheduler dando così falsi risultati.

Esempio di quest'ultimo punto: ho uno scheduler che toglie i processi che per 1 secondo non fanno I/O => i programmatori fanno scrivere a caso qualcosa sul terminale ogni secondo per non perdere priorità.

Torna alla pagina di Sistemi Operativi