La prolifération de petits équipements ouverts tels que les dispositifs personnels de confiance a favorisé l'essor des environnements d'exécution dynamiquement adaptables. Ainsi, de nouveaux logiciels peuvent être déployés à la volée après que les équipements soient délivrés à leurs porteurs. Par nos travaux, nous aspirons à garantir que chaque nouveau logiciel, dont le déploiement aboutit, est en mesure de délivrer les réponses aux requêtes qui lui sont adressées dans un délai maximal préalablement établi. Les garanties apportées sont cruciales tant en terme de sûreté de fonctionnement que de sécurité. À cet effet, nous avons proposé de distribuer le calcul du temps d'exécution au pire cas à la manière des approches de codes porteurs de preuve. Le fournisseur de code se voit attribuer les calculs gourmands en ressources matérielles ne supposant aucune connaissance préalable de l'environnement d'exécution sur lequel s'exécutera son logiciel, en l'occurrence la détermination des bornes des boucles. Quant au consommateur, il vérifie grâce à la preuve les bornes inférées par le fournisseur et calcule le temps d'exécution au pire cas. Nous avons évalué expérimentalement le bien-fondé de notre démarche sur une architecture matérielle et logicielle répondant aux exigences des dispositifs personnels de confiance. Enfin, nous nous sommes préoccupés du cas où plusieurs logiciels, émanant d'entité différentes, coexistent. Nous avons mis l'accent sur l'impact de l'interaction entre ces logiciels sur les garanties préalablement apportées par le système sur le temps d'exécution au pire cas et nous avons ébauché une solution basée sur les contrats pour maintenir ces garanties. / The proliferation of small and open objects such as personal trusted devices has encouraged the spread of dynamically adaptable runtime environments. Thus, new software can be deployed on the fly after the devices are delivered to their holders. Through our work, we aim to ensure that each new software, whose deployment is successful, will be able to deliver responses within a maximum delay previously established. These guarantees are crucial in terms of safety and security. To this end, we propose to distribute the computation of worst case execution time. Our solution embraces a proof carrying code approach making distinction between a powerful but untrusted computer used to produce the code, and a safe but resource constrained code consumer. The producer does not assume any prior knowledge of the runtime environment on which its software will be executed. The code is statically analyzed to extract loop bounds and a proof containing this information is joint to the software. By a straightforward inspection of the code, the consumer can verify the validity of the proof and compute the global worst case execution time. We experimentally validate our approach on a hardware and software architecture which meets the requirements of trusted personal devices. Finally, we address the challenges raised when software from different service providers potentially untrusted can coexist and interact in a single device. We focus on the impact of the interaction between different software units on the guarantees previously given by the system on the worst case execution time and we outline a solution based on contracts to maintain these guarantees.

La plupart des méthodes d'ordonnancement considèrent un environnement déterministe où les données du problème sont connues. Néanmoins, en réalité, plusieurs sortes d'aléas peuvent être rencontrées et l'ordonnancement robuste permet en tenir compte. Dans cette thèse, notre intuition initiale est que, d'une part, un ordonnancement non robuste deviendra rapidement inefficace avec les incertitudes qu'un ordonnancement robuste, et d'autre part, un ordonnancement robuste sera moins efficace qu'un ordonnancement non robuste en l'absence d'incertitudes. Dans ce cadre, nous avons proposé un algorithme génétique pour l'ordonnancement robuste. Un nouveau mécanisme de résolution et un nouveau critère de robustesse permettant de trouver une solution de bonne performance et peu sensible aux incertitudes ont été développés. Une phase expérimentale a été menée, d'une part, pour vérifier l'efficacité de l'algorithme génétique pour l'ordonnancement déterministe, sans tenir compte des incertitudes, et d'autre part, pour valider l'algorithme génétique pour l'ordonnancement robuste par la simulation afin de juger la qualité de la robustesse face aux incertitudes. Nous avons intégré cette approche de robustesse dans une démarche méthodologique générique intégrant des techniques d'optimisation et de simulation pour l'aide au dimensionnement des systèmes de production basé sur des ordonnancements robustes. Les différents modules de la démarche ont été développés sous forme d'un outil d'aide au dimensionnement, dans le cadre d'un cas applicatif réel, celui du bloc opératoire dans le secteur hospitalier.

Une des solutions les plus prometteuses actuellement à la course à la puissance de traitement consiste à créer des grilles. Néanmoins, leur utilisation optimale n'est pas encore atteinte dû notamment à la complexité que ce support d'exécution amène pour les administrateurs et utilisateurs. Cette thèse se concentre sur la gestion des ressources composant une grille de calcul. Nous montrons comment traiter ce problème à l'aide de paradigmes économiques. Nous définissons un modèle économique permettant de gérer les ressources d'une grille. Ce modèle propose d'associer un coût à chacune des machines de la grille. Le placement d'une application est assimilé à un problème d'optimisation non-linéaire sous contraintes et à variables entières, pour lequel le choix des machines à utiliser doit minimiser un compromis entre le temps d'exécution de l'application et son coût. Une implémentation de ce modèle à l'aide d'un algorithme génétique est proposée, de même que son intégration au sein de l'ordonnanceur OAR utilisé sur Grid'5000. Dans une seconde partie de la thèse, des travaux ont été effectués dans le domaine de la prédiction du temps d'exécution d'une application. Nous définissons une méthode hybride de prédiction basée à la fois sur le profil des applications ainsi que sur un historique d'exécutions passées, combinant une analyse de la structure du programme à une méthode d'apprentissage basé sur des instances. Nous montrons notamment que la prise en compte du profil des applications améliore les prédictions réalisées au moyen de méthodes classiques basées seulement sur des historiques d'exécutions passées.

Les défaillances des applications embarquées dans les systèmes temps-réel strict peuvent avoir des conséquences graves (catastrophes industrielles, mise en danger de vies humaines). La vérification des contraintes temporelles d'un système temps-réel strict dépend de la connaissance du temps d'exécution pire-cas des tâches constituant l'application embarquée. L'utilisation de processeurs multi-cœurs est l'un des moyens actuellement mis en œuvre afin d'améliorer le niveau de performances des systèmes embarqués. Cependant, la détermination du temps d'exécution pire-cas d'une tâche sur ce type d'architecture est rendue difficile par le partage de certaines ressources par les cœurs, et notamment le bus d'interconnexion permettant l'accès à la mémoire centrale. Ce document propose un nouveau mécanisme d'arbitrage de bus à deux niveaux permettant d'améliorer les performances des ensembles de tâches exécutés tout en garantissant le respect des contraintes temporelles. Les méthodes décrites permettent d'établir un niveau de priorité d'accès au bus optimal pour chacune des tâches exécutées. Elles permettent également de trouver une allocation optimale des tâches aux cœurs lorsqu'il y a plus de tâches à exécuter que de cœurs disponibles. Les résultats expérimentaux montrent une diminution significative des estimations de temps d'exécution pire-cas et de l'utilisation du processeur.

L'interaction sociale, l'éducation et la santé ne sont que quelques exemples de domaines dans lesquels l'évolution rapide de la technologie a eu un grand impact sur la qualité de vie. Les entreprises s’appuient de plus en plus sur les systèmes embarqués pour augmenter leur productivité, leur efficacité et leurs valeurs. Dans les usines, la précision des robots tend à remplacer la polyvalence humaine. Bien que les appareils connectés comme les drônes, les montres intelligentes ou les maisons intelligentes soient de plus en plus populaires ces dernières années, ce type de technologie a été utilisé depuis longtemps dans les industries concernées par la sécurité des utilisateurs. L’industrie avionique utilise des ordinateurs pour ses produits depuis 1972 avec la production du premier avion A300; elle a atteint des progrès étonnants avec le développement du premier avion Concorde en 1976 en dépassant de nombreuses années les avions de son époque, et ça a été considéré comme un miracle de la technologie. Certaines innovations et connaissances acquises pour le Concorde sont toujours utilisées dans les modèles récents comme A380 ou A350. Un système embarqué est un système à microprocesseur qui est construit pour contrôler une fonction ou une gamme de fonctions et qui n’est pas conçu pour être programmé par l'utilisateur final de la même manière qu'un ordinateur personnel. Un système temps-réel est un système de traitement de l’information qui doit répondre aux stimuli d’entrées générées de manière externe dans une période finie et spécifiée. Le comportement de ces systèmes prend en compte non seulement l'exactitude dépend non seulement du résultat logique mais aussi du temps dans lequel il a été livré. Les systèmes temps-réel peuvent être trouvés dans des industries comme l'aéronautique, l'aérospatiale, l'automobile ou l’industrie ferroviaire mais aussi dans les réseaux de capteurs, les traitements d'image, les applications multimédias, les technologies médicales, les robotiques, les communications, les jeux informatiques ou les systèmes ménagers. Dans cette thèse, nous nous concentrons sur les systèmes temps-réel embarqués et pour la facilité des notations, nous leur nommons simplement des systèmes temps réel. Nous pourrions nous référer aux systèmes cyber-physiques si tel est le cas. Le pire temps d’exécution (WCET) d'une tâche représente le temps maximum possible pour qu’elle soit exécutée. Le WCET est obtenu après une analyse de temps et souvent il ne peut pas être déterminé avec précision en déterminant toutes les exécutions possibles. C'est pourquoi, dans l'industrie, les mesures sont faites uniquement sur un sous-ensemble de scénarios possibles, celui qui générerait les temps d'exécution les plus élevés, et une limite supérieure de temps d’exécution est estimé en ajoutant une marge de sécurité au plus grand temps observé. L’analyses de temps est un concept clé qui a été utilisé dans les systèmes temps-réel pour affecter une limite supérieure aux WCET des tâches ou des fragments de programme. Cette affectation peut être obtenue soit par analyse statique, soit par analyse des mesures. Les méthodes statiques et par mesure, dans leurs approches déterministes, ont tendance à être extrêmement pessimistes. Malheureusement, ce niveau de pessimisme et le sur-provisionnement conséquent ne peut pas être accepté par tous les systèmes temps-réels, et pour ces cas, d'autres approches devraient être prises en considération. / In our times, we are surrounded by technologies meant to improve our lives, to assure its security, or programmed to realize different functions and to respect a series of constraints. We consider them as embedded systems or often as parts of cyber-physical systems. An embedded system is a microprocessor-based system that is built to control a function or a range of functions and is not designed to be programmed by the end user in the same way that a PC is. The Worst Case Execution Time (WCET) of a task represents the maximum time it can take to be executed. The WCET is obtained after analysis and most of the time it cannot be accurately determined by exhausting all the possible executions. This is why, in industry, the measurements are done only on a subset of possible scenarios (the one that would generate the highest execution times) and an execution time bound is estimated by adding a safety margin to the greatest observed time. Amongst all branches of real-time systems, an important role is played by the Critical Real-Time Embedded Systems (CRTES) domain. CRTESs are widely being used in fields like automotive, avionics, railway, health-care, etc. The performance of CRTESs is analyzed not only from the point of view of their correctness, but also from the perspective of time. In the avionics industry such systems have to undergo a strict process of analysis in order to fulfill a series of certification criteria demanded by the certifications authorities, being the European Aviation Safety Agency (EASA) in Europe or the Federal Aviation Administration (FAA) in United States. The avionics industry in particular and the real-time domain in general are known for being conservative and adapting to new technologies only when it becomes inevitable. For the avionics industry this is motivated by the high cost that any change in the existing functional systems would bring. Any change in the software or hardware has to undergo another certification process which cost the manufacturer money, time and resources. Despite their conservative tendency, the airplane producers cannot stay inactive to the constant change in technology and ignore the performance benefices brought by COTS processors which nowadays are mainly multi-processors. As a curiosity, most of the microprocessors found in airplanes flying actually in the world, have a smaller computation power than a modern home PC. Their chips-sets are specifically designed for embedded applications characterized by low power consumption, predictability and many I/O peripherals. In the actual context, where critical real-time systems are invaded by multi-core platforms, the WCET analysis using deterministic approaches becomes difficult, if not impossible. The time constraints of real-time systems need to be verified in the context of certification. This verification, done during the entire development cycle, must take into account architectures more and more complex. These architectures increase the cost and complexity of actual, deterministic, tools to identify all possible time constrains and dependencies that can occur inside the system, risking to overlook extreme cases. An alternative to these problems is the probabilistic approach, which is more adapted to deal with these hazards and uncertainty and which allows a precise modeling of the system. 2. Contributions. The contribution of the thesis is three folded containing the conditions necessary for using the theory of extremes on executions time measurements, the methods developed using the theory of extremes for analyzing real-time systems and experimental results. 2.1. Conditions for use of EVT in the real-time domain. In this chapter we establish the environment in which our work is done. The use of EVT in any domain comes with a series of restrictions for the data being analyzed. In our case the data being analyzed consists in execution time measurements.

Dans les systèmes informatiques temps réel, les tâches logicielles sont contraintes par le temps. Pour garantir la sûreté du système critique contrôlé par le système temps réel, il est primordial d'estimer de manière sûre le pire temps d'exécution de chaque tâche. Les performances des processeurs actuels du commerce permettent de réduire en moyenne le temps d'exécution des tâches, mais la complexité des composants d'optimisation de la plateforme rendent difficile l'estimation du pire temps d'exécution. Il existe différentes approches d'estimation du pire temps d'exécution, souvent ségréguées et difficilement généralisables ou au prix de modèles coûteux. Les approches probabilistes basées mesures existantes sont vues comme étant rapides et simples à mettre en œuvre, mais souffrent d'un manque de systématisme et de confiance dans les estimations qu'elles fournissent. Les travaux de cette thèse étudient les conditions d'application de la théorie des valeurs extrêmes à une suite de mesures de temps d'exécution pour l'estimation du pire temps d'exécution probabiliste, et ont été implémentées dans l'outil diagxtrm. Les capacités et les limites de l'outil ont été étudiées grâce à diverses suites de mesures issues de systèmes temps réel différents. Enfin, des méthodes sont proposées pour déterminer les conditions de mesure propices à l'application de la théorie des valeurs extrêmes et donner davantage de confiance dans les estimations. / Software tasks are time constrained in real time computing systems. To ensure the safety of the critical systems that embeds the real time system, it is of paramount importance to safely estimate the worst-case execution time of each task. Modern commercial processors optimisation components enable to reduce in average the task execution time at the cost of a hard to determine task worst-case execution time. Many approaches for executing a task worst-case execution time exist but are usually segregated and hardly scalable, or by building very complex models. Measurement-based probabilistic timing analysis approaches are said to be easy and fast, but they suffer from a lack of systematism and confidence in their estimates. This thesis studies the applicability of the extreme value theory to a sequence of execution time measurements for the estimation of the probabilistic worst-case execution time, leading to the development of the diagxtrm tool. Thanks to a large panel of sequences of measurements from different real time systems, capabilities and limits of the tool are enlightened. Finally, a couple of methods are provided for determining measurements conditions that foster the application of the theory and raise more confidence in the estimates.

Les tâches critiques en systèmes temps-réel sont soumises à des contraintes temporelles et de correction. La validation d'un tel système repose sur l'estimation du comportement temporel au pire cas de ses tâches. Le partage de ressources, inhérent aux architectures multi-cœurs, entrave le calcul de ces estimations. Le comportement temporel d'une tâche dépend de ses rivales du fait de l'arbitrage de l'accès aux ressources ou de modifications concurrentes de leur état. Cette étude vise à l'estimation de la contribution temporelle de la hiérarchie mémoire au pire temps d'exécution de tâches critiques. Les méthodes existantes, pour caches d'instructions, sont étendues afin de supporter caches de données privés et partagés, et permettre l'analyse de hiérarchies mémoires riches. Le court-circuitage de cache est ensuite utilisé pour réduire la pression sur les caches partagés. Nous proposons à cette fin différentes heuristiques basées sur la capture de la réutilisation de blocs de cache entre différents accès mémoire. Notre seconde proposition est la politique de partitionnement Preti qui permet l'allocation d'un espace sans conflits à une tâche. Preti favorise aussi les performances de tâches non critiques concurrentes aux temps-réel dans les systèmes de criticité hybride.

Afin de garantir qu'un programme respectera toutes ses contraintes temporelles, nous devons être capable de calculer une estimation fiable de son temps d'exécution au pire cas (WCET: worst case execution time). Cependant, identifier une borne précise du pire temps d'exécution devient une tâche très complexe du fait de la sophistication croissante des processeurs. Ainsi, l'objectif de nos travaux de recherche a été de définir une méthode formelle qui puisse s'adapter aux évolutions du matériel. Cette méthode consiste à développer un modèle du processeur cible, puis à l'exécuter symboliquement afin d'associer à chaque trace d'exécution un temps d'exécution au pire cas. Une méthode de fusionnement est également prévue afin d'éviter une possible explosion combinatoire. Cette méthode a pour principale contrainte de ne pas introduire trop d'imprécision sur les temps calculés.

Afin de garantir qu'un programme respectera toutes ses contraintes temporelles, nous devons être capable de calculer une estimation fiable de son temps d'exécution au pire cas (WCET: worst case execution time). Cependant, identifier une borne précise du pire temps d'exécution devient une tâche très complexe du fait de la sophistication croissante des processeurs. Ainsi, l'objectif de nos travaux de recherche a été de définir une méthode formelle qui puisse s'adapter aux évolutions du matériel. Cette méthode consiste à développer un modèle du processeur cible, puis à l'exécuter symboliquement afin d'associer à chaque trace d'exécution un temps d'exécution au pire cas. Une méthode de fusionnement est également prévue afin d'éviter une possible explosion combinatoire. Cette méthode a pour principale contrainte de ne pas introduire trop d'imprécision sur les temps calculés. / To ensure that a program will respect all its timing constraints we must be able to compute a safe estimation of its worst case execution time (WCET). However with the increasing sophistication of the processors, computing a precise estimation of the WCET becomes very difficult. In this report, we propose a novel formal method to compute a precise estimation of the WCET that can be easily parameterized by the hardware architecture. Assuming that we developed an executable timed model of the hardware, we use symbolic execution to precisely infer the execution time for a given instruction flow. We also merge the states relying on the loss of precision we are ready to accept, in order to avoid a possible states explosion.

Les tâches critiques en systèmes temps-réel sont soumises à des contraintes temporelles et de correction. La validation d'un tel système repose sur l'estimation du comportement temporel au pire cas de ses tâches. Le partage de ressources, inhérent aux architectures multi-cœurs, entrave le calcul de ces estimations. Le comportement temporel d'une tâche dépend de ses rivales du fait de l'arbitrage de l'accès aux ressources ou de modifications concurrentes de leur état. Cette étude vise à l'estimation de la contribution temporelle de la hiérarchie mémoire au pire temps d'exécution de tâches critiques. Les méthodes existantes, pour caches d'instructions, sont étendues afin de supporter caches de données privés et partagés, et permettre l'analyse de hiérarchies mémoires riches. Le court-circuitage de cache est ensuite utilisé pour réduire la pression sur les caches partagés. Nous proposons à cette fin différentes heuristiques basées sur la capture de la réutilisation de blocs de cache entre différents accès mémoire. Notre seconde proposition est la politique de partitionnement Preti qui permet l'allocation d'un espace sans conflits à une tâche. Preti favorise aussi les performances de tâches non critiques concurrentes aux temps-réel dans les systèmes de criticité hybride. / Critical tasks in the context of real-time systems submit to both timing and correctness constraints. Whence, the validation of a real-time system rely on the estimation of its tasks’ Worst case execution times. Resource sharing, as it occurs on multicore architectures, hinders the computation of such estimates. The timing behaviour of a task is impacted by its concurrents, whether because of resource access arbitration or concurrent modifications of a resource state. This study focuses on estimating the contribution of the memory hierarchy to tasks’ worst case execution time. Existing analysis methods, defined for instruction caches, are extended to support private and shared data caches, hence allowing for the analysis of rich memory hierarchies. Cache bypass is then used to reduce the pressure laid by concurrent tasks on shared caches levels. We propose different bypass heuristics, based on the capture of cache blocks’ reuse between memory accesses. Our second proposal is the Preti partitioning scheme which allows for the allocation to tasks of a cache space, free from inter-task conflicts. Preti offers the added benefit of providing for average-case performance to non-critical tasks concurrent to real-time ones on hybrid criticality systems.