关于FreeBSD和Linux调度器的一点业余考证

雨丝风片

这两天，看到多位朋友在这里就davidxu在FreeBSD引入的CORE调度器展开了讨论，讨论的内容无关调度器的设计细节，反而是这个调度器和Linux的O(1)调度器之间的微妙关系。用户本身是大可不必关心这个问题的，喜欢讨论的都应该是些对内核感兴趣的朋友。既然对内核感兴趣，讨论就不应该以形而上学的形式进行，多少还是要以代码等实际的东西来说话。我的这篇考证之所以称之为业余，是因为我之前并未专门研究过调度器，此番考证，纯属“视觉”扫描作品，各位如感兴趣，可进一步深究。

2006年6月13日，davidxu在合入CORE调度器代码的log中写到：

Add scheduler CORE, the work I have done half a year ago, recent,
I picked it up again. The scheduler is forked from ULE, but the
algorithm to detect an interactive process is almost completely
different with ULE, it comes from Linux paper "Understanding the
Linux 2.6.8.1 CPU Scheduler", although I still use same word
"score" as a priority boost in ULE scheduler.

看来，CORE调度器的确是参照Linux的O(1)调度器实现的。那么，Linux的O(1)调度器呢？真的是完全原创么？

我们来比较一下O(1)调度器和4.4BSD调度器。

首先比较一下两个调度器的核心数据结构，运行队列。这是4.4BSD调度器的运行队列：

这是Linux O(1)调度器的运行队列：

是不是觉得两张图很像？都是分优先级组织队列，在不同优先级的队列中再挂进程链表。我们再来看看他们的核心调度算法（为方便比较，仅列出代码框架）。这是FreeBSD中4.4BSD调度器的代码：

1. 
   
2.     while ((pri = runq_findbit(rq)) != -1) {
   
3.         rqh = &rq->rq_queues[pri];
   
4.         ke = TAILQ_FIRST(rqh);
   
5.     }
   

复制代码

这是Linux O(1)调度器的代码：

1. 
   
2.     idx = sched_find_first_bit(array->bitmap);
   
3.     queue = array->queue + idx;
   
4.     next = list_entry(queue->next, task_t, run_list);
   

复制代码

是不是觉得这两处代码也很像？都是先通过bitmap找到最高优先级的非空队列，然后取出队列上的第一个进程。

FreeBSD的4.4BSD调度器和4.4BSD的调度器设计思想一样，但代码变动很大，而我们所取的代码是在FreeBSD中的4.4BSD调度器代码。我们可以比较一下上述两段代码的出现时间：

FreeBSD中（采用上述算法）的4.4BSD调度器代码的合入时间是2001年的2月12日，作者为jake。
Linux的O(1)调度器代码的出现是在2002年的1月4日。

所以，从时间上来说，Linux的O(1)调度器代码的出现比FreeBSD中4.4BSD代码的相似算法晚了将近一年。

我的业余考证到此结束。仓促而成，等待各位感兴趣的和有研究的朋友予以指正。

一点感想：思想无国界。

geel

好好好好

isjfk

这两天风撕雨片兄在做这个...钩档？

assiss

不知道有谁研究过调试器的，是不是可以写一个BSD（现在各BSD调度器是否一样？）调度器发展、变革的历史简介？

雨丝风片

原帖由 isjfk 于 2006-11-16 21:13 发表
这两天风撕雨片兄在做这个...钩档？

不是这两天，是今天晚上。

雨丝风片

原帖由 assiss 于 2006-11-16 21:44 发表
不知道有谁研究过调试器的，是不是可以写一个BSD（现在各BSD调度器是否一样？）调度器发展、变革的历史简介？

好主意！小g同学前段时间就专攻过调度器。

gvim

Orz

jervis0211

雨丝风片

在KernelTrap上看到了对Linux O(1)调度器的作者Ingo Molnar的访谈，摘录其中相关的内容如下。全文另开新贴：
http://bbs.chinaunix.net/viewthr ... &extra=page%3D1


JA: Your most recent contribution to the Linux kernel was the O(1) scheduler, merged into the 2.5 development tree in early January. When did you first start working on this project and what was the inspiration?

Ingo Molnar: one of the core ideas used within the O(1) scheduler - the using of two sets of priority arrays to achieve fairness - in fact originates from around 1998, i even wrote a preliminary patch back in those times. I couldnt solve some O(N) problems back then so i stopped working on it. I started working on the current O(1) scheduler late last year (2001), sometime in December. The inspiration was what the name suggests - to create a good scheduler for Linux that is O(1) in its entirety: wakeup, context-switching and timer interrupt overhead.

JA: Did you base the design on any existing scheduler implementations or research papers?

Ingo Molnar: this might sound a bit arrogant, but i have only read (most of the) research papers after writing the scheduler. This i found to be a good approach in the area of Linux - knowing about too many well-researched details can often confuse the real direction we have to take. I like writing new code, and i prefer to approach things from the physics side: take a few elementary rules and build up the 'one correct' solution, no compromises. This might not be as effective as first reading all the available material and then cherry-picking a few ideas and thinking up the remaining things, but it sure gives me lots of fun :-)

[ One thing i always try to ensure: i take a look at all existing kernel patches that were announced on the linux-kernel mailing list in the same area, to make sure there's no duplication of effort or NIH syndrome. Since such kernel mailing-list postings are progress reports of active research, it can be said that i read alot of bleeding-edge research. ]

......

JA: Have you worked with any other open source kernels?

Ingo Molnar: not really. I occasionally take a look at FreeBSD - some things they do right, some things they dont, in the areas i'm most interested in the Linux kernel is currently ahead both design-wise and implementation-wise. Finally we caught up in the VM subsystem as well, with Andrea's big and important 2.4 rewrite, Rik's great rmap code and Andrew's fantastic integration work. But what other answer would one expect from a Linux kernel developer? :-)

JA: FreeBSD 5.0 is due to be released around December of this year, with some significant changes to the kernel. Have you followed this development?

Ingo Molnar: not really. The things i sometimes do is to look at their code. Also, when i search for past discussions regarding some specific topic, sometimes there's a FreeBSD hit and then i read it. That's all what i can tell. But i do wish their kernel gets better just as much as the Linux kernel gets better, there needs to be competition to drive both projects forwards. (the Windows kernel is closed up enough so that it does not create any development stimulus for Linux (and vice versa). Rarely do any Windows features get discussed.)

JA: What areas of the Linux kernel do you think still lags behind FreeBSD?

Ingo Molnar: there were two areas where i think we used to lag, the VM and the block IO subsystem - both have been significantly reworked in 2.5. Whether the VM got better than FreeBSD's remains to be seen (via actual use), but the Linux VM already has features that FreeBSD does not have, eg. support for more than 4 GB RAM on x86 (here i guess i'm biased, i wrote much of that code). But FreeBSD's core VM logic itself, ie. the state machine that decides what to throw out under memory pressure, how to swap and how to do IO, is top-notch. I think with Andrew Morton's and Jens Axobe's latest VM and IO work we are top-notch as well (with a few extras perhaps).

There's also an interesting VM project in the making, Arjan van de Ven's O(1) VM code. [without doubt i do appear to have a sweet spot for O(1) code :-) ] Rik van Riel has merged Arjan's code a couple of days ago. The code converts every important VM algorithm (laundering, aging) to a O(1) algorithm while still keeping the fundamentals - this is quite nontrivial for things like page aging. It's in essence the VM overhead reduction work that Andrea Arcangeli has started in 2.4.10, brought to the extreme. I have run Arjan's O(1) VM under high memory pressure, and it's really impressive - kswapd (the central VM housekeeping kernel thread), which used to eat up lots of CPU time under VM load, has almost vanished from the CPU usage chart.

I do have the impression that the Linux VM is close to a conceptual breakthrough - with all the dots connected we now have something that is the next level of quality. The 2.5 VM has merged all the seemingly conflicting VM branches that fought it out in 2.4, and the many complex subsystems involved suddenly started playing in concert and produce something really nice.

大大狗

厉害！