The ongoing interactive scheduling effort [LWN.net]

The interactive scheduling response of the 2.6.0-test kernels is a controversial topic. Some (including your editor) find the recent kernels to be noticeably more responsive than the 2.4 series; others complain loudly. It does seem that, despite the fact that some users are happy, the job is not yet entirely finished.

Con Kolivas has continued to produce his scheduler patches, which concentrate mostly on tweaking the interactivity estimation code. The basic idea remains that, if the system can get a good handle on which tasks are truly interactive, it can then be made to do the right thing. In many cases, that appears to be the case. Andrew Morton has, however, recently called for Con to take a step back and rethink things after being made aware of some significant performance regressions that appear to have been caused by the scheduler patches:

I suggest that what we need to do is to await some more complete testing of the CPU scheduler patch alone from Steve and co. If it is fully confirmed that the CPU scheduler changes are the culprit we need to either fix it or go back to square one and start again with more careful testing and a less ambitious set of changes.

Con did some quick testing and narrowed the problem down to Ingo Molnar's latest interactivity patch. There does not, as yet, appear to be a real understanding of what is going on, however.

Con has also recently posted a lengthy document on how the scheduler works and what changes his patches have made.

Nick Piggin is, perhaps, best known for scheduling disks - he is the author of the anticipatory I/O scheduler in 2.6.0-test. Nick recently decided to get into the CPU scheduler tuning game, and has started posting patches; his most recent is Nick's scheduler policy v7. These patches take a different approach, starting by hacking out almost all of the code that tries to calculate interactivity. They remove almost as much code as they add.

The key part of Nick's policy seems to be the manipulation of time slices. Processes at different priority levels get very different time slices - much more so than with the current scheduler. Time slices also depend on what else is running; if there aren't any high priority processes waiting to run, lower-priority processes will get larger slices. Process priorities also vary more quickly, allowing processes which sleep a lot to get back into the CPU quickly. Finally, this patch restores the "priority transfer" idea: when one process wakes another, a portion of the waking process's priority (and time slice) is given over to the process being awakened. This feature helps to keep the X server responsive. With Nick's patch, the X server benefits from being given a higher priority; this is not the case with Con's scheduler patches.

Getting scheduling right is hard, as can be seen by the amount of effort being put to the problem. By many accounts, 2.6 will be better than earlier kernels in this regard. But it would not be surprising if developers were still trying to improve it long after 2.6.0 is released.

(Log in to post comments)

The ongoing interactive scheduling effort

Posted Aug 28, 2003 16:29 UTC (Thu) by cpeterso (guest, #305) [Link]

Why doesn't Linux implement multi-level feedback queues? MLFQ is a classic scheduler algorithm used in Multics and most OS textbooks. It favors IO-bound processes over CPU-bound processes. If a process blocks before its CPU time slice is complete, then it is IO-bound and it is likely an interactive process waiting for mouse or keyboard input. If a process uses its entire CPU time slice without blocking, then it is CPU-bound and working hard crunchin' numbers. These processes are given a lower priority. I guess things get tricky when your MP3 player is working hard to decompress MP3 data, but you want it to have a high priority..

The ongoing interactive scheduling effort

Posted Aug 28, 2003 16:32 UTC (Thu) by cpeterso (guest, #305) [Link]

ok, I have now read Con's description of the O(1) scheduler and I see that they are effectively implementing multi-level feedback queues (with the scheduler's active and expired arrays). Of course, it sounds like yet again, the Linux developers are reinventing the wheel, unaware of the existing literature! :-\

The ongoing interactive scheduling effort

Posted Aug 28, 2003 20:34 UTC (Thu) by stuart (subscriber, #623) [Link]

or perhaps they have read the literature. If it was an easy problem to solve the 'literature' wouldn't contain so many damn algorithms for scheduling.

As the 'literature' hasn't conclusively solved the problem, then experimentation by the kernel hackers can't do any halm can it. In fact too close a study of the literature could mean too narrow a view being taken in development and hence true innovation not happening.

The ongoing interactive scheduling effort

Posted Sep 5, 2003 0:16 UTC (Fri) by conman (guest, #14830) [Link]

Thank you for pointing that out.

If you read carefully you'll see that nowhere was anything being reinvented. The algorithm for determining interactivity in place was a tried and tested and well described method. It simply wasn't flexible enough for real world usage so the aim was to use the available information in a smarter manner.