# 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)的代码来简单探索一下该调度器的实现思路。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/history/o-1-intro.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.