TECHNOLOGY BACKGROUNDER

Rate Monotonic Analysis (RMA)

To build real-time systems that are reliable and deterministic, the timing behavior of the tasks in a program must be predictable. Rate Monotonic Analysis (RMA) is a model for predicting, a priori, whether or not a system will meet its timing, as well as throughput requirements, when the system is operational.

Figure 1. An example of a flight control system task analysis.

With RAPID RMA (formerly PERTS) users can study the effects and relationships of various parameters in the system that directly affect the schedulability of the entire task set.

If the system is predictable, it can be formally analyzed (See Figure 1). RMA allows a user to determine ahead of time whether the system will meet its timing requirements.

Alternative approaches to RMA, such as simulation, do not determine schedulability on anything other than best case. RMA allows the user to look at worst case phasing of tasks, resource contention access problems, resource utilization, and prioritization.

RMA's modeling techniques also let a user do “what if” scenarios much quicker than it would take to change a simulation and run it for a few hours or days to see the results. Plus, early in the design cycle, RMA can find out if a process is schedulable. If it's not, the user can go back and re-architect before a prototype is created. With other techniques, early design analysis is typically hit or miss. As a result, users often overarchitect a system because they can't determine what resources are available.

RMA is also set apart by the fact that it permits a user to run an analysis, such as finding convergence or divergence of certain conditions only once, to see what the worst case phasing would be. That means users don't have to guess what the time frame would be to see worst case scheduling.

One of the biggest advantages RMA has over other methods is that it actually points the user to the problem areas. Blocking problems and other resource bottlenecks are indicated graphically. Task parameters can be changed quickly and easily to modify the system. Previously, many of these problems were not discovered until system integration and test, when hours were spent using logic and bus analyzers to find subtle, non-repeatable timing problems that caused many schedule delays. With end-to-end analysis capabilities also available, users can now look not just at an isolated task set on a specific processor. but at entire embedded systems and networks. Data flow analysis and pipelined systems can be analyzed in much the same way as single processor task sets.

Rate monotonic analysis can be used throughout the software life cycle in conjunction with other methods or by itself (See Figure 2.). In the early stages of development the only information the user has to determine the task execution times and deadlines are historical data, if it exists, some simple discrete event simulators, and customer specifications. At this point the user has a rough “first order” model.

Figure 2 - Lifecycle Model of Rate Monotonic Analysis

As preliminary design proceeds, prototyping efforts will produce more accurate estimates and device simulators will produce even more accurate numbers. These refinements are used to update the RMA model so that by the time implementation begins, a fairly accurate model has been used to develop the tasking architecture to the point where it should be close to truth. During implementation and on into integration and test, the RMA model can still be used. As a matter of fact, even existing systems that are being upgraded or enhanced can benefit from a model of the tasking architecture to determine if the required upgrades or enhancements will work before they are ever made.

The RM algorithm is useful for tasks that occur at a periodic rate. However, there are many aperiodic events in real time systems, such as hardware interrupts. These interrupts can occur at random intervals and can be devastating if not anticipated and handled correctly. Using RMA, these aperiodic events are modeled using devices called periodic servers. A periodic server is assigned to each aperiodic task and is responsible for executing that task. Priorities are assigned to the server based on the standard RM priority assignment. Processor time is also allocated to each server. How the servers manage this processor time can vary.

When the periodic server runs, if the aperiodic task assigned to the server is ready to run, it will be scheduled. The aperiodic tasks can be assigned execution intervals based on uniform or exponential distributions, and can have hard or soft deadlines. The goal of the user is to experiment with these different parameters to determine the best way to respond to aperiodic events. Allocating too much time to the handling of aperiodic events may lead to the entire system becoming unschedulable. 

Prototyping is a method that can be used during this phase to estimate more accurate task execution times and resource requirements that can then be used to update the RMA model. Tasks can be created and modified quickly in the model. Different scheduling algorithms can be chosen with the click of a button. Task priorities can be changed quickly. All this is helpful when performing sensitivity analysis to determine the best scheduling approach for a set of tasks and resources. By the completion of this phase, the user can prove to himself or herself, as well as management, that the tasking architecture chosen for the system is optimal based on a RMA sensitivity analysis.

The detailed design phase is typically where the system architecture is completely designed. The user now has accurate estimates for software size, I/O and other resource requirements, and execution times. During this phase, the details of task synchronization, inter-process communication, and resource management are decided. The schedulability model is updated to reflect these new conditions. By using RMA, adding resources, tasks, and dependencies is not difficult. Adding the details of the resource requirements into the model allows more detailed analysis of the system.

For example, blocking conditions, priority inversion conditions, and other bottlenecks can be discovered during this phase using an accurate model. Device simulation (for a new processor, for example) can be used to generate detailed estimates of tasks and resources. Problems can be corrected during the detailed design phase before the developers ever have to begin integration and test. The model can be changed quickly and easily to allow the user to experiment with different approaches to fix these problems early.

In the past, the user never knew how the system was really going to run until he/she got to integration and test. Finding problems with system scheduling at that time was difficult and expensive to fix. Even developing a discrete event simulation of the system wasn't always good enough because the user never knew how long to run the simulation. If a scheduling problem happens only during a certain task phasing situation, a simulation may never catch it. A RMA tool, based on mathematics of schedulability, will look for the worst case scenario and give the user an answer in seconds.

During implementation and on into integration and test, the RMA model becomes an even more valuable tool. During implementation, actual timing measurements are available. The RMA model can be updated to reflect these actuals. As changes are made to support various interfaces and functionality, the RMA model can be used to assess the impact of changes before they are ever made, thus preventing users from performing unnecessary tasks, such as:

1. Recompiling and executing the software to see if a change worked.
2. Moving functionality from a task to an interrupt service routine, or
3. Re-allocating resources that can be analyzed in the model before being implemented in the software.

In conclusion, rate monotonic analysis is a method for determining schedulability of real time systems. RMA can predict ahead of time whether or not a system will meet its timing and throughput requirements. RMA can guarantee a system will be schedulable if a set of requirements is met. One of the major advantages of RMA is its ability to predict, reliably, if a set of tasks will, under all conditions, be schedulable. With the development of interactive design tools, such as RAPID RMA based on RMA, the design of systems has become even easier. RAPID RMA allows rapid prototyping and extensive “what if” analysis to be performed. The only way to perform this same analysis previously was to spend hours running various derivatives of a simulation. RMA tools can now give a more reliable answer quickly.