Schedulazione dei processi — Concetti di sistemi operativi

La schedulazione dei processi è la decisione del sistema operativo su quale processo pronto riceverà la CPU per primo. In parole semplici, è la regola che decide chi viene eseguito adesso e chi deve aspettare. Questa regola cambia il tempo di attesa, il tempo di risposta, l’equità e il throughput complessivo.

La schedulazione dei processi è importante perché lo stesso insieme di processi può terminare in un ordine molto diverso con FCFS, SJF o round robin. Se capisci questa idea, la maggior parte degli esempi da manuale diventa molto più facile da leggere.

Che cosa significa schedulazione dei processi nei sistemi operativi

Nel modello classico dei sistemi operativi, i processi passano tra stati come pronto, in esecuzione e in attesa. Lo scheduler sceglie tra i processi pronti.

Per questo la schedulazione dei processi viene spesso chiamata anche schedulazione della CPU. Non crea nuovo lavoro. Decide l’ordine in cui il lavoro in attesa riceve tempo di CPU.

Nei sistemi moderni, il kernel spesso schedula direttamente i thread, ma il termine classico "schedulazione dei processi" resta ancora quello standard nell’insegnamento.

Che cosa cerca di ottimizzare uno scheduler

Uno scheduler di solito cerca di bilanciare diversi obiettivi:

• basso tempo di attesa
• risposta rapida per i compiti interattivi
• buon throughput
• equità
• comportamento prevedibile

Questi obiettivi possono entrare in conflitto. Una politica che riduce il tempo medio di attesa in un esempio semplificato può comunque sembrare poco equa nella pratica, e una politica equa di condivisione del tempo può ritardare il completamento di un lavoro breve.

Schedulazione prelativa e non prelativa

Uno scheduler non prelativo lascia che un processo in esecuzione mantenga la CPU finché termina il suo burst di CPU o si blocca. First-come, first-served è l’esempio standard.

Uno scheduler prelativo può interrompere un processo in esecuzione e assegnare la CPU a un altro. Round robin e molti scheduler a priorità fanno proprio questo.

Questa distinzione è importante perché il tempo di risposta spesso migliora quando il sistema può interrompere lavori lunghi.

Algoritmi comuni di schedulazione dei processi

First-Come, First-Served

First-come, first-served, o FCFS, esegue i processi nell’ordine di arrivo. È facile da capire e semplice da implementare, ma un lavoro lungo in testa alla coda può costringere tutti i lavori brevi dietro di lui ad aspettare.

Shortest Job First

Shortest job first, o SJF, preferisce il processo con il burst di CPU più piccolo. In un contesto semplificato in cui la durata dei burst è nota con precisione, può ridurre il tempo medio di attesa. Nei sistemi reali, però, questa durata di solito deve essere stimata.

Round Robin

Round robin assegna a ogni processo pronto una piccola fetta di tempo chiamata quantum. Se il processo non termina entro quella fetta, torna nella coda dei pronti. Questo di solito migliora l’equità e la reattività nei carichi di lavoro interattivi.

Schedulazione a priorità

La schedulazione a priorità esegue per primo il processo pronto con priorità più alta. Può essere utile quando alcuni compiti contano più di altri, ma se i compiti a bassa priorità aspettano troppo a lungo, il rischio è la starvation.

Un esempio svolto con il tempo di attesa

Supponiamo che tre processi arrivino tutti al tempo $0$ e che ciascuno richieda solo tempo di CPU:

• $P_1$: $6\ \mathrm{ms}$
• $P_2$: $2\ \mathrm{ms}$
• $P_3$: $1\ \mathrm{ms}$

Assumi che:

• ci sia una sola CPU
• non ci sia blocco per I/O
• il costo del context switch sia ignorato

In queste condizioni, il tempo di attesa è il tempo trascorso nella coda dei pronti prima che un processo venga eseguito. Il turnaround time è

$$\text{turnaround time} = \text{completion time} - \text{arrival time}$$

FCFS

Se si usa FCFS, l’ordine è $P_1 \rightarrow P_2 \rightarrow P_3$.

Timeline:

$$0 \to 6: P_1,\qquad 6 \to 8: P_2,\qquad 8 \to 9: P_3$$

Tempi di attesa:

• $P_1 = 0$
• $P_2 = 6$
• $P_3 = 8$

Tempo medio di attesa:

$$\frac{0 + 6 + 8}{3} = \frac{14}{3}\ \mathrm{ms}$$

SJF

Se si usa SJF non prelativo, l’ordine è $P_3 \rightarrow P_2 \rightarrow P_1$.

Timeline:

$$0 \to 1: P_3,\qquad 1 \to 3: P_2,\qquad 3 \to 9: P_1$$

Tempi di attesa:

• $P_3 = 0$
• $P_2 = 1$
• $P_1 = 3$

Tempo medio di attesa:

$$\frac{0 + 1 + 3}{3} = \frac{4}{3}\ \mathrm{ms}$$

Questo esempio mostra l’intuizione principale. Il carico di lavoro non è cambiato, ma la regola ha cambiato il risultato. Qui, SJF dà un tempo medio di attesa più basso perché i lavori brevi non restano bloccati dietro a quello lungo.

Questo non significa che SJF sia sempre la scelta migliore nel mondo reale. Significa che, con le ipotesi di questo esempio, l’ordine di schedulazione conta molto.

L’intuizione da ricordare

Pensa alla schedulazione dei processi come alla disciplina della coda per la CPU. La coda dei pronti può contenere gli stessi lavori, ma la regola con cui quella coda viene servita cambia ciò che gli utenti percepiscono.

Se ti interessa soprattutto una risposta iniziale rapida, potresti preferire una condivisione frequente. Se ti interessa soprattutto completare rapidamente molti lavori brevi, potresti preferire una politica che favorisca burst brevi. Se ti interessa una temporizzazione rigorosa, potresti aver bisogno di uno scheduler diverso.

Errori comuni nei problemi di schedulazione

Supporre che una politica sia sempre la migliore

Non esiste un unico vincitore per ogni carico di lavoro. Una politica può sembrare eccellente per il tempo medio di attesa e comunque essere scarsa per equità o rispetto delle scadenze.

Confondere tempo di attesa, tempo di risposta e turnaround time

Queste metriche sono collegate, ma non identiche. In particolare, il tempo di risposta di solito indica il tempo fino al primo servizio di CPU o alla prima risposta visibile, mentre il turnaround time misura l’intero lavoro dall’arrivo al completamento.

Ignorare la condizione dietro la formula

Le metriche hanno senso solo sotto le ipotesi dichiarate. Se un problema include blocco per I/O, tempi di arrivo diversi o overhead di context switch, la timeline e i risultati cambiano.

Dimenticare se la politica è prelativa

SJF e shortest remaining time first non sono la stessa regola. Anche la schedulazione a priorità si comporta in modo diverso a seconda che un lavoro con priorità più alta possa interrompere quello corrente.

Dove si usa la schedulazione dei processi

La schedulazione dei processi è importante ovunque un sistema operativo debba condividere il tempo di CPU:

• sistemi desktop e mobili che richiedono app reattive
• server che gestiscono molte richieste
• sistemi batch che puntano al throughput
• sistemi real-time che richiedono garanzie temporali

Gli scheduler reali sono di solito più complessi delle versioni da manuale, ma gli stessi compromessi continuano a comparire.

Prova una tua variante

Modifica l’esempio in modo che $P_2$ arrivi più tardi, oppure sostituisci FCFS con round robin usando un quantum di $2\ \mathrm{ms}$, e osserva come cambia il pattern di attesa. Se vuoi fare un passo in più dopo averlo risolto a mano, prova la tua variante in GPAI Solver e confronta la timeline che avevi previsto con quella calcolata.