Between the Mountains

Type: CPU Scheduler

Plateform: Linux

Website: http://ck.kolivas.org/patches/bfs/

Overview:

Brain Fuck Scheduler, which I will, from here on, abbreviate BFS to minimize obscenity in this post, is a Linux task scheduler offered as a patch for the Linux kernel.  It replaces the Completely Fair Scheduler built into the standard kernel [1].  From my, admittedly very superficial understanding of the operating system’s interaction with the CPU, the scheduler is responsible for determining which tasks are assigned to which CPU core, determining how the time on each CPU is split between the tasks, and for queuing tasks in memory for execution on the processor in order keep the processor busy [2].  BFS was written by Con Kolivas, an Australian Anesthesiologist, who apparently likes tinkering with deep operating system stuff in his spare time.  It is optimized for desktop performance on systems with small numbers of processors, as opposed to the standard Linux kernel which must support anything from my single-processor system to massively parallel super computers.  Kolivas was said to be inspired [3] to write BFS by the following comic:

Image © Randall Munroe, xkcd.com Used under Creative Commons Attribution-NonCommercial 2.5 License, hotlinked with permission

Install Experience:

The installation from source code was not trivial, but using a number of sources I was able to figure out what to do without a much compilation experience or any real understanding of the kernel source code.  The following description of my compilation of the kernel is as much for my own reference as anything else, but, if you find anything useful in it, that’s great.

The target system for this installation was my Lenovo T43, Type 2668 notebook with a Pentium M processor at 2 GHz.  This machine runs Ubuntu 10.04 (Lucid), originally with the 2.6.32 kernel.  My friend, Randy, helpfully suggested a guide for compilation of the Linux kernel on Ubuntuforums.org [4], which I more or less followed.  I obtained the standard kernel 2.6.34 source code [5] and the BFS patch for this kernel [6], extracting both tarballs and placing the single-file patch in the kernel source directory.  I navigated to this directory and issued the command

patch -p1 < patch-2.6.34-ck1

to apply the patch to the kernel [7].  Note that the character following “-p” is a numeral.  Although the compilation guide recommends placing the source code in /usr/src/linux-2.6.34 and soft linking /usr/src/linux to this, this entirely depleted my 2.6 GB of remaining disk space on my / drive before completing.  My my second and successful try to compile, I put the source code in a directory src on an external disk with 250 GB free space, which I assigned the same permissions, owner, and group as /usr/src and linked soft linked /usr/src/linux to that.  I have no idea how much space was actually used, but following completion, my source directory remains at just under 1 GB.  At step 11 of the guide [4], I found the identity of the kernel module supporting my wireless card by searching the output of dmesg for  “wireless”.  With xconfig open, I also unchecked the option for CONFIG_DEBUG_INFO upon advice that this would save disk space [8] and then pressed save in xconfig.

I let the compiler run overnight; I think it took about two hours.  I found the resulting deb files, not in /usr/src, but the directory above the one to which I had soft linked /usr/src/linux on my external drive.  Install of the deb files took a few minutes and the second resulted in an message that the “post-install script exiting due to error.  My kernel was installed successfully, but I had to run the command

sudo update-grub

before I could boot it [9].  However, I subsequently got the same error every time I ran the package manager which apparently tried to rerun the unfinished post-install script even though I wasn’t tinkering with the kernel package.  Reinstalling and then uninstalling the package nvidia-common via

sudo apt-get install nvidia-common
sudo apt-get purge nvidia-common

cleared up the issue [10], with the incomplete post-install script completing automatically after the second command, including the grub update which should have happened automatically with the kernel package installation.  It is notable that I have an ATI video card and no hardware by NVidia of which I am aware.  I’ve delinked /usr/src/linux from the source directory on my backup drive and haven’t encountered problems, but am holding on to the data.

GRUB2 responds to the “shift” key, held during boot, to produce a menu of bootable kernels.  This confused me since it was “escape” under GRUB.  It appears that GRUB boots the latest kernel by default, so in my case, upgrading from 2.6.32 to 2.6.34 in addition to the patch, my system boots automatically to the BFS kernel.

My Experience:

This upgrade really makes my single-core machine feel much more responsive.  Mouse and keyboard hangs pretty much eliminated, even under heavy processor load.  I have a Windows XP virtual machine which I use occasionally for the final preparation of technical documents which I am obligated to produce in MS Word format and the BFS kernel patch particularly shines while running Virtualbox [11].  Both the native applications on the host OS (Ubuntu) and guest OSs (Windows) share time nicely to make whichever I’m using at the time responsive, even while the other is working on something requiring processor time in the background.

Conclusion:

I’d recommend BFS to any desktop Linux user that has an inclination to ticker and has some familiarity with the packaging system and command line, particularly those running virtual machines.

References:

[1] Wikipedia, Brain Fuck Scheduler, http://en.wikipedia.org/w/index.php?title=Brain_Fuck_Scheduler&oldid=364967266, Accessed 13 June 2010

[2] Wikipedia, Scheduling (Computing),http://en.wikipedia.org/w/index.php?title=Scheduling_computing&oldid=366954349, Accessed 13 June 2010

[3] Linuxpromagazine.com, http://www.linuxpromagazine.com/Online/News/Con-Kolivas-Introduces-New-BFS-Scheduler

[4] ubuntuforums.org, Master Kernel Thread, http://ubuntuforums.org/showthread.php?t=311158, Accessed 12 June 2010

[5] kernel.org,  Linux Kernel 2.6.34 Source, http://www.kernel.org/pub/linux/kernel/v2.6/linux-2.6.34.tar.bz2

[6] kernel.org, Con Koliva’s kernel patch, http://www.kernel.org/pub/linux/kernel/people/ck/patches/2.6/2.6.34/2.6.34-ck1/patch-2.6.34-ck1.bz2

[7] http://www.linuxheadquarters.com/howto/tuning/kernelpatch.shtml

[8] http://tomoyo.sourceforge.jp/en/1.6.x/compile.html

[9] Ubuntuformus.org, “Grub 2 Basics”, http://ubuntuforums.org/showthread.php?t=1195275

[10] Ubuntuforums.org, “Kernel Installs, but …,” http://ubuntuforums.org/showthread.php?t=1274868 (See second post by user Ultima)

[11] http://www.virtualbox.org