Ce document constitue le premier Travaux Dirigés (TD1) du cours de Systèmes d'Exploitation Avancés, conçu pour les étudiants en première année d'ingénierie. Il a pour objectif de réviser et d'approfondir les concepts fondamentaux liés à l'ordonnancement des processus.
Il aborde les notions suivantes :
- Les définitions clés des processus, des threads et de leurs états.
- L'étude et l'application d'algorithmes d'ordonnancement classiques (FCFS, SJF, Tourniquet).
- L'exploration de l'ordonnancement basé sur les priorités, statiques et dynamiques.
- L'analyse des critères d'évaluation de l'efficacité des algorithmes d'ordonnancement.
L'Ordonnancement des Processus : Concepts et Algorithmes
L'ordonnancement des processus est une fonction essentielle des systèmes d'exploitation, permettant de gérer et d'allouer les ressources du processeur (CPU) entre les différentes tâches en cours. Ce mécanisme assure une utilisation efficace du CPU et une bonne réactivité du système.
Exercice 1 : Généralités sur l'Ordonnancement des Processus
Cette section aborde les concepts fondamentaux de l'ordonnancement, essentiels pour comprendre le fonctionnement interne des systèmes d'exploitation.
- Qu’est-ce qu’un processus ?
- Qu’est-ce qu’un PCB ?
- Qu’est-ce qu’un thread ?
- Quelle est la différence entre un processus et un thread ?
- Qu’est-ce qu’un PID ? PPID ?
- Quels sont les différents états d’un processus ? Quelles sont les transitions entre ces états ?
- Qu’est-ce que la commutation de contexte ?
- Quels sont les différents types d’algorithmes d’ordonnancement ?
- Quand est-ce que l’ordonnanceur est invoqué ?
- Comment juger de l’efficacité d’un algorithme d’ordonnancement ?
- Discuter les différents algorithmes (FCFS, SJF) et leur mise en œuvre pratique.
- Définir interruption, préemption et déroutement et discuter la différence.
Un processus représente une instance d'un programme en exécution, tandis qu'un thread est une unité d'exécution plus légère au sein d'un processus. Le PCB (Process Control Block) contient toutes les informations nécessaires pour gérer un processus. La commutation de contexte est l'opération qui consiste à sauvegarder l'état d'un processus et à charger l'état d'un autre.
Exercice 2 : Application des Algorithmes d'Ordonnancement
Cet exercice permet d'appliquer les concepts d'ordonnancement à travers des scénarios concrets et de visualiser leur exécution à l'aide de diagrammes de Gantt.
Ordonnancement des processus Cinq travaux A, B, C, D et E arrivent pratiquement en même temps dans un centre de calcul. Leur temps d’exécution respectif est estimé à 10, 6, 2, 4 et 8 secondes. Tracez le diagramme de Gantt et déterminez le temps moyen de rotation pour chacun des algorithmes d’ordonnancement suivants. Ne tenez pas compte du temps perdu lors de la commutation des processus.
- Premier arrivé, premier servi FCFS (exécution dans l’ordre 10, 6, 2, 4, 8) ;
- Plus court d’abord SJF ;
- Tourniquet (quantum q = 4 s).
Le diagramme de Gantt est un outil visuel qui représente la séquence d'exécution des processus sur le CPU. Le temps de rotation moyen (turnaround time) mesure le temps total qu'un processus passe dans le système, de son arrivée à sa complétion.
L'algorithme FCFS (First-Come, First-Served) exécute les processus dans l'ordre de leur arrivée. SJF (Shortest Job First) privilégie les processus ayant le temps d'exécution le plus court. Le Tourniquet (Round Robin) alloue un petit quantum de temps à chaque processus, assurant une certaine équité.
Exercice 3 : Analyse des Performances et Problèmes d'Ordonnancement
Cette section explore l'impact des paramètres d'ordonnancement sur les performances du système et les défis liés à la gestion des priorités.
Questions de compréhension
- Quel est l'effet de la diminution du quantum sur les performances de l'algorithme RR (tourniquet)? Et son augmentation ?
- Les algorithmes d’ordonnancement basés sur des priorités peuvent engendrer la famine (non exécution) des processus à faible priorité. Comment peut-on éviter ce problème ?
- Soit un système sur lequel les processus s'exécutent en moyenne pendant un temps de T secondes. La commutation de processus nécessite C secondes. L’ordonnancement est circulaire (RR ou Tourniquet) avec un quantum de Q secondes. Donnez une interprétation pour chacun des cas suivants :
- Q > T
- C < Q < T
- Q = C
- Q tend vers + ∞
- Q tend vers 0
Un quantum trop petit augmente le nombre de commutations de contexte, ce qui réduit l'efficacité globale. Un quantum trop grand peut dégrader la réactivité pour les processus interactifs. La famine peut être évitée par des techniques comme le vieillissement (aging), où la priorité des processus augmente avec le temps d'attente.
Exercice 4 : Ordonnancement avec Priorité Dynamique
Cet exercice se concentre sur l'ordonnancement des processus en utilisant des priorités, en particulier comment elles peuvent évoluer dynamiquement pour optimiser la performance du système.
On considère l’ensemble des processus suivants :
| Processus | Date d’arrivée | Temps CPU | Priorité |
|---|---|---|---|
| P1 | 7h00 | 10 mn | 2 |
| P2 | 7h00 | 15 mn | 3 |
| P3 | 7h03 | 8 mn | 4 |
| P4 | 7h10 | 18 mn | 5 |
A- On suppose qu’on utilise un algorithme d’ordonnancement basé sur la priorité. Donnez le diagramme de Gantt pour les processus donnés.
B- On voudrait que la priorité des processus soit dynamique au cours du temps. Ainsi, pour calculer la priorité d’un processus, on utilise la formule suivante :
Priorité = (Temps d'attente + Temps CPU restant) / Temps CPU
Remarque : Lors des calculs, on arrondira suivant l’exemple suivant : 3.5 ou 3.6 -> 4 ; 3.1 ou 3.4 -> 3.
- Donnez le diagramme de Gantt sachant que la priorité est recalculée toutes les 5 minutes.
- Calculez le temps d’attente moyen ainsi que le temps de rotation moyen.
- Comparez les résultats obtenus par rapport à ceux obtenus avec l’algorithme de priorité classique.
L'ordonnancement par priorité dynamique permet d'ajuster la priorité d'un processus en fonction de son comportement ou de son temps d'attente, offrant une plus grande flexibilité par rapport aux priorités statiques.
Questions Fréquemment Posées (FAQ)
Qu'est-ce que l'ordonnancement préemptif et non préemptif ?
L'ordonnancement préemptif permet au système d'exploitation d'interrompre l'exécution d'un processus pour en exécuter un autre, généralement de priorité plus élevée ou lorsque son quantum de temps est écoulé. L'ordonnancement non préemptif, en revanche, laisse un processus s'exécuter jusqu'à sa complétion ou jusqu'à ce qu'il se mette en attente d'une ressource.
Pourquoi le concept de thread est-il important dans les systèmes modernes ?
Les threads permettent à un programme d'exécuter plusieurs tâches simultanément au sein d'un même processus, partageant les mêmes ressources mémoire. Cela améliore l'efficacité des applications, la réactivité et l'utilisation des architectures multiprocesseurs, sans le coût de commutation de contexte plus élevé associé aux processus.
Comment la famine de processus peut-elle être évitée dans les systèmes d'ordonnancement basés sur les priorités ?
La famine (starvation) se produit lorsqu'un processus à faible priorité ne parvient jamais à s'exécuter à cause de l'arrivée constante de processus à haute priorité. Ce problème peut être résolu par des mécanismes comme le "vieillissement" (aging), où la priorité d'un processus augmente progressivement avec son temps d'attente, ou en utilisant des algorithmes d'ordonnancement combinant priorités et temps de rotation comme le Round Robin.