Algoritmi di Scheduling della CPU
Come il sistema operativo decide quale processo eseguire quando la CPU è libera. Teoria di 6 algoritmi e simulatore interattivo con animazione passo-passo.
💡 Guida + strumento · Livello intermedio · Configura fino a 5 processi
Quando più processi sono pronti per essere eseguiti ma la CPU può eseguirne uno solo alla volta, il sistema operativo deve decidere chi esegue e quando. Questa decisione è presa dallo scheduler della CPU, seguendo un algoritmo di scheduling.
Ogni processo è descritto da tre dati: il tempo di arrivo (quando diventa pronto), il burst (quanto tempo di CPU richiede in totale) e, per alcuni algoritmi, una priorità (numero più basso = priorità più alta).
Tempo di attesa = tempo di completamento − tempo di arrivo − burst (quanto il processo è rimasto in coda senza essere eseguito).
Tempo di turnaround = tempo di completamento − tempo di arrivo (quanto tempo totale il processo ha impiegato dall'arrivo al completamento, inclusa l'attesa).
Non-preemptive (senza prelazione): una volta che un processo inizia ad eseguire, continua fino al completamento — anche se nel frattempo arriva un processo "migliore" secondo il criterio dell'algoritmo (burst più corto, priorità più alta).
Preemptive (con prelazione): il processo in esecuzione può essere interrotto prima di finire, se un nuovo arrivo ha un titolo più forte secondo lo stesso criterio. Per Round Robin il meccanismo è diverso: l'interruzione non dipende da un arrivo "migliore", ma dallo scadere del quanto di tempo.
La prelazione è quindi una scelta di politica, indipendente dal criterio usato per scegliere: lo dimostra il fatto che "Priorità" compare due volte in questa guida (sezioni 3 e 5) — stesso criterio, comportamento diverso a seconda che sia o meno prelazionabile.
| Algoritmo | Prelazione | Criterio di scelta |
|---|---|---|
| FCFS | No | Ordine di arrivo |
| SJF | No | Burst totale più corto |
| Priorità (senza prelazione) | No | Priorità più alta |
| SRTF | Sì | Tempo rimanente più corto |
| Priorità (con prelazione) | Sì | Priorità più alta (anche durante l'esecuzione) |
| Round Robin | Sì (a tempo) | Turni a rotazione, quanto di tempo fisso |
Il più semplice: i processi vengono eseguiti nell'ordine in cui arrivano, senza interruzioni. Nessuna valutazione di durata o importanza — solo ordine di arrivo.
Esempio: A(arrivo 0, burst 5), B(arrivo 1, burst 3), C(arrivo 2, burst 1).
Un processo lungo arrivato per primo blocca tutti quelli dietro, anche se molto più brevi — qui C aspetta 7 unità per essere eseguito per solo 1.
Non preemptive: una volta scelto, il processo esegue fino al completamento. La scelta avviene solo quando la CPU si libera, tra i processi già arrivati.
Stessi processi di prima — questa volta l'ordine cambia in base al burst, non all'arrivo:
All'istante 0 è arrivato solo A: lo esegue per forza, non c'è ancora nessuna scelta da fare. B e C, arrivati dopo, restano in coda. La vera scelta secondo SJF avviene al tempo 5, quando la CPU si libera e tra i due processi in coda si sceglie quello con il burst più corto: C prima di B.
Minimizza l'attesa media a parità di processi arrivati — ma richiede di conoscere in anticipo la durata di ciascun processo, raramente nota con esattezza in un sistema reale.
SJF assomiglia molto a Priorità senza prelazione (sezione 3): se la priorità di ogni processo viene assegnata in modo inverso al suo burst (burst corto = priorità alta), i due algoritmi producono lo stesso identico risultato. Provalo nello strumento!
Identico a SJF nel meccanismo, ma il criterio di scelta è un valore di priorità assegnato esplicitamente, non il burst. Numero più basso = priorità più alta.
Stessi processi, priorità: A=2, B=1, C=3 (B il più importante):
Anche qui, all'istante 0 è arrivato solo A: lo esegue per forza, indipendentemente dalla sua priorità. La scelta secondo priorità avviene al tempo 5, quando la CPU si libera e tra i due processi in coda si sceglie quello con priorità più alta: B (1) prima di C (3).
Notare la differenza con SJF: qui B passa prima di C nonostante il burst più lungo, perché la sua priorità (1) è più alta di quella di C (3) — priorità e durata sono criteri indipendenti.
Ad ogni nuovo arrivo, si confronta il tempo rimanente del processo in esecuzione con quello del nuovo arrivato: se il nuovo arrivato ha meno lavoro da fare, prelaziona.
All'istante 0 è arrivato solo A, che parte per mancanza di alternative — non perché abbia il tempo rimanente più corto. Da qui in avanti, ogni nuovo arrivo viene confrontato con il tempo rimanente del processo in esecuzione.
Ogni prelazione comporta un cambio di contesto (context switch): qui A viene interrotto due volte prima di poter proseguire. In un sistema reale questo ha un costo in tempo non nullo, ignorato nei nostri calcoli semplificati.
Stessa relazione di SJF: SRTF coincide con Priorità con prelazione (sezione 5) quando la priorità è assegnata in modo inverso al burst totale.
Stesso meccanismo di SRTF, ma il confronto è sulla priorità dichiarata, non sul tempo rimanente. A parità di priorità, il processo in esecuzione NON viene interrotto.
Priorità: A=2, B=1, C=3 (C il meno importante):
All'istante 0 è arrivato solo A, che parte per mancanza di alternative — non per la sua priorità. Al tempo 1 arriva B con priorità più alta (1) e lo prelaziona immediatamente.
C arriva al tempo 2 con un burst di sole 1 unità, ma essendo il meno prioritario deve aspettare fino al tempo 8 per essere eseguito — bloccato da A e B che arrivano dopo di lui ma con priorità migliore. Se continuassero ad arrivare processi più prioritari, C potrebbe non essere mai eseguito: è il problema della starvation.
Non si basa né su priorità né su durata: ogni processo, a turno, riceve al massimo un quanto di tempo (TS). Se non ha finito, torna in fondo alla coda. È l'unico algoritmo tra i 6 pensato per l'equità, non per la velocità media.
Stessi 3 processi, quanto = 2:
Nessun processo aspetta indefinitamente: ognuno riceve comunque dei turni regolari. Ottimo per sistemi interattivi (time-sharing), dove la reattività percepita conta più della velocità media.
Non privilegia chi avrebbe più bisogno di essere veloce: un quanto troppo piccolo aumenta l'overhead dei cambi di contesto, uno troppo grande fa degenerare Round Robin in un quasi-FCFS.
| Processo | Arrivo | Burst | Priorità |
|---|