Bibliography
[Baker78] H. G. Baker, List Processing in Real Time on a Serial Computer, Communications of the ACM, Vol. 21, No.4, April, 1978.
[] Bollella, Greg, et al., The Real-Time Specification for Java, Addison-Wesley Longman, January 2000.
[] R. A. Brooks, Trading Data Space for Reduced Time and Code Space in Real-Time Garbage Collection on Stock Hardware, in Proceedings of the 1984 Symposium on Lisp and Functional Programming, Austin, Texas, August, 1984.
[Buttazzo05] Buttazzo, Georgia C., Hard Real-Time Computing Systems. Springer, 2005.
[.)
[.)
[.)
[.)
[Klein93] Klein, Mark, et al., A Practitioners Guide to Real-Time Analysis. Kluwer Academic Publishers, 1993.
[Layland73] Liu, C. L. and Layland, James W., Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM, 1973 (Available at http://portal.acm.org/citation.cfm?id=321743.)
[] Lindholm, Tim, and Yellin, Frank, Java Virtual Machine Specification, 2nd Edition. Prentice Hall PTR, 1999.
[] Liu, Jane W. S., Real-Time Systems. Prentice Hall, 2000.
[.)
[McCarthy60] McCarthy, John, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, Communications of the ACM, 1960 (Available online at http://www-formal.stanford.edu/jmc/recursive.pdf.)
[] McDougal, Richard, and Mauro, Jim, Solaris InternalsSolaris 10 and OpenSolaris Kernel Architecture. Prentice Hall, 2007.
[).
[.)
1
Real-Time for the Rest of Us
Let him who would enjoy a good future waste none of his present.
Roger Babson
THERE are many misunderstandings about what real-time is, even amongst seasoned enterprise Java developers. Some confuse it with high-performance, or fast, computing; others think of dynamic applications such as instant messaging. Neither one is necessarily an example of a real-time system. Therefore real-time does not always equal real fast, although good performance is often desirable and achievable. In fact, real-time is often orthogonal with high-throughput systems; theres a trade-off in throughput in many cases. The best way to avoid all of this confusion is to think of it this way: application performance and throughput requirements can be solved with faster, or additional, hardware; real-time requirements, in general, cannot.
This chapter will define real-time computing, and will explain why throwing hardware at a real-time requirement will almost never do any good. Well discuss the qualities of a real-time system, define key terms used in the discipline, and examine tools, languages, and environments available to real-time developers outside of the Java world. By the end of this chapter, youll have a good real-time foundation to build upon.
Qualities of Real-Time Systems
The goal of a real-time system is to respond to real-world events before a measurable deadline, or within a bounded time frame. However, a real-time system is also about precision. The measured speed of a systems response to an event is important, but whats also important is the systems ability to respond at precisely the right moment in time. Access to a high-resolution timer to perform actions on precise time periods is often a requirement. These two qualities together best define a real-time applications acceptable behavior: the ability to respond to an event before a deadline, and accurately perform periodic processing, regardless of overall system load. Before we go any further, its important to examine the term deadline a little more closely, as well as some other terms often used in the context of real-time systems.
The term deadline can have one of two meanings. First, it can be a deadline relative to an event, such as a notification or message in some form. In this case, the system must respond to that event within a certain amount of time of receiving that event, or from when that event originally occurred. One example of a relative deadline is an elevator as it passes over a sensor indicating that its almost at the floor its meant to stop at. The real-time software within the elevator must respond to that event within milliseconds of passing the sensor, or it wont be able to stop at the intended floor. The occupants of an elevator that skips stops are certain to consider this an error.
Relative Deadline (Di): the amount of time after a request is made that the system needs to respond.
Absolute Deadline (di): the precise point in time that a task must be completed, regardless of task start time, or request arrival.
Often, with an absolute deadline, a real-time system checks for a particular system state on a regular interval. Some examples of this are an aircraft flight control system, or a nuclear power plants core temperature monitoring system. In both of these cases, critical data is continuously polled, such as altitude, or core temperature. Failing to monitor these values at precise points in time can cause these systems to go into a bad state with potentially catastrophic results.
Regardless of the type of deadline, relative or absolute, time is still a main component in proper system behavior. Its not enough that an elevators software knows and responds to a floor sensor; it must do so within a deadline in order to behave correctly. Also, a flight control system must be able to move an aircrafts control surfaces at the precise time, in reaction to the most recent and accurate set of data, in order to fly the aircraft correctly (without crashing!).
For example, lets say we have a system requirement to send a response to a request within one millisecond. If the system responds within 500 microseconds every time, you may think the requirement has been met. However, if the request is delayed, outside the system under measurement, the response will not have been sent at the right moment in time (even if its sent within one millisecond). Remember, were talking about real time here; the one-millisecond requirement applies to when the originating system sent the original request.
illustrates the problem. Here you see that the system in question has responded to the request within one millisecond, but it was at the wrong time because the request was delayed in delivery. A real-time system must adhere to the end-to-end deadline.
Figure 1-1 The response time was good, but the deadline was missed. This is not a real-time system.
In a real-time system, the time delay from when a real-world event occurs (such as an object passing over a sensor, or the arrival of a stock market data-feed tick) to the time some code finishes processing that event should be reasonably bounded. The ability to meet this deadline must be predictable and guaranteed, all the time, in order to provide the determinism needed for a real-time system.
What Is Bounded?
When we use the term bounded in relation to a bounded amount of time, what we really imply is a reasonable amount of time for the system to respond. In other words, saying that the elevator responds to sensor events within a ten-year bounded timeframe is unreasonable. It must do so according to a time requirement that allows it to function properly. Therefore, when we use the term bounded, its relative to the proper operation of the time-critical event were describing.
When discussing real-time systems, the basic element of execution is often referred to as a job, or task. (For a more accurate definition of jobs and tasks in real-time systems, see the note on Jobs and Tasks in Real-Time Systems). There can be one or more tasks in a given system, and therefore tasks can either be running or waiting. On a uniprocessor machine, only one task can be running at a single point in time, as opposed to multiprocessor machines that can execute more than one task at a time.