Esercizio - Scheduling FCFS, SJF e priorità con sei processi (eserciziario, esercizio 24)

In questa pagina 5

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 24). Sei processi $P_1, \dots, P_6$ richiedono la CPU contemporaneamente, all'istante 0. Durata del burst di CPU e priorità (numeri bassi = priorità alta):

processo	burst	priorità
$P_1$	6	1
$P_2$	4	2
$P_3$	8	3
$P_4$	2	4
$P_5$	4	5
$P_6$	6	6

Si tracci il diagramma di Gantt e si calcoli il tempo di completamento di ogni processo con (1) Shortest Job First, (2) scheduling a priorità, (3) Round Robin con quanto $q = 2$ . Si trascura il tempo di cambio di contesto; in caso di parità si ordina per indice. Teoria: Scheduling della CPU - FCFS, SJF, priorità e round robin.

1. Shortest Job First

Tutti arrivano a 0, quindi SJF (non preemptive) esegue i processi in ordine di burst crescente, a parità per indice: $P_4$ (2), $P_2$ (4), $P_5$ (4), $P_1$ (6), $P_6$ (6), $P_3$ (8).

t	0 .. 2	2 .. 6	6 .. 10	10 .. 16	16 .. 22	22 .. 30
CPU	$P_4$	$P_2$	$P_5$	$P_1$	$P_6$	$P_3$

Tempi di completamento (= turnaround, perché arrivano tutti a 0): $P_4 = 2$ , $P_2 = 6$ , $P_5 = 10$ , $P_1 = 16$ , $P_6 = 22$ , $P_3 = 30$ . Media: $(2 + 6 + 10 + 16 + 22 + 30)/6 = 86/6 = 14{,}33$ .

2. Priorità

Priorità $P_1$ (1) la più alta ... $P_6$ (6) la più bassa; poiché le priorità coincidono con l'ordine degli indici e non c'è prelazione che cambi nulla, l'ordine è $P_1, P_2, \dots, P_6$ (come FCFS).

t	0 .. 6	6 .. 10	10 .. 18	18 .. 20	20 .. 24	24 .. 30
CPU	$P_1$	$P_2$	$P_3$	$P_4$	$P_5$	$P_6$

Completamenti: 6, 10, 18, 20, 24, 30; media $= 108/6 = 18$ .

3. Round Robin con $q = 2$

Coda iniziale $P_1, P_2, P_3, P_4, P_5, P_6$ . Ogni giro assegna 2 unità a ciascun processo ancora attivo. Burst residui dopo ogni giro:

giro	$P_1$	$P_2$	$P_3$	$P_4$	$P_5$	$P_6$	istanti
inizio	6	4	8	2	4	6
1	4	2	6	0 ( $P_4$ finisce a 8)	2	4	0 .. 12
2	2	0 ( $P_2$ finisce a 16)	4		0 ( $P_5$ finisce a 20)	2	12 .. 22
3	0 ( $P_1$ finisce a 24)		2			0 ( $P_6$ finisce a 28)	22 .. 28
4			0 ( $P_3$ finisce a 30)				28 .. 30

Diagramma di Gantt completo (ogni cella 2 unità):

0-2	2-4	4-6	6-8	8-10	10-12	12-14	14-16	16-18	18-20	20-22	22-24	24-26	26-28	28-30
$P_1$	$P_2$	$P_3$	$P_4$	$P_5$	$P_6$	$P_1$	$P_2$	$P_3$	$P_5$	$P_6$	$P_1$	$P_3$	$P_6$	$P_3$

Completamenti: $P_4 = 8$ , $P_2 = 16$ , $P_5 = 20$ , $P_1 = 24$ , $P_6 = 28$ , $P_3 = 30$ ; media $= 126/6 = 21$ .

Confronto

politica	$P_1$	$P_2$	$P_3$	$P_4$	$P_5$	$P_6$	media
SJF	16	6	30	2	10	22	14,33
priorità	6	10	18	20	24	30	18
RR $q=2$	24	16	30	8	20	28	21

SJF è ottimo per il tempo medio; RR ha il turnaround più alto ma il tempo di risposta migliore (tutti partono entro 10 unità). Risultati ricalcolati con una simulazione in Python e coincidenti con quelli del corso (14,3, 18, 21).

Domande d'esame

Con quale algoritmo il turnaround medio è minimo, e perché? Traccia. SJF: eseguire prima i processi brevi riduce l'attesa di molti processi al prezzo dell'attesa di uno solo lungo; qui 14,33 contro 18 e 21.

Versione ripasso

Dati: burst 6, 4, 8, 2, 4, 6; priorità 1..6; tutti a $t=0$ . Teoria: Scheduling della CPU - FCFS, SJF, priorità e round robin.
SJF: ordine $P_4,P_2,P_5,P_1,P_6,P_3$ (parità per indice); completamenti 2, 6, 10, 16, 22, 30; media 14,33.
Priorità: ordine $P_1..P_6$ ; completamenti 6, 10, 18, 20, 24, 30; media 18.
RR $q=2$ : Gantt $P_1P_2P_3P_4P_5P_6P_1P_2P_3P_5P_6P_1P_3P_6P_3$ (2 unità ciascuno); completamenti $P_4=8$ , $P_2=16$ , $P_5=20$ , $P_1=24$ , $P_6=28$ , $P_3=30$ ; media 21.
Turnaround = fine $-$ arrivo (qui arrivo 0). SJF minimo per l'attesa media; RR ha la risposta migliore.
Errori tipici: ordine sbagliato nelle parità; contare il quanto residuo male in RR; dimenticare che i processi finiti escono dal giro.

Teoria collegata

Scheduling della CPU - FCFS, SJF, priorità e round robin