Made available in DSpace on 2014-10-09T12:25:41Z (GMT). No. of bitstreams: 0 / Made available in DSpace on 2014-10-09T14:03:40Z (GMT). No. of bitstreams: 1 06914.pdf: 2955248 bytes, checksum: 106449a86e70d89b0638f2132a9326c4 (MD5) / Tese [Doutoramento] / IPEN/T / Instituto de Pesquisas Energeticas e Nucleares - IPEN/CNEN-SP

A Qualidade de Serviço oferece aos Sistemas de Tempo Real garantias das restrições temporais de aplicações tais como comércio eletrônico, vídeo conferência, telemedicina, entre outras que necessitam de confiabilidade e desempenho para efetivação dos seus serviços. Contribuições nessas áreas têm focado a provisão de qualidade de serviço em termos absolutos, descritos num limite máximo de média de tempo de atendimento, destinado às aplicações Web. Todavia, o controle de qualidade baseado em tempo médio de resposta durante todo o período de serviço prestado, não restringe os tempos de resposta quanto a sua dispersão. Um valor médio razoável pode ser resultado da combinação de tempos de resposta elevados e pequenos. O objetivo deste trabalho é reduzir a dispersão dos atrasos em sistemas escalonados com a política EBS (Exigency Based Scheduling ), definidos pela diferença positiva entre o tempo de resposta da requisição do usuário e o valor médio contratado, em um modelo de contrato determinado por janelas deslizantes de operações. A EBS é uma política de escalonamento que define um modelo de contratos de tempo médio de resposta avaliados durante todo o tempo de serviço. Avalia-se a dispersão dos atrasos, pois, é preferível que haja a possibilidade dos tempos de resposta ficarem substancialmente abaixo da média contratada. Os resultados são obtidos utilizando métodos de simulação dos algoritmos desenvolvidos durante o projeto / Quality of Service offers Real Time Systems guarantees the time constraints of applications such as electronic commerce, video conferencing, telemedicine, among others that need reliable and effective performance for their services. Contributions in these areas have made the provision of service quality in absolute terms, out of a maximum average time of service for Web applications. However, quality control based on average response time for the entire period of service, does not restrict the response time to their dispersion. A reasonable average value may be the result of the combination of response times of high and low. Objective of this research is reduce the delays dispersion in systems scheduled with policy EBS (Exigency Based Scheduling), defined by the positive difference between the response time of user request and the average contract value, in a model contract by a sliding operation windows. The EBS is a scheduling policy that defines a contracts model for an average response time evaluated throughout the time of service. We analyze the delays dispersion because it is preferable that there is the possibility of response time becomes substantially below the average contracted. Results are obtained using simulation methods of the algorithms developed during the project

[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.