Techn. Universiẗat, Diss., 2001--Berlin.

Techn. University, Diss., 2002--Berlin.

Techn. Universiẗat, Diss., 2005--Darmstadt.

Nürnberg, University, Diss., 2006--Erlangen.

This thesis covers the work to combine the two worlds of the hardware platform of the BLACKfin by Analog Devices and the software based on the eCos operating system to provide a foundation for embedded real-time applications to build on to benefit from the best aspects of both. This document will therefore outline the main objectives of this thesis followed by an overview of the functionality provided by eCos and the BLACKfin. It will further outline the steps required to combine both by porting the hardware abstraction layer and device drivers for the BLACKfin architecture to eCos. Prior to detailing selected implementations of particular code segments of special interest this thesis will outline the design and concept considerations involved and the conclusion drawn in order to provide a working HAL. After describing the current state of the hardware abstraction layer port conducted as part of this thesis this document will provide an evaluation of the implementation itself the benefits as well as possible limitations. To provide a conclusion to the work outlined in this document further possible questions of interest for future work based on the results of this thesis will be provided.

Rapid development processes and higher customer requirements lead to increasing integration of software solutions in the automotive industry’s products. Today, several electronic control units communicate by bus systems like CAN and provide computation of complex algorithms. This increasingly requires a controlled timing behavior. The following diploma thesis investigates how the timing analysis tool SymTA/S can be used in the software development process of the ZF Friedrichshafen AG.Within the scope of several scenarios, the benefits of using it, the difficulties in using it and the questions that can not be answered by the timing analysis tool are examined

Multimodal interfaces (MMIs) are a promising human-computer interaction paradigm. They are feasible for a wide rang of environments, yet they are especially suited if interactions are spatially and temporally grounded with an environment in which the user is (physically) situated. Real-time interactive systems (RISs) are technical realizations for situated interaction environments, originating from application areas like virtual reality, mixed reality, human-robot interaction, and computer games. RISs include various dedicated processing-, simulation-, and rendering subsystems which collectively maintain a real-time simulation of a coherent application state. They thus fulfil the complex functional requirements of their application areas. Two contradicting principles determine the architecture of RISs: coupling and cohesion. On the one hand, RIS subsystems commonly use specific data structures for multiple purposes to guarantee performance and rely on close semantic and temporal coupling between each other to maintain consistency. This coupling is exacerbated if the integration of artificial intelligence (AI) methods is necessary, such as for realizing MMIs. On the other hand, software qualities like reusability and modifiability call for a decoupling of subsystems and architectural elements with single well-defined purposes, i.e., high cohesion. Systems predominantly favour performance and consistency over reusability and modifiability to handle this contradiction. They thus accept low maintainability in general and hindered scientific progress in the long-term. This thesis presents six semantics-based techniques that extend the established entity-component system (ECS) pattern and pose a solution to this contradiction without sacrificing maintainability: semantic grounding, a semantic entity-component state, grounded actions, semantic queries, code from semantics, and decoupling by semantics. The extension solves the ECS pattern's runtime type deficit, improves component granularity, facilitates access to entity properties outside a subsystem's component association, incorporates a concept to semantically describe behavior as complement to the state representation, and enables compatibility even between RISs. The presented reference implementation Simulator X validates the feasibility of the six techniques and may be (re)used by other researchers due to its availability under an open-source licence. It includes a repertoire of common multimodal input processing steps that showcase the particular adequacy of the six techniques for such processing. The repertoire adds up to the integrated multimodal processing framework miPro, making Simulator X a RIS platform with explicit MMI support. The six semantics-based techniques as well as the reference implementation are validated by four expert reviews, multiple proof of concept prototypes, and two explorative studies. Informal insights gathered throughout the design and development supplement this assessment in the form of lessons learned meant to aid future development in the area. / Multimodale Schnittstellen sind ein vielversprechendes Paradigma der Mensch-Computer-Interaktion. Sie sind in einer Vielzahl von Umgebungen einsetzbar und eignen sich besonders wenn Interaktionen zeitlich und räumlich mit einer Umgebung verankert sind in welcher der Benutzer (physikalisch) situiert ist. Interaktive Echtzeitsysteme (engl. Real-time Interactive Systems, RIS) sind technische Umsetzungen situierter Interaktionsumgebungen, die vor allem in Anwendungsgebieten wie der virtuellen Realität, der gemischten Realität, der Mensch-Roboter-Interaktion und im Bereich der Computerspiele eingesetzt werden. Interaktive Echtzeitsysteme bestehen aus vielfältigen dedizierten Subsystemen, die zusammen die Echtzeitsimulation eines kohärenten Anwendungszustands aufrecht erhalten und die komplexen funktionalen Anforderungen des Anwendungsgebiets erfüllen. Zwei gegensätzliche Prinzipien bestimmen die Softwarearchitekturen interaktiver Echtzeitsysteme: Kopplung und Kohäsion. Einerseits verwenden Subsysteme typischerweise spezialisierte Datenstrukturen um Performanzanforderungen gerecht zu werden. Um Konsistenz aufrecht zu erhalten sind sie zudem auf enge zeitliche- und semantische Abhängigkeiten untereinander angewiesen. Diese enge Kopplung wird verstärkt, falls Methoden der künstlichen Intelligenz in das RIS integriert werden müssen, wie es für die Umsetzung multimodaler Schnittstellen der Fall ist. Andererseits bedingen Softwarequalitätsmerkmale wie Wiederverwendbarkeit und Modifizierbarkeit die Entkopplung von Subsystemen und Architekturelementen und fordern hohe Kohäsion. Bestehende Systeme lösen diesen Konflikt überwiegend zu Gunsten von Performanz und Konsistenz und zu Lasten von Wiederverwendbarkeit und Modifizierbarkeit. Insgesamt wird auf diese Weise geringe Wartbarkeit akzeptiert und auf lange Sicht der wissenschaftliche Fortschritt eingeschränkt. Diese Arbeit stellt sechs Softwaretechniken auf Basis von Methoden der Wissensrepräsentation vor, welche das etablierte Entity-Component System (ECS) Entwurfsmuster erweitern und eine Lösung des Konflikts darstellen, die die Wartbarkeit nicht missachtet: semantic grounding, semantic entity-component state, grounded actions, semantic queries, code from semantics und decoupling by semantics. Diese Erweiterung löst das Introspektionsdefizit des ECS-Musters, verbessert die Granularität von ECS-Komponenten, erleichtert den Zugriff auf Entity-Eigenschaften außerhalb der Subsystem-Komponentenzuordnung, beinhaltet ein Konzept zur einheitlichen Beschreibung von Verhalten als Komplement zur Zustandsrepräsentation und ermöglicht sogar Kompatibilität zwischen interaktiven Echtzeitsystemen. Die vorgestellte Referenzimplementierung Simulator X weist die technische Machbarkeit der sechs Softwaretechniken nach. Sie kann von anderen Forschern auf Basis einer Open-Source Lizenz (wieder)verwendet werden und beinhaltet ein Repertoire an üblichen Verarbeitungsschritten für multimodalen Eingaben, welche die besondere Eignung der sechs Softwaretechniken für eine solche Eingabeverarbeitung veranschaulichen. Dieses Repertoire bildet zusammen das integrierte multimodale Eingabeverarbeitungs-Framework miPro und macht damit Simulator X zu einem RIS, welches explizit die Umsetzung von multimodalen Schnittstellen unterstützt. Die sechs Softwaretechniken sowie die Referenzimplementierung sind durch vier Expertengutachten, eine Vielzahl an technischen Demonstrationen sowie durch zwei explorative Studien validiert. Informelle Erkenntnisse, die während Design und Entwicklung gesammelt wurden, ergänzen diese Beurteilung in Form von lessons learned, welche bei künftigen Entwicklungsarbeiten in diesem Gebiet helfen sollen.

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.

Rapid development processes and higher customer requirements lead to increasing integration of software solutions in the automotive industry’s products. Today, several electronic control units communicate by bus systems like CAN and provide computation of complex algorithms. This increasingly requires a controlled timing behavior. The following diploma thesis investigates how the timing analysis tool SymTA/S can be used in the software development process of the ZF Friedrichshafen AG.Within the scope of several scenarios, the benefits of using it, the difficulties in using it and the questions that can not be answered by the timing analysis tool are examined. (new: additional files)

Typically, a real-time system consists of a controlling system (i.e., a computer) and a controlled system (i.e., the environment). Real-time systems are those systems where correctness depends on two aspects: i) the logical result of computation and, ii) the time in which results are produced. It is essential to guarantee meeting timing constraints for this kind of systems to operate correctly. Missing deadlines in many cases -- in so-called hard real-time systems -- is associated with economic loss or loss of human lives and must be avoided under all circumstances. On the other hand, there is a trend towards consolidating software functions onto fewer processors in different domains such as automotive systems and avionics with the aim of reducing costs and complexity. Hence, applications with different levels of criticality that used to run in isolation now start sharing processors. As a result, there is a need for techniques that allow designing such mixed-criticality (MC) systems -- i.e., real-time systems combining different levels of criticality -- and, at the same time, complying with certification requirements in the different domains. In this research, we study the problem of scheduling MC tasks under EDF (Earliest Deadline First) and propose new approaches to improve scheduling techniques. In particular, we consider that a mix of low-criticality (LO) and high-criticality (HI) tasks are scheduled on one processor. While LO tasks can be modeled by minimum inter-arrival time, deadline, and worst-case execution time (WCET), HI tasks are characterized by two WCET parameters: an optimistic and a conservative one. Basically, the system operates in two modes: LO and HI mode. In LO mode, HI tasks run for no longer than their optimistic execution budgets and are scheduled together with the LO tasks. The system switches to HI mode when one or more HI tasks run for more than their conservative execution budgets. In this case, LO tasks are immediately discarded so as to be able of accommodating the increase in HI execution demand. We propose an exact test for mixed-criticality EDF, which increases efficiency and reliability when compared with the existing approaches from the literature. On this basis, we further derive approximated tests with less complexity and, hence, a reduced running time that makes them more suitable for online checks.:Contents 1. Introduction 1 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Structure of this Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Concepts, Models and Assumptions 7 2.1. Real-Time Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1. Tasks Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2. Scheduling Policies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1. Feasibility versus Schedulability . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2. Schedulability Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3. Mixed-Criticality Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4. Basic Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5. The Earliest Deadline First Algorithm . . . . . . . . . . . . . . . . . . . . . . 13 2.5.1. EDF-VD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.2. Mixed-Criticality EDF . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.5.3. Demand Bound Function . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. Related Work 17 3.1. Uniprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1. Uniprocessor Scheduling Based on EDF . . . . . . . . . . . . . . . . . 18 3.2. Multiprocessor Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1. Multiprocessor Scheduling Based on EDF . . . . . . . . . . . . . . . . 20 4. Introducing Utilization Caps 23 4.1. Introducing Utilization Caps . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.1. Fixed utilization caps . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.1.2. Optimized utilization caps . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5. Bounding Execution Demand under Mixed-Criticality EDF 29 5.1. Bounding Execution Demand . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 5.2. Analytical Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.1. The GREEDY Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 35 5.2.2. The ECDF Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.3. Finding Valid xi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.4. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 6. Approximating Execution Demand Bounds 41 6.1. Applying Approximation Techniques . . . . . . . . . . . . . . . . . . . . . . . 41 6.2. Devi’s Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2.1. Per-task deadline scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2.2. Uniform deadline scaling . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.2.3. Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3. Findings of this Chapter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7. Evaluation and Results 49 7.1. Mixed-Criticality EDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2. Obtaining Test Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2.1. The Case Di = Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2.2. The Case Di ≤ Ti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.3. Weighted schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.4. Algorithms in this Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . 51 7.4.1. The EDF-VD and DEDF-VD Algorithms . . . . . . . . . . . . . . . . 51 7.4.2. The GREEDY algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.4.3. The ECDF algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 7.5. Evaluation of Utilization Caps . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.5.1. 10 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.5.2. 20 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.5.3. 50 tasks per task set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.5.4. Comparison of runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 59 7.6. Evaluation of Execution Demand Bounds . . . . . . . . . . . . . . . . . . . . 61 7.6.1. Comparison for sets of 10 tasks . . . . . . . . . . . . . . . . . . . . . . 61 7.6.2. Comparison for sets of 20 tasks . . . . . . . . . . . . . . . . . . . . . . 64 7.7. Evaluation of Approximation Techniques . . . . . . . . . . . . . . . . . . . . . 67 7.7.1. Schedulability curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.7.2. Weighted schedulability . . . . . . . . . . . . . . . . . . . . . . . . . . 69 7.7.3. Comparison of runtime . . . . . . . . . . . . . . . . . . . . . . . . . . 72 7.8. Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 8. Conclusion and Future Work 77 8.1. Outlook/Future Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 Bibliography 83 A. Introduction 91 A.1. Multiple Levels of Criticality . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.1.1. Ordered mode switches . . . . . . . . . . . . . . . . . . . . . . . . . . 91 A.1.2. Unordered mode switches . . . . . . . . . . . . . . . . . . . . . . . . . 93 B. Evaluation and Results 95 B.1. Uniform Distribution for Task Periods . . . . . . . . . . . . . . . . . . . . . . 95