Thursday 3 November 2011

3.1.0-ck1, BFS 0.414

I finally found enough time to sync up BFS with the latest 3.1.0 linux kernel. In keeping with the fact that there are some changes to support new scheduler features in linux-3.1, and the general code churn that happens on every release, the version number is updated from the last 0.413 release but from the user perspective it should behave identically. There were some build fixes pending and one bug involving displayed hard interrupt usage that were fixed. Overall most users should notice no significant change.

Apply to linux-3.1.x:

Closely following on with syncing up with the latest kernel is an updated -ck kernel which is almost identical, apart from relaxing the swappiness from 0 to 10. Some very low ram users reported the virtual memory subsystem tried so hard to not swap anything at 0 that they experienced stalls while the VM twiddled its thumbs screwing around so I've relaxed the value to 10 which avoids these stalls and should still be quite aggressive at avoiding swapping.

Apart from that the -ck patch is a resync from the last 3.0.0-ck1 release:

Directory containing combined ck1 patch and separate patches:

With the recent hacking it has become a lot harder to get a account and as I would have great difficulty getting a gpg key personally signed by any other kernel developer in my area it could be a while before I can set up an account there again. So I've decided to just use my own storage once more instead of putting it on Unfortunately I don't have quite a few of the older -ck kernels since I never bothered to upload them there. I foolishly thought that storage would be permanent cloud storage for them so I don't even have a copy of many of them. If someone has archived the 2.6 -ck patches, or has an old mirror of please forward them on to me.


EDIT: A few bugs are showing up in this latest BFS release, and I'm currently accumulating fixes fort them and putting them in the directory listed above for ck1. There will be a ck2 soon to follow with all the fixes.


  1. tested is aproved :)

  2. Ubuntu packages are welcome :)

  3. Tested and build fine.
    install on test server and work fine.

  4. @ck: There is a mirror of your patches in

  5. In the function earliest_deadline_task you take the rq->preempt task before any other task in the global runqueue, even before realtime tasks, like the ones with SCHED_IDLEPRIO. Wouldn’t it make better latencies if it would be looked up if there is a realtime task and then look at the rq->preempt.

  6. @ck have rsync mirror too



  8. When I started the kernel with the BFS patch for the first time, it directly went into panic. I wasn't able to catch exactly the output. But I can say it is related to the scheduler, because in the call-trace, there was resched_closet_idle and other scheduling related functions.
    I tryed to reproduce the problem, but now everything is working fine.

  9. Thanks for the links.

    @Anonymous: The prerequisites for a task being flagged as rq->preempt_task are exactly the same as those for being selected in earliest_deadline_task, in the preemption function. Picking it before all other tasks in edt() is done precisely to avoid going through the same tests for no reason.

  10. Thanks ck!

    $ dmesg | grep BFS
    BFS CPU scheduler v0.414 by Con Kolivas.

  11. I could reproduce the problem.

    general protection fault: 0000 [#1] SMP

    Process fsck.ext4 (pid 688,...

    Call Trace:
    ? vfs_read+0x10d/0x180
    ? sys_read+0x4a/0x90
    RIP resched_best_mask+0x30/0x150

    Tested with Ubuntu 64 bit 10.10 on a Intel core i7 2600K

  12. Thanks!

    If you could reproduce it with the full debugging options that would be far more useful.

    General setup --->
    [ ] Configure standard kernel features (expert users) --->
    -*- Load all symbols for debugging/ksymoops
    -*- Include all symbols in kallsyms

    Kernel hacking --->
    [*] Kernel debugging
    [*] Compile the kernel with debug info
    [ ] Reduce debugging information
    -*- Compile the kernel with frame pointers

  13. Im looking forward to do this.
    Is it OK when I make a picture of the screen and send it to you via email.

  14. The usual make benchmark of 3.1 vs. 3.1 + ck1 (bfs v0.414).

    Statistically significant increase in make performance. The above was on a dual quad machine with 16 threads running "make -j16 bzImage" of linux v3.1

  15. [Ralph Ulrich]

    Also here runs better then vanilla linux-3.1, also patched with 178 patches of Greg KH queued stable release:
    Mac-Mini of 2009 core2, 64bit Gentoo unstable, using gcc-4.6.2

  16. @graysky

    Statistical significance adds to credibility. It is not, however, a measure of improvement! Always start from reporting deltas or relative speedup.

    But since you've started talking about statistics, you should notice that the distributions are clearly skewed and simple ANOVA is a bad idea. Do ranksum or U-test instead and, maybe, add AUC under ROC.

    The tails and the skewedness is actually very important here, because those tails result in random but noticeable stalls.

  17. @anon - I'm no statistician. I'd be glad to provide the dataset I collected to you if you're game for an analysis.

  18. I have some issues on atom-ck kernel from archlinux repo with uswsusp. Hibernation hangs just before the compression starts sometimes.
    Also if I choose bfs as elevator, sometimes I have to press some buttons (like shift,ctrl etc) to make system response to me while opening an application. :\

  19. @GG- dude, ck's blog is not the right place for this question. Start a thread on the forums. Also, bfs is not an I/O scheduler. You are confusing it with BFQ which isn't yet released for 3.1.

    My advice, build the linux-ck package from AUR and sort out your hibernation issue. If it is related to ck's patches, then post here.

  20. [Ralph Ulrich]
    @graysky, I take your benchmarkings as a reassurance there ire no regressions when applied to a new linux release! Also I know BFS is meant to reduce latency and you measure kind of throughput... Keep up benchmarking!

    Recently I saw the verb "latency" near profiling during "make menuconfig". Is there this cabability to measure in the kernel? I need to go into that further ....