AN ABSTRACT OF THE THESIS OF KAUSHIK POLURI, for the Master of Science degree in Electrical and Computer Engineering, presented on 07/03/2013, at Southern Illinois University Carbondale. TITLE: Bounding the Worst-Case Response Times of Hard-Real-Time Tasks under the Priority Ceiling Protocol in Cache-Based Architectures MAJOR PROFESSOR: Dr. HARINI RAMAPRASAD Schedulability analysis of hard-real-time systems requires a-priori knowledge of the worst-case execution times (WCET) of all tasks. Static timing analysis is a safe technique used for calculating WCET that attempts to model program complexity, architectural complexity and complexity introduced by interference from other tasks. Modern architectural features such as caches make static timing analysis of a single task challenging due to unpredictability introduced by their reliance on the history of memory accesses and the analysis of a set of tasks even more challenging due to cache-related interference among tasks. Researchers have proposed several static timing analysis techniques that explicitly consider cache-eviction delays for independent hard-real-time tasks executing on cache-based architectures. However, there is little research in this area for resource-sharing tasks. Recently, an analysis technique was proposed for systems using the Priority Inheritance Protocol (PIP) to manage resource-arbitration among tasks. The Priority Ceiling Protocol (PCP) is a resource-arbitration protocol that offers distinct advantages over the PIP, including deadlock avoidance. However, to the best of our knowledge, there is currently no technique to bound the WCET of resource-sharing tasks under PCP with explicit consideration of cache-eviction delays. This thesis presents a technique to bound the WCETs and hence, the Worst-Case Response Times (WCRTs) of resource-sharing hard-real-time tasks executing on cache-based uniprocessor systems, specifically focusing on data cache analysis.

This thesis discusses the development of an advanced real-time embedded systems course offered at California Polytechnic State University, San Luis Obispo, which aims to prepare students to design modern complex real-time embedded systems. It describes the goals of the real-time embedded systems curriculum, which includes an introductory and advanced course. Finally, this paper discusses the challenges of creating a successful advanced real-time embedded systems course and proposes changes to the current advanced real-time embedded systems course in response to those challenges.

This thesis describes novel machine learning techniques specifically designed for use in real-time embedded systems. The techniques directly address three major requirements of such learning systems. Firstly, learning must be capable of being achieved incrementally, since many applications do not have a representative training set available at the outset. Secondly, to guarantee real-time performance, the techniques must be able to operate within a deterministic and limited time bound. Thirdly, the memory requirement must be limited and known a priori to ensure the limited memory available to hold data in embedded systems will not be exceeded. The work described here has three principal contributions. The frequency table is a data structure specifically designed to reduce the memory requirements of incremental learning in embedded systems. The frequency table facilitates a compact representation of received data that is sufficient for decision tree generation. The frequency table decision tree (FTDT) learning method provides classification performance similar to existing decision tree approaches, but extends these to incremental learning while substantially reducing memory usage for practical problems. The incremental decision path (IDP) method is able to efficiently induce, from the frequency table of observations, the path through a decision tree that is necessary for the classification of a single instance. The classification performance of IDP is equivalent to that of existing decision tree algorithms, but since IDP allows the maximum number of partial decision tree nodes to be determined prior to the generation of the path, both the memory requirement and the execution time are deterministic. In this work, the viability of the techniques is demonstrated through application to realtime mobile robot navigation.

Cyber-physical systems (CPS) integrate sensing, computing, communication and actuation capabilities to monitor and control operations in the physical environment. A key requirement of such systems is the need to provide predictable real-time performance: the timing correctness of the system should be analyzable at design time with a quantitative metric and guaranteed at runtime with high assurance. This requirement of predictability is particularly important for safety-critical domains such as automobiles, aerospace, defense, manufacturing and medical devices. The work in this dissertation focuses on the challenges arising from the use of modern multi-core platforms in CPS. Even as of today, multi-core platforms are rarely used in safety-critical applications primarily due to the temporal interference caused by contention on various resources shared among processor cores, such as caches, memory buses, and I/O devices. Such interference is hard to predict and can significantly increase task execution time, e.g., up to 12 commodity quad-core platforms. To address the problem of ensuring timing predictability on multi-core platforms, we develop novel analytical and systems techniques in this dissertation. Our proposed techniques theoretically bound temporal interference that tasks may suffer from when accessing shared resources. Our techniques also involve software primitives and algorithms for real-time operating systems and hypervisors, which significantly reduce the degree of the temporal interference. Specifically, we tackle the issues of cache and memory contention, locking and synchronization, interrupt handling, and access control for computational accelerators such as general-purpose graphics processing units (GPGPUs), all of which are crucial to achieving predictable real-time performance on a modern multi-core platform. Our solutions are readily applicable to commodity multi-core platforms, and can be used not only for developing new systems but also migrating existing applications from single-core to multi-core platforms.

Debugging is an important phase in the embedded software development cycle because of its high proportion in the overall cost in the product development. Debugging is difficult for real-time applications as such programs are time-sensitive and must meet deadlines in often a resource constrained environment. A common approach for real-time systems is to monitor the execution instead of stepping through the program, because stepping will usually violate all deadline constraints. We consider a time-triggered approach for program monitoring at runtime, resulting in bounded and predictable overhead. In time-triggered execution monitoring, a monitor runs as a separate process in parallel with an application program and samples the program's state periodically to evaluate a set of properties. Applying this technique in computing systems, results in bounded and predictable overhead. However, the time-triggered approach can have high overhead depending on the granularity of the monitoring effort. To reduce this overhead, we instrument the program with markers that will require to sample less frequently and thus reduce the overhead. This leads to interesting problems of (a) where to place the markers in the code and (b) how to manipulate the markers. While related work investigates the first part, in this work, we investigate the second part. We investigate different instrumentation schemes and propose two new schemes based on bitvectors that significantly reduce the overhead for time-triggered execution monitoring. Time-triggered execution monitoring suffers from several drawbacks such as; the time-triggered monitor requires certain synchronization features at the operating system level and may suffer from various concurrency and synchronization dependencies in a real-time setting. Furthermore, the time-triggered execution monitoring scheme requires the embedded environment to provide multi-tasking features. To address the aforementioned problems, we propose a new method called time-triggered self-monitoring, where the program under inspection is instrumented, so that it self-samples its state in a periodic fashion without requiring assistance from an external monitor or an internal timer. The experimental results show that a time-triggered self-monitored program performs significantly better in terms of execution time, binary code size, and context switches when compared to the same program monitored by an external time-triggered monitor.

Increasing usage of multi-core processors has led to their use in real time embedded systems (RTES). This entails high performance requirements which may not be easily met when software development follows traditional techniques long used for single processor systems. In this study, parallel programming design patterns especially developed and reported in the literature will be used to improve RTES implementations on multi-core systems. Specific performance parameters will be selected for assessment, and performance of traditionally developed software will be compared with that of software developed using parallel programming patterns.

The model- and component-based development approach has emerged as an attractive option for the development of Distributed Real-time Embedded (DRE) systems. In this thesis we target several issues such as modeling of legacy communication, extraction of end-to-end timing models and support for holistic response-time analysis of industrial component-based DRE systems. We introduce a new approach for modeling legacy network communication in component-based DRE systems. By introducing special-purpose components to encapsulate and abstract the communication protocols in DRE systems, we allow the use of legacy nodes and legacy protocols in a component- and model-based software engineering environment. The proposed approach also supports the state-of-the-practice development of component-based DRE systems. The Controller Area Network (CAN) is one of the widely used real-time networks in DRE systems especially in automotive domain. We identify that the existing analysis of CAN does not support common message transmission patterns which are implemented by some high-level protocols used in the industry. Consequently, we extend the existing analysis to facilitate the worst-case response-time computation of these transmission patterns. The extended analysis is generally applicable to any high-level protocol for CAN that uses periodic, sporadic, or both periodic and sporadic transmission of messages. Because an end-to-end timing model should be available to perform the holistic response-time analysis, we present a method to extract the end-to-end timing models from component-based DRE systems. In order to show the applicability of our modeling techniques and extended analysis, we provide a proof of concept by extending the existing industrial component model (Rubus Component Model), implementing the holistic response-time analysis along with the extended analysis of CAN in the industrial tool suite (Rubus-ICE), and conducting an automotive case study. / EEMDEF

Debugging is an important phase in the embedded software development cycle because of its high proportion in the overall cost in the product development. Debugging is difficult for real-time applications as such programs are time-sensitive and must meet deadlines in often a resource constrained environment. A common approach for real-time systems is to monitor the execution instead of stepping through the program, because stepping will usually violate all deadline constraints. We consider a time-triggered approach for program monitoring at runtime, resulting in bounded and predictable overhead. In time-triggered execution monitoring, a monitor runs as a separate process in parallel with an application program and samples the program's state periodically to evaluate a set of properties. Applying this technique in computing systems, results in bounded and predictable overhead. However, the time-triggered approach can have high overhead depending on the granularity of the monitoring effort. To reduce this overhead, we instrument the program with markers that will require to sample less frequently and thus reduce the overhead. This leads to interesting problems of (a) where to place the markers in the code and (b) how to manipulate the markers. While related work investigates the first part, in this work, we investigate the second part. We investigate different instrumentation schemes and propose two new schemes based on bitvectors that significantly reduce the overhead for time-triggered execution monitoring. Time-triggered execution monitoring suffers from several drawbacks such as; the time-triggered monitor requires certain synchronization features at the operating system level and may suffer from various concurrency and synchronization dependencies in a real-time setting. Furthermore, the time-triggered execution monitoring scheme requires the embedded environment to provide multi-tasking features. To address the aforementioned problems, we propose a new method called time-triggered self-monitoring, where the program under inspection is instrumented, so that it self-samples its state in a periodic fashion without requiring assistance from an external monitor or an internal timer. The experimental results show that a time-triggered self-monitored program performs significantly better in terms of execution time, binary code size, and context switches when compared to the same program monitored by an external time-triggered monitor.

Traditionally, real-time applications have been executed within an isolatedembedded system, but this is becoming outdated. These systems are growing andbecoming larger, more distributed and complex, and are often closely integratedwith the external structure. The ability to dynamically adapt and regulate thesesort of systems during runtime is an increasingly desired feature. It can increaseits lifespan and save costs in the form of both money and time. This thesisproposes a method to perform this dynamic adaptation and regulation with theconcept of computational reflection. The method is conformed to support theconstrained and varied environment faced when working with distributedembedded real-time systems. A prototype framework of the method has beenrealized in the programming language C++. This framework is lightweight anduses a minimum amount of dependencies. By including this framework into anexisting program and registering variables into the framework, the variables gainreflective properties. These properties are dynamic regulation and limited selfawareness.Lastly, the framework has been evaluated regarding its computationalload and memory consumption. This, in order to show how much extra strainthis sort of method would inflict on an existing system. The results show that,relative the functionality it provides, the strain is low in most of the cases.However, in a hard real-time environment this might not be a viable solution. / Traditionellt har realtidsapplikationer körts inom ett isolerat inbyggt system,men detta har blivit ett föråldrat synsätt. Dessa system växer och blir allt större,mer distribuerade och komplexa, och är ofta nära integrerad med den yttrestrukturen. Förmågan att dynamiskt anpassa sig och reglera denna typ av systemunder drift är en allt mer önskad egenskap. Det kan öka dess livslängd och sparakostnader i form av både pengar och tid. Denna examensrapport föreslår enmetod för att utföra denna dynamiska anpassning och reglering med hjälp avkonceptet kring computational reflection. Metoden är anpassad för att stödja denansträngda och varierad miljö man möter när man arbetar med distribueradeinbyggda realtidssystem. Ett prototyp ramverk för metoden har skapats iprogrammeringsspråket C++. Detta ramverk är lättviktigt och använder ettminimalt antal beroenden. Genom att inkludera detta ramverk i ett befintligtprogram och registrera variabler till ramverket så får variablerna reflektivaegenskaper. Dessa egenskaper är bland annat dynamisk reglering och enbegränsad självkännedom. Slutligen har ramverket utvärderats genom att testadess beräkningslast och minnesförbrukning. Detta, för att visa hur mycket extrapåfrestning denna typ av metod skulle orsaka i ett befintligt system. Resultatenvisar att, relativt dess funktionalitet, så är belastning låg i de flesta av fallen.Men i en hård-realtidsmiljö så är detta antagligen inte en hållbar lösning.

Embedded systems are used in a wide spectrum of applications ranging from home appliances and mobile devices to medical equipment and vehicle controllers. They are typically characterized by their real-time behavior and many of them must fulfill strict requirements on reliability and correctness. In this thesis, we concentrate on aspects related to modeling and formal verification of realtime embedded systems. First, we define a formal model of computation for real-time embedded systems based on Petri nets. Our model can capture important features of such systems and allows their representations at different levels of granularity. Our modeling formalism has a welldefined semantics so that it supports a precise representation of the system, the use of formal methods to verify its correctness, and the automation of different tasks along the design process. Second, we propose an approach to the problem of formal verification of real-time embedded systems represented in our modeling formalism. We make use of model checking to prove whether certain properties, expressed as temporal logic formulas, hold with respect to the system model. We introduce a systematic procedure to translate our model into timed automata so that it is possible to use available model checking ools. Various examples, including a realistic industrial case, demonstrate the feasibility of our approach on practical applications.