Ce document présente le deuxième travail dirigé (TD n°2) du module Systèmes d'exploitation, destiné aux étudiants universitaires de licence. Il vise à consolider les connaissances sur l'ordonnancement des processus, un mécanisme essentiel de gestion des ressources système.
Les exercices proposés permettront d'étudier :
- Les principaux algorithmes d'ordonnancement (FCFS, SJF, Tourniquet, priorité préemptible).
- L'élaboration de diagrammes de Gantt pour visualiser l'exécution.
- Le calcul des temps de rotation et d'attente moyens des processus, y compris la gestion des E/S.
Introduction aux algorithmes d'ordonnancement
L'ordonnancement des processus est une fonction essentielle des systèmes d'exploitation. Il détermine l'ordre dans lequel les processus sont exécutés par le processeur (CPU) afin d'optimiser l'utilisation des ressources et de répondre aux exigences de performance. Ces exercices pratiques visent à explorer différents algorithmes d'ordonnancement et leurs impacts sur les métriques clés comme le temps de rotation et le temps d'attente.
Exercice 1 : Ordonnancement FCFS, SJF et Tourniquet
Cinq travaux (A, B, C, D et E) arrivent pratiquement en même temps dans un centre de calcul. Leurs temps d'exécution respectifs sont estimés à 10, 6, 2, 4 et 8 secondes.
Tracez le diagramme de Gantt et déterminez le temps moyen de rotation pour les algorithmes d'ordonnancement suivants :
FCFS (First-Come, First-Served) : Le processus qui arrive en premier est exécuté en premier et s'exécute jusqu'à sa fin.
SJF (Shortest Job First) : Le processus ayant le temps d'exécution le plus court est choisi en premier. Cet algorithme peut être non-préemptif ou préemptif.
Tourniquet (Round Robin) : Chaque processus reçoit une petite unité de temps CPU, appelée quantum (ici, q = 4 s). Si le processus ne termine pas pendant son quantum, il est préempté et placé à la fin de la file d'attente des prêts.
Le temps de commutation entre les processus est négligé.
Explication des métriques :
Temps de rotation (Turnaround Time) : Durée totale passée par un processus dans le système, de son arrivée à sa complétion (inclut le temps d'exécution, d'attente et d'E/S).
Diagramme de Gantt : Une représentation graphique de l'ordonnancement des tâches sur une ligne de temps, montrant quand chaque processus est actif sur le CPU.
Exercice 2 : Ordonnancement basé sur la priorité
On considère l'ensemble des processus suivants :
| N° processus | Date d'arrivée | Temps CPU | Priorité |
|---|---|---|---|
| 1 | 07:00 | 10 min | 2 |
| 2 | 07:00 | 15 min | 3 |
| 3 | 07:03 | 8 min | 4 |
| 4 | 07:10 | 18 min | 5 |
On suppose qu'on utilise un algorithme d'ordonnancement basé sur la priorité, où les priorités sont croissantes (5 est la priorité la plus élevée, donc la plus forte).
Donnez le diagramme de Gantt correspondant.
Calculez le temps d'attente moyen ainsi que le temps de rotation moyen.
Explication des métriques :
Temps d'attente (Waiting Time) : Durée totale pendant laquelle un processus est resté dans la file d'attente, prêt à être exécuté, mais n'a pas été alloué au CPU.
Ordonnancement par priorité : L'algorithme attribue le CPU au processus ayant la priorité la plus élevée parmi les processus prêts. Il peut être préemptif ou non préemptif.
Exercice 3 : Ordonnancement préemptif avec E/S
On considère un système monoprocesseur et quatre processus (P1, P2, P3 et P4) qui effectuent du calcul (CPU) et des opérations d'entrées/sorties (E/S) avec un disque. Les processus sont disponibles dès le début (au temps 0).
Le déroulement séquentiel des phases CPU et E/S pour chaque processus est le suivant :
| Processus | Séquence des opérations (Temps en unités) |
|---|---|
| P1 | CPU (3), E/S (7), CPU (2), E/S (1), CPU (1) |
| P2 | CPU (4), E/S (3), CPU (2), E/S (1), CPU (1) |
| P3 | CPU (2), E/S (3), CPU (2), E/S (1) |
| P4 | CPU (7), E/S (3) |
L'ordonnancement sur le processeur se fait selon une politique à priorité préemptive : le processus élu à un instant t est celui qui est prêt et possède la plus forte priorité. L'ordre de priorité est le suivant : P1 > P3 > P2 > P4.
L'ordre de service des requêtes d'E/S pour le disque se fait toujours selon une politique FIFO (First-In, First-Out).
Tracez le diagramme d'état pour chaque processus (E/S, Attente, Prêt, Actif) sur une ligne de temps.
Déterminez le temps d'attente moyen obtenu.
Explication des concepts :
Priorité préemptive : Un processus avec une priorité plus élevée peut interrompre l'exécution d'un processus de priorité inférieure en cours sur le CPU.
FIFO (First-In, First-Out) : Les requêtes sont traitées dans l'ordre où elles arrivent.
États d'un processus : Un processus peut être dans différents états (Prêt, Actif/Exécution, En attente/Bloqué pour E/S).
FAQ sur l'ordonnancement des processus
Qu'est-ce qu'un diagramme de Gantt en ordonnancement de processus ?
Un diagramme de Gantt est un outil visuel qui représente la séquence et la durée d'exécution des processus sur le CPU au fil du temps. Il aide à comprendre l'ordonnancement et à calculer des métriques telles que le temps de rotation et le temps d'attente.
Quelle est la différence principale entre les algorithmes préemptifs et non préemptifs ?
Un algorithme d'ordonnancement non préemptif permet à un processus, une fois qu'il a commencé son exécution sur le CPU, de la terminer sans interruption. En revanche, un algorithme préemptif peut interrompre un processus en cours d'exécution pour allouer le CPU à un autre processus de priorité plus élevée ou dont le quantum de temps est échu.
Pourquoi le choix d'un algorithme d'ordonnancement est-il crucial pour un système d'exploitation ?
Le choix de l'algorithme d'ordonnancement est essentiel car il impacte directement la performance globale du système, l'équité entre les processus, le temps de réponse pour les utilisateurs, le débit du système (nombre de processus terminés par unité de temps) et l'efficacité de l'utilisation du CPU. Un bon ordonnancement optimise ces facteurs selon les objectifs du système.