September 1, 1997

Rate-monotonic analysis keeps real-time systems on schedule

Robert Oshana, Texas Instruments Systems Group

In the design of real-time systems, time is critical. Rate-monotonic analysis can predict whether a system will meet its timing and throughput requirements, and interactive design tools make it easy to tailor the analysis to your system.

Real-time systems have become more widespread and complex in the last several years as designers discovered the systems' potential for a number of applications, including automotive, aerospace, avionics, and nuclear-power-plant environments. In many of these systems, time is an intrinsic part of the correct system behavior. Failure of tasks to meet deadlines can cause human, environmental, or economic damage.

A major problem in designing software for these sophisticated systems is determining how to schedule tasks. Typically, decisions about even the most important tasks are subjective, and responses to external events, such as interrupts, are extremely difficult to predict. Designers commonly run simulations to get an idea of how a system will run. However, in some situations, simulations can take a long time to develop and to modify if you want to experiment with scheduling policies and priority assignments. Depending on the complexity of the model and the whole tasking architecture, a simulation also can take a long to run time to run, and you don't know how long the simulation to get an accurate answer.

Alternatively, rate-monotonic analysis (RMA) is a mathematical method for predicting, a priori, whether a system will meet its timing and throughput requirements when the system is operational. To build reliable and deterministic systems, you must be able to predict the timing behavior of the tasks in the program. If the system is predictable, you can formally analyze it and determine beforehand whether it will meet its timing requirements. RMA can guarantee that a system is schedulable with a given set of requirements. RMA can also reliably predict if a set of tasks will be schedulable under all conditions.

Interactive design tools make it easy to apply RMA to any real-time system. These tools allow for rapid prototyping and extensive what-if analyses. Previously, the only way to perform these analyses was to spend hours running various derivatives of a simulation. RMA tools can now more quickly give a more reliable answer. Instead of having to use a variety of tools and methods, you can use one RMA tool to receive information throughout software development: for risk mitigation early in the project, as a design tool during development, and as an aid during the integration and test phase.

Another advantage RMA tools offer is that they point you to problem areas so that you can quickly and easily change task parameters. For example, the tools graphically indicate blocking problems and other resource bottlenecks. Many of these problems don't surface until the integration and test phase, during which you can spend hours using logic and bus analyzers to find subtle, nonrepeatable timing problems that cause many a schedule delay. With RMA tools' end-to-end analysis, you can look not just at an isolated task set on a processor, but also at entire embedded systems and networks. You can analyze data flow and pipelined systems in much the same way you do with single-processor task sets.

The theory of RMA

The RMA approach to task schedulability has been around since the 1970s and is still popular. The main scheduling model is shortest period first. That is, of the set of tasks that are ready at any time, the one with the shortest period executes before all others (Figure 1). Because you must know the task period in advance, this approach is a static-priority algorithm.

The rate-monotonic (RM) algorithm that determines if a set of tasks will run requires that the total task utilization be less than or equal to the utilization bound. The total task utilization is equal to

where C_i equals the worst-case task-execution time of each task i, T_i equals the period of task i, and i ranges from 1 to N. The utilization bound, U(N), for N tasks is

So, for the task characteristics in Figure 1, the total task utilization is

and the utilization bound is

This set of tasks results in 70% utilization, which is less than the utilization bound of 77.9%. Thus, this result means that these tasks will always meet their deadlines, regardless of how and when the system schedules the tasks.

Because this algorithm is based on the worst-case execution time of each task, it is "pessimistic." The algorithm provides a sufficient schedulability condition: A system task set is always schedulable if the total task utilization does not exceed the utilization bound. The system is guaranteed to be schedulable if it passes this first-order schedulability test, the utilization-bound test.

In this example, the algorithm guarantees schedulability for the tasks in Figure 1. In fact, the utilization is only around 70%, which means that the system isn't using 30% of the CPU time. If a total-processor utilization of a task set exceeds the utilization bound but is still less than one (which represents a processor utilization of 100%), the task set may still be schedulable. However, you must now perform a more elaborate test--the response-time test. This test is necessary and sufficient for schedulability. A response-time test is based on processor time demand. If the processor demand is lower than the processor supply for a time interval before a task deadline, the task is schedulable. If all the tasks in the system pass this test, the system is schedulable.

The RM algorithm is expandable and can include blocking terms. Blocking can lead to priority inversion. Priority inversion occurs when a lower priority task blocks a higher priority task because the lower priority task has locked a resource that the higher priority task needs. Priority inversion is always a threat in real-time systems. Another unavoidable situation in real-time systems is task switching, which occurs whenever the system stops one task to execute another. This switching requires time, and you must add this extra time to the total task-execution time.

Other expansions to the RM algorithm can handle other situations, such as aperiodic events, jitter control, message-passing paradigms, multiprocessor and distributed-system issues, and tasks that must synchronize to share common data. One of the benefits of the RM algorithm is its stability. Lower priority tasks execute after higher priority tasks. In conditions of transient overload, tasks miss their deadlines according to their priority, and the higher priority tasks finish first.

The RM algorithm is useful for tasks that occur at a periodic rate. However, many aperiodic events, primarily hardware interrupts, occur in real-time systems. These interrupts can take place at random intervals and be devastating if the system doesn't anticipate and correctly handle them. In RMA, you model these aperiodic events using periodic servers. The tool assigns a periodic server to each aperiodic task, and the server is responsible for executing that task. You assign priorities to the servers based on the standard RM priority assignment and then allocate processor time to each server. How the servers manage this processor time can vary.

Each server periodically checks to see if a task is ready (if all the resources for the task are available, for example). If the task is ready, the server immediately schedules and runs the task. Aperiodic tasks can have execution intervals based on uniform or exponential distributions and can have hard or soft deadlines. You can experiment with these parameters to determine the best way to respond to aperiodic events. Allocating too much time to the handling of aperiodic events may lead to an entire system that's unschedulable.

Tools support RMA

Numerous tools are available that help the software developer to prototype software and that support application development. However, few tools are available to help the system designer verify that real-time systems are meeting timing constraints. Simulations for real-time analysis can be large, costly, and time-consuming to develop. For most real-time systems, you first develop the application software and then verify the timing constraints using informal, ad hoc methods. The result is that you find many of the real-time problems during the integration and test phase, at which point they are costly to fix.

RMA tools, such as PERTS (prototyping environment for real-time systems, Tri-Pacific Corp, Alameda, CA), use analytical approaches to verify real-time constraints based on scheduling theory. PERTS abstractly analyzes the system as a model. The system designer develops the model and can then use the framework to determine schedulability based on scheduling algorithms. Also, new simulation tools, such as PERTS*Sim, complement RMA in an integrated modeling and prototyping environment and give designers the best of both worlds.

You can use PERTS RMA in a variety of tasks, including task modeling, resource modeling, aperiodic servers, multiple-scheduling algorithms, multiple-priority-assignment algorithms, interactive design environments, single- and multiple-node analysis, and end-to-end analysis. Using PERTS, you can analyze, validate, and evaluate real-time systems and then experiment with alternative scheduling and resource-management strategies. Several scheduling protocols are available. PERTS currently supports the RM and deadline-monotonic scheduling algorithms, as well as the priority-ceiling-protocol (PCP), stack-based-protocol (SBP), earliest-deadline-first (EDF), and cyclic executive priority-assignment algorithms.

A schedulability analyzer provides an interactive design environment. For example, PERTS allows you to study the effects and relationships of various parameters in the system that directly affect the schedulability of the entire task set. The analyzer not only determines if the system task set is schedulable, but also identifies where and why a failure to meet deadlines is most likely to occur. For example, the tool can point to a task model and identify its problem, such as a resource's being locked for too long.

You can easily modify a number of system parameters to improve schedulability. The analyzer also predicts the timing effects of changes to parameters at the hardware and operating-system-software level. Because the tool is based on analytical computation, the results are immediately available, and you can quickly perform what-if scenarios.

A real-time-system example

One example of RMA's usefulness is the development and analysis of a tasking architecture for an array of DSP mPs interfaced to a single-board control computer (Figure 2). This system processes incoming data and outputs reports along with some detailed high-bandwidth data to the single-board computer. Each node has two sets of concurrent tasks that process different segments of data. These tasks must communicate with the other tasks on the node as well as go off chip to communicate and send data to other tasks in neighboring nodes.

For this design, RMA can help you answer some significant questions:

• Can the system extract the necessary amount of high-data-rate information from each of the nodes within the allotted time?

• What is the impact of many node-to-node communication transfers?

• Do any significant blocking or priority-inversion problems occur?

• What effects do the operating system and runtime services have on the timing analysis?

• Is the system schedulable?

The RMA model of the system consists of a tasking model (Figure 3a) and a resource model (Figure 3b) for the C40 processors. The task model represents all of the periodic tasks in the system, as well as the aperiodic tasks that you model with periodic servers. You model the required resources and assign these resources to tasks. You also enter all task and resource parameters, such as scheduling algorithms; priority assignments; deadlines; periods; and execution, task-switch, resource-access, and interrupt-arrival times.

Analyzing the system is as simple as asking the tool to analyze schedulability. The tool calculates the CPU utilization and schedulability results and automatically determines what level of RMA is necessary. You don't have to get directly involved with the underlying mathematics that the tool uses to determine schedulability. If the system is unschedulable, the tool tells you which tasks were unschedulable and where in the task model the likely problems, such as blocking, exist. A schedulability interface allows you to quickly and easily make adjustments to the tasks--even to turn them on and off--and to rerun the analyzer (Figure 4).

Using an RMA tool isn't difficult, but creating the actual model of the system requires a different type of thinking: Most engineers are used to thinking in the physical sense, but RMA requires a more abstract representation of the physical architecture. You need to take the physical design and extract timing information from the logical model. Then, it is easy to go directly from a physical functional model to a timing model on a one-to-one basis. You need to analyze the functional model to determine what the actual logical timing model should be. You can then enter the data into the RMA tool.

RMA is a modeling approach to verifying schedulability. RMA tools allow the designer to run a model with one of several scheduling algorithms and then, with a click of the mouse, change the algorithm and rerun the analysis using a different algorithm. RMA also allows multiple-node and end-to-end analyses, which can be especially useful in distributed applications or in modeling local- and wide-area networks (using end-to-end scheduling). In addition, RMA tools can identify and easily change blocking conditions without changing the system's physical architecture. Blocking and pre-emption are the most common reasons for missing deadlines and thus are the problems most RMA tools focus on.

Simulation differs from RMA modeling because simulation needs to run for a certain, and often indeterminate, length of time to look for convergence or divergence of certain conditions. Also, if a scheduling problem happens only during a certain task-phasing situation, a simulation may never catch it. Using a modeling approach such as RMA allows you to run the analysis once to determine the worst-case phasing (when all tasks simultaneously want to execute) without trying to guess what the time frame would be to see the corresponding worst-case scheduling. Worst-case phasing leads to worst-case schedulability. Running what-if scenarios using RMA is much faster than changing a simulation and then running it for a few hours or days to see the results.

You should not totally ignore simulation, however, because it can provide a useful extension to RMA. The PERTS*Sim simulator, for example, allows PERTS users to perform simulation using PERTS RMA models. This simulator allows you to set confidence levels and triggers for each of the simulations. These triggers allow you to see how the model converges or diverges over time, which is one of the strengths of a simulation. Then, you can fine-tune the model based on this simulation analysis. Providing simulation as a natural extension of the RMA model offers a more dynamic view of the model. You can compare the worst-case results of the PERTS model with the simulation results. With simulation tools developed to work as part of a prototyping and modeling environment with RMA tools, new methodologies are evolving to combine simulation and RMA to further enhance real-time-system development.

Use RMA throughout the development cycle

You can use RMA throughout the software-development cycle with other methods or by itself (Figure 5) to obtain a constantly improving estimate of the tasks' periods and the system architecture. In the early stages of development, namely software-requirements analysis, historical data (if available) and customer specifications are the only pieces of information you have to determine the tasks' execution times and deadlines. Without using RMA, building a discrete-event simulation is the only way to perform any real analysis. Even a simple simulation of the system can be costly and somewhat unreliable. Also, each time you analyze the system, you have to determine how long to run the simulation.

Using an RMA tool instead of a simulation generally gives better results in schedulability analysis. During this early stage, you can build a rough first-order model. This rough model can provide early estimates of task-execution times, schedulability, and hardware requirements. By scaling the task-execution times in the model, you can estimate the processor's speed requirement.

For example, if the schedulability analysis based on a 50-MHz processor shows that the CPU utilization is 120% for that tasking architecture, a simple change in the processing-rate parameter to 1.2 makes the system schedulable and indicates that a 60-MHz processor is necessary. If the customer requires a certain CPU reserve, you can also add this requirement to the model. For a 100-MHz processor that requires a 20% CPU reserve, you can change the processing rate to 0.8. The system developers now have to develop an architecture that meets this new "virtual" processor rate to maintain the 20% reserve.

The software-tasking architecture must be in place during the preliminary design phase. You must determine each software task and its priority, and using an RMA tool during this phase is useful for determining the tasking architecture. You can use prototyping during this phase to estimate more accurate task-execution times and resource requirements and then subsequently update the model. You can quickly create and modify tasks and their priorities in the model and choose scheduling algorithms with the click of a button. All these features are helpful when you perform sensitivity analysis to determine the best scheduling approach for a set of tasks and resources. By the completion of this phase, it is comforting to be able to prove to yourself and the customer that the chosen tasking architecture for the software system is optimal based on an RM sensitivity analysis.

The development team typically completes the system-architecture design during the detailed design phase. At this point, the team has fairly accurate estimates for software size, I/O and other resource requirements, and execution times. During this phase, the team decides the details of task synchronization, interprocessor communication, and resource management. You can update the schedulability model to reflect these new conditions. Adding resources, tasks, and dependencies is not difficult using an RMA tool. Adding the details of the resource requirements to the model allows more detailed analysis of the system.

For example, an accurate model can discover blocking and priority-inversion conditions and other bottlenecks during this phase. If it is available, you can use device simulation (for a new processor, for example) to generate detailed estimates of tasks and resources. The goal is to correct problems during this detailed design phase before the integration and test phase begins. You can quickly and easily change the model to experiment with different approaches to fix these problems early.

During implementation and on into integration and test, the RMA model becomes even more valuable. During implementation, actual timing measurements are available, and you can update the RMA model to reflect the actual numbers. As changes occur to support various interfaces and functionalities, you can use the RMA model to assess the impact of changes before making them, thus preventing the system integrators from performing unnecessary tasks. These tasks include recompiling and executing the software to see if a change works, moving functionality from a task to an interrupt-service routine, or reallocating resources that the model can help analyze before the software implements those resources. Even systems that you are upgrading or enhancing can benefit from a model of the tasking architecture to determine if the necessary upgrades or enhancements will work.

References

1. Liu, C, and J Layland, "Scheduling algorithms for multiprogramming in a hard real time environment," Journal of the Association for Computing Machinery, January 1973.

2. Klein, Mark, Thomas Ralya, Bill Pollak, and Ray Obenza, A Practitioner's Handbook for Real Time Analysis, Kluwer Academic Publishers, Norwell, MA, 1993.

| EDN Access | Feedback | Table of Contents |