Esercizio - Round robin con due quanti di tempo (eserciziario, esercizio 61)

In questa pagina 4

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 61, tradotto). In un sistema con scheduling preemptive circolare (round robin) i processi, solo di calcolo (nessun I/O), hanno i tempi di arrivo ed esecuzione seguenti (unità in millisecondi):

processo	arrivo	esecuzione
$P_1$	0	500
$P_2$	100	300
$P_3$	300	400
$P_4$	600	1000
$P_5$	700	600

Si valuta l'effetto del quanto, con valori 200 e 500 ms. Per ciascuno: (1) l'istante di fine di ogni processo; (2) il tempo di turnaround; (3) tempo di servizio e di attesa; (4) il turnaround normalizzato; (5) tempo medio di attesa; (6) turnaround medio. Teoria: Scheduling della CPU - FCFS, SJF, priorità e round robin.

Definizioni usate. Turnaround $=$ fine $-$ arrivo. Tempo di servizio $=$ tempo di CPU effettivo $=$ burst. Attesa $=$ turnaround $-$ servizio. Turnaround normalizzato $=$ turnaround / servizio (quante volte il processo dura più del necessario). Quando un processo arriva nell'istante esatto in cui scade un quanto, qui entra in coda prima di quello prelazionato (v. sotto).

Quanto $q = 200$

Sequenza dei turni, con la coda dei pronti subito dopo ogni turno (tra parentesi i residui; il processo appena prelazionato è in fondo alla coda):

turno	esegue	residuo	coda dopo il turno
0 .. 200	$P_1$	300	$P_2$ (arrivato a 100), $P_1$
200 .. 400	$P_2$	100	$P_1$ , $P_3$ (arrivato a 300), $P_2$
400 .. 600	$P_1$	100	$P_3$ , $P_2$ , $P_4$ (arriva a 600), $P_1$
600 .. 800	$P_3$	200	$P_2$ , $P_4$ , $P_1$ , $P_5$ (arrivato a 700), $P_3$
800 .. 900	$P_2$	0, finisce a 900	$P_4$ , $P_1$ , $P_5$ , $P_3$
900 .. 1100	$P_4$	800	$P_1$ , $P_5$ , $P_3$ , $P_4$
1100 .. 1200	$P_1$	0, finisce a 1200	$P_5$ , $P_3$ , $P_4$
1200 .. 1400	$P_5$	400	$P_3$ , $P_4$ , $P_5$
1400 .. 1600	$P_3$	0, finisce a 1600	$P_4$ , $P_5$
1600 .. 1800	$P_4$	600	$P_5$ , $P_4$
1800 .. 2000	$P_5$	200	$P_4$ , $P_5$
2000 .. 2200	$P_4$	400	$P_5$ , $P_4$
2200 .. 2400	$P_5$	0, finisce a 2400	$P_4$
2400 .. 2800	$P_4$	0, finisce a 2800

Attenzione al caso $t = 600$ : il quanto di $P_1$ scade proprio quando arriva $P_4$ . In questo esercizio le soluzioni del corso mettono il nuovo arrivato davanti al processo prelazionato (la coda diventa $P_4, P_1$ ), cioè la convenzione opposta a quella dell'esercizio 31 (Esercizio - Round robin con arrivi e conteggio dei processi in coda (eserciziario, esercizio 31)). Qui si segue questa, per trovare i risultati del corso; le due soluzioni del corso non usano la stessa regola, per cui in un compito conviene dichiararla.

Diagramma di Gantt riassuntivo:

0-200	200-400	400-600	600-800	800-900	900-1100	1100-1200	1200-1400	1400-1600	1600-1800	1800-2000	2000-2200	2200-2400	2400-2800
$P_1$	$P_2$	$P_1$	$P_3$	$P_2$	$P_4$	$P_1$	$P_5$	$P_3$	$P_4$	$P_5$	$P_4$	$P_5$	$P_4$

	fine	turnaround	servizio	attesa	turnaround normalizzato
$P_1$	1200	1200	500	700	2,40
$P_2$	900	800	300	500	2,67
$P_3$	1600	1300	400	900	3,25
$P_4$	2800	2200	1000	1200	2,20
$P_5$	2400	1700	600	1100	2,83
media		1440		880	2,67

Quanto $q = 500$

Con $q = 500$ nessun processo di burst $\le 500$ viene prelazionato ( $P_1$ , $P_2$ , $P_3$ finiscono in un turno): RR si comporta come FCFS per loro.

0-500	500-800	800-1200	1200-1700	1700-2200	2200-2700	2700-2800
$P_1$	$P_2$	$P_3$	$P_4$	$P_5$	$P_4$	$P_5$

	fine	turnaround	servizio	attesa	turnaround normalizzato
$P_1$	500	500	500	0	1,00
$P_2$	800	700	300	400	2,33
$P_3$	1200	900	400	500	2,25
$P_4$	2700	2100	1000	1100	2,10
$P_5$	2800	2100	600	1500	3,50
media		1260		700	2,23

Confronto

quanto	attesa media	turnaround medio	normalizzato medio
200	880	1440	2,67
500	700	1260	2,23

Con il quanto più grande diminuiscono sia l'attesa media sia il turnaround medio (meno prelazioni, quindi meno ritardi aggiunti ai lunghi); la risposta, però, peggiora (per esempio $P_4$ riceve la CPU per la prima volta a 1200 invece che a 900). Qui si trascura il costo del cambio di contesto, che andrebbe sommato a ogni prelazione e penalizza il quanto piccolo. I valori coincidono con le tabelle del corso (880 / 2,67 e 700 / 2,23). I numeri sono stati ricalcolati con una simulazione in Python.

Domande d'esame

Cosa succede al turnaround medio aumentando il quanto fino a infinito? Traccia. RR tende a FCFS: qui con $q \ge 1000$ l'ordine è di arrivo, e il turnaround medio vale quello del FCFS sugli stessi dati.

Versione ripasso

Dati: (arrivo, burst) $P_1$ (0, 500), $P_2$ (100, 300), $P_3$ (300, 400), $P_4$ (600, 1000), $P_5$ (700, 600); $q=200$ e $q=500$ . Teoria: Scheduling della CPU - FCFS, SJF, priorità e round robin.
Definizioni: turnaround = fine $-$ arrivo; attesa = turnaround $-$ servizio; normalizzato = turnaround / servizio. Arrivo in un istante di fine quanto ( $t=600$ ): prima del prelazionato (opposto all'esercizio 31).
$q=200$ : Gantt $P_1P_2P_1P_3P_2P_4P_1P_5P_3P_4P_5P_4P_5P_4$ (fine 1200, 900, 1600, 2800, 2400 per $P_1,P_2,P_3,P_4,P_5$ ); attesa 700, 500, 900, 1200, 1100 -> 880; turnaround medio 1440; normalizzato 2,67.
$q=500$ : $P_1P_2P_3P_4P_5P_4P_5$ ; fine 500, 800, 1200, 2700, 2800; attesa 0, 400, 500, 1100, 1500 -> 700; turnaround 1260; normalizzato 2,23.
Conclusione: $q$ più grande -> meno prelazioni, attese minori, risposta peggiore.
Residui $q=200$ : $P_1$ 500 $\to$ 300 $\to$ 100 $\to$ 0; $P_2$ 300 $\to$ 100 $\to$ 0; $P_3$ 400 $\to$ 200 $\to$ 0; $P_4$ 1000 $\to$ 800 $\to$ 600 $\to$ 400 $\to$ 0; $P_5$ 600 $\to$ 400 $\to$ 200 $\to$ 0. Coda a 600: $P_3,P_2,P_4,P_1$ (nuovo arrivo davanti al prelazionato).
Normalizzato $q=500$ : $P_1$ 1,00; $P_2$ 2,33; $P_3$ 2,25; $P_4$ 2,10; $P_5$ 3,50 (media 2,23); con $q=200$ : 2,40; 2,67; 3,25; 2,20; 2,83 (media 2,67).
Errori tipici: attesa senza sottrarre il servizio; dimenticare i residui; confondere servizio e turnaround.

Teoria collegata

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