Ce document de Travaux Dirigés, destiné aux étudiants universitaires de Systèmes d'Exploitation de l'Université Mohammed V, aborde un aspect fondamental de l'informatique : l'ordonnancement des processus. Il fournit une série d'exercices pratiques conçus pour approfondir la compréhension des algorithmes de répartition de l'UCT et de gestion des E/S.
Il couvre les notions suivantes :
- Les algorithmes d'ordonnancement (PAPS, SJF, Tourniquet avec/sans priorités).
- La gestion des opérations d'entrée/sortie et des changements de contexte.
- L'analyse des performances système (débit, temps de rotation, temps d'attente).
TD1 : Ordonnancement des Processus
Introduction à l'Ordonnancement des Processus
L'ordonnancement des processus est une tâche essentielle des systèmes d'exploitation qui consiste à gérer l'accès des différents processus au processeur (UCT) et aux périphériques d'entrée/sortie (E/S). L'objectif est d'optimiser l'utilisation des ressources système et de répondre aux exigences des processus en termes de temps de réponse, de débit ou de temps de rotation.
Exercice 1 : Ordonnancement avec Giclées d'UCT et E/S
On considère trois processus, A, B, C, dont l'exécution se compose d'une répétition de giclées d'UCT et d'opérations d'E/S de longueur constante. Les caractéristiques sont les suivantes :
- Pour A : 7 unités de temps (ut) d'accès à l'UCT puis 2 ut d'E/S, répétées (7 UCT, 2 E/S, 7 UCT, 2 E/S, etc.).
- Pour B : 2 ut d'UCT, 2 ut d'E/S, répétées (2 UCT, 2 E/S, 2 UCT, 2 E/S, etc.).
- Pour C : 5 ut d'UCT, 4 ut d'E/S, répétées (5 UCT, 4 E/S, 5 UCT, 4 E/S, etc.).
On supposera que A se présente en premier, suivi de B 1 ut plus tard, puis C, 1 ut après B. Il s'agit de montrer comment les trois processus vont utiliser l'UCT pendant les 30 premières unités de temps dans les cas suivants :
I. Les processus n'attendent pas pour leurs E/S (périphérique propre)
Dans ce scénario, chaque processus dispose de son propre périphérique d'E/S, ce qui signifie qu'il n'y a pas de contention pour les ressources d'E/S et les processus n'attendent pas pour leurs E/S.
- Le répartiteur fonctionne selon l'algorithme PAPS (Premier Arrivé, Premier Servi).
- Le répartiteur fonctionne selon l'algorithme SJF (Shortest Job First / Plus Court D'abord).
- Le répartiteur utilise l'algorithme du tourniquet (Round Robin), avec un quantum de 3 unités de temps.
II. Les trois processus utilisent le même périphérique d'E/S
Ici, les processus partagent le même périphérique d'E/S, et sa file d'attente est gérée par l'algorithme SJF (concernant la durée d'E/S). Le répartiteur de l'UCT utilise l'algorithme du tourniquet, avec un quantum de 3 unités de temps.
Rappel des Métriques d'Ordonnancement
- Débit (Throughput) : Le nombre de processus qui terminent leur exécution dans une unité de temps. C'est une mesure de productivité.
- Temps de rotation (Turnaround time) : Le temps total écoulé entre l'arrivée d'un processus et sa terminaison. Il inclut le temps d'exécution, le temps d'attente en file prêt et le temps d'E/S.
- Temps d'attente : La somme de tout le temps passé par un processus dans la file d'attente prête à être exécutée.
- Temps de réponse (pour les systèmes interactifs) : Le temps entre une demande et la première réponse générée par le système, souvent crucial pour l'expérience utilisateur.
Exercice 2 : Calcul du Temps de Virement avec Tourniquet
On considère cinq processus, A, B, C, D et E, devant partager l'accès à une même UCT. L'exécution de chaque processus se compose d'une seule giclée d'UCT suivie d'une opération d'E/S prenant une unité de temps. Le tableau suivant donne les instants d'arrivée et les durées des giclées d'UCT de chaque processus :
| Processus | Instant d'arrivée (ut) | Durée giclée UCT (ut) |
|---|---|---|
| A | 0 | 25 |
| B | 1 | 6 |
| C | 2 | 11 |
| D | 3 | 17 |
| E | 4 | 10 |
Calculez le temps de virement (temps de rotation) de chaque processus dans les deux cas suivants :
- Le répartiteur utilise l'algorithme du tourniquet avec un quantum de temps de 5 unités. On suppose que les changements de contexte sont instantanés.
- Le répartiteur utilise l'algorithme du tourniquet avec un quantum de 5 unités de temps. De plus, on suppose que chaque changement de contexte dure 1 unité de temps.
Exercice 3 : Partage de l'UCT avec Giclées et E/S, et Priorités
On considère quatre processus, A, B, C et D, devant partager l'accès à une même UCT. L'exécution de chaque processus se compose d'une répétition de giclées d'UCT et d'opérations d'E/S de longueur constante. Les caractéristiques sont les suivantes :
- Pour A : 6 unités de temps (ut) d'accès à l'UCT puis 3 ut d'E/S, répétées.
- Pour B : 2 ut d'UCT, 6 ut d'E/S, répétées.
- Pour C : 4 ut d'UCT, 1 ut d'E/S, répétées.
- Pour D : 1 ut d'UCT, 3 ut d'E/S, répétées.
On suppose que A se présente en premier, suivi de B (1 ut plus tard), puis C (1 ut après B), et enfin D (1 ut après C). On souhaite analyser comment les quatre processus partageront l'UCT pendant les 30 premières unités de temps, selon le type de répartiteur utilisé.
- On suppose que les processus n'attendent pas pour leurs E/S (chacun ayant son périphérique propre) et que le répartiteur applique un mécanisme de tourniquet avec priorité et un quantum de 3 ut. L'indice de priorité d'un processus est incrémenté de 1 à chaque fois qu'il quitte l'état "élu". On suppose que A, B, C et D démarrent avec le même indice de priorité initial = 1. Le processus le plus prioritaire est celui avec le plus petit indice de priorité.
- Dans cette question, on suppose qu'il existe deux périphériques d'entrées/sorties partagés par les quatre processus. A et C partagent le premier périphérique, B et D partagent le deuxième. Le répartiteur applique l'algorithme du tourniquet sans priorités avec un quantum = 4 ut. Les deux files d'attente des périphériques sont gérées par un algorithme de PAPS.
Exercice 4 : Gestion de Processus avec Tourniquet et Priorités
On considère cinq processus, A, B, C, D et E partageant une même UCT. Leurs caractéristiques sont les suivantes :
- Pour A : 6 UT d'accès à l'UCT puis 3 UT d'E/S, répétées.
- Pour B : 3 UCT, 4 E/S, répétées.
- Pour C : 3 UCT, 1 E/S, répétées.
- Pour D : 1 UCT, 3 E/S, répétées.
- Pour E : 5 UCT, 2 E/S, répétées.
Les instants d'arrivée des processus sont les suivants : A se présente en premier (t=0), suivi de B (t=1), puis C (t=2). D se présente 8 UT après C (t=10) et E 1 UT après D (t=11).
- Les cinq processus partagent le même système d'E/S.
- Le répartiteur de la file d'attente des E/S fonctionne selon l'algorithme PAPS (Premier Arrivé, Premier Servi).
- Le répartiteur de bas niveau applique le mécanisme de Round Robin (RR) avec priorité et un quantum (q) de 3 UT.
- L'indice de priorité d'un processus est incrémenté de 1 à chaque fois qu'il quitte l'état élu.
- On suppose que A, B, C, D et E démarrent avec le même indice de priorité initial = 1.
- Le processus le plus prioritaire est celui avec le plus petit indice de priorité.
Il faut montrer l'état d'occupation de l'UCT ainsi que l'ordre des processus dans les deux files d'attente (UCT et E/S) pendant les 30 premières unités de temps d'exécution.
Foire Aux Questions (FAQ) sur l'Ordonnancement des Processus
Qu'est-ce que l'ordonnancement des processus dans un système d'exploitation ?
L'ordonnancement des processus est la méthode utilisée par le système d'exploitation pour déterminer quel processus doit être exécuté par le processeur (UCT) à un moment donné et pour combien de temps. Son objectif est de maximiser l'utilisation de l'UCT, de minimiser le temps de réponse et d'attente, et d'assurer une exécution équitable ou prioritaire des tâches.
Quels sont les principaux algorithmes d'ordonnancement mentionnés ?
Les exercices abordent plusieurs algorithmes clés :
- PAPS (Premier Arrivé, Premier Servi) : Les processus sont exécutés dans l'ordre de leur arrivée.
- SJF (Shortest Job First / Plus Court D'abord) : Priorise les processus ayant la plus petite durée d'exécution restante. Il peut être préemptif ou non.
- Tourniquet (Round Robin) : Chaque processus reçoit un petit quantum de temps UCT. Si le processus ne termine pas dans ce temps, il est préempté et placé à la fin de la file d'attente des prêts.
- Tourniquet avec Priorités : Une variante du Tourniquet où les processus ont des niveaux de priorité, influençant l'ordre d'exécution après l'expiration du quantum ou la préemption.
Quelles sont les métriques importantes pour évaluer la performance d'un algorithme d'ordonnancement ?
Les métriques clés pour évaluer un ordonnanceur incluent :
- Débit (Throughput) : Le nombre de processus complétés par unité de temps, indiquant l'efficacité du système.
- Temps de rotation (Turnaround Time) : Le temps total passé par un processus dans le système, de son arrivée à sa terminaison.
- Temps d'attente : Le temps total qu'un processus passe dans la file d'attente des prêts, en attendant d'être exécuté.
- Temps de réponse : Le temps entre une requête utilisateur et la première réponse du système, essentiel pour l'interactivité.