Esercizio - Lettura di un diagramma di Gantt e ordine di priorità (eserciziario, esercizi 25 e 28)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD).

Esercizio 28. Il diagramma di Gantt seguente mostra lo scheduling di cinque processi; ogni freccia indica l'istante di arrivo nella coda dei pronti: $P_0$ a 0, $P_1$ a 4, $P_2$ a 6, $P_3$ a 11, $P_4$ a 15.

Domande: (1) l'algoritmo prelaziona la CPU ai processi? (2) qual è il tempo massimo di turnaround e quello medio? (3) se lo scheduling fosse a priorità, qual è l'ordine di priorità dei cinque processi?

Esercizio 25. Sei processi $P_1, \dots, P_6$ sono eseguiti su un monoprocessore secondo un diagramma (i processi in coda dei pronti sono in grigio, in esecuzione in nero). Quali tra FIFO e Round Robin (con un esempio di quanto) possono aver prodotto quella sequenza? Giustificare. Ordine di arrivo e di esecuzione: $P_2, P_1, P_6, P_3, P_5, P_4$, ogni processo viene eseguito una volta sola, senza interruzioni, e il massimo tempo di esecuzione è quello di $P_3$ (10 unità).

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 28

(1) Prelazione. Sì. Per esempio a $t = 4$ arriva $P_1$ mentre $P_0$ ha eseguito 4 unità: $P_0$ viene interrotto e $P_1$ ottiene la CPU. $P_0$ non è terminato (finirà a 15): lo scheduler gli ha tolto la CPU, quindi è preemptive. Anche a $t=6$ $P_1$ è prelazionato da $P_2$.

(2) Turnaround. Turnaround $=$ fine $-$ arrivo. Le fine si leggono dal diagramma (l'ultima fascia di ogni processo):

Massimo $= 15$ ($P_0$). Media $= (15 + 8 + 4 + 7 + 5)/5 = 39/5 = 7{,}8$.

(3) Priorità. Si deduce da ogni prelazione e da ogni scelta:

• a $t=4$, $P_1$ prelaziona $P_0$: $P_1 > P_0$;
• a $t=6$, $P_2$ prelaziona $P_1$: $P_2 > P_1$;
• a $t=10$ finisce $P_2$ e riprende $P_1$ (non $P_0$): coerente con $P_1 > P_0$;
• a $t=11$ arriva $P_3$ ma $P_1$ continua fino a 12: $P_3 \le P_1$ (un arrivo con priorità uguale non prelaziona);
• a $t=12$ finisce $P_1$ e tra $P_0$ e $P_3$ (entrambi pronti) va $P_0$: $P_0 \ge P_3$;
• a $t=15$ arriva $P_4$ mentre esegue $P_0$ e dopo $P_0$ va $P_3$: $P_4 \le P_3$ (non prelaziona, e viene dopo).

Ordine: $P_2 > P_1 > P_0 \ge P_3 \ge P_4$.

Esercizio 25

• FIFO: sì. In FIFO ogni processo gira dall'inizio alla fine nell'ordine di arrivo senza interruzioni. L'ordine di arrivo $P_2, P_1, P_6, P_3, P_5, P_4$ è identico a quello di esecuzione e ogni processo ha un solo tratto nero: è compatibile.
• Round Robin: sì, con un quanto $q \ge$ il massimo tempo di esecuzione (10). Se il quanto è almeno pari alla durata del processo più lungo ($P_3$, 10), nessun processo viene mai prelazionato: RR si riduce a FIFO e produce la stessa sequenza. Un esempio: $q = 10$, o anche $q = 15$. Con un quanto più piccolo (per esempio $q = 4$), $P_3$ verrebbe interrotto e comparirebbe in più tratti, cosa che il diagramma non mostra.

Domande d'esame

Come si capisce da un Gantt se lo scheduling è preemptive? Traccia. Un processo compare in più tratti separati da altri processi prima di essere terminato, o un nuovo arrivo prende subito la CPU a metà del burst di un altro.