谈谈调度 - Linux O(1)

正文

请到「今天看啥」查看全文

对于那些对2.4 scheduler 不太了解的同学咱们多说两句：2.4 scheduler 维护两个 queue：runqueue 和 expired queue。两个 queue 都永远保持有序，一个 process 用完时间片，就会被插入 expired queue；当 runqueue 为空时，只需要把 runqueue 和 expired queue 交换一下即可。

注意，所有调度系统的难点不在于寻找下一个可执行的 process，这个操作一般都是 O(1)，因为我们只要妥善对 runqueue 排序，使其第一个 process 永远是下次需要调度的 process 即可。难点在于执行完的 process —— 怎样插入到合适的位置使得 runqueue 是有序的？

满足 O(1) 的数据结构 ？

根据我们在数据结构课程里学到的知识可以知道，大多数算法的时间复杂度，O(log N) 基本上就是最好的结果，那么，2.6 的 O(1) scheduler 是怎么做到的？

在回答这个问题之前，我们先回顾一下数据结构的四种基本操作以及其时间复杂度：

请到「今天看啥」查看全文