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.