Sistemi operativi - Scheduling processi nei sistemi operativi

Scheduling dei processi

Quando più di un processo è eseguibile in un certo istante, il sistema deve decidere quale eseguire per primo. Questa funazione la

svolge lo scheduler, programma facente parte del S.O. che si occupa di scegliere quale processo mandare in esecuzione. Per evitare

tempi troppo lunghi di esecuzione di un processo i calcolatori prevedono l'utilizzo di un clock, un segnale periodico usato per

sincronizzare i dispositivi elettronici digitali. Ad ogni interrupt del clock il S.O. verifica se il processo in esecuzione può continuare o

se deve essere sospeso per poterne eseguire un altro. La strategia che permette di sospendere temporaneamente processi logicamente

eseguibili è detto scheduling con diritto di prelazione (Preemptive Scheduling), in contrapposizione al metodo di esecuzione a

completamento (sistemi batch) o non preemptive scheduling (senza diritto di prelazione). Normalmente la CPU viene utilizzata per un

periodo di tempo molto limitato, ma c’e bisogno di una potenza significativa perchè sono necessari picchi molto elevati di frequenza per

poter portare a termine operazioni in poco tempo.

Scheduling della CPU

Seleziona fra i processi in memoria quelli pronti per l’esecuzione e alloca la CPU a uno di essi. La decisione di scheduling della CPU

può avvenire quando un processo:

1. Passa da in esecuzione a in attesa (non-preemptive)

2. Passa da in esecuzione a pronto(preemptive)

3. Passa da in attesa a pronto (preemptive)

4. Termina (non-preemptive)

Quando lo scheduler ha scelto il processo, un modulo chiamato dispatcher gli passa il controllo della CPU.

Il procedimento prevede:

• un context switch

• passaggio a user mode

• salto alla giusta posizione del programma utente.

Il tempo che il dispatcher impiega a eseguire queste operazioni è detto latenza di dispatch.

Un buon algoritmo di scheduling dovrebbe soddisfare i seguenti criteri:

• Equità: ogni processo deve avere a disposizione una corretta quantità di tempo di CPU.

• Efficienza: CPU utilizzata al 100% sempre.

• Tempo di completamento: più piccolo possibile

• Tempo di risposta: deve essere minimizzato

• Tempo di attesa (trascorso in coda): deve essere minimizzato

• Throughput: massimizzare il numero di job processati per unità di tempo essendo il tempo di CPU finito alcuni di questi

obiettivi non sono compatibili fra di loro. Algoritmi di scheduling

FCFS (First Come First Served): si eseguono i processi nell'ordine con cui arrivano. È stato ideato per sistemi non interattivi. Per

valutare la prestazione di tale algoritmo si può effettuare attraverso la media dei tempi di attesa. Il risultato è migliore, in termini di

tempi di attesa, se i processi brevi venissero eseguiti per primi.

Tempi di attesa: P1 = 0; P2 = 24; P3 = 27

Tempo di attesa medio: (0 + 24 + 27)/3 = 17

Se invece l’ordine e: P2 , P3 , P1

Tempi di attesa: P1 = 6; P2 = 0; P3 = 3

Tempo di attesa medio: (6 + 0 + 3)/3 = 3

Il risultato e migliore, per cui i processi brevi e meglio che vengano eseguiti per primi.

SJF (Shortest Job Firts): usato per sistemi batch per i quali i tempi di esecuzione sono noti a priori. Lo scheduler dovrebbe

utilizzare questo algoritmo quando nella coda di input risiedono alcuni job di uguale importanza. Garantisce sempre il minor tempo di

attesa medio di risposta. Può essere con o senza prelazione. Senza prelazione il processo in esecuzione non può essere interrotto,

mentre nel caso con prelazione, se arriva un nuovo processo con un CPU burst più breve del tempo rimanente per il processo corrente,

il nuovo processo ottiene la CPU. Il criterio è noto anche come ShortestRemaining-Time-First (SRTF). La priorita' di un processo e'

inversamente proporzionale al tempo di esecuzione valutato, cioè priorita' = 1 / tempo_esecuzione.

Invecchiamento (Aging): sono utilizzate priorita' dinamiche. Viene aumentata la priorita' di un processo a mano a mano che

invecchia. Questa soluzione si chiama aging, e consente di evitare la starvation (cioe' appunto che un processo "muoia di fame" perche'

mai schedulato). Aumentando la priorita' dei processi nel tempo, prima o poi qualunque processo raggiungera' una priorita' tale che gli

consentira' di essere schedulato. È utile raggruppare i processi in classi di priorità e utilizzare scheduling a priorità tra le classi e

scheduling round robin all'interno di una classe.

RR (Round Robin): si assegna un quanto tempo (time slice) per l'esecuzione di processi, al termine del quale, anche se il processo

non ha ancora terminato l'esecuzione, l'uso della cpu viene dato ad un nuovo processo. La priorità tra i processi è la stessa. La durata del