Hard real-time systems in robotics, space and military missions, and control devices are specified with stringent and critical time constraints. On the other hand, soft real-time applications arising from multimedia, telecommunications, Internet web services, and games are specified with more lenient constraints. Real-time systems can also be distinguished in terms of their implementation into preemptive and non-preemptive systems. In preemptive systems, tasks are often preempted by higher priority tasks. Non-preemptive systems are gaining interest for implementing soft-real applications on multithreaded platforms. In this dissertation, I propose a new algorithm that uses a two-level scheduling strategy for scheduling non-preemptive soft real-time tasks. Our goal is to improve the success ratios of the well-known earliest deadline first (EDF) approach when the load on the system is very high and to improve the overall performance in both underloaded and overloaded conditions. Our approach, known as group-EDF (gEDF), is based on dynamic grouping of tasks with deadlines that are very close to each other, and using a shortest job first (SJF) technique to schedule tasks within the group. I believe that grouping tasks dynamically with similar deadlines and utilizing secondary criteria, such as minimizing the total execution time can lead to new and more efficient real-time scheduling algorithms. I present results comparing gEDF with other real-time algorithms including, EDF, best-effort, and guarantee scheme, by using randomly generated tasks with varying execution times, release times, deadlines and tolerances to missing deadlines, under varying workloads. Furthermore, I implemented the gEDF algorithm in the Linux kernel and evaluated gEDF for scheduling real applications.

Both real-time virtualization and recursive virtualization are desirable properties of a virtual machine monitor (or hypervisor). Although the prospect for virtualization and even recursive virtualization has become better as the PC hardware becomes faster, the real-time systems community so far has not been able to reap much benefits. This is because no existing virtualization mechanism can properly support the stringent timing requirements needed by real-time systems. It is hard to do real-time virtualization, and it is even harder to do it recursively. In this dissertation, we propose a framework whereby the hypervisor is capable of running real-time guests and participating in recursive virtualization. Such a hypervisor is called a real-time hierarchical hypervisor. We first look at virtualization of abstract resource types from the real-time systems perspective. Unlike the previous work on recursive real-time partitioning that assumes fully-preemptable resources, we concentrate on other and often more practical types of scheduling constraints, especially the non-preemptive and limited-preemptive ones. Then we consider the current x86 architecture and explore the problems that need to be addressed for real-time recursive virtualization. We drill down on the problem that affects timing properties the most, namely, the recursive forwarding and delivery of interrupts, exceptions and intercepts. We choose the x86 architecture because it is popular and readily available, but it is by no means the only architecture of choice for real-time recursive virtualization. We conclude the research with an architecture-independent discussion on future possibilities in real-time recursive virtualization. / text

During the past decades of research in Real-Time systems, non-preemptive scheduling and fully preemptive scheduling have been extensively investigated, as well as compared with each other. However, it has been shown that none of the two scheduling paradigms dominates over the other in terms of schedulability. In this context, Limited Preemptive Scheduling (LPS) has emerged as an attractive alternative with respect to, e.g., increasing the overall system schedu- lability, efficiently reducing the blocking by lower priority tasks (compared to non-preemptive scheduling) as well as efficiently controlling the number of preemptions, thus controlling the overall preemption-related delay (compared to fully-preemptive scheduling). Several approaches within LPS enable the above mentioned advantages. In our work, we consider the Fixed Preemption Point Scheduling (LP-FPP) as it has been proved to effectively reduce the preemption-related delay compared to other LPS approaches. In particular, LP-FPP facilitates more precise estimation of the preemption-related delays, since the preemption points of a task in LP-FPP are explicitly selected during the design phase, unlike the other LPS approaches where the preemption points are determined at runtime. The main goal of the proposed work is to improve the schedulability of real-time systems under the LP-FPP approach. We investigate its use in different domains, such as: single core hard real-time systems, partitioned multi-core systems and real-time systems which can occasionally tolerate deadline misses. We enrich the state of the art for the single core hard real-time systems by proposing a novel cache-related preemption delay analysis, towards reducing the pessimism of the previously proposed methods. In the context of partitioned multi-core scheduling we propose a novel partitioning criterion for the Worst-Fit Decreasing based partitioning, and we also contribute with the comparison of existing partitioning strategies for LP-FPP scheduling. Finally, in the context of real-time systems which can occasionally tolerate deadline misses, we contribute with a probabilistic response time analysis for LP-FPP scheduling and a preemption point selection method for reducing the deadline-misses of the tasks.

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.