BFS: A Kernel Patch (new ‘Task Scheduler’) that Improves the ‘Responsiveness’ of your Desktop computer

Every operating system has a special kind of software that communicates directly with your computer’s hardware which is known as the ‘Kernel’. It’s actually a set of software tools, and not a single utility. And one of the important tools inside the Kernel is called the ‘Task Scheduler’.

It’s purpose is pretty simple (though the overall process is complex), and that is to help the OS or the user run multiple processes (multitasking) as ‘smooth’ as possible. When you run a process, the Kernel assigns it with a value called ‘nice’, which resembles how important that process is (from the user’s point of view). Then the scheduler uses this information for deciding how much CPU time it should give to that process (a process with a high ‘nice’ value will get more CPU time and a lower value means less CPU time) and the ‘nice’ value can either be a static or a dynamic one as well.

For example, let’s say that you were using your web browser and had an audio track playing from the background and later you double clicked to open the word processor.

Then the OS task scheduler would make the logical conclusion that, it’s still important to continue a smoother audio playback (duh :D) so it might not change its priority but, it might reduce the priority of your web browser (here a ‘dynamic nice’ value is used) because now you’ve selected the word processor instead (= you’re interested in the word processor not the web browser).

CPU says: ‘Anything else you want me to run?, moron!’ 😉 …

But, while the word processor is opening, if you selected the web browser’s window again, then the task scheduler will consider now it too has become an important application and will raise its priority in its ‘queue’ (it keeps a queue for running apps) and might lower the priority of the word processor loading activity.

However, one of the biggest drawbacks of task scheduler designing is the lack of communication between the applications and the task scheduler, which otherwise can really improve the efficiency.

For example, let’s say that you were playing a video file (while browsing the web) and decided to minimize it. Now if, the scheduler could know that the media player is minimized then it can reduce the priority of the video decoding (because the user isn’t watching it) and lower the CPU load but, will still keep decoding the audio track, by based on the conclusion that, the user hasn’t paused the playback (only minimized it), so he/she is still would like to hear the audio track.

I honestly don’t know if this level of efficiency is achievable yet, but some experts have suggests to overcome these issues by implementing better communication techniques between the applications and the scheduler so it can act accordingly thus increasing the efficiency …

Anyhow, the default task scheduler that comes with GNU/Linux these days is called ‘CFS’ (Completely Fair Scheduler) and it’s a ‘conservative’ one and is not optimized for a certain computing environment. But, because it’s carefully designed it’s a very effective one that can be used under any situation (Sever, Desktop, Laptop, Mobile phones, Tablet PCs etc).

But, ‘Con Kolivas’, a Kernel hacker, after seeing some of the ‘flaws’ of CFS (again, because it’s not aggressively optimized for a certain computing environment), well, in his own words

‘… the mainline kernel (Edit: ‘CFS’) was relatively reassuring in that the scheduler behavior was much better than what was in earlier kernels. However, it didn’t take long before I started being disappointed in that too.

Random stalls in mouse movements, keypresses … unpredictable behavior all around were exactly what I was hoping had gone away. So I threw it all out and wrote … BFS.

… it is a desktop orientated scheduler, with extremely low latencies for excellent interactivity by design …’

‘BFS’ or ‘Brain Fuck Scheduler’ (yep that’s what it’s called :D) is a slightly different task scheduler that’s optimized for Desktop/Laptop users (or any PC where the ‘load’ isn’t at its extreme levels, unlike in a ‘Server’) and when comparing with the CFS, according to numerous testings done by experts show that, generally, it has a tendency to improve the performance and most importantly the ‘responsiveness’ while multitasking.

It’s also known to outperform CFS while Gaming with noticeable improvements in performance as well.

Now, I did test it using a benchmark program called ‘lbench’. But please remember that I don’t have the equipment and an extremely through understanding about the subject (to be honest), thus these ‘claims’ might not be extremely accurate.

But the rest assured, when running few multiple applications (while them buggers using my CPU about 90-100% for instance :D), I did notice a slight improvement on individual application ‘responsiveness’, not always necessarily the performance. Then again, most of the time, applications too seemed to be opening a bit faster under BFS.

This is what I did …

I installed BFS and booted into the ‘BFS’ Kernel in Ubuntu 12.04 Precise Pangolin LTS. Then used ‘lbench’ and ran few tests (my CPU ‘Intel® Core™ i3-2330M’ with 2 multi-threaded cores and 4GB of RAM) for about 20 seconds (each test) and then did the same by using the ‘CFS’ Kernel, included by default in Ubuntu.

Thanks to a PPA provided by ‘Daniel Hollocher’, you can install the BFS scheduler in Ubuntu 12.04 Precise Pangolin, 11.10 Oneiric Ocelot, 11.04 Natty Narwhal and 10.10 by opening your Terminal and entering the below commands.

sudo add-apt-repository ppa:chogydan/ppa

sudo apt-get update

sudo apt-get install linux-image-generic-ck linux-headers-generic-ck

Then, simply reboot your PC and you should see a new entry at the GRUB boot loader for booting using the new Kernel (including an option to choose the ‘old/default’ Kernel that comes with your Ubuntu).

So what I did was, I used ‘lbench’ and ran multiple threads (=programs, not highly accurate in technical terms, but you get the general idea) simultaneously in 4 tests (with each test increasing the simultaneously running programs/threads) and measured how fast my CPU could ‘switch’ between threads/programs within a second (called ‘Context/Thread switch rate’).

What is a ‘Context/Thread/Process Switch’?

Let’s say that you’re running two programs (‘A’ and ‘B’) at the same time using a CPU that has a single core. Then what it does is, it’ll run the program ‘A’ for certain period and then ‘pause’ it, ‘switch’ over to the program ‘B’ and run it for few seconds. Then, it’ll ‘pause’ running ‘B’ too and come back to ‘A’ and ‘resume’ from where it stopped in the last attempt (it’ll do this again and again).

This is what’s really happening but the CPU does it so fast that for the user it looks like the two programs are actually running at the same time.

The technique used for ‘pausing’ a program and ‘resuming’ it later is called ‘Context Switching’. So in plain words :), a ‘Context Switch rate’ of ‘900’ means that, for that second, your CPU had switched between applications 900 times.

Now, since you have a basic understanding what ‘Context Switching’ means, let’s move over to the so called ‘test results’ ….

1. First, I benchmarked the CPU performance by running two ‘threads’ and the average reading for BFS the was ‘16531800’ and CFS scored ‘5991579’.

2-Threads-running-in-BFS  2-Threads-running-in-CFS

2. Then I ran the same test using 4 threads (=4 programs) and for BFS the reading was ‘4001471’ and CFS scored ‘4110781.

4-Threads-running-in-BFS  4-Threads-running-CFS

3. The third time I used 8 threads and the reading for BFS was ‘4135213’ and CFS scored ‘3735574’.

8-Threads-running-in-BFS  8-Threads-running-in-CFS

4. In the last test, I used 9 threads (maximum allowed in ‘lbench’, I hardly ever used 9-10 programs at once as a ‘desktop/laptop’ user) and BFS reading was ‘4272928’ and CFS scored ‘3838191’.

9-Threads-running-in-BFS  9-Threads-running-in-CFS

As you can see, while running 2 to 9 programs at once, BFS outperformed CFS (except with 4 threads, it was slightly ahead of BFS) and switched between programs fast (extremely fast when running two threads, about 2.7 times faster than CFS switched between apps!).

Does it improve performance then?

Just because BFS switches between applications faster doesn’t mean it’ll give superior performance as far as I understand. Though it should improve the ‘responsiveness’, but the reason it being able to achieve such higher ‘Context Switch Rates’ (again, lower the load the better) is because it uses the CPU aggressively for running programs, and that should improve the performance and yes programs did seem to load faster under BFS.

How does fast ‘Context Switch Rates’ improve ‘responsiveness’?

Let’s say that you’re running two applications at the same time, a web browser, and a text editor that you use to copy text from web pages. Let’s also assume that the CPU is switching between each app once every second and you’re also switching between the two programs at the same rate.

So from the user’s prospective, he won’t notice a lag in responsiveness, because as soon as you switch over to the text editor, the CPU is also working on it at the same time (vice versa).

But, let’s say that the user decided to switch between the applications twice every second. Then he/her would notice a slight lack in responsiveness, because when you’re selecting the text editor for instance, the CPU hasn’t started to ‘work on it’ yet and is still busy running the web browser.

So, the only solution to improve the responsiveness is to increase application switch rate (‘Context Switch rate’).

Just like that, because BFS switches between applications faster than CFS, then for an any given second, the possibility of it being ‘working on’ the same application that you’re also about to ‘switch’ over to, is higher than with CFS, thus the CPU can quickly run that app according to your requests and the user will perceive it as an improved ‘responsiveness’.

Then again, faster ‘Context Switch Rates’ can improve the responsiveness but, if it’s too extreme, then it can hurt the overall performance & stability too.

Some also say that, if you have a mobile computer, then BFS might slightly shorten the battery life as it tries to get the maximum out of your CPU (= more power consumption). But I don’t think it’s true because BFS is also designed to run in mobile computers too and I haven’t seen any noticeable differences in my Laptop either. But as always, the best thing to do is to test it yourself.

It’s also being used in some of the popular GNU/Linux distributions such as ‘Zenwalks’ and ‘PCLinuxOS’ for instance and it is extremal stable too.

So as a closing note, if you’re a GNU/Linux desktop computer user who’s not happy with the performance under CFS (especially under gaming), then why not try BFS?, good luck (sorry about the long rambling ;-)).

An RHCE, 'Linux' user with 14+ years of experience. Extreme lover of Linux and FOSS. He is passionate to test every Linux distribution & compare with the previous release to write in-depth articles to help the FOSS community.

4 thoughts on “BFS: A Kernel Patch (new ‘Task Scheduler’) that Improves the ‘Responsiveness’ of your Desktop computer”

  1. You’re talking about millions of switches per second. You’re not going to notice a 1 microsecond difference in response time, even if the computer’s display refreshed that quickly. At 60 Hz (times per second, standard monitor refresh rate) there’s a whopping 16.7 milliseconds between frames. That’s 16,700 microseconds. Even CFS would have to be switching between 1,000 applications to even come close to that delay.

    Context switches are a very expensive operation. In fact increased context switching would REDUCE performance, because now you’re spending more CPU time doing context switches, instead of doing usefull work actually running the programs.

    The best way to increase scheduler performance is to switch between programs smarter, not faster. Basically your results here are misleading, and mostly irrelevant.

    A little bit of research reveals that the BFS aims at being a simpler scheduler that uses less resources to determine which applications to run when. I imagine that’s most of the reason BFS performs better.

    • Hi Nolan,

      I understand that, and what you’re saying is true up to a point. But remember that I never claimed BFS improved the performance with absolute certainty (although some tests from ‘Phoronix’ have shown FPS increase in games while running using BFS).

      Anyhow, I don’t think the purpose of BFS is to improve the performance, but to enhance the Responsiveness, and that’s what I tried to show.


Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.