Real-Time System References and Reading Materials

Elec 494 Course on Real-Time Software - Spring, 1995
University of British Columbia
Dept. of Electrical Engineering
Donald W. Gillies - Professor

In a hard real-time system the correctness of a computation depends not only on the computed results but also on the time at which they are produced. A result produced on or after the deadline is typically useless.

A hard real-time system typically has many time constraints that must be satisfied simultaneously and periodically. Conventional operating systems and conventional data structures are optimized to meet one performance constraint - to optimize job throughput. Conventional performance techniques are nearly useless for hard real-time software.

Only the "core" of a hard real-time system must meet hard deadlines. The rest of the software is typically "soft" or "non" realtime. For example, consider the design of the Iridium satellite. The "core" tasks station keeping (flying precisely in the low earth orbit box) and keeping the solar panels pointed towards the sun. Phone calls would be nice to have but they aren't as mission-critical as these tasks. The "soft real-time tasks" are flash uploads, memory scrubbing (to repair radiation errors), heater maintenance, data checkpoint, power saving, etc. In particular, some activities like shifting users to different channels in order to power down a cluster of radio channels, and reorganizing memory to respond quickly to new phone-call or handoff arrivals, can run endlessly at very low priority. Every extra joule of power saved extends the satellite battery life and reduces the monthly subscription cost for the Iridium service, but there is no _hard target_ for power savings.

In a system with both hard and soft real-time tasks, the operating system and the software libraries must support the "core", and so a hard real-time OS and library must be used.

In the design of a highly concurrent system, care must be taken to minimize synchronization costs. A clever system designer will cast the software architecture into a form that requires no busy waiting and very few semaphores, if any. Operations that occur at similar frequencies or have a great deal of data flow or sharing will appear in the same task, to reduce context-switching overhead. Once the system is decomposed into tasks, the two most popular real-time system scheduling techniques are the cyclic executive and the static-priority preemptive kernel.

In a cyclic executive, a periodic schedule is planned as the software is designed. In the Boeing 777, a 200 ms schedule (called a super frame) was produced using combinatorial optimization and branch and bound programming. Resource contention was solved during this step so semaphores were not needed during execution. This 200 ms schedule is replayed endlessly onboard the airplane. In other systems (such as the MARS pathfinder), static priority preemptive scheduling is used to semi-dynamically select tasks for execution. These systems are easier to change (no replanning is necessary), and background and unused time is aggregated by the scheduler for more efficiency in soft real-time processing.

Some examples of software ideas found in real-time systems today are:

Data structures

• calendar queues
• bitmap priority queues
• pool memory allocator

• priority-inversion-control semaphores
• sporadic servers
• fine-grained clock synchronization
• watchdog timers
• bitmap task wakeup signals
• admission-control resource managers
• imprecise static-priority schedulers
• instrumented kernel

Few real-time operating systems today have more than 3 of these features. For example, UNIX and Windows-NT have none of these features.

In this reading list, we focus mainly on higher-level scheduling and macro performance analysis of real-time systems at the task level.

It often happens that the performance budgets are not met, and the application must be redesigned after the system is built. For ideas and testing techniques in performance-based application design and testing see the section on "Performance-Oriented Software Design".

In some cases, the engineers may write (very expensive) "negative instruction cycles" in order to meet all the deadlines. The book by Phillipe Laplante covers the topic of software tuning thoroughly.

I have been asked to identify a few seminal papers that could be read by someone just getting started in this field. In the reading list below, I have outlined these papers in BOLD FACE and I have provided a short description of why the paper is important to the field.

Journals and Conferences

• The Journal of Real-Time Systems, Kluwer academic publishers, Boston, Vols. 1-10, 1989-1998.
• IEEE Real-Time Systems Symposium (RTSS), Institute for Electrical and Electronics Engineers, Inc. Vols. 1-20, 1979-1998.
• IEEE Workshop on Real-Time Operating Systems and Software (in conjunction with) IFAC/IFIP Workshop on Real-Time Programming, Institute for Electrical and Electronics Engineers, Inc. Vols. 1-15, 1984-1998. Now known as the IEEE Real-Time Applications Symposium (RTAS).

• Foster, Caxton, real-time systems: neglected topics, Cambridge, MA: Addison Wesley Microbooks, 1982 (paperback, out of print).
• Garey, M.R. and D.S. Johnson, Computers and Intractability: A guide to the theory of np-completeness, New York: W. H. Freeman and Company, 1979.
• Gomaa, H., Software design methods for concurrent real-time systems, Reading, Massachusetts: Addison-Wesley (SEI series in software engineering), 1993.
• Klein et. al, A practitioner's handbook for real-time analysis, Boston: Kluwer Academic, 1993.
• Labrosse, John, MicroC/OS-II, R&D Books, 1998, ISBN 0879305436.
• Phillipe Laplante, Real-Time systems design and analysis: An engineer's handbook, New York: IEEE Press, 1993.
• Notes from a CMU SEI Course on Real-Time Systems (Available in UBC Library, a tutorial subset of Klein's book).

Performance-Oriented Software Design

• J. Saltzer, and D. Clark, End-to-end arguments in system design, ACM Transactions on Computer Systems 2(4), November 1984, pp 277-288. This describes the golden "occam's razor" rule of operating systems (and real-time system) kernel design.
• B. Lampson, Hints for computer systems design, IEEE Software Magazine, January 1984. Also ACM Symposium on Operating Systems Principles, 1983. Also, Xerox PARC Technical Report, 1983. Also, web page at http://www.research.microsoft.com/colleagues/blampson/33-Hints/WebPage.html.
• A. D. Birrell and B. J. Nelson, Implementing Remote Procedure Calls, ACM Transactions on Computer Systems 2(1), February 1984.
• D. Clark, Why computer network protocols DontGoFast!!!, Notes from a talk at Stanford University, 1986.
• D. Clark, V. Jacobsen, J. Romkey, and H. Salwen, An analysis of TCP processing overhead, IEEE Communications Magazine, June 1989.
• J. Bentley, Writing efficient programs, Prentice-hall, 1982.
• R. Jain, The art of computer systems performance analysis, Wiley, 1991.
• B.W. Lampson, and D. D. Redell. Experience with Processes and Monitors in Mesa. Communications of the ACM, Vol. 23, No. 2 (Feb 1980), pp. 105-117. The MESA language was almost adopted by the DoD instead of Ada, but Xerox refused to disclose this in-house wonder. This one self-contained paper describes almost everything you need to know to build an operating system. Real-Time systems builders often have to build or tightly control their own kernel. This is an early paper to identify the "priority inversion" problem and it suggested a lazy (but faulty) algorithm to solve it, spurring more research. The UNIX kernel uses the splx() (highest locker) algorithm to correctly solve the problem.

• C. D. Locke, Software architecture for hard real-time applications: cyclic executives vs. fixed priority executives, Journal of Real-Time Systems, vol. 4, no. 1, March 1992, pp. 37-53. This is an overview of the 2 major system architectures used in real-time systems, and their associated trade-offs.
• H. Gomaa, A software design method for real-time systems, Communications of the ACM, vol. 27 no. 9, September 1984, pp. 938-949. How to design your real-time system using the second system architecture, based on a static priority preemptive kernel.
• L. Sha and J.B. Goodenough, Real-time scheduling theory and Ada, IEEE Computer Magazine 23, 4 (April 1990), pp 52-62. ADA 8x, the original DOD-sponsored "real-time systems" language, had many serious design mistakes. This paper explains why you can't just use any systems architecture and expect to run real-time applications in a predictable way. A number of important but subtle issues are explained clearly.

Static-Priority Schedulability Utilization Theory

• C. L. Liu and J. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the ACM, 10(1), 1973. The paper that founded the field of mathematical real-time systems design.
• J. Labeltoulle. Some theorems on real-time scheduling. In E. Gelenbe and R. Mahl, editors, Computer Architecture and Networks, pp. 285-293, North Holland, 1974.
• J. Lehoczky, L. Sha and Y. Ding, The Rate monotonic scheduling algorithm: exact characterization and average case behavior, RTSS 1989, pp. 166-171, December 1989.
• J. Lehoczky, Fixed priority scheduling of periodic task sets with arbitrary deadlines, RTSS 1990, pp. 201-213, December 1990.
• S. K. Dhall and C. L. Liu, On a real-time scheduling problem, Operations Research, Vol. 26, pp. 127-140, 1978.
• S. Davari and S. K. Dhall, An on line algorithm for real-time task allocation, RTSS 1986, pp. 194-199, December 1986.
• B. Sprunt, J. Lehoczky and L. Sha, Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm, RTSS 1988, pp. 251-258.
• M. Klein, J. P. Lehoczky, R. Rajkumar, Rate-monotonic analysis for real-time industrial computing, IEEE Computer Magazine, January 1994, pp. 24-33. Introduces rate-monotonic analysis based on Liu-Layland paper (but you should read all the schedulability utilization papers to understand the analysis method thoroughly).
• M. G. Harbour, M. H. Klein and J. P. Lehoczky, Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priority, RTSS 1991.
• D. W. Gillies, Burst-processing in hard real-time systems. Submitted to IEEE Transactions on Computers, 1998.

• L. Sha, J. Lehoczky, and R. Rajkumar, Solution for some practical problems in prioritized preemptive scheduling, pp. 181-191, RTSS 1986.
• J. W.-S. Liu, K. J. Lin, W.-K. Shih, A. Yu, J.-Y. Chung and W. Zhao, Algorithms for scheduling imprecise computations, IEEE Computer Magazine, vol. 24 no. 5, May 1991.
• J. Lehoczky, L. Sha and J. K. Strosnider, Enhanced aperiodic responsiveness in hard real-time environments, RTSS 1987, pp. 261-270.
• B. Sprunt, J. Lehoczky and L. Sha, Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm, RTSS 1988, pp. 251-258.
• B. Sprunt, L. Sha and J. Lehoczky, Scheduling sporadic and aperiodic events in a hard real-time system, Technical report no. CMU/SEI-89-TR-11, Carnegie-Mellon Software Engineering Institute, April 1989.

• L. Sha, R. Rajkumar and J. P. Lehoczky, Priority inheritance protocols: an approach to real-time synchronization, IEEE Transactions on Computers, vol. 39 no. 9, September 1990, pp. 1175-1185.
• R. Rajkumar, L. Sha and J. P. Lehoczky, An experimental investigation of synchronization protocols, IEEE Real-Time Systems Newsletter, Spring/Summer 1989 (special special issue on the 6th Real-Time Operating Systems Symposium), pp. 11-17.
• SEI, Volume 2: Exercises and Case Studies, Carnegie-Mellon Software Engineering Institute Course on Rate-Monotonic Scheduling Theory, 1990.

• B. Sprunt, L. Sha and J. Lehoczky, Scheduling sporadic and aperiodic events in a hard real-time system, Technical report no. CMU/SEI-89-TR-11, Carnegie-Mellon Software Engineering Institute, April 1989.
• H. Kopetz and J. Reisinge, The non-blocking write protocol NBW: a solution to a real-time synchronization problem, RTSS 1993, pp 131-137
• D. Gillies, End-to-end real-time synchronization with modulators, IEEE Workshop on the role of real-time in multimedia/interactive computing systems, 1993.

• W.J. Quirk (ed), Verification and validation of real-time software, Berlin: Springer Verlag, 1985.
• R. A. DeMillo, R. J. Lipton and F. G. Sayward, Hints on test data selection: help for the practicing programmer, IEEE Computer Magazine, April 1978, pp 34-41.

• M. G. Harmon, T. P. Baker and D. B. Whalley, A retargetable technique for predicting execution time of code, Real-Time Systems, vol. 7 no. 2, September 1992, pp. 159-182
• A. D. Stoyenko, A real-time language with a schedulability analyzer, Ph.D. Thesis, Dept. of Computer Science, University of Toronto.
• C. Y. Park and A. C. Shaw, Experiments with a program timing tool based on source-level timing schema. Computer, vol. 24 no. 5, 1991, pp. 48-57.
• J. W.-S. Liu, J.-L. Redondo, Z. Deng, T.-S. Tia, R. Bettati, A. Silberman, M. Storch, Rhan Ha and W.K. Shih, ``PERTS: A Prototyping Environment for Real-Time Systems.'' Proceedings of the Real-Time Systems Symposium, Raleigh-Durham, N.C., Dec. 1993. Also appeared University of Illinois Dept. of CS as Technical Report UIUCDCS-R-93-1802.

Memory Allocation

• A. Aho and J. Ullman, Principles of compiler design, Reading Massachusetts: Addison Wesley, 1979 (3rd printing), chapter 10, pp 351-377.
• T. P. Baker, A stack-based resource allocation policy for realtime processes, RTSS 1990, pp. 191-200. (figures are wrong) Also in Real-Time Systems Journal, 1991.
• E. G. Coffman, An introduction to combinatorial models of dynamic storage allocation, SIAM Review, vol. 25 no. 3, July 1983, pp. 311-325.
• J. F. Ready, VRTX: A real-time operating system for embedded microprocessor applications, IEEE Micro Magazine, August 1986, pp. 8-17.
• D. L. Ripps, An implementation guide to real-time programming, Englewood Cliffs, NJ: Prentice-Hall (Yourdon Press Computing Series), 1990.
• T. A. Standish, Data structure techniques, Reading Massachusetts: Addison Wesley, 1980, chapter 6, pp. 247-284.

• A. Mahmood and E. J. McCluskey, Concurrent error detection using watchdog processors - a survey. IEEE Transactions on Computers, vol. 37, no. 2, February 1988, pp. 160-174.
• L. Lamport, R. Shostack and M. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems, July 1982.
• M. Singhal and N. G. Shivaratri, Advanced concepts in operating systems, New York: McGraw-Hill, Inc., 1994.

• P. Lawrence, Real-time microcomputer system design, Reading, Massachusetts: Addison-Wesley, 1987.
• S. R. Ray, Lecture notes on D/A and A/D converters, manuscript, Department of Computer Science, University of Illinois at Urbana-Champaign (1994).
• P. Horowitz and W. Hill, The art of electronics, second edition, Cambridge, England: Cambridge University Press, 1989.

• Intel Corp., 82527 Serial communications controller architectural overview (automotive), February 1995.
• Intel Corp., 82527 serial communications controller - controller area network protocol (automotive), March 1995.
• K. Tindell and A. Burns, Guaranteed message latencies for distributed safety-critical hard real-time control networks. Report no. YCS229, Dept. of Computer Science, University of York, May 1994.

• C. M. Bailey, A. Burns, A. J. Wellings and C. H. Forsyth, A performance analysis of a hard real-time system, Report no. YCS224, Dept. of Computer Science, University of York, 1994.
• C. M. Bailey, E. Fyfe, T. Vardanega and A. J. Wellings, The use of preemptive priority-based scheduling for space applications, IEEE Real-Time Systems Symposium, 1993, pp. 253-257.
• A. Burns, A. J. Wellings, C. M. Bailey and E. Fyfe, A case study in hard real-time system design and implementation, Report No. YCS190, Dept. of CS, University of York, 1993.

• D. Girling, real-time systems lecture notes, Simon Fraser University, 1992, pp. 16-22.
• J. DiGiacomo, Digital bus handbook, New York: McGraw-Hill, 1990, chapters 1 and 3.
• PCI special interest group., PCI system design guide, 1994.
• PCI special interest group., PCI local bus specification / revision 2.0, April 1993.
• L. Sha, R. Rajkumar and J. Lehoczky, Real-time scheduling support in Futurebus+, IEEE Real-Time Systems Symposium, 1990, pp. 331-340.

• E. A. Parr, Programmable controllers: an engineer's guide, Oxford: Newnes, 1993.
• Book, forgot the name and title, 1988.

• J. A. Stankovic (ed.), L. Sha, J. Lehoczky, A. Mok, C. L. Liu, E. Waldrum, K. Johnson, K. Shin, H. Tokuda, W. Zhao, J. Strosnider, P. Watson, A. van Tilborg, Real-time computing systems: the next generation, Dept. of Computer and Information Science, University of Massachussetts COINS technical report 88-06, 1988.

• MIMOSA timing tools
• RMA end-to-end queuing calculations
• mode changes
• network I/O
• more info on watchdogs / fault tolerance
• pinwheel references from al mok.
  • R. Holte, A. Mok, L. Rosier, I. Tulchinsky and D. Varvel, ``The Pinwheel: a Real-time Scheduling Problem'', in Proceedings, 22nd Hawaii International Conference on System Science, January, 1989.
  • S.K. Baruah, N. Cohen, C.G. Plaxton and D. Varvel, ``Proportionate Progress: a Notion of Fairness in Resource Allocation'' in STOC Proceedings, 1992 (1993?)