Linux 2.6 内核 O(1) 调度队列深度解析：为什么它能实现常数时间调度？

wbs_scy

986人浏览 · 2026-02-28 19:58:55

wbs_scy · 2026-02-28 19:58:55 发布

一. 核心数据结构：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[2]：包含两个prio_array
   ├─ prio_array[0]（活跃队列）
   │  ├─ queue[140]：140个优先级链表
   │  ├─ nr_active：活跃进程数
   │  └─ bitmap[5]：活跃队列优先级位图
   └─ prio_array[1]（过期队列）
      ├─ queue[140]：140个优先级链表
      ├─ nr_active：过期进程数
      └─ bitmap[5]：过期队列优先级位图

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

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

2.1 步骤 1：进程入队 —— 按优先级插入对应链表

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

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

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

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

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

✅️ 为什么是 O (1)？

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

2.3 步骤 3：队列切换 —— 当活跃队列为空时

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

调度器无需重新计算所有进程的时间片，只需交换active和expired指针；
原expired队列变为新的active队列，原active队列变为新的expired队列；
调度器同时为新expired队列中的进程重新计算时间片（这一步是后台操作，不影响调度决策时间）；
切换完成后，调度器继续从新的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) 调度队列通过 "优先级分组 + 位图标记" 的方式，完美支持优先级抢占。

优先级分组：高优先级的进程集中在 queue[140] 的低下标位置，低优先级进程在高下标位置；
位图快速定位：调度器始终从位图的第 0 位开始遍历，确保最高优先级的非空队列被优先选中；
抢占机制：当高优先级进程被唤醒（插入 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];
};