Équilibre préemptif vs non préemptif dans l'ordonnancement de processus

Ce document porte sur l'ordonnancement de processus, sous forme d'un corrigé d'exercices issus d'une évaluation universitaire. Il teste les compétences en compréhension des mécanismes d'ordonnancement préemptif et non préemptif, en analyse de performances, en gestion des priorités, et en résolution de problèmes liés aux temps d'exécution et d'attente des processus.

Solution 1

1. Identifier les erreurs dans la file des processus prêts.

Il est indiqué qu'il existe un pointeur dans la file des processus prêts qui pointe vers un processus déjà terminé, ce qui est incorrect car un processus terminé ne doit plus être dans la file des prêts.

De plus, il existe un pointeur sur un processus bloqué dans la file des processus prêts, ce qui est également une erreur puisque les processus bloqués ne doivent pas être dans la file des prêts.

Conclusion : La file des processus prêts ne doit contenir que des processus prêts à s'exécuter, ni terminés ni bloqués.

2. a. Représentation des intervalles d'exécution et d'attente sur CPU1, CPU2, file d'attente et E/S.

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. Calcul du Temps de Vie Moyen (TVM) :

TVM = (8 + (12 - 2) + (9 - 3.5)) / 3 = (8 + 10 + 5.5) / 3 = 23.5 / 3 = 7.8

Le Temps de Vie Moyen est donc 7.8 unités de temps.

Solution 2

1. Définir les ordonnancements non préemptifs et préemptifs.

- Non préemptifs : Lorsqu’un processus est élu, il conserve le processeur jusqu’à ce qu’il se bloque ou se termine.

- Préemptifs : Un processus élu peut être suspendu avant sa fin ou son blocage, permettant à un autre processus de prendre le processeur.

2. Expliquer les conséquences de chaque type d'ordonnancement.

- Non préemptifs : Le processus élu ne libère jamais volontairement le processeur, ce qui peut entraîner un problème de famine pour les autres processus.

- Préemptifs : Le processeur est retiré du processus élu après un temps fini, permettant aux autres processus d’être élus et évitant la famine.

3. a. Ordonnancement des threads dans deux cas :

Ordonnancement 1 : (T11,1) (T21,2) (T22,2) (T12,2) (T23,1) (T21,1) (T12,1)

Temps de service (TS) pour P1 = 10

TS pour P2 = 9

3. b. Ordonnancement 2 :

(P1 : T11,T12 2) (P2 : T21,T22,2) (P1 : T12, 2) (P2 : T23,T21,2) (P2 : T22,T21,2)

TS pour P1 = 6

TS pour P2 = 10

3. c. Analyse comparative :

Le processus P1 termine plus rapidement dans le deuxième cas. En effet, dans le premier cas, si un thread ne consomme pas tout son quantum, le processeur peut être alloué à un thread d’un autre processus. Dans le deuxième cas, le processeur est alloué à un autre thread du même processus, ce qui permet à P1 d’avancer plus vite.

Conclusion : Le deuxième ordonnancement est plus favorable à P1.

Solution 3

1. Définition des groupes et méthodes d'ordonnancement :

• Groupe A : Round Robin avec quantum Q = 3
• Groupe B : Priorité avec Q = 3 et Priorités PA = PS > PT

2. Calcul des temps moyens :

• Groupe A : TsA = 28, TsS = 10, TsT = 17, Temps moyen TsM = 18.33
• Groupe B : TsA = 25, TsS = 14, TsT = 26, Temps moyen TsM = 21.67

3. Analyse :

Le groupe A a de meilleures performances en termes de temps moyens. Cependant, le groupe B privilégie les processus A et S, considérant que le processus de transfert T est secondaire. Les temps de séjour des processus A et S sont inférieurs dans la solution B, ce qui est important.

Conclusion : Il est préférable de choisir la solution B pour respecter la priorité des processus.

Solution 4

a) Représentation chronologique des processus A, B et C :

B A 0 10

C A B C A B A 25 30 40 55 60 70 80 95 105

b) Respect des échéances :

Exemple : Processus A (CPU 25, échéance 30) et processus B (CPU 30, échéance 40).

Le processus B ne respecte pas son échéance car 25 + 30 > 40.

Conclusion : Il y a non respect d’échéance pour le processus B.

Solution 5

1. Analyse des événements d'ordonnancement :

Chronologie des événements : Ff1 0 1 3 4 7 8 9 10 14 16 17 18 19 20 21 23 24 25 26

ff2 rr1 ff4 ff2 ff1 Ff2 rr2 rr1 rr2 rr1 ff2 rr2 ff1 o ff3 ff2 Ff1

2. a) Ordonnancement des processus :

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) Inversion de priorité :

À l’instant 4, une inversion de priorité de 5 unités de temps survient. Le processus A, qui a la priorité la plus élevée, est bloqué par le processus C qui utilise la ressource Q entre 4-5 et 7-9, et par le processus B qui suspend C entre 5-7.

Conclusion : Une inversion de priorité est présente entre les instants 4 et 9.

Solution 6

a) Priorités attribuées :

PrA = 1, PrB = 3, PrC = 2, où 3 est la priorité la plus forte.

b) Ordonnancement des processus :

B C A B A

0 1 3 5 6 10 11 13 14 15 16 20 21 23 25 26 29 30

c) Représentation temporelle :

B C A

0 1 3 10 11 13 15 16 20 21 23 25 26 30

d) Respect des contraintes temporelles :

Oui dans le cas a).

Non dans le cas b), car B ne respecte pas sa contrainte temporelle sur la période 2 (entre 5 et 10).

Conclusion : Le respect des contraintes dépend de l’ordonnancement choisi.

Solution 7

Ordonnancement des processus A, B et C avec leurs intervalles :

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)

Ordre : A B C A C B A B C A C B A

Solution 8

1. Définition et comparaison des temps moyens :

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, alors TAM1 ≤ TAM2.

2. Ordonnancement avec quantum qt et reste r :

(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)

Temps moyen TSM1 = [(10 qt + r) + (10 qt + 2r) + (10 qt + 3r) + (10 qt + 4r) + (10 qt + 5r)] / 5 = 10 qt + 3 r

3. Autre ordonnancement :

(P1, 2qt + r) (P2, 2qt + r) (P3, 2qt + r) (P4, 2qt + r) (P5, 2qt + r)

TSM2 = [(2 qt + r) + 2(2 qt + r) + 3(2 qt + r) + 4(2 qt + r) + 5(2 qt + r)] / 5 = 6 qt + 2 r

TSM2 ≤ TSM1

Conclusion : Le second ordonnancement offre un temps moyen inférieur ou égal au premier.

Solution 9

1. Séquence des processus et durées :

(A,7) (B,6) (C,5) (A,5) (D,1) (B,4) (D,2)

2. Nouvelle séquence :

(A,5) (B,5) (A,2) (C,5) (B,1) (D,1) (A,5) (B,4) (D,2)

Temps total pour chaque processus :

• A : 24
• B : 27
• C : 8
• D : 18

3. Séquence répétée :

(A,5) (B,5) (A,2) (C,5) (B,1) (D,1) (A,5) (B,4) (D,2)

4. Données insuffisantes pour répondre précisément à cette question.

Méthodes et conseils

Ce corrigé récompense la maîtrise des notions d'ordonnancement préemptif et non préemptif, la capacité à analyser des séquences d'exécution, à calculer des temps moyens et à identifier les problèmes liés aux priorités et aux contraintes temporelles.

Les erreurs fréquentes à éviter sont :

• Confondre les états des processus (prêt, bloqué, terminé) dans les files d'attente.
• Omettre les étapes intermédiaires dans les calculs de temps moyen ou de durée de service.
• Ne pas justifier les choix d'ordonnancement ou les conséquences sur les performances.
• Ignorer les inversions de priorité et leurs impacts sur l'exécution.
• Ne pas respecter les conventions propres au sujet, notamment dans les notations et définitions des priorités ou des temps.

Il est essentiel de toujours expliciter son raisonnement et de vérifier la cohérence des résultats avec les données fournies.