FlexRay is a new automotive network communication protocol for control and interconnection among ECUs (electronic control units) in the cluster. In the FlexRay protocol, a communication cycle consists of static segment and dynamic segment. The static segment is a TDMA scheme designed for transmitting time-triggered messages. Due to its determinism and reliability, it is particularly applicable to X-by-wire applications. Each static slot is allocated to a specified task and the task can transmit message during the exclusive slot. However, if the task has no message to transmit during its assigned slot, the slot cannot be used by other tasks. The overall utilization is low if the bandwidth requirement of each task is not high. To improve the system utilization, we apply the real-time scheduling techniques to devising a deterministic, static cyclic scheduling. The objective is to reduce the demand on the number of static slots needed for scheduling time-triggered tasks. Specifically, we treat the set of static slots that are in the same position in every communication cycle as an individual real-time channel. We model each task as a real-time task, specified by (Ci,Ti). It requires that for every Ti communication cycles, the system must allocate at least Ci time slots to satisfy the real-time constraint of the task. We decompose each such task into a set of subtasks, allocate them to the real-time channels and then apply the rate-monotonic scheduling algorithm to schedule the subtasks within each channel. Finally, we perform computer simulation to evaluate the effectiveness of our proposal. From the simulation results, we conclude that our proposal is able to effectively reduce the demand for the static slots under a wide range of real-time requirements.

With multiprocessors and multicore processors becoming ubiquitous, focus has shifted from research on uniprocessors to that on multiprocessors. Results derived for the uniprocessor case unfortunately do not always directly extend to the multiprocessor case in a straightforward manner. This necessitates a paradigm shift in the approach used to design and analyse the behaviour of such processors. In the case of Real-time systems, that is, systems characterised by explicit timing constraints, analysis and performance guarantees are more important, as failure is unacceptable. Scheduling algorithms used in Real-time systems have to be carefully designed as the performance of the system depends critically on them. Efficient tests for determining if a set of tasks can be feasibly scheduled on such a computing system using a particular scheduling algorithm thus assumes importance. Traditionally, the ‘task utilization’ parameter has been used for devising such tests. Utilization based tests for Earliest Deadline First(EDF) and Rate Monotonic(RM) scheduling algorithms are known and are well understood for uniprocessor systems. In our work, we derive limits on similar bounds for the multiprocessor case. Our work diners from previous literature in that we explore the case when the individual processors constituting the multiprocessor need not be identical. Each processor in such a system is characterised by a capacity, or speed, and the time taken by a task to execute on a processor is inversely proportional to its speed. Such instances may arise during system upgradation, when faster processors may be added to the system, making it a non-identical multiprocessor, or during processor design, when the different cores on the chip may have different processing power to handle dynamic workloads. We derive results for the partitioned paradigm of multiprocessor scheduling, that is, when tasks are partitioned among the processors, and interprocessor migration after a part of execution is completed is not allowed. Results are derived for both fixed priority algorithms(RM)and dynamic priority algorithms (EDF) used on individual processors. A maximum and minimum limit on the bounds for a ‘greedy’ class of algorithms are established, since the actual value of the bound depends on the algorithm that allocates the tasks. We also derive the utilization bound of an algorithm whose bound is close to the upper limit in both cases. We find that an expression for the utilization bound can be obtained when EDF is used as the uniprocessor scheduling algorithm, but when RM is the uniprocessor scheduling algorithm,an O(mn) algorithm is required to find the utilization bound, where m is the number of tasks in the system and n is the number of processors. Knowledge of such bounds allows us to carry out very fast schedulability tests, although we have the limitation that the tests are sufficient but not necessary to ensure schedulability. We also compare the value of the bounds with those achievable in ‘equivalent’ identical multiprocessor systems and find that the performance guarantees provided by the non-identical multiprocessor system are far higher than those offered by the equivalent identical system.

This work makes significant contributions in the field of sufficient schedulability tests for rate-monotonic scheduling (RMS) and their application to partitioned RMS. Goal is the maximization of possible utilization in worst or average case under a given number of processors. This scenario is more realistic than the dual case of minimizing the number of necessary processors for a given task set since the hardware is normally fixed. Sufficient schedulability tests are useful for quick estimates of task set schedulability in automatic system-synthesis tools and in online scheduling where exact schedulability tests are too slow. Especially, the approach of Accelerated Simply Periodic Task Sets (ASPTSs) and the concept of circular period similarity are cornerstones of improvements in the success ratio of such schedulability tests. To the best of the author's knowledge, this is the first application of circular statistics in real-time scheduling. Finally, the thesis discusses the use of sharp total utilization thresholds for partitioned EDF. A constant-time admission control is enabled with a controlled residual risk. / Diese Arbeit liefert entscheidende Beiträge im Bereich der hinreichenden Planbarkeitstests für ratenmonotones Scheduling (RMS) und deren Anwendung auf partitioniertes RMS. Ziel ist die Maximierung der möglichen Last im Worst Case und im Average Case bei einer gegebenen Zahl von Prozessoren. Dieses Szenario ist realistischer als der duale Fall der Minimierung der Anzahl der notwendigen Prozessoren für eine gegebene Taskmenge, da die Hardware normalerweise fixiert ist. Hinreichende Planbarkeitstests sind für schnelle Schätzungen der Planbarkeit von Taskmengen in automatischen Werkzeugen zur Systemsynthese und im Online-Scheduling sinnvoll, wo exakte Einplanungstests zu langsam sind. Insbesondere der Ansatz der beschleunigten einfach-periodischen Taskmengen und das Konzept der zirkulären Periodenähnlichkeit sind Eckpfeiler für Verbesserungen in der Erfolgsrate solcher Einplanungstests. Nach bestem Wissen ist das die erste Anwendung zirkulärer Statistik im Echtzeit-Scheduling. Schließlich diskutiert die Arbeit plötzliche Phasenübergänge der Gesamtlast für partitioniertes EDF. Eine Zugangskontrolle konstanter Zeitkomplexität mit einem kontrollierten Restrisiko wird ermöglicht.

Scheduling is extremely important for modern real-time systems. It enables several programs to run in parallel and succeed with their tasks. Many systems today are real-time systems, which means that good scheduling is highly needed. This thesis aims to evaluate the real-time scheduling algorithm earliest deadline first, newly introduced into the Linux kernel, and compare it to the already existing real-time scheduling algorithms first in, first out and round robin in the context of firm tasks. By creating a test program that can create pthreads and set their scheduling characteristics, the performance of earliest deadline first can be evaluated and compared to the others. / Schemaläggning är extremt viktigt för dagens realtidssystem. Det tillåter att flera program körs parallellt samtidigt som deras processer inte misslyckas med sina uppgifter. Idag är många system realtidssystem, vilket innebär att det finns ett ytterst stort behov för en bra schemaläggningsalgoritm. Målet med det här examensarbetet är att utvärdera schema-läggningsalgoritmen earliest deadline first som nyligen introducerats i operativsystemet Linux. Målet är även att jämföra algoritmen med två andra schemaläggningsalgoritmer (first in, first out och round robin), vilka redan är väletablerade i Linux kärnan. Det här görs med avseende på processer klassificerade som firm. Genom att skapa ett program som kan skapa pthreads med önskvärda egenskaper kan prestandan av earliest deadline first algoritmen utvärderas, samt jämföras med de andra algoritmerna.

This term project deals with the problem of scheduling real-time tasks in overload conditions and techniques for lowering power consumption. Each of these parts features mechanisms and reasons for their using. There are also described specific algorithms, that are implemented, in operating system uC/OS-II, and compared in next phase of master's thesis.

Dans ce travail, nous nous focalisons sur l’ajout de contraintes temporelles dans les Bases de Données de Capteurs Sans Fil (BDCSF). La cohérence temporelle d’une BDCSF doit être assurée en respectant les contraintes temporelles des transactions et la validité temporelle des données, pour que les données prélevées par les capteurs reflètent fidèlement l’état réel de l’environnement. Cependant, les retards de transmission et/ou de réception pendant la collecte des données peuvent conduire au non-respect de la validité temporelle des données. Une solution de type bases de données s'avère la plus adéquate. Il faudrait pour cela faire coïncider les aspects BD traditionnelles avec les capteurs et leur environnement. À cette fin, les capteurs déployés au sein d'un réseau sans fils sont considérés comme une table d'une base de données distribuée, à laquelle sont appliquées des transactions (interrogations, mises à jour, etc.). Les transactions sur une BD de capteurs nécessitent des modifications pour prendre en compte l'aspect continu des données et l'aspect temps réel. Les travaux réalisés dans cette thèse portent principalement sur trois contributions : (i) une étude comparative des propriétés temporelles entre une collecte périodique des données avec une base de données classique et une approche de traitement des requêtes avec une BDCSF, (ii) la proposition d’un modèle de traitement des requêtes temps réel, (iii) la mise en œuvre d’une BDCSF temps réel, basée sur les techniques décrites dans la deuxième contribution. / In this thesis, we are interested in adding real-time constraints in the Wireless Sensor Networks Database (WSNDB). Temporal consistency in WSNDB must be ensured by respecting the transaction deadlines and data temporal validity, so that sensor data reflect the current state of the environment. However, delays of transmission and/or reception in a data collection process can lead to not respect the data temporal validity. A database solution is most appropriate, which should coincide with the traditional database aspects with sensors and their environment. For this purpose, the sensor in WSN is considered as a table in a distributed database, which applied transactions (queries, updates, etc.). Transactions in a WSNDB require modifications to take into account of the continuous datastream and real-time aspects. Our contribution in this thesis focus on three parts: (i) a comparative study of temporal properties between a periodic data collection based on a remote database and query processing approach with WSNDB, (ii) the proposition of a real-time query processing model, (iii) the implementation of a real time WSNDB, based on the techniques described in the second contribution.

This work makes significant contributions in the field of sufficient schedulability tests for rate-monotonic scheduling (RMS) and their application to partitioned RMS. Goal is the maximization of possible utilization in worst or average case under a given number of processors. This scenario is more realistic than the dual case of minimizing the number of necessary processors for a given task set since the hardware is normally fixed. Sufficient schedulability tests are useful for quick estimates of task set schedulability in automatic system-synthesis tools and in online scheduling where exact schedulability tests are too slow. Especially, the approach of Accelerated Simply Periodic Task Sets (ASPTSs) and the concept of circular period similarity are cornerstones of improvements in the success ratio of such schedulability tests. To the best of the author's knowledge, this is the first application of circular statistics in real-time scheduling. Finally, the thesis discusses the use of sharp total utilization thresholds for partitioned EDF. A constant-time admission control is enabled with a controlled residual risk. / Diese Arbeit liefert entscheidende Beiträge im Bereich der hinreichenden Planbarkeitstests für ratenmonotones Scheduling (RMS) und deren Anwendung auf partitioniertes RMS. Ziel ist die Maximierung der möglichen Last im Worst Case und im Average Case bei einer gegebenen Zahl von Prozessoren. Dieses Szenario ist realistischer als der duale Fall der Minimierung der Anzahl der notwendigen Prozessoren für eine gegebene Taskmenge, da die Hardware normalerweise fixiert ist. Hinreichende Planbarkeitstests sind für schnelle Schätzungen der Planbarkeit von Taskmengen in automatischen Werkzeugen zur Systemsynthese und im Online-Scheduling sinnvoll, wo exakte Einplanungstests zu langsam sind. Insbesondere der Ansatz der beschleunigten einfach-periodischen Taskmengen und das Konzept der zirkulären Periodenähnlichkeit sind Eckpfeiler für Verbesserungen in der Erfolgsrate solcher Einplanungstests. Nach bestem Wissen ist das die erste Anwendung zirkulärer Statistik im Echtzeit-Scheduling. Schließlich diskutiert die Arbeit plötzliche Phasenübergänge der Gesamtlast für partitioniertes EDF. Eine Zugangskontrolle konstanter Zeitkomplexität mit einem kontrollierten Restrisiko wird ermöglicht.