Calculation of Worst Case Execution Time safe upper bounds for hard real-time tasks, for systems using cache memories

Louise, Stéphane,

HAL, tel-00695930 / Harvested from HAL

Résumé

Ce mémoire présente une nouvelle approche pour le calcul de temps d'exécution au pire (WCET) de tâche temps-réel critique, en particulier en ce qui concerne les aléas dus aux caches mémoire. Le point général est fait sur la problématique et l'état de l'art en la matière, mais l'accent est mis sur la théorie elle-même et son formalisme, d'abord dans le cadre monotâche puis dans le cadre multitâche. La méthode utilisée repose sur une technique d'interprétation abstraite, comme la plupart des autres méthodes de calcul de WCET, mais le formalisme est dans une approche probabiliste (bien que déterministe dans le cadre monotâche) de par l'utilisation de chaînes de Markov. La généralisation au cadre multitâche utilise les propriétés proba- bilistes pour faire une évaluation pessimiste d'un WCET et d'un écart type au pire, grâce à une modification astucieuse du propagateur dans ce cadre. Des premières évaluations du modèle, codées à la main à partir des résultats de compilation d'applications assez simples montrent des résultats promet- teurs quant à l'application du modèle sur des programmes réels en vraie grandeur.

Détail

Publié le : 2002-01-21
Classification:  Worst-case Execution Time (WCET),  hard real-time systems,  static analysis,  Markov Model,  cache memory and memory hierarchy,  Temps d'exécution au pire cas (WCET),  systèmes temps-réels critiques,  analyse statique,  modèle de Markov,  Cache et hiérarchie mémoire,  [INFO.INFO-ES]Computer Science [cs]/Embedded Systems,  [MATH.MATH-OA]Mathematics [math]/Operator Algebras [math.OA],  [MATH.MATH-QA]Mathematics [math]/Quantum Algebra [math.QA],  [MATH.MATH-PR]Mathematics [math]/Probability [math.PR],  [INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR]