On Wed, Oct 12, 2011 at 02:55:39PM +0200, Gregor Best wrote: > Hi people, > > attached is a patch that basically rewrites the CPU scheduler. It > replaces the multilevel feedback queue currently employed with an > earliest effective deadline first approach, similar to the BrainFuck > Scheduler for Linux. > > My main motivation for rewriting the scheduler was mplayer getting > killed all the time because it went over its share of CPU resources, > something which can not happen with the patch I wrote. > > The algorithms employed simply assigns a (soft) deadline to each > process, which is calculated based solely on nice value and selects the > next process to execute based on the earliest deadline in the runqueue. > If more than one deadline is missed, the first one encountered in FIFO > order (FIFO with respect to insertion into the runqueue) with a deadline > smaller than current time is selected. This prevents processes from > yielding a small time before their timeslice expires to fool the > scheduler into leaving them in their respective priority queue, thus > preventing multiple processes from teaming up to starve others of CPU > runtime. > > I did a few benchmarks to test the difference between the original and > my patched scheduler to see whether there was any improvements. The tool > I used was sysbench (with both CPU and Threads benchmarks). There are a > few graphs of the tests at http://gurkenfunk.de/projects/openbsd-eevdf, > but it looks as if my patches improve latency on workloads with high CPU > usage, little I/O and a relatively large amount of threads. > > I'm not aiming for a "yeah, nice, we'll merge it" on this, but rather > for suggestions whether it's worth anyones time to pursue this further.
All this is very interesting and I've spent some time, in 2.7 days on trying to understand/improve the behaviour of interactive processes (aka processes like synths that wait on i/o and have a deadline for processing their input). I still believe that the current scheduler, in the UP case, is very friendly to audio, since interactive process almost always get the CPU at time. AFAICS, changing the scheduler won't improve correct audio code that already works. Another scheduler might improve the wrong code. Since we're talking about mplayer and alike, currently most of the stuttering is caused by mistakes in audio code and cpu-intensive code runnin in kernel mode. The scheduler doesn't hurt interactive processes, does it? > Oh, also, with the patch, the scheduler code is 225 lines shorter and > IMHO a bit easier to understand. > I love simplification diffs especially ones with more -'s than +'s. You've removed some of the MP affinity bits and the rlimit bits, i guess this is temporary for clarity only, isn't it? I've read kolivas design paper you suggest, but failed to understand how this scheduling algorithm would improve interactive processes like mplayer. Do you have further references? -- Alexandre
