总会有一些坚持
能从冰封的土地里
培育出十万朵怒放的蔷薇

---

Linux 系统篇(十七) —— 进程切换、O(1) 调度算法

---

一、并发与切换的必然性

假设你写了一个最简单的 C 程序：

int main() 
{
    while (1) 
    {
        // 什么也不做，就是死循环
    }
    return 0;
}

  如果你在 Linux 上编译并运行它，然后同时打开浏览器、音乐播放器、终端，你会发现其他程序依然流畅运行，并不会因为那个死循环而卡死。这是为什么呢？你可能会想：CPU 不是被那个死循环占满了吗？它一直在执行，哪有时间干别的？

  答案在于现代操作系统是一个分时操作系统。它通过时间片轮转机制，让每个进程轮流占用 CPU 一小段时间（通常几毫秒到几十毫秒），然后强制切换给下一个进程。你的死循环进程在跑完自己的时间片后，会被操作系统“请下” CPU，放到队列里重新排队。其他进程趁机运行，它们的时间片用完后同样被切换。由于切换频率极高（每秒几十到上千次），从宏观上看，所有进程都像是在“同时”运行。

  这种“让多个进程轮流使用一个 CPU”的机制就是并发。而每一次从一个进程切换到另一个进程的过程，就叫做进程切换。这个切换过程并不是简单的“暂停 A，启动 B”，它需要做大量细致的工作，确保 A 再次被调度时能无缝继续运行，仿佛从未离开过 CPU。

---

二、CPU 寄存器

  要理解进程切换，必须先理解 CPU 是如何执行一个进程的。当进程在 CPU 上运行时，它需要不断地从内存中取出指令、译码、执行，期间会产生大量中间结果。这些临时数据存放在哪里？内存太慢了，CPU 等不起；硬盘更不可能。所以 CPU 内部有一组寄存器，它们是最快的存储单元，直接与运算单元相连，用来暂存正在处理的数据、指令地址、状态标志等。

2.1 寄存器是盒子，数据是内容

  对于单核 CPU 来说，寄存器硬件只有一份，它是物理存在的电路。我们可以把它想象成办公桌上的一组“公用文件盒”。每个进程在运行时，都会往这些盒子里放入自己的“草稿纸”——即各种临时数值。当进程 A 在运行，盒子里的内容就是 A 的数据；当切换成进程 B，B 会把盒子里的内容覆盖成 B 的数据。

  所以一定要区分两个概念：

• 寄存器（盒子）：物理上唯一，属于 CPU 硬件。
• 寄存器里的数据（内容）：随着当前运行的进程变化而不断变化，每个进程在某一时刻都有自己特定的一份内容。

  这个区分是理解“上下文切换”的基石。因为盒子只有一个，而内容是多份的，所以要想让 A 和 B 都能正确运行，就必须在切换时把 A 的内容保存到 A 专属的存储区，再恢复 B 的内容到盒子里。

2.2 常见的寄存器分类

  不同架构（x86、ARM）的寄存器数量、名称可能不同，但功能大致类似。以 x86 32 位为例，主要包括：

寄存器类别	名称示例	作用
程序计数器	EIP / PC	存放下一条即将执行的指令的内存地址，CPU 靠它知道接下来该执行哪条指令
栈指针	ESP / EBP	维护函数调用栈，ESP 指向栈顶，EBP 指向当前栈帧基址
通用寄存器	EAX, EBX, ECX, EDX 等	存放运算的操作数、临时结果、函数返回值等
段寄存器	CS, DS, ES, SS 等	在实模式或保护模式下用于段寻址，现代操作系统大多采用平坦模型，但依然保留
标志寄存器	EFLAGS	记录运算结果的状态，如是否为零、是否为负、是否溢出、是否进位等
控制寄存器	CR0 ~ CR4	控制 CPU 工作模式、分页、保护模式等，通常由操作系统管理，用户态不可访问

  当进程在 CPU 上运行时，这些寄存器中的值构成了进程的硬件上下文。一旦进程被切换走，这些值必须被原封不动地保存下来。

---

三、进程上下文切换：保存现场与恢复现场

3.1 什么是进程上下文

  进程上下文包含了进程执行时所需的全部环境信息，可以粗略分为三个层次：

1. 用户级上下文：进程的虚拟地址空间，包括代码段、数据段、用户栈、共享库等。
2. 寄存器级上下文（硬件上下文）：CPU 中各寄存器在某一瞬间的值，它精确描述了 CPU 当前“正在做什么、做到哪一步了”。
3. 系统级上下文：操作系统管理该进程所需的数据结构，比如进程控制块（PCB / task_struct）、页表、打开的文件描述符表、内核栈、信号处理状态等。

  在进程切换时，操作系统主要保存和恢复的是寄存器级上下文，因为用户级上下文（地址空间）在切换时通常通过切换页表基址来实现（如果两个进程地址空间不同），而系统级上下文则始终存在于 PCB 中，不用每次都复制。

3.2 一个生动的类比：当兵保留学籍

  为了帮助理解，我们讲一个故事：

• 学校 → CPU（提供学习和运行的场所）
• 导员（辅导员） → 调度器（决定谁该上、谁该下）
• 你 → 进程
• 学籍/成绩单 → 寄存器中的内容（硬件上下文）

  假设你读到大二，决定响应号召去当兵：

1. 离开学校（进程被剥夺 CPU）：你必须暂停学业。
2. 保留学籍（保存上下文）：导员把你的所有成绩、学分等信息打包，存入学校的档案系统。这相当于把 CPU 寄存器的内容保存到进程的专属区域。
3. 退役复学（重新获得 CPU）：两年后你回来，想继续读大三。
4. 恢复学籍（恢复上下文）：导员从档案袋里取出你的资料，重新录入系统，你就可以无缝衔接大三的课程，而不用从大一开始重读。这相当于把保存的数据重新写回 CPU 寄存器。

  这个类比中的“保留学籍”就是保存上下文，“恢复学籍”就是恢复上下文。每次切换都包含这两步：先保存当前进程的上下文，再恢复下一个进程的上下文。

3.3 切换的具体步骤

  考虑单核系统，进程 A 正在运行，时间片用完，调度器决定切换到进程 B。整个过程如下：

1. 进入内核态：进程 A 的时间片耗尽会触发一个定时器中断，CPU 自动切换到内核态，并跳转到内核的中断处理程序。
2. 保存 A 的硬件上下文：内核将当前 CPU 中所有寄存器的值（EIP、ESP、EAX、EFLAGS 等）保存到进程 A 的专属存储区。这个存储区通常是 A 的内核栈或者 task_struct 中的 thread_struct 字段。
3. 选择下一个进程 B：调度器根据某种算法（比如 O(1) 调度）从就绪队列中挑选 B。
4. 恢复 B 的硬件上下文：从 B 的专属存储区中取出之前保存的寄存器值，逐一写回 CPU 对应的寄存器中。
5. 返回用户态：内核执行一条特殊的返回指令（如 iret），CPU 根据恢复后的 EIP 和 ESP 等寄存器，从 B 上次中断的地方继续执行，仿佛 B 从未离开过 CPU。

3.4 上下文保存在哪里？——从 TSS 到内核栈

  早期的 Linux 内核（如 0.11 版本）使用硬件提供的 任务状态段（Task State Segment, TSS） 来保存进程的硬件上下文。每个进程有一个 TSS，里面包含了所有寄存器的快照。切换时，CPU 硬件可以自动完成保存和恢复（通过 jmp 到 TSS 描述符）。但这种方式在后来被证明不够灵活，性能也不理想。

  现代 Linux（包括 2.6 及以后）改为基于软件的手动保存与恢复，将硬件上下文保存在进程的 thread_struct 中（嵌入在 task_struct 里），具体寄存器值存储在内核栈的顶部。切换时，调度器调用 switch_to 宏（底层汇编实现），手动将当前寄存器压入当前进程的内核栈，然后从下一个进程的内核栈弹出其保存的寄存器值。

  为什么这样做？因为手动管理可以精确控制哪些寄存器需要保存（比如段寄存器大多数情况下不用变），降低切换开销，而且不依赖特定硬件特性，可移植性好。

  在 task_struct 中有一个 thread_struct 成员，它包含了诸如 esp、eip、fs、gs 等关键寄存器。同时，内核还有一个全局指针 current，永远指向当前正在运行的进程的 task_struct。切换进程时，就是通过 current 找到当前进程，保存其上下文；再更新 current 指向新进程，恢复其上下文。

3.5 全新进程的首次调度

  对于已经运行过的进程，切换时只需恢复之前保存的上下文。但一个新进程（比如通过 fork 创建的子进程）从未在 CPU 上运行过，它的上下文从哪里来？

  答案是：内核在创建新进程时，会在其内核栈中伪造一个初始上下文。这个上下文看起来就像该进程之前被切走了一样。具体做法是：

• 将 EIP 设置为进程入口函数（如 main 的地址，在动态链接情况下是 _start 然后跳到 main）的地址。
• 将 ESP 设置为用户栈的栈顶。
• 将其他通用寄存器清零或赋予默认值。
• 设置 EFLAGS 为适当的初始状态。

  这样，当调度器第一次选择这个新进程时，它走的是和其他老进程一样的“恢复上下文”流程，从伪造的栈中弹出寄存器值，然后跳到入口函数开始执行。

---

四、O(1) 调度算法：Linux 2.6 的经典设计

  理解了进程切换的基本机制后，我们来看看调度器如何选择下一个要运行的进程。在 Linux 2.6 早期，内核采用了一种被称为 O(1) 调度算法的设计，它能在常数时间内选出最高优先级的进程，无论系统中有多少个就绪进程。

4.1 核心数据结构：运行队列 runqueue

  在多处理器系统中，每个 CPU 都有自己的运行队列 runqueue，这样可以减少锁竞争。runqueue 结构体定义在 kernel/sched.c 中，关键字段如下：

struct rq {
    spinlock_t lock;              // 自旋锁，保护队列
    unsigned long nr_running;     // 队列中可运行进程的总数
    unsigned long raw_weighted_load;
    unsigned long cpu_load[3];    // CPU 负载统计
    unsigned long long nr_switches; // 累计切换次数
    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;           // 等待 I/O 的进程数
#ifdef CONFIG_SMP
    struct sched_domain *sd;      // 调度域，用于负载均衡
    int active_balance;
    int push_cpu;
    struct task_struct *migration_thread;
    struct list_head migration_queue;
#endif
    // ... 其他统计信息
};

  其中最重要的成员是 active 和 expired，它们是指向两个 prio_array 结构的指针。arrays[2] 就是那两个结构体实体，active 和 expired 初始分别指向 arrays[0] 和 arrays[1]，之后会交换。

4.2 优先级数组 prio_array

prio_array 结构定义如下：

struct prio_array {
    unsigned int nr_active;          // 此数组中活跃进程的个数
    DECLARE_BITMAP(bitmap, MAX_PRIO+1); // 位图，快速查找非空优先级队列
    struct list_head queue[MAX_PRIO];   // 140 个链表头，对应 140 个优先级
};

• nr_active：记录这个数组中当前有多少个进程。
• bitmap：一个位图，用 5 个 unsigned long（32 位系统上 5*32=160 位）来表示 140 个优先级队列是否为空。如果第 i 个队列非空，则位图第 i 位为 1。
• queue[140]：一个数组，每个元素是一个链表头，所有具有相同优先级的就绪进程被链接到对应的链表中。数组下标就是优先级数值。

4.3 优先级划分与映射

Linux 将进程优先级分为两大类：

• 实时优先级：范围 0~99，数值越小优先级越高。实时进程用于需要严格时限的任务，但这里我们主要关注普通进程。
• 普通优先级：范围 100~139。普通进程的优先级由 nice 值 换算而来，公式为：

实际优先级 = nice + 120

   nice 值的范围是 -20（最高优先级）到 19（最低优先级），所以普通优先级范围是 100（-20+120）到 139（19+120）。默认 nice 为 0，对应优先级 120。

  为什么普通进程优先级从 100 开始而不是 0？这是为了和实时优先级区分开，实时进程的优先级数值更小，调度器会优先选择数值小的队列，所以实时进程总是先于普通进程运行。

4.4 活动队列与过期队列

  O(1) 调度器维护两个 prio_array，分别称为 活动队列（active） 和 过期队列（expired）：

• 活动队列：存放时间片尚未用完的进程。调度器只从这个队列中挑选进程运行。
• 过期队列：存放时间片已经耗尽的进程。当一个进程在 CPU 上运行完它的时间片后，调度器会重新计算它的时间片和动态优先级（基于 nice 值和交互性等），然后把它插入过期队列中相应的优先级链表。

  这样设计的好处是：防止高优先级进程不断产生新进程导致低优先级进程饥饿。因为正在运行的进程都是从活动队列取的，一旦它的时间片用完，就被丢到过期队列，而活动队列中剩下的进程继续被调度。当活动队列中的所有进程都被处理完（即 nr_active 变为 0）时，调度器只需交换两个指针：

struct prio_array *tmp = rq->active;
rq->active = rq->expired;
rq->expired = tmp;

  交换后，原来的过期队列变成了新的活动队列，里面全是时间片已经重置好的进程，可以开始新一轮调度。

4.5 位图加速：O(1) 查找最高优先级进程

  在活动队列中，有 140 个优先级链表，调度器需要找到优先级最高（数值最小）且非空的链表。如果顺序遍历 140 个链表头，时间复杂度是 O(140)，虽然常数不大，但在频繁调度中仍然不够理想。O(1) 算法的关键就是利用 位图 将查找时间降为 O(1)。

  位图 bitmap[5] 是一个长度为 5 的 unsigned long 数组，共 5*32 = 160 位，覆盖了 0~139 共 140 个优先级（多余位不用）。位图的第 i 位对应优先级为 i 的队列：如果该队列非空，则第 i 位为 1；为空则为 0。

  当需要查找最高优先级时，内核调用 sched_find_first_bit() 函数。这个函数利用 CPU 的 bsfl（Bit Scan Forward）指令，可以在一个机器周期内找到第一个（最低位）为 1 的位。例如，如果位图的最低非零位是第 102 位，那么 bsfl 立即返回 102，该指令执行时间是固定的，与总位数无关。于是调度器就能直接定位到 queue[102]，取出链表中的第一个进程（通常放在链表头部）运行。

  这样，无论系统中有 100 个还是 10000 个进程，查找最高优先级进程的时间都是常数级，因此称为 O(1) 调度算法。当然，严格来说，位图操作本身是常数时间，但还需要从链表中取一个节点，那也是 O(1)。整个选择过程就是 O(1)。

4.6 完整调度流程示例

  假设一个 CPU 的 runqueue 刚刚完成指针交换，现在活动队列中有若干进程。调度器的工作流程如下：

1. 检查 active->nr_active 是否大于 0。如果为 0，则交换 active 和 expired 指针（可能还需要重新填充过期队列，比如将所有过期进程重新计算时间片并放入活动队列，但 O(1) 算法中交换后过期队列变空，活动队列直接使用）。
2. 调用 sched_find_first_bit(active->bitmap) 得到第一个非空优先级，假设为 prio = 110。
3. 从 active->queue[110] 链表中取出第一个进程（通常是链表头指向的节点）。
4. 将该进程从活动队列中移除（list_del），同时更新 nr_active--，如果该链表变空，则清除位图中对应位。
5. 将这个进程的 task_struct 指针赋给 rq->curr，然后调用 switch_to 切换到该进程的上下文。
6. 当该进程运行完时间片后，它会重新被调度器处理，插入到过期队列的相应优先级链表中。

4.7 时间片的管理

  在 O(1) 调度器中，每个普通进程有一个时间片计数器 counter（在早期版本中）或类似字段。当进程被调度运行时，它的时间片会随着时钟中断递减。当时间片减到 0 时，进程就被移到过期队列。时间片的初始值通常与 nice 值相关：nice 值越低（优先级越高），分配的时间片越长；nice 值越高，时间片越短。这种设计让高优先级进程不仅更早被调度，还能运行更长时间。

  注意，实时进程的时间片可能不同，它们可能一直运行直到被更高优先级进程抢占或主动让出 CPU。

4.8 新进程的插入位置

  当一个新进程被创建（例如 fork 或 exec）时，调度器需要决定将它放入活动队列还是过期队列。在 O(1) 算法中，新进程通常被放入活动队列中，因为新进程往往是交互式进程，应该尽快得到响应。但这样做可能带来问题：如果大量新进程涌入活动队列，会延迟过期队列中进程的运行。因此，内核在 fork 时会有一些启发式规则，比如根据父进程的剩余时间片来分配子进程的初始时间片，并可能将子进程放入活动队列或过期队列。不过，常见实现是将新进程放入活动队列，但给予一个较短的时间片，以平衡响应性和公平性。

4.9 多处理器负载均衡

  每个 CPU 有自己的 runqueue，但系统需要保证负载均衡。当某个 CPU 的 runqueue 中进程过多，而另一个 CPU 很空闲时，内核会通过 调度域（sched_domain） 机制进行进程迁移。rq 结构中的 sd 指针指向调度域，负责在多个 CPU 之间平衡负载。此外，还有 cpu_load 数组记录 CPU 的负载历史，migration_thread 是一个内核线程，专门负责将进程从繁忙的 CPU 迁移到空闲 CPU。

---

五、常见问题

5.1 为什么不能直接修改进程的优先级？

  在 task_struct 中，有两个与优先级相关的字段：prio（实际优先级）和 nice（修正值）。为什么修改优先级时不直接改 prio，而是要改 nice 呢？

  假设一个进程正在活动队列中，它的优先级是 120，对应 queue[120] 链表。如果管理员通过 renice 命令修改它的 nice 值，直接改 prio 会产生一个问题：这个进程当前还挂在 queue[120] 上，如果它的优先级变成了 110，它应该被移到 queue[110] 才行。这就需要在队列中进行移动，而移动操作需要加锁、查找位置，开销较大，而且可能发生在调度器正在访问队列的临界区，增加复杂度。

  更麻烦的是，我们不知道这个进程当前是在活动队列还是过期队列（如果它的时间片已经用完，它可能在过期队列）。直接改 prio 就需要确定它所在的具体队列并执行移动，这很麻烦。

  所以内核引入了 nice 字段。修改优先级时，只修改 nice 值，不改变当前 prio。等这个进程的时间片用完，被放入过期队列时，调度器会根据新的 nice 值重新计算它的 prio，并插入到过期队列的正确位置。这样，本轮调度中它的优先级保持不变，下一轮生效。

5.2 为什么用两个队列而不是一个？

  单个队列的问题在于：如果所有进程都在一个优先级队列中，调度器每次选出最高优先级进程运行，时间片用完后又放回原队列，那么高优先级进程可能永远占据 CPU，低优先级进程饿死。即使引入了时间片轮转，也还是无法彻底避免优先级高的进程频繁获得 CPU。两个队列的设计巧妙地将“正在运行时间片内”和“时间片已用完”的进程分开，保证了所有进程都有机会运行：活动队列处理完后，过期队列变成了活动队列，原来的活动队列清空成为新的过期队列，如此循环。

5.3 O(1) 调度算法的优缺点

优点：

• 调度时间复杂度为 O(1)，即使系统负载很重，选择进程的时间也不会增加。
• 结构清晰，实现简单（相对于后来的 CFS）。
• 对交互式进程响应较好（通过优先级和动态调整）。

缺点：

• 对交互性的判断不够精确，有时会导致交互进程卡顿。
• 不能保证公平性，可能存在某些进程长时间得不到足够的 CPU 时间。
• 在多核系统上，进程迁移的决策较为粗糙。
• 后来被 CFS（完全公平调度器）取代，因为 CFS 能提供更好的公平性和响应性。

---

结语：

  今天的内容到这里就结束了，希望你能有所收获~

干货整理到手抖，觉得有用的话，赏个三连回回血？__(:ᗤ」ㄥ)_ _