Esercizio - Code a priorità con aging e feedback (eserciziario, esercizio 23)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 23). Cinque job:

Si descriva la sequenza di esecuzione (diagramma di Gantt) e si calcoli l'istante di completamento di ogni job con code multiple a priorità e feedback, dove ogni coda è gestita con FCFS. Il feedback: la priorità diminuisce di 1 (fino al livello base 1) se passano più di 6 unità di tempo consecutive in esecuzione, e aumenta di 1 per ogni 6 unità di tempo passate in attesa in una qualsiasi coda. Il numero più alto è la priorità più alta. Nota del corso: FCFS serve a gestire le code, non a far prelazionare un processo il cui valore di priorità aumenta durante l'esecuzione di un altro. 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 operative

• C'è una coda per ogni livello di priorità; si esegue il job della coda non vuota di priorità più alta; dentro la coda, FCFS nell'ordine di ingresso nella coda.
• Un job in esecuzione viene prelazionato solo da un job di priorità strettamente maggiore (all'arrivo o dopo un invecchiamento).
• Ogni job pronto accumula attesa; ogni 6 unità consecutive di attesa la sua priorità sale di 1 e il job entra in fondo alla coda del nuovo livello. Quando un job lascia la CPU (prelazione o declassamento), il suo contatore di attesa riparte da 0 e il job va in fondo alla coda del suo livello.
• Un job che raggiunge 6 unità consecutive in esecuzione scende di 1 (minimo 1). Questa è la lettura con cui si trovano i risultati del corso (v. la nota in fondo).

Svolgimento passo per passo

Si scrive per ogni istante significativo chi esegue e le priorità correnti.

Diagramma di Gantt:

Verifica delle durate: $A = 1 + 6 + 1 = 8$, $B = 6$, $C = 2 + 1 = 3$, $D = 4$, $E = 3$. Totale $24$.

Istanti di completamento: $B = 7$, $D = 19$, $E = 22$, $C = 23$, $A = 24$; turnaround ($=$ fine $-$ arrivo): $A = 24$, $B = 6$, $C = 21$, $D = 16$, $E = 18$. Coincidono con la soluzione del corso.

Note sull'incertezza della traccia

• La traccia dice "più di 6 unità" per il declassamento. Con quella lettura stretta $A$ esegue 7 unità consecutive (7 .. 14), che sono proprio il suo residuo, e termina a 14 senza essere declassato: risulterebbero $B = 7$, $A = 14$, $C = 17$, $D = 21$, $E = 24$. La soluzione del corso ($A = 24$) corrisponde invece al declassamento già al raggiungimento delle 6 unità: è la lettura seguita sopra.
• Il corso annota che in una versione del Gantt il cambio di priorità di $C$ dopo 5 istanti è errato: il job deve sempre aspettare 6 unità. Qui $C$ sale a 3 a $t=8$ (arrivato a 2).
• Entrambe le versioni sono state controllate con una simulazione in Python.

Domande d'esame

Perché il feedback con aging evita la starvation? Traccia. Ogni 6 unità di attesa la priorità cresce di 1: un job a bassa priorità arriva prima o poi a un livello più alto di quelli che lo precedono, e viene eseguito. Il calo dopo troppa esecuzione impedisce che i job lunghi monopolizzino la CPU.