Esercizio - Code multiple con SRTF, round robin e FCFS (eserciziario, esercizio 26)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 26). Dieci processi:

La lettera indica la coda in cui il processo viene ammesso. Scheduling a code multiple con prelazione: la coda $A$ è gestita con SRTF, la coda $B$ con Round Robin con quanto di 2 ms, la coda $C$ con FCFS; $A$ ha priorità su $B$, e $B$ su $C$. Si descriva la sequenza di esecuzione con un Gantt, si calcoli l'istante di completamento di ogni job e il tempo medio di attesa. 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 →.

Regole

• Si serve sempre la coda di priorità più alta che contiene un processo pronto; un arrivo in una coda più alta prelaziona il processo di una coda più bassa.
• Coda $A$: tra i processi pronti si sceglie quello con tempo residuo minore (e arrivo precedente a parità).
• Coda $B$: round robin, quanto 2; un processo prelazionato da un job di $A$ torna in fondo alla coda $B$ e il suo quanto riparte da zero la volta successiva. I nuovi arrivi nell'istante in cui scade un quanto entrano prima del prelazionato.
• Coda $C$: FCFS (nell'ordine di arrivo), senza prelazione tra i processi di $C$.

Svolgimento

Si tiene aggiornato lo stato della coda $B$ (a sinistra il prossimo) e ogni volta si guarda prima la coda $A$.

Sequenza completa (coincide con quella del corso): $A_1(0\text{-}4)$, $A_2(4\text{-}6)$, $B_1(6\text{-}8)$, $A_3(8\text{-}9)$, $B_2(9\text{-}11)$, $A_4(11\text{-}15)$, $B_1(15\text{-}17)$, $B_3(17\text{-}19)$, $B_2(19\text{-}21)$, $B_1(21\text{-}22)$, $B_3(22\text{-}23)$, $C_1(23\text{-}30)$, $C_2(30\text{-}38)$, $C_3(38\text{-}40)$. Il corso commenta: "$B_3$ arriva dopo il quanto dato a $B_1$, viene messo nella coda dopo $B_1$: dopo l'esecuzione di $B_2$ avrò nella coda $B_1 \to B_3 \to B_2$".

Tempi di completamento e attesa

Attesa $=$ fine $-$ arrivo $-$ burst:

Somma delle attese $= 117$; media $= 117/10 = 11{,}7$ ms (come nel corso).

Domande d'esame

Cosa significa che la coda $A$ ha priorità assoluta sulla coda $B$? Che rischio comporta? Traccia. Finché in $A$ c'è un processo pronto, $B$ e $C$ non girano, e un nuovo arrivo in $A$ prelaziona subito. I processi delle code basse possono soffrire di starvation (qui $C$ parte solo a 23); si evita con feedback e aging.