You are viewing paulmck

Previous Entry | Next Entry

elephant, penguin
My presentation at the Real Time Linux Workshop this past October, titled “On migrate_disable() and Lantencies” (presentation), was a bit of a departure for me. This presentation used a Markov model to analyze the behavior of some recent changes to the scheduler for the 3.0 series of -rt kernels.

Although this approach produced some interesting results, one difficulty is that a number of the corresponding scheduler measurement simply do not fit the exponential distribution very well. This question of course came up during my talk, where an audience member suggested instead using the Erlang distribution. Unfortunately, my only memory of Erlang distributions was of a 1980s operations-research class, where I learned how to use an Erlang distribution, but not why anyone would want to, at least not beyond the professor's vague assurances that it is helpful when modeling telephony networks.

So I answered that I might consider an Erlang distribution, but that I figured that I could match the data quite well by using cascaded Markov-model stages to represent a single state in the higher-level model. The big advantage of this cascading approach is that the math and software remains the same: You simply map additional states into the model.

However, my work reducing RCU's need for scheduler-clock ticks took precedence, so it was only recently that I got time to work out the math for cascaded Markov-model stages. I got the results I expected, but I figured that I should also do a quick review of the Erlang distribution. So I got out my old copy of “Introduction to Operations Research” by Hillier and Lieberman. Imagine my surprise to learn that the Erlang distribution is exactly cascaded Markov-model stages!

So my response to the question during my talk was essentially: “I might try the Erlang distribution, but I am going to try deriving it from scratch first.” Oh well, I would much rather look foolish with the correct answer than to look smart with the wrong answer!

On the other hand, this approach did give me a very good understanding of not only how to use the Erlang distribution, but also how to derive it and why you might want to use it. :-)