Sujet : Le Fonctionnement des Différents Algorithmes
d’Ordonnancement
Introduction
L’ordonnancement est un processus essentiel dans les systèmes
informatiques et industriels qui vise à organiser l’exécution des tâches en
fonction de certaines contraintes et objectifs. Dans un système
d’exploitation, par exemple, l’ordonnanceur gère l’exécution des processus
en attribuant les ressources du processeur de manière efficace. Dans le
domaine industriel, il optimise l’enchaînement des opérations pour
améliorer la productivité.
Les algorithmes d’ordonnancement ont pour objectif de minimiser le
temps d’attente, maximiser le débit du système, garantir l’équité entre les
tâches et, dans certains cas, assurer des délais stricts d’exécution (comme
dans les systèmes temps réel).
I. Classification des Algorithmes d’Ordonnancement
A. Ordonnancement Mono-Processeur vs Multi-Processeur
Ordonnancement Mono-Processeur : Gère un seul processeur, nécessitant
une organisation efficace des tâches pour éviter l’inactivité ou la
surcharge.
Ordonnancement Multi-Processeur : Implique plusieurs unités de calcul et
doit équilibrer la charge entre elles pour garantir une exécution efficace.
B. Ordonnancement Préemptif vs Non Préemptif
Ordonnancement Préemptif : Un processus en cours peut être interrompu
pour exécuter une tâche plus prioritaire. Cela garantit une meilleure
réactivité, mais augmente la complexité de gestion.
Ordonnancement Non Préemptif : Un processus s’exécute jusqu’à sa fin
sans interruption, réduisant la complexité mais risquant de pénaliser les
tâches urgentes.
C. Ordonnancement en Temps Partagé vs Temps Réel
Temps Partagé : Utilisé dans les systèmes interactifs où plusieurs
utilisateurs partagent les ressources (exemple : Windows, Linux).
Temps Réel : Assure des délais stricts pour les tâches critiques, comme
dans l’aéronautique ou le médical.
II. Principaux Algorithmes d’Ordonnancement
A. Algorithmes Classiques pour les Systèmes
d’Exploitation
1. First Come, First Served (FCFS)
Fonctionnement : Les tâches sont exécutées dans l’ordre de leur arrivée.
Avantages : Simple à implémenter, sans famine.
Inconvénients : Peut entraîner des temps d’attente élevés pour les tâches
longues (effet de convoi).
2. Shortest Job Next (SJN) / Shortest Job First (SJF)
Fonctionnement : La tâche la plus courte est exécutée en premier.
Avantages : Minimise le temps d’attente moyen.
Inconvénients : Risque de famine pour les tâches longues.
3. Round Robin (RR)
Fonctionnement : Chaque tâche reçoit un quantum de temps fixe et
alterne avec les autres.
Avantages : Équitable et interactif.
Inconvénients : La performance dépend du choix du quantum (trop long =
latence élevée, trop court = surcharge de commutation).
4. Priority Scheduling
Fonctionnement : Chaque tâche a une priorité ; la plus élevée est exécutée
en premier.
Avantages : Optimisation des tâches critiques.
Inconvénients : Risque de famine des tâches de faible priorité (solution :
Aging, qui augmente progressivement la priorité des tâches en attente).
5. Multilevel Queue Scheduling & Multilevel
Feedback Queue (MLFQ)
Fonctionnement : Organisation des tâches en plusieurs files selon des
critères (interactives, batch, etc.), avec la possibilité d’adapter
dynamiquement leur priorité (MLFQ).
Avantages : Bonne gestion des différents types de processus.
Inconvénients : Complexité de gestion.
B. Algorithmes pour les Systèmes Temps Réel
1. Rate Monotonic Scheduling (RMS)
Fonctionnement : Les tâches périodiques ont une priorité fixe en fonction
de leur fréquence (les plus fréquentes ont la priorité).
Avantages : Facile à implémenter.
Inconvénients : Ne fonctionne bien que si la charge est bien répartie.
2. Earliest Deadline First (EDF)
Fonctionnement : La tâche avec la date limite la plus proche est exécutée
en premier.
Avantages : Optimal en utilisation CPU.
Inconvénients : Difficile à implémenter dans des systèmes avec surcharge
variable.
3. Least Laxity First (LLF)
Fonctionnement : Priorise la tâche avec le moins de marge avant sa date
limite.
Avantages : Assure l’exécution des tâches critiques.
Inconvénients : Génère un coût en commutation de contexte élevé.
C. Algorithmes pour l’Ordonnancement en Cloud
Computing
Ordonnancement basé sur la charge : Répartit dynamiquement les tâches
sur les serveurs les moins sollicités.
Algorithmes heuristiques : Utilisent des méthodes d’optimisation comme
les colonies de fourmis ou les algorithmes génétiques pour améliorer
l’efficacité du cloud.
III. Comparaison et Optimisation des Algorithmes
d’Ordonnancement
A. Critères de Performance
Temps d’attente moyen : Doit être minimisé pour assurer une exécution
rapide.
Temps de réponse : Important pour les systèmes interactifs.
Débit du système : Nombre de tâches terminées par unité de temps.
Équité : Aucun processus ne doit être indéfiniment retardé.
B. Limites et Problèmes Courants
Famine : Certaines tâches peuvent attendre indéfiniment (ex. priorité
basse).
Équilibre entre équité et efficacité : Un système trop équitable peut
ralentir les performances globales.
Surcharge du système : Un algorithme mal adapté peut engendrer trop de
commutations de contexte.
C. Tendances et Évolutions Récentes
Ordonnancement adaptatif : Utilisation de l’intelligence artificielle pour
ajuster dynamiquement les priorités et les files d’attente.
Optimisation pour le cloud et l’edge computing : Développement
d’algorithmes plus efficaces pour la répartition dynamique des charges.
Systèmes hybrides : Combinaison d’algorithmes classiques et intelligents
pour améliorer les performances globales.
Conclusion
L’ordonnancement est un élément crucial pour l’efficacité des systèmes
informatiques et industriels. Différents algorithmes sont utilisés en
fonction des contraintes spécifiques, allant de la simplicité du FCFS à la
sophistication des algorithmes MLFQ ou EDF pour les systèmes critiques.
Le choix de l’algorithme dépend des objectifs à atteindre : réactivité,
performance, équité ou respect strict des délais.
Les avancées technologiques, notamment l’apprentissage automatique et
l’optimisation dynamique, promettent d’améliorer encore ces mécanismes
dans les années à venir, garantissant ainsi une gestion toujours plus
efficace des ressources informatiques.
Sommaire
Introduction
1. Définition et enjeux de l’ordonnancement
2. Domaines d’application (systèmes d’exploitation, cloud computing,
industrie, etc.)
3. Objectifs des algorithmes d’ordonnancement.
I. Classification des Algorithmes d’Ordonnancement
A. Ordonnancement Mono-Processeur vs Multi-Processeur
B. Ordonnancement Préemptif vs Non Préemptif
C. Ordonnancement en Temps Partagé vs Temps Réel
II. Principaux Algorithmes d’Ordonnancement
A. Algorithmes Classiques pour les Systèmes d’Exploitatio
B. Algorithmes pour les Systèmes Temps Réel
C. Algorithmes pour l’Ordonnancement en Cloud
Computing
III. Comparaison et Optimisation des Algorithmes
d’Ordonnancement
A. Critères de Performance
B. Limites et Problèmes Courants
C. Tendances et Évolutions Récentes
Conclusion
