Linux scheduler found inadequate !

logo Linux

An international research team recently proved that, contrary to common opinion, there is room for improvement of the kernel’s scheduling mechanisms, which have not been developed to the level of the technological innovations created for the hardware.

As a reminder, scheduling is a crucial activity for operating systems, assigning the tasks to be performed to the different computing instruments in a machine (core and processor) so as to ensure optimum performance levels and continuous availability of the machine.

Linus Torvalds spoke...

On the subject of Linux performance levels, Linus Torvalds wrapped things up almost 15 years ago, on 15 December 2001 precisely, considering that, the problem being simple and already resolved in the Linux kernel, it could easily be ported to multi-processor machines. With his usual tact, Linus Torvalds even felt that the question could be settled with some code and that developers couldn’t “screw up the few hundred lines too badly”. In short, the guru had spoken and any contradiction was out of the question. In reality, the shift to multi-processor, multi-core technologies proved to be more complicated than expected. An initial symptom was the under-use of the additional cores and processors.

Creating monitoring tools

They hadn’t reckoned on scientific scepticism, the innovative tool par excellence that pushed a team of researchers to try to explain the downgraded performance levels observed by comparing manual task assignment to the decisions made by the Linux kernel’s scheduler. After ruling out any other possibilities, the scheduler’s possible faultiness had to be examined. Because there were no existing monitoring tools, the team developed them and then came to an unimpeachable conclusion: some processors were overloaded while others were at rest, with no understandable recurring pattern in the scheduling choices made.


The team then inspected the source code for the concerned Linux kernel and discovered an initial fault in the CFS scheduler’s code. Supported by this initial discovery, the team continued its work and revealed four other major defects in that code. The performance gains observed after applying patches was glaring: by 12% to 23% in terms of general performance and up to a factor of 137 for specific high-performance computing (HPC) loads. This is an opportunity to assess that team’s colossal contributions, because conventional debugging methods were completely useless in those case studies.

New momentum for HPC research

The conclusions of the article published by the team clearly demonstrate that research on scheduling must continue, for application to many other use cases, a domain that appeared to have been well-defined up until recently. And another conclusion: don’t take Linus Torvalds’s words as gospel, even when talking about Linux...


comments powered by Disqus