4. O(1) 核心数据结构：prio_array_t 结构体、位图 bitmap、active/expired 双数组机制

O(1) 调度算法之所以能在常数时间内完成进程选择，核心在于其精巧的数据结构设计。它摒弃了 O(n) 算法中遍历整个就绪队列的做法，通过 prio_array_t 结构体、位图 bitmap 和 active/expired 双数组机制，将调度开销从“与进程数相关”降为“与优先级数相关”，且优先级数固定为 140，从而实现严格的时间复杂度 O(1)。

4.1 prio_array_t 结构体：就绪队列的容器

prio_array_t 是 O(1) 调度器中管理就绪进程的核心数据结构。每个 CPU 拥有两个这样的结构体实例：一个用于 active 数组，一个用于 expired 数组。其定义如下：

struct prio_array_t {
    unsigned long bitmap[BITMAP_SIZE];  // 优先级位图，用于快速查找非空队列
    struct list_head queue[MAX_PRIO];   // 140 个优先级链表头
    int nr_active;                      // 当前数组中活跃进程总数
};

该结构体通过三个关键字段实现了高效的进程管理：

  • queue[MAX_PRIO]：一个包含 140 个链表头的数组，每个链表对应一个优先级（0~139）。同一优先级的进程通过双向链表链接，新进程插入链表尾部，调度时从头部取出。
  • bitmap[BITMAP_SIZE]：一个位图数组，用于标记哪些优先级队列非空。Linux 2.6 中 BITMAP_SIZE 通常为 5（140 位需要 5 个 32 位无符号整数）。
  • nr_active：记录当前数组中所有进程的总数，用于快速判断是否需要切换 active/expired 数组。
设计要点：queue 数组使用链表而非数组存储进程，是因为同一优先级的进程可能动态增减，链表插入/删除操作的时间复杂度为 O(1)，与 O(1) 调度器的整体设计目标一致。

4.2 位图 bitmap：O(1) 查找的加速器

位图是 O(1) 调度器实现常数时间查找的关键。调度器不需要遍历 140 个队列来寻找最高优先级的非空队列，而是通过位图操作一步定位。

查找过程分为两步：

  1. 查找第一个非零位图字：使用 __ffs()（find first set）指令或软件模拟，在位图数组中从低位到高位找到第一个非零的 unsigned long。
  2. 在该字内查找第一个置位位：同样使用 __ffs() 找到该字内最低位的 1，该位的索引即为最高优先级（数值最小）的非空队列。

例如，若 bitmap[0] = 0x00000080，表示优先级 7 的队列非空，调度器直接定位到 queue[7] 并取出队首进程。

性能关键：现代 CPU 提供硬件指令（如 x86 的 BSF/BSR、ARM 的 CLZ）来加速位扫描，使得整个查找过程仅需几个 CPU 周期，与系统中进程总数完全无关。

4.3 active/expired 双数组机制：时间片轮转的基石

O(1) 调度器使用两个 prio_array_t 实例——active 和 expired——来实现公平的时间片轮转，同时避免 O(n) 算法中重新插入时的遍历开销。

双数组的工作流程如下：

步骤 操作 说明
1 进程从 active 数组被调度 调度器从 active 数组的最高优先级非空队列中取出进程执行
2 时间片耗尽 进程的时间片计数器减至 0，触发重新调度
3 计算新时间片 根据进程的静态优先级和交互性计算新的时间片长度
4 插入 expired 数组 进程被放入 expired 数组对应优先级的队列尾部
5 active 数组为空 当 active 数组的 nr_active 变为 0 时，交换 active 和 expired 指针
6 继续调度 调度器开始从新的 active 数组（原 expired）中选取进程

这种机制确保了所有进程都能在一个轮转周期内得到执行，且优先级高的进程获得更多 CPU 时间。

注意：交互式进程（如键盘响应）在时间片未用完时可能被主动抢占并放回 active 数组，而非进入 expired 数组。这是 O(1) 调度器为了降低交互延迟而做的特殊处理，但也导致了“交互式进程饥饿”等公平性问题，成为后来 CFS 调度器改进的动因之一。

4.4 数据结构关系总览

下图展示了 O(1) 调度器核心数据结构之间的关系：

O(1) 调度器核心数据结构关系图 O(1) 调度器核心数据结构关系图 调度器主控 active prio_array_t 当前可运行进程集合 expired prio_array_t 已耗尽时间片的进程集合 内部结构 bitmap[5] queue[140] nr_active 内部结构 bitmap[5] queue[140] nr_active active 为空时交换指针 位图查找示例：bitmap[0] = 0x00000080 → 优先级 7 非空 → 直接访问 queue[7] 时间复杂度 O(1)，与进程总数无关

4.5 数据结构对比总结

下表总结了 O(1) 调度器核心数据结构与 O(n) 调度器的关键差异：

特性 O(n) 调度器 O(1) 调度器
就绪队列结构 单个全局链表 140 个优先级链表 + 位图
进程选择方式 遍历链表计算 goodness 值 位图扫描 + 链表头取出
时间复杂度 O(n) O(1)
时间片管理 重新计算并插入链表 双数组指针交换
多核扩展性 全局锁，扩展性差 每 CPU 独立数据结构
交互式进程优化 无专门机制 时间片未用完可留在 active

通过 prio_array_t 结构体、位图 bitmap 和 active/expired 双数组机制的协同工作，O(1) 调度器在 Linux 2.6 内核中实现了里程碑式的性能提升，为后续 CFS 调度器的设计奠定了数据结构基础。

← 上一章 📖 返回目录 下一章 →