Analyses pour l'ordonnançabilité et la flexibilité de systèmes temps réel

Real-time systems are often used for applications in avionics or automotive domains. For those systems, timing constraints are as important as functional constraints. Thus for each functionality it is necessary to compute the maximum duration, denoted worst case latency, between data acquisition and the corresponding restitution of results. Given the needs that we identify at Thales firm, we consider uni-processor systems scheduled under fixed priority preemptive scheduling with task chains mapped on them. Each chain implements a functionality and each task has a fix and unique priority. The finishing time of a task triggers the activation of the following one in the chain. The processor always executes the task with the highest priority. Then we use scheduling analysis to characterize the timing behavior of systems and compute the worst case latency of chains. If the worst case latency of each chain is lower than or equal to its timing constraint then the system is schedulable. To guarantee the schedulability of a system, we compute upper bounds that are higher than or equal to the worst case latency, and these bounds may be over-approximated depending on the precision of the analysis. For a given system, if over-approximations are too important then it is necessary to over-dimension the system to guarantee its schedulability, that is not desirable in a industrial context. To solve this over-dimension problem, we compute a more precise and/or general upper bound than in the state of the art. When the upper bound is computed, it is useful to measure the gap between the worst case latency and its upper bound. To achieve this, we compute a lower bound on the worst case latency to evaluate the precision of the upper bound. In the state of the art, lower bounds are computed using simulation. We propose to use schedulability analysis to compute lower bounds that we define as execution scenarios that are realizable considering the system model. Lower bounds are developed using equations established to compute upper bounds. Finally, considering long lifetime of systems and the quick evolution of technologies, many systems have to evolve. A relevant evolution in an industrial context consists in adding a new chain in an existing system. To guarantee the schedulability of a system in this context we present a methodology to compute the largest execution time of a new chain while giving guarantees on the schedulability of the new system. This analysis may be used to analyze the sensitivity and/or the robustness of a system with respect to parameter changes as execution times of tasks. This consists in finding extreme values of a timing parameters such that the system remains schedulable. In this thesis, we present analyses to compute upper and lower bounds on the worst case latency and to schedule a new chain while giving guarantees on the schedulability. These works may be extended to handle more complex systems and computation of lower bound could be adapted to other analysis. Finally, developed analysis are complex, it would be interesting to formalize them using a proof assistant to guarantee that they are exact.Les systèmes temps réel sont développés pour de nombreuses applications dans les domaines de l'avionique ou l'automobile. Pour ces systèmes les contraintes temporelles sont aussi importantes que les contraintes fonctionnelles. Ainsi pour chaque fonctionnalité il faut calculer le temps maximum, appelé latence de bout en bout au pire cas, entre l'acquisition d'une donnée et la restitution du résultat correspondant. Compte tenu des besoins rencontrés au sein de l'entreprise Thales, nous considérons des systèmes mono-processeurs ordonnancés sous ordonnanceur préemptif à priorités fixes sur lesquels sont allouées des chaînes de tâches. Chaque chaîne implémente une fonctionnalité distincte et chaque tâche possède une priorité fixe et unique. La terminaison d'une tâche au sein d'une chaîne entraîne l'activation de la tâche suivante. Quant au processeur, il exécute toujours la tâche de priorité maximale. Nous utilisons ensuite l'analyse d'ordonnançabilité pour caractériser le comportement temporel des systèmes et calculer la latence au pire cas des chaînes. Si la latence au pire cas de chaque chaîne du système est inférieure à son échéance temporelle alors ce système est ordonnançable. Pour garantir l'ordonnançabilité d'un système, on calcule des majorants, qui sont supérieurs ou égaux à la latence au pire cas, et qui peuvent être surapproximés en fonction de la précision des analyses. Pour un système donné, si les surapproximations sont trop importantes alors il faut le surdimensionner afin de garantir son ordonnançabilité, ce qui n'est pas souhaitable dans un contexte industriel. Pour résoudre ce problème de surdimensionnement, nous calculons un majorant qui est plus précis et/ou plus général que ceux présentés dans l'état de l'art. Une fois le majorant calculé, il est utile de mesurer l'écart maximum entre la latence au pire cas d'une chaîne et son majorant. Dans cet objectif, nous calculons un minorant sur la latence au pire cas pour évaluer la précision du majorant. Dans l'état de l'art, les minorants sont calculés par simulation. Nous proposons quant à nous d'utiliser l'analyse d'ordonnançabilité pour calculer des minorants que nous définissons comme des scénarios réalisables compte tenu du modèle du système. Les calculs des minorants sont développés en utilisant les analyses développées pour le calcul des majorants. Pour finir, compte tenu des longs cycles de vies ou de l'évolution rapide des technologies, de nombreux systèmes sont amenés à évoluer. Une évolution pertinente dans un contexte industriel consiste au rajout d'une chaîne de tâches à un système existant. Pour garantir l'ordonnançabilité du système dans ce contexte, nous présentons une méthode pour calculer le plus grand temps d'exécution qui peut être alloué à la nouvelle chaîne tout en garantissant l'ordonnançabilité du nouveau système. Cette analyse peut être utilisée pour analyser la sensibilité et/ou la robustesse d'un système face à des changements de paramètres comme par exemple les temps d'exécution des tâches. Cela consiste à trouver les valeurs extrêmes d'un paramètre temporel de telle sorte que le système reste ordonnançable. Dans cette thèse, nous avons présenté des analyses pour majorer et minorer la latence au pire cas d'une chaîne et permettre à un système d'ordonnancer une nouvelle chaîne tout en étant garanti ordonnançable. Ces travaux pourront être étendus en analysant des systèmes plus complexes et en adaptant le calcul des minorants à d'autres types d'analyses. Pour finir, les analyses développées sont complexes, il serait intéressant de les formaliser via un assistant informatique (exemple: PROSA) de manière à garantir leur exactitude