Ce document, conçu pour les étudiants universitaires en informatique, présente une série d'exercices pratiques (TD) consacrés à l'ordonnancement des processus et à la programmation concurrente dans le cadre des systèmes d'exploitation. Il vise à approfondir la compréhension des mécanismes d'exécution et de gestion des processus.
Il couvre une variété d'algorithmes d'ordonnancement, incluant le Round-Robin, le SRTF, l'EDF et l'ordonnancement par priorité préemptive. Les exercices explorent également la gestion des processus fils, l'utilisation des sémaphores, ainsi que le calcul des temps de réponse, d'attente et de vie des processus, avec des analyses de diagrammes de Gantt.
Travaux Dirigés sur l'Ordonnancement des Processus
Ce document, issu des cours de l'École Nationale des Sciences de l’Informatique pour l'Année Universitaire 2017/2018, se concentre sur les Systèmes d’exploitation et la Programmation Concurrente. Il propose une série d'exercices pratiques pour approfondir la compréhension des mécanismes d'ordonnancement.
Exercice 1 : Ordonnancement Round-Robin et Gestion des Processus Fils
(Examen de rattrapage 06/2013) On considère trois (3) processus P1, P2, P3 dont les durées d’exécution sont respectivement 6, 4 et 8 unités de temps. On fait les hypothèses suivantes :
- H1 : Après 1 unité de temps d’exécution, le processus P2 crée un processus fils (qu’on appellera P4) dont la durée d’exécution est de 3 unités de temps.
- H2 : Le processus P4, après 2 unités de temps d’exécution, crée à son tour un nouveau processus fils P5, dont la durée d’exécution est de 2 unités de temps.
- H3 : Un processus ayant créé un fils doit se bloquer jusqu’à la terminaison de son processus fils.
Questions :
-
En supposant que tous les processus sont gérés en utilisant l'ordonnancement « Round-Robin » avec un quantum égal à 2 unités de temps :
- Dessinez le diagramme de Gantt.
- Déduisez les temps d’arrivée des processus P4 et P5 ainsi que les temps de réponse de chaque processus.
-
On relâche maintenant l’hypothèse H3 et on considère qu’un processus ayant créé un fils continue de s’exécuter, mais qu'à sa fin il doit se bloquer en attente de son fils. Reprenez la question 1 pour cette nouvelle hypothèse.
Exercice 2 : Comparaison d'Algorithmes d'Ordonnancement Préemptifs
(Examen de rattrapage 06/2011) Considérons les 6 processus suivants, à exécuter sur un monoprocesseur :
| Processus | Temps d’arrivée (ms) | Temps de traitement (ms) | Priorité |
|---|---|---|---|
| P1 | 0 | 10 | 2 (Argent) |
| P2 | 2 | 8 | 1 (Or) |
| P3 | 3 | 3 | 3 (Bronze) |
| P4 | 10 | 4 | 2 (Argent) |
| P5 | 12 | 1 | 3 (Bronze) |
| P6 | 15 | 4 | 1 (Or) |
Questions :
- Donnez les diagrammes de Gantt montrant l’exécution de ces différents processus en utilisant les algorithmes d’ordonnancement préemptifs suivants : à priorité ; et SRTF (Shortest Remaining Time First).
- Lequel des algorithmes d’ordonnancement de la question 1) a fourni le temps de séjour moyen le plus bas ? Déduisez, pour chaque processus, le temps d’attente.
Exercice 3 : Ordonnancement Préemptif à Priorité avec Sémaphores
(Examen 01/2011) Dans cet exercice, on suppose un ordonnanceur qui admet les caractéristiques suivantes :
- Plus la valeur de priorité est grande, plus la priorité est élevée.
- L’ordonnancement est basé sur une priorité préemptive.
Soient trois processus P1, P2 et P3, ayant les caractéristiques et les codes suivants :
Processus P1 (Priorité = 1, prêt à t=0)
- S’exécute pendant 2 unités de temps
- Fait P(S1)
- S’exécute pendant 2 unités de temps
- Fait V(S1)
- S’exécute pendant 1 unité de temps
Processus P2 (Priorité = 2, prêt à t=4)
- S’exécute pendant 1 unité de temps
- Fait V(S2)
- S’exécute pendant 1 unité de temps
Processus P3 (Priorité = 3, prêt à t=3)
- S’exécute pendant 2 unités de temps
- Fait P(S2)
- S’exécute pendant 2 unités de temps
- Fait P(S1)
- S’exécute pendant 1 unité de temps
Où "u" est égale à 1 unité de temps, S1 et S2 sont des sémaphores dont les valeurs initiales sont respectivement 1 et 0, et les opérations P et V s’exécutent pendant un temps nul.
Questions :
- Donnez sous la forme d’un tableau commenté la séquence d’exécution de ces trois processus. À t=0, c’est P1 qui démarre son exécution.
- Donnez le diagramme de Gantt correspondant à cet ordonnancement.
Exercice 4 : Ordonnancement Round-Robin avec Temps de Commutation
(Devoir Surveillé 11/2010) On considère trois (3) processus P1, P2, P3 dont les durées d’exécution sont respectivement 6, 4 et 8 unités de temps. On fait l’hypothèse suivante : après 1 unité de temps d’exécution, le processus P2 crée, par fork(), un processus fils (P4) dont la durée d’exécution est de 3 unités de temps. Le processus P4, après 2 unités de temps d’exécution, crée à son tour un nouveau processus fils P5, dont la durée d’exécution est de 2 unités de temps. On admet qu’un processus ayant créé un fils doit se bloquer jusqu’à la terminaison de son processus fils.
En supposant que tous les processus sont gérés en utilisant la politique d’ordonnancement « Round-Robin » avec un quantum égal à 2 unités de temps et un temps de commutation qui est égal à 1 unité de temps.
Questions :
- Dessinez le diagramme de Gantt.
- Déduisez pour chaque processus : le temps d’attente et le temps de séjour.
Exercice 5 : Ordonnancement EDF (Earliest Deadline First)
(Examen 01/2010) L’ordonnancement EDF (Earliest Deadline First) est un algorithme d’ordonnancement temps réel de processus. À chaque fois qu’un processus demande du temps CPU, il doit préciser une échéance (une date limite > 0). Le processus doit avoir obtenu son temps CPU avant d’atteindre la date limite. L’ordonnanceur vise à satisfaire les demandes avant leurs échéances.
Pour ce faire, il gère une liste des processus prêts, classés par ordre croissant des échéances. L’algorithme exécute le premier processus de la liste, qui correspond à celui dont l’échéance est la plus proche. Si deux processus ont la même échéance, l’ordonnanceur sélectionne le plus prioritaire.
Lorsqu’un processus devient prêt ou arrive dans le système, le système vérifie si son échéance est antérieure ou égale à celle du processus en cours d’exécution. Le processus en cours est préempté pour l’une des deux raisons suivantes :
- L’échéance du processus en cours est plus lointaine que celle d’un processus prêt.
- L’échéance du processus en cours est la même que celle d’un processus prêt plus prioritaire.
Considérez trois processus A, B et C suivants :
- A demande le CPU toutes les 20 ms et requiert à chaque fois 4 ms de temps CPU.
- B demande du temps CPU toutes les 30 ms et requiert à chaque fois 10 ms.
- C demande du temps CPU toutes les 40 ms et a besoin à chaque fois 20 ms de temps CPU.
- A est supposé plus prioritaire que B, qui est, à son tour, plus prioritaire que C.
Supposons qu’au départ, les processus sont prêts et que l’échéance de chaque demande est la date de la prochaine demande. Par exemple, pour A, les dates d’échéances sont successivement 20, 2*20, 3*20, ...
Question :
Donnez le diagramme de Gantt pour les 90 premières ms, en précisant à chaque fois le contenu de la file d’attente des processus prêts.
Exercice 6 : Ordonnancement à Priorité Préemptive avec Entrées/Sorties (E/S) Disque
(Examen 01/2008) On considère un système monoprocesseur et les 4 processus P1, P2, P3 et P4 qui effectuent du calcul et des E/S (disque) selon les temps donnés ci-dessous :
| Processus | Phases d'exécution |
|---|---|
| P1 |
|
| P2 |
|
| P3 |
|
| P4 |
|
On considère que l'ordonnancement sur le processeur se fait selon une politique de priorité préemptive : le processus élu à un instant t est le processus prêt de plus forte priorité. On donne la hiérarchie des priorités : priorité (P1) > priorité (P3) > priorité (P2) > priorité (P4).
On suppose que l'ordre de service des requêtes d'E/S pour le disque se fait également selon la priorité des processus : le processus commençant une E/S est celui de plus forte priorité parmi ceux en état d'attente du disque. Une opération d'E/S commencée ne peut pas être préemptée.
Questions :
- Donnez le chronogramme d'exécution des 4 processus P1, P2, P3 et P4. Vous distinguerez les états des processus : Prêt, Actif et Bloqué et vous indiquerez le contenu des files d’attente des processus (attente processeur et attente du disque). Pour vous guider, la première unité de temps est déjà portée sur le chronogramme.
- Justifiez votre raisonnement, en expliquant les transitions des processus.
- Donnez le temps de séjour moyen obtenu.
Foire Aux Questions (FAQ) sur l'Ordonnancement des Processus
Qu'est-ce qu'un algorithme d'ordonnancement de processus ?
Un algorithme d'ordonnancement de processus est une méthode utilisée par le système d'exploitation pour décider quel processus doit être exécuté par le CPU à un moment donné et pour quelle durée. Il vise à optimiser l'utilisation du CPU, le temps de réponse, le débit et à minimiser le temps d'attente.
Quelle est la différence entre l'ordonnancement préemptif et non préemptif ?
Dans l'ordonnancement préemptif, un processus en cours d'exécution peut être interrompu par un autre processus de plus haute priorité ou par l'expiration d'un quantum de temps. En ordonnancement non préemptif, une fois qu'un processus commence à s'exécuter, il continue jusqu'à ce qu'il se termine ou qu'il se bloque volontairement (par exemple, pour une opération d'entrée/sortie).
Qu'est-ce qu'un diagramme de Gantt en ordonnancement ?
Un diagramme de Gantt est une représentation graphique de la séquence d'exécution des processus au fil du temps sur un ou plusieurs processeurs. Il permet de visualiser les états des processus (exécution, attente, bloqué) et de calculer des métriques comme le temps d'attente, le temps de réponse et le temps de séjour (ou temps de rotation).