2.3.4 O（1）调度器 - 简介

O(n)调度器的实现思路非常简单，在它的年代也够用了，但随着多核架构的发展，其扩展性方面的问题越来越明显。其中最大的问题是系统中所有的CPU共享一个全局的运行队列，这个设计会导致如下问题：

1. 并发访问的问题，系统需要通过加锁来同步对队列的访问

2. 每次调度需要遍历整个队列，时间复杂度太高

3. 实时任务与普通任务共用一个队列，影响实时任务的响应速度

4. 任务在调度时，很容易在不同的CPU之间来回跳转，无法很好地利用CPU缓存

5. 在每个调度周期后期，容易造成有的CPU在空跑，例如此时还有剩余时间的就绪任务的总量小于CPU数量的话，就一定有CPU此时处于idle状态

6. 给任务分配调度时间时需要遍历系统的所有任务，效率过于低下，并且在该过程中其余的CPU实际上无事可做

总之，O(n) 调度器简单粗暴的实现很难适应SMP架构下的扩容问题，而随着系统任务数量的增加，其性能存在严重的缺陷，我们需要一种更精细化的策略来完成任务调度。

O(1)调度器就是对针对这种需求进行的优化，由Linux在2.6.0版本中引入，直到后来被CFS取代，本节我们基于linux-2.6.11.1的代码来简单探索一下该调度器的实现思路。