处理器管理

阅读指南：本章是操作系统的核心机制章节。知识链是线性的：硬件结构 → 中断机制 → 进程抽象 → 线程优化 → 调度算法。每一层都建立在上一层之上，建议严格按顺序阅读。

1. 处理器基础

1.1 CPU 的内部结构

理解 CPU 的结构，是理解”中断如何工作”和”进程切换如何发生”的前提。

┌─────────────────────────────────────────────────────┐
│                     CPU                             │
│                                                     │
│  ┌──────────┐    ┌──────────┐    ┌───────────────┐  │
│  │  控制单元 │    │   ALU    │    │  寄存器组      │  │
│  │  (CU)    │    │ 算术逻辑 │    │ (PC/IR/PSW...) │  │
│  └──────────┘    └──────────┘    └───────────────┘  │
│            ↕           ↕               ↕            │
│                  内部总线                            │
└─────────────────────────────────────────────────────┘
                       ↕
                  系统总线（连接内存、I/O 设备）

1.2 寄存器分类

CPU 的寄存器分为两大类，这一分类直接对应”用户模式”和”内核模式”的权限边界。

用户可见寄存器

所有程序（用户态和内核态）均可读写：

• 通用数据寄存器：暂存运算操作数和结果（x86: EAX, EBX…）
• 地址寄存器：
  • 索引寄存器：支持数组/循环的地址计算
  • 栈指针（SP）：指向当前栈顶
  • 段地址寄存器：存放段基址（段式管理中使用）

控制与状态寄存器

仅特权程序（OS 内核）可以修改：

寄存器	全称	作用
PC	Program Counter	下一条将执行的指令地址
IR	Instruction Register	当前正在执行的指令
CC	Condition Code	上次运算的结果标志（零/负/进位/溢出）
标志位	—	中断允许/屏蔽位、处理器模式位、内存保护信息

1.3 程序状态字（PSW）

PSW（Program Status Word） 是操作系统概念层面的核心数据结构，代表进程在某一时刻的”运行快照”。

PSW 包含：
┌───────┬──────┬──────┬──────────┬──────────┬────────┐
│  PC   │  IR  │  CC  │ 中断允许 │ 处理器模式│ 内存保护│
└───────┴──────┴──────┴──────────┴──────────┴────────┘

关键认识：进程切换的本质就是保存旧进程的 PSW、恢复新进程的 PSW。PSW 是进程执行状态的完整摘要。

在某些硬件上，PSW 对应一个专用硬件寄存器（如 IBM System/390）；在 x86 上，它被拆分到多个寄存器（EFLAGS, CS, EIP 等）。

1.4 指令执行流程

一条机器指令的执行遵循固定的三步循环：

┌─────────────────────────────────────────────────────────┐
│                   指令执行周期                            │
│                                                         │
│  ①取指  →  ②解码  →  ③执行                              │
│  PC→IR     ID分析    ALU运算                             │
│  PC+1      确定操作数  写回结果                           │
│                       更新PC/CC                         │
│                         ↓                              │
│                   ④检查中断  ← 这是中断发生的时机！        │
│                    ↓          ↓                         │
│                  无中断      有中断                       │
│                  继续①      跳入中断处理                  │
└─────────────────────────────────────────────────────────┘

关键细节：”检查中断”这个微操作被插入在每条指令的执行周期末尾，而不是任意时刻。这意味着中断只在指令边界处被响应，保证了指令的原子性。

1.5 指令流水线

问题：取指、解码、执行三个阶段，每个阶段使用不同的硬件单元。若顺序执行，大部分时间硬件处于空闲状态。

解决：流水线——让多条指令的不同阶段在同一时刻并发执行：

时间轴 →
指令 1：[取指][解码][执行]
指令 2：       [取指][解码][执行]
指令 3：              [取指][解码][执行]
指令 4：                     [取指][解码][执行]

工程代价：流水线引入了”冒险”问题（数据冒险、控制冒险、结构冒险），中断发生时需要清空流水线——这是中断响应有一定延迟的原因之一。

1.6 处理器模式

核心问题：如何防止用户程序破坏 OS 内核或其他进程？

解决方案：处理器支持不同的执行模式，在不同模式下，指令的执行权限不同。

Ring 0（内核模式）：可执行所有指令，包括特权指令
Ring 1
Ring 2
Ring 3（用户模式）：只能执行非特权指令

实践中大多数 OS（Linux、Windows）只使用 Ring 0 和 Ring 3 两级。

特权指令的例子：

• 启动/停止 I/O 设备
• 修改 PC（直接跳转到任意地址）
• 修改内存保护寄存器
• 关中断/开中断
• 访问控制寄存器（CR0、CR3 等）

为什么用户程序不能执行这些？ 若用户程序可以随意修改内存保护寄存器，它就能访问任意进程的内存；若能关中断，它就能阻止 OS 夺回 CPU 控制权。特权机制是 OS 安全的硬件基础。

1.7 模式切换

处理器模式的切换是受控的，不能由程序随意触发。

用户模式 → 内核模式（只有三种触发方式）：

触发方式	例子
中断（外部）	I/O 完成、时钟中断
异常（内部）	除零、缺页、越界访问
系统调用（主动陷入）	read(), write(), fork()

内核模式 → 用户模式：

• 只能通过执行特殊的”中断返回指令”（x86: iret）完成
• 该指令同时恢复 PC 和 PSW，保证原子性切换

工程意义：这种单向受控的切换机制，使得”进入内核”的路径是完全可控的——OS 知道用户程序只能通过特定入口（系统调用表、中断向量表）进入内核，而无法跳到任意内核地址。

---

2. 中断管理

2.1 中断的地位

“操作系统是中断驱动的。” ——中断是激活 OS 的唯一方式。

OS 并不是一个持续运行的程序，它更像一个”被动响应者”：

平时：用户程序运行，OS 静止
        ↓ 发生中断（I/O完成 / 时钟 / 系统调用 ...）
OS：被激活，处理事件，再选择下一个程序运行
        ↓ 执行中断返回
用户程序：恢复运行

没有中断，OS 就无法在用户程序运行时夺回 CPU 控制权，多道程序设计也就无从实现。

2.2 中断的三大类型

广义中断（中断 = 一切需要 CPU 暂停当前任务去处理的事件）在具体实现中分为三类：

类型	来源	与当前指令的关系	典型例子
中断（狭义）	处理器外部硬件	无关（异步）	I/O 中断、时钟中断、键盘输入
异常	当前指令执行本身引发	有关（同步）	除零、缺页、非法指令、越界
系统调用	程序主动执行陷入指令	有关（同步，主动）	read(), fork(), exit()

同步 vs 异步：

• 同步：中断与当前执行的指令直接相关，可重现（同样的程序序列必然在同一位置触发）
• 异步：中断由外部事件引发，与当前指令无关，发生时间不可预测

2.3 各类中断的处理原则

处理器硬件故障中断

• 触发：CPU、内存、总线等硬件物理故障
• 处理：保护现场 → 停机 → 向操作员报告
• 注意：这类中断优先级最高，因为硬件故障可能损坏数据

程序性中断（异常）

异常类型	触发条件	处理方式
算术异常	除零、浮点溢出	通知用户程序，允许用户自定义处理
指令异常	非法指令、越界访问、权限违反	终止进程（不可恢复）
虚拟地址异常	访问不在主存的页（缺页）	调入页面后重新执行该指令

为什么缺页后要重新执行，而不是继续执行？ 因为引发缺页的那条指令没有完成——它的内存访问失败了。只有调入页面、让访问成功，这条指令才算执行完毕。

系统调用（自愿性中断）

用户程序执行 INT n / SYSCALL 指令
        ↓
CPU 模式切换到内核态
        ↓
OS 读取调用号（功能号）
        ↓
查系统调用表，跳转对应处理函数
        ↓
处理完毕，返回结果，切换回用户态

系统调用是用户程序主动请求 OS 服务的标准接口。它与普通函数调用的核心区别：系统调用会触发模式切换，进入内核执行。

I/O 中断

I/O 设备完成操作 → 向 CPU 发送中断信号
        ↓
OS 检查 I/O 状态
  ├── 成功 → 唤醒等待该 I/O 的进程（进入就绪队列）
  └── 失败 → 重试 or 向用户报告错误 or 人工干预

外部中断

• 时钟中断：实现时间片轮转的基础，OS 借此定期夺回 CPU 控制权
• 键盘/鼠标：将输入事件通知 OS
• 关机/重启信号：触发系统清理流程

2.4 中断系统的实现：硬件与软件协同

中断系统分为两个子系统，严格分工：

┌──────────────────────────────────────────────────┐
│              中断系统                             │
│                                                  │
│  硬件子系统（中断响应）                            │
│  ─────────────────────────                       │
│  · 检测中断信号                                   │
│  · 判断是否屏蔽                                   │
│  · 选出最高优先级中断                              │
│  · 保存 PC/PSW 到核心栈                           │
│  · 跳转到中断处理程序入口                          │
│                                                  │
│  软件子系统（中断处理）                            │
│  ─────────────────────────                       │
│  · 保存其余寄存器状态                              │
│  · 识别中断源（分析中断码）                        │
│  · 查中断向量表，调用具体处理子程序                 │
│  · 恢复现场，决定返回哪个进程                      │
└──────────────────────────────────────────────────┘

硬件响应过程（自动完成，无需软件介入）

① 在指令执行周期末尾检测中断信号
        ↓
② 判断该中断是否被屏蔽（屏蔽位 = 1 → 忽略）
        ↓
③ 选择优先级最高的待处理中断
        ↓
④ 将当前 PC 和 PSW 压入核心栈（保护断点）
        ↓
⑤ 从中断向量表取出处理程序入口地址，跳转

中断向量表：一个固定地址的数组，每个中断号对应一个处理程序的入口地址。硬件直接用中断号作为索引查表，无需软件参与寻址。

软件处理过程（中断处理程序）

① 保存硬件未自动保存的寄存器（通用寄存器等）
        ↓
② 分析 PSW 中的中断码，确定中断来源
        ↓
③ 调用对应的中断处理子程序（查中断向量表）
        ↓
④ 处理完毕，决定恢复方向：
   ├── 直接返回被中断进程（无状态转换）
   └── 调整进程队列 + 触发进程调度

2.5 多中断处理

中断屏蔽

通过设置屏蔽位（mask bit），OS 可以在处理某个中断时，选择性地忽略其他中断。

中断屏蔽寄存器：每位对应一类中断
  bit = 1 → 该类中断被屏蔽（忽略）
  bit = 0 → 该类中断可被响应

用途：在执行原子操作（如修改进程队列）时，临时屏蔽所有中断，防止被打断导致数据结构不一致。

中断优先级

当多个中断同时到来时，按优先级决定响应顺序：

优先级（从高到低）：
  硬件故障 > 系统调用 > 程序异常 > 时钟/外部 > I/O > 关机

直觉：越是”不处理就会丢失数据或系统崩溃”的中断，优先级越高。

中断嵌套

处理优先级较低的中断 X 的过程中，更高优先级的中断 Y 到来，可以打断 X 的处理：

正常执行
    ↓ 中断 X（优先级低）
处理 X ──────────────────────────────→
    ↓ 中断 Y（优先级高）
    处理 Y ────────→
                   ↓ Y 处理完
    继续处理 X ────────────────────────→
                                      ↓ X 处理完
继续正常执行

后响应的 Y，比先响应的 X 先处理完——这是嵌套与顺序的关键区别。

嵌套层数需有上限（通常 ≤ 3 层），防止核心栈溢出。

两个经典场景：

场景一：X 和 Y 同时到来，Y 被屏蔽
  → 先响应并完整处理 X，再响应处理 Y（顺序执行）

场景二：X 和 Y 同时到来，Y 未被屏蔽且优先级更高
  → 先响应 X，Y 立即抢占 X，Y 先做完，再回来做 X（嵌套执行）

---

3. 进程管理

3.1 为什么需要进程？

问题：多道程序设计中，多个程序同时驻留内存并轮流使用 CPU。OS 如何追踪和管理每个”正在运行的程序”？

回答：程序本身是静态的（一段代码），而”运行”是动态的。同一份程序可以被多个用户同时使用（如 shell），每次运行都有独立的状态。

OS 需要一个管理实体来表示”程序的一次运行”——这就是进程（Process）。

进程的形式化定义：程序关于某数据集合的一次运行活动，是操作系统资源分配和处理器调度的独立单位。

3.2 进程的五元组描述

一个进程在任意时刻，可以用五元组完整描述：

进程 = (P, C, D, R, PSW)

P   — 进程控制块（OS 管理数据结构）
C   — 内存中的代码（程序文本段）
D   — 内存中的数据（数据段 + 堆 + 栈）
R   — 通用寄存器的当前值
PSW — 程序状态字（PC/IR/CC/标志位）

R 和 PSW 是进程”当前执行位置”的快照，进程切换时需要完整保存和恢复。

3.3 进程状态模型

三态模型（基础）

                    调度选中
        ┌─────────────────────────────────┐
        ↓                                 │
  ┌──────────┐    时间片到 / 被抢占    ┌──────────┐
  │  运行态  │ ─────────────────────→ │  就绪态  │
  │ Running  │                        │  Ready   │
  └──────────┘                        └──────────┘
        │                                 ↑
        │ 等待资源/I/O/信号                │ 资源满足/I/O完成
        ↓                                 │
  ┌──────────┐                            │
  │  等待态  │ ───────────────────────────┘
  │ Waiting  │
  └──────────┘

关键约束（必须记住）：

• ❌ 不存在：等待态 → 运行态（等待满足后必须先进就绪队列排队，再被调度）
• ❌ 不存在：就绪态 → 等待态（就绪进程不会主动等待资源）
• ✅ 运行 → 等待：进程主动请求资源或 I/O，得不到立即满足
• ✅ 等待 → 就绪：I/O 完成或资源可用，被 OS 唤醒
• ✅ 就绪 → 运行：调度程序选中该进程
• ✅ 运行 → 就绪：时间片用完，或被更高优先级进程抢占

为什么不能等待态 → 运行态？ 调度的公平性要求——多个进程都在等待，等待结束时应该进入就绪队列，与其他就绪进程公平竞争 CPU，而不是某个进程等待结束就直接独占 CPU。

五态模型（加入挂起）

动机：系统中进程数过多，内存不足，需要暂时将某些进程”冻结”并换出到磁盘。

┌──────────┐   挂起   ┌──────────────┐
│  就绪态  │ ────────→│  挂起就绪态  │
└──────────┘          └──────────────┘
      ↑                      ↓ 激活
┌──────────┐   挂起   ┌──────────────┐
│  等待态  │ ────────→│  挂起等待态  │
└──────────┘          └──────────────┘

挂起 vs 等待的本质区别：

	等待态	挂起态
内存	进程仍在内存中	进程被换出到磁盘
已占资源	保留（等待的是新资源）	全部归还
调度	不参与，但随时可被唤醒入就绪	完全不参与调度
恢复条件	等待事件发生	需被 OS 显式激活

3.4 进程控制块（PCB）

PCB 是 OS 管理进程的核心数据结构，记录进程的一切必要信息。

PCB 包含的三类信息

标识信息（区分进程）：

• 系统分配的进程 ID（PID）
• 进程组 ID
• 用户定义的进程名
• 父进程 ID

现场信息（进程切换时保存/恢复）：

• 通用寄存器值（R0, R1, …）
• PC（下一条指令地址）
• PSW（处理器状态字）
• 核心栈指针 / 用户栈指针

控制信息（OS 决策依据）：

• 调度状态（运行/就绪/等待）和优先级
• 代码段和数据段的地址
• 队列链接指针（父子兄弟进程的连接）
• 进程间通信信息（消息队列、信号量）
• 资源清单（已分配的内存、文件描述符等）
• 处理器使用时间（用于调度和计费）

进程映像 vs PCB

常见误区：进程映像 ≠ PCB。

进程映像（某时刻进程在内存中的完整实体）：
┌─────────────┐
│     PCB     │ ← PCB 只是其中一部分
├─────────────┤
│   程序块     │ ← 代码段
├─────────────┤
│   数据块     │ ← 数据段 + 堆
├─────────────┤
│   核心栈    │ ← 进程在内核态时使用的栈
└─────────────┘

进程上下文

进程上下文（Process Context）：进程执行所需的完整环境，分三层：

用户级上下文：用户程序块、数据区、用户栈、共享内存区
     ↕ 系统调用/中断跨越
寄存器上下文：PSW、栈指针、通用寄存器（切换时保存/恢复的核心）
     ↕
系统级上下文：PCB、内存区描述表、核心栈（OS 在内核态为该进程维护的数据）

3.5 进程队列管理

OS 维护多个队列组织进程：

就绪队列（通常按优先级排序）：
  PCB_A → PCB_C → PCB_F → ...

等待队列（每类资源一个队列）：
  磁盘I/O等待队列：PCB_B → PCB_D → ...
  网络等待队列：   PCB_E → ...
  信号量等待队列： PCB_G → ...

PCB 之间通过链表指针连接（PCB 中的”队列指引元”字段），O(1) 插入/删除。

3.6 进程控制原语

原语（Primitive）：不可分割的操作，执行过程中不允许被中断。通过关中断实现原子性。

创建进程

① 分配 PCB，初始化标识信息
② 建立进程映像（分配内存，加载代码和数据）
③ 初始化 PCB：设置初始 PC（程序入口）、优先级等
④ 分配必要资源（文件描述符等）
⑤ 将 PCB 插入就绪队列

撤销进程

① 将进程从所在队列中摘除
② 递归撤销所有子进程
③ 释放占用的全部资源（内存、文件、设备）
④ 回收 PCB

阻塞进程

（进程自己调用，等待某事件）
① 保存当前处理器现场到 PCB
② 修改 PCB 状态：运行态 → 等待态
③ 将 PCB 插入对应等待队列
④ 调用进程调度程序，选择新进程运行

唤醒进程

（OS 在事件发生时调用，如 I/O 完成）
① 将 PCB 从等待队列中摘除
② 修改 PCB 状态：等待态 → 就绪态
③ 将 PCB 插入就绪队列
④ 若该进程优先级高于当前运行进程 → 触发抢占

注意：唤醒和阻塞必须成对使用——有阻塞必有对应的唤醒事件，否则进程将永久阻塞（死锁或饥饿的一种形式）。

3.7 进程切换的完整过程

前提：进程切换必须在内核模式下完成。

触发条件（以时钟中断为例）：
  CPU 在用户模式执行进程 A
        ↓ 时钟中断
① 正向模式切换（硬件自动）
   · 保存 A 的 PC/PSW 到 A 的核心栈
   · 切换到内核模式
   · 跳转到时钟中断处理程序

② 保存被中断进程 A 的其余现场
   · 保存通用寄存器到 A 的 PCB

③ 处理时钟中断
   · 更新时钟计数、时间片统计

④ 判断是否需要进程切换
   · A 的时间片用完 → 需要切换
   · 保存 A 的核心栈指针到 A 的 PCB
   · 修改 A 的 PCB 状态：运行态 → 就绪态
   · 将 A 的 PCB 插入就绪队列

⑤ 进程调度
   · 从就绪队列选择下一个进程 B

⑥ 恢复进程 B
   · 修改 B 的 PCB 状态：就绪态 → 运行态
   · 恢复 B 的地址空间（切换页表）
   · 从 B 的 PCB 恢复核心栈指针 SP
   · 从 B 的核心栈恢复通用寄存器

⑦ 逆向模式切换（中断返回指令，如 iret）
   · 从 B 的核心栈弹出 PSW/PC
   · 切换到用户模式
   · 跳转到 B 上次被中断的地址继续执行

哪些中断不触发进程切换？ 若中断处理完毕后，没有进程状态发生转换（即被中断进程仍然是最高优先级就绪进程），则直接返回被中断进程，不进行进程切换。

3.8 fork 系统调用（理解进程创建）

fork() 创建一个与父进程几乎完全相同的子进程（写时复制）。

关键行为：fork() 被调用一次，返回两次：

• 在父进程中返回子进程的 PID（> 0）
• 在子进程中返回 0
• 出错返回 -1

经典题型：以下程序最多创建几个进程？

int main() {
    fork();   // ← ①
    fork();   // ← ②
    fork();   // ← ③
    return 0;
}

main
 ├─ fork①后：main 和 child1
 ├─ fork②后：main、child1、child2（main的子进程）、child3（child1的子进程）
 └─ fork③后：上面4个进程各自再fork，共 4×2 = 8 个进程

规律：n 次无条件 fork()，最终产生 2^n 个进程。

---

4. 多线程技术

4.1 为什么需要线程？

进程的问题：

• 切换开销大：切换进程需要切换地址空间（换页表、刷 TLB），代价高
• 通信代价高：进程间通信需要通过内核（管道、消息队列、共享内存），复杂且慢
• 进程内无法并发：一个进程内只有一条执行路径，无法同时处理多个任务

典型场景：Web 服务器需要同时处理数千个连接请求。用进程实现：每个请求一个进程，切换开销不可接受。

解决思路：将进程的两项核心功能分离：

进程（原来）= 资源分配单位 + 调度执行单位
                    ↓ 分离
进程（新） = 资源分配和保护的独立单位（虚拟地址空间 + 文件句柄 + ...）
线程      = 调度和分派的基本单位（执行路径，轻装运行）

4.2 线程的特征

同一进程内的多个线程：

共享（属于进程，不需要复制）：

• 虚拟地址空间（代码段、数据段、堆）
• 文件描述符
• 进程 ID 和权限

独立拥有（每个线程自己的）：

• 程序计数器（PC）——各自的执行位置
• 执行栈——函数调用链、局部变量
• 线程状态（运行/就绪/睡眠）
• 寄存器上下文

线程切换 vs 进程切换：

进程切换：需要切换地址空间（刷 TLB，换页表）→ 开销大（约 1-10 µs）
线程切换：同进程内，地址空间不变，只切换栈和寄存器 → 开销小（约 0.1-1 µs）

4.3 线程状态

线程只有三态（没有挂起——挂起是进程层面的操作）：

睡眠态 ←────────────── 运行态
  │    等待事件/资源      │
  │                      │ 时间片到/被抢占
  │ 事件/资源满足         ↓
  └─────────────────→ 就绪态

4.4 内核级线程（KLT）vs 用户级线程（ULT）

用户级线程（ULT, User-Level Thread）

线程的创建、调度、同步完全在用户空间由线程库实现，内核不感知线程的存在。

┌────────────────────────────────────┐
│            用户空间                 │
│  线程A  线程B  线程C                │
│    ↕ 线程库管理（用户态调度器）       │
└────────────────────────────────────┘
         ↕ 系统调用（进程级）
┌────────────────────────────────────┐
│            内核空间                 │
│       进程（内核只看到进程）         │
└────────────────────────────────────┘

优点：

• 线程切换无需陷入内核，速度极快
• 可在任何 OS 上实现（无需内核支持）

致命缺点：

• 一个线程阻塞 → 整个进程阻塞（内核不知道进程内部还有其他线程可以运行）
• 无法利用多核处理器（内核调度的是进程，多个 ULT 无法在多个 CPU 核上真正并行）

Jacketing 技术（缓解 ULT 阻塞问题）：

原来：线程 A 调用 read()（阻塞系统调用）
      → 内核阻塞整个进程 → 线程 B/C 也被阻塞

Jacketing：将 read() 包装成非阻塞版本
      → 先调用 select() 检查 I/O 是否就绪
      → 不就绪 → 切换到其他线程，稍后再试
      → 就绪 → 执行真正的 read()

内核级线程（KLT, Kernel-Level Thread）

内核直接管理线程，每个线程在内核中有对应的描述结构。

┌────────────────────────────────────┐
│            用户空间                 │
│  线程A  线程B  线程C                │
└────────────────────────────────────┘
         ↕ 每个线程独立的系统调用
┌────────────────────────────────────┐
│            内核空间                 │
│   KLT_A   KLT_B   KLT_C          │
│       内核调度器直接调度线程          │
└────────────────────────────────────┘

优点：

• 一个线程阻塞，其余线程继续运行
• 支持多核真正并行

缺点：

• 线程切换需要陷入内核，比 ULT 切换慢
• 线程创建/销毁需要系统调用

对比总结

	ULT（用户级）	KLT（内核级）
管理者	用户态线程库	OS 内核
线程阻塞影响	整个进程阻塞	只影响该线程
多核并行	❌ 不支持	✅ 支持
切换开销	小（无需陷入内核）	大（需系统调用）
适用场景	逻辑并发（单核）	物理并行（多核）

4.5 混合策略（M:N 模型）

结合 ULT 和 KLT 的优点：

用户空间：M 个 ULT
              ↕ 多对多映射
内核空间：N 个 KLT（N ≤ M）

工作方式：

• ULT 的创建/调度/同步在用户空间完成（快）
• KLT 的数量由程序员根据硬件和需求调节
• 有 KLT 空闲时，将 ULT 绑定到 KLT 上（活跃态），实现并行
• 阻塞的 ULT 解绑 KLT，让 KLT 去运行其他 ULT

工程实现：Solaris 的轻量级进程（LWP）是这种混合策略的经典案例。现代 Go 语言的 goroutine 调度器也是 M:N 模型的一个实现。

---

5. 处理器调度

5.1 调度的三个层次

OS 中的”调度”不是单一问题，而是分三层：

层次	别称	决策问题	时间尺度
高级调度	长程调度 / 作业调度	允许哪些新进程进入系统（后备队列 → 就绪队列）	分钟级
中级调度	中程调度 / 负载平衡	哪些进程驻留内存（控制挂起/激活）	秒级
低级调度	短程调度 / 进程调度	就绪队列中谁获得 CPU	毫秒级

最重要的是低级调度——它直接决定每一次 CPU 分配，对用户体验影响最直接。

高级调度的作用：在批处理系统中，控制系统中活跃进程的总数（多道程序度），防止内存过载和 CPU 饱和。

中级调度的作用：在负载高峰时挂起部分进程（换出到磁盘），缓解内存和 CPU 压力，之后再激活。

5.2 调度算法的评估指标

设计调度算法时需要权衡多个指标，这些指标往往相互冲突：

指标	含义	谁关心
CPU 利用率	CPU 忙碌的时间比例	系统管理员
吞吐量	单位时间完成的进程数	批处理用户
周转时间	进程从提交到完成的总时间	批处理用户
等待时间	进程在就绪队列中等待的总时间	所有用户
响应时间	从请求提交到首次响应的时间	交互式用户
公平性	每个进程获得公平的 CPU 份额	系统设计者

矛盾举例：最短进程优先（SPN）能最小化平均周转时间，但会导致长进程”饥饿”——公平性极差。

5.3 非抢占式调度算法

FCFS（先来先服务，First Come First Served）

策略：按进入就绪队列的先后顺序分配 CPU，一旦获得 CPU 就运行到结束（或主动放弃）。

示例（到达时间均为 0，服务时间如下）：

进程    服务时间
A         3
B         5
C         1
D         2

FCFS 顺序：A → B → C → D

时间轴：
0    3         8    9   11
|─A──|────B────|─C─|─D─|

等待时间：A=0, B=3, C=8, D=9
平均等待时间 = (0+3+8+9)/4 = 5

缺点：”护航效应”——一个长进程后面的所有短进程都要等待。对 I/O 密集型进程（短 CPU 时间片、频繁等待）特别不利。

SPN（最短进程优先，Shortest Process Next）

策略：选择估计剩余 CPU 时间最短的就绪进程。

优点：在所有非抢占算法中，SPN 给出最小的平均等待时间（可以数学证明）。

缺点：

• 需要预知进程的服务时间——实践中通常用历史执行时间做估计（指数加权平均）
• 长进程饥饿：只要不断有短进程到来，长进程可能永远等不到 CPU

平均等待时间（同上例）：
SPN 顺序：C(1) → D(2) → A(3) → B(5)

时间轴：
0  1   3      6          11
|C|─D─|──A───|─────B─────|

等待时间：C=0, D=1, A=3, B=6
平均等待时间 = (0+1+3+6)/4 = 2.5   ← 比 FCFS 的 5 少了一半

HRRN（最高响应比优先，Highest Response Ratio Next）

动机：SPN 对短进程偏袒，HRRN 通过引入”等待时间”因素来照顾长期等待的进程。

响应比公式：

响应比 = (等待时间 + 估计服务时间) / 估计服务时间
       = 1 + (等待时间 / 估计服务时间)

性质：

• 进程刚到时，响应比 = 1（等待时间 = 0）
• 等待越久，响应比越大，越容易被选中——自动解决饥饿问题
• 服务时间短的进程，响应比增长更快——仍偏袒短进程

代价：每次调度需要计算所有就绪进程的响应比，时间复杂度 O(n)；仍需估计服务时间。

5.4 抢占式调度算法

RR（时间片轮转，Round Robin）

策略：按 FCFS 顺序，每个进程最多运行一个时间片（quantum），时间片用完则强制剥夺 CPU，排到就绪队列末尾。

时间片选择的权衡：

时间片过短 → 切换开销占比过大（假设切换需 1ms，时间片 1ms → 50% 时间浪费在切换）
时间片过长 → 响应时间变差，退化为 FCFS
经验法则：时间片 = 10-100ms，切换时间 ~1ms（切换开销约占 1%）

优点：

• 不需要预知进程的服务时间（只需时钟中断）
• 对所有进程公平，响应时间有保证
• 适合交互式系统

示例（时间片 = 1，进程 A:3, B:5, C:1, D:2）：

时间轴：
0 1 2 3 4 5 6 7 8 9 10 11
A B C D A B D A B   B    B

SRT（最短剩余时间优先，Shortest Remaining Time）

SPN 的抢占版本：新进程到来时，如果其服务时间比当前运行进程的剩余时间更短，立即抢占。

优点：平均等待时间理论上比 SPN 更好（因为更早执行短进程）

缺点：

• 需要实时跟踪所有进程的剩余时间
• 长进程饥饿问题更严重（不断被新到的短进程抢占）

多级反馈队列（Feedback）

设计思想：不需要预先知道进程类型（交互式/批处理），让进程自己通过行为”分类”。

结构：

队列 0（最高优先级，时间片最短）：  [新进程优先入这里]
队列 1（次高优先级，时间片较短）：
队列 2（中等优先级，时间片中等）：
队列 3（低优先级，时间片较长）：
...
队列 N（最低优先级，时间片最长/FCFS）：  [长期运行的批处理进程沉到这里]

规则：

• 新进程进入最高优先级队列
• 每次被时钟抢占（时间片用完），降一级队列（表明进程需要较长 CPU 时间）
• 主动放弃 CPU（如等待 I/O），不降级（保持在当前队列）
• 只有高优先级队列为空，才调度低优先级队列的进程

效果：

短进程（交互式）：很快执行完，在高优先级队列里解决，响应时间短
长进程（批处理）：逐渐沉到低优先级队列，获得更长时间片（减少切换）但优先级低

关键洞察：Feedback 对短进程友好的程度超过 RR，因为短进程在高优先级队列竞争者少，等待时间更短。

现代实现：Linux 的 CFS（Completely Fair Scheduler）、Windows 的优先级队列都借鉴了这一思想，实际可有 32-128 个队列（包含实时队列）。

彩票调度（Lottery Scheduling）

思想：给每个进程分配若干”彩票”（表示资源份额），每次调度随机抽一张，持票进程获得 CPU。

进程 A：50 张票（50% 的 CPU 期望）
进程 B：30 张票（30% 的 CPU 期望）
进程 C：20 张票（20% 的 CPU 期望）

优点：

• 支持任意比例的资源分配（增减彩票即可）
• 合作进程可以互相”赠票”（提高彼此的优先级）
• 实现简单，无饥饿（每个进程都有票，总有机会被选中）

缺点：随机性导致短期内可能不公平（虽然长期期望是准确的）。

5.5 调度算法综合对比

算法	抢占	需要预知服务时间	饥饿风险	适用场景
FCFS	❌	❌	无（但短进程等待久）	批处理
SPN	❌	✅	长进程饥饿	批处理（已知服务时间）
SRT	✅	✅	长进程严重饥饿	批处理（可实时估计）
HRRN	❌	✅	无（响应比自动升高）	批处理
RR	✅	❌	无	交互式系统
Feedback	✅	❌	低优先级可能	通用（混合负载）
Lottery	可选	❌	理论上无	需要比例控制的场景

5.6 调度算法演示示例

以下用统一示例展示各算法的差异。

假设（到达时间和服务时间如下）：

进程    到达时间   服务时间
A          0          3
B          2          5
C          4          1
D          6          2

FCFS（非抢占）：

时间：0        3         8    9
      [──A──] [────B────] [C] [──D──]
                                    11
等待时间：A=0, B=1, C=4, D=3   平均=2

SPN（非抢占，在每次有进程完成时选最短的）：

时间：0    3  4       9  10      
      [─A─] [B先等] ... （需逐步分析）
（实际计算需结合到达时间，细节略）

RR（时间片=1）：

A到达时进队，B在t=2到达插队（RR末尾），以此类推
时间：0 1 2 3 4 5 6 7 8 9 10 11
      A A B A B C B D B  B
（C=1片执行完，A=3片，D=2片，B=5片）

Feedback（时间片=1，沉降规则）：

与 RR 的差异：长进程 B 在用完多个时间片后沉入低优先级队列，短进程 C、D 插到 B 前面，响应时间更短。

---

6. 附录：概念速查与常见误区

常见误区

误区	正确理解
“进程映像 = PCB”	PCB 是进程映像的一部分，进程映像还包括程序块、数据块、核心栈
“等待态可以直接变运行态”	不可以。必须先变就绪态，再被调度变运行态
“线程有挂起状态”	没有。挂起是进程层面的操作（涉及换出内存），线程只有运行/就绪/睡眠三态
“ULT 可以利用多核”	不能。内核只看到进程，ULT 绑定在单个进程上，无法分配到多个 CPU 核
“中断后一定发生进程切换”	不一定。若无进程状态转换，中断处理完直接返回被中断进程
“SPN 平均等待时间最短所以最好”	SPN 会导致长进程饥饿，实际系统需要权衡公平性
“时间片越短越好”	不对。时间片过短导致切换开销占比过大，系统效率下降

状态转换合法性速查

运行 → 就绪：✅ 时间片到/被抢占
运行 → 等待：✅ 请求资源/I/O
等待 → 就绪：✅ 资源满足/I/O 完成
就绪 → 运行：✅ 被调度选中

等待 → 运行：❌ 非法（必须经过就绪态）
就绪 → 等待：❌ 非法（就绪进程不会主动等待）

三层调度的触发时机

调度层次	触发时机
高级调度	新作业提交时；当前系统进程数低于阈值时
中级调度	内存不足时（挂起）；内存空闲且挂起进程等待结束时（激活）
低级调度	进程阻塞时；时间片用完时；进程终止时；新进程创建时（抢占型）

本章知识依赖图

CPU 硬件结构（寄存器、指令周期）
            ↓
处理器模式（特权 vs 非特权，Ring 0 vs Ring 3）
            ↓
模式切换机制（中断/异常/系统调用 → 内核）
            ↓
中断系统（响应 + 处理，中断向量表，优先级，嵌套）
            ↓
进程抽象（PCB，三态/五态，创建/撤销/阻塞/唤醒原语）
            ↓
进程切换（保存/恢复上下文的具体步骤）
            ↓
线程（分离调度与资源，ULT/KLT/混合）
            ↓
调度算法（三层调度，FCFS/SPN/RR/Feedback/...）

每一层都依赖上一层的机制。理解了中断，才能理解进程切换是如何被触发的；理解了进程切换，才能理解调度算法为什么需要关注切换开销。