General Navigation Buttons - Home | Search | Contact Us | Site Map | Whats New
products graphic
white space
products
Software Technology Roadmap
Background & Overview
Technology Descriptions
Defining Software Technology
Technology Categories
Template for Technology Descriptions
Taxonomies
Glossary & Indexes
white space
About SEI|Mgt|Eng|Acq|Collaboration|Prod.& Services|Pubs
pixel
Rollover Popup Hints for Topic Navigation Buttons above
pixel
Rate Monotonic Analysis


Status

Complete

Purpose and Origin

Rate Monotonic Analysis (RMA) is a collection of quantitative methods and algorithms that allows engineers to specify, understand, analyze, and predict the timing behavior of real-time software systems, thus improving their dependability and evolvability.

RMA grew out of the theory of fixed priority scheduling. A theoretical treatment of the problem of scheduling periodic tasks was first discussed by Serlin in 1972 [Serlin 72] and then more comprehensively treated by Liu and Layland in 1973 [Liu 73]. They studied an idealized situation in which all tasks are periodic, do not synchronize with one another, do not suspend themselves during execution, can be instantly preempted by higher priority tasks, and have deadlines at the end of their periods. The term "rate monotonic" originated as a name for the optimal task priority assignment in which higher priorities are accorded to tasks that execute at higher rates (that is, as a monotonic function of rate). Rate monotonic scheduling is a term used in reference to fixed priority task scheduling that uses a rate monotonic prioritization.

During the 1980s the limitations of the original theory were overcome and the theory was generalized to the point of being practicable for a large range of realistic situations encountered in the design and analysis of real-time systems [Sha 91a]. RMA can be used by real-time system designers, testers, maintainers, and troubleshooters, as it provides

  • mechanisms for predicting real-time performance
  • structuring guidelines to help ensure performance predictability
  • insight for uncovering subtle performance problems in real-time systems
This body of theory and methods is also referred to as generalized rate monotonic scheduling (GRMS), a codification of which can be found in Klein [Klein 93].

Technical Detail

RMA provides the analytical foundation for understanding the timing behavior of real-time systems that must manage many concurrent threads of control. Real-time systems often have stringent latency requirements associated with each thread that are derived from the environmental processes with which the system is interacting. RMA provides the basis for predicting whether such latency requirements can be satisfied. Some of the important factors that are used in RMA calculations include:

  • the worst-case execution time of each thread of control
  • the minimum amount of time between successive invocations of each thread
  • the priority levels associated with the execution of each thread
  • sources of overhead such as those due to an operating system
  • delays due to interprocess communication and synchronization
  • allocation of threads of control to physical resources such as CPUs, buses, and networks
These factors and other aspects of the system design are used to calculate worst-case latencies for each thread of control. These worst-case latencies are then compared to each thread's timing requirements to determine if the requirement can be satisfied.

A problem commonly revealed as a result of rate monotonic analysis is priority inversion. Priority inversion is a state in which the execution of a higher priority thread is forced to wait for a resource while a lower priority thread is using the resource. Not all priority inversion can be avoided but proper priority management can reduce priority inversion. For example, priority inheritance is a useful technique for reducing priority inversion in cases where threads must synchronize [Rajkumar 91].

Since RMA is an analytic approach that can be used before system integration to determine if latency requirements will be met, it can result in significant savings in both system resources and development time.

Usage Considerations

RMA is most suitable for systems dominated by a collection of periodic or sporadic processes (i.e., processes with minimum inter-arrival intervals), for which the processing times can be bounded and are without excessive variability. RMA is also primarily focused on hard deadlines rather than soft. However, soft deadlines can be handled through the use of server mechanisms that allocate time to tasks with soft deadlines in a manner that ensures that hard deadlines are still met. Still, with soft deadline tasks, the aperiodic server predictions work best when the workload is primarily periodic.

Systems in which worst-case executions are realized very infrequently or in which there is no minimum inter-arrival interval between thread invocations might not be suitable for RMA analysis. For example, consider multimedia applications where voice and data transmissions involve a great deal of variability. Principles of RMA, such as priority representation, priority arbitration, and priority inheritance, can be used in multimedia systems to reduce response times and meet deadlines at relatively high levels of use. However, deadlines in such environments may not be hard, and execution times can be stochastic, two requirements that are not currently handled well in the RMA framework. When most of the workload is aperiodic, one needs to move to queueing theory.

Maturity

Indicators of RMA maturity include the following:

  • In 1989 IBM applied RMA to a sonar training system, allowing them to discover and correct performance problems [Lucas 92].
  • Since 1990, RMA was recommended by IBM Federal Sector Division (now Lockheed Martin) for its real-time projects.
  • RMA was successfully applied to active and passive sonar of a major submarine system of US Navy.
  • RMA was selected by the European Space Agency as the baseline theory for its Hard Real-Time Operating System Project.
  • The applicability of RMA to a typical avionics application was demonstrated [Locke 91].
  • RMA was adopted in 1990 by NASA for development of real-time software for the space station data management subsystem. In 1992 Acting Deputy Administrator of NASA, Aaron Cohen stated, "Through the development of rate monotonic scheduling, we now have a system that will allow (Space Station) Freedom's computers to budget their time to choose [among] a variety of tasks, and decide not only which one to do first but how much time to spend in the process."
  • Magnavox Electronics Systems Company incorporated RMA into real-time software development [Ignace 94].
  • RMA principles have influenced the design and development of the following standards:
  • Tool vendors provide the capability to analyze real-time designs using RMA. RMA algorithms, such as priority inheritance, have been used by operating system and Ada compiler vendors.

Costs and Limitations

Case studies of RMA adoption show that "While RMA does require engineers to re-frame their understanding of scheduling issues to a more abstract level, only moderate training is required for people to be effective in using the technology" [Fowler 93]. A short (1-2 day) tutorial is usually sufficient to gain a working knowledge of RMA.

Additionally, the studies found "RMA can be incorporated into software engineering processes with relative ease over a period of several months.... RMA can be adopted incrementally; its adoption can range from application to an existing system by one engineer to application across an entire division as standard practice in designing new systems" [Fowler 93].

RMA can be applied with varying degrees of detail. Qualitative analysis through the application of design and trouble shooting heuristics can be very effective. Simple quantitative analysis using back-of-the-envelope calculations quickly yields insight into system timing behavior. More precise quantitative analysis can be performed as more precise system measurements become available during the development activity.

Dependencies

Application performance is influenced by system components such as operating systems networks and communication protocols. Therefore, it is important for such system components to be designed with RMA in mind.

Complementary Technologies

Simulation is often used to gain insight into a system's performance. Simulation can be used to corroborate RMA's performance predictions. Queueing theory is complementary to RMA. Whereas RMA is used to predict worst-case latencies when bounds can be placed on arrival dates and execution times, queueing theory can be used to predict average-case behavior when arrival rates and execution times are described stochastically. Together RMA and queuing theory solve a wide set of performance problems.

Index Categories

This technology is classified under the following categories. Select a category for a list of related topics.

Name of technology

 Rate Monotonic Analysis

Application category

 Detailed Design (AP.1.3.5)
System Analysis and Optimization (AP.1.3.6)
Code (AP.1.4.2)
Performance Testing (AP.1.5.3.5)
Reapply Software Life Cycle (AP.1.9.3)
Reengineering (AP.1.9.5)

Quality measures category

 Real-Time Responsiveness/Latency (QM.2.2.2)
Maintainability (QM.3.1)
Reliability (QM.2.1.2)

Computing reviews category

 Real-Time Systems (C.3)

References and Information Sources

[Audsley 95] Audsley, N.C., et al. "Fixed Priority Pre-Emptive Scheduling: An Historical Perspective." Real Time Systems 8, 2-3. (March-May 1995): 173-98.
[Fowler 93] Fowler, P. & Levine, L. Technology Transition Push: A Case Study of Rate Monotonic Analysis Part 1 (CMU/SEI-93-TR-29). Pittsburgh, PA: Software Engineering Institute, Carnegie Mellon University, 1993.
[Ignace 94] Ignace, S. J.; Sedlmeyer, R. L.; & Thuente, D. J. "Integrating Rate Monotonic Analysis into Real-Time Software Development," 257-274. IFIP Transactions, Diffusion, Transfer and Implementation of Information Technology (A-45). Pittsburgh, PA, October 11-13, 1993. The Netherlands: International Federation of Information Processing, 1994.
[Klein 93] Klein, M.H., et al. A Practitioners' Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Boston, MA: Kluwer Academic Publishers, 1993.
[Lehoczky 94] Lehoczky, J.P. "Real-Time Resource Management Techniques," 1011-1020. Encyclopedia of Software Engineering. New York, NY: J. Wiley & Sons, 1994.
[Liu 73] Liu, C. L. & Layland, J. W. "Scheduling Algorithms for Multi-Programming in a Hard Real-Time Environment." Journal of the Association for Computing Machinery 20, 1 (January 1973): 40-61.
[Locke 91] Locke, C.D.; Vogel, D.R.; & Mesler, T.J. "Building a Predictable Avionics Platform in Ada: a Case Study," 181-189. Proceedings of the Twelfth Real-Time Systems Symposium. San Antonio, TX, December 4-6, 1991. Los Alamitos, CA: IEEE Computer Society Press, 1991.
[Lucas 92] Lucas, L. & Page, B. "Tutorial on Rate Monotonic Analysis." Ninth Annual Washington Ada Symposium. McLean, VA, July 13-16, 1992. New York, NY: Association for Computing Machinery, 1992.
[Rajkumar 91] Rajkumar, Ragunathan. Synchronization in Real-Time Systems: A Priority Inheritance Approach. Boston, MA: Kluwer Academic Publishers, 1991.
[Serlin 72] Serlin, O. "Scheduling of Time Critical Processes," 925-932. Proceedings of the Spring Joint Computer Conference. Atlantic City, NJ, May 16-18, 1972. Montvale, NJ: American Federation of Information Processing Societies, 1972.
[Sha 91a] Sha, Klein & Goodenough, J. "Rate Monotonic Analysis for Real-Time Systems," 129-155. Foundations of Real-Time Computing: Scheduling and Resource Management. Boston, MA: Kluwer Academic Publishers, 1991.
[Sha 91b] Sha, L.; Rajkumar, R.; & Lehoczky, J. P. "Real-Time Computing with IEEE Futurebus+." IEEE Micro 11, 3 (June 1991): 30-38.

Current Author/Maintainer

Mark Klein, SEI

External Reviewers

Mike Gagliardi, SEI
John Goodenough, SEI
John Lehoczky, Professor, Statistics Department, Carnegie Mellon University
Ray Obenza, SEI
Raj Rajkumar, Carnegie Mellon University
Lui Sha, SEI

Modifications

10 Jan 97 (original)
The Software Engineering Institute (SEI) is a federally funded research and development center sponsored by the U.S. Department of Defense and operated by Carnegie Mellon University.

Copyright 2008 by Carnegie Mellon University
Terms of Use
URL: http://www.sei.cmu.edu/str/descriptions/rma_body.html
Last Modified: 24 July 2008