适用于桌面应用的Linux调度器BFS/MuqSS

粉浆里面有粪，猪血里面有shi。

大家都知道Linux内核task调度器经历了$O(n)$，$O(1)$调度器，目前是CFS，期间也出现了几个优秀的候选调度器，但最终都没能并入内核，我们只能从一些零散的patch和文章中知道它们的存在。

但Linux内核的世界乃是非常之宽广，在主线内核之外还有很多支线可供观摩。

Linux内核其实有很多支线分支，其中Linux-CK就是著名的一支：
https://wiki.archlinux.org/index.php/Linux-ck
该支线由Con Kolivas维护，所以称之为CK(并非内裤哦…)。

Con Kolivas的信仰是 万事不能一刀切，没有放之四海而皆准的真理！ 所以，他主要关注Linux桌面，他不相信存在one-size-fits-all的调度器，所以他设计了专门适用于桌面交互的BFS。

BFS不是一个普适的task调度器，相反，它仅仅适用于桌面交互的环境。所以，为你的水冷游戏机使用BFS，而不是在携带众核CPU嗡嗡作响的2U服务器上使用它。

MuqSS则是BFS的改进版。MuqSS的全称是 Multiple Queue Skiplist Scheduler 。

有必要先介绍一下什么是BFS，然后我们看MuqSS进行了什么改进。

简单来讲，BFS是一种向$O(n)$算法的回归，Con Kolivas认为：

• 桌面系统的task数量不会太多。
• 对于主线内核的调度算法太复杂。

基于这种认知，Con Kolivas设计了BFS。他认为 让一个支持4096个CPU的调度器去调度桌面交互应用的task是错误且可笑的做法 ，下面的BFS宣传漫画说明了这一点：

和BFS不同，BFS是在全局的链表中遍历找VD最小的task，而MuqSS则遍历每CPU链表的表头查找VD最小的task。

之所以要遍历所有CPU的Skiplist上的表头，是因为每次查找操作均要找到一个全局最优解，这样也就消除了主动负载均衡的必要，极大降低了算法的复杂性。

时间复杂度同样都是$O(n)$，但MuqSS的$n$指的是CPU数量而非task数量。我们看一下MuqSS选择task算法相比BFS的改进：

我们再看下最新的版本中选择task的实现，它实现了查找过程的无锁化，代价只是稍微损失了全局最优的准确度：

完整的代码请参见下面的链接：
http://ck.kolivas.org/patches/muqss/5.0/5.2/0001-MultiQueue-Skiplist-Scheduler-version-0.193.patch

关于BFS以及MuqSS的核心原理就介绍到这里。关于MuqSS更详细的信息，出了上述给出的源码链接之外，其本身的Doc以及Lwn文章也是值得一读：
Doc： http://ck.kolivas.org/patches/muqss/sched-MuQSS.txt
Lwn：https://lwn.net/Articles/720227/

接下来我们看看作为Linux Kernel patch的BFS，MuqSS是怎样一种存在。

Linux内核的调度器并不是可插拔的，内核中不存在sched_class的任何注册接口和替换接口，这意味着如果你想实现自己的调度器，会非常麻烦。

当然，最直接的方式就是直接修改内核源码了，Con Kolivas便采用了这个方法从而分裂出了自己的分支，你可以在下面的链接找到他的patch：
http://ck.kolivas.org/patches/

MuqSS调度器是通过直接修改schedule函数实现的：

由于MuqSS是专门针对桌面交互应用设计的调度器，而Linus本人则不认同主线内核中的任何专门化的定制设计，因此可以预见Con Kolivas的patch很难合