100% CPU Use With Rate Monotonic Scheduling

Rate Monotonic Scheduling (RMS) is probably what you should be using if you are using an RTOS. With rate monotonic scheduling you assign fixed priorities based solely on task execution periods. The fastest period gets the highest priority, and the slower periods get progressively lower priorities. It's that simple -- except for the math that limits maximum allowable CPU use.

The descriptions of Rate Monotonic theory (often called Rate Monotonic Analysis -- RMA) point out that you can't use 100% of the CPU if you want to guarantee schedulability. Maximum usage ranges between 69% to 85% of the CPU (see, for example Wikipedia for this analysis). And, as a result, many developers shy away from RMS. Who wants to pay up to about a third of their CPU capacity to the gods of scheduling?  Nobody. Not even if this is an optimal way to schedule using fixed priorities.

The good news is that you can have your cake and eat it too.

The secret to making Rate Monotonic Scheduling practical is to use harmonic task periods. This requires that every task period evenly divide the period of every longer period. So, for example, the periods {20,  60, 120} are harmonic because 20 divides 60 evenly, 20 divides 120 evenly, and 60 divides 120 evenly. The period set {20, 67, 120} is not harmonic because, for example, 20 doesn't divide 67 evenly.

If you have harmonic periods, you can schedule up to 100% of the CPU. You don't need to leave slack!  (Well, I'd leave a little slack in the real world, but the point is the math says you can go to 100% instead of saying you top out at a much lower utilization.)  So, in a real system, you can use RMA without giving up a lot of CPU capacity.

What if your tasks aren't harmonic? Them make them so by running some tasks faster. For example, if your task periods are {20, 67, 120} change them to {20, 60, 120}. In other words, run the 67 msec task at 60 msec, which is a little faster than you would otherwise need to run it. Counter-intuitively, speeding up one task will actually lower your total CPU requirements in typical situations because now you don't have to leave unused CPU capacity to make the scheduling math work. Let's face it; in real systems task frequencies often have considerably leeway. So make your life easy and choose them to be harmonic.

You can find out more about RMA and how to do scheduling analysis in Chapter 14 of my book.