Study and evaluation of real-time multiprocessor scheduling policies

De multiples algorithmes ont été proposés pour traiter de l’ordonnancement de tâchestemps réel dans un contexte multiprocesseur. Encore très récemment de nouvelles politiquesont été définies. Ainsi, sans garantie d’exhaustivité, nous en avons recensé plusd’une cinquantaine. Cette grande diversité rend difficile une analyse comparée de leurscomportements et performances. L’objectif de ce travail de thèse est de permettre l’étudeet l’évaluation des principales politiques d’ordonnancement existantes. La première contributionest SimSo, un nouvel outil de simulation dédié à l’évaluation des politiques. Grâceà cet outil, nous avons pu comparer les performances d’une vingtaine d’algorithmes. Laseconde contribution est la prise en compte, dans la simulation, des surcoûts temporelsliés à l’exécution du code de l’ordonnanceur et à l’influence des mémoires caches sur la duréed’exécution des travaux par l’introduction de modèles statistiques évaluant les échecsd’accès à ces mémoiresNumerous algorithms have been proposed to address the scheduling of real-time tasksfor multiprocessor architectures. Yet, new scheduling algorithms have been defined veryrecently. Therefore, and without any guarantee of completeness, we have identified morethan fifty of them. This large diversity makes the comparison of their behavior and performancedifficult. This research aims at allowing the study and the evaluation of keyscheduling algorithms. The first contribution is SimSo, a new simulation tool dedicatedto the evaluation of scheduling algorithms. Using this tool, we were able to compare theperformance of twenty algorithms. The second contribution is the consideration, in the simulation,of temporal overheads related to the execution of the scheduler and the impactof memory caches on the computation time of the jobs. This is done by the introductionof statistical models evaluating the cache miss ratio