"The Rate Monotonic Scheduling Algorithm: Exact Characterization And Average Case Behavior" by Lehoczky, Sha, and Ding attempted to mathematically characterize the rate monotonic algorithm, shown by Liu and Layland in 1973 to be the most optimum static priority scheduling algorithm, as well as to present a Monte-Carlo-style statistic model of its behavior. Lehoczky, Sha, and Ding showed that under a certain set of simplifying assumptions (listed in the introduction of Section 2, Problem Formulation), the rate monotonic algorithm can successfully schedule all tasks if the maximum of the tasks' cumulative processor demand index (some math notation and definitions I can't type here) is at most 1. The authors then go on to test the algorithm's average behavior using stochastic methods: tasks with random periods and random processor utilizations are generated and then scheduled with rate monotonic; the utilizations are then scaled up until the algorithm can no longer successfully schedule all the tasks. The tests showed that as the number of tasks was increased, the maximum or "breakdown" utilization level approached a constant that depended on only the probabilistic distribution of the tasks' periods and not the distribution of the tasks' processor utilizations.

The authors' paper, published in 1989, should be applauded for finally addressing the exact mathematical characterization of the rate monotonic algorithm that Liu and Layland had shown in 1973 to be optimum. Though the paper made several simplifications and assumptions in both the mathematical characterization and the stochastic modeling, the authors clearly stated what assumptions had been made and how they might be better addressed in the future. In Section 5, Summary and Conclusion, the authors also listed many ways in which the results of the paper should be generalized for application in less restrictive circumstances.

This was an interesting paper that allowed me to understand rate monotonic in more detail (though I admit I knew nothing about it to begin with). I was in a little over my head with the mathematical details, but the general results the authors presented were very neat and surprising. In particular, knowing nothing about rate monotonic beforehand, I would have expected intuitively that its asymptotic behavior depended on the task set's utilization distribution (not its period distribution), rather than the other way around.