[Nexus S Android Development] biergaizi:
Q&A:

What is a scheduler?

Your computer often has 1-8 CPUs only, a CPU can do one thing in one time only. But you can run 500 processes on it. Why? Because scheduler switches processes. For example, You have 1 CPU only, and you opened 100 processes, scheduler will let one process run some time, and interrupt it, then let the next process run. So, there is a single process running only. But CPU is very fast, and scheduler switches them quickly, so you can't feel it.

How long does the scheduler let one process run? Different schedulers have different answers. But all of them are using algorithms to schedule process rational.

The history of CFS & BFS?

5 years ago, there was a scheduler called CFS. It's a very high performance scheduler, so it replaced O(1) scheduler when it merged. Facts have proved that, it is really high performance, because it can use on a supercomputer with 4096 CPUs.

On a supercomputer, a priority is very important and useful. Because many people are connecting to the supercomputer and work on it, so, you must specify the priority to people, to share the resources fairly. CFS is this kind of scheduler: it has advanced priority system. Such as group scheduled, so we can specify the priority to every single user & usergroup.

But, Does the most people use the supercomputer??

For me, I still use a computer with legacy device: a Pentium M CPU sometimes. And I use SCMs, such as a MP3 player, or devices with ARM chips, such as routers, iDevices, and my Nexus S smartphone.

By design, CFS will use on everywhere. So, it can't optimize for the device you are use. For example, we still use a supercompuer to elaborate it: priority is important on the supercomputer, but how about on the SCMs or smartphones? There are only one user at the same time. But, CFS is trying to compute the priority of the users every second!! These things are useless on low-performance-devies, and cause the low performance. It really not optimized for the low-performance-devices.

So, Con Kolivas, the designer of CFS (he just wrote some paper for it, the developer is Ingo Molnár. He also is the developer of O(1), wroto CFS before Con Kolivas. Con Kolivas is very angry for that) wrote a new scheduler for low-performance-devices, called BFS, Brain **** Scheduler. Why Brain ****? Because it very easy and simple, and kind of stupid scheduler, but it can improve performance on low-performance-devices. It removed some "awesome" design, such as advanced priority, but a stupid and simple one, etc.

It really a bad scheduler for 8-core-systems, and a terrible scheduler for 16-core-systems. But a great system with single-core and dual-core. Con Kolivas said it will never be in to the mainline Linux kernel, because it isn't a general scheduler, but I will keep update for it outside the mainline kernel code.

But now, CFS is better than before too. Lots of people think, CFS is the winner now.

Tell me something about UKSM.

This is an improvement upon KSM.

Its new features:

1. Full system scan:

It automatically scans all user processes' anonymous VMAs. Kernel-user

interaction to submit a memory area to KSM is no longer needed.

2. Rich area detection:

It automatically detects rich areas containing abundant duplicated

pages based. Rich areas are given a full scan speed. Poor areas are

sampled at a reasonable speed with very low CPU consumption.

3. Ultra Per-page scan speed improvement:

A new hash algorithm is proposed. As a result, on a machine with

Core(TM)2 Quad Q9300 CPU in 32-bit mode and 800MHZ DDR2 main memory, it

can scan memory areas that does not contain duplicated pages at speed of

627MB/sec ~ 2445MB/sec and can merge duplicated areas at speed of

477MB/sec ~ 923MB/sec.

4. Thrashing area avoidance:

Thrashing area(an VMA that has frequent Ksm page break-out) can be

filtered out. My benchmark shows it's more efficient than KSM's per-page

hash value based volatile page detection.

5. Full Zero Page consideration(contributed by Figo Zhang)

Now uksmd consider full zero pages as special pages and merge them to an

special unswappable uksm zero page.

How to tweak UKSM?

http://kerneldedup.org/en/projects/uksm/uksmdoc/usage/

You are just add BFS patch to Air kernel, the kernel is useless, everyone can do it!!!

Yes, I am a patcher and a compiler. Some kernel in XDA, also just add some patch and small hack to improve proformance. And users will not compile their own kernels, right? I'm doing the same thing. I will do more work soon.