Emerging embedded devices in the Battery-Free Internet of Things have the benefit that they harvest their required energy during runtime from the environment (e.g., through solar power). However, from the perspective of the systems networking stacks, the main challenge is resilience against power failures: Existing network stacks for such systems (e.g., LwIP) face the problem that stored data, such as for address translation, is likely to be lost or inconsistent after a power outage. Besides the consistency of data, sending a packet without the knowledge about the required and available energy can result in energy inefficiency when the power failure occurs during sending, because of the energy waste of the incomplete packet. In this paper, we introduce Pfip, a network stack for UDP/IP specifically targeting scenarios with intermittent power supply. PFIP's primary design consideration is to modularize the network stack into distinct transactions in order to result in a state-machine-compliant structure with states and according transitions. The stack is able to introduce checkpoints between transactions to persistently store the stack's state. Besides handling data consistency, we employ code-analysis techniques that determine the energy demand of states/transitions. Combining the energy demand of operations along with the available energy on our hardware platform eventually yields runtime guarantees such that started transactions will safely be completed without facing power failures.

Sudden power outages remain one of the biggest threats to losing data, disrupting systems and causing financial damages. Whole system persistence (WSP) has previously been proposed as a solution to mitigate such threats through the use of non-volatile main memory (NVRAM). However, it missed out on external device state persistence and the NVRAM technology used at the time was expensive and limited with regard to their scalability. Today's NVRAM technologies are both more affordable and offer much higher storage capacities, but are typically slower than DRAM.

Traditionally, consumer communication and networking has been dominated by entertainment applications and voice communication. With smart homes and smart cars, consumer communication evolves more and more towards a basic supply and is used not only for convenience, but also in security-related applications like surveillance or in sensors and actors for window locks or doorbells. Resilience of this basic supply consequently suddenly becomes a hot research area, also in consumer networks. Our work in progress touches a topic within this research area that up to now has majorly been treated as an orphan: Network stacks are neither considered part of the smart device itself, nor are they managed by middleware or applications. After system or power failures, devices are rebooted, network stacks are restarted, and the middleware takes care of registration and inclusion of the platforms. We introduce the first steps into a transactional smart device, which in case of power failure is able to not only restart its operations (literally founded in the operating system) but also its communication. We strive to develop transactional network stacks, semantically based on Petri nets, for technologies such as Bluetooth or Wi-Fi, Such transactional semantics allow us to develop systems with power-failure resilience. Since each transaction consumes a certain amount of energy, static worst-case energy consumption analysis helps to fit the model to the platform and vice versa. We target consumer-grade embedded system-on-chip platforms (i.e., ESP32-C3) with additional non-volatile memory for storing system checkpoints.

Operating systems are crucial for the performance of the overall system. Any inefficiency leads to a suboptimal use of the available resources and causes performance loss. The wide range of processors in use today makes it challenging to generate the most efficient code for the current hardware ahead of time. Just-in-time compilation, on the other hand, is able to generate efficient code tailored to the current execution context going beyond the processor, also including operating-system configuration or application demands. Moreover, its configuration can even be adapted at runtime to match the current external and internal requirements. Unfortunately, on-demand compilation of operating-system code has not found widespread use due to inherent difficulties stemming from the fact that any just-in-time approach requires extensive runtime support (e.g., for memory allocation for the generated code) usually provided by the operating system itself. A chicken-and-egg problem is found.

Machine learning has shown tremendous success in a large variety of applications. The evolution of machine-learning applications from cloud-based systems to mobile and embedded devices has shifted the focus from only quality-related aspects towards the resource demand of machine learning. For embedded systems, dedicated accelerator hardware promises the energy-efficient execution of neural network inferences. Their precise resource demand in terms of execution time and power demand, however, is undocumented. Developers, therefore, face the challenge to fine-tune their neural networks such that their resource demand matches the available budgets. This article presents Precious , a comprehensive approach to estimate the resource demand of an embedded neural network accelerator. We generate randomised neural networks, analyse them statically, execute them on an embedded accelerator while measuring their actual power draw and execution time, and train estimators that map the statically analysed neural network properties to the measured resource demand. In addition, this article provides an in-depth analysis of the neural networks’ resource demands and the responsible network properties. We demonstrate that the estimation error of Precious can be below 1.5% for both power draw and execution time. Furthermore, we discuss what estimator accuracy is practically achievable and how much effort is required to achieve sufficient accuracy.

It is an ongoing challenge to efficiently use parallelism with today's multi- and many-core processors. Scalability becomes more crucial than ever with the rapidly growing number of processing elements in many-core systems that operate in data centres and embedded domains. Guaranteeing scalability is often ensured by using fully-strict fork/join concurrency, which is the prevalent approach used by concurrency platforms like Cilk. The runtime systems employed by those platforms typically resort to lock-based synchronisation due to the complex interactions of data structures within the runtime. However, locking limits scalability severely. With the availability of commercial off-the-shelf systems with hundreds of logical cores, this is becoming a problem for an increasing number of systems.This paper presents Nowa, a novel wait-free approach to arbitrate the plentiful concurrent strands managed by a concurrency platform's runtime system. The wait-free approach is enabled by exploiting inherent properties of fully-strict fork/join concurrency, and hence is potentially applicable for every continuation-stealing runtime system of a concurrency platform. We have implemented Nowa and compared it with existing runtime systems, including Cilk Plus, and Threading Building Blocks (TBB), which employ a lock-based approach. Our evaluation results show that the wait-free implementation increases the performance up to 1.64× compared to lock-based ones, on a system with 256 hardware threads. The performance increased by 1.17× on average, while no but one benchmark exhibited performance regression. Compared against OpenMP tasks using Clang's libomp, Nowa outperforms OpenMP by 8.68× on average.

The widespread adoption of cyber-physical systems in the safety-critical (hard real-time) domain is accompanied by a rising degree of code-reuse up to actual software product lines spanning different hardware platforms. Nevertheless, the dominant tools for static worst-case execution-time (WCET) analysis operate on individual, specific system instances at the binary level, further depending on machine-code–level annotations for precise analysis. Thus, this timing verification is neither portable nor reusable.

Many industrial real-time systems rely on the implicit register communication paradigm to minimize overheads and ease distributed development. Here, tasks follow a simple input-processing-output scheme, and data is passed without synchronization by the last-is-best semantics. In these systems, the age of data is the primary real-time objective, which is defined by data-flow chains that span from the system's inputs to outputs. Consequently, a real-time analysis aims to provide guarantees on worst-case data age. In general, there are two main approaches: (1) Task-level scheduling such that inter-task communication is arranged at the beginning and end of a task's execution interval, which guarantees a deterministic yet highly pessimistic data age. (2) Job-level dependencies (JLD) that are added at critical points in the schedule to link specific job instances of tasks of a multi-rate data-flow chain, which provides tighter upper bounds on data ages. However, the drawback is that JLDs induce substantial synchronization overheads, impact the overall schedulability, and are much more challenging to implement. In this paper, we address the trade-off between tight data-age guarantees, synchronization overheads, and schedulability in multi-core settings. Our proposed solution is to combine the potential of job-level optimization with the determinism and low overheads of static, task-level approaches. Therefore, we present a novel execution model to efficiently map data-age constrained tasksets with job-level dependencies on event-triggered systems by automated system analysis and transformation. Experimental results of an extensive real-world case study substantiate that our approach can further tighten data-age bounds, reduce overheads, and ease schedulability.

Operating systems rely on system calls to allow the controlled communication of isolated processes with the kernel and other processes. Every system call includes a processor mode switch from the unprivileged user mode to the privileged kernel mode. Although processor mode switches are the essential isolation mechanism to guarantee the system's integrity, they induce direct and indirect performance costs as they invalidate parts of the processor state. In recent years, high-performance networks and storage hardware has made the user/kernel transition overhead the bottleneck for IO-heavy applications. To make matters worse, security vulnerabilities in modern processors (e.g., Meltdown) have prompted kernel mitigations that further increase the transition overhead. To decouple system calls from user/kernel transitions we propose AnyCall, which uses an in-kernel compiler to execute safety-checked user bytecode in kernel mode. This allows for very fast system calls interleaved with error checking and processing logic using only a single user/kernel transition. We have implemented AnyCall based on the Linux kernel's extended Berkeley Packet Filter (eBPF) subsystem. Our evaluation demonstrates that system call bursts are up to 55 times faster using AnyCall and that real-world applications can be sped up by 24 % even if only a minimal part of their code is run by AnyCall.

The Internet of Things (IoT) requires that all components operate on “fresh” data. However, ensuring a low Age of Information (AoI) is challenging, in particular when communicating across the Internet. Achieving a low AoI requires cooperation of networking strategies as well as node-local strategies so that the entire system performs the right operation at the right moment in time. However, most modern operating systems are not designed to provide accurate timing—various low-level overheads cause delays and jitter that affect communication significantly.This paper presents CLOCKFIX, a run-time system for the Linux user-space that executes jobs accurately and precisely at their intended execution times. The evaluation shows that CLOCKFIX reduces undesired delays by more than 95%, and it improves the AoI in a real-world network protocol by over 16%.

Multi-core real-time systems face the challenge of efficiently maintaining consistency of shared data despite concurrent operations. Existing synchronisation techniques ignore data locality, resulting in cache-related execution time overheads. This paper proposes Migration-Based Synchronisation (MBS), a transparent replacement for locks. In MBS, control flows are migrated to data, instead of moving data to control flows. The consequence is an improvement of data locality that reduces the worst-case execution time of critical sections, and indirectly, worst-case blocking bounds.

The static timing analysis of universal real-time operating systems (RTOS) with generically implemented services requires application and system-context-specific knowledge (e.g., number of currently active tasks) to bound overheads. However, due to the missing notion of OS semantics, contemporary timing analysis tools are unable to exploit such information, resulting in failing or overly pessimistic analysis. To tackle this issue, we present our System-wide WCET Analyses framework (SWAN). SWAN's heart is Platina, a parametric source-level annotation language that facilitates the expression and propagation of context information from the application over the OS down to the machine-code level. Through the expression of semantic interdependencies in a unified and reusable way, analysis pessimism is significantly reduced, as we demonstrate by case studies on FreeRTOS, Linux, and a real-world flight-control system. Just as important as our system-aware timing analysis is the tool support for its practical usability. Therefore, we augmented SWAN by a powerful interactive visualization and annotation environment. This enables developers to quickly identify context-dependent spots that require annotation and thus to cope with large implementations associated with universal RTOSs. Eventually, SWAN allows determining if a generically implemented system is real-time capable and thus timeliness is guaranteed.

Task migration is a potent instrument to exploit multi-core processors. Like full preemption, full migration is particularly advantageous as it allows the scheduler to relocate tasks at arbitrary times between cores. However, in hard real-time systems, migration is accompanied by a tremendous drawback: poor predictability and thus inevitable overapproximations in the worst-case execution-time analysis. This is due to the non-constant size of the tasks' resident set and the costs associated with its transfer between cores. As a result, migration is banned in many real-time systems, regressing the developer to a static allocation of tasks to cores with disadvantageous effects on the overall utilization and schedulability. In previous work, we successfully alleviated the shortcomings of full migration in real-time systems by reducing the associated costs and increasing its predictability. By employing static analysis, we were able to identify beneficial migration points and thus generate static schedules migrating tasks at these identified points. In ongoing work, we extend this approach to dynamic scheduling by providing information about advantageous migration points to an operating system which then makes migration decisions at runtime.

As computer processors and their hardware designs continuously evolve, operating systems provide many different assembly-level implementations for the same functionality. This enables support for new platforms and ensures backward compatibility for older ones at the same time. However, the source code of operating systems grows more complex and becomes much harder to maintain.

Although internal devices (e.g., memory, timers) and external devices (e.g., transceivers, sensors) significantly contribute to the energy consumption of an embedded real-time system, their impact on the worst-case response energy consumption (WCRE) of tasks is usually not adequately taken into account. Most WCRE analysis techniques, for example, only focus on the processor and therefore do not consider the energy consumption of other hardware units. Apart from that, the typical approach for dealing with devices is to assume that all of them are always activated, which leads to high WCRE overestimations in the general case where a system switches off the devices that are currently not needed in order to minimize energy consumption. In this paper, we present SysWCEC, an approach that addresses these problems by enabling static WCRE analysis for entire real-time systems, including internal as well as external devices. For this purpose, SysWCEC introduces a novel abstraction, the power-state-transition graph, which contains information about the worst-case energy consumption of all possible execution paths. To construct the graph, SysWCEC decomposes the analyzed real-time system into blocks during which the set of active devices in the system does not change and is consequently able to precisely handle devices being dynamically activated or deactivated.

Interaction with physical objects often imposes latency requirements to multi-core embedded systems. One consequence is the need for synchronisation algorithms that provide predictable latency, in addition to high throughput. We present a synchronisation algorithm that needs at most 7 atomic memory operations per asynchronous critical section. The performance is competitive, at least, to locks.

Energy-neutral real-time systems harvest the entire energy they use from their environment. In such systems, energy must be treated as an equally important resource as time, which creates the need to solve a number of problems that so far have not been addressed by traditional real-time systems. In particular, this includes the scheduling of tasks with both time and energy constraints, the monitoring of energy budgets, as well as the survival of blackout periods during which not enough energy is available to keep the system fully operational. In this article, we address these issues presenting E n OS, an operating-system kernel for energy-neutral real-time systems. E n OS considers mixed time criticality levels for different energy criticality modes, which enables a decoupling of time and energy constraints when one is considered less critical than the other. When switching the energy criticality mode, the system also changes the set of executed tasks and is therefore able to dynamically adapt its energy consumption depending on external conditions. By keeping track of the energy budget available, E n OS ensures that in case of a blackout the system state is safely stored to persistent memory, allowing operations to resume at a later point when enough energy is harvested again.

Advances in semiconductor technology greatly extend the scope of special-purpose applications as multi-core processors find the way into embedded systems. The increasing number of processor cores makes it more important than ever to have real-time operating systems process parallel threads in the most efficient way. In doing so, they have to pursue multiple (often conflicting) goals: namely being predictable as to time and energy demand. In shared-memory multi-core systems, contention at critical sections makes it inevitable for the operating system to execute competing threads with highly efficient synchronisation methods. Related research has primarily focussed on timing aspects of synchronisation methods, while the energy efficiency of the latter is an unexplored field, yet. In this paper, we implement and evaluate five distinct synchronisation methods and analyse their run-time characteristics (i.e. time, energy) in-depth. We evaluate the overall demand at application level, and empirically prove that contention increases the energy demand significantly even when competing processes are temporarily suspended. Furthermore, the evaluation reveals that choosing the right synchronisation method can decrease the energy demand by more than a factor of 5. We come to the conclusion that it is mandatory to consider the effects of process synchronisation for energy analysis and energy-efficiency optimisations.

Reliable and fine-grained cost-models are fundamental for real-time systems to statically predict worst-case execution time (WCET) estimates of program code in order to guarantee timeliness. Analogous considerations hold for energy-constrained systems where worst-case energy consumption (WCEC) values are mandatory to ensure meeting predefined energy budgets. These cost models are generally unavailable for commercial off-the-shelf (COTS) hardware platforms, although static worst-case analysis tools require those models in order to predict the WCET as well as the WCEC of program code. To solve this problem, we present NEO, an end-to-end toolchain to automate cost-model generation for both WCET and WCEC analyses. NEO exploits automatically generated benchmarks, which are input for 1) an instruction-level emulation and 2) automatically conducted execution-time and energy-consumption measurements on the target platform. The gathered values (i.e., occurrences per instruction, execution-time and energyconsumption per benchmark) are combined as mathematical optimization problems. The solutions to the formulated problems, which are designed to reveal the worst-case behavior, yield the respective cost models. To statically determine upper bounds of benchmarks, we integrated the cost models into the stateof-the-art WCET analyzer PLATIN. Our evaluations on COTS hardware reveal that our open-source, end-to-end toolchain NEO yields accurate worst-case bounds.

Precisely evaluating the accuracy of worst-case execution time (WCET) analysis tools through benchmarking is inherently difficult and in general involves a significant amount of manual intervention. In this paper, we address this problem with ALADDIN, a tooling framework that enables fully-automated evaluations of WCET analyzers. To provide comprehensive results based on benchmarks with known WCETs, ALADDIN incorporates the GENE benchmark generator. Our demonstration shows how ALADDIN evaluates two state-of-the-art WCET analyzers: the commercial tool aiT and the open-source tool PLATIN.

Being able to comprehensively evaluate the individual strengths and weaknesses of worst-case execution time (WCET) analysis tools through benchmarking is essential for improving their accuracy. Unfortunately, a lack of knowledge about the detailed characteristics, actual complexities, and internal structures of existing benchmarks often prevents finegrained assessments, and sometimes even results in misleading conclusions. In this paper we present GENE, a tool that addresses these problems by automatically generating WCET benchmarks with known properties and predefined complexities. Due to the WCETs of benchmarks created by GENE being available, this approach for example makes it possible to precisely determine the accuracy of a WCET analyzer. In addition, the fact that GENE controls the program patterns of a benchmark enables fine-grained evaluations of the particular abilities and deficiencies of different WCET analyzers, as we demonstrate for aiT and PLATIN using multiple hardware platforms.

Soft errors are a challenging and urging problem in the domain of safety-critical embedded systems. For decades, checking schemes have been investigated and improved to mitigate soft-error effects for the class of control-flow faults, with current industrial standards strongly recommending their use. However, reality looks different: Taking a systems perspective, we implemented four representative Control-Flow Checking (CFC) schemes and put them through their paces in 396 fault-injection campaigns. In contrast to previous work, which typically relied on probability-based vulnerability metrics, we accounted for the influence of memory and time overheads on the fault-space dimensions and applied those in full-scan fault injections. This change in procedure alone severely degraded the perceived effectiveness of CFC. In addition, we expanded the perspective to data-flow faults and their influence on the overall susceptibility, an aspect that so far has been largely ignored. Our results suggest that, without accompanying measures, any improvement regarding control-flow faults is dominated by the increase in data faults caused by the increased attack surface in terms of memory and runtime overhead. Moreover, CFC performance less depended on the detection capabilities than on general aspects of the concrete binary compilation and execution. In conclusion, incorporating CFC is not as straightforward as often assumed and the vulnerability of systems with hardened control-flow may in many cases even be increased by the schemes themselves.

Although the manual creation of time-triggered schedules for multi-core real-time systems can be a daunting task, state-of-the-art scheduling algorithms are far from being widely used. This suggests that the availability of sound algorithms is only one side of the story: real-time systems have to be groomed substantially before they can serve as input to available algorithms. Moreover, systems engineers struggle with the temporal effects of their design decisions, in addition to the intended timing properties. Therefore, we believe that appropriate tools are the other side of the story. In this paper, we present the multicore extension of the Real-Time Systems Compiler, a compiler-based tool that analyses given event-triggered real-time systems and transforms them into time-triggered equivalents. We focus on the challenges and pitfalls in the transition from theory to practical implementation and present concrete solutions to resolve them. Existing algorithms need to be adapted for performance and, at model level, bound together appropriately to be applicable, for example. Our experiments substantiate the effectiveness and scalability of our approach, even for large tasks sets. Finally, lessons learned give an insight into implementation and hardware details and their impact on schedulability.

Comprehensive evaluations of the effectiveness of worst-case execution time (WCET) analyzers require a selection of benchmarks that pose a challenge to these tools. In this paper, we identify pitfalls that are associated with selecting such benchmarks based on complexity metrics (e.g., the number of loops contained in a program), which in part are caused by the fact that complexity measures are not necessarily stable in the face of compiler optimizations. To address these problems, we are developing a tool that automatically assesses the resilience of a benchmark against compiler optimizations by tracking complexity measures across different optimization levels. In combination with information on the data dependency of control flows, which is also provided by our tool, this allows users to find and discard benchmarks that appear challenging for WCET analyzers at the source-code level, but in fact are trivial at the machine-code level where the actual analysis is performed.

We explore the advantages of using Erasure Codes (ECs) in a very challenging sensor networking scenario, namely, monitoring and tracking bats in the wild. The mobile bat nodes collect contact information that needs to be transmitted to stationary base stations whenever they are in communication range. We are particularly interested in improving the overall communication reliability of the wireless communication. The mobile nodes are capable of storing a few 100kB of data and to exchange contact information in aggregated form. Due to the continuous flight of the bats and the forest environment, the wireless channel quality varies quickly and, thus, the communication is in general assumed to be highly unreliable. Given the very strict energy constraints of the mobile node and the inherently asymmetric channels, conventional techniques such as full data replication or Automatic Repeat Request to improve the communication reliability are prohibitive. In this work, we investigate the tradeoff between reliability achieved and the cost in form of additional transmissions, that is, the additional energy costs. Our energy measurements on a real platform combined with larger-scale simulation of the wireless communication clearly indicate the advantages of using ECs in our scenario. The results are also applicable in other configurations when unreliable communication channels meet tight energy budgets.

The fact that energy is a scarce resource in many embedded real-time systems creates the need for energy-aware task schedulers, which not only guarantee timing constraints but also consider energy consumption. Unfortunately, existing approaches to analyze the worst-case execution time (WCET) of a task usually cannot be directly applied to determine its worst-case energy consumption (WCEC) due to execution time and energy consumption not being closely correlated on many state-of-the-art processors. Instead, a WCEC analyzer must take into account the particular energy characteristics of a target platform. In this paper, we present 0g, a comprehensive approach to WCEC analysis that combines different techniques to speed up the analysis and to improve results. If detailed knowledge about the energy costs of instructions on the target platform is available, our tool is able to compute upper bounds for the WCEC by statically analyzing the program code. Otherwise, a novel approach allows 0g to determine the WCEC by measurement after having identified a set of suitable program inputs based on an auxiliary energy model, which specifies the energy consumption of instructions in relation to each other. Our experiments for three target platforms show that 0g provides precise WCEC estimates.

This paper is about a novel approach of organising non-sequential programs to the benefit of wait-free synchronisation. Other than critical sections, processes never block at entrance to a guarded section although only one process at a time is allowed to pass through. Competing processes are forced into bypass but, if necessary and by using futures, they can synchronise on concurrent state changes. In consequence, the execution model constrains the overlapping pattern of interacting (simultaneous) processes. Thereby, in the downstream transactional stage, efficient wait-free synchronisation of the "guarding operations" is gratifying by-product. First experimental results made with a 80-way multi-core system show that non-blocking wait-free synchronised guarded sections outperform MCS-locks.

Multi-core operating systems inherently face the problem of concurrent access to internal kernel state held in shared memory. Previous work on the Sloth real-time kernel proposed to offload the scheduling decisions to the interrupt hardware, thus removing the need for a software scheduler, no state has to be managed in software. While our existing design covers single-core platforms only, we now present Multi Sloth, a multi-core AUTOSAR OS implementation. In this paper, we show that our hardware-centric approach enables us to easily make the transition to multi-core platforms without the need for explicitly synchronizing kernel data. Even in the case of cross-core interactions, Multi Sloth keeps the unique Sloth properties of strict priority obedience and complete prevention of rate-monotonic priority inversions. AUTOSAR OS mandates only unordered spin locks, which do not guarantee predictable timing. We show the advantages of the Multi Sloth design by additionally providing a wait-free and efficient implementation of the priority-aware Multiprocessor Priority Ceiling Protocol (MPCP). On our reference platform, we achieve overheads as low as 1.1 μs for acquiring a globally shared resource using the MPCP and round-trip times of 1.4 μs for cross-core task activations.

The goal of the SLOTH family of operating system kernels is to provide a unified priority space to the real-time applications. By automated mapping of tasks to interrupts, we eliminate rate-monotonic priority inversion and increase execution determinism. In its standard implementation, however, SLOTH has been criticized for being unsafe, since interrupt service routines are executed in supervisor mode. SAFER SLOTH mitigates this shortcoming-while keeping the favorable properties of SLOTH-and provides a safe and isolated execution environment for application tasks. Adopting the SLOTH philosophy of embracing and exploiting hardware particularities, its generative approach automatically tailors the system to both the application and the target architecture. We achieve efficient MPU-based memory protection at reduced latency and low performance overhead by leveraging code inlining and compiler optimizations. In comparison to a commercial AUTOSAR OS, SAFER SLOTH achieves speedups between 8x (worst case) and 23x (best case) on kernel latencies while retaining the SLOTH advantages of strict priority obedience, excellent determinism and small memory footprints.

The reduction of structure sizes in microcontollers, environmental conditions or low supply voltages increase the susceptibility of embedded systems to soft errors. As a result, the employment of fault-detection and fault-tolerance measures is becoming a mandatory task even for moderately critical applications. Accordingly, software-based techniques have recently gained in popularity, and a multitude of approaches that differ in the number and frequency of tolerated errors as well as their associated overhead have been proposed. Using type-safe programming languages to isolate critical software components is very popular among those techniques. An automated application of fault-detection and fault-tolerance measures based on the type system of the programming language and static code analyses is possible. It facilitates an easy evaluation of the protection characteristics and costs, as well as the migration of software to new hardware platforms with different failure rates. Transient faults, however, are not bound to the application code secured by the type system, but can also affect the correctness of the type system itself. Thereby, the type system might lose its ability to isolate critical components. As a consequence, it is essential to also protect the type system itself against soft errors. In this paper, we show how soft errors can affect the integrity of the type system. Furthermore, we provide means to secure it against these faults, thus preserving its isolating character. These measures can be applied selectively to achieve a suitable tradeoff between level of protection and resource consumption.

One of the main reasons why Byzantine fault-tolerant (BFT) systems are not widely used lies in their high resource consumption: 3f+1 replicas are necessary to tolerate only f faults. Recent works have been able to reduce the minimum number of replicas to 2f+1 by relying on a trusted subsystem that prevents a replica from making conflicting statements to other replicas without being detected. Nevertheless, having been designed with the focus on fault handling, these systems still employ a majority of replicas during normal-case operation for seemingly redundant work. Furthermore, the trusted subsystems available trade off performance for security; that is, they either achieve high throughput or they come with a small trusted computing base.

Traditional time-triggered operating systems are implemented by multiplexing a single hardware timer - the system timer - in software, having the kernel maintain dispatcher tables at run time. Our Sloth on Time approach proposes to make use of multiple timer cells as available on modern micro controller platforms to encapsulate dispatcher tables in the timer configuration, yielding low scheduling and dispatching latencies at run time. Sloth on Time instruments available timer cells in different roles to implement time-triggered task activation, deadline monitoring, and time synchronization, amongst others. By comparing the Sloth on Time kernel implementation to two commercial kernels, we show that our concept significantly reduces the overhead of time-triggered operating systems. The speed-ups in task dispatching that it achieves range up to a factor of 171x, and its dispatch latencies go as low as 14 clock cycles. Additionally, we demonstrate that Sloth on Time minimizes jitter and increases schedulability for its real-time applications, and that it avoids situations of priority inversion where traditional kernels fail by design.

With more than 11,000 optional and alternative features, the Linux kernel is a highly configurable piece of software. Linux is generally perceived as a textbook example for preprocessor-based product derivation, but more than 65 percent of all features are actually handled by the build system. Hence, variability-aware static analysis tools have to take the build system into account.

SUMMARY Java still is a rather exotic language in the field of real‐time and particularly embedded systems, eventhough it could provide productivity and especially safety and dependability benefits over the dominating language C. The reasons for the lack of acceptance of Java in the embedded world are the high resource consumption caused by the Java runtime environment and the lacking language features for low‐level programming. KESO is a Java Virtual Machine (JVM) that was specifically designed for statically configured resource‐constrained embedded systems. Rather than providing a fixed subset of the Java standard functionality, KESO uses the available ahead‐of‐time knowledge to generate a Java runtime that is specifically tailored towards the particular application. A key feature of KESO is its Multi‐JVM architecture, which allows the isolated cohabitation of different applications on one hardware platform. Our evaluation uses two non‐trivial real‐time applications, a control application for a quadrotor helicopter and a collision detector, to compare the cost of an application using KESO to its C counterpart. Our results show that the resource consumption of applications developed on the base of KESO is comparable to C applications, and its mechanisms for communicating among isolated components are efficient and encourage the actual utilization of spatial isolation. Copyright © 2011 John Wiley & Sons, Ltd.

Much system software can be configured at compile time to tailor it with respect to a broad range of supported hardware architectures and application domains. A good example is the Linux kernel, which provides more than 10,000 configurable features, growing rapidly.

Type-safe high-level languages such as Java have not yet found their way into the domain of deeply embedded systems, even though numerous attempts have been made to make these languages cost attractive. One major challenge that remains is the huge existing code base in many industries. Completely reengineering this code base is not viable for cost and time reasons. We present an approach that allows to isolatedly combine legacy software components and safe software components in an embedded system using the two most common communication idioms found in this domain. Our approach allows the developer to freely choose between hardware- and software-based isolation mechanisms. We demonstrate the feasibility of our approach by porting a non-trivial part of a real-world, hard real-time embedded avionics application. Our results show that the cost of this mixed-mode operation is on the same scale as the pure operation.

We introduce our major ideas of a wait-free, linearizable, and disjoint access parallel NCAS library, called rtNCAS. It focuses the construction of wait-free data structure operations (DSO) in real-time circumstances. rtNCAS is able to conditionally swap multiple independent words (NCAS) in an atomic manner. It allows us, furthermore, to implement arbitrary DSO by means of their sequential specification.

Event latency is considered to be one of the most important properties when selecting an event-driven real-time operating system. This is why in previous work on the Sloth kernel, we suggested treating threads as ISRs -- executing all application code in an interrupt context -- and thereby reducing event latencies by scheduling and dispatching solely in hardware. However, to achieve these benefits, Sloth does not support blocking threads or ISRs, but requires all control flows to have run-to-completion semantics. In this paper, we present Sleepy Sloth, an extension of Sloth that provides a new generalized thread abstraction that overcomes this limitation, while still letting the hardware do all scheduling and dispatching. Sleepy Sloth abolishes the (artificial) distinction between threads and ISRs: Threads can be dispatched as efficiently as interrupt handlers and interrupt handlers can be scheduled as flexibly as threads. Our Sleepy Sloth implementation of the automotive OSEK OS standard provides much more flexibility to application developers while maintaining efficient execution of application control flows. Sleepy Sloth runs on commodity off-the-shelf hardware and outperforms a leading commercial OSEK implementation by a factor of 1.3 to 19.

SUMMARY In this paper, we present a prototype of the Real‐Time Systems Compiler (RTSC). The RTSC is a compiler‐based tool that enables the migration from event‐triggered to time‐triggered real‐time systems. This is achieved by replacing thereal‐time systems architectureof a given real‐time system. The real‐time systems architecture governs the structural properties of thewhite‐box viewof a real‐time system: how are tasks attached to events and how are dependencies between different tasks implemented. The RTSC uses an abstraction calledAtomic Basic Blocks(ABBs) to hide the real‐time systems architecture and capture all relevant dependencies of an event‐triggered system in a global ABB‐graph. The RTSC automatically extracts that ABB‐graph from an event‐triggered real‐time system given as source code, transforms that ABB‐graph appropriately, and maps it to a statically computed schedule that could be executed by standard time‐triggered real‐time operating systems. Important temporal properties of the physical environment of the real‐time system needed for that transformation are stored in asystem modelprovided as additional input to the RTSC. Furthermore, we demonstrate the applicability of our approach and the operation of our prototype by transforming an event‐triggered control application into a time‐triggered equivalent. Copyright © 2011 John Wiley & Sons, Ltd.

Approaching the configuration of non-functional properties (NFPs) in traditional software systems is not an easy task, addressing the configuration of these properties in software product lines (SPLs) imposes even further challenges. Therefore, we have devised the Feedback Approach, which extends the traditional SPL development techniques in order to improve the configuration of NFPs. In this work we present the general guidelines of our approach and also we show the feasibility of the idea by presenting a case study using the Linux Kernel.

The C Preprocessor (CPP) is the tool of choice for the implementation of variability in many large-scale configurable software projects. Linux, probably the most-configurable piece of software ever, employs more than 10,000 preprocessor variables for this purpose. However, this de-facto variability tends to be "hidden in the code"; which on the long term leads to variability defects, such as dead code or inconsistencies with respect to the intended (modeled) variability of the software. This calls for tool support for the efficient extraction of (and reasoning over) CPP-based variability.

In this paper we present a prototype of the RTSC ­ the Real-Time System Compiler. The RTSC is a compiler-based tool that leverages the migration from event-triggered to time-triggered real-time systems. For this purpose, it uses an abstraction called Atomic Basic Blocks (ABBs) which is used to capture all relevant dependencies of the event-triggered system in a so-called ABB-graph. This ABB-graph is transformed by the RTSC and finally mapped to a statically computed schedule that could be executed by standard time-triggered real-time operating systems. Moreover, we demonstrate the applicability of our approach and the operation of our prototype by transforming the event-triggered implementation of a real-world embedded system into a trime-triggered equivalent.

Managing and developing a set of software products jointly using a software product line approach has achieved significant productivity and quality gain in the last decade. More and more, product lines now are becoming themselves entities that are sold and bought in the software supply chain. Customers build more specialized product lines on top of them or derive themselves the concrete products. As customers have different requirements, whole product lines now may vary depending on customer needs—they need to be customized. Current approaches going beyond the scope of one product line do not provide appropriate means for customization. They either are tailored to specific implementation techniques, only regard customization on few levels (e.g., only source code level), or imply a lot of manual effort for performing the customization.

A common problem in event-triggered real-time systems is caused by low-priority tasks that are implemented as interrupt handlers interrupting and disturbing high-priority tasks that are implemented as threads. This problem is termed rate-monotonic priority inversion, and current software-based solutions are restricted in terms of more sophisticated scheduler features as demanded for instance by the AUTOSAR embedded-operating-system specification.

Traditional operating systems differentiate between threads, which are managed by the kernel scheduler, and interrupt handlers, which are scheduled by the hardware. This approach is not only asymmetrical in its nature, but also introduces problems relevant to real-time systems because low-priority interrupt handlers can interrupt high-priority threads. We propose to internally design all threads as interrupts, thereby simplifying the managed control-flow abstractions and letting the hardware interrupt subsystem do most of the scheduling work. The resulting design of our very light-weight Sloth system is suitable for the implementation of a wide class of embedded real-time systems, which we describe with the example of the OSEK-OS specification. We show that the design conciseness has a positive impact on the system performance, its memory footprint, and its overall maintainability.

In theory, the expressive power of an aspect language should be independent of the aspect deployment approach, whether it is static or dynamic weaving. However, in the area of strictly statically typed and compiled languages, such as C or C++, there seems to be a feedback from the weaver implementation to the language level: dynamic aspect languages offer noticeable fewer features than their static counterparts. Especially means for generic aspect implementations are missing, as they are very difficult to implement in dynamic weavers. This hinders reusability of aspects and the application of AOP to scenarios where both, runtime and compile-time adaptation is required. Our solution to overcome these limitations is based on a novel combination of static and dynamic weaving techniques, which facilitates the support of typical static language features, such as generic advice, in dynamic weavers for compiled languages. In our implementation, the same AspectC++ aspect code can now be woven statically or dynamically into the Squid web proxy, providing flexibility and best of bread for many AOP-based adaptation scenarios.

Web servers are exposed to extremely changing runtime requirements. Going offline to adjust policies and configuration parameters in order to cope with such requirements is not an available choice for long running Web servers. Many of the policies that need to be adapted are crosscutting in nature. Aspect-oriented programming (AOP) provides mechanisms to encapsulate the crosscutting policies as aspects. This paper describes the integration of a statically configurable Web server with our dynamic aspect weaving infrastructure. This integration transformed the server to a dynamically adaptable one that could adjust its policies and configuration parameters at runtime according to the changing requirements. This paper further provides a comprehensive analysis of the memory and runtime costs associated with this transformation, and explains how our dynamic aspect weaving infrastructure via its tailored support facilitates to minimise these costs.

We describe the implementation of memory protection by means of aspect-oriented programming (AOP) in CiAO, an AUTOSAR-like family of embedded operating systems. The use of AOP was originally motivated by the fact that memory protection is a cross-cutting policy, which, furthermore, has to be configurable at build-time in AUTOSAR. We learned, however, that besides switching between full protection and no protection, an AOP-based approach also makes it easy to apply completely different models of protection. For the domain of statically configured embedded systems, where certain failure scenarios can often be excluded by means of code analysis or even probability, this facilitates tailored and light-weight "pay-as-you-use" protection strategies.

Modern cars contain a multitude of micro controllers for a wide area of tasks. The diversity of the heterogeneous hardware and software leads to a complicated and expensive integration process.Integrating multiple tasks on fewer micro controllers reduces diversity and costs of production, but poses new problems with the growing complexity of software on a single micro controller. Therefore a more robust software development process and a safe execution environment is needed in the automotive area and other areas with similar constraints. With the KESO system we have implemented a very small and adapted Java execution environment for an OSEK/VDX operating system to address these issues.In this paper we present our approach for a low overhead OSEK/VDX system interface, which is an integral component of the KESO system. We show how access to the system services can be restricted at low cost to ensure the isolation of tasks by the use of type-safety and modern compiler techniques, while maintaining a familiar programming interface for developers that are used to OSEK application development using the C programming language.

Nearly ten years after its first presentation and five years after its first application to operating systems, the suitability of Aspect-Oriented Programming (AOP) for the development of operating system kernels is still highly in dispute. While the AOP advocacy emphasizes the benefits of AOP towards better configurability and maintainability of system software, most kernel developers express a sound skepticism regarding the thereby induced runtime and memory costs: Operating system kernels have to be lean and efficient.We have analyzed the runtime and memory costs of aspects in general, on the level of μ-benchmarks, and by refactoring and extending the eCos operating system kernel using AspectC++, an AOP extension to the C++ language. Our results show that most AOP features do not induce a intrinsic overhead and that the actual overhead induced by AspectC++ is very low. We have also analyzed a test case with significant aspect-related costs. This example shows how the structure of the underlying kernel can have a negative impact on aspect implementations and how these costs can be avoided by an aspect-aware design.Based on this analysis, our conclusion is that AOP is suitable for the development of operating system kernels and other kinds of highly efficient infrastructure software.

Determinism is mandatory for replicating distributed objects with strict consistency guarantees. Multithreaded execution of method invocations is a source of nondeterminism, but helps to improve performance and avoids deadlocks that nested invocations can cause in a single-threaded execution model. This paper contributes a novel algorithm for deterministic thread scheduling based on the interception of synchronisation statements. It assumes that shared data are protected by mutexes and client requests are sent to all replicas in total order; requests are executed concurrently as long as they do not issue potentially conflicting synchronisation operations. No additional communication is required for granting locks in a consistent order in all replicas. In addition to reentrant mutex locks, the algorithm supports condition variables and time-bounded wait operations. An experimental evaluation shows that, in some typical usage patterns of distributed objects, the algorithm is superior to other existing approaches

Most of the communication systems used to support high performance computing in clusters of workstations have been designed focusing on "the best" solution for a certain network architecture. However, a definitive best solution, independently of how well tuned to the underlying hardware it is, cannot exist, for parallel applications communicate in quite different ways. In this paper we describe a novel design method that supports the construction of run time systems as an assemblage of components that can be configured to closely match the demands of any given application. We also describe how this method has been deployed in the development of a communication system in the realm of EPOS, a project that aims at delivering automatically, generated application-oriented run-rime support systems. The communication system in question has been implemented for a cluster of PCs interconnected with Myrinet, and corroborates the effectiveness of the proposed design method.

A crucial aspect in the design of (embedded real-time) operating systems concerns interrupt handling. This paper presents the concept of a modularized interrupt-handling subsystem that enables the synchronization of interrupt-driven, non-sequential code without the need to disabling hardware interrupts. The basic idea is to use nonblocking/optimistic concurrency sequences for synchronization inside an operating-system kernel. Originally designed for the PURE embedded operating system, the presented object-oriented implementation is highly portable not only regarding the CPU but also operating systems and yet efficient.

Deeply embedded systems are forced to operate under extreme resource constraints in terms of memory, CPU, time and power consumption. Automotive systems are a typical example: today's limousines can be considered as (large-scale) distributed systems on wheels. There are cars in daily operation consisting of over 60 networked processors (i.e. microcontrollers). Conservative estimations suggest that, in the near future, every car will be equipped with about 20 networked microcontrollers, on average. The complexity of these "decentralized computer architectures" can no longer be managed by the application alone. Dedicated embedded operating systems are required to ensure the manageability, adaptability, portability and efficiency of the software. Resource-sparing operations under (hard) real-time constraints must be the maxim. This paper discusses the design and implementation of PURE (Portable Universal Runtime Executive) for these classes of deeply embedded systems.

Parallel computation environments exploiting conventional processors offer the potential to achieve high efficiency at a low cost.In the future, even heterogeneous clusters of symmetric multiprocessors (SMPs) will supersede special purpose computers.Due to this trend, the availability of special hardware support for global communication will be more unusual For such an environment, software-implemented multicasts and broadcasts are highly demanded to support a global dissemination of information over networks of processors.This article introduces the theory and presents an algorithm for the implementation of an one-source/manydestination distribution of a message (multicast communication) based on a send-and-forget semantic, i.e. the event of sending a message performs asynchronously with respect to the blocking receive event.The performance of a multicast communication is sensitive to the underlying communication system.In order to achieve optimal results, the algorithm must consider the latencies at the sending and receiving sites.It is shown that computing systems with a low probability for contentions in the communication network offer optimal performance results when they consider generalized Fibonacci sequences.Experiments on a parallel computing system and comparisons with related work demonstrate the relevance of the proposed work. introductionThe efficiency of communication is important to the overall system performance.Especially, this is true in large-scale computing systems consisting of distributed memory computing resources.Many message-passing communication libraries (e.g.PVM or MPI) are available and allow for a portable programming of parallel applications.Message-passing communication services can be grouped into two classes: point-to-point and collective operations.Point-to-point communications involves two communication partners in the form of various modes of send and receive operations, e.g.blocking or non-blocking semantics.A col-Penniwion to make digitniihnrd copies ofall or pnri ofthis mnterial for personrl or chwsroom use is granted without fee provided thnt the copies 'we not made or distributed for protit or commercial rdvantrtge, the copyright notice, the title ofthe puhlic~tion nnd it.<&te nppenr, nnd notice ix given tbnt

The next generation of supercomputers will be largely parallel MIMD architectures, ranging in peak performance from 10 to 100 GFLOPS in the mid nineties to 1000 GFLOPS in the late nineties. Largely parallel means that such a system will consist of hundreds or thousands of processing nodes (PN), and each PN will have a peak performance of several hundred MFLOPS. Obtaining such an extremely high performance is not only an issue of appropriate node architecture but requires also a very high bandwidth interconnection network and an extremely fast implementation of the inter process communication (IPC) protocol. The paper deals with an IPC protocol implementation that reduces the communication startup time to approximately 20 microseconds, by combining highly efficient software solutions, given in the form of lightweight processes, with dedicated hardware, given in the form of a specific communication processor in each PN, to perform the rendezvous required between sender and receiver processes.