What exactly is meant by real-time? [Note: more work on this page needed]
Definitions:
Please note that EmbeddedSystems engineers use exactly one definition of real time, and that is this: A real time system employs tasks which execute to completion in a guaranteed amount of time.
This is how real time systems can determine latency and predictive behavior. Without the constraint of completion to schedule no other aspect of a real time system can be predicted reliably. It has nothing to do with speed, nor synchronization to a clock, nor any of the other drivel you will hear from people who don't really know real time systems. Stuff has to get done on time, otherwise you don't have a real time system.
Among the less-than-knowledgeable the topic is controversial and definitions of real time may be contradictory, hazy, incomplete, and unhelpful.
PosixStandard
POSIX Standard 1003.1 defines "real-time" for operating systems as: "the ability of the operating system to provide a required level of service in a bounded response time."
Real-Time versus Interactive
I'm no expert on this, but I believe this to mean that certain events have to be handled within certain strict time limits like streaming video fast enough to refresh the display 60 times per second or responding to an interrupt within a certain amount of time (and never going over the limit).
-- AlastairBridgewater
More on delay and wait times
This is the definition I encounter often. It has nothing to do with total throughput per time period, but that the max processing for any given request is known. Most "on-line" systems probably would not qualify because occasionally things like web servers and RDBMS do garbage collection, which may cause a few customers to wait for a little bit.
But something like a nuclear missile cannot stop to wait for garbage collection; it has to have a result by a predetermined time, or (hopefully) trigger a self-destruct.
3 general categories of response expectations:
- Batch
- Interactive
- Real-time
Intermix of RealTime with Interactive
- People tend to intermix "real-time" and "interactive", but they are not really the same thing. Interactive tends to focus on average turn-around time while real-time focuses on maximum allowed turn-around time.
Are things treated within Time Limits
RealTime?
- Some consider payroll to be real-time since it falls within the definition of handling events with strict time limits. Payroll does allow for human intervention within the time limit so others may exclude it.
Comparisons to language
- Some consider FORTRAN 77 to be an object-oriented language... Real-time payroll seems unlikely for most definitions of "real-time" and "payroll".
- The comparison seems out of place. Why unlikely? If payroll happens every two weeks, and it must take less than two weeks to process data and print checks, then it sounds like it fits a fair definition of RealTime.''
- A two-week payroll would define a kind of real-time "problem", but one would be unlikely to apply RealTime design methods to the problem. Typical RealTime design is very concerned with predictable or guaranteed response time, and may even sacrifice some normal response speed in order to handle the worst case within a deadline. For instance, a RealTime approach might guarantee that no single payroll item takes longer than 20 seconds to process, but the guaranteed algorithms may raise the average processing time by several seconds. (One might use a mostly-slower sorting algorithm with better worst-case behavior, or other worst-case optimizations.) Over long time periods one may do better by optimizing the average case rather than the RealTime worst case.
- suggests another definition of real-time which avoids the pitfalls of the previous definitions. A system is real-time if its design requires optimizing for worst-case instead of average case.
- It seems to me that real-time refers to at least three different things:''
- criteria to apply real-time.
- essence of real-time.
- techniques of real-time. (RealTimeTechniques)
- ''Definitions of the form "there are at least N constraints of M degree" are obviously flawed when put so crassly. Which is probably why all the ones above are so fuzzy.
RealTime constraints
- All fully automated systems have constraints. That two weeks in the payroll system won't sound very long if you have to hire someone to fly to Uzbekistan to fix it manually, let alone launch a space shuttle to fix your space probe. Whether it's a nanosecond or the lifetime of the universe, the scale of time is irrelevant to the essence of real-time.
- The severity of constraints are dependent on the state of technology, so the scale of time matters in that sense.
Qualities of the definition
- Any definition of real-time must reflect facts without needing to be modified every time technology changes.
- Any good definition must not be fuzzy.
Weather prediction example
- Weather prediction is another one. If it takes you more than 24 hours to predict tomorrow's weather, you've failed. (Actually, there is a lot of interest in slow prediction algorithms - many of them can be either parallelized (as fast as you can pay for), or will become feasible in a few computing generations/years.)
Brain and its
RealTime system capabilities and function
- A friend and I were having an interesting discussion (to us, anyway) about the human brain and its RealTime system capabilities.
- Stomach churning example
- Have you ever thought about how your breathing, circulation, digestion, etc. has the higher priority when compared with conscious thought? It's somewhat humbling to realize that all conscious thought runs at a much lower priority than stomach churning, for example. I.e., you cannot stop your stomach churning in favor of utilizing more brain processing power for conscious thought. Though perhaps this is a bad example. Stomach churning is an autonomous function and there are neurons in the gut devoted to this task. All autonomous functions have neurons dedicated to those tasks.
- As with most psychological and physiological things, there almost always exist contradictions. I know for a fact that I have (several times, to my embarrassment) 'forgotten' to breathe when I was thinking really hard. A few times I ended up passing out (briefly - collapsing on the table or keyboard has a tendency to wake me back up). It isn't as though I normally have to think about breathing, but I have to do so when I'm thinking really hard.
Conscious thought priorities
MarkAndSweep collection and pausing
- RealTime systems tend to be built in terms of short pauses - a MarkAndSweep GarbageCollector is not RealTime, as it may lead to pauses of hundreds of milliseconds, whereas a ReferenceCounting collector might be, as it can keep the pauses down to a few hundred cycles (IBM's ReCycler collector is an example of this).
- A MarkAndSweep collector can work in a real-time system if the worst-case collection time is acceptable. "Real-time" does not require "short" pauses or "fast" response time - it only requires that time constraints be met. Pauses of several seconds, minutes, hours, or even days can be acceptable in some real-time systems.
- References
Cynical Definition
- A Whiz Bang word applied to systems, most of which do not deserve the term. My system has more WhizBang? than yours because mine handles RealTime constraints under XX [milliseconds|nanoseconds] with only YY hardware, and because I'm so clever I made it fly.
Abstract vs Ad hoc definitions
- A person who designs a real-time system that delivers results in less than one year, is not going to be taken to have designed a realtime system, even if in fact, he has. Thus there are both abstract and ad hoc usages for this word, the ad hoc one is more meaningful and useful than the abstract one, in daily professional use. Note that a person who designed all the realtime constraints out of his system might actually end up with a better product. Being Realtime doesn't make it better. Witness all the marketing for RealtimeOperatingSystems?, the snake oil of the software business, where the lowest context switch is king, and where people will pay millions of dollars for a few hundred lines of assembler code. Maybe we're assuming a problem needs solving when in fact sometimes, it needs avoiding? WPostma.
Really fast
- One of the tools I used years ago had a realtime version, and the tutorial had a neat story: Several developers were discussing realtime software, and each was telling how their application was so macho realtime. Then a woman spoke, describing her app - the sensor pod that hung at the end of a metal beam, the other end which contained the atomic bomb. The pod handled telemetry on the blast, which had to be collected and transmitted up the wire ahead of the shockwave that vaporized the wire. She won.
- Hmm . . . shockwaves cannot vaporize metal - that requires heat.
- While not a nuclear physicist, I imagine that the actual physical shockwave of a nearby atomic bomb blast will sufficiantly disassociate the atoms of a cable as effectively as heat, and the radiant flux of the blast will provide much heat.
BugFree
?
There seems to be some confusion here between
- situations that require a response from the computer within some fixed desired time ("real-time environments").
- software that is written such that it will always respond (worst-case) in some maximum actual worst-case time ("real-time software").
Clearly, if we have a real-time situation, then we need real-time software.
On the other hand, we could use that *same* software in other situations that don't need all that capability. Is it still a RealTimeOperatingSystem if I don't use it in a real-time environment?
If we are writing software for a real-time environment, and we follow the principle of OptimizeLater, we start writing code that logically produces the right results. Then we analyze the worst-case response time of our code. If the worst-case is infinity (such as when there are loops that hang indefinitely waiting for some input), we use some RealTimeTechniques to bound the worst-case time, converting our software from non-real-time to real-time software. If the worst-case time is still longer than the desired time, we keep applying OptimizationPatterns? and other RealTimeTechniques (such as "optimize the worst case, not the common case") to improve things until it works.
Well, at least that's the most common process. The really *smart* people convert the real-time environment into a non-real-time-environment, so that the software merely has to usually respond in a reasonable amount of time. (Is there already a WikiPage about this - something like SimplifyTheRequirements? ForthValues?)
Typically this is done by giving the CPU only non-real-time tasks, and somehow handling all other tasks (or at least the crucial real-time parts of them) in external hardware.
The external hardware can be as simple as hardware limit switches,
or as complicated as dedicated peripheral microcontrollers.
(It seems counter-intuitive that the big, expensive, central CPU is doing only the "non-critical" non-real-time stuff, while the cheap microcontrollers and simple hardware do all the critical real-time stuff).
In most of the systems I've worked on it hasn't been practical to do this, because the hard real-time part is too complicated (or needs to be changed too often) for hardware. Instead, there is a pattern that almost always works:
- first meet all safety requirements using hardware
- minimize the set of remaining operations that have to be hard real-time, and then move those into a handler that runs on a periodic interrupt (or by an EventLoop? in a high-priority task). The handler usually does:
read inputs
process inputs, preferably in constant time
write outputs
[optional] process a message from soft/non-realtime program in bounded time
This is the MessagePassingConcurrency variant; an alternative is to replace the message processing with a shared parameter area. Either way, I normally use WaitFreeSynchronization (the same library for all projects, since it's not application-dependent at all) to implement a single-message queue or control updates to the parameter area; this allows the periodic interrupt to pre-empt the rest of the program unconditionally, so it's not strictly necessary to have a RealTimeOperatingSystem as such. -- DavidSarahHopwood
Sometimes adding such "extra" hardware is less expensive and uses less power than trying to get the CPU to do everything with a minimum of external hardware (for example, see "Indoor GPS" article by Frank van Diggelen, Charles Abraham, 2001 http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id=3053 ). Perhaps this is related to RidiculousSimplicityGivesRidiculousResources.
A mousetrap is a RealTimeSystem? utilizing hardware even cheaper than cheap microcontrollers.
On page WhichColorOfiMac, someone claims However... pre-emptive multitasking is not always a boon. MacOsClassic was used widely within the music industry for sequencing and synthesis because the cooperative multitasking allows very predictable real-time behaviour. Unless MacOsx supports some form of real-time scheduling, musicians could well be tempted to move over to another platform.
This seems totally backwards to me. I thought pre-emptive multitasking gave very predictable real-time behavior, at least compared to cooperative multitasking.
Is this just a typo, or is there some reason cooperative is better than pre-emptive?
-- DavidCary
In the hard real-time environment, absolutely cooperative is better than pre-emptive. In a pre-emptive system, no process knows when it will be paged out, nor how long it will be out for. In a cooperative system, each process has the responsibility for using only as much time as they are given, but they know they will not be interrupted.
Multi-tasking is complex, and that complexity has to go somewhere. Giving it to the operating system and relinquishing control completely makes the programmer's life easier, but makes your life more of an adventure. Keeping control requires you to handle some of the complexity, but lets you know you won't be interrupted.
Cooperative becomes a nightmare when there is a rogue process, and that's why most people are willing to give up the control.
PS: Most people don't actually know what the terms mean. Make sure you have the same definition in your mind as others have in theirs.
Uh, no. Most developers of hard realtime systems consider a hard, realtime pre-emptive kernel to be a necessity for many real-time applications. Note that real-time operating systems (such as VxWorks) have distinctly different characteristics that desktop/server OS's, among them:
- Simple, fixed, priority based scheduler. The highest priority task that is ready to run gets the CPU, period. Desktop/server OS's use various "fair" scheduling techniques to ensure that no process/thread gets starved (denied a chance to run). In real-time systems, starvation is not considered an issue.
- Guaranteed upper bounds for both interrupt latency (the time it takes to service a processor interrupt; including any time the kernel may spend in critical sections with interrupts masked), and for task switch latency (the time it takes for the kernel to switch between tasks; important when a high-priority task becomes unblocked. This includes any time the kernel may spend in critical sections with pre-emption disabled.
- Many real-time systems lack virtual memory; given the rather unpredictable latencies involved in disk I/O. Other desktop/server features often disabled in real-time systems include virtual address translation (fetching translation lookaside buffers can add unpredictable and/or excessive latency), and even (in extreme cases) the processor's cache (a series of cache misses may cause latency requirements to be violated). It is important to remember the realtime is not about fast (or about throughput), but about deterministic and predictable.
Cooperative multitasking is rather lousy at ensuring that the software can respond to an external stimulus within a bounded amount of time (except for the simple case where the processor is in a tight loop with bounded cycle time; and can poll the hardware on a sufficient basis; this is common in many
DigitalSignalProcessor applications which are "realtime" in the sense that they have to process incoming datastreams without dropping data).
-- ScottJohnson
To Scott's list, I'd add rate-monotone scheduling, plus a requirement for some mechanism to mitigate priority inversion - at least if tasks of different priority can share resources. -- KevinKenny?
Also note that Scott talks about systems such as DSPs, where each task has a limited amount of work to do to ensure that it executes to completion before the next external event happens. Many microcontroller real time systems are designed this way to make use of a simple time-based task dispatcher scheme that runs tasks according to a schedule. As long as the work load for each task is limited to what can be completed in its allocated time slot then the overall latency and predictability of the system remains intact.
RealTime, n. Here and now, as opposed to FakeTime, which occurs there and then.
See: OperationalReasoning, NearRealTime (a pseudo-discussion)
CategoryRealTime
Real Time