Due to the need for advanced computer-controlled functionality in distributed embedded systems the requirements on network communication are becoming overly intricate. This dissertation targets the requirements that are concerned with real-time guarantees, run-time adaptation, resource utilization and flexibility during the development. The Flexible Time-Triggered Switched Ethernet (FTT-SE) and Hard Real-Time Ethernet Switching (HaRTES) network architectures have emerged as two promising solutions that can cater for these requirements. However, these architectures do not support multi-hop communication as they are originally developed for single-switch networks. This dissertation presents a fundamental contribution in multi-hop real-time communication over the FTT-SE and HaRTES architectures targeting the above mentioned requirements. It proposes and evaluates various solutions for scheduling and forwarding the traffic through multiple switches in these architectures. These solutions preserve the ability of dynamic adaptation without jeopardizing real-time properties of the architectures. Moreover, the dissertation presents schedulability analyses for the timeliness verification and evaluation of the proposed solutions as well as several protocols to support run-time adaptation in the multi-hop communication. Finally, the work led to an end-to-end resource reservation framework, based on the proposed multi-hop architectures, to support flexibility during the development of the systems. The efficiency of the proposed solutions is evaluated on various case studies that are inspired from industrial systems.

Methods for performing response time analysis of real-timesystems are important, not only for their use in traditionalschedulability testing, but also for deriving bounds on outputtiming variations in control applications. Automatic controlsystems are inherently sensitive to variations in periodicityand end-to-end delays. Therefore, real-time performance needsto be considered during control design. For this purpose, anyreal-time analysis of a potential control implementation shouldproduce results that can easily be used to examine how theimplementation affects control performance. To find the maximumresponse time variation for a task, bounds on both minimum andmaximum response times are needed. A tight bound on thismaximum variation is useful in the analysis of controlperformance and can also be used to improve the results of someiterative response time analysis methods. In this thesis, threemethods for response time analysis are developed. While earlier research has focused on bounding maximumresponse times, one of the analysis methods in this thesisallows a computation of the minimum response times ofindependent fixed priority scheduled tasks. The analysis findsthe largest lower bound of response times for such tasks, whichleads to a tighter bound on the response time variations. Asecond analysis method allows exact computation of maximumresponse times for tasks whose arrival times are related byoffsets. The method is a complement to schedule simulationbased analysis, which it outperforms for systems with tasksthat may experience release jitter. A common design principle for distributed real-time systemsis to let the completion of one task trigger the start of oneor more successors. A third method supporting the analysis oftasks in such systems is described. The method extends andimproves earlier methods as it allows a generalized systemmodel and also results in tighter bounds than the originalmethods. This method has been implemented as part of a toolsetthat enables an integrated approach to the design and analysisof control systems and their implementation as distributedreal-time systems. As part of the thesis, models for describingdistributed control systems have been developed. The toolset,which is based on these models, uses the derived response timebounds in a control system performance analysis based onsimulation. The use of the toolset is exemplified in a smallcase study. <b>Keywords:</b>real-time systems, scheduling, response time,fixed priority, control, jitter, offset, schedulabilityanalysis

<p>Methods for performing response time analysis of real-timesystems are important, not only for their use in traditionalschedulability testing, but also for deriving bounds on outputtiming variations in control applications. Automatic controlsystems are inherently sensitive to variations in periodicityand end-to-end delays. Therefore, real-time performance needsto be considered during control design. For this purpose, anyreal-time analysis of a potential control implementation shouldproduce results that can easily be used to examine how theimplementation affects control performance. To find the maximumresponse time variation for a task, bounds on both minimum andmaximum response times are needed. A tight bound on thismaximum variation is useful in the analysis of controlperformance and can also be used to improve the results of someiterative response time analysis methods. In this thesis, threemethods for response time analysis are developed.</p><p>While earlier research has focused on bounding maximumresponse times, one of the analysis methods in this thesisallows a computation of the minimum response times ofindependent fixed priority scheduled tasks. The analysis findsthe largest lower bound of response times for such tasks, whichleads to a tighter bound on the response time variations. Asecond analysis method allows exact computation of maximumresponse times for tasks whose arrival times are related byoffsets. The method is a complement to schedule simulationbased analysis, which it outperforms for systems with tasksthat may experience release jitter.</p><p>A common design principle for distributed real-time systemsis to let the completion of one task trigger the start of oneor more successors. A third method supporting the analysis oftasks in such systems is described. The method extends andimproves earlier methods as it allows a generalized systemmodel and also results in tighter bounds than the originalmethods. This method has been implemented as part of a toolsetthat enables an integrated approach to the design and analysisof control systems and their implementation as distributedreal-time systems. As part of the thesis, models for describingdistributed control systems have been developed. The toolset,which is based on these models, uses the derived response timebounds in a control system performance analysis based onsimulation. The use of the toolset is exemplified in a smallcase study.</p><p><b>Keywords:</b>real-time systems, scheduling, response time,fixed priority, control, jitter, offset, schedulabilityanalysis</p>

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

The requirements for real-time systems in safety-critical applications typically contain strict timing constraints. The design of such a system must be subject to extensive validation to guarantee that critical timing constraints will never be violated while the system operates. A mathematically rigorous technique to do so is to perform a schedulability analysis for formally verifying models of the computational workload. Different workload models allow to describe task activations at different levels of expressiveness, ranging from traditional periodic models to sophisticated graph-based ones. An inherent conflict arises between the expressiveness and analysis efficiency of task models. The more expressive a task model is, the more accurately it can describe a system design, reducing over-approximations and thus minimizing wasteful over-provisioning of system resources. However, more expressiveness implies higher computational complexity of corresponding analysis methods. Consequently, an ideal model provides the highest possible expressiveness for which efficient exact analysis methods exist. This thesis investigates the trade-off between expressiveness and analysis efficiency. A new digraph-based task model is introduced, which generalizes all previously proposed models that can be analyzed in pseudo-polynomial time without using any analysis-specific over-approximations. We develop methods allowing to efficiently analyze variants of the model despite their strictly increased expressiveness. A key contribution is the notion of path abstraction which enables efficient graph traversal algorithms. We demonstrate tractability borderlines for different classes of schedulers, namely static priority and earliest-deadline first schedulers, by establishing hardness results. These hardness proofs provide insights about the inherent complexity of developing efficient analysis methods and indicate fundamental difficulties of the considered schedulability problems. Finally, we develop a novel abstraction refinement scheme to cope with combinatorial explosion and apply it to schedulability and response-time analysis problems. All methods presented in this thesis are extensively evaluated, demonstrating practical applicability.

A real-time system is a system such that the correctness of operations depends not only on the logical results, but also on the time at which these results are available. A fundamental problem in designing real-time systems is to analyze response time of operations, which is defined as the time elapsed from the moment when the operation is requested to the moment when the operation is completed. Response time analysis is challenging due to the complex dynamics among operations. A common technique is to study response time under worst-case scenario. However, using worst-case response time may lead to the conservative real-time system designs. To improve the real-time system design, we analyze the non-worst-case response time of operations and apply these results in the design process. The main contribution of this thesis includes mathematical modeling of real-time systems, calculation of non-worst-case response time, and improved real-time system design. We perform analysis and design on three common types of real-time systems as the real-time computing system, real-time communication network, and real-time energy management. For the real-time computing systems, our non-worst-response time analysis leads a necessary and sufficient online schedulability test and a measure of robustness of real-time systems. For the real-time communication network, our non-worst-response time analysis improves the performance for the model predictive control design based on the real-time communication network. For the real-time energy management, we use the non-worst-case response time to check whether the micro-grid can operate independently from the main grid.

Nowadays, Industrial Control Systems (ICSs) are becoming larger and implement more complex functions. Therefore, technologies that are currently used to implement these functions, like hardware platforms and communication protocols might soon become unusable due to the lack of resources. The industry is trying to adopt new technologies that will allow these functionalities to be developed without an increase in the size of the equipment, or of the development costs. To enumerate some of these technologies: virtualization, multi-core technologies are the ones that show the biggest potential. Because these technologies are not mature, research has to be done in order to fully maximize their potential. Another technology that is highly used by the industry is the Ethernet communication protocol. It presents some advantages, but due to the non-real-time nature of the applications that it was designed for, it has to be extended in order to be used in real-time applications. The objective of this thesis work is to model an Ethernet network comprised of software partitions so that it can provide timing guarantees for the traffic that traverses the network. A Response Time Analysis for real-time flows over such networks is proposed. The model and the RTA are evaluated by experiments.

Embedded systems are becoming ubiquitous in our daily life. Due to close interaction with physical world, embedded systems are typically subject to timing constraints. At design time, it must be ensured that the run-time behaviors of such systems satisfy the pre-specified timing constraints under any circumstance. In this thesis, we develop techniques to address the timing analysis problems brought by the increasing complexity of underlying hardware and software on different levels of abstraction in embedded systems design. On the program level, we develop quantitative analysis techniques to predict the cache hit/miss behaviors for tight WCET estimation, and study two commonly used replacement policies, MRU and FIFO, which cannot be analyzed adequately using the state-of-the-art qualitative cache analysis method. Our quantitative approach greatly improves the precision of WCET estimation and discloses interesting predictability properties of these replacement policies, which are concealed in the qualitative analysis framework. On the component level, we address the challenges raised by multi-core computing. Several fundamental problems in multiprocessor scheduling are investigated. In global scheduling, we propose an analysis method to rule out a great part of impossible system behaviors for better analysis precision, and establish conditions to guarantee the bounded responsiveness of computing tasks. In partitioned scheduling, we close a long standing open problem to generalize the famous Liu and Layland's utilization bound in uniprocessor real-time scheduling to multiprocessor systems. We also propose to use cache partitioning for multi-core systems to avoid contentions on shared caches, and solve the underlying schedulability analysis problem. On the system level, we present techniques to improve the Real-Time Calculus (RTC) analysis framework in both efficiency and precision. First, we have developed Finitary Real-Time Calculus to solve the scalability problem of the original RTC due to period explosion. The key idea is to only maintain and operate on a limited prefix of each curve that is relevant to the final results during the whole analysis procedure. We further improve the analysis precision of EDF components in RTC, by precisely bounding the response time of each computation request.

During the past decades of research in Real-Time systems, non-preemptive scheduling and fully preemptive scheduling have been extensively investigated, as well as compared with each other. However, it has been shown that none of the two scheduling paradigms dominates over the other in terms of schedulability. In this context, Limited Preemptive Scheduling (LPS) has emerged as an attractive alternative with respect to, e.g., increasing the overall system schedu- lability, efficiently reducing the blocking by lower priority tasks (compared to non-preemptive scheduling) as well as efficiently controlling the number of preemptions, thus controlling the overall preemption-related delay (compared to fully-preemptive scheduling). Several approaches within LPS enable the above mentioned advantages. In our work, we consider the Fixed Preemption Point Scheduling (LP-FPP) as it has been proved to effectively reduce the preemption-related delay compared to other LPS approaches. In particular, LP-FPP facilitates more precise estimation of the preemption-related delays, since the preemption points of a task in LP-FPP are explicitly selected during the design phase, unlike the other LPS approaches where the preemption points are determined at runtime. The main goal of the proposed work is to improve the schedulability of real-time systems under the LP-FPP approach. We investigate its use in different domains, such as: single core hard real-time systems, partitioned multi-core systems and real-time systems which can occasionally tolerate deadline misses. We enrich the state of the art for the single core hard real-time systems by proposing a novel cache-related preemption delay analysis, towards reducing the pessimism of the previously proposed methods. In the context of partitioned multi-core scheduling we propose a novel partitioning criterion for the Worst-Fit Decreasing based partitioning, and we also contribute with the comparison of existing partitioning strategies for LP-FPP scheduling. Finally, in the context of real-time systems which can occasionally tolerate deadline misses, we contribute with a probabilistic response time analysis for LP-FPP scheduling and a preemption point selection method for reducing the deadline-misses of the tasks.

Optimised allocation of system architectures is a well researched area as it can greatly reduce the developmental cost of systems and increase performance and reliability in their respective applications.In conjunction with the recent shift from federated to integrated architectures in automotive, and the increasing complexity of computer systems, both in terms of software and hardware, the applications of design space exploration and optimised allocation of system architectures are of great interest.This thesis proposes a method to derive architectures and their allocations for systems with real-time constraints.The method implements integer linear programming to solve for an optimised allocation of system architectures according to a set of linear constraints while taking resource requirements, communication dependencies, and manual design choices into account.Additionally, this thesis describes and evaluates an industrial use case using the method wherein the timing characteristics of a system were evaluated, and, the method applied to simultaneously derive a system architecture, and, an optimised allocation of the system architecture.This thesis presents evidence and validations that suggest the viability of the method and its use case in an industrial setting.The work in this thesis sets precedence for future research and development, as well as future applications of the method in both industry and academia.