An experiment with the Linux scheduler

[Latest News Headlines]

I was curious to see how the Linux scheduler would manifest from a program's perspective, so today I did an experiment.

I wrote a single-threaded program running a simple loop. All the loop does is to compute the number of milliseconds since the last iteration, and store the result in a histogram. We are not so much interested in the performance of the loop (it does about a million iterations per second) but in the variations in the intervals between loop iterations. These variations are presumably caused by the Linux scheduler.

Here are the numbers I achieved, and the same numbers in a chart (with a logarithmic y-axis).

Interval (milliseconds)Frequency0 450,080,3021 909,0442 4,6423 1,6964 8535 5616 5577 3358 1,0989 15210 8611 5212 9813 1714 1315 616 2117 519 320 121 222 223 024 225 026 027 028 129 0

The vast majority of iterations occur zero milliseconds after the previous iteration. No surprise there; Java's clock granularity, 1 millisecond, is coarse enough to execute over a million instructions.

If the thread was never interrupted, one would expect the loop to tick forward 1 millisecond 1,000 times per second, or about 500,000 times in all. It actually ticks 909,044 times, so interrupts are at work: about 400,000 of them.

Longer delays also occur: 2, 3, 4, up to 28 milliseconds, occurring with exponentially decreasing frequency. Only 8 delays of 20 milliseconds or longer occur in the 7.5 minute run. The chart shows the exponential decay clearly. The chart plots log-frequency, and the trend line is indeed flat from 2 milliseconds onwards, so it is accurate to characterize the line as exponential.

The one surprising thing: significant bumps at 8, 12 and 16 milliseconds. Although the trend of the line is pretty consistently down, each of those interval durations has more distinctly occurrences than the previous interval. Does anyone know anything about the Linux scheduler that might explain this?


More from Julian Hyde on Open Source OLAP Blog ...