This thesis explores the possibility of the functional programming paradigm in the domain of hard embedded real-time systems. The implementation consists of re-implementing an already developed system that is written with the imperative and object oriented paradigms. The functional implementation of the system in question is compared with the original implementation and a study of code complexity, timing properties, CPU utilization and memory usage is performed. The implementation of this thesis consists of re-developing three of the periodic tasks of the original system and the whole development process is facilitated with the TDD development cycle. The programming language used in this thesis is C but with a functional approach to the problem. We conclusions of this thesis is that the functional implementation will give a more stable, reliable and readable system but some code volume, memory usage and CPU utilization overhead is present. The main benefit of using the functional paradigm in this type of system is the ability of using the TDD development cycle. The main con of this type of implementation is that it relies heavily on garbage collection due to the enforcement of data immutability. We find in conclusion that one can only use the functional paradigm if one has an over dimensioned system when it comes to hardware, mainly when it comes to memory size and CPU power. When developing small systems with scarce resources one should choose another paradigm.

In 1994, Alur and Dill introduced timed automata as a simple mathematical model for modelling the behaviour of real-time systems. In this thesis, we extend timed automata with weights. More detailed, we equip both the states and transitions of a timed automaton with weights taken from an appropriate mathematical structure. The weight of a transition determines the weight for taking this transition, and the weight of a state determines the weight for letting time elapse in this state. Since the weight for staying in a state depends on time, this model, called weighted timed automata, has many interesting applications, for instance, in operations research and scheduling. We give characterizations for the behaviours of weighted timed automata in terms of rational expressions and logical formulas. These formalisms are useful for the specification of real-time systems with continuous resource consumption. We further investigate the relation between the behaviours of weighted timed automata and timed automata. Finally, we present important decidability results for weighted timed automata.

Submitted by Dilene Paulo (dilene.fatima@ufcg.edu.br) on 2018-01-25T12:53:52Z No. of bitstreams: 1 ADRIANA CARLA DAMASCENO – TESE PPGCC 2015.pdf: 3272500 bytes, checksum: 779024871de692299535f2de0eeabfb9 (MD5) / Made available in DSpace on 2018-01-25T12:53:52Z (GMT). No. of bitstreams: 1 ADRIANA CARLA DAMASCENO – TESE PPGCC 2015.pdf: 3272500 bytes, checksum: 779024871de692299535f2de0eeabfb9 (MD5) Previous issue date: 2015-03-06 / We can find many examples of Real-time Systems (RTS) in critical applications such as patient monitoring, air traffic control and others. A failure in this kind of system can be catastrophic. For example, it can harm human lives or increase project budgets. Hence, the testing of real-time systems must be accurate. Models are used to perform this task, since they contain information about how the system behaves and when actions may happen. Due to the complexity of the available systems, most RTS are composed of subsystems that interact as part of a bigger system. These subsystems are combined through operators to model their specification behavior. However, works on the testing of compositional models for RTS are practically nonexistent. Among the available approaches to perform testing for non-compositional RTS models, the tioco conformance testing theory focuses on generating test cases based on implementation and specification models. Moreover, a conformance relation defines whether success in testing means conformance between an implementation and a specification. To express specifications and to represent implementations under test, we use Timed Input Output Symbolic Transitions Systems (TIOSTS). These models store symbolic data and clock variables, avoiding the state space and region explosion problems. Regarding the testing of compositional models, some questions may arise: If two subsystem implementations are tioco conformant to their specifications, is it correct to assume that the composition of the implementations is also tioco conformant to the composition of their specifications? In this case, how can operators be defined to work with TIOSTS and tioco? To answer these questions, this thesis proposes the sequential, interruption and parallel operators for the TIOSTS model. For each operator, we study how the tioco conformance relation behaves with respect to subsystems and the composed system. We present results towards properties of compositional operators when the subsystems are composed, as well as implementing them. Besides, we show three examples where each operator can be used and illustrate the applicability of our approach in two exploratory studies. The first models components of a aircraft specification and the second presents application level interruptions in an Android system. / We can nd many examples of Real-time Systems (RTS) in critical applications such as patient monitoring, air tra c control and others. A failure in this kind of system can be catastrophic. For example, it can harm human lives or increase project budgets. Hence, the testing of real-time systems must be accurate. Models are used to perform this task, since they contain information about how the system behaves and when actions may happen. Due to the complexity of the available systems, most RTS are composed of subsystems that interact as part of a bigger system. These subsystems are combined through operators to model their speci cation behavior. However, works on the testing of compositional models for RTS are practically nonexistent. Among the available approaches to perform testing for non-compositional RTS models, the tioco conformance testing theory focuses on generating test cases based on implementation and speci cation models. Moreover, a conformance relation de nes whether success in testing means conformance between an implementation and a speci cation. To express speci cations and to represent implementations under test, we use Timed Input Output Symbolic Transitions Systems (TIOSTS). These models store symbolic data and clock variables, avoiding the state space and region explosion problems. Regarding the testing of compositional models, some questions may arise: If two subsystem implementations are tioco conformant to their speci cations, is it correct to assume that the composition of the implementations is also tioco conformant to the composition of their speci cations? In this case, how can operators be de ned to work with TIOSTS and tioco? To answer these questions, this thesis proposes the sequential, interruption and parallel operators for the TIOSTS model. For each operator, we study how the tioco conformance relation behaves with respect to subsystems and the composed system. We present results towards properties of compositional operators when the subsystems are composed, as well as implementing them. Besides, we show three examples where each operator can be used and illustrate the applicability of our approach in two exploratory studies. The rst models components of a aircraft speci cation and the second presents application level interruptions in an Android system.

Um dos principais desafios no desenvolvimento de ferramentas e metodologias para sistemas multiprocessados, embarcados e de tempo-real é o reuso de software já desenvolvido, mantendo baixa utilização de recursos como memória, energia e desempenho de CPU, e ainda atendendo às restrições temporais. O presente trabalho procura atacar este problema no nível do middleware, comumente utilizado como forma de integrar componentes de software reusáveis, diminuindo o tempo e o esforço desprendido no desenvolvimento de aplicações e serviços com alta qualidade. Este trabalho especifica e implementa um middleware para uma plataforma MPSoC voltada para sistemas embarcados e de tempo-real, permitindo adaptações durante o projeto e/ou execução da aplicação, a fim de otimizar o uso dos recursos e atender às restrições de projeto. Ao projetista da aplicação é permitido reusar os serviços do middleware e da plataforma em diferentes aplicações. Igualmente, aplicações escritas sobre o middleware podem ser portadas para outras plataformas onde o middleware possa ser executado. O middleware proposto oferece serviços implementados em hardware e encapsulamento da comunicação hardware-software na própria aplicação. Além disso, são oferecidos meios para gerenciamento de requisitos não funcionais de energia e tempo-real, como deadline e tempo de execução. / One of the main challenges in the development of tools and methodologies for a multiprocessor real-time embedded system is to reuse already developed software, but at the same time obtaining low memory footprint, low energy consumption, and minimal area, obviously addressing the real-time constraints. This work aims at facing these problems at the middleware level, frequently used to integrate components of reusable software, accelerating development cycle and reducing the effort to develop applications and services with high quality. The present work specifies and implements a middleware for an MPSoC platform oriented to real-time and embedded systems, providing adaptations at development and execution time, in order to optimize resources usage and fulfill design restrictions. The designer can reuse middleware services and the platform as well, when developing different applications. Likewise, applications developed under the middleware can be ported to run in other platforms where the middleware was ported to. The proposed middleware offers hardware implemented services and encapsulates hardware-software communication in the application. Moreover, it permits to specify non-functional requirements of energy and real-time, as deadline and execution time.

Embedded/real-time systems are becoming ubiquitous in today's world and their pervasive nature is increasing with the advent of cyber-physical systems. Providing temporal guarantees is paramount in such systems. Most of the normal operation in real-time systems is modelled using periodic tasks. Event-driven behaviour is modelled using aperiodic jobs. To ensure an acceptable Quality of Service for aperiodic jobs without jeopardizing safety of periodic tasks, aperiodic servers were introduced [2], [3]. Aperiodic servers are used to reserve a quota for the execution of aperiodic jobs. However, they do not take into account, cache-related delays that the execution of aperiodic jobs could impose on periodic tasks, thereby making their use in systems with caches unsafe. In this thesis, we introduce Cache Related Delay Servers to solve this problem. Statically, every periodic task's worst-case execution time includes a pre-determined delay quota for delay caused by aperiodic jobs. During system operation, the aperiodic server is allowed to execute only if periodic jobs that may be affected by it have sufficient delay quota to accommodate its execution. Otherwise, the priority of the aperiodic server is temporarily decreased to the level of the lowest-priority periodic job with insufficient quota, thereby ensuring safe execution of periodic tasks.

Um dos principais desafios no desenvolvimento de ferramentas e metodologias para sistemas multiprocessados, embarcados e de tempo-real é o reuso de software já desenvolvido, mantendo baixa utilização de recursos como memória, energia e desempenho de CPU, e ainda atendendo às restrições temporais. O presente trabalho procura atacar este problema no nível do middleware, comumente utilizado como forma de integrar componentes de software reusáveis, diminuindo o tempo e o esforço desprendido no desenvolvimento de aplicações e serviços com alta qualidade. Este trabalho especifica e implementa um middleware para uma plataforma MPSoC voltada para sistemas embarcados e de tempo-real, permitindo adaptações durante o projeto e/ou execução da aplicação, a fim de otimizar o uso dos recursos e atender às restrições de projeto. Ao projetista da aplicação é permitido reusar os serviços do middleware e da plataforma em diferentes aplicações. Igualmente, aplicações escritas sobre o middleware podem ser portadas para outras plataformas onde o middleware possa ser executado. O middleware proposto oferece serviços implementados em hardware e encapsulamento da comunicação hardware-software na própria aplicação. Além disso, são oferecidos meios para gerenciamento de requisitos não funcionais de energia e tempo-real, como deadline e tempo de execução. / One of the main challenges in the development of tools and methodologies for a multiprocessor real-time embedded system is to reuse already developed software, but at the same time obtaining low memory footprint, low energy consumption, and minimal area, obviously addressing the real-time constraints. This work aims at facing these problems at the middleware level, frequently used to integrate components of reusable software, accelerating development cycle and reducing the effort to develop applications and services with high quality. The present work specifies and implements a middleware for an MPSoC platform oriented to real-time and embedded systems, providing adaptations at development and execution time, in order to optimize resources usage and fulfill design restrictions. The designer can reuse middleware services and the platform as well, when developing different applications. Likewise, applications developed under the middleware can be ported to run in other platforms where the middleware was ported to. The proposed middleware offers hardware implemented services and encapsulates hardware-software communication in the application. Moreover, it permits to specify non-functional requirements of energy and real-time, as deadline and execution time.

abstract: Cyber-physical systems and hard real-time systems have strict timing constraints that specify deadlines until which tasks must finish their execution. Missing a deadline can cause unexpected outcome or endanger human lives in safety-critical applications, such as automotive or aeronautical systems. It is, therefore, of utmost importance to obtain and optimize a safe upper bound of each task’s execution time or the worst-case execution time (WCET), to guarantee the absence of any missed deadline. Unfortunately, conventional microarchitectural components, such as caches and branch predictors, are only optimized for average-case performance and often make WCET analysis complicated and pessimistic. Caches especially have a large impact on the worst-case performance due to expensive off- chip memory accesses involved in cache miss handling. In this regard, software-controlled scratchpad memories (SPMs) have become a promising alternative to caches. An SPM is a raw SRAM, controlled only by executing data movement instructions explicitly at runtime, and such explicit control facilitates static analyses to obtain safe and tight upper bounds of WCETs. SPM management techniques, used in compilers targeting an SPM-based processor, determine how to use a given SPM space by deciding where to insert data movement instructions and what operations to perform at those program locations. This dissertation presents several management techniques for program code and stack data, which aim to optimize the WCETs of a given program. The proposed code management techniques include optimal allocation algorithms and a polynomial-time heuristic for allocating functions to the SPM space, with or without the use of abstraction of SPM regions, and a heuristic for splitting functions into smaller partitions. The proposed stack data management technique, on the other hand, finds an optimal set of program locations to evict and restore stack frames to avoid stack overflows, when the call stack resides in a size-limited SPM. In the evaluation, the WCETs of various benchmarks including real-world automotive applications are statically calculated for SPMs and caches in several different memory configurations. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2017

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

Um dos principais desafios no desenvolvimento de ferramentas e metodologias para sistemas multiprocessados, embarcados e de tempo-real é o reuso de software já desenvolvido, mantendo baixa utilização de recursos como memória, energia e desempenho de CPU, e ainda atendendo às restrições temporais. O presente trabalho procura atacar este problema no nível do middleware, comumente utilizado como forma de integrar componentes de software reusáveis, diminuindo o tempo e o esforço desprendido no desenvolvimento de aplicações e serviços com alta qualidade. Este trabalho especifica e implementa um middleware para uma plataforma MPSoC voltada para sistemas embarcados e de tempo-real, permitindo adaptações durante o projeto e/ou execução da aplicação, a fim de otimizar o uso dos recursos e atender às restrições de projeto. Ao projetista da aplicação é permitido reusar os serviços do middleware e da plataforma em diferentes aplicações. Igualmente, aplicações escritas sobre o middleware podem ser portadas para outras plataformas onde o middleware possa ser executado. O middleware proposto oferece serviços implementados em hardware e encapsulamento da comunicação hardware-software na própria aplicação. Além disso, são oferecidos meios para gerenciamento de requisitos não funcionais de energia e tempo-real, como deadline e tempo de execução. / One of the main challenges in the development of tools and methodologies for a multiprocessor real-time embedded system is to reuse already developed software, but at the same time obtaining low memory footprint, low energy consumption, and minimal area, obviously addressing the real-time constraints. This work aims at facing these problems at the middleware level, frequently used to integrate components of reusable software, accelerating development cycle and reducing the effort to develop applications and services with high quality. The present work specifies and implements a middleware for an MPSoC platform oriented to real-time and embedded systems, providing adaptations at development and execution time, in order to optimize resources usage and fulfill design restrictions. The designer can reuse middleware services and the platform as well, when developing different applications. Likewise, applications developed under the middleware can be ported to run in other platforms where the middleware was ported to. The proposed middleware offers hardware implemented services and encapsulates hardware-software communication in the application. Moreover, it permits to specify non-functional requirements of energy and real-time, as deadline and execution time.

Made available in DSpace on 2014-06-12T15:49:47Z (GMT). No. of bitstreams: 1 license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / A grande expansão do mercado de dispositivos digitais tem forçado empresas desenvolvedoras de sistemas embarcados em lidar com diversos desafios para prover sistemas complexos nesse nicho de mercado. Um dos desafios prominentes está relacionado ao consumo de energia, principalmente, devido aos seguintes fatores: (i) mobilidade; (ii) problemas ambientais; e (iii) o custo da energia. Como consequência, consideráveis esforços de pesquisa têm sido dedicados para a criação de técnicas voltadas para aumentar a economia de energia. Na última década, diversas técnicas foram desenvolvidas para reduzir o consumo de energia em sistemas embarcados. Muitos métodos lidam com gerenciamento dinâmico de energia (DPM), como, por exemplo, dynamic voltage scaling (DVS), cooperativamente com sistemas operacionais especializados, a fim de controlar o consumo de energia durante a execução do sistema. Entretanto, apesar da disponibilidade de muitos métodos de redução de consumo de energia, diversas questões estão em aberto, principalmente, no contexto de sistemas de tempo real crítico. Este trabalho propõe um método de síntese de software, o qual leva em consideração relação entre tarefas, overheads, restrições temporais e de energia. O método é composto por diversas atividades, as quais incluem: (i) medição; (ii) especificação; (iii) modelagem formal; (vi) escalonamento; e (v) geração de código. O método também é centrado no formalismo redes de Petri, o qual define uma base para geração precisa de escalas em tempo de projeto, adotando DVS para reduzir o consumo de energia. A partir de uma escala viável, um código customizado é gerado satisfazendo as restrições especificadas, e, dessa forma, garantindo previsibilidade em tempo de execução. Para lidar com a natureza estática das escalas geradas em tempo de projeto, um escalonador simples em tempo de execução é também proposto para melhorar o consumo de energia durante a execução do sistema. Diversos experimentos foram conduzidos, os quais demonstram a viabilidade da abordagem proposta para satisfazer restrições críticas de tempo e energia. Adicionalmente, um conjunto integrado de ferramentas foram desenvolvidas para automatizar algumas atividades do método de síntese de software proposto