Calculation of latency of real-time system and fixed-parameter tractibility of UET-UCT scheduling problems
Calcul de la latence du système en temps réel et à paramètre fixe traçabilité des problèmes d'ordonnancement UET-UCT
Résumé
This thesis considers two main problems. The first problem considers the minimization of the makespan and the maximum lateness for a set of dependent tasks with unit duration, unit communication delays release times and due dates. Time windows of tasks are built from upper bounds of the makespan and the minimum maximum lateness respectively. A fixed-parameter algorithm based on a dynamic programming approach is developed to solve this optimization problem. The parameter considered is the pathwidth of the associated interval graph. They are, as far as we know, the first fixed-parameter algorithms for a scheduling problem with communication delays and a limited number of processors. The second problem considers real-time systems. Automotive and avionics embedded systems are usually composed by several tasks submitted to complex timing constraints. In this context, LET paradigm was introduced to improve the determinism of a system of tasks that communicate data through shared variables. The age latency corresponds to the maximum time for the propagation of a data in these systems. Its precise evaluation is an important challenging question for the design of these systems. We considered a set of multi-periodic tasks that communicate data following the LET paradigm. Our main contribution is the development of mathematical and algorithm tools to model precisely the dependence between tasks executions. Experiments on random generated graphs proved that systems with up to 90 periodic tasks with an hyper-period bounded by 100 can be handled within a reasonable time.
Cette thèse considère deux problèmes principaux. Le premier problème considère la minimisation du makespan et le retard maximum pour un ensemble de tâches dépendantes avec une durée unitaire, des retards de communication unitaires, des temps de libération et des dates d'échéance. Les fenêtres temporelles des tâches sont construites à partir des bornes supérieures du makespan et du retard maximum minimum respectivement. Un algorithme à paramètres fixes basé sur une approche de programmation dynamique est développé pour résoudre ce problème d'optimisation. Le paramètre considéré est la largeur de chemin du graphe d'intervalle associé. Ce sont, à notre connaissance, les premiers algorithmes à paramètres fixes pour un problème d'ordonnancement avec des retards de communication et un nombre limité de processeurs. Le deuxième problème concerne les systèmes en temps réel. Les systèmes embarqués automobiles et avioniques sont généralement composés de plusieurs tâches soumises à des contraintes temporelles complexes. Dans ce contexte, le paradigme LET a été introduit pour améliorer le déterminisme d'un système de tâches qui communiquent des données via des variables partagées. L'âge de latence correspond au temps maximum de propagation d'une donnée dans ces systèmes. Son évaluation précise est un défi important pour la conception de ces systèmes. Nous avons considéré un ensemble de tâches multi-périodiques qui communiquent des données selon le paradigme LET. Des expériences sur des graphes générés aléatoirement ont prouvé que des systèmes comportant jusqu'à 90 tâches périodiques avec une hyper-période bornée par 100 peuvent être traités dans un délai raisonnable.
Domaines
Recherche opérationnelle [math.OC]
Origine : Version validée par le jury (STAR)