Esercizio - Round robin con priorità e task idle (eserciziario, esercizio 83)

In questa pagina 3

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 83, tradotto). Dato lo scheduling round robin preemptive con priorità e quanto di 10 unità; esiste inoltre un task idle con burst 0 che gira quando non ci sono processi pronti. Un processo prelazionato viene messo in fondo alla coda del proprio livello di priorità. Il numero più alto è la priorità più alta.

processo	priorità	burst	arrivo
$P_1$	40	20	0
$P_2$	30	25	25
$P_3$	30	25	30
$P_4$	35	15	60
$P_5$	5	10	100
$P_6$	10	10	105

Si mostri il diagramma di Gantt, il turnaround e l'attesa di ogni processo. Teoria: Scheduling della CPU - FCFS, SJF, priorità e round robin.

Regole

Si esegue il processo pronto di priorità più alta. Un nuovo arrivo con priorità strettamente maggiore prelaziona subito il processo in esecuzione (che va in fondo alla propria coda).
Processi con la stessa priorità girano a round robin con quanto 10.
Quando nessun processo è pronto gira l'idle.

Svolgimento

intervallo	esegue	motivo
0 .. 20	$P_1$ (40)	unico processo; il quanto scade a 10 e a 20 ma nessun altro è pronto, quindi continua; finisce a 20
20 .. 25	idle	nessun processo pronto
25 .. 35	$P_2$ (30)	arriva a 25; quanto fino a 35
35 .. 45	$P_3$ (30)	$P_3$ è arrivato a 30 e attende in coda 30; scaduto il quanto di $P_2$ (residuo 15) tocca a lui (residuo 15)
45 .. 55	$P_2$ (30)	altro quanto (residuo 5)
55 .. 60	$P_3$ (30)	residuo 15: esegue 5 unità e a 60 arriva $P_4$
60 .. 75	$P_4$ (35)	$P_4$ ha priorità 35 > 30 e prelaziona $P_3$ (residuo 10); esegue 15 unità (un quanto e mezzo, nessuno ha priorità uguale) e finisce a 75
75 .. 80	$P_2$ (30)	$P_2$ (in coda prima di $P_3$ ) esegue le sue 5 unità residue e finisce a 80
80 .. 90	$P_3$ (30)	residuo 10, finisce a 90
90 .. 100	idle
100 .. 105	$P_5$ (5)	arriva a 100 e parte
105 .. 115	$P_6$ (10)	$P_6$ arriva a 105 con priorità 10 > 5 e prelaziona $P_5$ (residuo 5); finisce a 115
115 .. 120	$P_5$ (5)	termina a 120

Diagramma di Gantt:

0-20	20-25	25-35	35-45	45-55	55-60	60-75	75-80	80-90	90-100	100-105	105-115	115-120
$P_1$	idle	$P_2$	$P_3$	$P_2$	$P_3$	$P_4$	$P_2$	$P_3$	idle	$P_5$	$P_6$	$P_5$

Verifica delle durate eseguite: $P_2 = 10 + 10 + 5 = 25$ ✓; $P_3 = 10 + 5 + 10 = 25$ ✓; $P_4 = 15$ ✓; $P_1 = 20$ ✓; $P_5 = 5 + 5 = 10$ ✓; $P_6 = 10$ ✓.

Turnaround e attesa

	arrivo	fine	turnaround	burst	attesa
$P_1$	0	20	20	20	0
$P_2$	25	80	55	25	30
$P_3$	30	90	60	25	35
$P_4$	60	75	15	15	0
$P_5$	100	120	20	10	10
$P_6$	105	115	10	10	0

Risultati coincidenti con la soluzione del corso (turnaround 20, 55, 60, 15, 20, 10; attesa 0, 30, 35, 0, 10, 0).

Domande d'esame

Perché $P_5$ attende anche se è stato il primo a partire dopo l'idle? Traccia. Perché a $t=105$ arriva $P_6$ con priorità maggiore (10 > 5) e lo prelaziona: $P_5$ riprende solo a 115 e attende 10 unità.

Versione ripasso

Dati: $q=10$ , priorità alta = numero alto; $P_1$ (40, burst 20, arrivo 0), $P_2$ (30, 25, 25), $P_3$ (30, 25, 30), $P_4$ (35, 15, 60), $P_5$ (5, 10, 100), $P_6$ (10, 10, 105). Teoria: Scheduling della CPU - FCFS, SJF, priorità e round robin.
Regole: prelazione solo con priorità strettamente maggiore; stessa priorità in RR; idle se nulla è pronto.
Gantt: $P_1$ 0-20, idle 20-25, $P_2$ 25-35, $P_3$ 35-45, $P_2$ 45-55, $P_3$ 55-60, $P_4$ 60-75, $P_2$ 75-80, $P_3$ 80-90, idle 90-100, $P_5$ 100-105, $P_6$ 105-115, $P_5$ 115-120.
Turnaround: 20, 55, 60, 15, 20, 10. Attesa: 0, 30, 35, 0, 10, 0.
Errori tipici: prelazione con priorità uguale; dimenticare i tempi idle; far ripartire il quanto della stessa coda a metà.

Teoria collegata

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