Embedded Systems

This paper presents about ENRICHMENT OF EMBEDDED SYSTEMS SOFT WARE METHODS. Normally an A Embedded System. An Embedded System is a computer system designed to perform one or a few dedicated function often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. By contrast, a general-purpose computer, such as a personal computer (PC), is designed to be flexible and to meet a wide range of end-user needs. Embedded systems control many devices in common use today. Embedded systems are critical components of our everyday lives, be they in control systems like airbag controllers in cars, or in consumer products like washing machines and phones. Since such electronic products evolve to software intensive systems, software, becoming larger, more complex and prevalent, poses severe problems in the development of those systems. The required degree of dependability will lead to more rigour in construction and validation, and hence, strengthen the role of formal methods. Moreover, methods used in other areas, such as model checking in hardware verification and finite-state-machine-based testing in protocol testing, will make their way.

1.    Introduction: Embedded systems are composed of both software and hardware; they may include analogue devices in addition to digital ones. They are dedicated to some specific task which they perform as part of some larger system. Embedded systems are part of our everyday lives. They may be found in household goods like washing machines and video recorders, in other consumer products like car electronics and telecommunication systems, in transportation systems like car navigation systems, aeroplane and railway control, in autonomous robots, as well as in industrial process control like chemical and power generation plants.

Both the number and the size and complexity of applications are increasing. According to current day televisions require between 50-100 person years of software development and the amount of control software is doubling roughly every 2 years. Moreover, "Embedded software is the fastest increasing area of information technology….” In class Germany nearly a third of costs for developing high class cars is   spent for intelligent electronics and software such as airbag control, anti blocking, and electronic stability systems. Electronic products evolve to software intensive systems. In contrast to traditional software development, embedded system development is mass production: the product is produced in very many (physical) instances. Therefore, the costs of each individual instance count; saving just some cents for one instance quickly sums up to a large amount of money. Hence, the cheapest possible parts are likely to be used, resulting in problems like lack of memory, well known from the early days of software development.
   
Another consequence from the applications is the need for a high degree of dependability. As part of physical systems, such as air bag controllers in today's, and brake-by-wire systems in tomorrow's cars, software failures may result in physical damage up to the loss of  lives; as part of process control systems, for instance in the chemical industries, system failures may lead to ecological damage; even in non safety critical applications software failures may cause severe damage -in this case economic damage -because of mass production. If a car company has to recall a car (the German car company VW, for instance, had to recall 35.000 cars of type Golf because of a software fault in the airbag controller) this results in costs for repair and also loss of reputation. Hence, dependability of embedded systems is an issue not only in safety-critical applications.

These special circumstances have some general impact on the development process: the need for rigorous design and validation. Embedded systems cannot be developed like some of-the shelf software. Letting the user do the beta testing could be very expensive. Once the product is delivered it is difficult to remove faults, there are far too many devices to take them back for repair. Moreover, it is obvious that it would not be a good idea to first build the system (physically) and then start checking whether its functionality meets the requirements.

This poses severe restrictions on the methods used for both construction and validation. The need for rigorous validation in the development process requires design methods that support verification and test. They must allow to ensure the satisfaction of required properties, and validation methods must be used to do so. Since validation cannot be neglected, its costs count. Early validation through prototyping and simulation helps to save time and costs. Furthermore, it is worth while to re-consider the use of formal verification, since it may need less effort than simulation and testing.

Looking at the variety of applications it is not surprising that the discussion of embedded systems is influenced by many different engineering disciplines, ranging from hardware engineering, electronics, mechatronics and control theory to software engineering, protocol development, real-time systems, and fault tolerance. The journal Design Automation for Embedded Systems, for instance, provides a hardware-oriented view, discussing in particular topics such as hardware-software codesign (e.g. partitioning of software and hardware), and Computer  Aided Design (CAD) (hardware synthesis, hardware simulation, test and verification).

2.    Embedded systems: Embedded systems are typically reactive. In contrast to transformational systems which take the input available on start of the computation, produce their output and provide it on termination, reactive systems are usually non-terminating processes which continuously respond to stimuli from the environment. An embedded, reactive system monitors its environment via sensors and emits commands to actuators. Its external behavior is that of a sequence of stimuli and responses between system and environment. Different from interactive systems, reactive systems have to react on time. There action time of an interactive system is determined by the system itself the environment (e.g. a user) may have to wait. Examples include word processors, software for building up connection lines for phone calls, and internet services. In contrast, the reaction time of a reactive system, such as an airbag controller in a car, a landing control system in an aeroplane, and a traffic-light controller is determined by the environment. It should be noticed that on time does not necessarily mean fast. Reactive systems need to be fast enough to respond to every input event, and their reaction latency need to be short enough that the environment is still receptive to the responses. On the other hand, they must not be too fast: a reactive system would not be on time neither if the environment would not yet be ready for the response.

Embedded systems have to be considered within their environment, since only together they provide the service necessary to solve the task they are intended for. Embedded (reactive) systems typically are real-time systems, consisting of parallel components which may be distributed. Timing constraints may require on time

Embedded systems may be found in a variety of systems ranging from single simple devices and micro computers to large complex systems, multi processors and computer networks. This variety may even be found within one application area. The automotive industry may serve as an example. A high class BMW today already contains about 50 electronic controllers, serving either comfort or safety. Examples include window and engine-control, anti-blocking system, air bag and belt control. Each of these controllers is a reactive real-time system which communicates with its environment via signals (sensors and actuators). It may consist of concurrent components. Such devices are connected through some bus, often a CAN bus. This again forms a reactive real-time system which now is intrinsically concurrent, consisting of distributed components. Distribution is local in the sense that communication is through signals on a bus.

3.    Software for embedded systems : The Dynamic behaviour of embedded systems is characterized through sequences of input and output events. Such traces are often represented as sequence diagrams,that describe communication between entities in a graphical form. Horizontal lines in a sequence diagram represent the considered entities (e.g. processes, tasks, objects); vertical arrows between horizontal ones represent message flow (e.g. data, signals). The diagram is interpreted from top to bottom: an arrow above another one means that the respective communication comes first.

In object-oriented methods sequence diagrams are used to capture scenarios and the collaboration among objects. In the telecommunication area they are known as Message Sequence Charts (MCSs), standardised by the International Telecommunication Union {Telecommunication Sector (ITU-T) and recommended to be used together with SDL (Specification and Description Language, see below). Specifying example executions in the requirement phase, sequence diagrams capture required behaviours, generating them from program executions they capture actual behaviours. By comparing the two they can be used for validation and testing. A sequence diagram models one execution. For modelling a system's behaviour it is not sufficient to specify particular executions, all possible behaviours have to be captured.

While transformational systems can well be modelled as functions mapping some input domain onto some output domain this is not adequate for modelling reactive behaviour. Reactive behaviour is continuous {at least in normal cases. The output of a reactive system does not only depend on the input but also on the current state. Therefore, the behaviour of a reactive system cannot be characterized by a pair of inputs and outputs. For describing reactive behaviour, sequences of such pairs are needed. Hence, the well known models of a function and a flow graph are not adequate for describing reactive behaviour. The basic model for describing reactive behaviour is that of a finite-state machine (FSM) where states represent memory and transitions represent reactions.

An FSM allows to model statements like "if the system is in state A and x occurs, the system change to state B producing Finite-state y". FSMs are a well known concept, and automata theory is well defined. FSMs are used in software development. State transition diagrams tend to grew very quickly leading to a large number of states such that the diagram cannot be represented conveniently on some sheets of paper (or a screen) any more. Being at and lacking structure, they are inappropriate for modeling large, complex systems. Furthermore, they do not address concurrency. "To be useful, a state/event approach must be modular, hierarchical and well-structured"

In State charts a state may be decomposed into a hierarchy of substates. Thus, there are three types of  states, basic states (which are not decomp osed), OR-states and AND-states. An OR-state represents a refinement, i.e. the subautomaton can be only in one state at a time, while an AND-state represents parallel composition, i.e. the automaton being in this state, is in all concurrent substates. Communication between concurrent states is broadcast (everybody may listen). For describing real-time systems, two types of models are used, event-based and time-based. While an event-based system is triggered by external events, a time-based system reads its input signals periodically (driven by some clock). Triggered means that the system performs its action(s) and responds. Hence, sin event-based systems the environment decides on activation while in time-based ones, the system decides. Event-based systems may be characterized as interrupt-driven, time-based systems as sampling. Being asynchronous, communication in event-based systems needs explicit means for synchronization. Time-based systems can be synchronized implicitly through the (periodic) signals of the global clock. Event-triggered, asynchronous communication is typical for telecommunication systems, an area where SDL (Specification and Description Language) is widely used. SDL is standardized and recommended by the ITU-T (International Telecommunication Union -Telecommunication Sector), and many protocol standards are described by ITU-T in SDL.

An SDL description consists of a behavior description through extended finite-state machines, an architectural description as a hierarchy of blocks, sub blocks, processes and procedures, a communication description through signals, and data descriptions through abstract data types. The behavior description is a variant of State charts. FSMs communicate with each other and the environment through signals. The communication is asynchronous. The architectural description is object oriented in that it provides typing of blocks and processes as well as inheritance.
Time-based, synchronous communication is typical for hardware systems which are clocked. Synchronous languages and time-triggered communication protocols are two promising approaches. Synchronous languages have been developed in particular for developing embedded systems. In the synchronous model all parallel automata in one step make a transition (all are triggered simultaneously by the clock signal) while in event-driven model there may be idle sub automata. Synchronous languages will be discussed in more detail in the next section.

Time-triggered architectures are promoted, for instance, by the automotive industry that intends to use them for safety-critical car electronics, in particular x-by-wire systems. Time-triggered communication protocol, each node has its own predefined time-slot for sending its message. The protocol is based on broadcast communication: everybody may listen to the bus and read messages which are not consumed by reading. The protocol is based on globally synchronized clocks. Time-triggered architectures are deterministic. They cannot be overloaded, and they do not need dynamic buer management.

Designing an embedded system the trade-off between exibility of event-based approaches and controllability of time-based approaches must be decided. The synchronous communication in time-based systems need more pre-planning in the design and is less exidible than the asynchronous communication in event-based systems. On the other hand it provides a better chance for dependability, since it is deterministic, i.e. predictable and easier to validate. This is the reason why synchronous communication an issue. In Kopetz reports that "The control system for Japan's Hankinson bullet train uses a large time triggered real-time fault-tolerant system", and application she claims right that "Safety critical computer for control, nuclear power plant shutdown, and so on, have to be fault tolerant and are therefore based on the time triggered instance, paradigm."The European aircraft industry, therefore uses languages and German automotive industry is interested in time-triggered protocols for car electronics.

Designing software and systems typically include not only designing behaviour but also architecture and data structures. While finite-state machine approaches are well suited for describing reactive behavior they lack means for describing architecture and data. Even for small embedded systems which are mainly control driven, containing only few and simple data, object-oriented concepts may help. Using software, devices are built as variants and also as versions over time. This lead to the typical (software) problems with versions and variants, with maintainability and re-use. Object-oriented concepts provide the edibility needed for coping with such problems. Furthermore, as already discussed above, software makes it possible to add functionality to devices, with the eect that size and complexity tend to grow rapidly. Hence, it seems quite natural to combine State charts like descriptions and object-oriented technology. A prominent example is the Unified Modeling Language (UML).

Another example is the synchronous object-oriented language synchronous Eiffel which combines object-oriented technology with synchronous languages. The synchronous approach, it is based on the hypothesis of perfect synchrony which says that computations are fast enough so that, for the environment, output signals appear to be synchronous with the inputs. A synchronous program may be regarded as a set of reactive objects which communicate via signals on a bus with a special signal, a clock tick. Objects read their input signals, compute their reactions, and finally emit their output signals between two clock ticks (one reaction step, called instant). Though not yet widely spread in the software community this conforms to a common basic concept of hardware design and many engineering formalisms: processes are clocked. Many real-time systems are designed under such a premise.

Several synchronous languages have been developed and are used in practice [1]. The languages look quite different. Argos , for instance, a purely synchronous variant of State charts, is graphical in style, Esterel is imperative. Both are state-based languages and thus well suited for modeling control-dominated applications. approaches are popular in applications where safety is Luster is a declarative data flow language and thus
better suited for capturing continuous behavior. A Luster-program is a set of equations. In each reaction step (triggered by a clock), each variable on the left hand side takes the value of the expression on the right hand side.

Synchronous languages support modeling control, but they do not support describing architectures and data. Therefore, the synchronous object-oriented language synchronous Eiffel  has been developed. Designing a system in SE means defining reactive objects, and reactive classes respectively. A reactive class contains a description of operations and attributes as known from object-oriented construction, and a description of the reactive behavior. Behavior may be described graphically similar to Argos or (synchronous) State charts, imperatively (similar toEsterel), or declaratively (similar toLustre). Integrating these styles, see enables multi-style design: the designer is free to adopt the language most appropriate for different aspects of the same design. For understanding the power and flexibility of the synchronous model it is important to notice that a synchronous program can be translated into a finite state machine encoded as a set of Boolean equations, a Boolean Automaton (for a detailed discussion see [15]). Each signal of the program is represented as a Boolean variable which is true If the respective signal is present and false otherwise. The state is captured in a set of Boolean variables, registers: if a register is true, the object is in that state. The reactive behaviour is determined by the evaluation of these sets of equations.

The variable representing an input signal is true if the signal is present in this instant. Each output signal and each register is determined by an equation: the respective Boolean variable (on the left hand side of the equation) is set to the value of the expression on the right hand side. If the expression on the right hand side of the equation for an output signal evaluates to true the output signal is emitted in this instant. If the expression for a register evaluates to true this aspects the context instant: the register is true in the next instant. This set of Boolean equations is the basis for many tools. It can be statically checked for causality errors. For example, the presence of a signal must not depend on another signal that in turn depends on the first one. Such a situation corresponds to a deadlock situation. Programs with causality cycles are rejected by the compilers. The set of Boolean equations can be translated into any programming language, e.g. C, since every programming language supports Booleans. It also can be translated into hardware descriptions like BLIFF and Virology, since the format is very close to hardware net lists. Furthermore, it can be transformed into the input format of model checkers such as VIS [9]. Hence, some temp oral logic, e.g. CTL (Computation Tree Logic), branching time logic with future operator, can be used for specifying properties, and the model checker automatically checks whether the property is verified by the program Note that this way verification is done on the program itself rather than an additional model of the program.

The synchronous approach supports rigorous validation and formal verification. Reactivity can be guaranteed through static analysis (causality) such that a successfully compiled program is free from deadlocks and life locks. Reactivity here means that the system always reacts to an input and that the reaction is unique and terminates within a fixed amount of time. Taken as executable specification, the design can be validated early in the development process. Though the specification usually consists of many parallel components, the program is deterministic. Required properties may be specified as temp oral logic formulas (with past or future operators) and ensured through automatic formal
Verification with model checking tools.

In addition, the synchronous approach provides another, very attractive, way of speciation: the required property or behavior can be formulated as a synchronous program too, a synchronous observer [11]. An observer receives input and output signals of the program to be validated, checks whether they come at the right instant and in the correct sequence, and as result produces a special signal OK in every reaction step if the
program reacts correctly (or ERROR if it does not).Observers may be used for checking at run time whether the program reacts correctly. They do not change the system's behavior. Furthermore, they provide a practical route to formal verification: a model checker can be used which automatically checks (at compile time) whether the signal OK is emitted in every step (or ERROR never). Hence, many properties (in particular safety properties) can be specified and proved without using a separate temporal logic language. An example is discussed in [14].

4.    Conclusion: Since Embedded Systems come within a variety of applications from single and simple devices to large and complex distributed systems, various concepts and methods are needed for their development. So the question is not which method to use but rather how they use it. A trend to combine object-oriented technology, state-machine based approaches and sequence charts and to graphic notations (with defined semantics) can be noticed. A problem still is the modeling of hybrid systems, i.e. the problem of mixed discrete and continuous behaviors caused by the co-existence of digital and analogue devices. Combining a data flow language like Luster with a state-oriented language like Argos or Sterol is only a first step into this direction. Concepts from both computer science and control theory need to be integrated. “It seems sensible that these systems should be designed and implemented by engineers trained in both control and computer sciences.” Complex systems generally have both synchronous and asynchronous behaviors. Asynchronous components are easier to distribute, but they are typically none Deterministic and their behaviors are difficult to predict. Synchronous behaviors are precisely predictable (at compile-time). Hence, the designer has to decide on te trade off between flexibility and dependability. The synchronous approach will get a similar important role in the development of dependable, embedded systems as object-oriented development has among software engineers today. The same can be said about time-triggered protocols, and because of the same reason: in many applications the dependability provided by time-triggered approaches is more important than the edibility provided by other paradigms. In car electronics, for instance, time-triggered (synchronous) protocols are considered to t better to the requirements than the event-triggered proto cols [12]. Current research is addressing the extension of the synchronous paradigm through asynchronous aspects for handling distribution without loosing too much controllability. The need for dependability and thus rigorous validation requires methods and tools to introduce a high level of confidence into the development process as a whole. This also implies a design flow from requirements and specifications to software and hardware generation and optimization without any gap such as manual coding from some (validated) specification.


5.    References:
1.    Benveniste, (1994) Synchronous languages provide safety in reactive system design. Control Engineering, September.
2.    G. Benveniste,(1991) A.; Berry. The synchronous approach to reactive and real-time systems. Proceedings of the IEEE, 79(9).
3.    A. Bochmann, von G.; Petrenko. Protocol testing: review of methods and relevance for software testing. In Software Engineering Notes.]
4.    R.H. Bourgonjon, (1998) Embedded systems in consumer products. In F. Rozenberg, G.; Vaandrager, editor, Lectures on Embedded Systems, volume 1494 of Lecture Notes in Computer Science, pages 395{ 403. Springer, Berlin.
5.    J. Camp osano, R; Wilb erg. Embedded system design. Design Automation for Embedded Systems.
6.    T.S. Chow, (1978) Testing software design modeled by finite-state machines. IEEE Trans. on Software Engineering, 4(3):178{187.
7.    E. Dilger and et al., (1997) Towards an architecture for safety related fault tolerant systems in vehicles. In ESREL'97.
8.     B.P. Douglass, (1999) Doing hard time: developing real-time systems with UML, objects, frameworks, and patterns. Addison Wesley Longman.
9.    The VIS Group. VIS: A system for verification and synthesis. In 8th International Conference on Computer Aided Verification, volume 1102 of Lecture Notes in Computer Science, pages 428-432, July 1996.
10.    N. Halbwachs, (1993) Synchronous Programming of Reactive Systems. Kluwer Academic Publishers.
11.    N. Halbwachs, F. Lagnier, and P. Raymond, (1993) Synchronous observers and the verification of reactive systems. In Third Int. Conf. on Algebraic Methodology and Software Technology, AMAST'93, Workshops in Computing. Springer-Verlag.
12.    H. Kopetz, (1995) Automotive electronics  present state and future prospects. In FTCS 25.
13.    H. Kopetz and G. Grunsteidl (1994) TTP { a protocol for fault-tolerant real-time systems. IEEE COMPUTER, pages 14{23, Jan.
14.    M. Mullerburg (1998) Validating embedded system software. In uroSTAR98, pages 363-374
15.    A. Poigne, M. Morley, O. Maes, L. Holenderski, and R. Budde (1998) The synchronous approach to designing reactive systems. Formal Methods in System Design, 12:163-187.