Soutenance mémoire
Un système temps réel est un système avec des contraintes temporelles fortes [Sta88, Fis07] : la validité du système ne dépend pas seulement du résultat mais également de la date à laquelle le résultat a été obtenu. Ces systèmes sont de plus en plus présents autour de nous, que ce soit dans les produits grand public ou industriels. Leur étude est un domaine actif de la recherche, notamment pour exploiter au mieux les capacités matérielles tout en respectant les contraintes temporelles. Les travaux existants ont notamment cherché à améliorer l’ordonnançabilité de ces systèmes, c’est-à-dire garantir qu’un nombre maximum de tâches puissent être exécutées sur le système tout en garantissant qu’aucune échéance ne soit violée.
Un système embarqué est un système soumis à certaines contraintes en raison de son environnement. Contrairement à un système classique, il est situé dans un environnement plus ou moins « hostile » avec principalement des contraintes d’énergie et d’espace. Par exemple, les constructeurs automobiles intègrent maintenant de plus en plus de systèmes embarqués dans leurs véhicules et ces systèmes doivent prendre le moins de place possible pour s’intégrer dans l’habitacle du véhicule.
Représentation des systèmes temps réel
Nous définissons dans cette section la terminologie utilisée pour modéliser un système temps réel, tout d’abord les tâches puis les algorithmes d’ordonnancement. Nous définissons un système comme un ensemble de composants centrés sur une unité de calcul (i.e. un processeur) et également une mémoire ainsi que des entrées/sorties pour communiquer avec le monde extérieur. Au niveau logiciel, un système d’exploitation est nécessaire pour intégrer ces différents composants, c’est la plus basse couche logicielle s’exécutant sur le processeur. Elle est chargée de faire la liaison entre les applications du système et ses composants.
Les systèmes temps réel sont généralement séparés en plusieurs catégories suivant le niveau de sûreté temporelle demandé. Les deux catégories principales sont le temps réel dur et le temps réel mou. Un système temps réel dur est un système où aucune contrainte temporelle ne peut être violée. Chaque violation est considérée comme critique et le système ne peut fonctionner correctement en cas de violation de contrainte. Au contraire, un système temps réel mou peut tolérer que certaines contraintes temporelles ne soient pas satisfaites. Ces violations ne sont pas critiques pour le bon fonctionnement du système et peuvent seulement dégrader l’expérience utilisateur du système sans compromettre le fonctionnement global. Le temps réel mou peut par exemple être trouvé dans les systèmes multimédia qui fonctionnent correctement même si l’image ou le son sont retardés.
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.
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.
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é ne 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.
|
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 Conclusion
Télécharger le rapport complet
