Scheduling

Lo scheduler del S.O. ha il compito di decidere quale processo eseguire e per quanto tempo.

I criteri di scheduling si basano sul tipo di processo, tra cui:

Processor-bound: usa tutto il tempo CPU disponibile
I/O-bound: genera velocemente richieste I/O e lascia il processore
Batch: lavorano senza interazione dell'utente
Interattivi: richiedono frequenti input dell'utente

e ha come obbiettivi,

per sistemi generali: l'equità del tempo CPU per ogni processo
per sistemi batch: massimizzare il throughput e l'uso CPU
per sistemi interattivi: minimizzare il tempo di risposta
per sistemi real-time: rispettare le scadenze

Priorità

Ad ogni processo può essere assegnata priorità statica, che ha basso overhead perchè non cambia nel tempo, oppure dinamica, per aumentare la reazione in cambio di maggior overhead.

Nel caso siano presenti più utenti si usa una politica di fair share, dove i processi di ogni utente rientrano in un determinato gruppo, ognuno dei quali avrà percentuali diverse di risorse utilizzabili.

Livelli

Lo scheduler può essere suddiviso in livelli, per la scelta di quali processi eseguire e quali no:

Alto: sceglie i job di cui cominciare lo scheduling
Intermedio: determina quali processi sospendere dall'uso della CPU
Basso: assegna le priorità ed effettua dispatch e timeout

Algoritmi

Ogni algoritmo di scheduling gestisce quando e quanto eseguire ogni processo in modo differente.

Lo scheduling può avvenire senza prelazione, eseguendo fino al completamento (bloccando altri processi):

First In First Out (FIFO, o First Come First Serve)

La scelta di quale processo eseguire avviene sequenzialmente in base al suo tempo di arrivo.

Per esempio, dati i processi $P_{1} = 10 us$ , $P_{2} = 1000 us$ e $P_{3} = 5 us$ il loro tempo di risposta media sarà $T_{m} = \frac{10 us + 1010 us + 1015 us}{3} = \frac{2035 us}{3} \approx 678 us$ .
Shortest Job First (SJF)

Migliora il FIFO scegliendo il processo con il minimo tempo stimato, che può essere però inaccurato.

Dato l'esempio precedente, la risposta media sarà $T_{m} = \frac{5 us + 15 us + 1015 us}{3} = \frac{1035 us}{3} = 345 us$ .
Highest Response Ratio Next (HRRN)

Estende il SJF tenendo conto anche del tempo di attesa, per cui più tempo viene eseguito più la priorità si abbassa e più tempo attende più si alza.

Altrimenti può essere con prelazione, per migliorare il tempo di risposta (e.g. nei sistemi interattivi):

Shortest Remaining Time First (SRT)

Estende il SJF causando il prelascio dei processi in esecuzione quando ne è in arrivo uno più corto.

Migliora il tempo di risposta medio, ma aumenta il tempo dei processi già lunghi e può anche aumentare l'overhead se avvengono cambi di contesto per processi corti o su processi quasi finiti.
Round Robin (RR)

Comincia come il FIFO, ma prelascia il processo dopo un quanto di tempo, mettendolo poi per ultimo.

La dimensione del quanto va bilanciata, perchè se è troppo piccola il cambio di contesto occupa più tempo che l'esecuzione mentre se è troppo grande la reattività del sistema si riduce.

Idealmente con $n \to \infty$ processi il tempo per tornare ad eseguire il primo sarà $T \to \infty$ , ma dato che la memoria è finita, $n \leq M \in N$ e quindi sarà possibile stimare il massimo tempo richiesto.
Priority

Consiste nell'assegnare ad ogni processo una classe di priorità, che può essere fissa o variabile (e.g. in base alla dimensione dell'ultimo quanto assegnato).

Un'implementazione si basa sull'utilizzo di istanze di round robin separate su ogni classe di processi. Se però i processi ad alta priorità non terminano, avviene l'attesa infinita di quelli a bassa priorità.
Selfish Round Robin (SRR)

Gestisce i processi esistenti con round robin e aumenta la priorità dei processi nuovi con l'età fino ad entrare in coda. Per favorire i processi importanti sarà sufficiente aumentare la velocità di crescita.

In questo modo si evita di fermare i processi più anziani troppo a lungo.

Code multilivello

Un'alternativa agli algoritmi precedenti sono le code multilivello, in cui i processi corti terminano mentre quelli più lunghi scalano di livello, su ognuno dei quali ci saranno tempi di prelazione più lunghi.

Lo scheduler passerà all'esecuzione dei livelli inferiori solamente se quelli superiori si svuotano. All'arrivo di un nuovo processo in un livello superiore invece, verrà forzato il prelascio di quello nel livello inferiore.

Dato che l'algoritmo si adatta ai processi, avrà una migliore sensibilità a costo di un overhead maggiore.

Real-time

Nei sistemi con processi con vincoli temporali si usa lo scheduling a scadenza, che richiede di conoscere i requisiti dei processi per eseguire prima quelli con scadenza più vicina, cosa che comporta overhead.

Se i vincoli temporali non sono garantiti (e.g. riproduzione multimediale) si tratta di soft real-time scheduling, altrimenti (e.g. controllo del traffico aereo) si tratta di hard real-time scheduling.

Nel caso il sistema usi eventi periodici, è richiesto che di $n$ processi: $i = 1 \sum n \frac{C _{i}}{T _{i}} \leq 1$ dove $C_{i}$ è il tempo di esecuzione dell' $i$ -esimo processo e $T_{i}$ il suo periodo che corrisponde alla sua deadline.

Durante l'esecuzione l'algoritmo di scheduling può essere:

Statico

Non adegua le priorità alle condizioni di esecuzione, ed è quindi pratico per i sistemi con condizioni che cambiano raramente, come per l'hard real-time scheduling.

Tra gli algoritmi di scheduling ci sono:
- Rate monotonic (RM): sfrutta il RR, aumentando la priorità con la frequenza di esecuzione
- Deadline rate monotonic: per i processi la cui deadline non coincide con il periodo
Dinamico

Adatta le priorità col tempo, assicurandosi che l'overhead risultante non porti a scadenze mancate.

In base alle deadline si hanno:
- Earliest deadline first (EDF): sceglie il processo con la scadenza più vicina dopo il prelascio
- Least laxity first (LLF): tipo EDF ma in base al tempo che rimarrà, dopo l'esecuzione, alla deadline