概要

在前面的学习中，我们已经知道，操作系统通过 PCB（进程控制块）管理进程，也了解了进程的不同状态以及优先级。

但是，还有两个问题值得继续研究：

• 一个进程正在 CPU 上运行，突然需要切换到另一个进程，那么原来进程执行到哪里了？CPU 又是如何记住它的运行位置的？
• 如果系统中有很多进程都处于就绪状态，操作系统应该让谁先运行？又如何快速找到这个进程？

这就涉及今天的两个核心知识点：进程上下文切换和进程调度算法。

首先，我们要理解 CPU 寄存器、进程上下文以及保存和恢复现场的过程；然后再从进程调度的问题出发，了解 Linux 曾经使用的经典 O(1) 调度算法，看看它是如何利用优先级数组、位图以及活跃队列和过期队列，提高调度效率的。

一、进程切换与 CPU 寄存器原理

1.1 一个死循环进程，会一直占用 CPU 吗？

先来看一个简单的问题。

假设我们写了一个程序：

#include <stdio.h>

int main()
{
    while (1)
    {
        printf("hello Linux\n");
    }

    return 0;
}

这个程序进入死循环之后，就会一直执行下去。

那么问题来了：如果一个进程一直不结束，是不是就会一直占用 CPU，导致其他进程没有机会运行？

当然不是。

我们前面学习过，操作系统需要管理多个进程，并且要合理分配 CPU 资源。CPU 是有限的，一个 CPU 核心在同一时刻只能执行一条指令流，因此多个进程需要轮流获得 CPU 的使用权。

为了实现这种效果，操作系统会给进程分配一定的 CPU 运行时间，这个时间通常称为时间片（Time Slice）。

我们可以把它理解成一张限时使用的通行证：

假设系统中有 A、B、C 三个进程，操作系统给它们分配一定的运行时间。

• A 先运行，获得自己的时间片。
• A 的时间片用完，操作系统暂停 A。
• 接下来让 B 运行。
• B 运行一段时间后，再轮到 C。
• 等到后面再次轮到 A，A 就可以继续运行。

这样，多个进程就能够轮流使用 CPU。

这里要注意，时间片不是说进程必须把这段时间全部用完才能退出 CPU。

例如，进程 A 在运行过程中需要读取磁盘数据，而磁盘数据还没有准备好，那么 A 就需要等待。此时 A 会进入阻塞状态，主动让出 CPU，操作系统就可以调度其他进程运行。

所以，进程离开 CPU 主要有两类情况：

1. 被动让出 CPU：时间片用完，或者被更高优先级的进程抢占。
2. 主动让出 CPU：进程需要等待某种资源，例如等待 I/O 操作完成。

无论是哪一种情况，都会引出一个问题：

原来的进程暂停以后，下一次再获得 CPU 时，怎么知道自己执行到哪里了？

总不能每次重新从 main 函数开始执行吧？

这就需要认识 CPU 内部的一个重要组成部分——寄存器。

1.2 CPU 寄存器：程序运行时的临时存储空间

我们之前学习过冯·诺依曼体系结构，计算机主要由输入设备、输出设备、存储器、运算器和控制器组成。

其中，CPU 负责执行指令，而内存负责存放程序运行所需要的数据和指令。

但是，CPU 执行指令时，并不是每次都直接从内存中读取数据，再把计算结果写回内存。

因为内存的访问速度远远低于 CPU 内部的运算速度，如果每一步都访问内存，就会影响 CPU 的执行效率。

所以，CPU 内部设计了速度非常快的存储单元，这就是寄存器（Register）。

寄存器可以理解成 CPU 内部的小型高速存储空间，用来暂时保存正在执行指令时需要的数据和状态。

例如：

int a = 10;
int b = 20;
int c = a + b;

当 CPU 执行这段代码时，需要读取 a 和 b 的值，完成加法运算，再得到 c 的结果。

在实际执行过程中，编译器会根据具体情况生成机器指令，CPU 也可能利用寄存器保存中间数据和运算结果。

寄存器虽然数量不多，但它们对程序的执行非常重要。

其中有几个寄存器尤其值得我们了解。

（1）通用寄存器

通用寄存器主要用于保存程序运行过程中的临时数据，例如运算操作数、中间结果以及函数调用过程中需要使用的数据。

不同 CPU 架构的寄存器名称和数量不完全相同。

例如，在 x86-64 架构中，可以看到 RAX、RBX、RCX、RDX 等通用寄存器。

（2）程序计数器 PC

PC（Program Counter），也叫程序计数器。

它主要用于记录 CPU 接下来应该执行哪条指令的地址。

假设程序中有下面三条指令：

指令1：a = 10
指令2：b = 20
指令3：c = a + b

CPU 执行完第一条指令之后，需要知道下一条指令在哪里。

这时候就需要程序计数器记录下一条待执行指令的位置。

因此，PC 对程序的正常执行非常重要。

在 x86-64 架构中，对应的指令指针寄存器通常称为 RIP；在 32 位 x86 架构中则称为 EIP。

（3）栈指针寄存器 SP

SP（Stack Pointer），也就是栈指针。

我们之前学习函数调用时，接触过栈帧的概念。

函数调用过程中，会涉及局部变量、函数参数、返回地址等信息，其中一部分会存放在栈上。

那么 CPU 如何知道当前栈的位置呢？

就需要栈指针寄存器来记录当前栈顶的位置。

在 x86-64 架构中，对应的寄存器是 RSP。

（4）标志寄存器

标志寄存器用于保存 CPU 执行指令后产生的一些状态信息。

例如，两个数进行比较之后，结果可能相等，也可能一个大于另一个。

CPU 会根据运算结果更新相应的标志位，后续的条件跳转指令就可以根据这些标志位决定是否跳转。

在 x86-64 中，这部分状态主要体现在 RFLAGS 寄存器中。

（5）控制寄存器

控制寄存器主要用于控制 CPU 的运行模式和内存管理等功能。

例如，x86 架构中的 CR3 寄存器就与页表管理有关，它保存当前地址空间顶层页表的物理地址。

后面讲到进程切换时，我们还会遇到它。

1.3 一个重要区别：寄存器不等于寄存器中的数据

了解了寄存器之后，我们再回到最开始的问题。

假设 CPU 正在执行进程 A。

此时，CPU 内部的寄存器保存着 A 当前运行所需要的数据，例如：

• 通用寄存器中保存的临时计算结果。
• 程序计数器记录的下一条指令地址。
• 栈指针记录的当前栈位置。
• 标志寄存器保存的运算状态。

这些数据共同描述了 A 当前的执行现场。

现在，A 的时间片用完了，操作系统决定让 B 运行。

问题来了：

CPU 的寄存器是由当前 CPU 核心使用的，A 离开 CPU 后，B 也要使用这些寄存器。

如果直接让 B 使用，A 原来保存在寄存器中的数据就会被覆盖。

那么等到下一次 A 再次获得 CPU 时，原来的计算结果、栈位置和执行位置都可能丢失。

这显然不行。

所以，操作系统必须在切换进程之前，先把 A 当前运行所需要的现场信息保存起来。

等到以后 A 再次获得 CPU 时，再把之前保存的信息恢复到寄存器中。

这样，A 就能够从之前暂停的位置继续执行。

这里可以先记住一句话：

寄存器是 CPU 内部的硬件存储单元，而寄存器中的数据是程序运行过程中不断变化的执行现场。进程切换时，需要保存和恢复的是这些数据，而不是把寄存器本身搬走。

这就引出了进程上下文的概念。

二、进程上下文与切换机制

2.1 什么是进程上下文（Process Context）？

我们刚才知道，进程运行过程中，CPU 寄存器里保存着它当前的执行信息。

但一个进程要想继续运行，难道只需要保存寄存器就够了吗？

当然不够。

我们知道，一个进程并不只是 CPU 正在执行的一段代码，它还有自己的虚拟地址空间、内存管理信息、打开的文件、信号处理信息以及其他资源。

这些信息共同构成了进程运行所需要的环境。

因此，进程上下文（Process Context）可以理解为：为了让一个进程能够暂停后再继续运行，操作系统需要维护的那一整套运行环境信息。

为了方便理解，可以把它分成几个层次。

（1）用户级上下文

主要是进程在用户空间中的运行环境。

例如：

• 程序代码段。
• 全局变量和静态变量。
• 堆空间。
• 用户栈。
• 共享库等映射区域。

这些信息构成了进程的用户空间运行环境。

（2）寄存器级上下文（硬件上下文）

主要是 CPU 寄存器中的运行状态。

例如：

• 通用寄存器。
• 程序计数器。
• 栈指针。
• 标志寄存器。
• 其他与当前执行状态有关的寄存器。

它们能够帮助 CPU 恢复进程原来的执行现场。

（3）系统级上下文

主要是操作系统为了管理进程而维护的信息。

例如：

• 进程控制块 PCB。
• 进程状态。
• 文件描述符表。
• 信号相关信息。
• 内存管理信息。
• 调度优先级等。

这里需要注意，进程上下文是一个比较广义的概念。不同教材和内核资料对上下文的划分方式可能有所不同。

而在实际的进程切换中，我们最关注的是硬件上下文的保存和恢复，以及内核如何切换当前运行任务所需要的内核栈和地址空间等环境。

2.2 进程切换的本质：保存与恢复

现在我们已经知道，进程 A 要离开 CPU，必须先保存自己的执行现场。

那么，这些信息保存在哪里呢？

还记得我们之前学习的 PCB 吗？

PCB 是操作系统用来管理进程的数据结构。在 Linux 中，它主要对应 task_struct 结构体。

每个进程都有自己的 task_struct，里面保存着操作系统管理这个进程所需要的各种信息。

因此，PCB 是保存和关联进程运行信息的重要载体。

不过，这里不能简单理解为：所有寄存器数据都直接放在 task_struct 结构体内部。

在 Linux 中，不同架构、不同类型的寄存器状态，可能保存在内核栈、thread_struct 或其他专门的数据结构中。它们通过 PCB 关联起来，共同完成进程上下文的管理。

我们先从整体上理解这个过程。

假设现在 CPU 正在运行进程 A，接下来需要切换到进程 B。

整个过程可以分为三个阶段：

第一步：保存进程 A 的现场。

A 离开 CPU 之前，操作系统需要保存它当前的执行状态，包括必要的寄存器信息和栈信息。

第二步：切换到进程 B 的运行环境。

操作系统需要找到 B 之前保存的运行状态，并准备好 B 所需要的内核栈和地址空间。

第三步：恢复进程 B 的现场。

把 B 之前保存的寄存器状态恢复到 CPU 中，让 CPU 从 B 上次暂停的位置继续执行。

所以，进程上下文切换的核心就是：

保存当前进程的运行现场，再恢复下一个进程的运行现场。

我们可以把它理解成玩游戏时的存档和读档。

A 玩到一半需要暂停，就先保存当前进度；等以后再次轮到 A 时，再读取之前的存档，继续游戏。

当然，这只是帮助我们理解原理的比喻，真正的进程切换还涉及内核栈、地址空间和处理器架构相关的底层操作。

2.3 一次完整的进程上下文切换

下面我们把整个过程串起来。

假设系统中有两个进程：

进程 A：正在 CPU 上运行
进程 B：处于就绪状态

此时，A 的时间片用完了。

第一阶段：时间片用完，进入内核。

CPU 运行过程中，时钟硬件会定期产生时钟中断。

当时间片耗尽时，内核能够通过时钟中断处理流程发现当前进程已经需要重新调度。

注意：时钟中断本身并不等于进程切换，它只是让操作系统获得处理时机。

第二阶段：保存进程 A 的运行现场。

操作系统需要保存 A 当前的执行状态。

例如：

进程 A
  |
  | 当前执行状态
  |
  +-- 通用寄存器
  +-- 程序计数器
  +-- 栈指针
  +-- 标志寄存器

这些信息会根据具体的处理器架构和进入内核的方式，保存在相应的上下文区域中。

第三阶段：选择进程 B。

操作系统通过调度器，从当前 CPU 的可运行任务中选择下一个应该运行的进程。

假设这次选中了 B。

第四阶段：切换运行环境。

操作系统切换到 B 对应的内核栈，并根据需要切换地址空间。

例如，在两个不同进程的地址空间之间切换时，可能需要更新 CR3 寄存器，让 MMU 使用新的页表。

第五阶段：恢复进程 B 的执行现场。

操作系统恢复 B 之前保存的寄存器状态。

CPU 就可以继续执行 B 的指令。

整个过程可以概括为：

          进程 A 正在运行
                 |
                 |
           时间片用完
                 |
                 v
          进入内核处理
                 |
                 v
        保存进程 A 的上下文
                 |
                 v
          调度器选择进程 B
                 |
                 v
        切换 B 的运行环境
                 |
                 v
        恢复进程 B 的上下文
                 |
                 v
          进程 B 开始运行

那么，等到下一次轮到 A 时，操作系统再恢复 A 之前保存的状态。

A 就可以继续执行，而不是从头开始。

这就是进程上下文切换的基本过程。

2.4 上下文究竟保存在哪里？

前面我们一直在说保存上下文，那么 Linux 到底把这些信息放在哪里？

这就需要把 PCB、内核栈、thread_struct 和 TSS 联系起来理解。

（1）PCB：进程的管理中心

Linux 中，每个进程都有一个 task_struct。

它记录着进程的各种管理信息，例如：

task_struct
    |
    +-- 进程状态
    |
    +-- PID
    |
    +-- 优先级
    |
    +-- 内存管理信息
    |
    +-- 文件相关信息
    |
    +-- thread_struct
    |
    +-- 内核栈相关信息

可以把 task_struct 理解为进程的管理档案。

操作系统通过它找到和管理进程的各种资源。

（2）内核栈：保存内核执行过程中的现场

我们知道，每个进程都有自己的用户栈，用于用户程序中的函数调用。

除此之外，Linux 还为每个任务维护内核栈。

当进程通过系统调用或者中断进入内核态时，内核需要在内核栈上执行函数调用、保存相关现场以及处理内核代码。

例如，用户程序调用 read() 读取文件，执行过程中进入内核态，内核就会在相应的内核执行环境中处理这次请求。

如果之后发生进程切换，内核需要保存足够的信息，让这个任务以后能够继续执行。

这里要特别注意：进入内核时形成的寄存器现场，通常保存在内核栈上的相应结构中；而真正的任务切换还需要保存和恢复底层切换所需的寄存器及栈指针。

（3）thread_struct：保存与线程执行有关的架构信息

task_struct 中包含与线程执行状态有关的信息。

Linux 中有一个重要的数据结构：

struct thread_struct;

它用于保存与具体处理器架构相关的线程状态。

例如，在 x86 架构下，会涉及内核栈指针、部分寄存器状态以及其他架构相关信息。

因此，我们可以这样理解：

• task_struct：负责管理整个任务。
• 内核栈：保存内核执行过程中的调用现场和相关寄存器现场。
• thread_struct：保存架构相关的线程执行状态。
• 其他内核数据结构：管理地址空间、文件、信号等资源。

它们共同配合，才能让一个进程在离开 CPU 后再次恢复运行。

（4）TSS：任务状态段

在学习 x86 架构时，还经常会遇到一个概念：TSS（Task State Segment），也就是任务状态段。

在传统 x86 硬件任务切换机制中，TSS 可以保存任务的处理器状态，例如寄存器、栈指针等信息。

但是，现代 Linux 并不依靠 x86 的硬件任务切换机制完成普通进程切换，而是主要通过软件方式保存和恢复任务上下文。

在现代 x86 Linux 中，TSS 仍然存在，但它主要承担一些特定的处理器状态管理工作，例如为不同特权级切换提供内核栈信息，以及管理 I/O 权限位图等。

所以不要把 TSS 和 Linux 的 PCB 混为一谈。

简单来说：

TSS 是 x86 架构提供的一种硬件数据结构，而 task_struct 是 Linux 内核自己设计的任务管理结构。

2.5 新进程与老进程：第一次运行有什么不同？

现在我们已经知道，进程切换时，需要先保存当前进程的现场，再恢复下一个进程的现场。

但是这里又出现一个问题：

如果一个进程刚刚被创建出来，它还没有真正运行过，那么操作系统应该恢复什么？

例如，我们通过 fork() 创建一个子进程。

子进程刚创建出来时，虽然已经拥有自己的进程管理信息，也已经具备运行所需要的基本环境，但是它还没有真正获得过 CPU。

因此，它并不存在一个完整的、由自己之前运行所产生的现场。

那么第一次调度时怎么办？

答案是：操作系统需要为新进程准备一个初始运行上下文。

也就是说，新进程第一次运行时，不是恢复之前保存的现场，而是使用内核提前准备好的初始上下文进入相应的执行流程。

以 Linux 的实现为例，内核会根据创建方式准备新任务的内核栈、线程状态以及首次运行所需的执行路径。

当调度器第一次选择这个进程时，就能够通过相应的底层切换机制，让它进入内核中预先准备好的启动流程。

之后，它才逐渐进入正常的运行过程。

所以：

• 老进程再次运行：恢复之前保存的上下文。
• 新进程第一次运行：使用内核准备好的初始上下文。

两者的目的都是让 CPU 能够正确开始执行这个进程，只不过起点不同。

2.6 补充：分时操作系统与实时操作系统

前面我们提到，操作系统会给进程分配时间片，让多个进程轮流使用 CPU。

这种思想与分时操作系统有关。

分时操作系统主要强调多个任务共享 CPU，让用户能够获得及时的交互体验。

例如，我们一边听音乐，一边打开浏览器，再一边运行编辑器。

虽然 CPU 的资源有限，但是操作系统可以通过快速调度，让这些程序看起来像是在同时运行。

而实时操作系统更加关注任务能否在规定时间内完成。

例如，在工业控制、汽车控制等场景中，有些任务不仅要求执行结果正确，还要求在规定的时间范围内完成。

两者的关注重点不同：

对比	分时操作系统	实时操作系统
主要目标	提高交互体验和资源利用率	满足任务的时间约束
关注重点	响应速度、公平性	时间确定性
调度特点	多任务共享 CPU	根据实时任务需求调度

需要注意，实时系统不一定完全不使用时间片，分时系统也可能有优先级调度。这里主要是从设计目标上进行区分。

到这里，我们已经弄清楚了进程为什么需要切换，以及切换时如何保存和恢复运行现场。

但是还有一个问题没有解决：

假设现在有十几个进程都处于就绪状态，操作系统应该选择哪一个？

这就进入下一部分——进程调度。

三、O(1) 调度算法与调度队列

3.1 从进程切换到进程调度

前面我们讲了进程切换。

进程切换解决的是：当前进程离开 CPU 后，如何保存它的运行现场，再让另一个进程继续执行。

而进程调度解决的是另一个问题：

当多个进程都想使用 CPU 时，操作系统应该选择谁？

这两个概念虽然经常一起出现，但它们不是一回事。

我们可以这样理解：

• 进程调度：决定下一个运行的进程是谁。
• 进程切换：真正完成从当前进程到下一个进程的运行环境切换。

例如：

进程 A：就绪
进程 B：就绪
进程 C：就绪

现在 CPU 正在运行进程 A。

A 的时间片用完后，操作系统需要从 B 和 C 中选择一个。

假设选择了 B。

那么，调度器负责做出选择，底层上下文切换机制负责让 CPU 从 A 转换到 B。

因此，进程调度和进程切换是相互配合的两个过程。

那么，操作系统选择进程时依据什么？

最重要的依据之一就是优先级。

我们之前学习过，进程优先级决定了进程获得 CPU 资源的竞争顺序。

一般来说，优先级越高，进程越容易优先获得 CPU。

但是，系统中的进程数量可能非常多，如果每次调度都从头开始遍历所有进程，再寻找优先级最高的那个，效率会不会很低？

这就需要设计一种更加高效的数据结构。

经典的 Linux O(1) 调度器，就是为了解决这类调度效率问题而设计的。

3.2 优先级数组：把进程按照优先级分类

先假设系统中有很多进程：

进程 A：优先级 5
进程 B：优先级 2
进程 C：优先级 8
进程 D：优先级 2
进程 E：优先级 5

如果每次调度都遍历所有进程，逐个比较优先级，最后找出最高优先级的进程，那么进程数量越多，需要检查的对象就越多。

有没有更简单的方法？

我们可以提前按照优先级，把进程分组。

例如：

优先级 2：A、B
优先级 5：C、D
优先级 8：E

这样，当操作系统需要寻找最高优先级的进程时，就不必再逐个比较每个进程。

只需要找到优先级最高的非空队列，再从这个队列中取出一个进程即可。

这就是优先级数组的基本思想。

在经典 Linux O(1) 调度器中，系统使用一个优先级数组来组织可运行进程。

每个优先级对应一个队列，同一优先级的进程放在同一个队列中。

可以简化成下面的结构：

优先级数组
    |
    +-- queue[0]   -> 进程链表
    |
    +-- queue[1]   -> 进程链表
    |
    +-- queue[2]   -> 进程链表
    |
    +-- queue[3]   -> 进程链表
    |
    +-- ...

注意，这里的每个 queue 本质上是一个链表队列。

同一优先级的多个进程可以通过链表连接起来，操作系统从对应队列中选择进程。

为什么要使用链表？

因为进程会不断地加入队列、离开队列以及调整位置。

链表比较适合这种频繁插入和删除的场景。

我们之前学习过 Linux 内核中的 list_head，它就是一种侵入式双向链表结构。

在经典 O(1) 调度器中，优先级队列就利用链表组织进程。

那么，优先级数组到底有多少个位置？

经典 O(1) 调度器使用 140 个优先级。

其中：

• 0～99：实时进程优先级。
• 100～139：普通进程优先级。

这里要注意，Linux 的优先级数值与我们日常理解的数字大小相反：

数值越小，优先级越高。

例如：

优先级 2 > 优先级 5 > 优先级 8

优先级 2 的进程会比优先级 8 的进程更优先获得 CPU。

这 140 个优先级对应 140 个队列。

但是，新的问题又出现了：

如果有 140 个队列，操作系统每次调度都要从 queue[0] 开始，一个一个检查到 queue[139]，才能找到第一个非空队列吗？

如果还是这样，就没有真正解决遍历问题。

于是，经典 O(1) 调度器又引入了一个重要的数据结构——Bitmap。

3.3 如何快速找到最高优先级的进程？

我们先想一个简单的问题：

如果一个数组中有很多队列，我只想知道哪些队列不为空，应该怎么做？

其实不需要把每个队列中的进程都检查一遍。

我们只需要额外维护一张表，记录每个队列是否为空就可以了。

这张表就是位图（Bitmap）。

Bitmap 的核心思想非常简单：

用一个二进制位表示一个队列的状态。

例如：

优先级：  0 1 2 3 4 5 6 7

Bitmap：  0 0 1 0 1 1 0 0

我们规定：

• 0：对应优先级的队列为空。
• 1：对应优先级的队列不为空。

那么上面的 Bitmap 就表示：

优先级为 2、4、5 的队列中存在可运行进程。

这样，操作系统就不需要挨个检查队列了。

只要查看 Bitmap，就能够知道哪些优先级有进程等待运行。

（1）Bitmap 如何帮助调度器找到进程？

假设现在有三个非空队列：

优先级 2：有进程
优先级 4：有进程
优先级 5：有进程

由于数值越小，优先级越高。

所以，操作系统应该选择优先级 2 对应的队列。

而 Bitmap 可以通过寻找第一个置位的位置，快速找到优先级最高的非空队列。

（2）如何快速找到第一个置位的位置？

这就涉及 CPU 提供的一些位扫描指令。

例如，在 x86 架构中，可以使用 BSF（Bit Scan Forward）等指令查找一个数中最低位的 1 所在的位置。

Linux 内核也提供了相应的位图操作接口，例如：

find_first_bit()

具体实现会根据架构和内核版本有所不同。

我们不需要在这里深入汇编指令，只需要理解：

CPU 可以利用专门的位操作指令，快速定位 Bitmap 中第一个置位的位置。

这样，调度器就能够快速找到最高优先级的非空队列。

（3）为什么叫 O(1)？

我们之前学习算法时，接触过时间复杂度。

例如：

• O(1)：操作次数不随数据规模增长。
• O(N)：数据量增加，操作次数也会相应增加。
• O(N²)：数据量增加时，操作次数增长得更快。

如果每次调度都要遍历 N 个进程，那么时间复杂度可能达到 O(N)。

而经典 O(1) 调度器通过固定数量的优先级队列和 Bitmap，避免了随着可运行进程数量增加而进行线性遍历。

因为优先级数量是固定的，查找最高优先级非空队列的操作不需要遍历所有进程。

所以，经典调度器的选择操作可以做到 O(1)。

这里的 O(1) 主要指调度器选择可运行任务的核心操作，而不是说进程调度和上下文切换中的所有操作都永远只需要一步。

3.4 活跃队列与过期队列：解决进程饥饿问题

到目前为止，我们已经知道：

经典 O(1) 调度器通过优先级数组和 Bitmap，可以快速找到优先级最高的非空队列。

但是，这样还有一个问题。

假设系统中有两个进程：

进程 A：优先级较高
进程 B：优先级较低

如果 A 一直处于就绪状态，并且不断获得 CPU，那么 B 会不会一直等下去？

有可能。

如果一个低优先级进程长期得不到 CPU，就会产生**进程饥饿（Starvation）**问题。

那么，操作系统应该怎么处理？

经典 O(1) 调度器使用了一个非常巧妙的设计：

活跃队列（Active Array）和过期队列（Expired Array）。

先不要急着看代码，我们先理解它们为什么存在。

（1）什么是活跃队列？

活跃队列中存放的是当前调度周期内还可以继续使用时间片的可运行进程。

可以理解成：

这些进程已经获得了当前调度周期的运行资格，只要时间片还有剩余，就可以继续参与调度。

（2）什么是过期队列？

当一个普通进程的时间片用完后，它就不能继续使用当前调度周期分配给自己的时间了。

此时，调度器会根据它的优先级等信息重新计算相关调度参数，并将它放入过期队列，等待下一个调度周期。

所以：

• Active Array：当前调度周期内还有运行机会的进程。
• Expired Array：当前调度周期内已经用完时间片、等待下一轮的进程。

注意，这里的过期并不是进程已经结束，更不是进程退出了。

它只是表示当前调度周期的时间片已经用完。

（3）为什么需要两个队列？

假设现在有 A、B、C 三个进程。

它们最初都在活跃队列中：

Active Array

A：还有时间片
B：还有时间片
C：还有时间片

随着 CPU 不断调度：

• A 的时间片用完，进入过期队列。
• B 的时间片用完，进入过期队列。
• C 的时间片用完，进入过期队列。

最终：

Active Array：空

Expired Array：
    A
    B
    C

此时，当前活跃队列已经没有可运行进程了。

那么怎么办？

经典 O(1) 调度器不会重新创建一套队列，也不需要把 A、B、C 一个一个搬回去。

它只需要交换两个队列的指针。

（4）指针交换：两个队列互换身份

我们先看交换之前：

active  -----> 原来的活跃队列
expired -----> 原来的过期队列

当活跃队列为空时，调度器交换两个指针：

交换之前：

active  -----> 空队列
expired -----> A、B、C


交换之后：

active  -----> A、B、C
expired -----> 空队列

注意：

这里交换的是两个队列的指针，并不是把链表中的所有进程重新复制一遍。

原来的过期队列变成新的活跃队列，原来的活跃队列则变成新的过期队列。

这样，A、B、C 就能够进入下一轮调度。

整个操作非常高效。

（5）双队列如何帮助缓解进程饥饿？

假设低优先级进程 B 的时间片用完了。

它会进入过期队列。

即使高优先级进程 A 在当前周期内多次获得 CPU，B 也不会因为每次都要和 A 重新竞争当前活跃队列，而被无限期地留在原地。

当活跃队列中的进程都用完时间片之后，两个队列就会交换。

B 就有机会进入新的活跃队列，重新参与调度。

因此，双队列设计可以帮助管理不同调度周期中的运行机会，缓解进程饥饿问题。

不过要注意，O(1) 调度器并不是简单地保证所有进程完全公平。它还会结合动态优先级、交互性等因素调整调度行为。

3.5 串联整个 O(1) 调度过程

前面我们分别讲了优先级数组、Bitmap、Active Array 和 Expired Array。

现在把它们放在一起，看看一次完整的调度过程。

假设当前 CPU 正在运行进程 A。

系统中还有 B、C、D 等进程处于就绪状态。

第一步：进程 A 的时间片用完。

时钟中断让内核获得处理时机，内核发现 A 需要重新参与调度。

第二步：处理进程 A 的时间片。

如果 A 的时间片已经用完，就需要根据调度规则重新计算相关参数，并放入对应的过期队列。

第三步：检查活跃队列。

调度器查看当前 Active Array。

如果里面还有可运行进程，就继续从活跃队列中选择。

如果活跃队列已经为空，就交换 Active Array 和 Expired Array 的指针。

第四步：利用 Bitmap 查找最高优先级队列。

调度器通过 Bitmap 找到第一个非空优先级队列。

由于数值越小优先级越高，因此找到的就是当前应该优先考虑的队列。

第五步：从链表中取出进程。

找到对应优先级队列后，调度器从链表中选择一个进程。

假设选中了 B。

第六步：切换进程。

调度器确定下一个运行的进程是 B，接下来由底层上下文切换机制完成运行环境的切换。

保存 A 的必要上下文，恢复 B 的上下文。

最终，CPU 就开始执行 B。

整个过程可以用下面的图来理解：

             进程 A 正在运行
                    |
                    v
             时间片用完
                    |
                    v
          A 进入 Expired Array
                    |
                    v
             检查 Active Array
                    |
           +--------+--------+
           |                 |
         不为空              为空
           |                 |
           |                 v
           |          交换两个队列指针
           |                 |
           +--------+--------+
                    |
                    v
              检查 Bitmap
                    |
                    v
          找到最高优先级非空队列
                    |
                    v
             从链表取出进程 B
                    |
                    v
              上下文切换
                    |
                    v
               进程 B 运行

这样，我们就把 O(1) 调度器的几个核心组成部分串起来了。

可以发现，它的设计思路其实很清晰：

• 优先级数组：负责按照优先级组织进程。
• Bitmap：负责快速找到非空队列。
• Active Array：管理当前调度周期内的可运行进程。
• Expired Array：管理时间片已经用完、等待下一轮的进程。
• 指针交换：快速完成两个调度周期之间的切换。

这些数据结构共同配合，完成进程的选择和调度。

3.6 调度队列的其他成员

除了前面介绍的优先级数组和 Bitmap，经典 O(1) 调度器还需要维护一些其他信息。

这些信息主要用于记录运行队列的状态以及统计调度情况。

（1）每个 CPU 的运行队列 Runqueue

在多核 CPU 系统中，不同 CPU 核心可以同时运行不同的进程。

因此，经典 O(1) 调度器会为每个 CPU 维护自己的运行队列。

每个 CPU 都有对应的调度数据结构，管理分配给这个 CPU 的可运行任务。

这样做可以减少不同 CPU 之间对同一个运行队列的竞争，也方便进行负载均衡。

（2）nr_active

用于记录当前运行队列中可运行任务的数量。

调度器可以通过它了解当前有多少任务处于可运行状态。

（3）nr_switches

用于记录上下文切换次数。

操作系统可以通过相关统计信息了解系统发生了多少次进程或线程切换。

（4）cpu_load

用于记录和计算 CPU 负载相关的信息。

内核可以利用这些信息辅助判断 CPU 的工作负载，并进行相应的调度和负载均衡。

需要注意，这些字段的具体定义和使用方式会随着内核版本变化，不能把某个历史版本中的字段直接当成当前 Linux 的统一实现。

3.7 PRI 与 NI：为什么修改优先级要通过 NI？

前面我们说过，优先级决定了进程参与 CPU 竞争时的顺序。

那么，如果我们想让某个进程更容易获得 CPU，应该怎么调整它的优先级？

在 Linux 中，我们经常会遇到两个概念：

• PRI：优先级。
• NI：nice 值。

它们之间有什么关系？

（1）什么是 NI？

NI 就是 nice 值，也叫友好值。

它的取值范围通常是：

-20 ～ 19

其中：

• NI 越小，进程越容易获得 CPU。
• NI 越大，进程越不容易获得 CPU。

例如：

进程 A：NI = -5
进程 B：NI = 0
进程 C：NI = 10

在其他条件相同的情况下，A 的调度优先级会高于 B，B 又会高于 C。

（2）什么是 PRI？

PRI 是系统显示和描述进程优先级时常见的字段。

在 Linux 的普通进程中，优先级数值越小，通常表示优先级越高。

因此：

PRI 数值越小
      |
      v
优先级越高
      |
      v
越容易获得 CPU

不过，ps、top 等工具显示的 PRI/PR 是面向用户的优先级表示，和内核内部调度器使用的优先级字段不能完全简单地画等号。

（3）NI 和 PRI 有什么关系？

在经典 O(1) 调度器中，普通进程的静态优先级会受到 nice 值影响。

可以先简单理解为：

NI 改变
   |
   v
静态优先级受到影响
   |
   v
动态优先级也会受到影响
   |
   v
影响进程参与调度的顺序

经典 O(1) 调度器还会根据进程的交互性等因素计算动态优先级，因此并不是只看 NI 一个值。

（4）为什么不直接修改 PRI？

因为 PRI 是调度器内部根据调度规则维护和计算的结果之一。

如果直接随意修改它，就可能破坏调度器原有的优先级管理逻辑。

而 NI 是专门提供给用户调整普通进程调度倾向的参数。

因此，我们通常通过调整 nice 值来影响普通进程的优先级。

Linux 中可以使用：

nice -n 10 ./a.out

让程序以指定的 nice 值启动。

也可以使用：

renice 10 -p 1234

调整 PID 为 1234 的进程的 nice 值。

其中，普通用户通常只能提高 nice 值，也就是降低进程的调度优先级；想要提高进程优先级，通常需要相应的权限。

（5）修改 NI 后，进程会发生什么变化？

当 nice 值发生变化后，调度器会根据新的参数调整普通进程的调度优先级。

在经典 O(1) 调度器中，进程的动态优先级还会结合其他因素进行计算。

当进程时间片用完、需要重新进入调度队列时，调度器会根据更新后的优先级，将它放入对应的优先级队列。

这样，进程之后参与 CPU 竞争时，就会按照新的优先级参与调度。

这里需要记住：

NI 是用户可以调整的 nice 值，PRI 是常见的优先级显示字段，而内核内部还有更具体的静态优先级和动态优先级管理机制。

四、总结：从寄存器到调度队列，理解 Linux 进程运行的完整过程

这篇文章我们主要解决了两个问题：

第一个问题：进程离开 CPU 后，下一次如何继续运行？

因为 CPU 寄存器中的数据会随着程序执行不断变化，所以进程切换时，需要保存当前进程的执行现场，并在下一次运行时恢复。

这就是进程上下文切换的本质。

第二个问题：多个进程都想使用 CPU 时，操作系统如何选择下一个进程？

经典 Linux O(1) 调度器通过优先级数组组织进程，通过 Bitmap 快速查找最高优先级的非空队列，再利用 Active Array 和 Expired Array 管理不同调度周期中的进程。

当活跃队列为空时，只需要交换两个队列的指针，就能够快速开始下一轮调度。

最后，我们把整个过程串起来：

多个进程处于就绪状态
          |
          v
       进程调度
          |
          v
  O(1) 调度器选择进程
          |
          v
    确定下一个进程
          |
          v
     上下文切换
          |
          v
  保存当前进程的现场
          |
          v
  恢复下一个进程的现场
          |
          v
       CPU 运行
          |
          v
    时间片用完或阻塞
          |
          v
       再次调度

最后还要补充一点：O(1) 调度器是 Linux 历史上的经典调度器，主要用于早期 Linux 2.6 内核。后来 Linux 引入了 CFS（完全公平调度器），而较新的 Linux 内核又逐步引入了 EEVDF 调度机制。

因此，我们今天学习 O(1) 调度算法，主要是为了理解 Linux 调度器曾经如何利用数据结构优化进程选择过程，以及优先级调度的底层思想。

本篇结束，下一篇继续学习 Linux 进程篇的相关知识！