Interview with Con Kolivas (APC)

It could be that the kernel hackers don't have great incentive to improve desktop responsiveness, because it already is superior to the main competition.

Con's interview seems a little bit like complaining. He couldn't get his patches into the kernel, so he is sad and angry. That is understandable. However as far as I can tell, Ingo's CFS is actually superior to Con's staircase scheduler. I think the mature thing for Con to do would be to continue his involvement in the kernel. It isn't an all or nothing game.

(On the other hand, I see how it must be extremely hard and frustrating to do it on an 100% voluntary basis in your free time)

I didn't believe what you said, so I set out to prove it myself. I was actually rather surprised at the results, though I still think you're exaggerating.

The labels on the left say which IO scheduler was used. The first column below is the time taken for oowriter by itself to start. The next column is oowriter startup time with dd running copying a 4 GB DVD image from /dev/sda to /dev/sdc (SATA). The third column is the same test, except with the dd process running at nice -n +19

Anticipatory     13s    154s   135s
CFQ              11s    200s    90s

Note that for all tests over 95 seconds or so, the dd was run in a loop because it completed in about that amount of time.

The machine is an Intel Core 2 Duo 2.4 GHz with 2 GB of RAM and 2 Seagate 400 GB hard drives on a 2.6.21.5 SMP kernel with preemption (including BKL) and RT mutexes. All tests were run after clearing the page cache using /proc/sys/vm/drop_caches

The same tests with xterm instead of OpenOffice give:

Anticipatory      4s     25s    22s
CFQ               5s     50s    50s

So therefore, I think your 5 minute claim is wrong. However, I do see 10x slowdowns, sometimes 20x with CFQ.

The response time of a the machine when a disk bound is running task is a major issue. To the extent that in 2.6.8, you could literally kill a machine with a mke2fs because it flooded the block cache, invoking the OOM killer which then took out some important process or other. It doesn't do that with newer kernels, but it can still delay the start up of vi by a minute or two.

Think about it. A single mke2fs, nice'ed to 19, can bring a 4 CPU machine to its knees. You can tell the CPU scheduler you want mke2fs to only take a small percentage of the available CPU time, but apparently there is no way to tell the IO scheduler its not allowed hog 95% of memory by swamping the block cache. Yuk!

Hardware is cheap as dirt nowaday, but still can't find much motivation to upgrade my Duron 1300 and 256 MB ram. Listening to other people's complaints it almost seems that the more ram and the faster your cpu the slower the system is. ;-)

Yeah, money talks, as always. If/when we see more acceptance of Linux on the desktop, things may indeed change.

Chicken and Egg though. It's widely known that firefox, for example, works much better under Windows than Linux. Until there's a compelling case that The Desktop is obviously better under Linux than Windows, there won't be the numbers, and until there are the numbers, the kernel devs won't be inclined to do the work to make it better.

Think of your processor as if it's a black hole.

Wafers are getting bigger and purer. Fab processes are getting faster and smaller. You just have SO MANY TRANSISTORS. They got so many that they are throwing 4 or more cores on a single die.

Intel has a research processor that has 80 cores on it.

WTF is any desktop going to do with 80 cores? Sure 2 cores is great, and 4 is pretty good. 8 is so-so, but your looking at 32 or 64 cores you simply are not going to see any improvement in performance! So what is happening is that all the functionality of your computer is just going to get sucked into that processor, piece by piece. Your video card, your wifi, your north bridge, your sound midi, your modem, etc etc etc.

It's cheaper, faster, more reliable, more energy efficient.

> They caught up because of specialized hardware, specifically 3DFX cards and sound cards

Physics acceleration? It's a joke.

Sound card acceleration? It's dead and dying, killed by it's own patents. You can blame Creative for that one. Wait till their patents dry up then you'll see real innovation in realistic 3D sound. It'll be all software, though.

3d Acceleration? The movement is torwards cpu cores of different types, specialized for specific workloads.

State of the art "hardware acceleration" graphics nowadays for video graphics is you take proprietary shader language and you compile it into to binaries to run on your GPU. Sounds familar? Doesn't sound like 'hardware acceleration' to me, it sounds more like regular old software on a special cpu.

If it wasn't for the fact that ATI and Nvidia were such A-holes about their 'IP' we would be compiling are software to run on both the CPU and on the GPU. GCC would decide which would be faster and you would be able to use that massive amounts of memory bandwidth for something actually useful.

ATI and Nvidia are heading towards GPGPU. Intel is heading towards media optimized x86-like cores. Either way it will be faster and be useful for so much more then current video cards are used for.

Hardware raid? Software raid is faster... eventually it will be better.

---------------------

Modern OSes are bloated, no doubt about that. But the solution isn't hardware.. the solution is fixing the OS.

The Linux kernel is already kick-ass. Sure it has issues, but it's still better then OS X's kernel or Window's kernel or Solaris's kernel. It's best there is for what it does well. If Linux devs can figure out solutions to the remaining driver issues and fix userspace-to-kernel ABI/API breakage issues then there will be almost no reason to use anything else.

For this I think embedded development is helping a lot. You can spend all day banging your head against the Linux kernel, but it won't compare to fixing some memory usage issues with GTK in terms of positive impact.

Projects like Maemo for the Nokia N800 or OpenMoko for Neo1973 were you have a nearly full Linux install with X, networking, GTK/Gnome, and Linux work well on a hand-held device is hugely positive. I think things like that are eventually going to help improve desktop performance considerably....

If Gnome can be made to run well on a phone with 128megs of ram, 64 megs worth of flash drive, and a 300mhz ARM cpu then it's going to kick ass on a modern desktop. This sort of thing is probably the most important thing right now, I think.

Hopefully KDE4 will be everything they promise it will be...

any way to reset those stats?

Yeah: you can reset them on a per-task/thread basis by writing 0 to the /proc/[PID]/sched file. Then they'll go down to 0. (Unprivileged users can do it to, to their own tasks. root can reset it for everyone.)

You can reset it periodically as well if you want to sample/profile their typical sleep/block behavior.

So assuming that these values are in nanoseconds, ksoftirqd waited at most 111 ms before it could finally run, and X 81 ms.

Yes, the values are in nanoseconds. What priority does it have? [the prio field in /proc/[PID]/sched file] If it's niced to +19 then a longer delay is possible because other, high-prio tasks might delay it.

Anyway, when hunting for latency spikes, sluggish apps and similar creatures, I guess the se.wait_max and se.block_max are most interesting?

Yes. There's also se.sleep_max - that's the maximum time the task spent sleeping voluntarily. ('se' stands for 'scheduling entity' - a task here)

block_max stands for the maximum involuntary delay. (waiting for disk IO, etc.)

wait_max stands for the maximum delay that a task saw, from the point it got on the runqueue to the point it actually started executing its first instruction.

Note that for multithreaded apps such as firefox all the worker threads are not in /proc/[PID]/sched but in /proc/[PID]/task/[TID]/sched. Often firefox latencies are in those threads not in the main thread.

If people are expected to ever use these knobs, it might be good to document what those wakeup and stat variants are, and the meaning of sched_features. When that's done all fields are easy to understand.

Yeah, i'll do that. _Normally_ you should not need to change any knobs - the scheduler auto-tunes itself. That's why they are only accessible under CONFIG_SCHED_DEBUG. (But it helps when diagnosing scheduler problems that you can tune various aspects of it without having to reboot the kernel.)

One other interesting field is sum_exec_runtime versus sum_wait_runtime: the accumulated amount of time spent on the CPU, compared to the time the task had to wait for getting on the CPU.

The "sum_exec_runtime/nr_switches" number is also interesting: it shows the average time ('scheduling atom') a task has spent executing on the CPU between two context-switches. The lower this value, the more context-switching-happy a task is.

se.wait_runtime is a scheduler-internal metric that shows how much out-of-balance this task's execution history is compared to what execution time it could get on a "perfect, ideal multi-tasking CPU". So if wait_runtime gets negative that means it has spent more time on the CPU than it should have. If wait_runtime gets positive that means it has spent less time than it "should have". CFS sorts tasks in an rbtree with this value as a key and uses this value to choose the next task to run. (with lots of additional details - but this is the raw scheme.) It will pick the task with the largest wait_runtime value. (i.e. the task that is most in need of CPU time.)

This mechanism and implementation is basically not comparable to SD in any way, the two schedulers are so different. Basically the only common thing between them is that both aim to schedule tasks "fairly" - but even the definition of "fairness" is different: SD strictly considers time spent on the CPU and on the runqueue, CFS takes time spent sleeping into account as well. (and hence the approach of "sleep average" and the act of "rewarding" sleepy tasks, which was the main interactivity mechanism of the old scheduler, survives in CFS. Con was fundamentally against sleep-average methods. CFS tried to be a no-tradeoffs replacement for the existing scheduler and the sleeper-fairness method was key to that.)

This (and other) design differences and approaches - not surprisingly - produced two completely different scheduler implementations. Anyone who has tried both schedulers will attest to the fact that they "feel" differently and behave differently as well.

Due to these fundamental design differences the data structures and algorithms are necessarily very different, so there was basically no opportunity to share code (besides the scheduler glue code that was already in sched.c), and there's only 1 line of code in common between CFS and SD (out of thousands of lines of code):

  * This idea comes from the SD scheduler of Con Kolivas:
  */
 static inline void sched_init_granularity(void)
 {
         unsigned int factor = 1 + ilog2(num_online_cpus());

This boot-time "ilog2()" tuning based on the number of CPUs available is a tuning approach i saw in SD and i asked Con whether i could use it in CFS. (to which Con kindly agreed.)

The non-soft-NX parts look mergeable at least to my eyes.

In Linux we reject _lots_ of code, and that's the only way to create a quality kernel. It's a bit like evolutionary selection: breathtakingly wasteful and incredibly efficient at the same time.

In general, evolutionary algorithms have never had a serious breakthrough because turning on your brain (as long as one is involved) tends to produce much better results. The bottom line is: evolutionary selection is just wasteful, period. That after billions of years of mindless tinkering something interesting results doesn't mean that it is "efficient".

Back to the linux kernel, it seems to me that the fundamental human problem behind kernel development is that stuff has to get "approved" and merged in. If there was an easy way to keep changes separate, that didn't imply intense maintaining efforts, none of this would happen. We would have dozens of schedulers and VMs, the best would be used most, progress would be very fast, and there would be less fights and frustration.

The fact that good, motivated people that have a positive impact are leaving in frustration is not good at all. Please stop rationalizing it.