Rate Monotonic Analysis

Say what?

Yes that is right, this mornings lecture covered the fascinating subject of rate monotonic analysis.

I say that somewhat in jest, but it actually was a fascinating subject.

Here is the problem.

Given a given set of tasks that an RTOS wants to schedule, what is the appropriate priority level for each task?  Further more can we guarantee that all time constraints can be met?

Now I didn’t talk about task priorities in yesterday’s post, but in a true RTOS, tasks which are deemed to have a higher priority will always get access to the resources of the processor over any lower priority task.  This is necessary if we are to meet the real time constraints of an embedded system.

Going back to the problem statement though, if we have a dozen tasks or more, each of which has a real time constraint, how do we decide which priority to give to each task, and can we always be sure that the time constraints will be met.  Well rate monotonic analysis can provide the answer for us.

In order to do this analysis we need to know 3 main things about the embedded system.

1. How many tasks are there.
2. What is each task’s time constraint; how often must it get access to the processor
3. What is each task’s worst case time for how long it needs access to the processor

Once we have this information we can simply follow the following steps.

1. Assign task priorities based on each task’s time constraint.  The task which has the shortest time constraint has the highest priority.  That was easy.
2. Multiply each time constraint by its worst case execution time to get the CPU utilization for that each task.  This is actually quite hard to calculate.
3. Add up all the utilizations to determine the total processor utilization.

Now if the answer to 3 is greater than 100% we know that it is impossible to schedule the events so that all the tasks time constraints can be met.  It is time to buy a faster processor, or improve the code to speed up the tasks.

The question now becomes if the overall processor utilization is less than 100% do we guarantee all time constraints can be met?

The answer is no.  In order to guarantee all time constraints are met the maximum processor utilization turns out to be the equation:  n * (2^(1/n) – 1), where n is the number of tasks.

For one task we can obviously have 100% processor utilization.  For two tasks this drops to 82.8% processor utilization.  For three tasks it is 77.9% .  And for n as it grows the limit approaches 69.3% processor utilization.

This turns out to be very nice for the designer.  Regardless of how many tasks there are, and as long as priorities are assigned in order of time constraint, and as long as our processor utilization is less than 69% we are guaranteed that all time constraints can be met.

See didn’t I tell you.  Pretty cool stuff.