[pt] O objetivo do presente trabalho foi apresentar e avaliar técnicas estruturadas e ferramentas conceituais de modelagem para o desenvolvimento de sistemas de Tempo-Real, baseadas em extensões sobre Diagramas de Fluxo de Dados – DFDs, sendo estas propostas, primeiramente, por Ward e Mellor nos livros Structured Development for Real-Time Systems. Assim, modelou-se um Piloto Automático para Automóvel, sendo para este desenvolvido os Modelos da Essência, da Implementação (Modelo da Configuração dos Processadores, Modelo da Configuração dos Processos e Modelos da Configuração dos Módulos) e da Automação. / [en] This work goal was to describe and to evaluate structured techniques and conception tools of modelling to develop Real-Time Systems, based on Data Flow Diagrams – DFDs – extensions, that were first described by Ward & Mellor on Structured Development for Real-Time Systems books. Therefore, it was modeled a Control Cruise System, describing its Essential Model, Implementation Model (Process Model, Task Model and Module Model) and Project Model.

Genetic algorithms have a lot of properties that makes it a good choice when one needs to solve very complicated problems. The performance of genetic algorithms is affected by the parameters that are used. Optimization of the parameters for the genetic algorithm is one of the most popular research fields of genetic algorithms. One of the reasons for this is because of the complicated relation between the parameters and factors such as the complexity of the problem. This thesis describes what happens when time constraints are added to this problem. One of the most important parameters is population size and we have found by testing a well known set of optimization benchmark problems that the optimal population size is not the same when time constraints were involved. / Genetiska algoritmer har många egenskaper som gör dem till ett bra val när man ska lösa väldigt komplicerade problem. Prestandan för genetiska algoritmer påverkas av de parametrar som används. Optimering av parametrarna för genetiska algoritmer är ett av de mest populära forskningsområdena för genetiska algoritmer. En av anledningarna till detta är den komplexa relationen mellan parametrarna och faktorer så som komplexiteten av problemet. Detta arbete beskriver vad som händer när tidsfaktorn läggs till detta problem. En av de viktigaste parametrarna är populationsstorlek och vi har sett genom att testa en grupp med väl testade optimiseringsproblem att optimal populationsstorlek inte är samma när tidsfaktorn är inblandat.

Dans cette thèse nous nous intéressons à la problématique de l'ordonnancement temps réel à priorité fixe des systèmes embarqués récupérant leur énergie de l'environnement. Ces derniers collectent l'énergie ambiante de l'environnement et la stockent dans un réservoir d'énergie afin d'alimenter un appareil électronique. Cette technologie est utilisée dans les petits systèmes embarqués qui nécessitent une longue autonomie. Les réseaux de capteurs et les implants médicaux sont des applications typiques de cette technologie. La majorité des systèmes qui opèrent avec cette technologie doivent exécuter des tâches récurrentes dans un temps imparti. Ainsi, ces systèmes sont soumis à des contraintes dites temps réel où le respect des contraintes temporelles est aussi important que l'exactitude des résultats. Cette thèse traite l'ordonnancement préemptif à priorité fixe de ce genre de systèmes sur des plateformes monoprocesseur. La problématique ici est de trouver des algorithmes d'ordonnancement performants ainsi que des conditions d'ordonnançabilité qui vérifient l'ordonnançabilité d'un système donné dans une configuration d'énergie donnée. La première contribution de cette thèse est la proposition de l'algorithme PFPasap. Il s'agit d'une adaptation de l'ordonnancement préemptif classique à priorité fixe aux contraintes énergétiques. Cela consiste à exécuter les tâches dès que l'énergie est suffisante pour exécuter au moins une unité de temps et à seulement recharger dans le cas échéant. Les périodes de rechargement sont aussi longues que nécessaire pour pouvoir exécuter une seule unité de temps. On prouve que PFPasap est optimal mais uniquement dans le cas des systèmes dits non-concrets où la date de la première activation des tâches et le niveau initial du réservoir d'énergie ne sont connus qu'au moment de l'exécution, et quand toutes les tâches consomment plus d'énergie pendant leur exécution que le système n'en collecte. Une condition d'ordonnançabilité nécessaire et suffisante pour ce type de systèmes est également proposée. Malheureusement, si l'on relâche l'hypothèse sur le profil de consommation d'énergie des tâches, en considérant des tâches qui consomment plus que le rechargement et d'autres qui consomment moins, l'algorithme PFPasap n'est plus optimal et l'activation synchrone n'est plus le pire scénario ce qui rend la condition d'ordonnançabilité précédemment citée seulement nécessaire. Pour cela, nous proposons de borner le pire temps de réponse des tâches afin de construire des conditions suffisantes. Concernant l'optimalité, nous explorons différentes idées dans le but de construire un algorithme optimal en considérant tous les types de systèmes de tâches et tous les profils de consommation d'énergie. Nous montrons aussi que la plupart des idées intuitives n'aboutissant pas à des algorithmes optimaux. Dans le but de mieux comprendre notre problématique, nous proposons d'explorer les solutions proposées pour des problématiques similaires, en particulier celles où le retardement des exécutions est parfois nécessaire pour respecter certaines contraintes. L'ordonnancement avec contraintes thermiques est l'une de ces problématiques. Cette dernière consiste à exécuter les tâches de tel sorte qu'une certaine température maximale n'est jamais atteinte. Cela passe par la suspension des exécutions de temps en temps pour rajouter des temps de refroidissement afin d'éviter que la température maximale ne soit atteinte. Comme première étape, nous proposons d'adapter les solutions proposées pour les systèmes à énergie renouvelable aux systèmes à contraintes thermiques. Ainsi, nous adaptons l'algorithme PFPasap afin que la contrainte thermique soit respectée. Nous proposons également une analyse d'ordonnançabilité basée sur des bornes du pire temps de réponse des tâches. Pour terminer, nous présentons YARTISS : l'outil de simulation développé pendant cette thèse pour évaluer les résultats théoriques / In this thesis, we are interested in the real-time fixed-priority scheduling problem of energy-harvesting systems. An energy-harvesting system is a system that can collect the energy from the environment in order to store it in a storage device and then to use it to supply an electronic device. This technology is used in small embedded systems that are required to run autonomously for a very long lifespan. Wireless sensor networks and medical implants are typical applications of this technology. Moreover, most of these devices have to execute many recurrent tasks within a limited time. Thus, these devices are subject to real-time constraints where the correctness of the system depends not only on the correctness of the results but also on the time in which they are delivered. This thesis focuses on the preemptive fixed-task-priority real-time scheduling for such systems in monoprocessor platforms. The problematic here is to find efficient scheduling algorithms and schedulability conditions that check the schedulability of a given task set in a given energy configuration. The first result of this thesis is the proposition of the PFPasap scheduling algorithm. It is an adaptation of the classical fixed-task-priority scheduling to the energy-harvesting context. It consists of executing tasks as soon as possible whenever the energy is sufficient to execute at least one time unit and replenishes otherwise. The replenishment periods are as long as needed to execute one time unit. We prove that PFPasap is optimal but only in the case of non-concrete systems where the first release time of tasks and the initial energy storage unit level are known only at run-time and where all the tasks consume more energy than the replenishment during execution times. A sufficient and necessary schedulability condition for such systems is also proposed. Unfortunately, when we relax the assumption of tasks energy consumption profile, by considering both tasks that consume more energy than the replenishment and the ones that consume less than the replenishment, PFPasap is no longer optimal and the worst-case scenario is no longer the synchronous release of all the tasks, which makes the precedent schedulability test only necessary. To cope with this limitation, we propose to upper bound tasks worst-case response time in order to build sufficient schedulability conditions instead of exact ones. Regarding algorithms optimality, we explore different ideas in order to build an optimal algorithm for the general model of fixed-task-priority tasks by considering all types of task sets and energy consumption profiles. We show through some counter examples the difficulty of finding such an algorithm and we show that most of intuitive scheduling algorithms are not optimal. After that, we discuss the possibility of finding such an algorithm. In order to better understand the scheduling problematic of fixed-priority scheduling for energy-harvesting systems, we also try to explore the solutions of similar scheduling problematics, especially the ones that delay executions in order to guarantee some requirements. The thermal-aware scheduling is one of these problematics. It consists of executing tasks such that a maximum temperature is never exceeded. This may lead to introduce additional idle times to cool down the system in order to prevent reaching the maximum temperature. As a first step, we propose in this thesis to adapt the solutions proposed for energy-harvesting systems to the thermal-aware model. Thus, we adapt the PFPasap algorithm to respect the thermal constraints and we propose a sufficient schedulability analysis based on worst-case response time upper bounds. Finally, we present YARTISS: the simulation tool used to evaluate the theoretical results presented in this dissertation

In a distributed database system, pessimistic concurrency control is often used to ensure consistency which implies that the execution time of a transaction is not predictable. The execution time of a transaction is not dependent on the local transactions only, but on every transaction in the system. In real-time database systems it is important that transactions are predictable. One way to make transactions predictable is to use eventual consistency where transactions commit locally before they are propagated to other nodes in the system. It is then possible to get predictable transactions due to the fact that the execution time of the transaction only depends on concurrent transactions on the local node and not on delays on other nodes and delays from a network. In this report an investigation is made on how a replication protocol using eventual consistency can be designed for, and implemented in, DeeDS, a distributed real-time database prototype. The protocol consists of three parts: a propagation method, a conflict detection algorithm, and a conflict resolution mechanism. The conflict detection algorithm is based on version vectors. The focus is on the propagation mechanism and the conflict detection algorithm of the replication protocol. An implementation design of the replication protocol is made. A discussion on how the version vectors may be applied in terms of granularity (container, page, object or attribute) and how the log filter should be designed and implemented to suit the particular conflict detection algorithm is carried out. A number of test cases with focus on regression testing have been defined. It is concluded that the feasibility of the conflict detection algorithm is dependent on the application type that uses DeeDS.

The emerging need for dynamically scheduled real-time systems requires methods for handling transient overloads. Current methods have in common that they deal with transient overloads as they occur, which gives the real-time system limited time to react to the overload. In this work we enable new approaches to overload management. Our work shows that artificial neural networks (ANNs) can predict future transient overloads. This way the real-time system can prepare for a transient overload before it actually occurs. Even though the artificial neural network is not yet integrated into any system, the results show that ANNs are able to satisfactory distinguish different workload scenarios into those that cause future overloads from those that do not. Two ANN architectures have been evaluated, one standard feed-forward ANN and one recurrent ANN. These ANNs were trained and tested on sporadic workloads with different average arrival rates. At best the ANNs are able to predict up to 85% of the transient overloads in the test workload, while causing around 10% false alarms.

Real-time computing paradigm is being pervasively deployed in many critical and non-critical applicationssuch as aerospace and telecommunication systems. Most of these systems employ a preemptiveFixed Priority Scheduling (FPS) policy to schedule real-time tasks. Fixed priority scheduling is knownfor its implementation simplicity and low run-time overheads. However, FPS may not be able to use100% of the processor time, when compared to dynamic priority scheduling policies such as the EarliestDeadline First (EDF) scheduling scheme. Dynamic priority scheduling scheme, on the other hand, has tore-calculate the priorities on-line and hence may have significantly high run-time overheads. In this thesis, we investigate a novel scheduling scheme, known as the Dual Priority Scheduling scheme,that can potentially guarantee a feasible schedule. The main advantage of using a dual priority scheduleris that, it can achieve the implementation simplicity of a FPS scheme, while potentially assuring 100%processor utilization similar to EDF. Alan Burns proved the optimality of the dual priority scheme for twotasks, leaving its optimality for n tasks as an open problem. We investigate the optimality of dual priorityscheduling for three tasks, using simulations. We propose and evaluate three different approaches: lastchance method, slack method and brute force method, to calculate the dual priorities and the time intervalswhere these priorities are valid. Our evaluations showed that, of the proposed heuristics, the extended slack method which is a variationof the slack method, performed same as the brute force method. An interesting observation was that,the brute force and the extended slack methods could not schedule the same task sets, nor was the tasksets schedulable using any of the proposed methods.

In industrial automation systems, there is usually large volume of data which needs to be delivered to right places at the right time. In addition, large number of nodes in the automation systems are usually distributed which increases the complexity that there needs to be more point-to-point Ethernet-connections in the network. Hence, it is necessary to apply data-centric design and reduce the connection complexity. Data Distributed Service for Real-Time Systems (DDS) is a data-centric middleware specification adopted by Object Management Group (OMG). It uses the Real-Time Publish-Subscribe protocol as its wiring protocol and targets for mission- and business-critical systems. The IEC 61499 Standard defines an open architecture for the next generation of distributed control and automation systems. This thesis presents the structure and key features of DDS and builds a model of real-time distributed system based on the IEC 61499 Standard. Then a performance evaluation of the DDS communication based on this model is carried out. The traditional socket-based communication is also evaluated to act as a reference for the DDS communication. The results of the evaluation mostly show that DDS is considered as a good solution to reduce the complexity of the Ethernet connections in distributed systems and can be applied to some classes of industrial automation systems.

Safety-critical software intensive systems are used in a lot of industries nowadays. Examples ofthese are in automotive and aircraft industry, medicine, and autonomous systems. Fault in suchsystems can lead to severe damage and/or loss of human lives. Therefore fault-tolerance should beconsidered at all stages of the system development, starting from the analysis and design.Different languages and tools have been developed for that purpose across the years. One of these isthe Architecture Analysis and Design Language (AADL) – a modeling language used to describethe architecture of a software system. It consists of textual and graphical descriptions of three typesof components – software, execution platform and composite.In this work we implement a prototype of an AADL simulator in Java that enables us to examine thepossible dynamic executions of an AADL specification. This allows us to verify the correctness ofan AADL specification based on the behavior it shows. The simulator would expect an AADLspecification of a software system as an input and simulate the dynamic execution of that system.Before implementing the simulator, we introduce the problem area - safety-critical systems andAADL. Since AADL is used primarily in the automotive and aircraft industries, we have chosen todescribe a simplified flight control system for a plane. It should give the reader an initialunderstanding of the language without going into unnecessary detail about rarely used features.Part of the simulator is a compiler that reads the AADL specification, validates it and transforms itto a Java model. We take a look at the individual steps needed for that, with focus on parsing theinput. Therefore we review the different kinds of algorithms used for parsing and explore how theywork.We also make a detailed literature review of previous works in the area of AADL modeltransformations. Finally, we describe the analysis, design and implementation of the simulator andexamine a case study to test the prototype.

This thesis is related to the knowledge area of real-time systems and real-time databases. The increasing complexity of the systems, specifically the embedded systems, and the need of store and share the information they use leads to the need of new technologies. For this reason a need of real-time database management system has emerged to satisfy the new requirements. Several commercial database systems claim to be real-time, but this technology is not consolidated enough. The thesis will perform an evaluation of those databases mainly in predictability terms since predictability is necessary for the correct execution of hard real-time systems. In order to complete the evaluation, a real-time database application has been implemented. This application implements two commercial databases, namely Mimer and eXtremeDB, and a monitor application which is responsible for displaying all the relevant database behavior’s information at runtime. A comparative studying of both databases has been carried out in order to determine how predictable these databases are. Parameters such as response time, CPU time consumption, etc has been studied. Finally, it can be concluded that both databases are predictable to a certain level. On one hand Mimer has an estimation of the worst case response time around 12 µs and CPU overload of 36%, and the fluctuation along the transactions is nearly negligible. On the other hand, eXtreme has an estimation of the worst-case response time around 18 µs and CPU overload of 41%, and the fluctuation along the transactions are rather bigger than the Mimer’s. However, it can be concluded that both databases provide real-time transactions and, thus, they are able to be implemented in real-time systems.

To gain confidence in that a dynamic real-time system behaves correctly, we test it. Automated verification & validation can be used to conduct testing of such systems in an effective and economic way. An event monitor can be used as a part of a test oracle to monitor the system that is being tested. The test oracle could use the data (i.e., the streams of events) derived from the tested system, to determine if an executed test case gave a positive or negative result. To do this, the test oracle compares the streams of events received from the event monitor with the event expressions derived from the formal specification, and decides if the executed test case has responded positive or negative. Any deviations between observed behaviour and accepted behaviour should be reported by the test oracle as a negative result. If the executed test case gave a negative result, the monitor part should signal this to the reporter part of the test oracle. This work aims to investigate how the event expressions can be derived from the formal specification, and in particular, how the event specification language Solicitor can be used to represent these event expressions. We also discuss the need for parameterized event types in Solicitor, and any other event specification languages used in event monitoring. We also show that support for parameterized event types is a significant requirement for such languages.