Problème — Ordonnancement par tourniquet

Systèmes d'exploitation et processus · niveau 3 (difficile)

Énoncé

Problème — Ordonnancement par tourniquet.

Quatre processus arrivent tous à l'instant $0$ : $P_{1}$ (durée $5$ ), $P_{2}$ (durée $3$ ), $P_{3}$ (durée $1$ ), $P_{4}$ (durée $4$ ). On applique un ordonnancement tourniquet (Round Robin) de quantum $2$ , en respectant l'ordre $P_{1}, P_{2}, P_{3}, P_{4}$ dans la file. On suppose qu'une commutation de contexte est instantanée.

Construire le diagramme de Gantt.
Donner l'instant de fin de chaque processus.
Calculer le temps de rotation moyen.

Corrigé

1. Déroulement. On sert chaque processus pour au plus $2$ unités, puis on le replace en fin de file s'il reste du travail. Durées restantes notées entre crochets.

$[0, 2]$ : $P_{1}$ (reste $3$ ), file : $P_{2}, P_{3}, P_{4}, P_{1}$ .
$[2, 4]$ : $P_{2}$ (reste $1$ ), file : $P_{3}, P_{4}, P_{1}, P_{2}$ .
$[4, 5]$ : $P_{3}$ (reste $0$ , durée $1 < 2$ ) : $P_{3}$ termine à $5$ , file : $P_{4}, P_{1}, P_{2}$ .
$[5, 7]$ : $P_{4}$ (reste $2$ ), file : $P_{1}, P_{2}, P_{4}$ .
$[7, 9]$ : $P_{1}$ (reste $1$ ), file : $P_{2}, P_{4}, P_{1}$ .
$[9, 10]$ : $P_{2}$ (reste $0$ ) : $P_{2}$ termine à $10$ , file : $P_{4}, P_{1}$ .
$[10, 12]$ : $P_{4}$ (reste $0$ ) : $P_{4}$ termine à $12$ , file : $P_{1}$ .
$[12, 13]$ : $P_{1}$ (reste $0$ ) : $P_{1}$ termine à $13$ .

2. Instants de fin. $P_{3} : 5$ , $P_{2} : 10$ , $P_{4} : 12$ , $P_{1} : 13$ .

3. Temps de rotation (fin $-$ arrivée, arrivée $= 0$ ) : $P_{1} = 13$ , $P_{2} = 10$ , $P_{3} = 5$ , $P_{4} = 12$ . $Moyenne = \frac{13 + 10 + 5 + 12}{4} = \frac{40}{4} = 10 unit e ˊ s.$

Le tourniquet répartit équitablement le processeur : aucun processus n'attend indéfiniment, mais le processus long $P_{1}$ termine en dernier malgré son arrivée en tête.