# Scheduling

Lo scheduler dei processi è il componente del sistema operativo che si occupa di decidere quale processo va mandato in esecuzione e di eseguire (indirettamente) il context switch.
Nell'ambito della multiprogrammazione è pensato per mantenere la CPU occupata il più possibile, ad esempio avviando un processo mentre un altro è in attesa del completamento di un'operazione di I/O.

### Tipi di scheduler
#### Scheduler a breve termine

seleziona il processo da eseguire tra i processi in stato ready. Questo può avvenire
* Con prelazione, se lo scheduler non attende che il processo gli ceda indietro il controllo della CPU.
* Senza prelazione se lo scheduler aspetta che il processo (che deve essere cooperativo) abbia finito di elaborare e gli ceda il controllo.
Il processo selezionato dallo scheduler a breve termine ottiene poi il controllo della CPU grazie al dispatcher. In questo contesto si definisce anche la latenza di dispatch come il tempo necessario a fermare un processo e a riprenderne un altro. Si indica invece con turnaround il tempo totale impiegato per l'esecuzione di un processo.

#### Scheduler a medio termine (o swapper)

Si basa sull'idea che qualche volta può rivelarsi un vantaggio rimuovere un processo dalla memoria, ad esempio per migliorare il process mix o perché si ha la necessità di liberare della memoria.
Togliere e reinserire un processo in memoria prende il nome di swapping.

#### Scheduler a lungo termine

Sceglie quale tra i processi in job queue portare nella ready queue secondo suoi criteri stabiliti.

### Code

Per gestire lo scheduling si utilizzano varie code:
* coda dei job, che contiene tutti i processi del sistema.
* coda dei processi pronti (ready queue), formata da una lista linkata in cui si ha un header che punta al primo PCB della lista, il quale punta al PCB successivo e così via.
* coda del dispositivo: lista dei processi che sono in attesa di un particolare dispositivo di I/O.

## Algoritmi di scheduling

Gli obiettivi di un algoritmo di scheduling possono dipendere dall'ambiente (ad esempio se si ha a che fare con dei sistemi batch oppure con sistemi real-time). In generale un algoritmo di scheduling deve essere equo (cioè deve cercare di dare a tutti i processi lo stesso tempo CPU), deve rispettare le politiche di sistema e deve cercare di mantenere il sistema il più occupato possibile.

### First-Come, First-Served (FCFS)

Si tratta di uno dei più semplici algoritmi di scheduling ed è senza prelazione. I processi vengono assegnati alla CPU nell'ordine in cui essi l'hanno richiesta (si ha una singola ready queue).

### Scheduling a priorità

Ad ogni processo si associa un numero intero che ne indica la priorità. Questo tipo di scheduling può comportare il problema della starvation: un processo a bassa priorità rischia di venir eseguito molto tardi (oppure mai nel peggiore dei casi) se esso incontra in continuazione processi a priorità maggiore. Per evitare questo problema si fa in modo di aumentare la priorità di un processo al passare del tempo (aging).

### Round Robin (RR)

Un processo viene eseguito per un piccolo lasso di tempo (detto quanto), dopodiché viene prelazionato e rimesso nella ready queue. La durata del quanto non deve essere troppo lunga (altrimenti si ritorna a un caso simile al FCFS), né troppo corta (in tal caso si avrebbe overhead troppo alto).

### Shortest Job First (SJF)

Algoritmo di scheduling che pone nella lista di ready i processi in base al loro CPU burst, minore sarà il tempo di burst e prima verrà eseguito dalla CPU.
* Tempo di attesa molto basso.
Può essere:
* Senza prelazione (non-preemptive) nel caso in cui la scelta del processo da eseguire venga fatta non appena il processo precedente ha restituito (volontariamente) il controllo della CPU al sistema operativo.
* Con prelazione (preemptive) nel caso in cui l'aggiunta di un processo alla coda dei processi pronti (ready queue) porti lo scheduler a ricalcolare ogni tempo (previsto) di CPU burst e riassegnare la CPU al processo il cui tempo è il minore di tutti.