Soutenance mémoire
Modélisation des tâches
Notre modélisation d’un système temps réel est basée sur celle proposée par Liu et Layland [LL73]. Un système temps réel est composé d’un ensemble de tâches nommé Γ qui comprend n tâches périodiques dont les caractéristiques sont détaillées ci-dessous. Nous définissons dans cette section tous les termes qui seront utilisés en relation avec la notion d’ensemble de tâches.
Tâche. Une tâche correspond à une application utilisateur du système et chaque tâche est développée par l’utilisateur du système pour répondre à un besoin. Une tâche τ est définie comme l’exécution d’une suite d’instructions. Nous supposons que toutes les tâches sont indépendantes et que l’ordre dans lequel les tâches sont exécutées n’a pas de conséquence sur la bonne exécution du système du moment qu’elles respectent leurs contraintes temporelles. Nous faisons également l’hypothèse que les tâches sont synchrones, donc que toutes les tâches sont actives dès que le système débute son exécution, les tâches sont toutes libérées simultanément. Le modèle de tâches que nous utilisons est le modèle de tâches dit périodique, le modèle le plus courant dans le monde industriel, utilisé par exemple dans le standard ARINC 653 [ARI].
Travail. Chaque tâche libère périodiquement des travaux. Un travail est une suite d’instructions qui doit être réalisée avant une date fixée. Lorsqu’une tâche libère un travail, celui-ci est prêt à être exécuté et devient disponible pour l’algorithme d’ordonnancement. Une tâche τi libère ses travaux périodiquement suivant sa période Ti, un travail n’a donc pas de période associée. Ce modèle est appelé modèle de tâche périodique car chaque travail est libéré exactement lorsque la tâche atteint sa période. D’autres modélisations plus souples existent comme les systèmes de tâches sporadiques ou apériodiques. Pour les systèmes sporadiques, la période d’une tâche est la période de temps minimale entre deux libérations de travaux pour une tâche, ce qui signifie que le système ne peut savoir la date exacte où le travail va être libéré. Dans le cas de systèmes apériodiques, l’intervalle de temps entre deux libérations de travaux n’est soumis à aucune contrainte. Ces systèmes sont plus difficiles à étudier du fait de l’imprévisibilité de l’arrivée des tâches.
Hyperpériode. L’hyperpériode H de l’ensemble de tâches correspond au plus petit commun multiple de toutes les périodes de l’ensemble de tâches. Pour chaque tâche, le nombre maximal de travaux J dans une hyperpériode est égal à l’hyperpériode divisée par la période de la tâche en question. Ce nombre dépend donc de la valeur de l’hyperpériode et des valeurs des périodes des tâches : J =Øni=1HTi(2.1) Le nombre de tâches dans un système temps réel embarqué est limité et les périodes de ces tâches ont en général des relations temporelles entre elles. Par exemple, il est peu probable que les périodes des tâches soient premières entre elles, les périodes des tâches sont souvent des harmoniques. En prenant un exemple concret, des tâches peuvent avoir des périodes de 1ms, 2ms, 5ms ou 10ms mais il est moins fréquent de trouver des tâches avec des périodes de 1.78ms et de 8.54ms. La valeur de l’hyperpériode ainsi que le nombre de travaux dans une hyperpériode restent donc naturellement raisonnables.
WCET – AET. Le WCET (Worst Case Execution Time) d’une tâche est la durée maximale de l’exécution de chacun de ses travaux. Le WCET de la tâche τi est noté Ci et le WCET du travail j est noté j.c. Calculer le WCET d’une tâche est difficile et ce sujet est une thématique de recherche à lui tout seul. Nous renvoyons le lecteur à [WEE+08] pour plus d’informations. Nous supposons que le WCET de chaque travail est connu. Le temps d’exécution réel d’un travail (Actual Execution Time en anglais) est le temps utilisé par ce travail lors de l’exécution. Nous faisons l’hypothèse que l’AET est compris entre 0 et le WCET de ce travail.
Échéance. Chaque travail une fois libéré doit terminer son exécution avec une certaine date sous peine de violer son échéance. Nous notons Di l’échéance relative de la tâche τi. L’échéance absolue j.d du travail j sera donc la date de sa libération additionnée de cette échéance relative. Nous faisons l’hypothèse que l’échéance de chaque tâche est égale à sa période. Dans la littérature, ces ensembles de tâches sont appelés ensembles de tâches à « échéances implicites ». Un autre modèle utilisé est le modèle à « échéances contraintes » où l’échéance de chaque travail est inférieure ou égale à sa période. Enfin, le modèle à « échéances arbitraires » ne fixe aucune contrainte entre les échéances et les périodes des tâches.
Criticité. Chaque tâche est caractérisée par sa criticité. Nous supposons deux niveaux de criticité : HIGH et LOW. Pour les systèmes temps réel dur, la criticité de chaque tâche est HIGH car aucun dépassement d’échéances n’est autorisé. Les systèmes temps réel à criticité mixte permettent d’ordonnancer des tâches de différents niveaux de criticité et les tâches de criticité LOW autorisent qu’un certain pourcentage d’échéances soient violées. Ce modèle est différent du modèle classique des systèmes temps réel à criticité mixte proposé par Vestal et al. [Ves07]. Nous détaillerons au chapitre 6 quels sont les différences entre le modèle que nous adoptons ici et le modèle classique.
Ordonnancement de systèmes multiprocesseurs
Cette section propose un résumé non exhaustif des algorithmes d’ordonnancement multiprocesseurs existants. Ces algorithmes n’ont pas comme objectif de réduire la consommation énergétique mais il est néanmoins important d’avoir une connaissance de ces solutions car les algorithmes d’ordonnancement réduisant la consommation énergétique doivent satisfaire les contraintes d’ordonnancement. Nous supposons ici que le système possède au minimum deux processeurs. L’ordonnancement des systèmes temps réel multiprocesseurs ne peut être considéré comme la généralisation de l’ordonnancement monoprocesseur. Ce problème est plus complexe que sur systèmes monoprocesseurs car il ajoute une dimension spatiale à un problème d’allocation temporelle des ressources. L’ordonnancement multiprocesseur souffre également d’anomalies d’ordonnancement [AJ02]. Un algorithme d’ordonnancement multiprocesseur peut par exemple ordonnancer correctement un ensemble de tâches et engendrer des dépassements d’échéances lorsque la période d’une tâche de cet ensemble de tâches augmente. Les algorithmes d’ordonnancement multiprocesseurs peuvent être divisés en plusieurs catégories selon un certain nombre de critères. Ils sont généralement triés en trois catégories selon qu’ils autorisent ou non la migration des tâches et des travaux entre processeurs.
Algorithmes partitionnés. Un algorithme d’ordonnancement partitionnée permet pas à un travail ou à une tâche de migrer d’un processeur à un autre. Chaque tâche est assignée horsligne à un processeur et reste sur ce même processeur durant toute l’exécution du système. Chaque processeur peut donc être ordonnancé comme un système à un seul processeur. Allouer les tâches aux processeurs est un problème similaire au problème de bin packing, qui est NP-Complet [GJ90], et des heuristiques comme First-Fit ou Best-Fit peuvent être utilisées [Ber07, LW82]. Ces algorithmes sont souvent utilisés en pratique de par leur facilité d’implémentation. En effet, après l’allocation des tâches au processeur, le problème se résume à m problèmes monoprocesseurs qui sont des problèmes connus et largement étudiés. En contrepartie, ces algorithmes d’ordonnancement ont une borne d’ordonnançabilité plus faible que les algorithmes d’ordonnancement qui autorisent les migrations [Ber07].
Algorithmes globaux. Cette catégorie d’algorithmes temps réel multiprocesseurs est la plus permissive, toute migration est autorisée, que ce soit pour les travaux ou les tâches. Cette approche permet d’obtenir des algorithmes optimaux. Global-EDF [Bak03] est un algorithme d’ordonnancement multiprocesseur global utilisant EDF pour ordonnancer les tâches. Plusieurs variantes de Global-EDF existent, nous utiliserons par la suite la variante autorisant toutes les migrations. Nous supposons que Global-EDF exécute la tâche dont l’échéance est la plus rapprochée et exécute la tâche avec l’identifiant le plus faible si deux tâches ont une même échéance. Le premier algorithme optimal, PFair, a été proposé par Baruah et al. [BCPV93]. Le principe de cet algorithme est d’allouer du temps processeur à une tâche en fonction de son utilisation, le temps étant découpé en de courts intervalles de temps. Bien que cette première solution ait été améliorée par la suite avec Boundary Fair (BF) [ZMM03], cette approche n’est pas utilisable du fait du grand nombre de préemptions et de migrations engendrées. Anderson et al. [AHS05] propose un résumé des différents algorithmes d’ordonnancement reposant sur cette notion de « fairness » où chaque tâche reçoit le temps processeur qui lui est imparti en fonction de son utilisation. Différents algorithmes d’ordonnancement temps réel multiprocesseurs globaux optimaux ne reposant pas sur la notion de fairness ont depuis été proposés, parmi lesquels Incremental scheduling with Zero Laxity (IZL) [MSD10], U-EDF [NBGM11, NBN+12] et Reduction to UNiprocessor (RUN) [RLM+11]. Cependant, tous ces algorithmes souffrent de certains défauts, comme une complexité en-ligne importante pour U-EDF ou le fait qu’ils ne puissent pas ordonnancer de systèmes de tâches sporadiques pour RUN et IZL. D’autres algorithmes se basent sur la laxité des tâches, comme par exemple Fixed Priority with Zero Laxity (FPZL) [DB11a] ou Earliest Deadline First with Zero Laxity (EDZL) [WCL+07]. Ces algorithmes monitorent la laxité des tâches du système et ordonnancent en priorité la tâche dont la laxité est nulle pour ne pas violer son échéance. Les approches classiques utilisent les priorités pour ordonnancer les tâches, d’autres solutions sont néanmoins possibles. Une autre méthode a par exemple été proposée par Lemerre et al. [LDAVN08]. Elle exprime le problème d’ordonnancement comme le fait d’assigner sur une hyperpériode divisée en intervalles un poids à chaque tâche sur chaque intervalle. Comme nous allons utiliser cette solution, nous la détaillerons au chapitre 4.
Algorithmes à migrations restreintes. Entre les algorithmes partitionnés qui n’autorisent aucune migration et les algorithmes globaux où toutes les migrations sont autorisées, les algorithmes à migrations restreintes autorisent les migrations mais sous certaines conditions. La migration des tâches peut par exemple être autorisée mais pas la migration des travaux. La tâche peut donc changer de processeur lorsqu’un travail termine son exécution mais n’y est pas autorisé lorsqu’un travail est en cours d’exécution. Aucun algorithme d’ordonnancement optimal n’existe pour cette catégorie d’algorithme.
Systèmes temps réel à criticité mixte. Les algorithmes d’ordonnancement s’intéressant aux systèmes temps réel à criticité mixte ont pour objectif d’améliorer l’ordonnançabilité de ces systèmes, notamment celle des tâches à faible criticité tout en garantissant les échéances des tâche à haute criticité. Le modèle classique des systèmes temps réel à criticité mixte a été proposé par Vestal [Ves07] et définit un WCET pour chaque niveau de criticité, pour représenter par exemple les différents niveaux d’exigence des autorités de certification. Dans cette représentation, plus le niveau de criticité est élevé, plus le WCET est important. Dans le cadre de systèmes multiprocesseurs, Li et Baruah [LB12] utilisent un ordonnancement global. Mollison et al. [MEA+10] utilisent eux une stratégie partitionnée en utilisant des algorithmes d’ordonnancement différents suivant la criticité des tâches. Burns et Davis [BD13] proposent un résumé des dernières recherches sur les systèmes à criticité mixte. À notre connaissance, aucun algorithme d’ordonnancement n’a été proposé pour réduire la consommation énergétique des systèmes temps réel à criticité mixte.
Possibilités matérielles pour contrôler la consommation énergétique
Pour réduire la consommation statique des processeurs, il est nécessaire d’utiliser leurs états basse-consommation lors de leurs périodes d’inactivité. Nous appelons périodes d’inactivité les périodes de temps durant lesquelles un processeur est inactif et où aucune tâche n’est exécutée. Les processeurs disposent maintenant de plusieurs états basse-consommation où un certain nombre de composants sont désactivés pour réduire la consommation énergétique. Le problème lié à l’utilisation de ces états basse-consommation est qu’éteindre, rallumer ou changer d’état un processeur n’est pas anodin, que ce soit du point de vue énergétique ou temporel. Nous définissons dans cette section quatre notions relatives aux états basse consommation. Nous notons ns le nombre d’états basse-consommation de chaque processeur et nous supposons que tous les processeurs possèdent les mêmes états basse-consommation.
Consommation énergétique. Nous notons Conss la consommation énergétique de l’état basse-consommation s. C’est la consommation énergétique dépensée lorsque le processeur se trouve dans cet état basse-consommation. Elle dépend du nombre de composants qui ont été désactivés. Plus ce nombre est important, plus la consommation énergétique sera réduite.
Délai de transition. Nous définissons le délai de transition d’un état basse-consommation comme le temps nécessaire pour revenir de cet état basse-consommation à l’état actif. C’est le temps nécessaire pour réactiver tous les composants éteints durant l’état basse-consommation. Le délai de transition de l’état basse-consommation s est noté Dels. Plus la consommation énergétique de l’état basse-consommation est faible, plus son délai de transition va être important car davantage de composants devront été réactivés.
Pénalité énergétique. Nous notons Pens la pénalité énergétique pour revenir de l’état basse-consommation s à l’état actif. Cette pénalité énergétique correspond à la consommation énergétique nécessaire pour réactiver tous les composants qui ont été éteints lors de l’activation de l’état basse-consommation. Elle est consommée lorsque le processeur passe de l’état basseconsommation à l’état actif, c’est-à-dire lors du délai de transition. Plus la consommation énergétique d’un état basse-consommation est faible, plus sa pénalité est importante.
|
Table des matières
1 Introduction
1.1 Motivations
1.2 Objectif
1.3 Contributions
1.4 Plan
2 Contexte – État de l’art
2.1 Représentation des systèmes temps réel
2.1.1 Modélisation des tâches
2.1.2 Caractéristiques des algorithmes d’ordonnancement multiprocesseurs
2.2 Représentation de la consommation énergétique
2.2.1 Caractéristiques des processeurs ciblés
2.2.2 Modèles énergétiques
2.2.3 Possibilités matérielles pour contrôler la consommation énergétique
2.3 État de l’art
2.3.1 Réduction de la consommation dynamique
2.3.2 Réduction des consommations dynamique puis statique
2.3.3 Réduction de la consommation statique
2.4 Conclusion
3 Problématique
3.1 Exploitation des états basse-consommation
3.1.1 Prérequis sur le modèle de tâches et les capacités matérielles
3.1.2 Propriétés nécessaires aux algorithmes d’ordonnancement
3.2 Simplification pour la génération de l’ordonnancement
3.2.1 Simplification sur une hyperpériode
3.2.2 Calcul de la taille des périodes d’inactivité
3.2.3 Optimisation de la taille de la prochaine période d’inactivité
3.3 Cadres d’application
3.3.1 Systèmes temps réel dur
3.3.2 Systèmes temps réel à criticité mixte
3.4 Conclusion
4 Approche hybride
4.1 Fonctionnement général
4.1.1 Ordonnancement hors-ligne
4.1.2 Hypothèses et contraintes
4.1.3 Modélisation hors-ligne de l’inactivité du processeur
4.2 Résolution par programmation linéaire
4.2.1 Division de l’hyperpériode en intervalles
4.2.2 Contraintes d’ordonnançabilité
4.3 Cadres d’application
4.3.1 Systèmes temps réel dur
4.3.2 Systèmes temps réel à criticité mixtes
4.4 Ordonnancement en-ligne
4.5 Conclusion
5 Systèmes temps réel dur
5.1 Minimisation du nombre de périodes d’inactivité
5.1.1 Minimisation des préemptions à l’intérieur des intervalles
5.1.2 Minimisation des préemptions entre deux intervalles consécutifs
5.1.3 Fonction d’optimisation
5.1.4 Ordonnancement en-ligne
5.2 Minimisation de la consommation statique
5.2.1 Division de τ′ en deux sous-tâches
5.2.2 Calcul de la taille des périodes d’inactivité
5.2.3 Fonction d’optimisation
5.2.4 Ordonnancement en-ligne
5.3 Évaluation
5.3.1 Environnement de simulation
5.3.2 Résolution du programme linéaire
5.3.3 Comparaison entre LPDPM1 et LPDPM2
5.3.4 Comparaison avec les algorithmes existants
5.4 Conclusion
6 Systèmes temps réel à criticité mixte
6.1 Compromis entre dépassements d’échéances et gain énergétique
6.1.1 Introduction
6.1.2 Adaptation des contraintes et fonction objectif
6.1.3 Ordonnancement en-ligne
6.2 Évaluation
6.2.1 Utilisation des état basse-consommation
6.2.2 Consommation énergétique
6.2.3 Dépassements d’échéances
6.3 Conclusion
7 Conclusion et perspectives
7.1 Conclusion
7.2 Perspectives
7.2.1 Implémentation
7.2.2 Perspectives générales
7.2.3 Systèmes temps réel à criticité mixte
7.2.4 Modélisation
Bibliographie
Télécharger le rapport complet
