Real-Time Systems

The purpose of this introductory chapter is to describe the environment of real-time computer systems from a number of different perspectives. A solid understanding of the technical and economic factors that characterize a real-time application helps to interpret the demands that the system designer must cope with. The chapter starts with the definition of a real-time system and with a discussion of its functional and meta-functional requirements. Particular emphasis is placed on the temporal requirements that are derived from the well-understood properties of control applications. The objective of a control algorithm is to drive a process such that a performance criterion is satisfied. Random disturbances occurring in the environment degrade system performance and must be taken into account by the control algorithm. Any additional uncertainty that is introduced into the control loop by the control system itself, e.g., a non-predictable jitter of the control loop, results in a degradation of the quality of control.

A recent report on Software for Dependable Systems: Sufficient Evidence? [Jac07] by the National Academies contains as one of its central recommendations: One key to achieving dependability at reasonable cost is a serious and sustained commitment to simplicity, including simplicity of critical functions and simplicity in system interactions. This commitment is often the mark of true expertise. We consider simplicity to be the antonym of cognitive complexity (in the rest of this book we mean cognitive complexity whenever we use the word complexity). In every-day life, many embedded systems seem to move in the opposite direction. The ever-increasing demands on the functionality, and the non-functional constraints (such as safety, security, or energy consumption) that must be satisfied by embedded systems lead to a growth in system complexity.

This chapter starts with a general discussion on time and order. The notions of causal order, temporal order, and delivery order and their interrelationships are elaborated. The parameters that characterize the behavior and the quality of a digital clock are investigated. Section 3.2 proceeds along the positivist tradition by introducing an omniscient external observer with an absolute reference clock that can generate precise time-stamps for all relevant events. These absolute time-stamps are used to reason about the precision and accuracy of a global time base, and to expose the fundamental limits of time measurement in a distributed real-time system.

The objective of this chapter is to introduce the reader to a cross-domain architecture model of the behavior of a real-time system. This model will be used throughout the rest of the book. The model is based on three basic concepts, the concept of a computational component, the concept of state, and the concept of a message. Large systems can be built by the recursive composition of components that communicate by the exchange of messages. Components can be reused on the basis of their interface specification without having to understand the component internals. Concerns about the understandability have been of utmost importance in the development of this model.

It is said that Nobel Laureate Hannes Alfven once remarked that in Technology Paradise no acts of God can be permitted and everything happens according to the blueprints. The real world is no technology paradise – components can fail and blueprints (software) can contain design errors. This is the subject of this chapter. The chapter introduces the notions of fault, error, and failure and discusses the important concept of a fault-containment unit. It then proceeds to investigate the topic of security and argues that a security breach can compromise the safety of a safety-critical embedded system. The direct connection of many embedded systems to the Internet – the Internet of Things (IoT) – makes it possible for a distant attacker to search for vulnerabilities, and, if the intrusion is successful, to exercise remote control over the physical environment. Security is thus becoming a prime concern in the design of embedded systems that are connected to the Internet. The following section deals with the topic of anomaly detection. An anomaly is an out-of-norm behavior that indicates that some exceptional scenario is evolving. Anomaly detection can help to detect the early effects of a random failure or the activities of an intruder that tries to exploit system vulnerabilities. Whereas an anomaly lies in the grey zone between correct behavior and failure, an error is an incorrect state that requires immediate action to mitigate the consequences of the error.

The focus of this chapter is on the architectural view of real-time communication. The chapter commences by summarizing the requirements of a real-time communication system: low protocol latency with minimal jitter, the establishment of a global time base, fast error detection at the receiver, and the need for temporal error containment by the communication system, such that a babbling node cannot hinder the communication among the correct nodes. The next section presents a waistline model of a real-time communication system. At the center of the waist is the basic message transport service (BMTS) that transports a message from a sender to a set of receivers within a given latency and with a given reliability. In real-time systems, the tradeoff between reliability and timeliness has to remain in the hands of the application and should not be hardwired in the BMTS. The protocols above the BMTS, called higher-level protocols, implement services that require the bidirectional exchange of messages such as a simple request-reply service. The protocols below the BMTS, called lower-level protocols, implement the basic message transport service. The important topic of flow control, the different types of flow control and the phenomenon of thrashing are discussed in the following section. From the temporal point of view, three different communication services can be distinguished: event-triggered communication, rate-constrained communication, and time-triggered communication. The section on event-triggered communication contains the Ethernet protocol, the CAN protocol, and the UDP protocol from the Internet suite of protocols.

In a component-based distributed real-time system we distinguish two levels of system administration, the coordination of the message-based communication and resource allocation among the components and the establishment, coordination, and control of the concurrent tasks within each one of the components. The focus of this chapter is on the operating system and middleware functions within a component.

Many thousands of research papers have been written about how to schedule a set of tasks in a system with a limited amount of resources such that all tasks will meet their deadlines. This chapter tries to summarize some important results of scheduling research that are relevant to the designer of real-time systems. The chapter starts by introducing the notion of a schedulability test to determine whether a given task set is schedulable or not. It distinguishes between a sufficient, an exact, and a necessary schedulability test. A scheduling algorithm is optimal if it will find a schedule whenever there is a solution. The adversary argument shows that generally it is not possible to design an optimal on-line scheduling algorithm. A prerequisite for the application of any scheduling technique is knowledge about the worst-case execution time (WCET) of all time-critical tasks. Section 10.2 presents techniques to estimate the WCET of simple tasks and complex tasks. Modern processors with pipelines and caches make it difficult to arrive at tight bounds for the WCET. Anytime algorithms that contain a root segment that provides a result of sufficient (but low) quality and an optional periodic segment that improves on the quality of the previous result point to a way out of this dilemma.

This chapter on architecture design starts with a discussion on design in general. The designer must get a deep insight into all different aspects of the problem domain before she/he can design a proper structure for the application. In computer system design, the most important goal is controlling the complexity of the evolving artifact. A thorough analysis of the requirements and constraints limits the design space and avoids the investigation of unrealistic design alternatives. Any kind of structure restricts the design space and has a negative impact on the performance of a system, which must be carefully evaluated in real-time systems. The central step in the development of an architecture is concerned with the allocation of functions to nearly decomposable clusters of components. Components should have a high internal cohesion and simple external interfaces. In the following, different design styles such as model-based design and component-based design are discussed. The design of safety-critical systems starts with the safety analysis such as fault tree analysis and/or failure mode and effect analysis (FMEA) of the envisioned application, and the development of a convincing safety case. Different standards that must be observed in the design of safety-critical system are described, such as the IEC 61508 for electric and electronic equipment and the ARINC DO 178B standard for airborne equipment software. The elimination of all design errors, e.g., software errors or hardware errata of a large safety-critical system is a major challenge.

This chapter deals with assessment technologies. These technologies must convince a designer, user, or a certification authority that the developed computer system is safe to deploy and will fulfill its intended function in the planned real-world environment. In Sect. 12.1 we elaborate on the differences between validation and verification. Validation deals with the consistency between the informal model of the user’s intention and the behavior of the system-under-test (SUT), while verification deals with the consistency between a given (formal) specification and the SUT. The missing link between validation and verification are errors in the specification. The following section deals with the challenges of testing, the preferred validation technique. At the core of testing are the interference-free observability of results and the controllability of the inputs. The design for testability provides a framework that supports these characteristics. In most cases, only a tiny fraction of the input space can be examined by test cases. The proper selection of test cases should justify the assumption that, given the results of the test cases are correct, the system will operate correctly all over the input domain. In digital systems the validity of such an induction is doubtful, since digital inputs are not continuous but discrete – a single bit-flip can make a correct result erroneous. The decision whether the result of a test input is correct is delegated to a test oracle. The automation of test oracles is another challenge in the domain of testing. Model-based design, where a model of the plant and a model of the computer controller are interconnected to study the performance of closed-loop control systems is a promising route towards the automation of the test oracle. Given that a complete formal model of a design is available, formal methods can be deployed to check whether selected properties hold in all possible states of the model. In the last few years, the technique of model checking has matured such that it can handle systems of industrial size. The correct operation of the fault-masking mechanisms of a fault-tolerant system can only be assessed if the input space is extended to include the faults the system is supposed to tolerate. In the last section, the topics of physical fault-injection and software-based fault injection are covered. Since any physical sensor or actuator will eventually fail, fault-injection campaigns must establish the safe operation of a system even in the case that any particular sensor or actuator has failed.

The connection of physical things to the Internet makes it possible to access remote sensor data and to control the physical world from a distance. The mash-up of captured data with data retrieved from other sources, e.g., with data that is contained in the Web, gives rise to new synergistic services that go beyond the services that can be provided by an isolated embedded system. The Internet of Things is based on this vision. A smart object, which is the building block of the Internet of Things, is just another name for an embedded system that is connected to the Internet. There is another technology that points in the same direction – the RFID technology. The RFID technology, an extension of the ubiquitous optical bar codes that are found on many every-day products, requires the attachment of a smart low-cost electronic ID-tag to a product such that the identity of a product can be decoded from a distance. By putting more intelligence into the ID tag, the tagged thing becomes a smart object. The novelty of the Internet-of-Things (IoT) is not in any new disruptive technology, but in the pervasive deployment of smart objects.

This final chapter puts a closing bracket around the contents of the book. It is shown by a concrete example that it is possible to integrate the different concepts that have been explained in the previous 13 chapters of this book into a coherent framework. This coherent framework, the time-triggered architecture (TTA), is the result of more than 25 years of research at the Technische Universität Wien where numerous master and PhD students have contributed their part to the investigations. We must also gratefully mention the many inputs from colleagues from all over the world, particularly form the IFIP Working Group 10.4, that provided critical feedback and constructive suggestions. At first, the research was driven by curiosity to get a deep understanding of the notions of real-time, simultaneity, and determinism. In the later phases, the active participation by industry brought in the technical and economic constraints of the real world of industry and helped to adapt the concepts. What now has the appearance of a consistent whole is the result of many iterations and an intense interaction between theoretical insights and practical necessities.