Esercizio - Scheduling FCFS e SJF con tempo di turnaround e processi in coda (eserciziario, esercizi 29 e 30)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizi 29 e 30).

Esercizio 29. All'istante $t = 0$ arrivano nella coda dei processi pronti, prima vuota, sei processi con i burst seguenti: $P_0 = 3$, $P_1 = 5$, $P_2 = 2$, $P_3 = 6$, $P_4 = 7$, $P_5 = 3$. (a) Si disegni il diagramma di Gantt con scheduling in ordine di arrivo (FCFS) e si calcolino tempo medio di turnaround, tempo medio di attesa in coda e numero medio di processi in attesa nella coda. (b) Come cambiano le risposte con scheduling per brevità (SJF), a parità di durata ha priorità il processo con indice minore?

Esercizio 30. Con SJF senza prelazione si calcoli il tempo medio di turnaround dei processi di tabella e si mostri il diagramma di Gantt; poi si risponda cosa cambia con prelazione (SRTF).

Teoria: Scheduling della CPU - FCFS, SJF, priorità e round robinLo scheduler della CPU sceglie tra i processi pronti quello a cui dare il core (il dispatcher esegue il cambio, con latenza di dispatch); lo scheduling è non preemptive (il processo tiene la CPU finché termina o si blocca) o preemptive (la CPU gli può essere tolta, con rischio di race condition); i criteri sono utilizzo della CPU e throughput (da massimizzare), tempo di attesa, di turnaround (completamento meno arrivo) e di risposta (da minimizzare); FCFS è semplice ma soffre dell'effetto convoglio (esempio 24, 3, 3: attesa media 17 contro 3); SJF è ottimo per l'attesa media ma richiede la lunghezza del prossimo burst, stimata con la media esponenziale tau(n+1) = alfa t(n) + (1-alfa) tau(n); SRTF è la versione preemptive (esempio con attesa media 6,5 contro 7,75); round robin dà a ciascuno un quanto q e nessuno attende più di (n-1)q; la priorità causa starvation, risolta con l'aging; code multilivello e a feedback (MLFQ) combinano le politiche.Scheduling della CPU - FCFS, SJF, priorità e round robin →.

Esercizio 29(a): FCFS

I processi arrivano tutti a 0 nell'ordine $P_0..P_5$.

• Turnaround (fine $-$ 0): 3, 8, 10, 16, 23, 26; media $= 86/6 = 14{,}33$.
• Attesa (turnaround $-$ burst): 0, 3, 8, 10, 16, 23; media $= 60/6 = 10$.
• Numero medio di processi in coda. Si conta, istante per istante, quanti processi sono pronti ma non in esecuzione, e si media sui 26 istanti:

$$\frac{5\cdot 3 + 4\cdot 5 + 3\cdot 2 + 2\cdot 6 + 1\cdot 7 + 0\cdot 3}{26} = \frac{60}{26} = 2{,}31.$$

Il valore 60 coincide con la somma dei tempi di attesa (60): è la legge di Little, numero medio in coda $=$ (somma delle attese) / (durata totale). Il corso riporta 2,31, corretto.

Esercizio 29(b): SJF

Ordine per burst crescente: $P_2$ (2), $P_0$ (3), $P_5$ (3), $P_1$ (5), $P_3$ (6), $P_4$ (7).

Turnaround: $P_2 = 2$, $P_0 = 5$, $P_5 = 8$, $P_1 = 13$, $P_3 = 19$, $P_4 = 26$; media $= 73/6 = 12{,}17$. Attese: 0, 2, 5, 8, 13, 19; media $= 47/6 = 7{,}83$. Processi in coda: $47/26 = 1{,}81$ (con 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1 seguiti da zeri: somma 47).

Esercizio 30: SJF senza prelazione

Ad ogni fine di burst si sceglie tra i processi già arrivati quello più breve (parità per indice).

Turnaround $=$ fine $-$ arrivo: $P_0 = 3$, $P_1 = 8$, $P_2 = 6$, $P_3 = 3$, $P_4 = 6$, $P_5 = 12$, $P_6 = 18$, $P_7 = 3$, $P_8 = 2$, $P_9 = 4$. Media $= 65/10 = 6{,}5$.

Con prelazione (SRTF)

(nell'intervallo 3-8 la CPU è inattiva). Per esempio a $t = 11$ arriva $P_2$ (burst 1) mentre $P_1$ ha ancora 5 unità: lo prelaziona; a $t = 21$ arriva $P_7$ (1) con $P_4$ a 2 unità dalla fine: lo prelaziona. Turnaround: $P_0 = 3$, $P_1 = 18-8 = 10$, $P_2 = 1$, $P_3 = 1$, $P_4 = 24-17 = 7$, $P_5 = 32-19 = 13$, $P_6 = 18$, $P_7 = 1$, $P_8 = 2$, $P_9 = 1$; media $= 57/10 = 5{,}7$. I valori del corso (6,5 e 5,7) sono confermati da una simulazione.

Domande d'esame

Perché il numero medio di processi in coda si può ricavare dai tempi di attesa? Traccia. Legge di Little: la somma, istante per istante, dei processi in coda è uguale alla somma dei tempi di attesa di tutti i processi (ogni processo contribuisce 1 per ogni istante in cui attende); si divide per la durata totale. Con FCFS: $60/26 = 2{,}31$.