BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 7, 2009 18:39 UTC (Mon) by niner (guest, #26151)
In reply to: BFS vs. mainline scheduler benchmarks and measurements by paragw
Parent article: BFS vs. mainline scheduler benchmarks and measurements

"We could even do sillier things on the desktop by feeding the desktop scheduler a list of
processes and its descendants to award more interactivity to - no matter what happens
in the background"

But you can do that already! In fact, you ought to have been able to do that for
decades. What you want is just the simple nice and renice commands. Works for any
list of processes you want and their descendants. No need to hardcode names into a
scheduler.

I keep wondering why people seem to have completely forgotten about nice values and
instead expect the scheduler to guess what are the important processes for them, when
they can simply tell it.

to post comments

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 7, 2009 20:37 UTC (Mon) by roskegg (subscriber, #105) [Link] (9 responses)

Because nice and renice don't affect interactivity issues as much as you would think they would.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 7, 2009 21:35 UTC (Mon) by mingo (subscriber, #31122) [Link] (8 responses)

Because nice and renice don't affect interactivity issues as much as you would think they would.

What do you mean?

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 5:12 UTC (Tue) by realnc (guest, #60393) [Link] (7 responses)

Meaning that even if you nice 19 every other process, mplayer will still battle for CPU time with the compositor and drop frames and skip sound as soon a composite effect kicks in.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 6:10 UTC (Tue) by mingo (subscriber, #31122) [Link] (6 responses)

Does it behave in an anomalous way for you? What would you expect it to do and what does it do for you currently?

I.e. the default behavior is that if both compiz and mplayer are running (and both are a single thread) then they should get 50%/50% of a single CPU - or be nicely on separate CPUs on dual-core. (with an added twist that Xorg generally tends to get some amount of CPU time as well when compiz is active - plus whatever other app that is generating X output.)

If that's not enough then come nice levels into play.

You can indeed renice up - but you can also renice down - so you can set mplayer to nice -5 for example.

Nice levels work according to a very simple rule: if you set mplayer to nice -1, it will get 55% of CPU time, compiz gets 45% of time. Yet another nice level and it's 60% versus 40%. It goes roughly 20% up with every nice level - so nice -5 should get you 75%/25%, nice -10 gives you 90% CPU time and 10% CPU time for compiz.

More tasks can modify this behavior - but this is the general principle. If this does not work like that for you, please report it as a scheduler bug on lkml.

Note, you can set negative nice levels as an ordinary user as well, There's an rlimit for it (and PAM support): see the 'nice' attribute in /etc/security/limits.conf - you can set it per user.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 7:31 UTC (Tue) by epa (subscriber, #39769) [Link] (4 responses)

The thing is, nice levels mostly affect total throughput, but what needs improvement is latency. A 50-50 split between two tasks sounds ideal, but that only makes sense if they are both CPU-bound tasks. In the case of compiz and mplayer, the first spends most of its time blocking on user input, and the second doesn't need much CPU time (probably a lot less than 50% on a modern system) but it does need to respond quickly and not be blocked for too long. 'nice' doesn't really address these issues.

(Also I think that 'nice' won't help you if one process starts thrashing the memory and swapping; another process, even if nominally at a lower niceness level, will be heavily slowed down.)

When nice lets you specify desired maximum latencies, as well as just throughput, then it will be a suitable way to get good desktop performance.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 9:44 UTC (Tue) by mingo (subscriber, #31122) [Link] (3 responses)

The thing is, nice levels mostly affect total throughput, but what needs improvement is latency.

That's exactly what the upstream scheduler does. The upstream scheduler considers latency goals in a nice-level normalized way. See the wakeup_gran() function in kernel/sched_fair.c:


  static unsigned long
  wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
  {
          unsigned long gran = sysctl_sched_wakeup_granularity;
          [...]
                 if (unlikely(se->load.weight != NICE_0_LOAD))
                          gran = calc_delta_fair(gran, se);
          [...]
  }

See the calc_delta_fair() - that is the nice level normalizer. Plus-reniced tasks will get longer latencies - minus-reniced tasks will get shorter wakeup latencies.

If this does not work for you then that's a bug, please report it in that case.

Note that you can tune the basic kernel latency goals/deadlines via two dynamic sysctls: sched_wakeup_granularity_ns and sched_latency_ns. Lower those and you'll get a snappier desktop - at the expense of some throughput.

You can set these in /etc/sysctl.conf to make the settings permanent. (and please report it to us if a new setting improves some workload in a dramatic way - we constantly re-tune the upstream default as well, to make for a snappier desktop.)

(Note that for forced preemption (CPU bound tasks) HZ is a lower limit - but otherwise it's tunable in a finegrained way. So say you want to change from HZ=250 to HZ=1000 if you want to set the latency targets down to 1 millisecond.)

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 10:22 UTC (Tue) by epa (subscriber, #39769) [Link] (2 responses)

Thanks for the info. I was still thinking of classic UNIX nice values. It would be even better if you could specify some units for the latency - Linux is not a hard real-time system but nonetheless users might want to say 'maximum latency 10ms for this process' as a best-effort goal and something to benchmark against. Do any distributions come with an appropriate set of nice values built in?

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 11:58 UTC (Tue) by mingo (subscriber, #31122) [Link] (1 responses)

One difference is that nice levels are relative - that way "nice +5" makes relative sense from within a nice +10 workload. Latency values tend to be absolute. Relative makes more conceptual sense IMO - as workloads are fundamentally hierarchical and a sub-workload of some larger workload might not be aware of the larger entity it is running in.

Also, a practical complication is that there's not much of a culture of setting latencies and it would take years to build them into apps and to build awareness.

Also, latencies are hardware dependent and change with time. 100 msecs on an old box is very different from 100 msecs on a newer box.

Maybe for media apps it would make sense to specify some sort of deadline (a video app if it wants to display at fixed frequency, or an audio app if it knows its precise buffering hard limit) - but in practice these apps tend to not even know their precise latency target. For example the audio pathway could be buffered in the desktop environment, in the sound server and in the kernel too.

Nor would it solve much: most of the latencies that people notice and which cause skipping/dropped-frames etc. are bugs, they are unintended and need fixing.

Nevertheless this has come up before and could be done to a certain degree. I still hope that we can just make things behave by default, out of box, without any extra tweaking needed.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 12:41 UTC (Tue) by epa (subscriber, #39769) [Link]

I agree that relative niceness levels make the most sense in a batch processing environment or in a 'lightly interactive' environment such as a Unix shell, where it should respond quickly when you type 'ls', but there is no firm deadline.

I think they make a bit less sense for multimedia applications or even ordinary desktop software (where users nowadays expect smooth scrolling and animations). You are right that in the Unix world there isn't much culture of setting quantifiable targets for latency or CPU use; we are accustomed to mushy 'niceness' values, where setting a lower niceness somehow makes it go faster, but only the most greybearded of system administrators could tell you exactly how much.

One reason to specify a latency target in milliseconds is just to have something quantifiable. A lot of discussions on LKML and elsewhere about scheduling seem to suffer from a disconnect between one side running benchmarks such as kernel compiles, which give hard numbers but aren't typical of desktop usage, and another side who just talk in qualitative terms about how much faster it 'feels'.

I expect that if a 'max latency' option were added to the kernel and it did almost nothing at all to start with, it would still provide a framework for improvements to take place - a latency of 110ms when 100ms was requested could now be a quantifiable performance regression, and people can benchmark their kernel against a promised performance target rather than just trying to assess how it feels. (You yourself have provided such a latency benchmark - the 'load enormous JPEG in Firefox' test suite :=-).

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 19:12 UTC (Tue) by realnc (guest, #60393) [Link]

Does it behave in an anomalous way for you? What would you expect it to do and what does it do for you currently?

It does behave "anomalous." A simple example would be mplayer (or any other video player) or an OpenGL app "hanging" for a bit while I leave my mouse over the clock in the systray. This brings up details about the current time (what day it is, month, etc) in a "bells and whistles" pop-up that just doesn't pop-up out of the blue but slowly fades-in using transparency. It is for the duration of this compositing effect (which actually doesn't even need that much CPU power) that mplayer stalls, barks and drops frames.

Now image how bad things can seem with virtually a crapload of actions (opening menus, switching desktops, moving windows, etc, etc) result in frame skipping, sound stuttering, mouse pointer freezing, etc. They perform well, that's not the problem. The problem is that due to the skips and lag, they *seem* to be sluggish. Not in a dramatic way, but still annoying. I was actually quite used to Linux behaving like that. But after applying the BFS patch, Linux joined the list of "smooth GUI" OSes (alongside OS X and MS Vista/7). That's how a desktop should feel like. Frankly, I never quite suspected the kernel to be at fault here, but rather the applications themselves. But after seeing BFS solving all those problems, it seems the kernel can be at fault for such things.

The Android folks also confirmed that their devices ran much more fluid and responsive after they loaded a custom firmware on them with a BFS-patched kernel. Folding users claim increased folding performance which doesn't interfere with their GUI anymore. This can't be coincidence.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 7, 2009 20:55 UTC (Mon) by paragw (guest, #45306) [Link] (9 responses)

"I keep wondering why people seem to have completely forgotten about nice values and instead expect the scheduler to guess what are the important processes for them, when they can simply tell it."

Did that ever work satisfactorily in practice though? If it did why are people still cranking out different scheduler for desktops?

Thing is usability wise we have come further on a Linux desktop and I guess people are starting to expect the OS to do the right thing without them having to do work and make decisions. (About Xorg renice - what about its clients - every time I start a program, should I renice it if it is a Xorg client? If we instead had the desktop scheduler boost interactivity for all Xorg client programs - that makes it very easy for the user.)

And I was saying we can afford to do such silly things in the Desktop scheduler if the sole objective of the desktop scheduler was interactivity. If one scheduler was to do interactivity and throughput and what not - it quickly becomes complex and thus ineffective. If we had a pluggable scheduler for one thing we could simplify a lot of code and for another we can let people choose what fits their needs best.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 3:55 UTC (Tue) by fest3er (guest, #60379) [Link]

When I was going to do something that might get away from me (fork lots of
processes doing something), I would try to remember to 'nice --20 sh' in
another window. Because I would often have the boundary condition wrong
and would generate 20 000 to 40 000 processes running BTTW. That one
nice'd shell would save me almost every time. I've done this on my AT&T
UNIXPC, and systems running SysV/68, SysV/88, Irix, SunOS[345], Linux,
BeOS, BSD, and others.

There have been times in the past when nice'ing the X server improved
performance on my single-proc PIII-866; for 5-10 years now, only two or
more CPUs let X run smoothly.

There have been times in the past when nothing would smooth out the
choppiness of the EXT2/3 driver under heavy R/W load, whether I had two
PII-266's or a PIII-866. I solved that problem by switching to ReiserFS.

In recent years and on two completely different systems, I've noticed a
tendency for the kernel to do weird things with the PS/2 drivers (system
slows down, gets choppy, and even silently resets). This last time, I
pulled the plugs for the PS/2 ports and the system returned to normal.
(The chipset fan was overworking itself, so I had *some* clue where to
look.)

There can be many reasons why a system is 'choppy', and it's not always
the scheduler. Sometimes it's the interrupt handler dealing with some
device that's gone haywire. Sometimes it's the block layer not doing disk
I/O very nicely or a server process being very inefficient. Sometimes it's
an application that's gone braindead. And if a scheduler can be developed
that smooths out the choppiness in single- and dual-core systems, great!
Go for it! An older single-CPU system may never be fast, but it ought to
run smoothly under normal user operations.

The scheduler has gotten better over the past 15 years. And it will
continue to improve. But apps have to improve as well and not always
assume the 'system' will take care of everything.

As Ingo says, 8-core systems aren't mainline. But they will be. Perhaps
Con is looking to improve today's mainline systems, not tomorrow's. Is
this apples v. oranges? Or is it ain't? Mayhap never the twin shall meet.
But all parties involved should strive to keep the discourse civil and
positive.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 6:39 UTC (Tue) by mingo (subscriber, #31122) [Link] (7 responses)

Did that ever work satisfactorily in practice though?

Yes. (See my other post about nice levels in this discussion.) If it does not it's a bug and needs to be reported to lkml.

There's also the /proc/sys/kernel/sched_latency_ns control in the upstream scheduler - that is global and if you set that to a very low value like 1 msec:

    echo 1000000 > /proc/sys/kernel/sched_latency_ns

you'll get very fine-grained scheduling. This tunable has been upstream for 7-8 kernel releases already.

If it did why are people still cranking out different scheduler for desktops?

Primarily because it's fun to do. Also, in no small part because it's much easier to do than to fix an existing scheduler (with all its millions of current users and workloads) :-)

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 12:30 UTC (Tue) by i3839 (guest, #31386) [Link] (6 responses)

Weird, I don't see /proc/sys/kernel/sched_latency_ns. After reading
the code it's clear it depends on CONFIG_SCHED_DEBUG, any reason for
that? It has nothing to do with debugging and the code saved is minimal.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 8, 2009 12:37 UTC (Tue) by mingo (subscriber, #31122) [Link] (5 responses)

Please send a patch, i think we could make it generally available - and also the other granularity options i think. CONFIG_SCHED_DEBUG default to y and most distros enable it. (alongside CONFIG_LATENCYTOP)

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 9, 2009 8:42 UTC (Wed) by realnc (guest, #60393) [Link] (1 responses)

I've tried those tweaks. They don't really help much.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 10, 2009 9:53 UTC (Thu) by mingo (subscriber, #31122) [Link]

Thanks for testing it. It would be helpful (to keep reply latency low ;-) to move this to email and Cc: lkml.

You can test the latest upstream scheduler development tree via:

http://people.redhat.com/mingo/tip.git/README

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 9, 2009 11:50 UTC (Wed) by nix (subscriber, #2304) [Link] (1 responses)

I thought CONFIG_LATENCYTOP had horrible effects on the task_struct size and people were being encouraged to *disable* it as a result?

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 10, 2009 9:56 UTC (Thu) by mingo (subscriber, #31122) [Link]

It shouldnt have too big cost unless you are really RAM constrained. (read running: a 32 MB system or so) So it's a nice tool if you want to see a general categorization of latency sources in your system.

latencytop is certainly useful enough so that several distributions enable it by default. It has size impact on task struct but otherwise the runtime cost should be near zero.

BFS vs. mainline scheduler benchmarks and measurements

Posted Sep 10, 2009 19:35 UTC (Thu) by i3839 (guest, #31386) [Link]

I'll try to send a patch against tip later this week, not feeling too well at the moment.