Esercizio - Round robin con arrivi e conteggio dei processi in coda (eserciziario, esercizio 31)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 31). La CPU è assegnata con Round Robin e quanto $q = 3$. Processi:

(1) Tempo medio di turnaround, quando due processi arrivano nello stesso istante ha priorità l'indice minore. (2) Tempo medio di attesa in coda. (3) Numero medio di processi nella coda dei pronti. 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 →.

La convenzione da fissare

In RR, quando un quanto scade nello stesso istante in cui arriva un processo nuovo, bisogna decidere chi entra per primo in coda. Il corso usa la convenzione: il processo prelazionato entra prima del nuovo arrivato; solo gli arrivi strettamente prima della fine del quanto stanno davanti. Con la convenzione opposta i risultati cambiano (vedi il confronto in fondo).

Svolgimento

Si tiene la coda dei pronti (a sinistra il prossimo):

Diagramma di Gantt (un'unità per colonna dove serve):

(Il processo $P_2$ che a 8 è prelazionato con residuo 2 ritorna a 11; $P_3$ è prelazionato a 11 con residuo 1.)

(1) Turnaround

Turnaround $=$ fine $-$ arrivo:

Media $= 68/10 = 6{,}8$.

(2) Attesa in coda

Attesa $=$ turnaround $-$ durata: $0, 0, 5, 9, 11, 6, 7, 6, 0, 1$. Media $= 45/10 = 4{,}5$.

(3) Numero medio di processi in coda

Si conta, per ogni istante intero, quanti processi sono pronti ma non in esecuzione:

Somma $= 45$, istanti $= 25$ (da 0 a 25), media $= 45/25 = 1{,}8$. Come nell'esercizio precedente coincide con la somma delle attese diviso la durata (Little).

Controllo con la convenzione opposta

Se il nuovo arrivato entra prima del prelazionato, la sequenza cambia (per esempio a $t=8$ la coda diventa $P_3, P_4, P_2$ invece di $P_3, P_2, P_4$) e il turnaround medio diventa $7{,}1$ (attesa media $4{,}8$, coda media $1{,}92$): la scelta della convenzione conta, e va dichiarata. Risultati ricalcolati con una simulazione; quelli del corso (6,8; 4,5; 1,8) sono confermati con la prima convenzione.

Domande d'esame

Cosa succede in RR se un processo arriva nello stesso istante in cui scade il quanto di un altro? Traccia. Dipende dalla convenzione: se il testo non la dice, si dichiara. Con "prelazionato per primo" il processo interrotto entra in coda prima del nuovo arrivato.