2LFIG 2015-2016 Correction série N° 2
2LFIG 2015-2016 Correction série N° 2
Operating System Scheduling Algorithms · exam
Voir tous les documents en programmationTous les exercices en programmation
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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 :
Réponse : Le temps processeur consommé par chaque processus est celui indiqué ci-dessus.
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 :
Réponse : Les temps d'attente sont ceux indiqués ci-dessus.
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.
On distingue deux configurations selon la politique d'ordonnancement :
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.
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.
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 moyen d’exécution :
TME = (3 + 8 + 4) / 3 = 15 / 3 = 5
Temps moyen d’exécution :
TME = (9 + 4 + 6) / 3 = 19 / 3 ≈ 6.3
Temps moyen d’exécution :
TME = (5 + 7 + 5) / 3 = 17 / 3 ≈ 5.7
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).
Calcul des temps d’attente (TA) et du temps moyen d’attente (TMA) pour les mêmes algorithmes :
Temps moyen d’attente :
TMA = (0 + 3 + 2) / 3 = 5 / 3 ≈ 1.7
Temps moyen d’attente :
TMA = 0 / 3 = 0
Temps moyen d’attente :
TMA = (0 + 1 + 1) / 3 = 2 / 3 ≈ 0.7
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).
On considère quatre processus avec les triplets (temps d’arrivée, temps de calcul, priorité) :
On applique différents algorithmes en respectant l'ordre imposé par l'énoncé : P1, P2, P3, P4.
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
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
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
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).
On donne les temps d’exécution (TE) des processus P1 à P4 :
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.
On donne les temps d’attente (TA) des processus P1 à P4 :
Temps moyen d’attente :
TMA = (0 + 40 + 70 + 140) / 4 = 250 / 4 = 62.5
Réponse : Le temps moyen d’attente est 62.5.
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.
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.
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.
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 :
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.