Software engineering is a fundamentally collaborative activity, yet most tools that support software engineers are designed only for single users. There are many foreseen benefits in using tools that support real time collaboration between software engineers, such as avoiding conflicting concurrent changes to source files and determining the impact of program changes immediately. Unfortunately, it is difficult to develop non-trivial tools that support real time Collaborative Software Engineering (CSE). Accordingly, the few CSE tools that do exist have restricted capabilities. Given the availability of powerful desktop workstations and recent advances in distributed computing technology, it is now possible to approach the challenges of CSE from a new perspective. The research goal in this thesis is to investigate mechanisms for supporting real time CSE, and to determine the potential gains for developers from the use of CSE tools. An infrastructure, CAISE, is presented which supports the rapid development of real time CSE tools that were previously unobtainable, based on patterns of collaboration evident within software engineering. In this thesis, I discuss important design aspects of CSE tools, including the identification of candidate patterns of collaboration. I describe the CAISE approach to supporting small teams of collaborating software engineers. This is by way of a shared semantic model of software, protocol for tool communication, and Computer Supported Collaborative Work (CSCW) facilities. I then introduce new types of synchronous semantic model-based tools that support various patterns of CSE. Finally, I present empirical and heuristic evaluations of typical development scenarios. Given the CAISE infrastructure, it is envisaged that new aspects of collaborative work within software engineering can be explored, allowing the perceived benefits of CSE to be fully realised.

CPS (Cyber-Physical Systems) enable a new class of applications that perceive their surroundings using raw data from sensors, monitor the timing of dynamic processes, and control the physical environment. Since failures and misbehaviors in application domains such as cars, medical devices, nuclear power plants, etc., may cause significant damage to life and/or property, CPS need to be safe and dependable. A conventional way of improving dependability is to use redundant hardware to replicate the whole (sub)system. Although hardware replication has been widely deployed in conventional mission-critical systems, it is cost-prohibitive to many emerging CPS application domains. Hardware replication also leads to limited system flexibility. This dissertation studies the problem of making CPS affordably dependable and develops a system-level framework that manages critical CPS resources including processors, networks, and sensors. Our framework called SAFER (System-level Architecture for Failure Evasion in Real-time applications) incorporates configurable software mechanisms and policies to tolerate failures of critical CPS resources while meeting their timing constraints. It supports adaptive graceful degradation, the effective use of different sensor modalities, and the fault-tolerant schemes of hot standby, cold standby, and re-execution. SAFER reliably and efficiently allocates tasks and their backups to CPU and sensor resources while satisfying network traffic constraints. It also fuses and (re)configures sensor data used by tasks to recover from system failures. The SAFER framework aims to guarantee the timeliness of different types of tasks that fall into one of four categories: (1) tasks with periodic arrivals, (2) tasks with continually varying periods, (3) tasks with parallel threads, and (4) tasks with self-suspensions. We offer the schedulability analyses and runtime support for such tasks with and without resource failures. Finally, the functionality of the proposed system is evaluated on a self-driving car using SAFER. We conclude that the proposed framework analytically satisfies timing constraints and predictably operates systems with and without resource failures, hence making CPS dependable and timely.

Scheduling of aperiodic and independent tasks in hard real-time symmetric multiprocessing systems is an NP-complete problem that is often solved using heuristics like particle swarm optimization (PSO). The performance of these class of heuristics, known as evolutionary algorithms, are often evaluated based on the number of iterations it takes to find a solution. Such metrics provide limited information on how the algorithm reaches a solution and how the process could be accelerated. This thesis presents a methodology to analyze the trajectory formed by candidate solutions in order to analyze them in both the time and frequency domains at a single scale. The analysis entails (i) the impact of different parameters for the PSO algorithm, and (ii) the evolutionary processes in the swarm. The work reveals that particles have a directed movement towards a solution during a transient phase, and then enter a steady state where they perform an unguided local search. The scheduling algorithm presented in this thesis uses a variation of the minimum total tardiness with cumulative penalties cost function, that can be extended to suit different system needs. The experimental results show that the scheduler is able to distribute tasks to meet the real-time deadlines over 1, 2, and 4 processors and up to 30 tasks with overall system loads of up to 50\% in fewer than 1,000 iterations. When scheduling greater loads, the scheduler reaches local solutions with 1 to 2 missed deadlines, while larger tasks sets take longer to converge. The trajectories of the particles during the scheduling algorithm are examined as a means to emphasize the impact of the behaviour on the application performance and give insight into ways to improve the algorithm for both space and terrestrial applications.

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