<p>Safety-critical applications have to function correctly even in presence of faults. This thesis deals with techniques for tolerating effects of transient and intermittent faults. Reexecution, software replication, and rollback recovery with checkpointing are used to provide the required level of fault tolerance. These techniques are considered in the context of distributed real-time systems with non-preemptive static cyclic scheduling.</p><p>Safety-critical applications have strict time and cost constrains, which means that not only faults have to be tolerated but also the constraints should be satisfied. Hence, efficient system design approaches with consideration of fault tolerance are required.</p><p>The thesis proposes several design optimization strategies and scheduling techniques that take fault tolerance into account. The design optimization tasks addressed include, among others, process mapping, fault tolerance policy assignment, and checkpoint distribution.</p><p>Dedicated scheduling techniques and mapping optimization strategies are also proposed to handle customized transparency requirements associated with processes and messages. By providing fault containment, transparency can, potentially, improve testability and debugability of fault-tolerant applications.</p><p>The efficiency of the proposed scheduling techniques and design optimization strategies is evaluated with extensive experiments conducted on a number of synthetic applications and a real-life example. The experimental results show that considering fault tolerance during system-level design optimization is essential when designing cost-effective fault-tolerant embedded systems.</p>

Embedded systems have become indispensable in our life: household appliances, cars, airplanes, power plant control systems, medical equipment, telecommunication systems, space technology, they all contain digital computing systems with dedicated functionality. Most of them, if not all, are real-time systems, i.e. their responses to stimuli have timeliness constraints. The timeliness requirement has to be met despite some unpredictable, stochastic behaviour of the system. In this thesis, we address two causes of such stochastic behaviour: the application and platform-dependent stochastic task execution times, and the platform-dependent occurrence of transient faults on network links in networks-on-chip. We present three approaches to the analysis of the deadline miss ratio of applications with stochastic task execution times. Each of the three approaches fits best to a different context. The first approach is an exact one and is efficiently applicable to monoprocessor systems. The second approach is an approximate one, which allows for designer-controlled trade-off between analysis accuracy and analysis speed. It is efficiently applicable to multiprocessor systems. The third approach is less accurate but sufficiently fast in order to be placed inside optimisation loops. Based on the last approach, we propose a heuristic for task mapping and priority assignment for deadline miss ratio minimisation. Our contribution is manifold in the area of buffer and time constrained communication along unreliable on-chip links. First, we introduce the concept of communication supports, an intelligent combination between spatially and temporally redundant communication. We provide a method for constructing a sufficiently varied pool of alternative communication supports for each message. Second, we propose a heuristic for exploring the space of communication support candidates such that the task response times are minimised. The resulting time slack can be exploited by means of voltage and/or frequency scaling for communication energy reduction. Third, we introduce an algorithm for the worst-case analysis of the buffer space demand of applications implemented on networks-on-chip. Last, we propose an algorithm for communication mapping and packet timing for buffer space demand minimisation. All our contributions are supported by sets of experimental results obtained from both synthetic and real-world applications of industrial size.

The proper composition of independently developed components of an embedded real- time system is complicated due to the fact that besides the functional behavior also the non-functional properties and in particular the timing have to be compatible. Nowadays related compatibility problems have to be addressed in a cumbersome integration and configuration phase at the end of the development process, that in the worst case may fail. Therefore, a number of formal approaches have been developed, which try to guide the upfront decomposition of the embedded real-time system into components such that integration problems related to timing properties can be excluded and that suitable configurations can be found. However, the proposed solutions require a number of strong assumptions that can be hardly fulfilled or the required analysis does not scale well. In this paper, we present an approach based on timed automata that can provide the required guarantees for the later integration without strong assumptions, which are difficult to match in practice. The approach provides a modular reasoning scheme that permits to establish the required guarantees for the integration employing only local checks, which therefore also scales. It is also possible to determine potential configuration settings by means of timed game synthesis. / Die korrekte Komposition individuell entwickelter Komponenten von eingebetteten Realzeitsystemen ist eine Herausforderung, da neben funktionalen Eigenschaften auch nicht funktionale Eigenschaften berücksichtigt werden müssen. Ein Beispiel hierfür ist die Kompatibilität von Realzeiteigenschaften, welche eine entscheidende Rolle in eingebetteten Systemen spielen. Heutzutage wird die Kompatibilität derartiger Eigenschaften in einer aufwändigen Integrations- und Konfigurationstests am Ende des Entwicklungsprozesses geprüft, wobei diese Tests im schlechtesten Fall fehlschlagen. Aus diesem Grund wurde eine Zahl an formalen Verfahren Entwickelt, welche eine frühzeitige Analyse von Realzeiteigenschaften von Komponenten erlauben, sodass Inkompatibilitäten von Realzeiteigenschaften in späteren Phasen ausgeschlossen werden können. Existierenden Verfahren verlangen jedoch, dass eine Reihe von Bedingungen erfüllt sein muss, welche von realen Systemen nur schwer zu erfüllen sind, oder aber, die verwendeten Analyseverfahren skalieren nicht für größere Systeme. In dieser Arbeit wird ein Ansatz vorgestellt, welcher auf dem formalen Modell des Timed Automaton basiert und der keine Bedingungen verlangt, die von einem realen System nur schwer erfüllt werden können. Der in dieser Arbeit vorgestellte Ansatz enthält ein Framework, welches eine modulare Analyse erlaubt, bei der ausschließlich miteinender kommunizierende Komponenten paarweise überprüft werden müssen. Somit wird eine skalierbare Analyse von Realzeiteigenschaften ermöglicht, die keine Bedingungen verlangt, welche nur bedingt von realen Systemen erfüllt werden können.

Ethernet Switches are widely used in real-time distributed systems as a solution to guarantee the real-time behavior in communication. In this solution there are still some limitations which are the important obstacles obtaining timeliness in the network. These limitations are the limited number of priority levels as well as the possibility of memory overruns with consequent messages. The mentioned limitations can be eliminated using a master/slave technique along with FTT paradigm. The FTT-SE protocol which is a technique based on the master/slave and FTT methods was proposed to overcome the mentioned limitations. However, the FTT-SE protocol has been investigated for a small network architecture with a single switch and master node. Extension of this solution to larger networks is still an open issue. Three different architectures were suggested to scale the FTT-SE to large scale network. In this thesis we propose a solution that extends the FTT-SEprotocol while keeping the real-time behavior of the network. In this solution, we divided the network into a set of sub-networks, each contains one switch, set of slave nodes and one master node that connected to the associated switch in the network. Moreover, the switches are connected together directly without gateways and form a tree topology network. The solution includes both synchronous and asynchronous traffic in the network. We also show that the timeliness of the traffic can still be enforced. Moreover, to validate the solution we have designed and implemented a simulator based on the Matlab/Simulink which is a tool to evaluate different network architecture using Simulink blocks. All transmission can be visualized by the ordinary Scope block in the Simulink. Moreover, the end-to-end delay for all messages is calculated after the simulation running to show the response time of the network. Furthermore, the response time analysis is done for both synchronous and asynchronous messages in this thesis according to the proposed solution. The results from simulation and the analysis are compared together to validate the investigations.

In this thesis, we propose an approach to estimate the Worst Case Response Time (WCRT) of each task in a preemptive multi-tasking single-processor real-time system utilizing an L1 cache. The approach combines inter-task cache eviction analysis and intra-task cache access analysis to estimate the Cache Related Preemption Delay (CRPD). CRPD caused by preempting task(s) is then incorporated into WCRT analysis. We also propose a prioritized cache to reduce CRPD by exploiting cache partitioning technique. Our WCRT analysis approach is then applied to analyze the behavior of a prioritized cache. Four sets of applications with up to six concurrent tasks running are used to test our WCRT analysis approach and the prioritized cache. The experimental results show that our WCRT analysis approach can tighten the WCRT estimate by up to 32% (1.4X) over prior state-of-the-art. By using a prioritized cache, we can reduce the WCRT estimate of tasks by up to 26%, as compared to a conventional set associative cache.

In this thesis, the problem of optimal resource allocation in real-time systems is studied. A recently proposed resource allocation approach called Q-RAM (Quality of Service based Resource Allocation Model) is investigated in detail. The goal of the Q-RAM based approaches is to minimize the execution speed in real-time systems while meeting resource constraints and maximizing total utility. Phased array radar system is an example of a system in which multiple tasks contend for multiple resources in order to satisfy their requirements. In this system, multiple targets are tracked (each a separate task) by the radar system simultaneously requiring processor and energy resources of the radar system. Phased array radar system is considered as an illustrative application area in order to comparatively evaluate the resource allocation approaches. For the problem of optimal resource allocation with single resource type, the Q-RAM algorithm appears incompletely specified, namely it does not have a termination criteria set that can terminate the algorithm in all possible cases. In the present study, first, the Q-RAM solution approach to the radar resource allocation problem with single resource type is extended to give a global optimal solution in all possible termination cases. For the case of multiple resource types, the Q-RAM approach can only generate near-optimal results. In this thesis, for the formulated radar resource allocation problem with multiple resource types, the Methods of Feasible Directions are considered as an alternative solution approach. For the multiple resource type case, the performances of both the Q-RAM approach and the Methods of Feasible Directions are investigated in terms of optimality and convergence speed with the help of Monte-Carlo simulations. It is observed from the results of the simulation experiments that the Gradient Projection Method produce results outperforming the Q-RAM approach in closeness to optimality with comparable execution times.

No description available.

Performance analysis is an objective method of gathering the data of performance, and generally transforms these observations into numerical data. Performance indicators, as well as a selection or elements of sucessful outcome, have often been used in order to feedback augmented information in performance analysis systems, but they have rarely been considered within the classification of performance analysis systems based on timing of analysis and feedback. The main aim of this study is to investigate performance indicators used within real-time and lapsed time systems so that the definitions of the performance indicators, the effectiveness of the performance indicators, their reliability and validity within real time analysis systems can be analyzed.

Testing is the dominant verification technique used in the software industry today. The use of automatic test case execution increases, but the creation of test cases remains manual and thus error prone and expensive. To automate generation and selection of test cases, model-based testing techniques have been suggested. In this thesis two central problems in model-based testing are addressed: the problem of how to formally specify coverage criteria, and the problem of how to generate a test suite from a formal timed system model, such that the test suite satisfies a given coverage criterion. We use model checking techniques to explore the state-space of a model until a set of traces is found that together satisfy the coverage criterion. A key observation is that a coverage criterion can be viewed as consisting of a set of items, which we call coverage items. Each coverage item can be treated as a separate reachability problem. Based on our view of coverage items we define a language, in the form of parameterized observer automata, to formally describe coverage criteria. We show that the language is expressive enough to describe a variety of common coverage criteria described in the literature. Two algorithms for test case generation with observer automata are presented. The first algorithm returns a trace that satisfies all coverage items with a minimum cost. We use this algorithm to generate a test suite with minimal execution time. The second algorithm explores only states that may increase the already found set of coverage items. This algorithm works well together with observer automata. The developed techniques have been implemented in the tool CoVer. The tool has been used in a case study together with Ericsson where a WAP gateway has been tested. The case study shows that the techniques have industrial strength.

Modern general purpose programming languages like Java or C# provide a rich feature set and a higher degree of abstraction than conventional real-time programming languages like C/C++ or Ada. Applications developed with these modern languages are typically deployed via platform independent intermediate code. The intermediate code is typically executed by a virtualizing runtime environment. This allows for a high portability. Prominent examples are the Dalvik Virtual Machine of the Android operating system, the Java Virtual Machine as well as Microsoft .NET’s Common Language Runtime. The virtualizing runtime environment executes the instructions of the intermediate code. This introduces additional challenges to real-time software development. One issue is the transformation of the intermediate code instructions to native code instructions. If this transformation interferes with the execution of the real-time application, this might introduce jitter to its execution times. This can degrade the quality of soft real-time systems like augmented reality applications on mobile devices, but can lead to severe problems in hard real-time applications that have strict timing requirements. This thesis examines the possibility to overcome timing issues with intermediate code execution in virtualizing runtime environments. It addresses real-time suitable generation of native code from intermediate code in particular. In order to preserve the advantages of modern programming languages over conventional ones, the solution has to adhere to the following main requirements: - Intermediate code transformation does not interfere with application execution - Portability is not reduced and code transformation is still transparent to a programmer - Comparable performance Existing approaches are evaluated. A concept for real-time suitable code generation is developed. The concept bases on a pre-allocation of the native code and the elimination of indirect references, while considering and optimizing startup time of an application. This concept is implemented by the extension of an existing virtualizing runtime environment, which does not target real-time systems per se. It is evaluated qualitatively and quantitatively. A comparison of the new concept to existing approaches reveals high execution time determinism and good performance and while preserving the portability deployment of applications via intermediate code.