> For the complete documentation index, see [llms.txt](https://s3.shizhz.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://s3.shizhz.me/linux-sched/history/o-1-intro.md).

# 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](https://cdn.kernel.org/pub/linux/kernel/v2.6/linux-2.6.11.1.tar.gz)的代码来简单探索一下该调度器的实现思路。