INF3600+INF2610
Automne 2006
Partie 6 : Ordonnancement de processus
Le corrigé
Solution 1
1. Il existe, dans la file des processus prêts, un pointeur sur un processus déjà terminé.
Il existe, dans la file des processus prêts, un pointeur sur un processus bloqué.
2. a. CPU1 :(0,A,4) (4,C,7) (7,C,9) (10,B,12)
CPU2 : (2,B,5) (6,A,8)
File : (3.5,C)(4,vide)
E/S : (4,A,6) (6,B,10)
File E/S : (5,B) (6,vide)
2. b. TVM = (8+(12-2) + (9-3.5))/3 = 7.8
Solution 2
1. Non préemptifs : Lorsqu’un processus devient élu, il conserve son état jusqu’à ce qu’il se
bloque ou se termine.
Préemptifs : Un processus élu peut être suspendu avant qu’il se termine ou se bloque.
2. Non préemptifs : Le processus élu ne restituera jamais le processeur. Par conséquent, les
autres processus resteront toujours à l’état prêt (problème de famine).
Préemptifs : Le processeur sera arraché au processus élu au bout d’un certain temps fini. Ce qui
permet aux autres de passer à l’état élu.
3. a. (T11,1) (T21,2) (T22,2) (T12,2) (T23,1) (T21,1) (T12,1)
TS(P1) = 10
TS(P2) = 9
1
3. b. (P1 : T11,T12 2) (P2 : T21,T22,2) (P1 : T12, 2) (P2 : T23,T21,2) (P2 : T22,T21,2)
Advertisement
TS(P1) = 6
TS(P2) = 10
3. c. P1 termine plus rapidement dans le deuxième cas. Dans le premier cas, si un thread d’un
processus ne consomme pas son quantum, le processeur peut être alloué à un thread d’un autre
processus. Par contre, dans le deuxième cas, le processeur est alloué à un autre thread du même
processus (s’il y en a). Ce qui a permis à P1 d’exécuter plus rapidement dans le cas b).
Solution 3
1- Groupe A : Round Robin Q = 3
Groupe B : Priorité Q = 3 et PA= PS > PT
2- Groupe A : TsA = 28 TsS = 10 TsT = 17
TsM = 18.33
Groupe B : TsA = 25 TsS = 14 TsT = 26
TsM = 21.67
3- Avec leur round robin, le groupe A possède de meilleures performances que le groupe B au
niveau des temps moyens. Cependant le groupe B a tenu compte du fait que le processus de
transfert n’est qu’un processus de second plan et qu’il est important de privilégier les Processus
A et S. Les temps de séjour des processus A et S sont inférieurs avec la solution du groupe B. Il
est donc important de choisir le B.
Solution 4
a)
B
A
0 10
C
A
B
Advertisement
C A
B
A
25 30 40 55 60 70 80 95 105
2
b) Oui.
Exemple : Processus A (CPU 25, Échéance 30)
Processus B (CPU 30, Échéance 40)
Dans ce cas, il y a non respect d’échéance pour B (25+30 > 40).
Solution 5
1.
Ff
1
0 1 3 4 7 8 9 10 14 16 17 18 19 20 21 23 24 25 26
ff2 rr1 ff4 ff2 ff1 Ff
2
rr2 rr1 rr2 rr1 ff2 rr2 ff1 o
ff3 ff2 Ff
1
2.
a)
C C A A C B B C C A A
0 1 2 3 4 5 6 7 8 9 10 11
Q Q Q Q Q
b) Oui. À l’instant 4 une inversion de priorité d’une durée de 5 unités de temps survient. Le
processus A, qui possède la priorité la plus élevée, est empêché de s’exécuter par le processus C,
Advertisement
qui accède à la ressource Q entre les instants 4 et 5 et 7 et 9, et par le processus B, qui suspend le
processus C entre les instants 5 et 7.
Solution 6
a) PrA = 1, PrB = 3, PrC = 2, où 3 est la priorité la plus forte
b)
B C A B A
0 1
3 5 6 10 11 13 14 15 16 20 21 23 25 26 29 30
B C A B
B C
B
A
c)
B C A
0 1 3 10 11 13 15 16 20 21 23 25 26 30
d) Oui, dans le cas a).
Non, dans le cas b). B ne respecte pas sa contrainte temporelle sur la période 2 (entre les instants
5 et 10).
B C
B C
B
B
3
Solution 7
A(0-4)B(4-10)C(14-6)A(20-4)C(24-14)B(38-2)A(40-4)B(44-8) C(52-8)A(60-4)C(64-12)B(76-
10)A(86-4)
Advertisement
A B C A C B A B C A C B A
Solution 8
1) Posons Ai = min(qt,ci) pour i=1,n
TAM1 = [0+ (n-1)A1 + (n-2)A2 +….+ An-1] / n
TAM2 = [0+ (n-1)c1 + (n-2)c2 +….+ cn-1] / n
Comme Ai ≤ ci pour i=1,n , TAM1 ≤ TAM2.
2) (P1,qt) (P2,qt) (P3,qt) (P4,qt) (P5,qt) (P1,qt) (P2,qt) (P3,qt) (P4,qt) (P5,qt) (P1,r) (P2,r) (P3,r)
(P4,r) (P5,r)
TSM1 = [ (10 qt +r) + (10 qt +2r) + (10 qt +3r) + (10 qt + 4r) +(10qt +5r) ] /5
= 10 qt + 3 r
3) (P1, 2qt+r)(P2, 2qt+r) (P3, 2qt+r) (P4, 2qt+r) (P5, 2qt+r)
TSM2 = [(2 qt +r) + 2(2qt+r) + 3(2 qt +r) + 4(2 qt +r) + 5(2 qt +r) ] /5
= 6 qt + 2 r
TSM2 ≤ TSM1
Solution 9
1) (A,7) (B,6) (C,5) (A,5)(D,1)(B,4)(D,2)
2) (A,5) (B,5) (A,2)(C,5)(B,1)(D,1)(A,5)(B,4)(D,2)
pour A : 24
pour B : 27
pour C : 8
pour D : 18
3) (A,5) (B,5) (A,2)(C,5)(B,1)(D,1)(A,5)(B,4)(D,2)
4