Real-Time Linux Thesis

What is Real-Time? -- Briefly...

A real-time computer system means that it performs its functions and responds to external, asynchronous events within a specified amount of time. So a real-time operating system can be defined as a system capable of guaranteeing timing requirements of the processes under its control.

Linux is a standard time-sharing operating system which provides good average performance. To obtain correct timing it is necessary to make some changes in the kernel sources, i.e. in the interrupt handling and scheduling policies. In this way, you have a real-time platform, with low latency and high predictability requirements, typically for using in control and data-acquisition applications.

The time required for a system to respond to an event is called latency. The lower the latency the better the system will respond to events which require immediate attention. The predictability is related to how long the system will take to perform a particular action.

But what is it, really?

Real-Time systems are characterized by the fact that severe consequences will result if logical as well as timing correctness properties of the system are not satisfied. Typically, a real-time system consists of a controlling system and a controlled system. For example, in an automated factory the controlled system is the factory floor with its robots, assembling stations and the assembled parts. The controlling system is the computer and human interfaces that manage and coordinate the activities on the factory floor. Thus, the controlled system can be viewed as the environment with which the computer interacts.

The controlling system interacts with its environment based on the information available about the environment, say from various sensors attached to it. It is imperative that the state of the environment, as perceived by the controlling system, be consistent with the actual state of the environment. Otherwise, the effects of the controlling systems' activities may be disastrous. Hence, periodic monitoring of the environment as well as timely processing of the sensed information is necessary.

Timing correctness requirements in a real-time system also arise because of the physical impact of the controlling systems' activities upon its environment. For example, if the computer controlling a robot does not command it to stop or turn in time, the robot might collide with another object on the factory floor. Needless to say, such a mishap can result in a major catastrophe.

Real-time systems span many application areas. In addition to automated factories, applications can be found in avionics, undersea exploration, process control, robot and vision systems, as well as military applications such as command and control. The complexity of real-time systems also spans the gamut from very simple control of laboratory experiments, to process control applications, to very complicated projects such as the space station.

In most of these systems, activities that have to occur in a timely fashion coexist with those that are not time-critical. An accounting application or a long-term planning activity running on an automated factory's computer is an example of the latter. [Another example of that same kind is, the automatic gear box control task in dumper trucks which coexists with tasks controlling windshield wipers and the status panel. Ed.] Let's call both types of activities tasks and a task with a timeliness requirement a real-time task. In the literature real-time tasks are sometimes called time-critical tasks. Ideally, the computer should execute time-critical tasks so that each task meets its deadline, and it should execute the non time-critical tasks so as to minimize their average response time. One of the difficulties of designing a real-time system is meeting the requirements of individual time-critical requirements. Other issues include fault tolerance and the need to operate in uncertain environments. However, in the reminder of this introduction we concentrate on the timing issue, as it permeates all systems and environment issues.

Timing constraints for tasks can be arbitrarily complicated but the most common timing constraints for tasks are either periodic or aperiodic. An aperiodic task has a deadline by which it must finish or start, or it may have a constraint on both start and finish times. In the case of a periodic task, a period might mean "once per period T" or "exactly T units apart".

Low-level application tasks, such as those that process information from sensors or those that activate elements in the environment, typically have stringent timing constraints dictated by the environments physical characteristics. Most sensory processing is periodic. For example, a radar that tracks flights produces data at fixed rate. A temperature monitor of a nuclear reactor core should be read periodically to detect any changes promptly. Some of these periodic tasks may exist from the of of system initialization, while others may come into existence dynamically. A reactor's temperature monitor is an instance of a permanent task. An example of a dynamically created task is a (periodic) task that monitors a particular flight; the task begins when the aircraft enters an air traffic control region and ends when the aircraft leaves the region.

More complex types of timing constraints also occur. For example, spray painting a car on a moving conveyor band must be started after time t₁ and completed before time t₂. Aperiodic requirements can arise from dynamic events, such as an object falling in front of a moving robot or a human operator pushing a button on a console. [I.e. an interrupt. Ed.]

In addition, time-related requirements may also be specified in indirect terms. For example, a value may be attached to the completion of each task where the value may increase or decrease with time; or a value may be placed on the quality of an answer whereby an inexact but fast answer might be considered more valuable than a slow but accurate answer. In other situations, missing X deadlines might be tolerated, but missing X + 1 deadlines cannot be tolerated.

This brings us to the question of what happens when timing constraints are not met. The answer depends, for the most part, on the type of application. Needless to say, a real-time system that controls a nuclear power plant or one that controls a missile, cannot [ever] afford to miss timing constraints of the critical tasks. Resources needed for critical tasks in such systems have to be preallocated so that the tasks can execute without delay. Many situations, however, offer some leeway. For example, on an automated factory floor, if a system estimates that the correct command to a robot cannot be generated on time, it may be appropriate to command the robot to stop (provided it will not cause other moving objects to collide with it and cause a different type of disaster). This is an instance of a real-time task producing a lower quality result, but on time. In the case of a periodic task monitoring an aircraft, depending on the aircrafts trajectory, missing the processing of one or two radar readings may not cause any problems.

In summary, real-time systems differ from traditional systems in that deadlines or other explicit timing constraints are attached to tasks, the systems are in a position to make compromises, and faults including timing faults may cause catastrophic consequences. This implies that, unlike many systems which separate correctness and performance, real-time systems tightly interrelate correctness and performance. Thus, real-time systems solve the problem of missing deadlines in ways specific to the requirements of the target application. The sooner a system determines it will miss a deadline, the more flexibility it will have in dealing with the exception.

In addition to timing constraints, a task can have the following types of constraints and requirements.

• Resource constraints. A task may require access to certain resources other that the CPU such as I/O devices, data structures, files and databases.
• Precedence relationships. A complex task (for example, one requiring access to many resources) is better handled by breaking it up into multiple subtasks related by precedence constraints and each requiring a subset of the resources.
• Concurrency constraints. Tasks should be allowed concurrent access to resources providing the consistency of the resource is not violated.
• Communication requirements. Tasks should be allowed concurrent access to resources providing the consistency of the resources.
• Placement constraints. When multiple instances of a task are executed for fault-tolerance, the different instances should be executed on different processors.
• Criticalness. Depending on the functionality of a task, meeting the deadline of one task may be considered more critical than another. For example, a task that reacts to an emergency situation, such as fire on the factory floor, probably will be more critical than the task that controls the movements of a robot under normal operating conditions.

Characteristics of the various application tasks are usually known a priori [i.e. before hand] and may be scheduled to statically or dynamically. Whereas static specification of schedules is typically the case for periodic tasks, the opposite is true for aperiodic tasks. When the temperature monitor a nuclear reactor senses a problem in the core, it can invoke another (aperiodic) task to activate the appropriate elements of the reactor to correct the problem - for example, to force more coolant into the reactor core. In this case, the deadline for the aperiodic task can be statically set depending on the physical characteristics of the reactions within the core. On the other hand, the deadline of a task that controls a robot in a factory floor can be determined dynamically, depending on the speed and direction of the robot. The command to the robot forcing it to turn right, left, or stop should be generated before this time.

In a static system, the characteristics of the controlled system are assumed to be known a priori, and hence the nature of activities and the sequence in which they take place can be determined off-line before the system begins operation.Needless to say, such systems are quite inflexible event though they may incur lower run-time overheads. In practice, most applications involve several components that can be statically specified along with many dynamic components. If handled appropriately, a system with high resource utilization and low overheads can be produced for such applications.

Whereas a large portion of currently implemented real-time systems are static in nature, by necessity, next-generation systems will be large and complex and they will function in environments that are dynamic and physically distributed. More importantly, they will have to be maintainable and extensible due to their evolving and projected long lifetimes.

Because of these characteristics, real-time systems in general, and systems with the above characteristics in particular, need to be fast and predictable, reliable and adaptive.

A popular misconception about real-time computing is that these systems only need to be fast. The article "Misconceptions About Real-Time Computing", discusses this and other misconceptions. Speed is necessary, but it is not enough. A system has to be fast and predictable. Predictability has many meanings. (See the article "What is Predictability for Real-Time Systems?") For now, let's define predictability as the ability to determine a task's completion time with certainty. This must be done taking into account the state of the system (including the state of the operating system and the state of the resources controlled by the operating system) and the task's resource needs. For a system with predictability, given a particular situation, the question "Will task T meet its timing requirements?" is answerable. Other possible questions are:

• How many tasks will complete before their deadline?
• What will be the maximum utilization of a given resource?
• When will a task complete?

Reliability is a prerequisite for real-time systems. real-time constraints cannot be achieved if system components are not reliable. The level of reliability should be specifiable and predictability will involve determining system performance under different levels of reliability.

A real-time system should be adaptive to changes in

• system state, that is, system dynamics including overloads and failures (short-term),
• system configuration (long-term), and
• input specifications, in particular, task specifications (long-term).

Adaptability is particularly important for real-time systems because if a task's deadlines can be met only under a restricted system state and and configuration, reliability and performance may be compromised. If a system is adaptive, one does not have to redefine the system or recompute resource and task allocation for every small change. This reduces development and maintenance costs. To be predictable and adaptive at the same time we need carefully designed schemes. Maintainability and expandability follow from being adaptive. A real-time system's timing properties, specifically task execution times, are very tightly related to the system's hardware; thus the logical functions are often bound to the hardware early in the design process. The point at which this binding occurs, in part determines the system's adaptability and predictability.

Clearly, design and implementation strategies adopted will vary depending on the complexity of a controlled system, the static versus dynamic nature of the activities of the environment, the complexity of the tasks executed by the controlling system, and the system's goals.

...

Interesting Links for Further Reading

• Strategic Directions in Computing Research - Real-Time Working Group.
• Real-Time and Embedded Systems. Report from the Real-Time Working Group.
• What is Predictability for Real-Time Systems?, John A. Stankovic and Krithi Ramamritham -93
• Misconceptions About Real-Time Computing, John A. Stankovic -88
• The Time-Triggered Model of Computation, Hermann Kopetz -98