前言：
在 Linux 2.6 内核之前，进程调度采用的是 O(n) 算法 —— 调度器需要遍历所有就绪进程才能找到优先级最高的那个，进程数量越多，调度效率越低，严重影响多任务场景的性能。而 2.6 内核引入的 O(1) 调度算法，彻底解决了这一痛点，其核心就是设计了高效的调度队列结构，让调度器无论面对多少进程，都能在常数时间内找到最优进程，大幅提升了系统吞吐量。
一。核心数据结构：runqueue 与 优先级组织
要实现 O(1) 调度，关键在于 "如何快速找到最高优先级的就绪进程"。Linux 2.6 内核通过 runqueue（运行队列）和 prio_array（优先级数组）的组合结构，完美解决了这个问题。
1.1 运行队列（runqueue）：每个 CPU 的'专属调度池'
每个 CPU 核心对应一个独立的 runqueue，避免多 CPU 间的调度竞争，提升并行效率；
核心字段解析：
active：活跃队列，存储时间片未耗尽的就绪进程；expired：过期队列，存储时间片已耗尽的进程；arrays[2]：包含两个 prio_array 结构，分别对应active和expired队列；bitmap：优先级位图，用于快速标记非空优先级队列（核心优化点）。
1.2 优先级数组（prio_array）：按优先级分组的进程容器
prio_array 是 O(1) 调度的核心，它将进程按优先级分组管理，结构如下：
queue[140]：140 个进程链表，每个下标对应一个优先级（0~139）；0~99：实时优先级（高优先级，现在先暂不关注）；100~139：普通进程优先级（对应 nice 值 -20~19，nice 值越小，优先级越高）；nr_active：当前数组中总共有多少个运行状态的进程；bitmap[5]：5 个 32 位整数组成的位图（共 160 位），每一位对应一个优先级队列是否非空，这样还可以一口气检查 32 个；（例如：bitmap 的第 100 位为 1，表示优先级 100 的队列中有就绪进程）。
结构关系可视化：
runqueue（每个 CPU 一个）
├─ lock：队列锁（保证线程安全）
├─ nr_running：就绪进程总数
├─ active：指向活跃队列的 prio_array
├─ expired：指向过期队列的 prio_array
└─ arrays：包含两个 prio_array
├─ prio_array（活跃队列）
│ ├─ queue： 个优先级链表
│ ├─ nr_active：活跃进程数
│ └─ bitmap：活跃队列优先级位图
└─ prio_array（过期队列）
├─ queue： 个优先级链表
├─ nr_active：过期进程数
└─ bitmap：过期队列优先级位图
