What is "real-time"?
Bob Kitzberger
>I've given definitions of "real-time" from three different English language
>dictionaries. Everyone seems to say that these are insufficient in a
>computer science context. However, no one has actually posted an alternate
>third-party definition of "real-time". I'll agree to use a formal definition
>as given by the FAQ of the comp.realtime group (sight unseen).
I've cross-posted this to comp.realtime (forgive me ;-). I've followed
many a thread on comp.realtime discussing this worn-out topic, but haven't
saved any of it.
Can anyone from comp.realtime post a pithy summary definition of
comp.realtime's "conclusions" on what is real-time?
.Bob.
----------------
Bob Kitzberger VisiCom Laboratories, Inc.
r...@visicom.com 10052 Mesa Ridge Court, San Diego CA 92121 USA
+1 619 457 2111 FAX +1 619 457 0888
Paul Sharkey
Having come from a control background, my definition of real-time
tends to rely on the task to be achieved. F'rinstance, many robotics
applications require different bandwidths for reasonable performance
and that bandwidth determines a sample rate (or vica versa). If that
sample rate can be achieved then that's real-time. Eg. a reactive
vision system uses ccd cameras as a sensor. These cameras are synched
at 25Hz. Thus if the vision algorithm can also run at 25 Hz then it is
called RT. On the other hand a process controller in a chemical plant
may have a time constant of minutes, if not hours/days. Patently the
controller need not run at 1kHz ;-)
Paul..
-------------------------------------------------------------------
Paul M Sharkey Office: +44 (0)865 273 150
Reactive Vision Laboratory Lab: +44 (0)865 273 168
Robotics Research Group Fax: +44 (0)865 273 908
Dept Engineering Science
Parks Road, Oxford OX1 3PJ Email: sha...@uk.ac.oxford.robots
Tim Chambers
> Can anyone from comp.realtime post a pithy summary definition of
> comp.realtime's "conclusions" on what is real-time?
Hi, Bob,
First I'll explain the approach which is used in our organization. Rather
than define "real-time" software, we break it into two categories:
"time-sensitive" and "time-critical." Time-sensitive software is that for
which there is some kind of continuous function (typically linear) for how
"well" the software does its job based on how fast it runs. A compiler is an
ideal example. The faster it runs, the "better" it is -- everyone *wants*
faster compile times.
Time-critical software uses a step function to define its quality -- it either
runs fast enough to do the job or it doesn't do the job. If the software
can't keep up with external stimulus it *ceases to function*. And running
faster doesn't necessarily improve the quality of time-critical software,
either (what quality improvement could a 68040 add to a Hayes-compatible
1200-baud modem, anyway, other than allowing the modem to run UNIX at the same
time :-).
To contrast the two, consider the software in a GUI. The software that moves
the sprite in response to mouse movements is more time-sensitive than
time-critical -- no one *wants* the sprite to lag behind mouse movements on a
window, but one can live with it. The time-critical aspect is in the data
acquisition as the mouse ball sends data up the I/O port to the computer.
So to draw a distinction between "real-time" software and non-real-time
software, we only consider the "time-critical" software to be in the former
category. "Real time systems" have a mix of time-sensitive and time-critical
software.
If you want other views, I've put a file on hpcsos.col.hp.com (15.255.240.16)
called pub/realtime.Z. It contains about 40 articles from comp.realtime that
I've collected over the years on this subject. Compressed it's 69Kb.
Uncompressed, it 3343 lines, 154Kb. I haven't read it all thoroughly enough
to summarize.
I don't think I've seen a FAQ for this newsgroup -- if there's interest, I'm
willing to compile one, starting with an answer to this question. Mail me
your votes and advice.
Tim Chambers || t...@col.hp.com
Hewlett-Packard Company ||
P.O. Box 2197 || (719) 590-5570 (office)
Colorado Springs, CO 80901-2197 || (719) 488-3345 (home)
|| FAX: (719) 590-5054
David M. Hansen
Many people will define a real-time system in terms of its execution speed,
e.g., "it must complete certain tasks before a deadline", or "an answer that is
late is the wrong answer." These definitions aren't bad, but they leave out
(what I consider) a critical component: an answer that's _early_ is just as
bad as one that's late. Imagine a program sending data to a modem one character at a time. If the program loads the (single-character, in this example)
transmit buffer _before_ transmission of the previous character has been
completed, the data is mangled and the program has failed. Similarly, when
receiving data, the program must react quickly enough to snatch each
character from the receive buffer before the next incoming character over-
writes it. Both components are critical.
A better definition, I think (this is not original BTW), is that a real-time
system must _manage_ time as a resource. Certainly, it must meet all its
deadlines (I imagine that word has an interesting etymology), but also it
must delay taking action on a calculation if that calculation completes before
its answer is required.
-=Dave
David C. Navas
>vision system uses ccd cameras as a sensor. These cameras are synched
>at 25Hz. Thus if the vision algorithm can also run at 25 Hz then it is
>called RT. On the other hand a process controller in a chemical plant
Hmm, I offer these as humble beginnings: [Go easy, my first time here... ;)]
Real-time:
A characteristic of the responsiveness of a system model. Often used to
describe a model whose worst-case response to its inputs is as fast, or
faster, than the system it is modeling, or, alternatively, a model that
can update or change its outputs as fast as its inputs may allow or require.
The following two capture some of what I feel is the right zen, but seem to
imply things which are not true:
A system whose response-time is limited only by the sampling frequency of it
inputs and the required sample frequency of its outputs.
[That -seemed- to imply linear response charactersitics, whereas real-time is
more like a bounded-response time, so....]
A system which, given any known stimulus and input-state, will produce a
known output and output-state within a maximum-time threshhold.
[Unfortunately, any finite-state Turing machine which does not get stuck in
an infinite loop, and is provided a finite input state [err, halts], will
achieve its output in a maximum bounded time. However, the bounds seem
to grow worse than exponential.... If I remember from theory class, anyway.]
Anybody else?
--
David Navas ja...@netcom.com
Co-author of: Web Data Acq. and Anal. dna...@oracle.com
Upcoming products: Shadow V, Jazzbench 2.0.
Michael A. Whelan
meet the deadlines of the application domain for a response. The key is
deadline or response time guarantee. As long as an acceptable response
is made by the deadline, then it operates in real-time. If by
deterministic you mean ability to meet deadlines than I agree.
If however you mean the response is exactly the same, i.e. can be
determined for every case than I must disagree. Since we are found of
using missiles and pilots, imagine what a pilot would think of a missile
avoidance system that responded deterministically. The first it might
work great, the second time it might be okay. The third time the
aircraft does not return. The reason is the responses were
deterministic. Even to the guy shooting. Again, the key is meeting a
response time requirement for the application domain, not a fully
deterministic system.
P.S. My wife operates in real-time, but I truly believe she is not
deterministic!
Mike Whelan
Mike Palmer
You definition is "interesting", but I'm not sure it's a definition that
instantly says to someone who does not understand real-time, "Oh yes, now
I see!".
Regards, Encore Computer Corporation
Mike palmer 6901 W Sunrise Boulevard
90 Layered Software Development Fort Lauderdale, Fl 33313
email: mpa...@encore.com Telephone: (305) 797-2326
Sean Case
>A better definition, I think (this is not original BTW), is that a
>real-time system must _manage_ time as a resource.
This is the definition I've been working towards for some time.
Do you have a reference for it?
>Certainly, it must meet all its deadlines (I imagine that word has
>an interesting etymology), but also it must delay taking action on
>a calculation if that calculation completes before its answer is
>required.
More generally, it must perform calculations taking into account the
time elapsed since its inputs were valid and the time that will elapse
before its outputs are used.
Consider a radar tracking system: it has a position for an object at
some point in the past, and must calculate where to look for it the
next time around.
Now, one way to improve management of any resource is to use less,
and speed does help. But a fast system that thinks it's infinitely
fast is often less useful than a somewhat slower one that properly
accounts for its own usage of time. Ideally, we'd like a fast system
with proper time management, but this seems to be beyond the
capabilities of most contractors...
(Off the top of my head, a deadline was originally a line around a
prison beyond which the guards could shoot to kill. I think.)
Sean Case
--
Sean Case g...@coombs.anu.edu.au
"[...] if a poststructuralist doesn't get you,
a deconstructionist will."--Ursula K. LeGuin
Don Gillies
a function of the logical correctness of the program itself, but also
a function of the time at which inputs are read and answers are
produced. There are an infinite number of ways to specify timing
constraints on a computation; deadlines are just one of many ways.
For examples, here are some other ways:
temporal constraints -- the computation values are not allowed
to become "stale", i.e. the input from a previous computation will
become stale and useless and must be acted upon by the next
computation before the values are stale. Sensors typically provide
temporal data.
distance constraints -- minumum or maximum distance between
two computations must be maintained. These can minimize response time
in a process like a keyboard-polling process. periodic constraints
are not an efficient way to do this. For instance, if you want to
poll the keyboard every 50 milliseconds, you need a 25 millisecond
period (just in case a polling task executes at the start of period
#n, and the end of period #(n+1)). But with distance constraints you
can specify a relative maximum separation of 50 milliseconds between
task 1 and task 2. This can reduce system load by 50%.
timing constraints -- these are the traditional types of
constraints, such as release-times, deadlines, and periods (for
--
David B Stewart
>First I'll explain the approach which is used in our organization. Rather
>than define "real-time" software, we break it into two categories:
>"time-sensitive" and "time-critical." Time-sensitive software is that for
Isn't that the same as "soft real-time" vs. "hard real-time"? Why do you offer
new terminology for the same old categories? The definition of real-time is
confusing enough as it is, without a proliferation of terminology!
~dave
-------------------------------------------------------------------------------
David B. Stewart - email: <dste...@cmu.edu> The Robotics Institute
snail mail: - ECE Dept., Carnegie Mellon University, Pittsburgh, PA 15213
Current Projects: - Chimera 3.0 Real-Time Operating System
- Reconfigurable Sensor-Based Control Systems
Hossein Moiin
and published by IEEE. As previously mentioned a real-time system is
a system for which the correctness of result not only depends on the
logical correctness but also on the time at which the results are
produced. This is a very general and vague and correct defenition.
I have a question though for those of you who are academically inclined.
What is real about real-time? What does the word real imply in the
definition of real-time systems? I have wondered about this and I think
that I saw a paper of the same title some time ago. I was wondering if
the real in real-time means that time-axis is treated as a real axis.
Your response will be appreciated.
--Hossein Moiin
Daniel Wengelin
>First I'll explain the approach which is used in our organization. Rather
>than define "real-time" software, we break it into two categories:
>"time-sensitive" and "time-critical." Time-sensitive software is that for
It somehow appears as if "time-sensitive" is rather irrelevant. I cannot
remember that I've ever seen a program that is not "time-sensitive"
according to the proposed definition. And if all programs are "time-
sensitive", and some programs are also "time-critical", then this
distinction is of little use.
I agree on the definition on the theme "a real-time task is a task whose
correctness rely on time constraints". I also find it probable that most
systems is a mix of real-time and other tasks.
The distinction between "hard" and "soft" real-time is obscure to me. I
see two different explainations. 1) "Hard" real-time has fixed deadlines
while "soft" has statistical time constraints. 2) "Hard" real-time
systems are bought by someone that considers the proof of rate-monotonic
scheduling as magic ;) , and wants to see the scheduling of tasks in
a timing diagram, while "soft" real-time systems are ordered by a
customer that is satisfied if the system meets its deadlines, no matter
when in the allowed time-frame an individual task executes.
The latter explaination puts the classification of "hard" or "soft"
in the eye of the beholder (customer) rather than in the system itself.
Daniel W.
-- The above is my personal opinion
-----------------------------------------------------------------------
-- --
-- Daniel Wengelin --
-- NobelTech AB (Winner of the -92 Ada Industry Leadership Award) --
-- Naval Systems Division --
-----------------------------------------------------------------------
David M. Hansen
|> han...@micro.cs.umn.edu (David M. Hansen) writes:
|>
|> >A better definition, I think (this is not original BTW), is that a
|> >real-time system must _manage_ time as a resource.
|>
|> This is the definition I've been working towards for some time.
|> Do you have a reference for it?
Unfortunately, no, I don't. To be honest, at the time I read this, I
didn't much like it, although it did stick in my mind. I believe I read it
in Computer Language magazine about three years ago, and I believe it was
P. J. Plauger who wrote it, but I'm far from certain on either count.
|>
|> >Certainly, it must meet all its deadlines (I imagine that word has
|> >an interesting etymology), but also it must delay taking action on
|> >a calculation if that calculation completes before its answer is
|> >required.
|>
|> More generally, it must perform calculations taking into account the
|> time elapsed since its inputs were valid and the time that will elapse
|> before its outputs are used.
|>
|> Consider a radar tracking system: it has a position for an object at
|> some point in the past, and must calculate where to look for it the
|> next time around.
Well put, I agree completely.
-=Dave
Subba Somanchi
|> Please refer to "Hard real-time systems" by Stankovic and Ramaritham
|> and published by IEEE. As previously mentioned a real-time system is
|> a system for which the correctness of result not only depends on the
|> logical correctness but also on the time at which the results are
|> produced. This is a very general and vague and correct defenition.
|>
|> I have a question though for those of you who are academically inclined.
|> What is real about real-time? What does the word real imply in the
|> definition of real-time systems? I have wondered about this and I think
|> that I saw a paper of the same title some time ago. I was wondering if
|> the real in real-time means that time-axis is treated as a real axis.
|> Your response will be appreciated.
|>
|> --Hossein Moiin
My intuitive understanding of a 'real-time computer system' was a system
in which the computation part does not introduce an additional delay into
its environment - i.e. the comp. sys. reacts with the environment when it
"should." Thus the 'operating time' of the system is REAL-(world)-time as
opposed to a 'simulated time'
am i way off on this?
- subba
--
/--------------------------------------------------------\
| ".sig-files are overrated" - old jungle saying |
\--------------------------------------------------------/
MILLS,JOHN M.
>In article <1992Oct16.2...@col.hp.com> t...@col.hp.com (Tim Chambers) writes:
>>First I'll explain the approach which is used in our organization. Rather
>>than define "real-time" software, we break it into two categories:
>>"time-sensitive" and "time-critical." Time-sensitive software is that for
[ deleted ... ]
We could fine-tune the definition of real-time software indefinitely, but I
would be interested in comments as to _how_ time constraints affect
software development, from requirements definition through testing.
My experience had been almost entirely in systems with interrupt-driven
response to time-critical (by T. Chambers' definition) conditions, and
usually to the time-sensitive activities as well, and a clear definition
of what activities were in which category. We are now working on a
three-processor, six-task radar controller written in XDAda; while I am
confident we can meet our [somewhat vague] task response targets, I
do not believe we dealt with speed requirements in an intelligent way
from the beginning of our project. We just said: "we can always use a
faster processor," and so forth, and _could_ have gotten hung, since
no clear interdependence of our tasks was expressed nor translated into
testable requirements.
This situation was aggravated by what appears to have been reluctance
on the part of our software designers to directly consider the computer-
or system-hardware performance and shortcomings in specifiying and
designing the software.
I write that in order to raise questions of method and approach, and
move the discussion onward from "changing 'glad's to 'happy's", as
one of my customers described a diminishing-returns editing situation. It
would also be nice if we avoided [for a few days] the evergreen threads:
"Why I love/hate Ada more/less than C++", and maybe
"Why I love/hate Ada tasking more/less than Unix." [;*>)
Regards --jmm--
--
John M. Mills, SRE; Georgia Tech/GTRI/TSDL, Atlanta, GA 30332
uucp: ...!{decvax,hplabs,ncar,purdue,rutgers}!gatech!prism!jm59
Internet: jm...@prism.gatech.edu
"f U cn rd dis, U mst uz Unix!!!" ...jaw
Ian Cunningham
attempt to highlight the need to handle the concurrancy problems. I am
not sure how to do this but I feel it should be part of the definition.
It is after all a vital piece of the puzzle.
IanC
Russell McFatter
>Real-time software does not have to be fully deterministic. It has to
>meet the deadlines of the application domain for a response. The key is
[...]
> The reason is the responses were
>deterministic. Even to the guy shooting. Again, the key is meeting a
>response time requirement for the application domain, not a fully
>deterministic system.
>
[...]
>
>Mike Whelan
>
No! When I said "deterministic", of course, I meant time-domain
determinism, not that the code produces the same output (responses) to
different input (stimuli)!
The other suggestions being bantered around ("must produce a result or act
on the data before the required deadline") are also weak, at best.
Put your own personal definitions of "real-time" through the following
quiz:
1: Is a system "real-time" if it completes processing input data
substantially faster than it did the same input on a previous "run",
EVEN THOUGH both attempts met the required "deadline"?
Answer: NO. As a real-time developer, you would be as concerned of
results coming back too early as you would of them coming back too
"late". Why? Because, theoretically, if the system completed the
processing "quickly" on the faster pass, something unrelated to
the system itself-- a total unknown-- delayed the "slow" pass. You
would be correct to worry that this unknown might cause you to
miss the deadline at some point in the future. (Obviously, conditions
known to the developer-- such as the presence or absence of higher-
priority tasks, can affect time-to-solution even though they are not
"unknowns").
2: Does a real-time system ALWAYS process input in the same
(deterministic) time?
Answer: NO. Many applications' performance depends on the kind or amount
of data being processed. The key is that the timing is, at least,
*predictable*. That way the designer knows that the system will meet
the specifications under all of the specified conditions.
3: Does real-time code always meet its deadlines?
Answer: NO. The deadlines are only guaranteed to be met when the work
meets the criteria that the real-time system is certified for. The
specifications may or may not say what is to be done if the deadlines
cannot be met. Your phone system, for example, is a real-time system
to a great extent-- at certain times. On "older" switches, for
example, your line was polled about ten times per second when your
phone was on the hook, to see if you had picked it up or not. After
picking up the phone, the system had to provide a dial tone within a
certain amount of time, at which point the line is scanned about
100 times per second for dial pulses/DTMF.
What if every phone on the switch is picked up at once? Well, that's
outside the specifications for "real-time" behavior, so the switch is
free to fall into some kind of backup strategy (resulting in very long
wait for dial tone, error tone or other message, or perhaps, if this
situation was not anticipated in the specs, a complete collapse of the
domestic dial network).
A real-time application might detect this kind of situation by
prequalifying the input ("Hmmm... I count 8 radar targets... I know
I can't handle that many in the time requirements, so take the first
6 and put up a warning to the operator"), or by an OS-supplied
scheduler feature. For example, a frame scheduler might provide two
different behaviors on frame overruns-- one preempts the process whose
frame has ended, thus preventing it from interfering with possibly
"more critical" processes in adjacent frames; or it might allow the
process to continue, but send it an "overrun" signal or interrupt
that it can use to somehow change its behavior ("I haven't been
counting radar targets, but I'm not meeting my deadline. I'll start
ignoring targets beyond a certain distance and will warn the
operator.")
4: Parts of a "real-time" system can be nondeterministic, but the results
can still be considered "real-time".
Answer: TRUE. Example: You have a fairly slow PC running a
bulletin-board system. Your *only* specification: The BBS must allow
1024-character typeahead at rates of up to 2400 baud, under all
circumstances. You collect a username and password, and then access
a floppy-disk to look up the user information. This might take
anywhere from 3 to 30 seconds, and is entirely nondeterministic;
meanwhile the user might be blasting away at a full 2400 baud.
HOWEVER: You implemented the serial connection using an interrupt
handler at a higher priority than the floppy drive; thus no characters
are lost (even though the floppy access might slow to a crawl). Your
BBS meets your own "real-time" criteria despite the fact that the
non-critical components are nondeterministic. Of course, if some other
interrupt is possible at a higher priority (say a mouse or other
external device), the system no longer meets the "real-time"
requirements. If you were requiring *unlimited* typeahead, the specs
would be a bit harder to meet.
If you're asking: How can this setup be considered "real-time" at
all? Suppose for the moment that the PC is receiving data once an hour
from a real-time system that has a deterministic time in which to
connect to the PC, transmit a username/password and some sort of data,
then disconnect (regardless of response from the PC) and get on with
its other work.
Simple "real-time" requirements can almost always be faked in hardware
(by passing off the task to some dedicated device that has nothing
"better" to do). Example: A terminal multiplexor. It has its own
buffer, does its own character echoing, and generally won't lose input
even if the main CPU takes a "long" time to get around to reading
from it. You can even bring the entire machine to a stop and the
multiplexor keeps on handling user input-- to a point...
ip00> mti: duart overrun (059004, -1):
5: A system is either clearly "real-time" or not, regardless of its
purpose.
Answer: FALSE. You might consider that there is a *scale* to real-time
events; a range of "legal" nondeterminism for a particular kind of
event to happen-- an allowable "plus or minus" that is still, for
"all practical purposes", deterministic. For example, no computer
system can be more time-deterministic than its own clock frequency allows
for. A credit-card authorization network might be documented to have
a deterministic response time of "8 seconds" for any successful
transaction, and "no more than 11 seconds" for any unsuccessful
one. It is reasonable to say that an "approved" response will never
happen in four seconds, or forty seconds, when the system is behaving
properly-- but, for the purposes intended (to not keep the customer
waiting), 8.1 seconds might be considered within the "deterministic"
window, and given the variable delay of the phone transmission itself,
the variation is unavoidable.
An additional note:
Be very careful when using the word "critical" to discuss real-time
systems and components, because the word has so many meanings. Example:
which of the following is more "critical"?
1: A task which controls firing of an automobile's spark plugs
2: A task which controls the Space Shuttle's brakes in response to
the pilot's controls
Well, in the first case, the misfiring of a spark plug probably won't
kill anyone. However, the *timing* is critical-- if off by even a tenth
of a second, the entire engine won't run (or could be irreversibly
damaged). On the shuttle, a delay of even two entire seconds in applying
the brakes would be unlikely to endanger the mission or anyone on it,
given the length of the runway. The real-time "scale" and the "failure
penalty" are entirely independent, even though the word "critical" is often
used to described both.
--- Russ McFatter [ru...@alliant.com]
std. disclaimers apply.
Peter Moylan
> definition of real-time systems? I have wondered about this and I think
> that I saw a paper of the same title some time ago. I was wondering if
> the real in real-time means that time-axis is treated as a real axis.
In the control systems community, there is a tradition of distinguishing
between real time and, for example, simulated time. This ties in with
the distinction between on-line and off-line algorithms. An off-line
calculation is one which can be done before the system starts running,
e.g. at the design stage. An on-line calculation is one which has to
be done while the system is running because it uses data from the
running system. Obviously, there's a relationship between "meeting
timing constraints" and "on-line", so to many control people think of
"on-line" and "real-time" as synonymous.
This is not precisely the way the real-time community thinks of things
these days, but I think it does explain the etymology. "Real time"
simply means genuine, actual, real time as measured by a clock. It
has nothing to do with the meaning of "real" when talking about
complex numbers.
I think that we're just now beginning to realise that the modern
definitions of "hard real-time" are broken, or at least that they're
irrelevant to real-time control. Any practical real-time system must
have some reasonable robustness properties, i.e. it should degrade
gracefully under conditions like a short-duration processor failure.
From this it seems to follow that a real-time system should not contain
any hard real-time deadlines.
Of course this does not destroy the usefulness of "hard real-time"
as a concept. We can continue to design our scheduling methods while
maintaining the fiction that deadlines can be met. We do, however,
have to recognise that these deadlines will not be met out in the
real world of power surges, sensor failures, and the like.
--
Peter Moylan ee...@wombat.newcastle.edu.au