【Linux】 进程（7）深度剖析 进程内核O（1）调度队列 + 饥饿问题

  Linux2.6 O(1)调度队列深度剖析｜进程切换核心原理+面试题  

一、背景：为什么需要O(1)调度器

        在Linux2.4及更早内核，调度器是O(n)算法：每次调度需要遍历全部就绪进程，进程数量越多，调度耗时越长，多核场景下锁竞争严重，服务器压力大时调度延迟飙升。

        Linux2.6的O(1)调度器核心目标：无论系统存在多少就绪进程，选择下一个运行进程的时间为常数时间O(1)，大幅提升大并发、多核机器调度性能。

二、核心数据结构 runqueue

2.1 一个CPU拥有一个runqueue

每个CPU核心，独立维护一个本地runqueue运行队列。

• 本CPU上所有处于就绪（TASK_RUNNING）状态的进程，全部挂入本CPU的runqueue；
• 设计目的：多核环境下，尽量减少跨CPU全局锁竞争，每个CPU只操作自己本地队列，提升并发性能；
• 进程可以通过负载均衡，被迁移到其他CPU的runqueue。

runqueue内部维护两组完全一样的优先级数组prio_array：

struct runqueue {
spinlock_t lock; //自旋锁，保护整个runqueue，访问队列必须拿锁，SMP防并发修改
unsigned long nr_running; //本CPU就绪状态（可运行）进程总数量
#ifdef CONFIG_SMP
unsigned long cpu_load; //CPU负载因子，采样runqueue进程数量，用于SMP多CPU负载均衡计算
#endif
unsigned long nr_switches; //该CPU上累计发生的进程上下文切换总次数
unsigned long nr_uninterruptible;//处于TASK_UNINTERRUPTIBLE不可中断睡眠进程数目（IO阻塞，计入负载统计）
unsigned long expired_timestamp;//记录上一次active/expired指针交换的时间戳
unsigned long timestamp_last_tick;//上一次时钟tick调度事件时间，负载均衡时间判断
struct task_struct *curr; //*curr：指向当前CPU正在运行的进程task_struct
struct task_struct *idle; //*idle：本CPU空闲进程（idle进程，没有就绪进程时运行）
struct mm_struct *prev_mm; //保存上一个进程的虚拟内存地址空间，加速上下文切换
struct prio_array_t *active; //【活跃队列指针】指向array[0]：时间片还没用完的就绪进程
struct prio_array_t *expired; //【过期队列指针】指向array[1]：时间片耗尽的就绪进程
struct prio_array_t arrays[2]; //实际存储两个prio_array_t数组 arrays[0]=active，arrays[1]=expired
int best_expired_prio; //expired队列里最高优先级，负载均衡辅助参数
atomic_t nr_iowait; //等待IO休眠进程数量
struct sched_domain *sd; //调度域，SMP负载均衡域结构
int active_balance; //标记是否需要主动做CPU负载迁移
struct task_struct *migration_thread;//迁移线程，专门负责跨CPU迁移进程
struct list_head migration_queue; //待迁移进程请求链表
};

2.2 进程优先级

struct prio_array_t {
unsigned int nr_active; //本数组内就绪进程总个数
unsigned long bitmap[5]; //优先级位图，5个unsigned long，5*32bit=160bit，覆盖全部140个优先级
struct list_head queue[140]; //140条双向链表，下标就是进程优先级0~139
};

O(1)调度器一共维护 140个优先级 0~139

2.21 bitmap [5] 位图：O (1) 查找最高优先级进程（调度器加速核心）

• 如果 queue [k] 链表不为空（存在就绪进程），就把 bitmap 对应第 k 位设置为 1；链表为空对应 bit 置 0。
• 调度选进程时，调用内核函数find_first_bit()，硬件指令快速扫描 bitmap，直接找到值为 1 的最低 bit 下标，就是当前最高就绪优先级。

        不管队列有几千进程，找最高优先级进程时间固定，真正实现 O (1)。

        5 个 unsigned long：5×32bit=160bit，大于 140，足够容纳全部优先级位标记。

2.22 nr_active

      记录当前 prio_array 里面一共有多少就绪进程。

  当runqueue‑>active‑>nr_active == 0，代表 active 队列全部进程时间片耗尽，触发 active 与 expired 指针交换。

2.3 active 活动队列

active指针指向活动prio_array数组：

• 存放时间片尚未消耗完毕的就绪进程；
• CPU调度永远优先从active队列挑选进程运行；
• 调度逻辑：查bitmap找到最高优先级位，取出该链表头部进程投入CPU运行；
• 进程运行消耗时间片；当时间片耗尽，该进程会被移出active队列。

2.4 expired 过期队列

expired指针指向过期prio_array数组：

• 存放时间片已经耗尽的普通进程；
• 当普通进程时间片用完，调度器会重新计算该进程的新时间片，根据新的优先级，插入expired队列对应优先级链表；
• 实时进程时间片耗尽不会进入expired队列；实时进程会重新放回active队列。

expired队列上的进程，此时已经拥有全新时间片，只是暂时得不到CPU。

2.5 active指针与expired指针交换（O(1)调度最巧妙设计）

        当active队列内部所有进程全部耗尽时间片，active彻底为空，不需要把expired队列所有进程拷贝迁移到active。

        只需要交换runqueue内部active、expired两个指针的值，就完成一轮调度轮回。

伪代码示意：

if(rq->active->nr_active == 0){
// 仅仅交换指针，零拷贝，O(1)完成队列切换
swap(rq->active, rq->expired);
}

交换之后：

关键点：没有拷贝任何进程链表，仅仅交换两个指针变量，这是O(1)名称的重要来源。

三、完整调度流程梳理

场景 1：时钟 tick 中断（时间片递减）

场景 2：active 队列全部耗尽（active‑>nr_active ==0）

✅ 指针交换（O (1) 操作，无进程拷贝）

//伪代码，仅仅交换指针
struct prio_array_t *temp = rq->active;
rq->active = rq->expired;
rq->expired = temp;

重点：不需要移动 task_struct 链表节点，仅仅修改指针变量，所以常数时间。

场景 3：挑选下一个要运行进程

场景 4：新进程创建

        根据进程静态优先级，挂入 runqueue 的 active 对应 queue 链表，更新 bitmap、nr_active 计数。

场景 5：SMP 负载均衡

        每个 runqueue 有 cpu_load 负载因子；调度域 sd；migration_thread 迁移线程。

         当发现 CPU 之间负载差距大，把进程从繁忙 CPU runqueue 迁移到空闲 CPU runqueue。

四、O(1)调度器优缺点总结

✅ 优点

❌ 致命缺陷（最终被CFS替换的根源）

五、高频内核面试题

面试题1：Linux2.6 O(1)调度器，O(1)指什么？

答：选择下一个待运行进程的时间复杂度是常数O(1)，与系统就绪进程总数无关。依靠优先级位图快速定位最高优先级进程；active/expired指针交换，不需要搬运进程节点。

面试题2：runqueue为什么每个CPU一个，而不是全局一个runqueue？

答：全局runqueue多核访问时需要大锁，多核会频繁锁竞争，性能差。每个CPU独立runqueue，CPU优先操作自己本地队列，减少锁冲突；跨CPU调度依靠负载均衡迁移进程。

面试题3：active与expired队列什么时候交换？交换做了什么操作？

答：当active队列所有进程时间片耗尽，active队列没有就绪进程的时候触发交换。仅仅交换runqueue中active和expired两个指针，不会拷贝、移动任何进程链表节点，开销极低。

面试题4：进程时间片用完，一定会进入expired队列吗？

答：不会。普通进程时间片耗尽，重新计算时间片后放入expired；实时进程时间片耗尽，放回active队列，不会进入expired。

面试题5：bitmap位图作用是什么？

答：1bit对应1条优先级链表；bit=1代表该优先级链表存在就绪进程；利用CPU指令快速找到第一个置1的bit，直接拿到最高优先级就绪队列，避免遍历全部140条链表，保证查找O(1)。

面试题6：O(1)调度器有什么缺点，为什么被CFS替代？

答：普通进程公平性不足，低优先级进程饥饿；交互式进程启发算法复杂容易出错；时间片静态分配，多任务场景时间分配不够平滑，因此2.6.23后被CFS完全公平调度器取代。

面试题7：nice值和O(1)调度器内部优先级怎么对应？

答：nice范围[-20,19]，映射内部优先级100~139；nice越小，内部优先级数字越小，优先级越高。

六、延伸思考

        CFS调度器不再使用active/expired双队列+位图，改用红黑树维护就绪进程，根据虚拟运行时间调度，追求公平分配CPU时间，不再区分静态时间片。但O(1)调度器的per‑CPU runqueue设计思想，在CFS中依然继承保留。

  O (1) 调度器：饥饿问题 + nice 值完整解析  

结合上面runqueue、prio_array_tO (1) 调度模型来讲。

一、nice 值的意义

1. nice 存在的意义

• IO 密集（经常睡眠，交互程序：编辑器、shell）：提升动态优先级，给更多 CPU；
• CPU 密集（一直跑，计算程序）：降低动态优先级。

⚠️注意：nice只作用普通分时进程；实时进程 SCHED_FIFO/SCHED_RR 不受 nice 控制，使用 0‑99 实时优先级。

2. nice 的局限

nice 只是权重偏移，O (1) 调度下不是比例分配 CPU，是时间片分配：

         nice 越小，分配得到的时间片长度越长；nice 越大，分得时间片越短。

         nice=-20：时间片最长；nice=+19：时间片最短。

二、O (1) 调度器中的饥饿问题

什么是饥饿

饥饿 (starvation)：低优先级进程永远得不到 CPU 时间，一直无法运行。

1. O (1) 调度为什么会产生饥饿？

回顾 O (1) 调度逻辑：调度器每次永远选active 队列里最高优先级的进程运行。

场景：系统一直存在大量高优先级就绪进程。

关键点：只要 active 队列不为空，就不会去看 expired 队列。

两种饥饿情况

① 普通分时进程饥饿

        系统持续不断有高 nice（小数值，比如 nice=-5）CPU 密集进程。 只要 active 队列始终有高优先级任务，低优先级进程得不到运行机会。 虽然时间片耗尽会扔到 expired，但只要 active 不空，expired 队列里的进程不会被调度。

        O (1) 做了补救：交互进程奖励机制，IO 密集低优先级进程会动态提升优先级缓解饥饿，但不能彻底根除。

② 实时进程饥饿（SCHED_FIFO）

        实时进程优先级 0‑99，优先级高于所有普通进程。 如果一个高优先级 SCHED_FIFO 实时进程一直就绪不阻塞，同 CPU 上所有更低优先级实时进程、全部普通进程直接饥饿，完全抢不到 CPU。

        SCHED_FIFO 没有时间片概念：只要不主动 sleep / 退出，就一直占 CPU。

2.O (1) 调度器缓解饥饿的机制（不能完全消除）

        但是！如果active 永远不为空（源源不断高优先级进程），纪元永远不会触发交换，低优先级进程依旧饥饿。👉这就是 O (1) 调度器最大痛点。

        举例：源源不断创建高优先级进程，active 队列一直有任务，active‑>nr_active永远不等于 0，expired 队列里面低优先级进程会长期得不到调度。

3. CFS 如何解决饥饿（对比理解）

        后来 CFS 调度器抛弃 active/expired 双队列 + bitmap 方案，采用完全公平，按权重比例分配 CPU 时间。 不再有 “优先选最高优先级” 逻辑，维护虚拟运行时间vruntime，永远挑 vruntime 最小进程运行。

• 低优先级进程哪怕权重小，随着时间累积vruntime，终究会被调度；从机制上杜绝饥饿问题。
• nice 依旧保留，nice 决定权重，决定分得 CPU 时间占比。

三. 新进程的加入情况

内核真实行为（Linux2.6 O (1) 原版）

fork()创建子进程：

✅逻辑：新进程时间片是满的，属于 “时间片未消耗”，理应进active，参与本轮调度，可以抢占当前 CPU 进程。

❌expired队列语义：时间片已经用光的就绪进程。只有进程运行后时钟 tick 把时间片减到 0，才会被迁移到 expired。

四、面试简答整理

nice

饥饿

新进程