Steve Furr on “What is Real-time?”
Sep 14, 1997 — by Rick Lehrbaum — from the LinuxDevices Archive — 2 viewsHere are Steve Furr's answers . . .
- What is real-time? — Real-time is a property of systems that is often misunderstood. I will attempt to provide a summary of some of the critical elements of real-time computing, but for a formal treatment of the issue with rigorous definition of the terms, I would strongly encourage visiting target=”_blank”>www.real-time.org.
Real-time is, correctly speaking, a property of systems where time literally is “of the essence”. In a real-time system, the value of a computation in the system is dependent on how timely the answer is. A computation that is completed late has a diminishing value, or no value whatsoever, and a computation completed early is of no extra value.
This property is always a matter of degree, since even batch computing systems have a real-time aspect to them — nobody wants to get their payroll deposit two weeks late! The problem arises when there is competition for resources in the system and resources are shared amongst many activities, which is where we begin to apply the real-time property to operating systems themselves.
In implementing any real-time system, a critical step in the process will be the determination of a schedule of the activities in the system such that all the activities will be completed on time.
The embodiment of a real-time system on a particular platform will comprise schedulable activities, that were accounted for in the schedule, non-schedulable activities, such as operating system facilities, other operating system activities and interrupt handlers, and non-real-time activities. If non-schedulable activities can execute in preference to schedulable activities, they will affect the ability of all of the timeliness constraints reflected in the schedule to be met.
- Who needs real-time? hard real-time? — The obvious answer here are the cases most often used for hard real-time. That is, systems where failure to perform activities in a timely manner can result in harm to persons or property.
Often overlooked, however, are situations where there is a need to meet quality of service (QoS) guarantees, particularly, where failure to meet them could result in financial penalty. This covers obvious situations, such as “thirty minutes or its free”, but it also includes intangible penalties, such as lost opportunities or loss of market share. For example, a consumer device aimed at presenting decoded MPEG data that depends on software for any part of the delivery of the content may experience dropped frames at a rate that is perceived by the customer as unacceptable.
In both cases, a subjective assessment must be made about whether the downside risk warrants the use of real-time technology, but a decision made early can have unforeseen consequences when overload of the deployed system leads to pathological behavior in which most or none of the activities complete on time, if at all.
- What is hard real-time? — Hard real-time is a property of the timeliness of a computation in the system. A hard real-time constraint in the system is one for which there is no value to a computation if it is late, and the effects of a late computation may be catastrophic to the system. A hard real-time system is then one where all of the activities have to be completed on time.
- What is soft real-time? — Soft real-time is a property of the timeliness of a computation where the value diminishes according to its tardiness. A soft real-time system can tolerate some late answers to soft real-time computations *as long as* the value hasn't diminished to zero. A soft real-time system will often carry meta requirements such as a stochastic model of acceptable frequency of late computations.
Note that this is very different to conventional applications of the term which don't account for how late a computation is completed or how frequently this may occur. This term is often improperly applied to operating systems that don't satisfy the necessary conditions for guaranteeing that computations can be completed on time. Such operating systems are best described as quasi-real-time or pseudo-real-time in that they execute real-time activities in preference to others whenever necessary, but don't adequately account for non-schedulable activities in the system.
- What is a hard real-time OS? — To the best of my knowledge an acceptable definition of what constitutes a hard real-time operating system has never been put forward. I propose a modest definition based on real-time scheduling theory that is consistent with industry practice.
The basic definition is that a hard real-time operating system must guarantee that a feasible schedule can be executed given sufficient computational capacity if external factors are discounted. External factors in this case are devices that may generate interrupts, including network interfaces that generate interrupts in response to network traffic. In other words, if a system designer controls the environment of the system, the operating system itself will not be the cause of any tardy computations.
We can apply this term to conventional operating systems — which typically execute tasks according to their priority — by referring to scheduling theory and deriving a minimum set of conditions that must be met. Without getting into too much detail, scheduling theory demonstrates that a schedule can be translated into static priority assignments in a way that guarantees timeliness. It does so by dividing the time available into periodic divisions and assuming a certain proportion of each division is reserved for particular real-time activities. In order to do so the following basic requirements must be met:
- Higher priority tasks always execute in preference to lower priority tasks
- Priority inversions, which may result when a higher priority task needs a resource allocated to a lower priority one, are bounded
- Non-schedulable activities including both non-real-time activities and operating system activities don't exceed the remaining capacity in any particular division.
Because of condition 3, we must discount those activities outside of the control of the operating system, yielding the external factors provision above. We can then derive the following OS requirements:- The OS must support fixed priority preemptive scheduling for tasks (both threads and processes as applicable).
- The OS must provide priority inheritance or priority ceiling emulation for synchronization primitives
- The OS kernel must be preemptable
- Interrupts must have a fixed upper bound on latency
4a. By extension nested interrupt support is required - Operating system services must execute at a priority determined by the client of the service
5a. All services on which it is dependent must inherit that priority
5b. Priority inversion avoidance must be applied to all shared resources used by the service.
Items 3 & 4 impose a fixed upper bound on the latency imposed on the onset of any particular real-time activity. Item 5 ensures that operating system services themselves — which are internal factors — don't introduce non-schedulable activities into the system that could violate basic requirement 3.Since the question is raised with regard to Linux systems a few observations are in order. There are two approaches commonly applied to Linux kernels: kernel modifications [i.e. scheduler patches, preemptability patches, etc.]; and a host kernel [i.e. RTLinux, RTAI, etc.].
The first approach addresses items 1 through 4 by altering the scheduling behavior of the kernel. The drawback to this approach is that it cannot address item 5. Item 5 cannot be satisfied without architectural changes which would have an impact on the frameworks in the kernel such as filesystem and driver interfaces, and a pervasive impact on filesystems and drivers themselves. For comparison one should consider the level of effort involved in creating an SMP capable version of Unix in System V Release 4.2.
The second approach provides a realtime operating system, but it is hard to consider a genuine “real-time Linux”, since only real-time activities executing within the host real-time kernel itself can be categorized as real-time and only so long as they have no dependencies on Linux services.
By contrast, the architecture used in QNX operating systems is designed to directly deal with all of these requirements in two key ways related to its microkernel architecture. Foremost is that all device drivers and operating system services apart from basic scheduling and inter-process communication (IPC) exist as separate processes within the system. The second is that all services are accessed through a synchronous message passing IPC mechanism that allows the receiver to inherit the priority of the client.
The priority inheritance scheme allows 5 to be met by carrying the priority of the original real-time activity into all service requests and subsequent device driver requests.
There is an attendant flexibility available as well. Since items 1 and 5 stress that device driver requests need to operate in priority order, at the priority of the client, throughput for normal operations can be substantially reduced. Using this model an operating service or device driver can be swapped out in favor of a real-time version that satisfies these requirements. Complex systems will generally partition such resources into real-time and non-real-time
with different service and device driver implementations for each resource. - What is a soft real-time OS? — A soft real-time OS must be capable of doing effectively everything that a hard real-time OS must do. In addition, a soft real-time OS must be capable of providing monitoring capabilities with accurate cost accounting on the tasks in the system to determine when activities have failed to complete on time or when they have exceeded their allocated CPU capacity, and trigger the appropriate response.
A third approach to real-time under Linux subverts the Linux scheduler by providing a kernel module that dynamically adjusts the task priorities used by the kernel for scheduling. At the same time, the kernel module monitors activities to catch overruns and deals with them.
Since this third approach deals directly with information derived from the original schedule, the API calls used for real-time necessarily differ from standard Linux calls. The approach does provide an acceptable level of soft real-time capability for many applications and demonstrates an exceptional adaptability to overload situations and bursty activity. It remains to be seen, however, how well it can be adapted to providing hard real-time capability in a Linux environment.
- How do you characterize real-time performance? — Real-time characterization is a genuine problem, since it focuses on the question “how fast?”, rather than “how timely?”. Interrupt latencies and context switching may be interesting in terms of overall computation capacity of the system, but in the absence of the ability of an OS to satisfy 5 or accurate information about the costs of OS facilities required by the application they are of no benefit at best, and misleading at worst.
A truly useful real-time characterization would provide a statement of conformance to 5, for each OS facility, and would provide best case, average case and worst case timings for all such facilities. In practice, however, this has proven impractical in the real world and users of the technology have made more practical use of their time with empirical testing of the behavior of their systems under load.
In terms of real-time performance, the real benefit of open source is that it allows many people to work together to generate such a characterization for the operating system, and examine its ability to meet the minimum sufficient conditions for real-time.
Author's bio: Steve Furr is a Senior Software Developer at QNX Software Systems, Ltd. QNX supplies a POSIX-compliant “hard real-time” operating system based on a proprietary (i.e. non-open source) microkernel.
This article was originally published on LinuxDevices.com and has been donated to the open source community by QuinStreet Inc. Please visit LinuxToday.com for up-to-date news and articles about Linux and open source.