Le coût du système d’exploitation est composé de deux parties : une partie facile à déterminer, correspondant au coût de l’ordonnanceur et une partie difficile à déterminer, correspondant au coût de la préemption. Cette difficulté est due au fait qu’une préemption peut en engendrer une autre, pouvant ainsi créer un phénomène d’avalanche [Yom09]. Meumeu et Sorel [Yom09] ont proposé une condition d’ordonnançabilité qui permet de prendre en compte le coût exact de la préemption, donc le coût de l’OS. Mais cette condition d’ordonnançabilité n’est applicable qu’à des tâches indépendantes à priorités fixes et sur une architecture monoprocesseur. Notre premier objectif est d’étendre cette condition d’ordonnançabilité pour étudier l’ordonnancement de tâches temps réel indépendantes sur une architecture multiprocesseur et en tenant compte du coût exact de la préemption. Les applications temps réel embarquées étant généralement composées de tâches dépendantes, notre deuxième objectif est d’étudier l’ordonnancement de tâches dépendantes sur une architecture multiprocesseur et toujours avec prise en compte du coût exact de la préemption. Pour cela nous allons étudier une nouvelle condition d’ordonnançabilité pour des tâches dépendantes, qui permet de prendre en compte le coût exact de la préemption puisque la condition d’ordonnançabilité proposée par Meumeu et Sorel est applicable uniquement pour des tâches indépendantes à priorités fixes et ne permet donc pas de gérer les inversions de priorités que peut entraîner l’ordonnancement de tâches dépendantes. Enfin notre troisième et dernier objectif est, à partir de l’analyse d’ordonnançabilité que nous avons proposée, d’utiliser la table d’ordonnancement déterminée hors ligne dans un nouveau type d’ordonnanceur en ligne prenant mieux en compte le coût de l’OS que les ordonnanceurs classiques.

Ce manuscrit est constitué de trois parties. La première partie est consacrée aux concepts de bases de l’ordonnancement temps réel pour faciliter la compréhension de la suite de la thèse et à l’état de l’art dans lequel on met l’accent sur les méthodes d’allocation des tâches dans l’ordonnancement multiprocesseur, sur la prise en compte du coût exact de la préemption et sur les dépendances de données. La deuxième partie est consacrée à l’ordonnancement multiprocesseur de tâches indépendantes avec prise en compte du coût exact de la préemption. Dans le premier chapitre de cette partie on présente la condition d’ordonnançabilité proposée par Meumeu et Sorel qui permet de prendre en compte le coût exact de la préemption en monoprocesseur pour des tâches à priorités fixes. Le deuxième chapitre de cette deuxième partie présente l’étude d’ordonnancement multiprocesseur de tâches indépendantes qui étend la condition d’ordonnançabilité de Meumeu et Sorel en multiprocesseur. La troisième partie est consacrée à l’ordonnancement multiprocesseur de tâches dépendantes. Dans le premier chapitre de cette partie, on étudie l’ordonnancement des tâches dépendantes en monoprocesseur en proposant une nouvelle condition d’ordonnançabilité qui permet d’ordonnancer des tâches dépendantes en prenant en compte du coût exact de la préemption et les transferts de données entre tâches qui conduisent à des inversions de priorités. Dans le deuxième chapitre de cette partie, on présente l’étude d’ordonnancement multiprocesseur de tâches dépendantes qui étend cette nouvelle condition d’ordonnançabilité monoprocesseur en multiprocesseur tout en tenant compte le coût exact de la préemption et les coûts de communication inter processeurs. Dans le troisième chapitre de cette partie, on présente l’ordonnanceur en ligne de chaque processeur qui utilise la table d’ordonnancement produite hors ligne, pour ce processeur.

Un système réactif doit réagir continûment aux stimuli venant d’un processus qu’il cherche à commander. Un système temps réel est un système réactif qui doit respecter des contraintes de temps. Un système temps réel doit être capable de traiter les informations venant du processus dans un délai qui ne nuit pas à la commande du processus. Réagir trop tard peut conduire à des conséquences catastrophiques pour le système lui-même ou le processus. Le respect des contraintes temporelles est la principale contrainte à satisfaire. La validité d’un système temps réel dépend non seulement des résultats du traitement effectué mais aussi de l’aspect temporel (un calcul juste mais hors délai est un calcul non valable). Dans un système temps réel, les évènements d’entrée sont produits par des capteurs et les évènements de sortie sont consommés par des actionneurs.

La criticité des contraintes temporelles conduit à classifier les système temps réel en trois catégories suivantes :

– système temps réel strict : c’est un système soumis à des contraintes temporelles strictes, c’est-à-dire pour lequel la moindre faute temporelle peut avoir des conséquences humaines ou économiques catastrophiques. La plupart des applications dans les domaines avioniques, automobile, etc., sont temps réel strict;
– système temps réel souple : c’est un système soumis à des contraintes temporelles souples, un certain nombre de fautes temporelles peut être tolérées. On parle alors de qualité de service;
– système temps réel mixte : c’est un système soumis à des contraintes temporelles strictes et à des contraintes temporelles souples.

Une tâche temps réel est formée d’un ensemble d’instructions pouvant s’exécuter en séquence sur un ou plusieurs processeurs et respecter des contraintes de temps. Dans la suite nous ferons l’hypothèse qu’une tâche ne s’exécutera pas en parallèle. Elle peut se répéter un nombre quelconque de fois, éventuellement infini. Chacune de ses exécutions est appelée instance ou travail (« job »). Un système temps réel est composé d’un ensemble de tâches temps réel soumises à des contraintes temps réel . Une tâche temps réel peut être :
– périodique : ses instances (exécutions) se répètent indéfiniment et il existe une durée constante entre deux activations d’instances successives appelée période,
– sporadique : ses instances (exécutions) se répètent indéfiniment et il existe une durée minimum entre deux instances successives,
– apériodique : il y a pas de corrélation entre deux instances successives.