1

Real-Time Systems and Time Predictability

This introduction discusses real-time systems and shows how they differ from general purpose computing systems. Different types of real-time systems are explained and examples of these types are given. The need for time predictability of computer systems is exposed and the structure of the book is presented.

1.1. Real-time systems

1.1.1. Introduction

Most of the processors in use today are not part of what we usually call computers, i.e. servers, workstations, laptops or tablets. They are instead components of hidden computing systems that control and interact with physical environments, also referred to as embedded systems. Such systems are developed in a wide range of domains: transport (cars, aircrafts, trains and rockets), household appliances (washing machines and vacuum cleaners), communications (cellular phones, modems and routers), multimedia (MP3 players and set top boxes), construction machinery (drilling machines), production lines (robots), medicine (pacemakers), etc. In cars, for example, embedded software controls the behavior of the engine with the goal of saving fuel and, at the same time, limiting emissions. Digital equipment also provides safety improvement by the means of dedicated functions (e.g. antilock breaking systems and air bags) and the well-being of passengers (e.g. air conditioning, power windows or audio systems). In recent years, the notion of cyber-physical systems has been introduced. This refers to such systems that link several computing elements, which tightly interact both among one another and with their physical environment.

Embedded systems typically abide by a number of constraints that go beyond the usual scope of computing systems. Economical considerations, especially for large markets such as those for phones or cars, impose optimizing the cost. This is particularly true for hardware components: even an additional 5 cents is a lot when multiplied by 1,000,000 units. But cost issues also concern software development. For this reason, the reuse of software components (intellectual property (IP) components) is usually favored. Hand-held electronic devices should be as small and as light as possible. But size and, above all, weight may also be an issue in some transportation systems: additional weight usually increases the cost. Mobile devices must exhibit low energy consumption to optimize the life of batteries between charges. Thermal dissipation may be an issue in cases of limited cooling facilities, e.g. in confined spaces. Other constraints are put on systems that operate in harsh environments and are subjected to heat, vibrations, shocks, radio frequency (RF) interference, corrosion water, etc. Components in aerospace systems can be hit by cosmic and high-energy ionizing particles that engender the so-called single event upset that may change the state of bits. Radiation-hardened components are used in spatial systems but also around nuclear reactors.

Furthermore, some embedded systems must fulfill timing constraints: some of the tasks that implement the system must meet deadlines. For such systems, referred to as real-time systems, producing results in time is required as much as producing correct results. As a result, part of the system design and verification process consists of performing timing analysis of critical tasks, then checking that they can be scheduled in such a way that they are able to meet their deadlines. Various techniques and tools have been developed for this purpose and will be surveyed throughout this book. In section 1.1.2, the concept of task criticality will be discussed, safety standards will be briefly reviewed in section 1.1.3 and various examples of real-life real-time systems will be discussed in section 1.1.4.

Progress in technology and in computer architecture designs leads to components that offer steadily increasing computing power. Today, increasing clock frequencies in order to obtain higher performance from advanced processors is no longer feasible. So, the trend is to integrate multiple cores on a single chip: the aggregated performance is higher than what can be achieved with single-core architectures, and at the same time the performance/energy ratio is improved. Better performance allows us to consider the implementation of new and advanced functionalities, such as steer-by-wire and brake-by-wire driver-assistance systems, combustion engine control, or automatic emergency-braking tiggered by collision avoidance techniques. These systems can evaluate more sensor signals and master more complex situations if higher performance is provided by future control units. Examples could be online distance measures that trigger higher security actions for passengers such as closing the windows and setting the passenger seats in upright positions if an unavoidable crash is detected. Motor injection could be optimized to reduce gas consumption and emissions through better processor performances. Embedded systems for automotive applications are under permanent pressure of cost, while demanding higher performance due to new standards and Quality-of-Service (QoS). Also of paramount and vital importance is the ability to develop and produce systems that are capable of achieving maximum safety, reliability and availability.

Aerospace applications benefit from more powerful processors by providing support for ever-increasing demands of additional functionality on board or a higher level of comfort through a better control of the actuators and, at the same time, requiring absolute guarantees on the timing performance of the system. In addition, certification requirements (e.g. DO-178C) impose restrictions on proving properties of hardware and software, especially regarding timing. At the very least, a fourfold increase in performance is desired for next-generation aircrafts.

On a similar level, future space applications will require increased performance; however, higher CPU clock frequency rates are not generally feasible due to the increased risk of electromagnetic interference and errors induced from cosmic radiation. In this context, an increase in performance is not due to increasing CPU frequencies, but increasing the number of computation units. The most energy and weight efficient way to achieve this is through multicore processors. Current trends in the development of the freely available LEON family of processors for space applications precisely follow this trend. However, in a project performed for ESA by Rapita Systems called PEAL, it was shown that there are still significant issues regarding the adoption of these advanced features by industry unless provable properties regarding timing can be demonstrated. In aerospace, the demand for reduced weight and size is relentless. Guidance, navigation and control algorithms routinely coexist on a single processor. With the advent of free flight and autonomous flight, we must increasingly co-host many other safety and non-safety critical applications on a common powerful processor to maximally utilize hardware that reduces recurring costs, size, weight and power.

This race for computing performance has consequences on the verification and validation of critical systems. Most schemes implemented in modern processors to achieve high performance exhibit one of the following characteristics: (1) their behavior relies on the execution history (e.g. dynamic branch predictors make their decisions based on the issues of previous branches; cache memories contain instructions and data that have been accessed in the past); (2) their behavior is dynamic, i.e. it depends on information that is only available at runtime (e.g. the way an instruction crosses a pipeline depends on which instructions are in the pipeline at the same time); (3) they speculate on the results of some instructions in order to process other instructions faster. These characteristics combined with a wide range of possible values of input data make the execution profile of tasks difficult to predict at analysis time. With multicore architectures, the sharing of resources (e.g. the interconnection network and part of the memory) among cores adds to the complexity. Paradoxically, a faster architecture does not systematically mean a better chance of meeting deadlines: the sophisticated mechanisms used to increase the instruction rate are often hard, sometimes even impossible, to model, and this may result in longer estimated execution times due to the pessimism engendered by overcautious assumptions. In section 1.2, we review the concept of time predictability. One objective of this book is to show why some of the above-mentioned schemes challenge timing analysis techniques and to provide some recommendations for time-predictable architectures. Shortly, the global advice is: Make the worst case fast and the whole system easy to analyze [SCH 09b].

1.1.2. Soft, firm and hard real-time systems

Real-time systems are commonly divided into the following three categories according to the consequence of missing a deadline (see Figure 1.1):

– In hard real-time systems, missing a deadline is a full system failure. Dramatic consequences include environmental disaster, economic crash, or even loss of human lives. An example of such a system is the control unit that triggers inflating air bags during a car crash. The decision to use the air bag is taken from monitoring various sensors, e.g. accelerometers, wheel speed sensors, gyroscopes, seat occupancy sensors and brake pressure sensors. It must be taken in time, i.e. within a given delay after the collision is anticipated, so that the driver and the passengers are protected against hitting the steering...