早期的Linux调度策略设计的比较简单，逐步的随着linux的越来越火热，调度问题受到了很多人的关注，本文基于历史和一些数据总结一下linux2.4和linux2.6的调度状态。为什么从这两个版本说呢，因为现在linux内核的调度策略的雏形是从2.6开始形成的

Linux 2.4

在linux 2.4时，内核使用全局队列来管理任务，当任务到来的时候，此队列在content switch的时候会遍历整个runqueue，找到优先级最高的任务来运行。这样的设计有如下几个问题

• O(n)负载度：因为没有考虑设计问题，所以调度器本身的效率低下
• 锁争用：所有CPU都在同一个全局runqueue上争抢锁，这使得锁竞争巨大

Linux 2.6

2.6版本的调度器为了设计O(1)的调度器，对齐进行了整体的设计，首先为了解决锁的问题，调度队列是通过per-cpu上维护两个队列（active和expired），0-99作为实时任务，值越高优先级越高，100-140作为普通任务。下面来介绍2.6上调度是如何设计的。

其实翻看我之前rtems的分析就可以提前知道，调度器通过bitmap+拉链来设计O(1)的代码。同样的Linux 2.6就是这么设计的。它有两个关键元素

• bitmask: 以优先级作为bitmask，这样在寻找优先级最高的任务的时候，只是高效的bitmap就能知道哪个优先级内的队列非空
• queue： 每个优先级的bit下对应一个拉链，拉链本身是fifo结构的，当找到最高优先级的非空队列的时候，只需要在队列里面pop最先入队的任务即可
• active和expired： 在per-CPU上设计两个队列轮转，active是需要立即调度的任务队列，expire将要调度的任务队列。当active的任务运行完毕之后，active和expired做一次轮转

通过图可以演示这两个队列

此时OS从100上选择了一个任务来运行，当运行完成之后，该任务被放置在expired队列上，等待轮转后运行

当active runqueues的任务都运行完成了，则active和expired做一次轮转。

关于timeslice

调度器的分片是在时钟tick中计算的。默认会分配一个值，每次tick到期，会对当前正在运行的任务的timeslice值自减1。当tick完成的时候，也就是timeslice完成的时候。就是将该任务从active迁移到expired的时机。

总结

本文介绍了基本的调度概念，可以强化理解O(1)调度器的历史由来。

参考

https://zhuanlan.zhihu.com/p/33461281