Linux2.6 为每个 CPU 保留 active 和 expired 两个优先级数组, active 数组中包含了有剩余时间片的任务,expired 数组中包含了所有用完时间片的任务。
当一个任务的时间片用完了就会重新计算其时间片,并插入到 expired 队列中,当 active 队列中所有进程用完时间片时,只需交换指向 active 和 expired 队列的指针即可。此交换是实现 O(1)算法的核心,由 schedule()中以下程序来实现:
array = rq ->active;
if (unlikely(!array->nr_active)) {
rq -> active = rq -> expired;
rq -> expired = array;
array = rq ->active;
...
}
参考资料：《linux内核设计与实现》《深入理解linux内核》
其中例子几乎书上都有，如有错误欢迎指正。