Sistemi Operativi

SCHEDULING DELLA CPU

L’operazione dei scheduling permette di sfruttare al meglio le risorse del PC

rendendolo più produttivo, operando direttamente sui thread. In un sistema

monoprocessore un solo processo viene eseguito per volta. Durante la sua esecuzione

si altreran tra due fasi: CPU burst e I/O burst. L’idea è quella di utilizzare i tempi di

attesa della CPU durante la fase di I/O burst per assegnare la CPU ad un altro

processo. Un processo consiste in un ciclo di elaborazione svolto dalla CPU e da un

tempo di attesa di un disp I/O.

In fase di lancio un processo esegue un lungo ciclo di utilizzo della CPU e

successivamente si alternano fasi di CPU e I/O burst. Quelli con prevalenza I/O

producono tanti accessi alla CPU ma di breve durata mentre quelli con prevalenza CPU

producono pochi accessi alla CPU ma di lunga durata. Lo scheduler a breve

terminedella CPU seleziona tra tutti i processi presenti in memoria e pronti per essere

eseguiti, quello a cui assegnare la CPU.

1.Un processo passa dallo stato di esecuzione allo stato di attesa

2.Un processo passa dallo stato di esecuzione allo stato di pronto

3.Un processo passa dallo stato di attesa allo stato di pronto

4.Un processo termina.

Se le scheduler interviene solo nelle fasi 1 e 4 allora è chiamato senza diritto di

prelazione (non preemptive) altrimenti è chiamato con diritto di prelazione. Per quanto

riguarda lo scheduler con prelazione, due processi che lavorano con dati condivisi

potrebbero avere problemi di incoerenza quando uno dei due processi viene

prelazionato mentre si sta modificando dei dati. Durante una chiamata di sistema il

processo potrebbe essere prelazionato mentre il SO è in modalità kernel.

Il dispatcher è il modulo del sistema operativo che si occupa di passare alla CPU il

processo quindi, cambio di contesto, il passaggio alla modalità utente, il salto alla

giusta posizione del programma utente per riavviare l’esecuzione. il tempo impiegato

per fermare un processo e avviarne l’esecuzione di un altro viene chiamata la latenza

di dispatch. Per potere scegliere un algoritmo di scheduling è opportuno tener conto

dell’utlizzo della CPU, il tempo di completamento, quello di attesa (somma degli

intervalli di tempo passati nella coda dei processi pronti) e quello di risposta. È

opportuno, inoltre, massimizzare l’utilizzo della CPU tenendola sempre occupata, 8

minimizzare il tempo di completamento e minimizzare il tempo di risposta producendo

il risultato quanto prima possibile.

Lo scheduling in ordine di arrivo (First-come first-served FCFS) assegnando la CPU al

primo processo che la richiede. I vari processi quindi, vengono messi all’interno di una

coda FIFO, quando la CPU è libera, viene assegnata al primo processo in testa alla

coda. Questo è un algoritmo senza prelazione la CPU viene rilasciata dal processo

dopo che termina l’esecuzione o quando richiede una operazione di I/O. Si verifica

l’effetto convoglio quando un processo occupa per molto tempo la CPU e numerosi

processi al termine di un I/O si accodano.

Lo scheduling per brevità (shortest-job-first SJF) assegna la CPU al processo con il CPU

burst minore ma nel caso in cui due processi hanno lo stesso tempo di occupazione

allora si untilizza uno scheduler FCFS.

Può essere con o senza prelazione: con prelazione, se arriva un nuovo processo con

CPU burst ingeriore a quello attualmente in esecuzione, il processo viene prelazionato;

senza prelazione, una volta che la CPU è stata assegnata non può essere prelazionata

finchè il processo non completa il suo CPU burst. Il tempo medio di attesa è minimo

per un dato insieme di processi.

Nello scheduling con priorità associamo un valore di priorità ad ogni processo. La CPU

viene assegnata al processo con priorità più alta, ad esempio il valore 0 potrebbe

indicare una priortà bassa mentra il valore 4999 una priorità più alta. Le proprità

possono essere assegnate internamente (in base al numero di operazioni di I/O e alla

lunghezza delle sequenze di operazioni della CPU; esternamente, importanza del

processo, tipo di processo, fondi pagati e politica di assegnazione delle priorità.

Lo scheduling per priorità può essere: con o senza prelazione. Con prelazione, quando

arriva un processo con priorità maggiore allora viene prelazionato il processo attuale

in esecuzione; Senza prelazione, l’ultimo processo arrivato viene inserito in testa alla

coda. Negli scheduling per priorità vi è il problema dell’attesa indefinita o starvation,

ovvero un processo con priorità bassa ed in attesa della CPU, potrebbe rimanere in

attesa per un tempo indefinito. Una soluzione sarebbe quella di applicare un

invecchiamento in cui la priorità dei processi viene aumentata con il passare del

tempo. In base al quanto di tempo è possibile stabilire i vari cambi di contesto e quindi

è opportuno evitare overhead.

Nell’algoritmo di scheduling circolare (round robin RR) ad ogni processo è concesso un

quanto di tempo o porzione di tempo (time slice). Al termine del quanto di tempo il

processo in esecuzione è prelazionato ed inserito alla fine della coda circolare. Lo

scheduler della CPU scorre la coda dei processi pronti per individuare il primo processo

della coda a cui assegnare il prossimo quanto di tempo. Una volta determinato il

processo, lo scheduler imposta un timer pari al quanto di tempo ed attiva il dispatcher

per l’esecuzione del processo.

Durante l’esecuzione del processo possono accadere due cose: il processo ha una

sequenza di operazioni della CPU minore del quanto di tempo e quindi rilascerà

spontaneamente la CPU; il processo termina il suo quanto di tempo e lo scheduler

passa all’esecuzione del prossimo processo. Se ci sono n processo nella coda dei

processi pronti e il quanto di tempo è q allora ogni processo otterrà 1/n del tempo

della CPU e nessun processo attenderà più di (n-1)q quanti di tempo.

Performance (se q è molto grande si ottiene lo scheduling FCFS); se q è piccolo il

contex switch potrebbe essere prevalente sul tempo totale creando un eccessivo

overhead. La dimensione del quanto di tempo è fondamentale per evitare overhead

dei cambi di contesto.

È possibile distinguere i processi eseguiti in primo piano da quelli eseguiti in

sottofondo. Per i processi foreground si può utilizzare un algoritmo RR mentre per

quelli in background si piò utilizzare un algoritmo FCFS. Quelli in foreground quindi

devono essere eseguiti prima dei processi in background oppure è possibile assegnare

ad ogni coda un certo quanto di tempo della CPU. 9

Nello scheduling a code multiple con retroazione i processi possono essere spostati da

una coda ad un’altra nel senso che, un processo che utilizza troppi cicli di CPU viene

spostato su una coda con priorità più bassa mentre quelli con prevalenza di I/O sono

spostati in code con priorità più alta. Essi sono caratterizzati da una serie di parametri:

numero di code, algo di scheduling per ciascuna coda, metodo utilizzato per spostare

un processo da una coda con priorità maggiore verso una con priorità minore o

viceversa.

Esistono due tipi di multielaborazione: asimmetrica (un solo processore si occupa di

gestire il sistema e gli altri processori eseguono solo il codice; simmetrica (i processi

sono mantenuti in una coda comune oppure ogni processore ha una coda propria). I

processori moderni dispongono di enormi quantità di cache per migliorare le

prestazioni. Di conseguenza i processi possono migrare tra i vari processori ma nel

momento in cui viene spostato i dati della cache saranno invalidati e per questa

ragione si utilizza la predilezione, ovvero la possibilità di essere eseguito su di una

particolare CPU o meno (predilezione debole (cambia processore) predilezione forte

(non cambia processore)). Nel caso in cui un processore non viene occupato allo

stesso modo degli altri, per ottenere il bilanciamento, è opportuno adottare la

migrazione guidata (un processo si occupa di bilanciare periodicamente il carico di

lavoro sulle diverse CPU) o migrazione spontanea (un processore poco carico sottrae

processi ad una CPU troppo carica).

SINCRONIZZAZIONE DEI PROCESSI

Poiché nei nei SO multi programmati è possibile che i diversi thread o i diversi processi

possono essere eseguiti in maniera asincrona (condividendo dati), allora è opportuno

adottare delle politiche di sincronizzazione in modo tale da evitare una certa

incoerenza nel momento in cui si fa accesso ai dati condivisi. Considerando il

paradigma, produttore e consumatore (di oggetti), useremo una variabile contatore

che si incrementa o decrementa ogni volta che aggiungiamo un elemento nel buffer.

L’ordine con cui si accede ai dati condivisi è importante e determina la consistenza dei

dati (race condition).

La condizione deve essere che un solo processo alla volta può modificare i dati

attraverso una forma di sincronizzazione e coordinazione dei processi. Viene definita

sezione critica quella porzione di codice del processo in cui va a modificare dati

condivisi. Ogni processo deve chiedere il permesso di accesso alla sezione critica

tramite una sezione d’ingresso e come ultimo step abbiamo la sezione di uscita

mentre il rimanente codice non è critica. Si dice mutua esclusione quando un processo

è in esecuzione nella sua sezione critica e di conseguenza nessun altro processo può

trovarsi nella propria sezione critica.

Solo i processi fuori dalle rispettive sezioni non critiche possono decidere chi sarà il

prossimo processo ad entrare nella propria sezione critica e questa decisione non può

essere rimandata indefinitamente; cioè Qualsiasi processo deve riuscire ad entrare

nella propria sezione critica. Abbiamo una attesa limitata nel senso che deve esistere

un limite al numero di volte che si consente ai processi di entrare nella propria sezione

critica dal momento in cui un processo precedentemente ha richiesto di farlo. Per cui è

opportuno garantire una mutua esclusione, progresso e attesa limitata.

Nella progettazione di un SO la gestione delle sezioni critiche vengono attuate per

mezzo dei kernel senza o con diritto di prelazione. Con diritto di prelazione, un

processo in kernel mode, può essere interrotto da un altro processo; senza diritto di

prelazione, non può essere interrotto da un altro processo.

Progettare un kernel senza diritto di prelazione è più semplice in quanto è sufficiente

disattivare gli interrupt quando un processo è in modalità kernel; normalmente la

disabilitazione degli interrupt sarà temporanea e di breve durata. Al termine tutto

riprenderà a funzion