2LFIG 2015-2016 Correction série N° 2

Ce document présente une correction d'une série d'exercices en informatique portant sur les algorithmes d'ordonnancement des processus. Il s'agit d'un contrôle qui évalue la compréhension des notions de temps processeur, temps d'attente, temps d'exécution, ainsi que la mise en œuvre et l'analyse de différents algorithmes : FIFO, File de priorité, Round Robin, Shortest Remaining Time Next. Les calculs de temps moyens d'exécution et d'attente sont également abordés.

Exercice I.a

On demande de calculer le temps processeur consommé par chaque processus, en utilisant la formule :

Temps processeur consommé = Nombre de files d’attente consommées (Fils parcourues si le système applique le recyclage)

Les processus sont notés P1, P2, P3, P4, P5, P6. Les résultats donnés sont :

• TC1 = 0Q
• TC2 = 3Q
• TC3 = 2Q
• TC4 = < 1Q
• TC5 = 2Q
• TC6 = 1Q

Réponse : Le temps processeur consommé par chaque processus est celui indiqué ci-dessus.

Exercice I.b

Il s'agit de déterminer le temps d'attente de chaque processus, défini comme le temps nécessaire avant que le processus devienne actif (chargé dans le processeur).

Les temps d'attente sont exprimés en multiples du quantum Q :

• TA1 = < Q (entre 0 et Q)
• TA2 = 9Q
• TA3 = 4Q
• TA4 = 0Q
• TA5 = 5Q
• TA6 = 1Q

Réponse : Les temps d'attente sont ceux indiqués ci-dessus.

Exercice I.c

Après 2 quantum (2Q), on observe la situation du recyclage des processus dans les files d'attente et le processeur. La figure montre l'ordre des processus dans les files FP1 à FP4, ainsi que le processus actif dans le processeur.

On peut déduire que le système applique un recyclage des files d'attente, avec les processus P2, P5, P3, P1, P4 dans les files, et P6 dans le processeur.

Réponse : Après 2Q, la répartition des processus dans les files et le processeur est conforme à la description donnée.

Exercice I.d

On distingue deux configurations selon la politique d'ordonnancement :

Cas 1 : Politique sans préemption

Chaque processus respecte le temps qui lui est alloué (quantum). Le recyclage des files d'attente est maintenu, avec les processus P2, P5, P3, P1, P4 dans les files, P6 dans le processeur, et P7 en attente.

Cas 2 : Politique avec préemption

Le processus ne respecte pas le quantum Q, donc l'arrivée de P7 provoque une coupure. P6 est déplacé dans la file FP1 et le processeur est donné à P7, ce qui signifie que P7 a une priorité plus élevée.

Réponse : La politique sans préemption respecte le quantum, tandis que la politique avec préemption interrompt un processus pour donner la priorité à un nouveau processus.

Exercice II.a

On calcule les temps d'exécution (TE) et le temps moyen d'exécution (TME) pour trois processus selon différents algorithmes :

Formules utilisées :

• Temps d’attente = Temps de début de calcul – Temps de soumission
• Temps d’exécution = Temps de calcul + Temps d’attente
• Temps moyen d’exécution = (∑ Temps d’exécution des processus) / Nombre de processus

Algorithme First In First Out (FIFO)

• TEp1 = 3 + 0 = 3
• TEp2 = 4 + 4 = 8
• TEp3 = 2 + 2 = 4

Temps moyen d’exécution :

TME = (3 + 8 + 4) / 3 = 15 / 3 = 5

Algorithme File de priorité

• TEp1 = 7 + 2 = 9
• TEp2 = 0 + 4 = 4
• TEp3 = 3 + 3 = 6

Temps moyen d’exécution :

TME = (9 + 4 + 6) / 3 = 19 / 3 ≈ 6.3

Algorithme Round Robin

• TEp1 = 3 + 2 = 5
• TEp2 = 3 + 4 = 7
• TEp3 = 2 + 3 = 5

Temps moyen d’exécution :

TME = (5 + 7 + 5) / 3 = 17 / 3 ≈ 5.7

Algorithme Shortest Remaining Time Next

• TEp1 = 1 + 2 = 3
• TEp2 = 3 + 4 = 7
• TEp3 = 1 + 3 = 4

Temps moyen d’exécution :

TME = (3 + 7 + 4) / 3 = 14 / 3 ≈ 4.7

Réponse : Le meilleur temps moyen d'exécution est obtenu avec l'algorithme Shortest Remaining Time Next (4.7).

Exercice II.b

Calcul des temps d’attente (TA) et du temps moyen d’attente (TMA) pour les mêmes algorithmes :

Algorithme First In First Out (FIFO)

• TAp1 = 0
• TAp2 = 3
• TAp3 = 2

Temps moyen d’attente :

TMA = (0 + 3 + 2) / 3 = 5 / 3 ≈ 1.7

Algorithme File de priorité

• TAp1 = 0
• TAp2 = 0
• TAp3 = 0

Temps moyen d’attente :

TMA = 0 / 3 = 0

Algorithme Round Robin

• TAp1 = 0
• TAp2 = 1
• TAp3 = 1

Temps moyen d’attente :

TMA = (0 + 1 + 1) / 3 = 2 / 3 ≈ 0.7

Algorithme Shortest Remaining Time Next

• TAp1 = 0
• TAp2 = 3
• TAp3 = 2

Temps moyen d’attente :

TMA = (0 + 3 + 2) / 3 = 5 / 3 ≈ 1.7

Réponse : Le temps moyen d’attente le plus faible est obtenu avec la File de priorité (0).

Exercice II.2

On considère quatre processus avec les triplets (temps d’arrivée, temps de calcul, priorité) :

• P1 = (1, 2, 2)
• P2 = (0, 5, 4)
• P3 = (2, 4, 5)
• P4 = (3, 10, 1)

On applique différents algorithmes en respectant l'ordre imposé par l'énoncé : P1, P2, P3, P4.

Algorithme First In First Out (FIFO)

• TEp1 = 2
• TEp2 = 8
• TEp3 = 10
• TEp4 = 19
• TAp1 = 0
• TAp2 = 3
• TAp3 = 6
• TAp4 = 9

Temps moyen d’exécution :

TME = (2 + 8 + 10 + 19) / 4 = 39 / 4 = 9.75

Temps moyen d’attente :

TMA = (0 + 3 + 6 + 9) / 4 = 18 / 4 = 4.5

Algorithme Shortest Remaining Time Next

• TEp1 = 6
• TEp2 = 5
• TEp3 = 9
• TEp4 = 18
• TAp1 = 4
• TAp2 = 0
• TAp3 = 5
• TAp4 = 8

Temps moyen d’exécution :

TME = (6 + 5 + 9 + 18) / 4 = 39 / 4 = 9.5

Temps moyen d’attente :

TMA = (4 + 0 + 5 + 8) / 4 = 17 / 4 = 4.25

Algorithme Round Robin (Quantum = 1)

• TEp1 = 6
• TEp2 = 13
• TEp3 = 12
• TEp4 = 18
• TAp1 = 1
• TAp2 = 0
• TAp3 = 1
• TAp4 = 1

Temps moyen d’exécution :

TME = (6 + 13 + 12 + 18) / 4 = 49 / 4 = 12.25

Temps moyen d’attente :

TMA = (1 + 0 + 1 + 1) / 4 = 3 / 4 = 0.75

Algorithme File de priorité (Quantum = 1)

• TEp1 = 10
• TEp2 = 5
• TEp3 = 7
• TEp4 = 18
• TAp1 = 8
• TAp2 = 0
• TAp3 = 3
• TAp4 = 8

Temps moyen d’exécution :

TME = (10 + 5 + 7 + 18) / 4 = 40 / 4 = 10

Temps moyen d’attente :

TMA = (8 + 0 + 3 + 8) / 4 = 19 / 4 = 4.75

Réponse : Le meilleur temps moyen d’exécution est obtenu avec Shortest Remaining Time Next (9.5), et le meilleur temps moyen d’attente avec Round Robin (0.75).

Exercice III.a

On donne les temps d’exécution (TE) des processus P1 à P4 :

• TEp1 = 230
• TEp2 = 300
• TEp3 = 280
• TEp4 = 340

Temps moyen d’exécution :

TME = (230 + 300 + 280 + 340) / 4 = 1150 / 4 = 287.5

Réponse : Le temps moyen d’exécution est 287.5.

Exercice III.b

On donne les temps d’attente (TA) des processus P1 à P4 :

• TAp1 = 0
• TAp2 = 40
• TAp3 = 70
• TAp4 = 140

Temps moyen d’attente :

TMA = (0 + 40 + 70 + 140) / 4 = 250 / 4 = 62.5

Réponse : Le temps moyen d’attente est 62.5.

Exercice IV.a

On demande de préciser la politique d’ordonnancement et la gestion des périphériques E/S.

Réponse : FIFO + Chacun à son périphérique E/S.

Exercice IV.b

On considère l’algorithme Round Robin avec quantum Q=5, chaque processus ayant son propre périphérique E/S.

Réponse : RR (Q=5) + Chacun à son périphérique E/S.

Exercice IV.c

On considère l’algorithme Round Robin avec quantum Q=5, mais tous les processus partagent le même périphérique E/S.

Réponse : RR (Q=5) + Même périphérique E/S.

Méthode

Ce contrôle récompense la maîtrise des formules fondamentales du temps d’attente, du temps d’exécution et du temps moyen, ainsi que la capacité à appliquer correctement différents algorithmes d’ordonnancement des processus. Il est essentiel de suivre rigoureusement les définitions et notations données dans l’énoncé, notamment pour le calcul des temps d’attente et d’exécution.

Les erreurs fréquentes sanctionnées sont :

• Confondre temps d’attente et temps d’exécution.
• Ne pas respecter l’ordre imposé des processus lorsque demandé.
• Omettre les étapes de calcul intermédiaires, ce qui empêche de vérifier la cohérence des résultats.
• Ne pas appliquer correctement les règles spécifiques à chaque algorithme (par exemple, la préemption dans Round Robin ou Shortest Remaining Time Next).

Pour réussir, il faut également savoir analyser qualitativement les politiques d’ordonnancement, notamment la différence entre préemption et non-préemption, et comprendre l’impact du quantum sur la répartition du temps processeur.