Ordonnancement non préemptif et condition d'ordonnançabilité pour systèmes embarqués à contraintes temps réel

Après un état de l'art sur l'ordonnancement en général et l'ordonnancement temps réel en particulier, permetttant de préciser les notions utilisées en suite et après avoir motivé l'intérêt d'une nouvelle contrainte temps réel de latences, nous proposons un modèle qui formalise les systèmes temps réel avec contraintes de précédences, de périodicités et de latences. Dans ce modèle, les précédences sont définie par un graphe orienté acyclique. Pour le cas monoprocesseur, on étudie trois problèmes d'ordonnancement : des systèmes avec contraintes de précédences et de périodicités, des systèmes avec contraintes de précédences et latences et des systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème on étudie la cohérence entre les contraintes, on donne des conditions d'ordonnançabilité et on propose un algorithme prouvé optimal dans le sens où s'il y a un ordonnancement, l'algorithme le trouvera. On passe en suite au cas multiprocessor où l'architecture est définie par un graphe non-orienté. On étudie trois problèmes d'implantation (distribution et ordonnancement) : des systèmes avec contraintes de précédences et de périodicités, systèmes avec contraintes de précédences et de latences et systèmes avec contraintes de précédences, de périodicités et de latences. Pour chaque problème, le modèle prend en compte les communications. On prouve que ces trois problèmes sont NP-difficiles et on propose, donc, des heuristiques. Les performances de chaque heuristique sont comparées à celles d'algorithme exacte de type "branch and bound", en utilisant des simulations numériques.After a state of art on classical scheduling and on real-ime scheduling, particularly, allowing to define the notions used afterwards and after motivating a new real-time constraint of latency, we propose a model which describes the real-time systems with precedence, periodicity and latency constraints. In this model, the precedences are defined using a directed acyclic graph. In the monoprocessor case, we study three problems of scheduling: systems with precedence and periodicity constraints, systems with precedence and latency constraint and systems with precedence, periodicity and latency constraints. For each problem we study the relation between the precedences and the periodicity, respectively the latency, we give schedulability conditions and we propose scheduling algorithm which are proved optimal (if there is a schedule, the algorithm will find it). For the multiprocessor case the architecture is defined by a non-oriented graph. We study three multiprocessor scheduling problems: of systems with precedences and periodicty constraints, of systemes with precedences and latency constraints and of systems with precedences, periodicity and latency constraints. For each problem the model takes into account the communications. We prove that each problem is NP-hard and we propose heuristics. The performances of each heuristic is compared to those of an exact algorithm of type branch and bound, using numerical simulations.ORSAY-PARIS 11-BU Sciences (914712101) / SudocSudocFranceF