This thesis focuses on the scheduling of mixed-criticality scheduling algorithms for multi-processors. The correctness of the execution of the real-time applications is ensured by a scheduler and is checked during the design phase. The execution platform sizing aims at minimising the number of processors required to ensure this correct scheduling. This sizing is impacted by the safety requirements. Indeed, these requirements tend to overestimate the execution times of the applications to ensure their correct executions. Consequently, the resulting sizing is costly. The mixed-criticality scheduling theory aims at proposing compromises on the guarantees of the execution of the applications to reduce this over-sizing. Several models of mixed-criticality systems offering different compromises have been proposed but all are based on the use of execution modes. Modes are ordered and tasks have non decreasing execution times in each mode. Yet, to reduce the sizing of the execution platform, only the execution of the most critical tasks is ensured. This model is called the discarding model. For simplicity reasons, most of the mixed-criticality scheduling algorithms are limited to this model. Besides, the most efficient scheduling policies for multi-processors entail too many preemptions and migrations to be actually used. Finally, they are rarely generalised to handle different models of mixed-criticality systems. However, the handling of more than two execution modes or of tasks with elastic periods would make such solutions more attractive for the industry. The approach proposed in this thesis is based on the separation of concerns between handling the execution modes and the scheduling of the tasks on the multi-processors. With this approach, we achieve to design an efficient scheduling policy that schedules different models of mixed-criticality systems. It consists in performing the transformation of a mixed-criticality task set into a non mixed-criticality one. We then schedule this task set by using an optimal hard real-time scheduling algorithm that entails few preemptions and migrations: RUN. We first apply our approach on the discarding model with two execution modes. The results show the efficiency of our approach for such model. Then, we demonstrate the versatility of our approach by scheduling systems of the discarding model with more than two execution modes. Finally, by using a method based on the decomposition of task execution, our approach can schedule systems based on elastic tasks.

Ce document prĂ©sente nos contributions aux algorithmes d’ordonnancement Ă  criticitĂ© mixte pour multi-processeurs. La correction de l’exĂ©cution des applications temps rĂ©el critiques est assurĂ©e par l’utilisation d’un ordonnancement vĂ©rifiĂ© Ă  la conception. Dans ce contexte, le dimensionnement des plate-formes d’exĂ©cution vise Ă  minimiser le nombre de processeurs nĂ©cessaires pour assurer un ordonnancement correct. Ce dimensionnement est affectĂ© par les exigences de sĂ»retĂ© de fonctionnement. Ces exigences poussent Ă  surestimer le temps nĂ©cessaire garantissant l’exĂ©cution correcte des applications. Il en dĂ©coule un dimensionnement assez coĂ»teux. Les mĂ©thodes d’ordonnancement des systèmes Ă  criticitĂ© mixte proposent des compromis sur les garanties d’exĂ©cution des applications amĂ©liorant le dimensionnement. DiffĂ©rents compromis ont Ă©tĂ© proposĂ©s mais tous reposent sur la notion de mode d’exĂ©cution. Les modes sont ordonnĂ©s, et les tâches voient leur temps d’exĂ©cution requis croĂ®tre avec les modes. Cependant, afin de diminuer le dimensionnement du système, seul l’ordonnancement des tâches les plus critiques est garanti. Ce modèle est appelĂ© “discarding”. La majoritĂ© des algorithmes proposĂ©s se limitent Ă  deux modes d’exĂ©cutions par simplicitĂ©. De plus, les algorithmes les plus efficaces pour multi-processeurs exhibent un nombre Ă©levĂ© de prĂ©emptions, ce qui constitue un frein Ă  leur adoption. Finalement, ces algorithmes sont rarement gĂ©nĂ©ralisables. Pourtant, la prise en compte de plus de deux modes, ou de tâches aux pĂ©riodes Ă©lastiques permettrait une adoption plus large par le milieu industriel. L’approche proposĂ©e repose sur la sĂ©paration des prĂ©occupations entre la prise en compte des modes de fonctionnement, et l’ordonnancement des tâches sur multi-processeurs. Cette mĂ©thode permet de concevoir une politique d’ordonnancement efficace et adaptable Ă  diffĂ©rents modèles de systèmes Ă  criticitĂ© mixte. Notre approche consiste Ă  transformer un lot de tâches Ă  criticitĂ© mixte en un lot de tâches qui n’est plus Ă  criticitĂ© mixte. Ceci nous permet d’utiliser un algorithme d’ordonnancement temps rĂ©el optimal engendrant peu de prĂ©emptions et de migrations, Ă  savoir RUN. Cette approche, appliquĂ©e en premier pour le modèle discarding avec deux modes d’exĂ©cution, rempli son objectif d’efficacitĂ©. Nous illustrons sa gĂ©nĂ©ricitĂ© en utilisant le mĂŞme principe pour ordonnancer des systèmes discarding avec plus de deux modes d’exĂ©cution. Enfin, une dĂ©marche reposant sur la dĂ©composition de tâche permet de gĂ©nĂ©raliser l’approche au cas des tâches Ă©lastiques.