ALLOCATION DE TÂCHES INDÉPENDANTES

Dans ce chapitre, nous étudions les algorithmes appliqués aux tâches avant le dé- marrage de l’ordonnancement. Il s’agit d’une approche par partitionnement (FT) où nous considérons que l’ordonnancement en ligne est réalisé par un algorithme de la classe FTP. Nous considérons des tâches sporadiques à échéan-ces contraintes. Ces tâches sont indépendantes dans le sens où elles ne partagent pas de ressources communes. L’approche d’ordonnancement temps réel multiprocesseur hors-ligne la plus repré- sentative est l’approche par partitionnement. Chaque sous-ensemble de tâches obtenu à partir d’un partitionnement est ensuite ordonnancé de manière indépendante sur chaque processeur. Cette approche interdit donc les migrations inter-processeurs. Mais nous pouvons tout à fait concevoir des approches d’ordonnancement pour lesquels des schémas de migrations sont connus à l’avance. Nous proposons un algorithme de partitionnement qui soit robuste aux variations négatives de WCET et de périodes. Plus particulièrement, un algorithme pour lequel la marge sur le WCET ou la période des tâches est maximisée. L’aspect de la robus- tesse qui est ici considéré consiste à rendre le système plus tolérant à des fautes, à de mauvaises estimations de WCET ou à un mauvais dimensionnement au niveau des périodes. Dans la section 3.2, nous décrivons les modèles et les notations utilisés dans ce cha- pitre. Dans la section 3.3, nous présentons la problématique de l’ordonnancement par partitionnement. Dans la section 3.5, nous discutons des propriétés de robustesse des algorithmes de partitionnement. Enfin, nous proposons une synthèse de ce chapitre dans la section 3.6.

Partitionnement

Nous nous intéressons dans cette section au modèle de tâches indépendantes. L’ap- proche par partitionnement consiste à subdiviser un ensemble de tâches en autant de sous-ensembles disjoints qu’il y a de processeurs. Chaque sous-ensemble est en- suite ordonnancé sur un processeur, et ce sans migration. Cette approche a l’avantage qu’une fois le partitionnement connu, les résultats provenant de l’état de l’art sur l’or- donnancement temps réel monoprocesseur sont valides. La difficulté dans l’étude de l’ordonnancement par partitionnement réside dans la recherche de partitions ordon- nançables. Certains algorithmes de partitionnement peuvent être sujets à des anomalies. An- dersson et Jonsson montrent dans [AJ02] que des anomalies peuvent se produire avec l’algorithme R-BOUND-MP [LMM98] lorsque les périodes des tâches sont augmen- tées. Ce phénomène se produit car la condition d’admission R-BOUND (utilisée par R-BOUND-MP) exploite le rapport entre la période maximale et la période minimale des tâches à assigner. Une période plus grande implique un rapport différent qui peut modifier la condition d’admission. Un ensemble de tâches pouvant être partitionné par R-BOUND-MP peut ne plus pouvoir l’être avec une ou plusieurs tâches ayant des périodes plus grandes. Dans le cas où le partitionnement est effectué hors-ligne, le problème des anomalies n’est qu’un problème de dimensionnement du système. En effet, le fait qu’un ensemble de tâches ne puisse pas être partitionné avec des périodes plus grandes ne conduit pas à ce que des échéances soient dépassées.

Nous considérons une plate-forme multiprocesseur composée de processeurs iden- tiques. Étant donné un ensemble de tâches sporadiques caractérisées par leur utili- sation, nous pouvons nous poser la question de savoir combien de processeurs sont nécessaires pour pouvoir ordonnancer cet ensemble de tâches. Cette formulation du problème est très similaire à celle du problème de BIN-PACKING. PACKING. Il suffit de considérer nos processeurs comme étant des boîtes dont la taille serait la puissance de calcul des processeurs et de considérer nos tâches comme des ob- jets à ranger dont la taille serait l’utilisation de ces tâches. Nous pouvons maintenant résoudre notre problème de partitionnement en utilisant un algorithme permettant de résoudre le problème de BIN-PACKING. Malheureusement, il a été montré que ce dernier est un problème NP-difficile [GJ79]. Cela signifie qu’à moins qu’il soit prouvé que P = N P , aucun algorithme ne peut garantir de trouver la solution optimale à ce problème en temps polynomial. Une solution optimale correspondrait, pour notre problème, au nombre minimal de processeurs nécessaires pour pouvoir ordonnancer un ensemble de tâches. Heureusement, le problème de BIN-PACKING a été largement étudié et il existe de nombreuses heuristiques permettant de le résoudre sans garantie de trouver la solution optimale.Une autre question que nous pouvons nous poser est de savoir si il existe un parti- tionnement d’un ensemble de tâches pour une plate-forme multiprocesseur donnée, en d’autres termes lorsque le nombre de processeurs est fixé. Ce problème correspond au problème de décision associé au problème BIN-PACKING. La description du problème donnée dans la définition 3.1 correspond au problème de minimisation. Pour résoudre le problème de décision, il suffit d’appliquer un algorithme résolvant le problème de minimisation et de vérifier que la valeur de la solution retournée est inférieure ou égale au nombre de processeurs.