Linux 2.6 内核 O(1) 调度队列原理：如何实现常数时间调度

二、O(1) 调度的核心流程：活跃队列与过期队列的切换

O(1) 调度的核心巧妙之处，在于通过活跃队列和过期队列的交替使用，实现时间片管理与优先级调度的解耦。

2.1 进程入队：按优先级插入对应链表

当进程变为就绪状态时（如从睡眠中唤醒）：

1. 调度器根据进程的优先级（PRI），找到对应的 queue[PRI] 链表；
2. 将进程的 task_struct（PCB）插入该链表的尾部（FIFO 规则）；
3. 置位 bitmap 中对应优先级的比特位（标记该队列非空）；
4. 若进程时间片未耗尽，插入 active 队列；若已耗尽，插入 expired 队列。

2.2 调度决策：位图快速查找最高优先级进程

调度器需要选择下一个执行进程时，核心操作仅需两步（O(1) 关键）：

1. 遍历 active 队列的 bitmap，找到第一个置位的比特位（对应最高优先级）；
2. 从该比特位对应的 queue[PRI] 链表中，取出头部进程（FIFO 规则）；
3. 将该进程设置为当前 CPU 的运行进程，分配 CPU 时间片。

为什么是 O(1)？ 位图遍历的时间不随进程数变化（最多遍历 140 位，实际通过硬件指令优化，仅需几个时钟周期），链表取头节点是 O(1) 操作，因此整体调度决策时间为常数。

2.3 队列切换：当活跃队列为空时

当 active 队列中的所有进程都耗尽时间片后：

1. 调度器无需重新计算所有进程的时间片，只需交换 active 和 expired 指针；
2. 原 expired 队列变为新的 active 队列，原 active 队列变为新的 expired 队列；
3. 调度器同时为新 expired 队列中的进程重新计算时间片（这一步是后台操作，不影响调度决策时间）；
4. 切换完成后，调度器继续从新的 active 队列中选择进程，整个切换过程是 O(1)。

流程示意：

初始：
active → Prio_Array1（有 5 个任务）
expired → Prio_Array2（空）

调度过程：
任务逐个从 active 取出执行，时间片用完后放入 expired

当 active.nr_active == 0 时：
交换指针：temp = active; active = expired; expired = temp

结果：
active → Prio_Array2（现在有任务）
expired → Prio_Array1（现在为空，等待填充）

三、优先级管理：如何保证高优先级的先执行？为什么不直接修改 PRI 值？

O(1) 调度队列通过优先级分组 + 位图标记的方式，完美支持优先级抢占。

1. 优先级分组：高优先级的进程集中在 queue[140] 的低下标位置，低优先级进程在高下标位置；
2. 位图快速定位：调度器始终从位图的第 0 位开始遍历，确保最高优先级的非空队列被优先选中；
3. 抢占机制：当高优先级进程被唤醒（插入 active 队列）时，若当前 CPU 正在运行低优先级进程，调度器会立即触发进程切换，让高优先级进程抢占 CPU。

能不能直接修改 PRI 值？

不能直接改 pri 是因为任务已经在活跃队列的某个优先级链表中。直接改 pri 会导致：

• 位置错误：任务还在旧优先级的链表里，但 pri 值已经变了；
• 调度混乱：调度器按位图找任务时，可能找到空队列或错误任务；
• 数据不一致：位图显示某优先级有任务，但链表中实际没有。

正确做法：改 nice 值标记任务需要更新，等任务自然出队时（时间片用完），再按新优先级插入过期队列。这是延迟更新设计，保证数据结构一致性。

四、源码结构与图解

下图涉及了本文中包含的大部分知识点，并补充了一点实时操作系统的理解。

关键结构定义如下：

struct rq {
    spinlock_t lock;
    /* * nr_running and cpu_load should be in the same cacheline because *
     * remote CPUs use both these fields when doing load calculation.
     */
    unsigned long nr_running;
    unsigned long raw_weighted_load;
#ifdef CONFIG_SMP
    unsigned long cpu_load[3];
#endif
    unsigned long long nr_switches;
    /* * This is part of a global counter where only the total sum *
     * over all CPUs matters. A task can increase this counter on *
     * one CPU and if it got migrated afterwards it may decrease *
     * it on another CPU. Always updated under the runqueue lock:
     */
    unsigned long nr_uninterruptible;
    unsigned long expired_timestamp;
    unsigned long long timestamp_last_tick;
    struct task_struct *curr, *idle;
    struct mm_struct *prev_mm;
    struct prio_array *active, *expired, arrays[2];
    int best_expired_prio;
    atomic_t nr_iowait;
#ifdef CONFIG_SMP
    struct sched_domain *sd; /* For active balancing */
    int active_balance;
    int push_cpu;
    struct task_struct *migration_thread;
    struct list_head migration_queue;
#endif
#ifdef CONFIG_SCHEDSTATS
    /* latency stats */
    struct sched_info rq_sched_info;
    /* sys_sched_yield() stats */
    unsigned long yld_exp_empty;
    unsigned long yld_act_empty;
    unsigned long yld_both_empty;
    unsigned long yld_cnt;
    /* schedule() stats */
    unsigned long sched_switch;
    unsigned long sched_cnt;
    unsigned long sched_goidle;
    /* try_to_wake_up() stats */
    unsigned long ttwu_cnt;
    unsigned long ttwu_local;
#endif
    struct lock_class_key rq_lock_key;
};

/* * These are the runqueue data structures: */
struct prio_array {
    unsigned int nr_active;
    DECLARE_BITMAP(bitmap, MAX_PRIO + 1); /* include 1 bit for delimiter */
    struct list_head queue[MAX_PRIO];
};

总结

Linux 2.6 内核的 O(1) 调度队列，是内核设计的经典案例 —— 通过巧妙的数据结构（位图 + 双队列），将复杂的调度问题转化为常数时间操作，完美解决了多进程场景的调度效率瓶颈。其核心思想'按优先级分组 + 快速定位非空队列'，不仅适用于进程调度，还能迁移到线程池、任务调度等各类场景。理解 O(1) 调度队列的设计，能帮你更深刻地理解操作系统'管理资源'的核心逻辑 —— 好的设计往往不是复杂的算法，而是用最简洁的数据结构解决关键问题。