Système d’Exploitation I

Ce support de cours s'adresse aux étudiants en informatique et traite des principes fondamentaux de l'ordonnancement des processus dans un système d'exploitation. Il présente les objectifs, les modes, les critères d'évaluation, ainsi que plusieurs politiques d'ordonnancement classiques, accompagnées d'exercices pratiques pour illustrer leur fonctionnement.

Ordonnancement des processus : contexte et objectifs

Un processeur ne peut exécuter qu'un seul processus à la fois, mais les systèmes actuels permettent l'exécution simultanée de plusieurs processus. Pour gérer cette simultanéité, il existe deux solutions :

• Un processeur dédié par processus (peu pratique et coûteux).
• Partager le processeur entre les processus demandant simultanément son utilisation, ce qui nécessite un ordonnancement.

L'ordonnancement des processus vise plusieurs objectifs :

• Maximiser le nombre de processus exécutés par unité de temps.
• Maximiser le temps d'attente d'exécution de chaque processus (équité).
• Maximiser l'utilisation des processeurs et autres ressources.
• Éviter la famine (starvation) où certains processus ne sont jamais exécutés.
• Favoriser les processus prioritaires.
• Minimiser le nombre de changements de contexte (overhead).

Il est difficile de satisfaire tous ces objectifs simultanément, d'où la nécessité de prioriser certains critères selon le contexte d'utilisation du système d'exploitation.

L’ordonnanceur et ses modes

L'ordonnanceur (scheduler ou dispatcher) est un composant du système d'exploitation qui gère l'ordre d'exécution des processus. Il applique un algorithme d'ordonnancement choisi par les concepteurs du système, qui ne change pas dynamiquement.

Il existe deux classes principales d'ordonnanceurs :

• Non préemptif : le processus sélectionné s'exécute jusqu'à ce qu'il se bloque ou libère volontairement le processeur. Aucun changement forcé n'intervient pendant son exécution.
• Préemptif : le processus s'exécute pendant un délai déterminé (quantum). Si ce délai expire, il est suspendu et un autre processus est sélectionné.

En cas d'égalité selon la politique d'ordonnancement, des règles d'arbitrage sont appliquées, par exemple :

• Choix aléatoire.
• Processus le plus court.
• Processus le plus prioritaire.

Critères d’évaluation de la performance de l’ordonnancement

• Rendement (throughput) : nombre de travaux exécutés par unité de temps.
• Temps de service (turnaround time) : durée entre la soumission d'un travail et sa fin d'exécution (incluant attente, exécution CPU et E/S).
• Temps d’attente (waiting time) : temps passé dans la file des processus prêts à s'exécuter.
• Temps de réponse (response time) : délai entre la soumission d'une requête et la première réponse obtenue.

Politiques d’ordonnancement

First Come First Served (FCFS)

Le processus arrivé en premier est exécuté en premier. La file d'attente est une file FIFO. Une fois la CPU allouée, le processus la garde jusqu'à sa libération (fin ou E/S).

Cette politique est simple mais inadaptée aux systèmes temps partagé car elle peut engendrer de longs délais pour certains utilisateurs.

Le temps d'attente moyen n'est généralement pas minimal et varie fortement selon la durée des processus.

Processus | Date arrivée | Temps CPU
P1        | 0            | 9
P2        | 3            | 5
P3        | 4            | 7
P4        | 10           | 4

1) Diagramme de Gantt FCFS :
P1 (0-9) → P2 (9-14) → P3 (14-21) → P4 (21-25)

2) Calculs :
- Temps d'attente (TA) moyen = ((0) + (9-3) + (14-4) + (21-10)) / 4 = (0 + 6 + 10 + 11) / 4 = 6.75
- Temps de réponse (TR) moyen = TA moyen (car réponse au début de l'exécution)
- Temps de service (TS) moyen = ((25-0) + (14-3) + (21-4) + (25-10)) / 4 = (25 + 11 + 17 + 15) / 4 = 17
- Rendement = 4 / 25 = 0.16 processus par unité de temps
  

Shortest Job First (SJF)

Le processus avec le plus court temps CPU est exécuté en premier. Si deux processus ont la même durée, FCFS sert d'arbitre.

SJF est optimal pour minimiser le temps d'attente moyen, mais nécessite de connaître à l'avance la durée du prochain cycle CPU, ce qui est difficile en pratique.

Il existe deux modes :

• Non préemptif : le processus choisi s'exécute jusqu'à la fin.
• Préemptif : un nouveau processus plus court peut interrompre le processus en cours.

Processus | Date arrivée | Temps CPU
P1        | 0            | 9
P2        | 3            | 5
P3        | 4            | 7
P4        | 10           | 4

1) Diagramme de Gantt SJF non préemptif :
P1 (0-9) → P2 (9-14) → P4 (14-18) → P3 (18-25)

2) Calculs :
- TA moyen = ((0) + (9-3) + (18-10) + (14-4)) / 4 = (0 + 6 + 8 + 10) / 4 = 6
- TR moyen = TA moyen
- TS moyen = ((25-0) + (14-3) + (25-4) + (18-10)) / 4 = (25 + 11 + 21 + 8) / 4 = 16.25
- Rendement = 4 / 25 = 0.16
  

3) Diagramme de Gantt SJF préemptif (extrait) :
P1 (0-3) → P2 (3-8) → P4 (8-12) → P3 (12-19) → P1 (19-25)

4) Calculs similaires à l'exercice non préemptif, avec des temps d'attente et de réponse généralement améliorés.
  

Tourniquet (Round Robin)

Chaque processus reçoit une tranche de temps fixe appelée quantum q. L'ordonnanceur parcourt la file des processus prêts, allouant la CPU à chacun pendant un quantum.

Si un processus n'a pas fini à l'expiration du quantum, il est replacé en queue de la file.

Tous les processus ont la même priorité, et la file est une file FIFO.

Le choix du quantum est crucial :

• Si q est trop grand, Round Robin devient équivalent à FCFS.
• Si q est trop petit, le système passe beaucoup de temps en commutations de contexte, ralentissant l'exécution effective.

Processus | Date arrivée | Temps CPU
P1        | 0            | 9
P2        | 3            | 5
P3        | 4            | 7
P4        | 10           | 4

1) Diagramme de Gantt RR (q=3) :
P1 (0-3) → P2 (3-6) → P3 (6-9) → P1 (9-12) → P2 (12-14) → P3 (14-16) → P1 (16-18) → P4 (18-21) → P3 (21-22)

2) Calculs :
- TA moyen, TR moyen, TS moyen et rendement calculés en fonction des temps d'attente et d'exécution observés.
  

Ordonnancement avec Priorités

Chaque processus se voit attribuer une priorité. La CPU est allouée au processus de plus haute priorité (priorité 1 > priorité 2).

Les processus de même priorité sont ordonnancés selon FCFS ou SJF.

Deux modes d'exécution existent : préemptif et non préemptif.

Un problème majeur est la famine : les processus à faible priorité peuvent ne jamais être exécutés.

Une solution est le vieillissement, qui consiste à augmenter progressivement la priorité des processus en attente depuis longtemps.

Ordonnancement à files d’attente multiples

Les processus sont répartis dans plusieurs files selon leurs caractéristiques :

• Processus consommant beaucoup de CPU : file de priorité inférieure.
• Processus dépendant d'E/S : file de priorité supérieure.
• Un processus qui attend trop longtemps dans une file basse peut être promu dans une file de priorité supérieure (vieillissement).

Exemple avec trois files :

• Q0 : quantum 8 ns
• Q1 : quantum 16 ns
• Q2 : FCFS

Un nouveau processus est inséré dans Q0. S'il ne termine pas en 8 ns, il est déplacé dans Q1. S'il ne termine pas en 16 ns dans Q1, il est déplacé dans Q2. Les processus de Q2 sont exécutés en FCFS seulement lorsque Q0 et Q1 sont vides.

Glossaire des termes clés

• Ordonnancement : gestion de l'ordre d'exécution des processus sur un processeur.
• Ordonnanceur (Scheduler) : composant du système d'exploitation qui applique une politique d'ordonnancement.
• Préemption : interruption forcée d'un processus pour en exécuter un autre.
• Quantum : unité de temps allouée à un processus dans l'ordonnancement préemptif.
• File FIFO : file d'attente où les éléments sont servis dans l'ordre d'arrivée.
• Famine (Starvation) : situation où un processus ne reçoit jamais la CPU.
• Vieillissement : technique d'augmentation progressive de la priorité d'un processus en attente.
• Temps d'attente : durée passée par un processus dans la file des prêts avant d'être exécuté.
• Temps de réponse : délai entre la soumission d'une requête et la première réponse.
• Temps de service (turnaround time) : temps total entre la soumission et la fin d'exécution d'un processus.
• Rendement (throughput) : nombre de processus terminés par unité de temps.

Points clés à retenir

• L'ordonnancement permet de partager un processeur entre plusieurs processus simultanés.
• Les politiques d'ordonnancement classiques sont FCFS, SJF, Round Robin et avec priorités.
• Chaque politique présente des avantages et des inconvénients, notamment en termes d'équité, de famine et de temps de réponse.
• Le choix du quantum dans Round Robin est crucial pour l'efficacité du système.
• Le vieillissement est une solution pour éviter la famine dans les politiques à priorité.
• Les systèmes modernes utilisent souvent des files d'attente multiples pour mieux gérer les différents types de processus.