Linux 2.6 内核早期引入O(1)调度器解决旧调度器O(n)性能瓶颈，但因其公平性缺陷，在2.6.23被CFS完全公平调度器取代。

O(1)调度器

Per-CPU runqueue + 双 prio_array

每个CPU核心独占独立runqueue运行队列，多核队列互相隔离，规避全局大锁竞争。
runqueue包含两组完全一致的prio_array：

• active：活跃数组，存放时间片未耗尽的就绪进程；
• expired：过期数组，存放时间片耗尽的就绪进程。

prio_array结构成员：

1. nr_active：当前数组就绪进程总数；
2. bit_map[5]：5个int共160bit位图，规范使用低140bit。
   • bit 0～99：对应实时进程静态优先级；
   • bit 100～139：对应普通分时进程静态优先级；
   • bit置1代表该优先级存在就绪进程，可快速定位最高优先级任务。
3. queue[140]：140条双向链表，下标等于静态优先级，同优先级进程挂载在同一条链表。

核心轮转逻辑（Swap指针交换）：

1. 调度器仅从active数组选取进程，通过bit_map找到数值最小（优先级最高）就绪进程运行；
2. 进程运行持续消耗时间片，时间片耗尽后移出active，加入同优先级expired链表；
3. active.nr_active == 0时，执行指针互换active <-> expired；原过期队列变为活跃队列，所有进程重新分配时间片，开启新一轮调度周期。

静态优先级 & 动态优先级

Linux 140 档静态优先级划分：

• 实时进程：0 ~ 99（SCHED_FIFO / SCHED_RR）
• 普通分时进程：100 ~ 139，映射关系：static_prio = 120 + nice，nice范围[-20,19]

O(1)引入动态优先级作为交互优化手段：

• 动态优先级基于静态优先级调整；
• 频繁休眠的交互进程唤醒后，内核主动提升其动态优先级、奖励额外时间片；
• 弊端：属于经验策略，没有理论边界，行为不可预测。

时间片机制

普通进程时间片由静态优先级直接计算：

time_slice = (MAX_TIMESLICE * (140 - static_prio)) / 140

• MAX_TIMESLICE 默认 100ms

static_prio越小（nice越小），时间片越长。

O(1)抢占模型

1. 实时进程 > 所有普通进程：只要实时任务就绪，立刻抢占普通进程；
2. 不同静态优先级普通进程：不会互相抢占；
3. 普通进程之间必须等到自身时间片耗尽才会让出CPU。

这是桌面交互卡顿最核心根源：
后台大量低nice长耗时进程拿到CPU后会持续运行直到时间片用完，鼠标、窗口这类短时交互进程无法及时抢占，造成明显延迟。

O(1)调度器优缺点

• 优点：

  1. 通过位图查找最高优先级进程，查找操作复杂度恒定O(1)，不受就绪进程数量影响；
  2. per-cpu runqueue设计，多核扩展性优于更早的O(n)调度器；
  3. 实时进程具备强优先级保障。

• 致命缺陷（被CFS替代的根本原因）：

  1. 公平性差：普通进程静态优先级机制，低优先级进程极易饥饿；
  2. 普通进程之间无抢占，后台任务长时间霸占CPU，交互体验差；
  3. 依赖动态优先级、睡眠奖励等大量启发式策略优化交互，逻辑臃肿，时序行为难以分析；
  4. 分时模型下，任务唤醒后进入就绪链表排队，系统重载下唤醒抖动随机性强。

CFS完全公平调度器

CFS只负责普通分时进程，实时调度器独立存在，优先级全局高于CFS。

放弃双队列，采用vruntime红黑树就绪队列

• 移除 active/expired、位图、140条优先级链表;

• 单CPU CFS就绪队列核心：一棵以vruntime为key的红黑树:

  • 所有CFS就绪调度实体挂在红黑树上；
  • 排序规则：vruntime越小越靠左；
  • 调度规则：永远选择最左侧vruntime最小的调度实体运行。

• 核心思想：摒弃固定时间片，让就绪进程按权重比例均分CPU时间。

vruntime 计算公式

物理运行时间 → 虚拟运行时间换算公式：

vruntime += delta_exec * weight_0 / weight_task

• weight_0：nice=0对应的基准权重
• weight_task：当前进程权重

• 高权重进程 weight_task 更大 → 同等物理时间下，vruntime增量更小；
• 进程休眠、阻塞IO时，delta_exec=0，vruntime停止上涨；

nice与权重是内核内置常量表：
nice=-20 权重最高；nice=0基准权重1024；nice=19权重最低。

长时间休眠任务唤醒时，内核会对vruntime做对齐修正，防止休眠很久的进程唤醒后持续抢占CPU引发调度震荡。

CFS调度周期与最小调度粒度

CFS不允许无限制频繁抢占，内核两个核心阈值：

1. sysctl_sched_latency：目标调度周期。当就绪进程较少时，所有进程需要在该周期内轮流获得CPU；
2. sysctl_sched_min_granularity：最小调度粒度。一个进程最少持续运行这么久，避免频繁上下文切换。

也就是说：即使别的进程vruntime更小，当前进程至少运行min_granularity才允许被抢占，防止系统在大量进程间疯狂切换。

CFS三类抢占机制

1. 唤醒抢占（新进程就绪抢占）
   进程被唤醒加入红黑树，如果它的vruntime远小于当前运行进程，满足阈值条件则触发抢占。交互任务流畅主要依靠该机制。
2. 周期抢占（定时检查）
   当前进程持续运行超过最小调度粒度，内核检查是否存在vruntime更小的任务，满足条件则切换。
3. 自愿抢占
   进程主动sleep、调用sched_yield主动放弃CPU。

重要结论：CFS不存在基于静态优先级的无条件抢占，一切抢占判断依托vruntime差值。

CFS调度实体 & 组调度简述

CFS调度单元不是task_struct，而是sched_entity 调度实体：

• 普通进程：一个任务对应一个调度实体；
• 组调度（cgroup CPU子系统）：进程组作为一个调度实体参与红黑树调度。
  实现两级公平：先组之间按权重分配CPU，组内进程再二次分配。天然适配容器、云多租户资源隔离场景。

CFS优缺点

• 优点：

  1. 架构层面实现按权重公平分配CPU，彻底解决O(1)时代进程饥饿问题；
  2. 依靠唤醒抢占，频繁休眠的交互进程可及时抢占CPU，天然改善桌面响应；
  3. 移除大量启发式补偿代码，核心逻辑简洁；
  4. 原生支持组调度、CPU带宽限制，适配虚拟化、容器场景。

• 缺点：

  1. 调度实体查找、插入红黑树复杂度 O(logN)；
  2. 分时调度模型固有局限：
     • 任务唤醒后仍需要进入红黑树排队，CPU满载时存在调度延迟；
     • 调整nice权重只能降低等待概率，无法彻底消除；

O(1)查找是O(1)，所以整体比CFS更快？

不是。

• O(1)只是寻找下一个运行进程这一步是常数时间；
• 真实系统开销由上下文切换、就绪队列排队延迟、缓存失效主导；
• logN红黑树操作开销极小，通用业务场景几乎无法观测；
• CFS带来的公平性、交互体验收益远大于微小的logN开销，这也是主线内核全面切换CFS的根本原因。

定时任务抖动原理分析

抖动根源

1. 定时器硬件抖动：时钟中断、内核定时器层带来的微小偏差；
2. 调度延迟（主要抖动来源）：定时器到期唤醒线程 → 线程置为就绪态 → 等待CPU就绪队列调度。

O(1)、CFS都会存在调度延迟，但抖动特征不同：

• O(1)：普通进程之间不能互相抢占，后台长任务一旦拿到CPU会跑完整个时间片，交互 / 定时线程最长需要等待一整个时间片，抖动上限高；
• CFS：有唤醒抢占+最小调度粒度约束，新唤醒的低vruntime任务有机会抢占正在运行的进程，不需要等待当前进程“耗尽时间片”。这是CFS相比O(1)定时抖动更小的底层原因。

nanosleep 为什么一定会存在随机抖动？

• std::this_thread::sleep_until的底层nanosleep仅在内核定时器到期后将线程标记为TASK_RUNNING，不会立刻分配CPU；
• 线程加入对应CPU就绪队列排队，CPU重载下排队时长随机；
• 调高nice只是提升进程权重、缩短平均等待时间，不能根除排队延迟。

timerfd + epoll 缓解抖动原理

• timerfd到期触发内核中断；
• 中断上下文优先级高于进程调度；
• 中断上下文可以快速唤醒用户线程，缩短就绪等待窗口，降低调度延迟。

注意：属于优化手段，不构成硬实时。对严格周期确定性需求，需要 SCHED_FIFO/SCHED_RR 实时策略或 PREEMPT_RT 补丁。

O(1) vs CFS 全维度对比表