What is the purpose of this FAQ ?
The purpose of this FAQ is to give sufficient knowledge to a new user in the Real-Time field and to serve as a reference to the engineer working in this field. This FAQ gives an overview about each topic and refers to other ressources (Internet, Publications, Company) for a more complete information.
A companion posting to this one, “Comp.realtime: Welcome to comp.realtime” @message-id realtime_welcome@, complements this one by providing a concise introduction to the group. Another posting, “Comp.realtime: A list of real-time operating systems”, @message-id realtime_list@, provides references to available operating systems.
——————————
What is the charter of comp.realtime?
The charter of comp.realtime is to provide a forum for discussion of both the theory and practice of real-time computer systems. The group is unmoderated; participation is open to all.
[If there was a formal charter for the newsgroup at the time of its creation, we don’t have access to it at the moment. Readers?]
Note that the listing in the canonical “newsgroups” file is:
comp.realtime Issues related to real-time computing.
——————————
Where should I ask questions about real-time systems?
Comp.realtime is certainly the place. However, if you are asking about a particular real-time system, see below for a (possibly) better place to start.
For topics that are only somewhat related to real-time systems, also consider comp.arch and/or comp.os.misc. For instance, topics about bus-based computer systems are best asked in comp.arch, or, if they’re about the VMEbus, comp.arch.bus.vmebus.
——————————
What is considered good net.etiquette on comp.realtime?
Here are some etiquette reminders that will help us all to make the group an ever-friendlier place:
— Please, before posting, ensure that you’ve read the basic Usenet etiquette guide in news.announce.newusers.
— Please set the Followup-To: line in your post. This is especially true if you are cross-posting. If you are requesting information, consider setting:
Followup-To: poster, and then summarizing the replies to the net.
— When following up, please change the Subject: line if the subject has really changed.
— Some sites that receive comp.realtime are on branches of the net that frown on overtly commercial announcements. These postings are welcomed on comp.newprod and anywhere in the biz.* hierarchy. However, short offers by vendors to provide further information by email are usually seen as acceptable.
======================================================
II- DEFINITIONS
——————————
What exactly is meant by real-time?
There are _several_ definitions of real-time, most of them contradictory. Unfortunately the topic is controversial, and there doesn’t seem to be 100% agreement over the terminology.
1. The canonical definition of a real-time system , is the following:
“A real-time system is one in which the correctness of the computations not only depends upon the logical correctness of the computation but also upon the time at which the result is produced. If the timing constraints of the system are not met, system failure is said to have occurred.”
Others have added:
“Hence, it is essential that the timing constraints of the system are guaranteed to be met. Guaranteeing timing behavior requires that the system be predictable. It is also desirable that the system attain a high degree of utilization while satisfying the timing constraints of the system.”
A good example is a robot that has to pick up something from a conveyor belt. The piece is moving, and the robot has a small window to pick up the object. If the robot is late, the piece won’t be there anymore, and thus the job will have been done incorrectly, even though the robot went to the right place. If the robot is _early_, the piece won’t be there yet, and the robot may block it.
Another example is the servo loops in an airplane when on auto-pilot.
The sensors of the plane must continuously supply the control computer with proper measurements. If a measurement is missed, the performance of the airplane can degrade, sometimes to unacceptable levels.
David Sonnier adds the distinction:
In the robot example, it would be hard real time if the robot arriving late causes completely incorrect operation. It would be soft real time if the robot arriving late meant a loss of throughput. Much of what is done in real time programming is actually soft real time system. Good system design often implies a level of safe/correct behavior even if the computer system never completes the computation. So if the computer is only a little late, the system effects may be somewhat mitigated.
2. POSIX Standard 1003.1 defines “real-time” for operating systems as:
“Realtime in operating systems: the ability of the operating system to provide a required level of service in a bounded response time”
3. One will occasionally see references to “real-time” systems when what is meant is “on-line”, or “an interactive system with better response time than we used to have”. Often, this is just marketing hype. For instance, although some have queried whether running “rn” is real-time, it is not, as it is interacting with a human who can tolerate hundreds of milliseconds of delays without a problem. Similarly, on-line stock quotation systems interact with humans.
4. One will also see references to “real-time” systems when what is meant is just “fast”. It might be worth pointing out that “real-time” is not necessarily synonymous with “fast”; that is, it is not the latency of the response per se that is at issue (it could be of the order of seconds), but the fact that a bounded latency sufficient to solve the problem at hand is guaranteed by the system. In particular, frequently, algorithms that guarantee bounded latency responses are less efficient overall than algorithms that don’t.
5. One will also occasionally see discussions of “soft” vs. “hard” real-time systems. In many of these discussions, “hard” real-time means the type of real-time system discussed above, and “soft” real-time means systems which have reduced constraints on “lateness” but still must operate very quickly and repeatably. However, the definition is controversial, as some mean by “hard” and “soft” the degree of time constraints. For instance, a real-time process attempting to recognize images may have only a few hundred microseconds in which to resolve each image, but a process that attempts to position a servo-motor may have tens of milli-seconds in which to process its data.
6. Robert Bristow-Johnson adds the following distinction (in the case of DSP):
In a real-time DSP process, the analyzed (input) and/or generated (output) samples (whether they are grouped together in large segments or processed individually) can be processed (or generated) continuously in the time it takes to input and/or output the same set of samples independent of the processing delay.
Consider an audio DSP example: if a process requires 2.01 seconds to analyze or process 2.00 seconds of sound, it is not real-time. If it takes 1.99 seconds, it is (or can be made into) a real-time DSP process.
A common life example I like to make is standing in a line (or queue) waiting for the checkout in a grocery store. If the line asymtotically grows longer and longer without bound, the checkout process is not real-time. If the length of the line is bounded, customers are being “processed” and outputted as rapidly, on average, as they are being inputted and that process _is_ real-time. The grocer might go out of business or must at least lose business if he/she cannot make his/her checkout process real-time (so it’s fundamentally important that this process be real-time).
The last definition (6) is the one used for real-time audio and video, for phone call over Internet, and so on. It means that the processing time is less than the time to get a sample. Note that in the case of Internet it is easy to get starvation because the sample arrivals depend on the bandwidth.
——————————
What is POSIX 1003.1b (formerly 1003.4)? Where is it available?
POSIX 1003.4 was the working name for what is now the 1003.1b standard..
Recently, Dan Hildebrand posted:
The ratified POSIX standards that generally pertain to real-time OS’s consist of: 1003.1 (OS, process, filesystem and device API), 1003.2 (utilities), 1003.1b (real-time), and 1003.1c (threads). POSIX 1003.1d (which defines some additional real-time extensions like standardized interrupt handler support) is not yet ratified, although some OS’s already support portions of it.
The best way to get the most current status is to refer to some of these texts and contacts:
The POSIX 1003.1 standard is ISBN 1-55937-061-0. A good O’Reilly text is “POSIX Programmer’s Guide: Writing Portable UNIX Programs”. Donald Lewine. ISBN: 0-937175-73-0
For other standards, the IEEE’s address is:
Secretary, IEEE Standards Board
445 Hoes Lane
P.O. Box 1331
Piscataway, NJ 08855-1331
USA
http://cs-www.bu.edu/pub/ieee-rts/Home.html
Many of the POSIX draft standards can also be obtained by calling the IEEE Draft Standards Office. Credit card in-hand, phone +1 202 371 0101 to place an order.
Another contact is the IEEE-USA Customer Service Center at 800 678 4333
(+1 908 981 1393 for outside of 800 zone); fax: +1 908 981 9667.
——————————
What makes an OS a RTOS?
1. A RTOS (Real-Time Operating System) has to be multi-threaded and preemptible.
2. The notion of thread priority has to exist as there is for the moment no deadline driven OS.
3. The OS has to support predictable thread synchronisation mechanisms
4. A system of priority inheritance has to exist
5. OS Behaviour should be known
So the following figures should be clearly given by the RTOS manufacturer:
1. the interrupt latency (i.e. time from interrupt to task run) : this has to be compatible with application requirements and has to be predictable. This value depends on the number of simultaneous pending interrupts.
2. for every system call, the maximum time it takes. It should be predictable and independent from the number of objects in the system;
3. the maximum time the OS and drivers mask the interrupts.
The following points should also be known by the developer:
1. System Interrupt Levels.
2. Device driver IRQ Levels, maximum time they take, etc.
——————————
What is a good RTOS?
A good RTOS is not only a good Kernel ! A good RTOS should have a good documentation, should be delivered with good tools to develop and tune your application. So even if some figures like the Interrupt latency, Context switch time are important, there are a lot of other parameters that will make a good RTOS. For example a RTOS supporting many devices will have more advantages than a simple very good nano-kernel.
——————————
What is RMA?
“Rate-Monotonic Analysis” is a term coined by researchers at CMU. It refers to the real-time performance analysis of a system design that uses static-priority driven scheduling, in particular, the “rate-monotonic” static priority assignment, where tasks with shorter periods get the higher priorities, in a typical static-priority driven real-time operating system like pSOS VxWorks VRTX etc.
Research (mostly) from CMU and U-York and Illinois gives you the mathematical tools to answer “what if I designed it this way???” analysis on your system workload. You need to break your software into “tasks” with “periods” and “deadlines” (relative to the period) and you must be able to guess or prototype a rough “execution time” for each task. Also, for more precise analysis, it helps to know all the critical sections and their runtimes and who shares them, or at the least, the length of the longest critical section in all of your software.
You can plug all this data into a “schedulability analyzer” tool (PERTS, MIMOSA, Scheduler 1-2-3 (CMU), TimeWiz (TimeSys), Software Engineer(?s) Notebook (CMU, newer)), or even the back of an envelope “Utilization Test” or “Formula Test” and find out if your workload will meet all its different deadlines.
If you workload does not meet deadlines, the better tools can help you to explore changes to your workload, in order to meet all the deadlines.
======================================================
III- PUBLICATIONS COVERING REAL-TIME TOPICS
————————-
Here are some references to the theory and practice
Several people recommended as a starting place the article “Tutorial on Hard Real-Time Systems”, edited by John A. Stankovic and Krithi Ramamritham, IEEE Computer Society reprint series, Computer Society order number 819.
Kopetz, H.: Real-Time Systems, Design Principles for Distributed Embedded Applications. Kluwer Academic Publishers, Massachusetts, 1997.
A good book indeed. It covers:
Real-Time Environment, Distributed Solutions, Global Time, Modeling Real-Time Systems, Real-Time Entities and Images, Fault Tolerance, Real-Time Communication, The Time-Triggered Approach, Input/Output, Real-Time Operating Systems, Real-Time Scheduling, Validation, System Design, Time Triggered Architecture
PRACTITIONER’S HANDBOOK FOR REAL-TIME ANALYSIS: Guide to Rate Monotonic Analysis for Real-Time Systems. Klein,Mark; et al, Year 1993, Definitive developer’s guide. Ten chapters in 4 parts: Introduction;Concepts & Techniques; Analyzing Real-Time Systems; & Using the Handbook on Realistic Systems. KLUWER ACADEMIC, Pages 712, ISBN: 0-7923-9361-9
STRATEGIES FOR REAL-TIME SYSTEM SPECIFICATION, Hatley,D.J. & Pirbhai, I.A, Year 1988, Casebook & practical reference for modeling requirements & architecture. Topeics include: Process; Control; Finite State Machines, Timing; Dictionary; & Examples, DORSET HOUSE, Pages 408, ISBN: 0-932633-11-0
STRUCTURED DEVELOPMENT FOR REAL-TIME SYSTEMS, Combined Version, Vols 1,2 & 3., Ward, P.T. & Mellor, S. J., Year 1987, PRENTICE HALL, Pages 468, ISBN: 0-13-854654-1
Caxton Foster’s “Real-Time Programming: Neglected Topics,” despite the title, is a very good introduction to the basic topics of real-time control,
starting with simple things like interrupts and debouncing switches, all the way through digital filters. It’s a thin paperback (Addison Wesley MicroBooks), and a (somewhat) experienced programmer can get through it in a couple of days.
iRUG. Proceedings of the Intel Real-Time User’s Group. Annual, back copies available from iRUG, P.O. Box 91130, Portland, OR 97291, (800) 255-4784. Annual conference proceedings dealing primarily with Intel’s family of real-time OSs, iRMX.
Books references in The Online Dedicated Systems Encyclopaedia(there is always a comment there) http://www.dedicated-systems.com/encyc/publications/books.htm
J.E. Cooling, Software Design for Real-time Systems, SBN 0-412-34180-8, published by Chapman and Hall.
Yann Hang Lee and C.M. Krishna, Readings in real-time systems, ISBN 0-8186-2997-5, 1993, published by IEEE Computer Society Press.
Mathai Joseph, Real-Time Systems, University of Warwick, ISBN 0-13-455297-0, 1996, published by Prentice Hall Professional Technical Reference.
Krishna M. Kavi , Real-time systems, abstractions, languages and design methodologies, ISBN 0-8186-3152-X, 1992, published by IEEE Computer Society Press.
Phillip Laplante, Real-time systems design and analysis, an engineer’s handbook, ISBN 0-8186-3107, 1993, published by IEEE Computer Society Press
David L. Ripps, An implementation guide to real-time programming, ISBN 0-13-451873-X, 1989, published by Yourdon Press, Prentice-Hall Building, now out of print!
Ken Shumate and Marilyn Keller, Software specification and design, a disciplined approach for real-time systems, ISBN 0-417-53296-7, 1992, published by John Wiley and Sons, Inc.
Another list of books with comments http://www.realtime-os.com/rtresour.html
A publisher: http://www.powells.com
———————————
Peter Desnoyers sends along:
The classic reference in the area of timers is:
George Varhese and Tony Lauck, “Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility”, Operating Systems Review 21, no. 5 (Proceedings of 11th ACM Symposium on Operating Systems), 1987.
Their results show O(1) times for insert and delete of 13 and 7 instructions for one of the schemes, and decent performance with large numbers of outstanding timers.
———————————
Christian Ebner sends along a classic reference in priority inheritance algorithm:
Sha, L., Rajkumar, R. and Sathaye, S.: Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions on Computers, Vol. 39(9). pp.1175-1185.
Analysis shows that the priority inheritance protocol can lead to chained blocking and deadlocks. To solve this problem, the priority ceiling protocol was developed by L. Sha, R. Rajkumar and S. Sathaye.
———————————
Here are some other suggestions from various net.sources, in publishing date order:
Mellichamp, D. A. Real-Time Computing. New York: Van Nostrand Reinhold, 1983. 552 pp.
Twenty chapters by 11 authors on topics ranging from signal processing to managing real-time computing facilities.
A. K. Mok, The Design of Real-time Programming Systems Based on Process Models, in Proc. 1984 Real-Time Systems Symposium, Dec.1984, pp5-17.
E. Kligerman and A. Stoyenko, Real-Time Euclid: A Language for Reliable Real-Time Systems, in TOSE, Sep. 1986, pp 941-949, vol SE-12.
D. W. Leinbaugh and M.-R. Yamini, Guaranteed Response Times in a Distributed Hard-Real-Time Environment, in TOSE, Dec.1986, vol SE-12.
A. Stoyenko, A Real-Time Language With A Schedulability Analyzer, Computer Systems Research Institute, University of Toronto, Dissertation, Dec. 1987.
Lawrence, P. D. and Mauch, K. Real-Time Microcomputer System Design. New York, McGraw-Hill, 1987. 568 pp.
The emphasis is on the design of I/O circuits and assembly language interfaces for small microprocessors used for embedded systems.
H. Kopetz and A. Damm and Ch. Koza and M. Mulazzani and W. Schwabl and Ch. Senft and R. Zainlinger, Distributed Fault-Tolerant Real-Time Systems: The MARS Approach, in IEEE Micro, vol.9, Feb.1989, pp25-40.
Burns, A. and Wellings, A. Real-Time Systems and Their Programming Languages. Wokingham: Addison-Wesley, 1990. 575 pp.
Ada, Modula-2, and occam 2 are used throughout the book, which covers topics ranging from basic programming techniques, fault tolerance, exception handling, concurrency, resource management, and distributed designs.
Vickery, C. Real-Time and Systems Programming for PCs. New York: McGraw-Hill, 1993. 604 pp. The thesis is that the development environment for real-time systems is ideal for studying systems programming, too. After some introductory material, the book deals exclusively with Intel’s iRMX operating systems, with particular emphasis on iRMX for Windows.