CPU Scheduling: algoritmi e pttimizzazione nei sistemi operativi

CPU.

Non si occupa di performance istantanee, ma della stabilità e performance

complessiva del sistema a lungo termine, mantenendo un mix equilibrato di processi.

MIDDLE-TERME SCHEDULER

lo scheduler a medio termine è il "vigile" che gestisce il traffico interno,

sfoltendolo quando c'è troppa congestione.

Il suo compito principale è regolare dinamicamente il grado di

multiprogrammazione (il numero di processi in memoria) per evitare il degrado

delle prestazioni, in particolare il trashing.

Mentre il Job Scheduler decide solo chi entra, il Middle-term Scheduler può anche

decidere di "sospendere" temporaneamente chi è già dentro. Lo fa attraverso due

operazioni complementari, note come swapping.

1. Swap Out (Scarica dalla memoria)

Quando avviene? Quando il sistema rileva che il grado di

 multiprogrammazione è troppo elevato e c'è il rischio di trashing (troppi

processi competono per una memoria insufficiente).

Cosa fa? Seleziona uno o più processi (spesso quelli bloccati in attesa o a bassa

 priorità) e li "congela". Li rimuove temporaneamente dalla memoria RAM e salva

il loro stato completo su disco.

Transizione di stato: Come mostra il secondo diagramma, un processo può

 passare dallo stato running o waiting a uno stato di "sospeso" (nel primo

diagramma, partially executed swapped-out processes). Il suo stato logico passa

a wait (in attesa di essere ricaricato).

2. Swap In (Ricarica in memoria)

Quando avviene? Quando il carico del sistema diminuisce (es. perché altri

 processi sono terminati) e ci sono di nuovo abbastanza risorse disponibili.

Cosa fa? Seleziona uno dei processi che erano stati precedentemente

 "congelati" su disco e lo ricarica in memoria.

Transizione di stato: Il processo viene reinserito nella ready queue (coda dei

 pronti) e il suo stato passa da wait (in attesa di essere ricaricato) a ready. Da

questo momento, torna a competere normalmente per l'accesso alla CPU.

I processi circolano

normalmente tra ready

queue, CPU, e le I/O

waiting queues. Quando

necessario, lo scheduler

a medio termine

interviene, prendendo

un processo da una di queste code e spostandolo nell'area swapped-out processes su

disco. Successivamente, lo riprende da lì e lo reinserisce nella ready queue.

CPU SCHEDULER

Lo CPU Scheduler è il componente che decide a chi tocca adesso.

il suo compito è selezionare un processo tra tutti quelli presenti nella ready queue

(la coda dei pronti in memoria) e decidere di allocargli la CPU.

Lo scheduler non è sempre attivo, ma entra in gioco in momenti specifici, quando

avviene un cambio di stato di un processo:

running waiting

- Un processo passa da a (es. fa una richiesta di I/O).” Il

processo che stava usando la CPU fa una richiesta di I/O (es. legge un file). Ora

è bloccato e non può più usare la CPU. La CPU è libera! Lo scheduler deve

guardare la ready queue e scegliere un nuovo processo da mandare in running.”

running ready

- Un processo passa da a (es. scade il suo quanto di tempo, Il

processo attuale è stato messo in panchina. L'allenatore deve decidere chi far

giocare adesso. Potrebbe scegliere lo stesso processo se ha ancora la priorità

più alta, o potrebbe sceglierne un altro).

waiting ready

- Un processo passa da a (es. la sua operazione di I/O è

terminata). “Un processo che era bloccato in attesa di un I/O ha finito Ora è

pronto a usare di nuovo la CPU e viene messo nella ready queue Un nuovo

giocatore è tornato disponibile in panchina. L'allenatore deve chiedersi: "Questo

giocatore appena tornato è così importante da dover sostituire subito quello che

sta giocando adesso?". Se il nuovo processo ha una priorità più alta di quello in

running, lo scheduler potrebbe decidere di effettuare un cambio.”

- Un processo termina (exit). “Il processo che stava usando la CPU ha finito

tutto il suo lavoro. Come nel caso 1, la CPU è libera. Lo scheduler deve

scegliere un nuovo processo dalla ready queue.”

La differenza fondamentale tra gli algoritmi di scheduling si basa su quali di questi

quattro momenti vengono sfruttati:

Scheduling Non-Preemptive (senza diritto di prelazione):

 Come funziona: Una volta che la CPU viene assegnata a un processo,

o nessuno può togliergliela. Il processo la tiene finché non la rilascia

volontariamente, o perché termina (caso 4) o perché si mette in attesa

per l'I/O (caso 1).

Caratteristica: È un approccio più semplice, ma meno reattivo. Un

o processo lungo può monopolizzare la CPU.

Scheduling Preemptive (con diritto di prelazione):

 Come funziona: Il sistema operativo ha il potere di interrompere un

o processo e sottrargli la CPU con la forza, anche se questo non ha

ancora finito il suo lavoro.

Caratteristica: Questo tipo di scheduling agisce in tutti e quattro i casi.

o È fondamentale per garantire la reattività e l'interattività dei sistemi

moderni (come Windows, macOS, Linux, Android), perché impedisce a un

singolo processo di bloccare tutti gli altri.

Se lo scheduler è il "cervello" che prende la decisione, il Dispatcher è il "braccio" che

la mette in pratica.

Funzione principale: Il Dispatcher è il modulo che riceve il nome del processo

 scelto dallo scheduler e si occupa di effettuare materialmente il cambio di

contesto per dargli il controllo della CPU.

Cosa fa nel dettaglio:

 1. Commutazione di contesto (Context Switching): Salva lo stato del

processo che stava usando la CPU e carica lo stato del nuovo processo da

eseguire.

2. Passaggio alla modalità utente: Cambia la modalità del processore da

"kernel mode" (in cui operano scheduler e dispatcher) a "user mode".

3. Salto all'istruzione corretta: Imposta il program counter della CPU

all'indirizzo dell'istruzione da cui il nuovo processo deve ripartire.

Latenza di Dispatch (Dispatch Latency): È il tempo che intercorre tra il

 momento in cui lo scheduler decide di fermare un processo e il momento in cui

il nuovo processo inizia effettivamente la sua esecuzione. Questo tempo

rappresenta un "overhead" (un costo operativo) e deve essere il più basso

possibile.

CPU SCHEDULING NEI SISTEMI

MONOPROCESSORE

I cinque principali criteri di performance utilizzati per valutare e confrontare

l'efficacia dei diversi algoritmi di scheduling. Un buon scheduler cerca di trovare il

miglior equilibrio possibile tra questi indicatori, che spesso sono in conflitto tra loro.

Vediamoli uno per uno.

1. Utilizzo della CPU (CPU Utilization): Vogliamo che il nostro processore, che è il

motore del computer, lavori il più possibile e non stia mai fermo a non fare nulla. Da

massimizzare.

2. Produttività (Throughput): Il numero di processi che vengono completati in una data

unità di tempo. Un throughput elevato significa che il sistema è efficiente e smaltisce

molti task. Da massimizzare.

3. Tempo di Completamento (Turnaround Time): L'intervallo di tempo totale che

intercorre tra il momento in cui un processo viene sottomesso al sistema e il momento

in cui termina completamente. Un tempo di completamento basso indica che i singoli

processi vengono gestiti rapidamente. Da minimizzare

4. Tempo di attesa: La somma di tutti i periodi di tempo che un processo passa nella

ready queue, in attesa del suo turno per usare la CPU. È una misura diretta

dell'efficienza dello scheduler nel non far aspettare inutilmente i processi pronti. Da

minimizzare

5. Tempo di risposta: tempo che passa da quando un utente fa una richiesta (es. un

clic) a quando il sistema produce la prima risposta visibile, non necessariamente

l'output finale. Questo è il criterio più importante per i sistemi interattivi, perché

misura la fluidità e la reattività dell'esperienza utente. Da minimizzare.

INIZIAMO CON GLI ALGORITMI

FCFS: l primo che arriva, viene servito per primo è una politica di scheduling non-

preemptive. I processi vengono serviti esattamente nell'ordine in cui arrivano nella

ready queue, come persone in fila alla posta. Una volta che un processo ottiene la

CPU, la tiene finché non ha terminato il suo CPU burst.

Ma cambiando i processi di arrivo

Confrontando i due scenari, il tempo medio di attesa è passato da 17 ms a 3 ms, un

miglioramento enorme. Questo evidenzia il difetto principale dell'algoritmo FCFS:

l'Effetto Convoglio (Convoy Effect).

L'effetto convoglio si verifica quando processi brevi sono costretti ad attendere

in coda dietro a un processo molto lungo. Questo degrada notevolmente le

prestazioni medie del sistema, in particolare il tempo di attesa medio.

SJF: Shortest-Job-First non si basa sull'ordine di arrivo ma sulla durata del lavoro da



compiere. L'idea è quella di dare la precedenza ai processi più brevi per "toglierli di

mezzo" rapidamente, migliorando così i tempi medi di attesa.

Ad ogni processo viene associata la lunghezza del suo prossimo ciclo di CPU. Lo

scheduler sceglie il processo con il burst più breve e gli assegna la CPU.

L'algoritmo SJF è teoricamente ottimale, in quanto è dimostrato che produce il

tempo medio di attesa più basso possibile per un dato insieme di processi. La sua

grande debolezza è che richiede di conoscere in anticipo la durata del prossimo CPU

burst, cosa impossibile da sapere con certezza. Nella pratica si usano tecniche di stima

basate sul comportamento passato del processo.

L'algoritmo esiste in due versioni

Non-Preemptive SJF

una volta che un processo ottiene la CPU, la tiene finché non ha completato il suo

burst, anche se nel frattempo arriva un processo più breve. Tempo 0: L'unico

processo nella ready

queue è P1. Parte P1 e,

siccome è non-

preemptive, continuerà

a girare per tutti i suoi

7ms.

Tempo 2: Arriva P2

(burst=4). Va in coda.

Tempo 4: Arriva P3

(burst=1). Va in coda.

Tempo 5: Arriva P4

(burst=4). Va in coda.

Tempo 7: P1 finisce. Lo scheduler ora guarda la ready queue, che contiene {P2(4),

P3(1), P4(4)}. Sceglie il processo con il burst più breve: P3. Parte P3.

Tempo 8: P3 finisce. La ready queue ora contiene {P2(4), P4(4)}. I due processi hanno

la stessa durata. In caso di parità, si usa la politica FCFS (First-Come, First-Served).

Poiché P2 è arrivato prima di P4, parte P2.

Tempo 12: P2 finisce. L'unico processo rimasto è P4, che parte.

Tempo 16: P4 finisce