Spelling suggestions: "subject:"analyse d’d'ordonnançabilité"" "subject:"analyse d’l'ordonnançabilité""
1 |
Cadre fondé sur les modèles pour une utilisation avancée de la théorie de l’ordonnancement dans la conception des systèmes temps réel / Model-based Framework for Using Advanced Scheduling Theory in Real-Time Systems DesignOuhammou, Yassine 12 December 2013 (has links)
Les systèmes embarqués temps réel nécessitent une analyse temporelle pour valider leur comportement temporel.Afin de réduire le coût de développement, l’analyse doit être effectuée à une phase précoce au moment de la modélisationpour détecter les anomalies de conception. L’analyse d’ordonnançabilité est une des analyses temporelles qui permettentde s’assurer du bon fonctionnement du système conçu. Elle est issue de la théorie de l’ordonnancement temps réel.Plusieurs méthodes et tests analytiques ont été proposés par la communauté académique mais peu sont les tests adoptéspar les industriels. En effet, l’utilisation des tests d’analyse exige une large connaissance des travaux de recherches - misà jour régulièrement - afin de choisir la méthode la plus adaptée aux systèmes conçus pour les valider ou les dimensionnerpour le cas des systèmes qui sont en cours de conception.Cette thèse s’intéresse à cette utilisation minimaliste de la théorie de l’ordonnancement dans l’industrie, et propose dessolutions d’aide à la décision basées sur l’ingénierie dirigée par les modèles. Nos solutions visent à augmenter l’applicabilitéde la théorie de l’ordonnancement, à faciliter le choix des tests appropriés et à réduire le surdimensionnement qui peutêtre généré au moment de la conception. Ces solutions sont implémentées dans un Framework appelé MoSaRT offrantdes fonctionnalités pour les concepteurs (modeleurs et analystes) afin d’améliorer le processus de conception des systèmestemps réel en vue de leur ordonnançabilité. / Real-time embedded systems need to be analyzed at an early stage in order to detect temporal vulnerabilities. Indeed,software development costs are sharply impacted by wrong design choices made in the early stages of development, inparticular during the design phase, but often detected after the implementation. The schedulability analysis is one of themain analyses required to ensure the timing correctness of a real-time system. Indeed, the real-time scheduling theoryhas been devoted to propose different models providing several levels of expressiveness, and different analytical methodswith different levels of accuracy. The utilization of the real-time scheduling theory in practical cases could be profitable.Unfortunately, it is not sufficiently applied and research results have been exploited in an industrial context only to amodest extent to date. Actually, a difficulty faced by the real-time designers is to find the appropriate analysis testshelping to validate properly the system and also to reduce the over-dimensioning. This thesis is interested in the chasmexisting between real-time design community and real-time analysis community. The purpose of our work is to fill thegap between the modeling of real-time systems and the scheduling analysis. Then, we propose a decision aiding solutionbased on model-driven engineering. Our solution is dedicated (i) to increase the usage of the real-time scheduling theory,(ii) to facilitate the scheduling analysis tests choice and (iii) to reduce the pessimism during the design phase of real-timesystems.Our proposal is embodied as a framework unifying the designers and analysts efforts. The framework called MoSaRToffers a design language very close to the taxonomy of real-time scheduling theory. Moreover, MoSaRT provides ananalysis repository concept to enhance the applicability of the scheduling theory and also to improve the way designerscheck their designs.
|
2 |
Ordonnancement temps réel dur multiprocesseur tolérant aux fautes appliqué à la robotique mobile / Fault tolerant multiprocessor hard real-time scheduling for mobile roboticsMarouf, Mohamed 01 June 2012 (has links)
Nous nous sommes intéressés dans cette thèse au problème d'ordonnancement temps réel dur multiprocesseur tolérant aux fautes pour des tâches non préemptives périodiques strictes pouvant être combinées avec des tâches préemptives. Nous avons proposé des solutions à ce problème et les avons implantées dans le logiciel SynDEx puis nous les avons testées sur une application de suivi de véhicules électriques CyCabs. Nous avons d'abord présenté un état de l'art sur les systèmes temps réel embarqués et plus précisément sur l'ordonnancement classique monoprocesseur et multiprocesseur de tâches préemptives périodiques. Comme nous nous intéressons aux applications de contrôle/commande temps réel critiques, les traitements de capteurs/actionneurs et les traitements de commande de procédés ne doivent pas avoir de gigue. Pour ces raisons nous avons aussi présenté un état de l'art sur l'ordonnancement des tâches non-préemptives périodiques strictes. Par ailleurs nous avons présenté un état de l'art sur la tolérance aux fautes. Comme nous nous sommes intéressés aux fautes matérielles, nous avons présenté les deux types de redondances : logicielle et matérielle. Les analyses d'ordonnançabilité existantes de tâches non préemptives périodiques strictes dans le cas monoprocesseur ayant de faibles taux de succès d'ordonnancement, nous avons proposé une nouvelle analyse d'ordonnançabilité. Nous avons présenté une stratégie d'ordonnancement qui consiste à ordonnancer une tâche candidate avec un ensemble de tâches déjà ordonnancée. Nous avons utilisé cette stratégie pour ordonnancer des tâches harmoniques et non harmoniques, et nous avons proposé des nouvelles conditions d'ordonnançabilité. Afin d'améliorer le taux de succès d'ordonnancement de tâches non préemptives périodiques strictes, nous avons proposé de garder certaines tâches non préemptives périodiques strictes et d'y ajouter des tâches préemptives périodiques non strictes ne traitant ni les entrées/sorties ni le contrôle/commande. Nous avons ensuite étudié le problème d'ordonnancement multiprocesseur selon une approche partitionnée. Ce problème est résolu en utilisant trois algorithmes. Le premier algorithme effectue une analyse d'ordonnançabilité monoprocesseur et assigne chaque tâche sur éventuellement plusieurs processeurs. Le deuxième algorithme transforme le graphe de tâches dépendantes en un graphe déroulé où chaque tâche est répétée un nombre de fois égal au rapport entre le PPCM des autres périodes et sa période. Le troisième algorithme exploite les résultats des deux algorithmes précédents pour choisir sur quel processeur ordonnancer une tâche et calculer sa date de début d'exécution. Nous avons ensuite proposé d'étendre l'étude d'ordonnançabilité temps réel multiprocesseur précédente pour qu'elle soit tolérante aux fautes de processeurs et de bus de communication. Nous avons proposé un algorithme qui permet de transformer le graphe de tâches dépendantes en y ajoutant des tâches et des dépendances de données répliques et des tâches de sélection permettant de choisir la réplique de tâches allouée à un processeur non fautif. Nous avons étudié séparément les problèmes de tolérance aux fautes pour des processeurs, des bus de communication, et enfin des processeur et des bus de communication. Finalement nous avons étendu les trois algorithmes vus précédemment d'analyse d'ordonnançabilité, de déroulement et d'ordonnancement afin qu'ils soient tolérants aux fautes. Nous avons ensuite présenté les améliorations apportées au logiciel SynDEx tant sur le plan de l'analyse d'ordonnançabilité et l'algorithme d'ordonnancement, que sur le plan de la tolérance aux fautes. Finalement nous avons présenté les travaux expérimentaux concernant l'application de suivi de CyCabs. Nous avons modifié l'architecture des CyCabs en y intégrant des microcontrôleurs dsPICs et nous avons testé la tolérance aux fautes de dsPICs et du bus CAN sur une application de suivi de CyCab. / In this thesis, we studied the fault-tolerant multiprocessor hard real-time scheduling of non-preemptive strict periodic tasks which could be combined with preemptive tasks. We proposed solutions that we implemented into the SynDEx software, then we tested these solutions on an electric vehicle following. First, we present a state of the art on real-time embedded systems and more specificaly on the classical uniprocesseur and multiprocessor scheduling of preemptive periodic tasks. Since we were interested in critical real-time control applications, sensor/actuators computations and processes control must not have jitter. For these reasons, we also presented a state of the art of the scheduling of non-preemptive strict periodic tasks. Also, we presented a state of the art on fault-tolerance. As we were interested in hardware faults, we presented two types of redundancies: software and hardware. Presently, existing schedulability analyses of non-preemptive strict periodic tasks have low schedulability success ratios, thus we proposed a new schedulability analysis. We first presented a scheduling strategy which consists in scheduling a candidate task whereas a task set is already scheduled. We used this strategy to solve the problem of scheduling harmonic and non-harmonic tasks, and we proposed new schedulability conditions. In order to improve the scheduling success ratio of non-preemptive strict periodic tasks, we proposed to keep some non preemptive strict periodic tasks and to add preemptive periodic tasks which are neither dedicated to input/output nor to control. Then, we studied the multiprocessor scheduling problem using the partitioned approach. In order to solve this problem we proposed three algorithms. The first algorithm performs a uniprocessor schedulability analysis and assigns each task according to a schedulability condition to possibly several processors. The second algorithm transforms the dependent task graph into an unrolled graph where each task is repeated a number of times equal to the ratio between the LCM of all tasks periods and its period. The third algorithm exploits the two precedent algorithms to choose, with a cost function, on which processor it will schedule a task previously assigned to several processors, and it computes the first start times of each task. Then, we extended the multiprocessor schedulability analysis to be tolerant to processor and bus media faults. We proposed an algorithm which transforms the dependent task graph by adding redundant tasks, redundant dependencies, and selecting tasks. The latter allow to choose the redundant task allocated to non faulty processors. We studied separately the processor fault-tolerance problem, the bus fault-tolerant problem, and finally both processor and bus fault-tolerant problem. Finally, we extended the schedulability analysis algorithms, the unrolling algorithm and the scheduling algorithm to be fault-tolerant. Then, we presented the improvements provided to the SynDEx software for the schedulability analysis algorithm, the scheduling algorithm and the fault-tolerance algorithm. Finally, we conducted some experiments on the electric vehicle following called CyCab. We modified the hardware architecture of the CyCab to integrate dsPICs microcontrolers, and we tested dsPICs and CAN buses fault-tolerant on the CyCabs following.
|
Page generated in 0.0571 seconds