Principaux algorithmes d’ordonnancement
Ordonnancement temps réel - Ordonnancement multiprocesseur

Le simple fait d’ajouter un processeur supplémentaire à la plateforme augmente drastiquement la complexité des problèmes d’ordonnancement temps réel. Dès 1969, C.L. Liu constatait que très peu de résultats connus en environnement monoprocesseur pouvaient être directement généralisés aux systèmes multiprocesseurs . Le premier algorithme optimal, c’est-à-dire d’ordonnancer des systèmes de tâches avec une utilisation totale égale à la capacité de la plateforme n’a été proposé qu’en 1993 . La définition d’algorithmes d’ordonnancement performants, de leurs tests associés, et qui soient capables d’exploiter pleinement la puissance des processeurs demeure un sujet de recherche en pleine expansion.

À des fins de clarté et de concision, nous nous limitons à la présentation de résultats sur les systèmes de processeurs identiques exécutant des tâches périodiques, indépendantes et à échéance implicite. L’ordonnancement de ces systèmes est le problème central de la théorie de l’ordonnancement multiprocesseur. De plus, il sera supposé dans toute la suite que les préemptions et les migrations, lorsqu’elles sont autorisées, sont effectuées avec des coûts négligeables.

Les approches développées pour ordonnancer les systèmes multiprocesseurs sont :

• le partitionnement des tâches avant leur exécution, puis celles-ci sont ordonnancées localement sur chaque processeur ;

• l’ordonnancement global autorisant la migration des tâches d’un processeur à un autre durant l’exécution des tâches ;

• enfin, des méthodes hybrides combinant les deux méthodes précédentes ont été aussi proposées...