今天看了2.6中调度相关的O(1)算法

windseeker

感觉它与2.4中的O(n)算法的区别仅仅在于：该算法的运行时间不随系统任务数量的改变而改变，
现在比较不解的是，这个算法上的优化对内核的整个调度器性能影响就这么大吗， 可能这个缘于
偶对Linux调度算法细节不是很清楚，所以哪位大侠解释一下。

nntp

Scheduler: O(1) vs. O(n)

O(n) scheduling:
for (each process on the system) {
find worthiness of this process
is this the worthiest process yet?
}
run most worthy process

O(1) scheduling:
get highest priority level that has
processes
get first process in the list at that
priority level
run it

windseeker

got it 3x

rwen2012

原帖由 nntp 于 2006-6-1 17:01 发表
Scheduler: O(1) vs. O(n)

O(n) scheduling:
for (each process on the system) {
find worthiness of this process
is this the worthiest process yet?
}
run most worthy process

O(1) scheduling: ...

that is very clear.

圆点坐标

有点类似链表和hash表