Real-Time facilities

As mentioned, response time is crucial in any embedded (/real-time) system. As this is often near impossible to guarantee, due to computing resources under all possible conditions, real-time systems are often constructed using processors with considerable spare capacity. This is to ensure that a worst-case scenario does not produce unwelcome delays. Given adequate processing power, language and run-time support are required to enable the programmer to:

• specify times at which actions are to be performed;
• specify times at which actions are to be completed;
• support repeating (periodic or aperiodic) work;
• control (i.e. bound) the jitter on input and output operations;
• respond to situations where not all of the timing requirements can be met;
• respond to situations where the timing requirements are changed dynamically.

These are called real-time control facilities, and enable the program to synchronize with time itself.

Some systems are more demanding at certain periods, and therefore needs to change the timing requirements dynamically. As an example, an aircraft flight control system needs to focus at the task at hand, and also be ready to give all computing resources to handle an emergency. Such changes are generally known as mood changes, and the also have consequences for the temporal characteristics of the executing software.

Concurrent control of separate system components

Often, an embedded system must handle several coexisting external elements with which the computer must interact simultaneously. Then it is necessary to consider distributed and multiprocessor embedded systems. The problem then becomes how to express the concurrency in the structure of programs which exhibit concurrency. Chapter 4, 5 and 6 will consider various models of concurrent programming, and how to achieve reliable communication and synchronization between concurrent processes in the presence of design errors.

Low-level programming

An embedded system typically requires the computer components to interact with the external world, by monitoring sensors and controlling actuators for a wide variety of devices. These devices interface the computer via input and output registers, and their operational requirements are device- and computer-dependent, and may also generate interrupts. A real-time system is also often run by battery in a mobile device. We have also mentioned that real-time systems are very dependent on response time. Low-level programming eliminates both delay and extra power consumption by using built in language features. High-level programming enables the programmer to abstract away from implementation details, and to concentrate on solving the problem at hand. For a real-time programmer, this luxury is unacceptable, since delay and power consumption are two central problems when programming a real-time system.

Support for numerical computation

When a real-time system is to control some engineering activity, it often involves continuous signals. For very simple systems, one might have an analog controller working on the continuous signals. One wish to calculate an input, based on comparing the output with a reference signal. This will often require heavy calculations, depending on the complexity of the model and the number of inputs and outputs. Because of these difficulties, most controllers are implemented as digital computers. Since nature is analog, and computers are digital, converters are needed in order to convert analog signals to digital, and vice versa. This must again be taken into account when designing of the control algorithms. A fundamental requirement of a real-time programming language, therefore, is the ability to manipulate real or floating-point numbers. Fortunately most engineering languages do provide the necessary abstractions in this area.

Large and complex

Largeness is, by Lehman and Belady (1985) related to variety. Since most real-time systems respond to real-world events, the amount of variety is great. Hence, most real-time systems will exhibit the rather undesirable property of largeness. Due to this large- ness, real-time systems needs to be broken down into smaller components which can be managed effectively. Real-time languages provides features, such as abstract data types, classes, objects, generic components, separate compilation, etc to manage this software complexity.

Extremely reliable and safe

For some systems, failure is simply not an option. Systems providing life support, controlling nuclear plants or transferring money, can not fail, and if they do, however, fail, they must fail in a controlled way. When human interaction is required, care must be taken in the design of the interface in order to minimize the possibility of human error. Chapter 2 and 3 will consider the problems of producing reliable and safe software. Copying with both expected and unexpected error conditions will be examined in chapter 7 and 13(?).

Structure of the book

If you are interested in the structure of the book, read the book, not the compendium.

Requirement specification

Almost all computing projects start with an informal description of what is desired, followed by an extensive analysis of requirements. In this stage, functionality is defined, temporal behaviour made explicit and reliability requirements and the desired behaviour of the software in the event of component failure. The environment must also be modelled. Since interaction with the environment is especially important for a real-time system, maximum rate of interrupts, maximum number of objects and failure modes are all important.

Design activities

Decomposition and abstraction form the basis of most software engineering methods. Decomposition involves the systematic breakdown of the complex system into smaller and smaller parts, until components are isolated that can be understood and engineered by individuals or small groups.Abstraction enables the consideration of detail, particularly that appertaining to implementation, to be postponed. Sub-levels in the design must have well-defined roles in order to be verifiable. If the specification of the entire system can be verified just in terms of the specification of the immediate subcomponents, the decomposition is said to be compositional. This is an important property when formally analysing programs. Whenever a class (object) is used, typically, it involves the addition of some form of task (process). Both object and task abstractions are important in the design and implementation of reliable embedded systems. These forms of encapsulation lead to the use of modules. From the definition of modules, more sizable components can be defined that may even be re-usable in subsequent designs. Cohesion and coupling are two metrics that are often used to describe the relationships between entities within a design. Cohesion is concerned with how well a module holds together - its internal strength. Allworth and Zobel gave six measures of cohesion that range from the very poor (Coincidental) to the strong (Functional). Coupling, by comparison, is a measure of the interdependence of program modules. Two modules passing control information between the are said to be tight, or have high coupling. On the other end you have loose coupling if only data is communicated. A loose coupling means that the module is easy to replace with an other one, ie what we want. A good decomposition is one with strong cohesion, and loose coupling. This principle is equally true in sequential and concurrent programming domains.

Testing and simulation

To assist in any complex testing activity, a realistic test bed presents many attractions. For software, such a test environment is called a simulator. Using a simulator helps create normal, as well as abnormal system behaviour without having to meltdown a nuclear reactor in order to test the system. It is crucial that the simulator are able to reproduce accurately the sequence of events expected in the real system. As mentioned before, high reliability requirements are the essence of most real-time systems, as it is clear that testing must be extremely stringent.

General language design criteria

Young (1982) lists the following six criteria as the basis of a real-time language design: security, readability, flexibility, simplicity, portability and efficiency.

Security

The security of a language design is a measure of the extent to which programming errors can be detected automatically by the compiler or language run-time support system. Some errors, like errors in the programmer's logic, cannot be detected automatically. A secure language must, therefore, be well structured and readable so that such errors can easily be spotted. The disadvantage of security is compiler complexity and compilation time (I'm not slacking of, my code is compiling!)

Readability

Readability depends on it having the appropriate choice of keywords, the ability to define types and the facilities for program modularization. Good readability leads to increased maintainability, security and reduced documentation costs. It does, however, tend to increase the length of any given program.

Flexibility

Flexibility is when the language allow the programmer to express all the required operations in a straightforward and coherent fashion, without having to report to operating system commands or machine code.

Simplicity

Simplicity reduce cost associated with programmer training, minimizes the effort required to produce compilers and diminishes the possibility of making programming errors as a result of misinterpretation of the language. Simplicity and Flexibility can also be related to the expressive power, the ability to express the solution of a wide range of problems, and usability, the ease of use of the language.

Portability

Portability is the ability to run a program independent of the hardware on which it is executed on. Java claims to have this ability. This is difficult to achieve for a real-time system, however, it should be able to isolate the machine-dependent part of the program, from the machine-independent part.

Efficiency

Efficiency is the languages ability to allow efficient and predictable programs to be produced. Response times are crucial in a real-time system, however, this must be balanced against security, flexibility and readability requirements.

Assembly languages

Initially, most real-time systems were written in assembly language. Mostly due to the lack of support in high-level languages on microcomputers. Assembly language achieves efficient implementations, but is machine-oriented rather than problem-oriented. This keeps development costs high and makes maintenance difficult and expensive.

Sequential systems implementation languages

Most common programming languages used for real-time programming today, are sequential. They also tend to be weak in the facilities they provide for real-time control and reliability. As a result of these shortcomings, it is often necessary to rely on operating system support and assembly code inserts.

High-level concurrent programming languages

The software crisis in the 1970s had several symptoms. In short terms, the general language design criteria discussed above was seldom met. This was due to the fact that there were to many general-purpose languages in use. In the American Departement of Defence (DoD), there were over 450 different languages used in their embedded computer applications. DoD concluded that a single language was a desirable goal, and that no current language was suitable. So they decided to develop a new language, which resulted in Ada in 1983. Ada was later updated in 1995, 2005 and 2012, which is the current version.

Error detection

Since the recovery system is not continually running, there needs to be some way to detect a fault. There are many triggers that could be used.

• Replication checks are an extension to N-version programming that starts a recovery routine if one or more of the N results are wrong. Also consider a 2-version system: We cannot know which result is correct, but we know something is wrong, and action has to be taken.

• Timing checks take the form of a watchdog timer that each process have to reset within a set interval. Note that timing checks can only be used to check for time failures 􏰁 Other error detection systems have to be used for value failures.

• A reversal check can be used if there is a one-to-one relationship between the input and output. Thus, given an output, we can do a reversal calculation and compare it to the original input2.

• Coding checks rely on extra information sent along with the data, which can be compared on the receiving side. This is often used in communication. For example, imagine an integer is being sent on the network. A checksum might be the square of the number, which is calculated on the sending side. When both numbers are received, the square root of the second number is compared to the first: A mismatch is proof of error.

• Reasonableness checks rely on the knowledge of the system. This includes range checks, such as date and time validation.

• Structural checks are used to ensure the data structures are correct. We know the number of items in a list; if this changes when it is not supposed to, something is wrong. Go users might recall that the json.Marshal-function produce an error when the information it has received does not fit the target struct.

• Dynamic reasonableness checks the current output to the current output. Imagine a system on the form $x' = ax$ suddenly change from a large positive value to a small negative value: This jump should not occur, and something is wrong.

Damage confinement

Normally, errors are not detected the instant it occurred. Thus when an error is detected, the system have to figure out how far it has spread. Damage confinement concerns how the rest of the system is affected by an error. The two main techniques of doing this are modular decomposition and atomic actions. Modular decomposition emphasizes on breaking down the system into components where each component only communicates with another through well-defined interfaces. The internal details are hidden from other modules. If done properly, all errors are detected before another module needs the result. Atomic actions will be described in a later chapter.

Error recovery

When the error is found and we know the extent of it, the recovery process can start. There are two methods of error recovery: Forward and backward recovery. Forward recovery involves continuing as before with selected corrections. While this is an efficent method of error recovery, it requires a good understanding of what the error is and how it can be remedied, else the corrections might only be for the worse. Backward recovery steps back to a previous state, called a recovery point, and tries to accomplish the same action with a different method. This works straightforward when there are no threads, but it quickly gets complicated with multiple threads, because of communication between threads: If we need to roll one thread back to an earlier recovery point, we might have to undo a message sent to the other thread. If this is the case, the other thread might have to roll back, requiring messages sent to other threads to be undone. Thus since one thread has had an error, multiple other threads will have to roll back as well. This is called the domino effect.

Fault treatment

While error corrections remedy the error, it does not remove the underlying fault. This fault might be easy to identify and/or remedy, and the experienced error will not happen again. Both hardware and software faults are relatively easy to fix once identified if the system is allowed to be brought o􏰆ine. If the program have to be modified while executing, things get a little more complicated.

Ada

Supports explicit exception declaration in the same fashion as constants, with keyword exception. Can be declared in the same place as any other declaration and has the same scope. Some standard exceptions, like Constraint_Error and Storage_Error has the whole program as scope. Every block in Ada can contain an optional collection of exception handlers declared at the end of the block. They have the following syntax: when (the name of the identity) => (action). see textbook for more details. when others can be used as the last exception-handling choice to pick up all exceptions not listed previously. In Ada an exception which is raised and not handled by a subprogram is propagated to the caller of the subprogram. Therefore, such an exception will only be handled by the initialization code if it itself called the subprogram. See textbook (p.73) for example. The exception can also be propagated by a program re-raising the exception in the 3 EXCEPTIONS AND EXCEPTION HANDLING 24 local handler. This facility is useful in the programming of last wishes. See textbook (p.74) for example. Exceptions will never meet requirement 3, as detecting possible error conditions will require some resources. The Ada language provides a facility that checks if standard exceptions raised by the run-time environment becomes too costly for a particular application. Difficulties with the Ada model of exceptions:

• It can be hard to keep track of where an exception is raised.

• Ada does not allow a full range of parameters to be passed to handlers only a character string. This can be inconvenient if an object of a particular type needs to be passed.

• It is possible for exceptions to be propagated outside of the scope of their declaration. Such exceptions can only be trapped by others. However, they may go back into scope again when propagated further up the dynamic chain. This is disconcerting, although probably inevitable when using a block structured language and exception propagation.

Java

Java supports a termination model of exception handling, like Ada, but the exceptions are integrated into the object-oriented model. Raising an exception in Java is called throwing the exception, and it can only be han- dled from within a try-block. Each handler is specified using a catch statement, that works like a function declaration. A handler with parameter type T will catch a thrown object of type E if:

• T and E are the same type; or

• T is a parent (super) class of E at the throw point.

As with Ada, if no exception is found in the calling context of a function, the calling context is terminated and a handler is sought in a try-block within its calling context. Java supports a finally clause as part of a try-block. The code attached to this clause is guaranteed to execute whatever happens in the try-block irrespective of whether exceptions are thrown, caught or propagated, or, indeed, even if there are no exceptions thrown at all. To illustrate this, consider the following example, which will return false:

try {
    return true;
} finally {
    return false;
}

C

C does not define any exception-handling facilities within the language. This limits the possibilities of programming reliable systems, but it is possible to provide some form of exception-handling mechanism by using the macro facility of the language. To implement a termination model in C, it is necessary to save the status of a program's registers, and so on, on entry to an exception domain and then restore them if an exception occurs. This can be done using setjmp and longjmp.

Task/thread/process

A task/thread is the unit of parallelism and a single thread of control. A process is threads working within its own shared memory context.

Fundamental facilities

All concurrent programming consist of these fundamental facilities:

1. Activities (threads, tasks or processes).
2. Synchronization mechanisms.
3. Support of communication between concurrent activities.

Types of interaction

Interaction between tasks can be grouped as one of the following: - Independent: No synchronization or communication between threads. - Cooperate: Synchronization and communication. - Competing: About their share of resources. Although they communicate and synch to obtain resources, they are essentially independent.

Hierarchy

Based on hierarchy and relation, one often distinguish between tasks to be:

• Parent/child: Responsibility for the creation of another task. The parent may be delayed while the child is being created and initialized.

• Guardian/dependant: A task may be dependent on the guardian task itself. The guardian is not allowed to terminate until all dependent tasks have terminated.

• Sometimes the parent is also the guardian, but not necessarily with dynamic tasks.

Variation between the languages

The models of concurrency for the programming languages varies, especially when it comes to:

• Structure: The number of tasks can be either:

  • Static: fixed at compile-time
  • Dynamic: tasks are created any time

• The level of parallelism: Tasks can be either:

  • Nested: allowed to be defined within other tasks
  • Flat: not nested

• Granularity (detaljnivå): Within languages that supports nested constructs we distinct between:

  • Course grain parallelism: Program contains few tasks, each with a longer life. (Applies to most concurrent programming languages, typified by Ada.)
  • Fine grain parallelism: Program contains a large number of simple tasks, some of which exist only for a single action (e.g Occam2).

• Initialization: The tasks can be supplied with information by:

  • Passing it as parameters (most modern languages allow this)
  • Communicating explicitly after is has commenced its execution.

• Termination: Can be done in a variety of ways:

  1. Normal completion of execution of the task's body
  2. Suicide, by a self-terminate statement
  3. Abortion, through action of another task
  4. An untrapped error condition
  5. Never (when executing non-terminating loops)
  6. When no longer needed

Fork and join

The fork statement specifies that a designated routine should start executing concurrently with the invoker of the fork. The join statement allows the invoker to synchronize with the completion of the invoked routine. For example:

A procedure P(parent) begins and forks function F(child). They will now execute concurrently until the point when P states join. Here P will wait for F to finish (if it hasn't already done so). Fork and join allow for dynamic task creation and provide a means of passing information to the child via parameters. This can however be error prone in use, for example, in some systems a guardian must explicitly rejoin all dependants rather than merely wait for their completion.

Cobegin

The cobegin denotes the concurrent execution of a collection of statements, from $S_1$ to $S_n$. The cobegin terminates (equals join in the "Fork and join") when all statements have terminated. Data can be passed to the invoked tasks via parameters of the procedure call. A cobegin statement can even include a collection of statements that itself has a cobegin within it.

Explicit task declaration

The routines within the "Explicit task declaration" can state themselves whether they will be executed concurrently. This has become the standard way of expressing concurrency in real-time languages.

Ada

The unit of parallelism is called task in Ada. Tasks consist of a specification and a body. They can be passed initialization data upon creation, but only discrete types and access (pointer) types. The tasks can be given as task types. Tasks that do not have types declared for them and have no pointers to them are called anonymous.

Dynamic tasks can be created by giving a non-static value to the bounds of an array (of tasks) or using the 'new' operator on an access type (of task type). Tasks created by the ('new') allocator have the important property that the guardian (called master in Ada) is not in the block in which it was created, but in the one that contains the declaration of the access type. That means that if task Y is created inside an inner block, but was first declared outside, the inner block can terminate even though Y hasn't yet terminated. Termination: A task will terminate as it completes its body, there is an unhandled exception, when no longer needed (done by a select statement, or when it is aborted. Any task can abort any other task, and as a result, all its dependants will also abort. This is a dangerous action, and should be used only when no other alternative actions are possible.

Java

Java has a predefined class, java.lang.Thread which provides threads. Java also has a interface, called Runnable, to express concurrent execution. This provide a run method.

There are two ways to create threads. One way is to declare a class to be a subclass of Thread and override the run method. The second way is to declare a class that implements the Runnable interface. Common for all threads in Java is that they are not created automatically when their associated objects are created, but must be explicitly created and started using the start method (e.g thread1.start();).

Java allows dynamic thread creation like Ada, but unlike Ada, Java allows arbitrary data to be passed as parameters. Java has no guardian concept, and relies on garbage collection to clean up objects no longer accessible. But the main function still terminates when all its threads are terminated. The join method works like described in "fork and join", and the isAlive method tells whether a target has terminated.

Termination

A thread terminates as it completes its body or there is an unhandled exception.

Deamon threads provide genereal service and typically never terminate until they are no longer needed (like in Ada using the select statement). In Java, one does not longer have the same opportunity to abort threads like in Ada.

C/Real-Time POSIX

C/Real-Time POSIX provides three mechanisms for creating concurrent activities. The first is the fork and wait mechanism. The second is spawn, which is a combination of fork and exec. It also allows for a process to contain several threads like in Ada and Java. A thread can be executed when it is called by pthread_create. Here the parameters are passed.

Termination: A thread can be terminated normally by returning from its start_routine or by calling pthread_exit. One thread can wait for another to terminate by the pthread_join function. The cleaning up and reclaiming the storage of a thread is called detaching.

Steps to make a distributed system

Production of an application for a distributed system involves some steps not required when programs are produced for a single or multiprocessor platform.

Partitioning

dividing the system into parts

Configuration

the partitioned parts are associated with particular elements in the system

Allocation

turning the configured system into a system of executable modules

Transparent execution

the distributed software is executed so remote resources can be accessed independent of location

Reconfiguration

the dynamic change to the location of a software component