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.

Is there any formal proof that the 100% utilisation for Harmonic task sets can be achieved for RM?

ReplyDeleteLet's consider the following task set:

ReplyDeleteTau_1 = {Ci = 1, Ti = 2}; Tau_2 = {Ci = 1, Ti = 4}; Tau_3 = {Ci = 2, Ti = 8} where Ci is the "worst case execution time" of Tau_i and Ti the period of Tau_i.

U(task set) = 100%

By doing a response time analysis, I can see that the lowest priority task, Tau_3, has a response time equal to its period. I have tested a few more task sets and found out that this is always the case. However, to assure that this is the case for any arbitrary Harmonic task set, I need a formal proof to show that 100% utilisation is the max_bound.

Thanks

Lehoczky J.P., Sha L., Strosnider J.K., Tokuda H. (1991) Fixed Priority Scheduling Theory for Hard Real-Time Systems. In: van Tilborg A.M., Koob G.M. (eds) Foundations of Real-Time Computing: Scheduling and Resource Management. The Springer International Series in Engineering and Computer Science (Real-Time Systems), vol 141. Springer, Boston, MA

ReplyDeletehttps://doi.org/10.1007/978-1-4615-3956-8_1

page 8