Scheduling della CPU - FCFS, SJF, priorità e round robin

In un sistema multiprogrammato più processi sono pronti nello stesso momento ma c'è una sola CPU (o poche): lo scheduling decide chi la usa. Questa nota presenta i criteri e gli algoritmi classici, ognuno con un esempio svolto passo per passo (in diagrammi di Gantt scritti come tabelle). Il caso di più core e dei sistemi con scadenze (real-time) è in Scheduling multiprocessore e real-timeNei sistemi real-time conta la scadenza: si misurano latenza di interrupt e latenza di dispatch; i sistemi soft real-time danno priorità ai compiti critici senza garanzie, quelli hard devono rispettare le scadenze; per compiti periodici (burst t, scadenza d, periodo p, con 0 <= t <= d <= p) l'utilizzo è la somma di t/p: Rate Monotonic (priorità fissa, minore il periodo maggiore la priorità) garantisce le scadenze se l'utilizzo non supera N(2^(1/N)-1) (83% per due compiti), Earliest Deadline First (priorità dinamica, scadenza più vicina) le garantisce se l'utilizzo è sotto il 100%; la ripartizione proporzionale assegna T quote con controllo di ammissione; con più processori si hanno code comuni o private (SMP), core con più thread hardware, bilanciamento del carico (push e pull migration), affinità al processore (soft e hard), scheduling NUMA-aware; Linux usa CFS/EEVDF con domini di scheduling, Windows 32 livelli di priorità.Scheduling multiprocessore e real-time →. Gli stati e le code dei processi sono in Processi - stati, PCB, creazione con fork ed execUn processo è un programma in esecuzione (entità attiva) con codice (text), dati globali, heap, stack e lo stato dell'esecuzione; il kernel lo descrive con il PCB (Process Control Block: stato, program counter, registri, informazioni di scheduling, memoria, accounting, file aperti, in Linux la struct task_struct) e passa da un processo all'altro con il context switch (puro overhead); gli stati sono new, ready, running, waiting, terminated, con una ready queue e varie wait queue; in UNIX fork() crea un figlio copia del padre (restituisce 0 al figlio e il pid del figlio al padre), exec() sostituisce il programma del figlio, wait()/waitpid() raccoglie lo stato di uscita: senza di essa un figlio terminato è uno zombie, un figlio il cui padre è morto è un orfano adottato da init/systemd; i processi cooperanti comunicano con memoria condivisa (POSIX shm) o scambio di messaggi (diretto o indiretto, sincrono o asincrono, buffer a capacità zero, limitata, illimitata) e con pipe ordinarie (padre-figlio, unidirezionali) e named pipe (FIFO).Processi - stati, PCB, creazione con fork ed exec →; i problemi d'esame con numeri sono raccolti negli esercizi elencati in fondo.

Il ciclo CPU-I/O

L'esecuzione di un processo alterna burst di CPU (periodi di calcolo) e burst di I/O (periodi di attesa del dispositivo). L'istogramma dei burst di CPU ha tanti burst brevi e pochi lunghi: i processi I/O-bound hanno la curva spostata verso i burst brevi, quelli CPU-bound verso i lunghi. Con la multiprogrammazione, quando un processo entra in un burst di I/O la CPU può servire un altro: è questa sovrapposizione che dà la massima utilizzazione della CPU.

Scheduler e dispatcher

Lo scheduler della CPU sceglie, tra i processi nella ready queue, quello a cui assegnare un core. Le decisioni si prendono in quattro situazioni:

Se le decisioni sono prese solo nei casi 1 e 4 lo scheduling è non preemptive (senza prelazione, non-preemptive): una volta assegnata la CPU, il processo la tiene finché la rilascia terminando o passando in attesa. Se si decide anche nei casi 2 e 3 è preemptive (con prelazione): il sistema può togliere la CPU a un processo in esecuzione. Praticamente tutti i sistemi attuali (Windows, macOS, Linux, UNIX) sono preemptive.

La prelazione ha un costo: se due processi modificano dati comuni e uno viene interrotto a metà, l'altro vede i dati in uno stato incoerente (race condition, v. Sincronizzazione - sezione critica, race condition e mutexQuando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine degli accessi si ha una race condition (esempio: counter++ e counter-- sono tre istruzioni macchina ciascuna, e interleaving diversi danno 4, 5 o 6 partendo da 5); il problema della sezione critica chiede un protocollo (entry section, sezione critica, exit section, remainder section) che garantisca mutua esclusione, progresso e attesa limitata; disabilitare gli interrupt non scala sui multiprocessori, l'alternanza stretta con turn viola il progresso, la soluzione di Peterson (flag[2] e turn) soddisfa i tre requisiti ma può fallire su hardware moderno per il riordino delle istruzioni, per cui servono barriere di memoria; l'hardware offre test_and_set e compare_and_swap (atomiche) e variabili atomiche; il mutex lock (acquire/release, in POSIX pthread_mutex_t) è lo strumento di alto livello, con attesa attiva se è uno spinlock oppure con sospensione del thread se è un mutex di sistema; bloccare due volte lo stesso mutex senza sbloccarlo causa deadlock.Sincronizzazione - sezione critica, race condition e mutex →); inoltre preempire troppo spesso aumenta la latenza totale di dispatch.

Il dispatcher è il modulo che dà il controllo della CPU al processo scelto: cambia il contesto, passa in modalità utente e salta al punto giusto del programma. La latenza di dispatch è il tempo che passa tra l'arresto di un processo e l'avvio dell'altro.

Criteri di scheduling

Per processi con un solo burst di CPU: attesa $=$ turnaround $-$ durata del burst. Il turnaround normalizzato è turnaround / burst.

FCFS - First Come, First Served

Il primo processo arrivato nella ready queue è il primo a ricevere la CPU. È non preemptive e si realizza con una coda FIFO.

Esempio: arrivano a $t=0$, nell'ordine $P_1, P_2, P_3$ con burst 24, 3, 3.

Attese: $P_1 = 0$, $P_2 = 24$, $P_3 = 27$; media $= (0+24+27)/3 = 17$. Se arrivano nell'ordine $P_2, P_3, P_1$:

Attese: $P_2=0$, $P_3=3$, $P_1=6$; media $= 3$. La differenza si chiama effetto convoglio (convoy effect): i processi brevi restano bloccati dietro uno lungo (per esempio un processo CPU-bound davanti a molti I/O-bound).

SJF - Shortest Job First

Si dà la CPU al processo con il burst di CPU successivo più breve. Se due hanno lo stesso burst si usa FCFS. È non preemptive. È ottimo: dà il minimo tempo di attesa medio per un insieme di processi con burst noti (portare avanti un processo breve riduce l'attesa dei brevi più di quanto aumenti quella del lungo).

Esempio con arrivi diversi: $P_1$ (arrivo 0, burst 8), $P_2$ (1, 4), $P_3$ (2, 9), $P_4$ (3, 5). A $t=0$ c'è solo $P_1$, che parte e non viene interrotto. A $t=8$ sono pronti $P_2$ (4), $P_3$ (9), $P_4$ (5): si sceglie $P_2$.

Attese $=$ inizio $-$ arrivo: $P_1 = 0$, $P_2 = 8-1 = 7$, $P_4 = 12-3 = 9$, $P_3 = 17-2 = 15$; media $= 31/4 = 7{,}75$.

Il problema: il prossimo burst non si conosce. Si può far indicare all'utente, oppure stimarlo dai burst precedenti con una media esponenziale.

Stima del prossimo burst

Definizione (media esponenziale). Siano $t_n$ la lunghezza effettiva dell'$n$-esimo burst e $\tau_n$ la stima. La stima successiva è $$\tau_{n+1} = \alpha\, t_n + (1-\alpha)\,\tau_n, \qquad 0 \le \alpha \le 1.$$

Espandendo, ogni burst passato pesa meno del precedente: $\tau_{n+1} = \alpha t_n + (1-\alpha)\alpha t_{n-1} + \dots + (1-\alpha)^{n+1}\tau_0$. Casi limite: $\alpha = 0$ dà $\tau_{n+1} = \tau_0$ (la storia recente non conta); $\alpha = 1$ dà $\tau_{n+1} = t_n$ (conta solo l'ultimo burst). Di solito $\alpha = 0{,}5$, cioè $\tau_{n+1} = (t_n + \tau_n)/2$.

Esempio con $\tau_0 = 10$ e $\alpha = 0{,}5$:

Per esempio $\tau_1 = 0{,}5\cdot 6 + 0{,}5\cdot 10 = 8$ e $\tau_5 = 0{,}5\cdot 13 + 0{,}5\cdot 5 = 9$: la stima segue i burst con un certo ritardo.

SRTF - Shortest Remaining Time First

È la versione preemptive di SJF: ogni volta che un nuovo processo entra nella ready queue si riconfronta il suo burst con il tempo rimanente del processo in esecuzione; se è minore, lo sostituisce. Stesso esempio di prima ($P_1$: 0, 8; $P_2$: 1, 4; $P_3$: 2, 9; $P_4$: 3, 5):

• a $t=1$ arriva $P_2$ con burst 4 < rimanente di $P_1$ (7): prelazione;
• a $t=2$ arriva $P_3$ (9) e a $t=3$ arriva $P_4$ (5): nessuno batte il rimanente di $P_2$ (2 e 1);
• a $t=5$ $P_2$ finisce; tra $P_1$ (rimanente 7), $P_3$ (9), $P_4$ (5) vince $P_4$; poi $P_1$ e $P_3$.

Attese $=$ turnaround $-$ burst: $P_2 = 4-4 = 0$, $P_4 = 7-5 = 2$, $P_1 = 17-8 = 9$, $P_3 = 24-9 = 15$; media $= 26/4 = 6{,}5$, meglio dei 7,75 di SJF non preemptive.

Round Robin

Ogni processo riceve la CPU per un piccolo intervallo, il quanto di tempo (time quantum) $q$, di solito 10-100 ms; scaduto, viene prelazionato e messo in fondo alla ready queue. Si usa un interrupt del timer per far partire il processo successivo. Con $n$ processi pronti nessuno attende più di $(n-1)\,q$ unità di tempo prima del turno. Se $q$ è molto grande RR si riduce a FCFS; se è molto piccolo il cambio di contesto (meno di 10 $\mu$s, contro $q$ di 10-100 ms) pesa troppo: $q$ deve essere grande rispetto al tempo di cambio di contesto.

Esempio con $q = 4$, tutti arrivati a $t=0$: $P_1$ burst 24, $P_2$ burst 3, $P_3$ burst 3.

$P_2$ finisce a 7 (turnaround 7), $P_3$ a 10, $P_1$ a 30. Attese: $P_1 = 30 - 24 = 6$, $P_2 = 7 - 3 = 4$, $P_3 = 10 - 3 = 7$; media $= 17/3 = 5{,}67$ (in FCFS sarebbe 17, in SJF 3). Il turnaround medio è $(30 + 7 + 10)/3 = 15{,}67$.

Rispetto a SJF, RR ha di solito un turnaround medio maggiore ma una risposta migliore.

Convenzione sugli arrivi simultanei. Quando un processo finisce il quanto nello stesso istante in cui ne arriva un altro, bisogna dire chi entra prima in coda. Le soluzioni del corso non usano sempre la stessa regola: nell'esercizio 31 il processo prelazionato entra prima del nuovo arrivato (Esercizio - Round robin con arrivi e conteggio dei processi in coda (eserciziario, esercizio 31), dove le due convenzioni danno risultati diversi), nell'esercizio 61 il nuovo arrivato entra prima (Esercizio - Round robin con due quanti di tempo (eserciziario, esercizio 61)). In un compito si segue la regola dichiarata dal testo, o si dichiara la propria.

Scheduling a priorità

A ogni processo è associata una priorità (un intero); la CPU va al processo con la priorità più alta (nelle slide: il numero più piccolo, ma alcuni esercizi usano il numero più grande: si controlla sempre la convenzione). Può essere preemptive o no. SJF è uno scheduling a priorità in cui la priorità è l'inverso del burst.

Problema: starvation (starvation, attesa indefinita): i processi a bassa priorità possono non eseguire mai. Soluzione: aging (invecchiamento): col passare del tempo si aumenta la priorità del processo in attesa.

Esempio (priorità più piccola = più alta, tutti arrivati a 0): $P_1$ (burst 10, priorità 3), $P_2$ (1, 1), $P_3$ (2, 4), $P_4$ (1, 5), $P_5$ (5, 2).

Attese: $P_2=0$, $P_5=1$, $P_1=6$, $P_3=16$, $P_4=18$; media $= 41/5 = 8{,}2$. Turnaround: 1, 6, 16, 18, 19; media $= 60/5 = 12$.

Priorità con round robin: si esegue il processo di priorità più alta; quelli con la stessa priorità girano a RR. Con $q=2$ e tre livelli, per esempio, quelli del livello migliore si alternano a quanti di 2 finché non finiscono, poi tocca al livello successivo. Un processo che arriva con priorità più alta del processo in esecuzione lo prelaziona (v. Esercizio - Round robin con priorità e task idle (eserciziario, esercizio 83)).

Code multilivello e a feedback

Una coda multilivello (multilevel queue) divide la ready queue in più code, ciascuna con il suo algoritmo (per esempio una coda per i processi interattivi con RR e una per i batch con FCFS). Parametri: numero di code, algoritmo di ogni coda, regola per decidere in quale coda entra un processo, scheduling tra le code (di solito a priorità: si serve la coda più alta non vuota). È di solito un criterio basato sul tipo di processo.

Nel feedback multilivello (multilevel feedback queue, MLFQ) i processi si spostano tra le code: un processo che usa troppa CPU viene declassato, uno che aspetta troppo viene promosso (così si realizza anche l'aging). Parametri: numero di code, algoritmo di ciascuna, regole per scegliere la coda d'ingresso, per promuovere e per declassare. Esempio (slide): tre code, $Q_0$ RR con quanto 8 ms, $Q_1$ RR con quanto 16 ms, $Q_2$ FCFS. Un nuovo processo entra in $Q_0$ e riceve 8 ms; se non finisce passa a $Q_1$, dove riceve altri 16 ms; se ancora non finisce va in $Q_2$, dove aspetta tutti i processi presenti in $Q_2$ e quelli in $Q_0$ e $Q_1$. I processi brevi finiscono presto, i lunghi scendono.

Esercizi collegati

• Esercizio - Scheduling FCFS, SJF e priorità con sei processi (eserciziario, esercizio 24)
• Esercizio - Scheduling FCFS e SJF con tempo di turnaround e processi in coda (eserciziario, esercizi 29 e 30)
• Esercizio - Round robin con arrivi e conteggio dei processi in coda (eserciziario, esercizio 31)
• Esercizio - Round robin con due quanti di tempo (eserciziario, esercizio 61)
• Esercizio - Lettura di un diagramma di Gantt e ordine di priorità (eserciziario, esercizi 25 e 28)
• Esercizio - Scheduling con I-O, effetto convoglio ed EDF (eserciziario, esercizio 27)
• Esercizio - Code a priorità con aging e feedback (eserciziario, esercizio 23)
• Esercizio - Code multiple con SRTF, round robin e FCFS (eserciziario, esercizio 26)
• Esercizio - Round robin con priorità e task idle (eserciziario, esercizio 83)

Domande d'esame

1. Perché SJF è ottimo per il tempo di attesa medio e perché non si usa in pratica così com'è? Traccia. Scambiare due processi adiacenti, il più lungo prima del più breve, aumenta l'attesa totale: mettere avanti i brevi la minimizza. Non si usa tal quale perché il prossimo burst non è noto: si stima con la media esponenziale $\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$ e c'è rischio di starvation per i lunghi.

2. Che cos'è l'effetto convoglio? Fare un esempio con numeri. Traccia. Processi brevi in coda dietro uno lungo. Esempio: burst 24, 3, 3 in FCFS: attese 0, 24, 27, media 17; con l'ordine 3, 3, 24 la media è 3.

3. Come si sceglie il quanto in round robin? Che cosa succede se è troppo grande o troppo piccolo? Traccia. Deve essere grande rispetto al tempo di cambio di contesto (q tra 10 e 100 ms, contro meno di 10 $\mu$s). Troppo grande: RR degenera in FCFS e la risposta peggiora. Troppo piccolo: l'overhead del cambio di contesto domina. Nessun processo attende più di $(n-1)q$ prima del suo turno.