今天抽空小研究了下传说中的CFS，顺便也看了一下BFS和以前的O(1)调度，再加上一点LKML上的八卦事，在这里扔点notes。

kernel 2.4之前一直用的某种O(N)调度算法，大概就是所有的cpu用1个全局的link list，也用一个超大的lock来做保护，这种坏处就不说了。

后来一个叫Ingo的人进入了kernel的dev，提出了O(1)算法，每个cpu都有一个run queue，O(1)算法就是我们在早年各种kernel书里必介绍的算法了，每个进程都有一个time slice，然后用完了就要被deschedule了。

再后来，CK大人(Con Kolivas)07年的时候提出了Rotating Staircase Deadline算法，基于Packet Switching中常用的fair queueing。这也就是大名鼎鼎的ck补丁(部分)，但没能成功被kernel接纳。关于fair queueing可以参看wikipedia。

之后Ingo在这个基础上写了CFS, Completely Fairness Scheduler。Ingo也是个牛人，他花了62个小时就写出了100k的CFS patch并且release了出去。当然CK大人就很不高兴了，于是在mailing list上有过一番争吵，然后CK似乎酒销声匿迹了。

CFS主要是用了virtual runtime的概念(对应fair queueing里的virtual time)，每个进程都有维护一个vruntime，scheduler总是挑最小的那个switch过去。在每个时间中断时更新当前进程的vruntime值，vruntime+=ticks / weight，weight值根据nice值来确定的，是一个指数关系。一旦当前运行的进程不再是最小的vruntime，就会进行scheduling。数据结构CFS采用的是Red-black Tree，O(logn)复杂度，但又维护了一个变量保存left-most节点也就是queue里最小的vruntime。另外Ingo在写的时候对scheduler做了模块化，有个sched_class的structure，里面就是各种函数指针 orz。慢慢的，CFS就是我们现在的默认scheduler了。

关于CFS有些挺有用的资料：
1. 一个介绍的ppt: http://www.linux-foundation.jp/jp_uploads/seminar20080709/lfjp2008.pdf
2. http://www.ibm.com/developerworks/linux/library/l-cfs/index.html
3. Mailing list的一些讨论: http://kerneltrap.org/node/8208
4. Kernel代码里 Document/scheduler/sched-design-CFS.txt 和 kernel/sched_fair.c

两年之后，CK大人再次出山，带来了BFS，Brain Fuck Scheduler。CK认为现在的Scheduler包括CFS用在个人电脑上浪费了太多的cpu在处理scheduling和cpu load balance（kernel要支持4096个cpu）。BFS用了超简单的算法，来获得在并没有那么多核时的性能突破。BFS就是一个全局的List，一个lock(不算realtime的100个list和另外两个和算法关系不大的list)，复杂度O(n)。BFS也是借鉴fair queueing，使用virtual deadline = jiffies + (prio_ratio * rr_interval)作为time slice，一个进程用完之后就不得不被schedule了。rr_interval是可配置的参数，CK在document里还给出了一些指导。

在CK发布没多久，Ingo同学就在Mailing list里发布了他对bfs的一些评测，但他错误的采用了公司非常nb的测试机，跑出来的结果不那么优秀。但用户们普遍反应在双核和四核机器上性能提升显著。

CK在FAQ里的几句话很有意思，用来作为收尾吧。改天有空我得去试试这个补丁 😀

Why “Brain Fuck”?

..
Because it’s designed in such a way that mainline would never be interested
in adopting it, which is how I like it.
..
Because it throws out the philosophy that one scheduler fits all and shows
that you can do a -lot- better with a scheduler designed for a particular
purpose. I don’t want to use a steamroller to crack nuts.
..
Because I must be fucked in the head to be working on this again.
I’ll think of some more becauses later.