Introduction

Real-time systems design is an increasingly important topic in systems research communities as well as the software industries. Real-time applications and their requirements can be found in almost every area of operating systems and networking research. An incomplete list of such domains includes distributed systems, embedded systems, network protocol processing, aircraft design, spacecraft design..., and the list goes on. This page is intended to give the reader a brief, however incomplete, introduction to the concept of real-time tasks and their implications in the design of operating systems.

Real-time Task Models

In order to understand the functions of a real-time system, it is necessary to develop models of real-time activities and study their characteristics. In this section, two fundamental real-time task models are described: periodic and aperiodic real-time tasks.

Periodic Real-time Tasks

In general, a real-time task requires a specified amount of particular resources during specified periods of time. A periodic task is a task that requests resources at time values representing a periodic function. That is, there is a continuous and deterministic pattern of time intervals between requests of a resource. In addition to this requirement, a real-time periodic task must complete processing by a specified deadline relative to the time that it acquires the processor (or some other resource).

For simplicity, assume that a real-time task has a constant request period (ie, must begin execution on the processor every n milliseconds). We can characterize such tasks as a tuple of values, (C, T), where T denotes the request period, which corresponds to the amount of time between temporally adjacent requests, and C represents the service time, or the amount of time for which the task must execute (in total) before a deadline, which is typically assumed to occur at the start of the next request period.

For example, a robotics application may consist of a number of periodic real-time tasks, which perform activities such as sensor data collection or regular network transmissions. Suppose the robot runs a task that must collect infrared sensor data to determine if a barrier is nearby at regular time intervals. If the configuration of this task requires that every 5 milliseconds it must complete 2 milliseconds of collecting and processing the sensor data, then the task is a periodic real-time task, and can be characterized in this model as the tuple: (C=2ms, T=5ms).

Aperiodic Real-time Tasks

The aperiodic real-time task model involves real-time activities that request a resource during non-deterministic request periods. There may either be no bound or only a statistical bound on the arrival period of individual requests (task instances). Each task instance is also associated with a specified deadline, which represents the time necessary for it to complete its execution.

Examples of aperiodic real-time tasks are found in event-driven real-time systems, such as ejection of a pilot seat when the command is given to the navigation system in a jet fighter. Many, less time-sensitive, applications also arise in distributed systems involving real-time streaming media (ie, end-host routing over a logical overlay).

Real-time Scheduling

One of the most important responsibilities of a real-time system is to schedule tasks according to their deadlines in order to guarantee that all real-time activities achieve the required service level. Many scheduling algorithms exist for a variety of task models, but fundamental to many of these are the earliest deadline first (EDF) and rate-monotonic (RM) scheduling policies. A schedule for a set of tasks is said to be feasible if a proof exists that every task instance in the set will complete processing by its associated deadline. Also, a task set is schedulable if there exists a feasible schedule for the set. The utilization associated with a given task schedule and resource (ie, CPU) is the fraction of time that the resource is allocated over the time that the scheduler is active.

Earliest Deadline First

The EDF scheduling algorithm is a preemptive and dynamic priority scheduler that executes tasks in order of the time remaining before their corresponding deadlines. Tasks with the least time remaining before their deadline are executed before tasks with more remaining time. At each invocation of the scheduler, the remaining time is calculated for each waiting task, and the task with the least remaining time is dispatched. If a task set is schedulable, the EDF algorithm results in a schedule that achieves optimal resource utilization. However, EDF is shown to be unpredictable if the required utilization exceeds 100%, known as an overload condition. EDF is useful for scheduling aperiodic tasks, since the dynamic priorities of tasks do not depend on the determinism of request periods.

Rate Monotonic

Recall the parameterization of a real-time periodic task as a tuple (C, T). Under the static-priority rate monotonic scheduling algorithm, tasks are ordered according to the value of their request period, T. Tasks with shorter request periods are assigned higher priority than those with longer periods. Liu and Layland proved that a feasible schedule is found under rate monotonic scheduling if the total requested utilization is less than or equal to ln(2), which is approximately 69.3%.

RM scheduling is optimal with respect to maximum utilization over all static-priority schedulers. However, this scheduling policy only supports tasks that fit the periodic task model, since priorities depend upon request periods. Because the request times of aperiodic tasks are not always predictable, these tasks are not supported by the RM algorithm, but are instead typically scheduled using a dynamic priority scheduler such as EDF.

Hard vs. Soft Real-time

The issue of predictability is of key concern in real-time systems. In fact, the term "predictable" can often be found in the multitude of definitions of real-time in the literature. Both periodic and aperiodic tasks have strict timing requirements in the form of deadlines. That is, the scheduler must be able to guarantee that each task is allocated a resource by a particular point in time, based on the task's parameters. In order to accomplish this, every allocation of any resource to any task must incur a latency that is deterministic or that can at least be predicted within a statistical margin of error.

Hard real-time tasks are required to meet all deadlines for every instance, and for these activities the failure to meet even a single deadline is considered catastrophic. Examples are found in flight navigation, automobile, and spacecraft systems. In contrast, soft real-time tasks allow for a statistical bound on the number of deadlines missed, or on the allowable lateness of completing processing for an instance in relation to a deadline. Soft real-time applications include media streaming in distributed systems and non-mission-ciritical tasks in control systems.

Real-time Networking

The growth in number of real-time distributed applications has fueled interest in methods for providing predictable communication-related services. Consider a wireless sensor network designed to locate injured civilians in disaster areas, or a networked application that allows a surgeon to control medical instruments from a distance. Many researchers are developing real-time network protocols and operating system mechanisms to ensure predictability of data distribution for such applications.

The real-time transport protocol (RTP) is a protocol based on UDP and is typically used in video/audio streaming applications in which there is a high tolerance for packet loss and low tolerance for delay variation. RTP is used in both multicast and unicast scenarios along with RTCP for transmission of control messages that carry quality feedback data.

Even if real-time networking protocols are employed, predictable service may not be possible unless end-host operating systems are equipped with appropriate mechanisms for processing incoming/outgoing network packets. These services typically dispatch event handlers in interrupt context in order to respond to events on the network, such as a packet received or ready for transmission. Systems such as RTLinux and RTAI, when used in conjunction with extensions like RTNet, provide deterministic timing guarantees on network packet processing and thus allow for real-time communication assuming that the low level network protocols in use are sufficiently predictable.

A Survey of Real-time Systems

The following is a list of some well-known real-time systems and links to more information:

QNX Neutrino Realtime Operating System
VxWorks RTOS
RTLinuxPro and RTLinuxFree at FSMLabs
RTAI - the RealTime Application Interface for Linux
Montavista Real-time Linux
Xenomai - Real-time framework for Linux
RTnet - Hard Real-Time Networking for Real-Time Linux

Conclusion

As real-time applications become ubiquitous in various areas of computing research, there is motivation to extend existing systems with the mechanisms and policies necessary for providing predictable service. Also, many new real-time task models are being investigated in order to devise suitable scheduling algorithms for these new applications. Computer scientists will continue to analyze these new methods and apply them in situations where predictability and timeliness is of key consideration. Real-time systems is a rich domain for further study and will most likely continue to thrive for years to come.