Correction TD

Ordonnancement des processus

Exercice 1

avec l'algo. SJF :

a) Diagramme de Gantt
P1 P2 P P4 P5
3
0 2 6 7 8 9

TTM = (2 + 6 + 4 + 5 + 6)/5 = 23/5 = 4.6 sec

TAM= (0 + 2 + (4-1) + (5-1) + (6-1) )/5 = 14/5 = 2,8 sec

b) Tous les travaux sont soumis en même temps :

P3 P4 P5 P1 P2
0 1 2 3 5 9

TTM=(5+9+1+2+3)/5=20/5=4 sec
TAM= (3 + 5 + 0 + 1 + 2) )/5 = 11/5 = 2,2 sec
 L’algorithme SJF n’est optimal que si tous les travaux sont soumis en même temps.
c) Représenter le diagramme de Gantt en considérant que le temps de commutation soit
égale à 1 unité. (dans le cas où P1 et P2 sont arrivés à l’instant 0 et P3, P4 et P5 sont
arrivés à l’instant 3).

P1 P3 P4 P5 P2
0 1 3 4 5 6 7 8 9 10 14

Exercice 2
Cinq travaux arrivent simultanément.
1. Diagramme de Gantt
a. FCFS
P1 P2 P3 P4 P5
0 1 4 6 8 11
TTM = ( 1 + 4 + 6 + 8 + 11) / 5 = 6
 On a négligé le temps de commutation du contexte.
b. SJF
P1 P3 P4 P2 P5
0 1 3 5 8 11

1
 TTM = ( 1 + 3 + 5 + 8 + 11) / 5 = 5,6
 SJF est meilleur que FCFS pour le critère TTM.

3. Le système dispose de deux processeurs et les processus sont dépendants :

a. FCFS :

P2 P5
 Processus actifs sur le processeur 1
P1 P3 P4  Processus actifs sur le processeur 2
0 1 3 5 6 7
Entre t=1 et t=3, P3 ne peut pas commencer car il dépend de P2.
SJF :

P2 P5  Processus actifs sur le processeur 1

P1 P3 P4  Processus actifs sur le processeur 2
0 1 3 5 6 7
b.
TTM2 (FCFS) = (1 + 3 + 5 + 7 + 6 ) = 22/5 = 4,4.
TTM2 (SJF) = (1 + 3 + 5 + 7 + 6 ) = 22/5 = 4,4.
 L’exécution des travaux est plus rapide dans un système multiprocesseur.
 Les tâches sont partagées sur les processeurs.

Exercice 7
Afin de minimiser le TTM, il faut appliquer le SJF. Ainsi, selon la valeur de x, l’ordre
d’exécution des processus doit être comme suit :
- Si x < 2 : E C B D A
- Si x = 2 : C E B D A
- Si 2 < x < 5 : C E B D A
- Si x = 5 : C E B D A
- Si 5 < x < 7 : C B E D A
- Si x = 7 : C B D E A
- Si 7 < x < 9 : C B D E A
- Si x = 9 : C B D A E
- Si x > 9 : C B D A E
Exercice 3
Une valeur de priorité élevée correspond à une priorité plus importante.
L'algorithme d’ordonnancement par priorité :
a. non préemptif :

2
 P1 P3 P4 P2
0 4 8 13 16
b. préemptif :
P1 P2 P3 P4 P2 P1
0 1 2 6 11 13 16

Exercice 4
Exécution de Etat Priorité Quantum
t=…
… P1 P2 P1 P2 P1 P2
initialement - prêt prêt 2 3 2 5
0 P2 // actif // // // //
P2 lance E/S 3 P1 actif bloqué // 2 // 5
5 // // // 2 // 2 //
P1 lance E/S 7 - bloqué bloqué 2 // // //
P1 termine E/S 8 P1 actif // // // // //
P1 et P2 sont
10 P2 prêt actif // // // //
prêts
15 P1 actif prêt 2 2 2 5
17 P2 prêt actif // // // //
P2 ne termine pas
son quantum et 20 P1 actif bloqué // 1 // 5
lance E/S
P1 lance E/S 22 - bloqué bloqué 2 // 2 //
P1 termine E/S
23 P1 actif prêt 2 1 2 5
P1 est prioritaire
25 // // // // // // //
27 // // // // // // //
P1 termine 29 P2 terminé actif - 1 - 5
P2 termine 34 - - terminé - - - -

P1 P2
E/S E/S

E/S E/S
0 3 7 8 10 15 17 20 22 23 29 34

Exercice 5
T T T T T T T T T T T T T T T T T T T T T T T T T
1 2 3 4 5 6 7 1 2 3 5 6 1 2 3 6 1 2 3 6 1 3 1 3 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Ci-dessous, nous présentons le calcul des priorités :

Tâche 0 1 2 3 4 5 6 7 8 9 10
T1 1 2 2 2 2 2 2 2 3 3 3

3
 T2 - 1 2 2 2 2 2 2 2 3 3
T3 - 1 1 2 2 2 2 2 2 2 3
T4 - - 1 1
T5 - - 1 1 1 2 2 2 2 2 2
T6 - - 1 1 1 1 2 2 2 2 2
T7 - - - 1 1 1 1
Tâche 11 12 13 14 15 16 17 18 19 20 21 22 23
T1 3 3 4 4 4 4 5 5 5 5 6 6 7
T2 3 3 3 4 4 4 4
T3 3 3 3 3 4 4 4 4 5 5 5 6 6
T4
T5
T6 2 3 3 3 3 4 4 4 4
T7

Exercice 5
T T T T T T T T T T T T T T T T T T T T T T T T T
1 2 3 4 5 6 7 1 2 3 5 6 1 2 3 6 1 2 3 6 1 3 1 3 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Ci-dessous, nous présentons le calcul des priorités :

Tâche 0 1 2 3 4 5 6 7 8 9 10
T1 1 2 2 2 2 2 2 2 3 3 3
T2 - 1 2 2 2 2 2 2 2 3 3
T3 - 1 1 2 2 2 2 2 2 2 3
T4 - - 1 1
T5 - - 1 1 1 2 2 2 2 2 2
T6 - - 1 1 1 1 2 2 2 2 2
T7 - - - 1 1 1 1
Tâche 11 12 13 14 15 16 17 18 19 20 21 22 23
T1 3 3 4 4 4 4 5 5 5 5 6 6 7
T2 3 3 3 4 4 4 4
T3 3 3 3 3 4 4 4 4 5 5 5 6 6
T4
T5
T6 2 3 3 3 3 4 4 4 4
T7

4
Exercice 6

1. Oui, avec cet algorithme, il y a un risque d’avoir un problème de famine : un processus de

faible priorité risque de ne pas s’exécuter si des processus plus prioritaires se présentent
constamment.
2.

P2 P2 P5 P2 P5 P2 P1 P4 P7 P1 ……. P1 P3 P6 P3 P6 P3 P6
0 1 2 3 4 5 6 7 8 9 10 15 16 17 18 19 20

P3 P6 P3 P3
21 24 25

Exercice 8

1. Processeur géré par FCFS et le Disque géré par FCFS

Processeur
Actif P1 P P P1 P1 P P2 P1 P1
2 1 1
Attent P2 P
e 2
Disque
Actif P1 P1 P P2 P1 P P2 P2 P1 P
2 1 1
Attent 0 P2 100 P 200 P1 300
P1 e 2
Actif x x x x x x x
Prêt
Bloqué x x x x x x x
P2
Actif x x
Prêt x x
Bloqué x x x x x x

2. Processeur géré par SJF et le Disque géré par FCFS

(même résultat car SJF est non préemptif)

Processeur
Actif P1 P P P1 P1 P P2 P1 P1
2 1 1
Attent P2 P
e 2
Disque
Actif P1 P1 P P2 P1 P P2 P2 P1 P
2 1 1
Attent 0 P2 100 P 200 P1 300
e 2

5
3. Processeur géré par SRTF et le Disque géré par FCFS

Processeur
Actif P1 P2 ... P P1 P2 P1 P1 ... ... P1 ... ... P1
1
Attente P1
Disque
Actif ... P1 P1 P2 P2 ... P2 P2 P P1 P1 P1 ...
1
Attent 0 P2 100 200 300
e