操作系统 SJTU 版(3)：进程管理

Last updated on November 20, 2025 am

这是《操作系统》SJTU-CS3601 课程的课程笔记系列。本文整理部分为“第 3 部分：进程管理”。

Lecture 9: 进程

进程的状态数据：
- 进程标识号（PID）
- 运行状态：处理器上下文（CPU Context）
- 地址空间
- 打开的文件
处理器上下文：包含恢复进程执行所需要的状态
- 具体包括：PC 寄存器值，栈寄存器值，通用寄存器值，状态寄存器值

进程的表示: PCB

进程：进程是计算机程序运行时的抽象
- 静态部分：程序运行需要的代码和数据
- 动态部分：程序运行期间的状态（程序计数器、堆、栈等）
进程控制块（PCB）：每个进程都对应一个元数据，称为“进程控制块” （PCB）
- 进程控制块存储在内核态
- 进程控制块中包括：独立的虚拟地址空间、独立的处理器上下文、内核栈
内核栈：
- 进程在内核中依然需要执行代码，有读写临时数据的需求
- 进程在用户态和内核态的数据应该相互隔离，增强安全性

进程的创建

创建和初始化的内容：
- 用户视角：代码、数据、堆栈
- 内核视角：PCB、虚拟地址空间、上下文、内核栈

一、PCB 相关初始化：PCB 及其包含的内容都需要创建及初始化
- 分配 PCB 本身的数据结构
- 初始化 PCB：虚拟内存
  - 创建及初始化 vmspace 数据结构
  - 分配一个物理页，作为顶级页表
- 内核栈：分配物理页，作为进程内核栈
二、可执行文件加载：可执行文件通常有固定的存储格式，以 ELF（Executable and Linkable Format）为例
- 从程序头部表可以获取需要的段所在位置
- 通常只有代码段和数据段需要被加载（loadable）
- 加载即从 ELF 文件中映射到虚拟地址空间的过程
三、准备运行环境：在返回用户态运行前，还需为进程准备运行所需的环境
- 分配用户栈：分配物理内存并映射到虚拟地址空间
- 准备程序运行时的环境：将参数和环境变量放到栈上
四、处理器上下文初始化：最后才初始化处理器上下文，因为其包含的内容直到前序操作完成才确定
- SP：用户栈分配后才确定地址
- PC（保存在 ELR_EL1）：加载 ELF 后才知道入口所在地址
- 大部分寄存器初始值可直接赋为 0

进程的退出与等待

进程退出的实现：
- 销毁 PCB 及其中保存的所有内容
- 告知内核，选择其他进程执行

进程等待（process_waitpid）的实现：
- 为每个进程引入进程标识符（pid），记录在 PCB 中
- 仍然调用 schedule，让其他进程执行，自己在while循环中等待
- 改进1：为进程添加退出状态支持
  - PCB：增加退出状态
  - process_exit：退出前设置退出状态
- 改进2：修改 process_waitpid
  - 如果进程已设置为退出，则记录其退出状态并回收
  - 将进程资源的回收操作从 exit 移到了 waitpid
- 改进3：限制进程等待的范围（安全性）
  - 目标：只有创建某进程的程序才能监控它
  - 实现：引入父（创建者）子（被创建者）进程概念
    - 进程之间的创建关系构建了一棵进程树，第一个进程（树根）通常由内核主动创建
    - PCB：维护子进程列表
    - waitpid：扫描子进程列表而不是所有进程
  - 若父进程不调用 waitpid，则在父进程退出后，由 init 进程代管并回收

进程的状态

进程睡眠：不断查看时间，如果未到规定时间则继续等待
进程的五种典型执行状态：
- 新生（new）：刚调用 process_create
- 就绪（ready）：随时准备执行（但暂时没有执行）
- 运行（running）：正在执行
- 僵尸（zombie）：退出但未回收
- 终止（terminated）：退出且被回收

调度：目的是选出下一个可以执行（就绪）的进程
- PCB 结构：增加执行状态
- 调度逻辑片段：只选择状态为 READY 的进程

案例分析：LINUX 进程创建

fork() 创建进程：为调用进程创建一个一模一样的新进程
- 调用进程为父进程，新进程为子进程
- 接口简单，无需任何参数
- fork 后的两个进程均为独立进程
  - 拥有不同的进程id
  - 可以并行执行，互不干扰（除非使用特定的接口）
  - 父进程和子进程会共享部分数据结构（内存、文件等）
  - fork 后父子进程顺序不确定，视调度策略而定
- 使用 fork 的返回值来分辨父/子进程：
  - 0: 子进程
  - 非 0（子进程id）：父进程
fork() 的实现：将父进程的 PCB 拷贝一份
- 包括 PCB、内核栈、处理器上下文等，实现比较简单
fork 的优点：
- 接口非常简洁，（过去）实现简单
- 将进程创建和执行（exec）解耦，提高了灵活度
fork 的缺点：
- 创建拷贝的复杂度与 PCB 复杂度相关（如今越来越复杂）
- 完全拷贝过于粗暴（不如 clone）
- 性能差、可扩展性差（不如 vfork 和 spawn）
- 不可组合性 (如 fork() + pthread())
fork 的替代接口：
- vfork：类似于 fork，但让父子进程共享同一地址空间
  - 优点：连映射都不需要拷贝，性能更好
  - 缺点：只能用在“fork + exec”的场景中；共享地址空间存在安全问题
- posix_spawn: 相当于 fork + exec
  - 优点：可扩展性、性能较好
  - 缺点：不如 fork 灵活
- clone: fork 的进阶版，可以选择性地不拷贝内存
  - 优点：高度可控，可依照需求调整
  - 缺点：接口比 fork 复杂，选择性拷贝容易出错

进程切换

进程切换的基本步骤：
1. 进程1进入内核态
2. 进程1处理器上下文保存
3. 进程上下文切换
4. 进程2处理器上下文恢复
5. 进程2返回用户态
处理器上下文与进程上下文：
- 处理器上下文：用于保存切换时的寄存器状态（硬件）
  - 在每个 PCB 中均有保存
- 进程上下文：表示目前操作系统正以哪个进程的身份运行（软件）
  - 通常使用一个指向 PCB 的全局指针表示
进程切换的节点：所有调用 schedule() 的地方
- 告知内核选择下一个执行的进程，也就涉及到了进程的切换
一、p0 进入内核态：由硬件完成部分寄存器保存
- PC 和 PSTATE 分别自动保存到 ELR_EL1 和 SPSR_EL1
二、p0 处理器上下文保存：将处理器中的寄存器值保存到处理器上下文对应的位置
三、由 p0 切换到 p1：
- 1. 虚拟地址空间切换：设置页表相关寄存器（TTBR0_EL1）
  - 使用 PCB 中保存的页表基地址赋值给 TTBR0_EL1
- 2. 内核栈切换：设置内核中的栈寄存器 SP_EL1
  - 使用 PCB 中保存的内核栈顶地址赋值给 SP_EL1
- 3. 进程上下文切换：设置 cur_proc 为之后要执行的进程（p1）
  - 表明之后操作系统将以 p1 的身份运行
四、p1 处理器上下文恢复：从处理器上下文中加载各寄存器的值，放入对应寄存器中
五、p1 回到用户态：由硬件自动恢复部分寄存器
- 将 ELR_EL1 和 SPSR_EL1 中的值自动保存到 PC 和 PSTATE 中

Lecture 10: 线程

为什么需要线程

进程的问题：
- 创建进程的开销较大：包括了数据、代码、堆、栈等
- 进程的隔离性过强：进程间交互可以通过进程间通信（IPC），但开销较大
- 进程内部无法支持并行
背景：单台设备计算资源逐渐丰富
- 多核处理器在 21 世纪初逐渐兴起
- 大型计算机包含大量多核处理器
简单方法：进程+调度
- 进程数量一般远超过 CPU 核数
- 调度器通过分时复用增加计算资源利用率
- 存在局限：单一进程无法利用多核资源
- 解决思路：用 fork 创建相似进程
Fork 方法存在的局限：
- 进程间隔离过强，共享数据困难
  - 各进程拥有独立的地址空间，共享需以页为粒度
  - 协调困难，需要复杂的通信机制（如管道）
- 进程管理开销较大
  - 创建：地址空间复制
  - 切换：页表切换
解决方案：使单一进程跨核执行
- 优势：无需用 fork 创建新进程
  - 降低进程管理开销
  - 同一地址空间数据共享/同步方便
- 需要的支持：
  - 处理器上下文：不同核执行状态不同，需要独立处理器上下文
线程：更加轻量级的运行时抽象
- 线程只包含运行时的状态
  - 静态部分由进程提供
  - 包括了执行所需的最小状态（主要是寄存器和栈）
- 一个进程可以包含多个线程
  - 多个线程共享同一地址空间（方便数据共享和交互）
  - 允许进程内并行

线程的使用：`pthread` 接口

常用库：POSIX threads（pthreads）
- 实现的功能与进程相关系统调用相似
- 创建：pthread_create，创建子线程并获得子线程 id（tid）
- 回收：pthread_join，等待 tid 对应线程退出并回收
- 退出：pthread_exit，只退出当前线程
- 一个线程执行系统调用，可能影响该进程的所有线程（如 exit 会使所有线程退出）
程序控制流分析：
- 主线程创建子线程后，两线程独立执行
- 建子线程后，两线程独立执行
  - 若主线程先执行，则 exit 被调用，子线程直接被终止
基于 join 的方法的问题：需要主线程手动调用回收资源
- 若主线程未调用则可能出现资源溢出
- 解决方案：加入 detach 操作，调用 detach 可使线程进入“分离”状态
  - 分离线程不能被其他线程杀死或回收，退出时资源自动回收
pthreads 使用小结：
- 常用接口：创建、合并、分离、退出
- 线程资源默认需要手动回收：
  - 主线程可使用合并（pthread_join）回收其他线程
  - 也可调用分离（pthread_detach）使其他线程自动回收
- 主线程退出默认会终结所有线程
  - 可改为调用退出（pthread_exit），只退出主线程

线程

多线程的进程：
- 一个进程可以包含多个线程
- 一个进程的多线程可以在不同处理器上同时执行
  - 调度的基本单元由进程变为了线程
  - 每个线程都有自己的执行状态
  - 切换的单位由进程变为了线程
多线程进程的地址空间：
- 每个线程拥有自己的栈
- 内核中也有为线程准备的内核栈
- 其它区域共享：数据、代码、堆

线程与进程的对比
- 相似之处：
  - 都可以与其他进程/线程并发执行（可能在不同核心上）
  - 都可以进行切换
    - 引入线程后，调度管理单位由进程变为线程
- 不同之处：
  - 同一进程的不同线程共享代码和部分数据
    - 不同进程不共享虚拟地址空间
  - 线程与进程相比开销较低
    - 进程控制（创建和回收）通常比线程更耗时

线程的实现

线程的表示：TCB（线程控制块）
- 将 PCB 中部分内容移入 TCB 中：
  - 每个线程 TCB 保存自己的处理器上下文、内核栈、退出/执行状态
  - 进程 PCB 仍维护共享的地址空间
  - PCB/TCB 间相互引用，便于管理

内核栈：除 TCB 外，每个线程也使用独立的内核栈
- 便于各线程在内核中独立执行
线程创建的实现：与进程创建相比步骤更少（如不需要加载可执行文件）

线程退出与合并的实现：与进程退出/等待的实现类似，线程退出时销毁内容更少（如不需要销毁 vmspace）

与进程管理接口的关系：以 fork 为例，一个多线程的程序调用 fork
- 实现方式1：拷贝父进程中所有的线程
- 实现方式2：只拷贝父进程中调用 fork 的线程
- POSIX 建议：尽量避免用 fork 拷贝多线程程序
用户态线程与内核态线程：根据线程是否受内核管理，可以将线程分为两类：
- 内核态线程：内核可见，受内核管理
  - 由内核创建，线程相关信息存放在内核中
- 用户态线程（纤程）：内核不可见，不受内核直接管理
  - 在应用态创建，线程相关信息主要存放在应用数据中
线程模型：表示了用户态线程与内核态线程之间的联系
- 多对一模型：多个用户态线程对应一个内核态线程
  - 优点：内核管理简单
  - 缺点：可扩展性差，无法适应多核机器的发展
  - 在主流操作系统中被弃用
  - 用于各种用户态线程库中
- 一对一模型：一个用户态线程对应一个内核态线程
  - 优点：解决了多对一模型中的可扩展性问题
  - 缺点：内核线程数量大，开销大
  - 主流操作系统都采用一对一模型
- 多对多模型：多个用户态线程对应多个内核态线程
  - 优点：解决了可扩展性问题（多对一）和线程过多问题（一对一）
  - 缺点：管理更为复杂
  - 在虚拟化中得到了广泛应用

一对一模型的 TCB：可以分为两部分
- 内核态：与 PCB 结构类似，线程切换中会使用
- 应用态：可以由线程库定义，可以认为是内核TCB的扩展

Lecture 11: 处理器调度

处理器调度

调度的背景：系统中的任务数远多于处理器数
- 任务（Task）：线程、单线程进程
处理器调度：
- 对象：CPU 执行的最小单元，可以是进程或线程，统一用“任务”描述
- 时机：执行时间用尽；等待 I/O 请求；睡眠；中断；等
- 决策：下一个执行的任务；执行该任务的 CPU；执行的时长
调度：协调请求对于资源的使用
- 适用的场景：I/O (磁盘)、打印机、内存、网络包、…
- 共用的调度指标：高资源利用率、多任务公平性、低调度开销
  - 降低周转时间：任务第一次进入系统到执行结束的时间
  - 降低响应时间：任务第一次进入系统到第一次给用户输出的时间
  - 实时性：在任务的截止时间内完成任务
  - 公平性：每个任务都应该有机会执行，不能饿死
  - 开销低：调度器是为了优化系统，而非制造性能 BUG
  - 可扩展：随着任务数量增加，仍能正常工作
- 调度的挑战：
  - 缺少信息（没有先知）：工作场景动态变化
  - 任务间的复杂交互
  - 调度目标多样性：不同的系统可能关注不一样的调度指标
  - 许多方面存在取舍
Linux 中的调度策略：为了满足不同需求提供多种调度策略
- 以 Linux 两种调度器为例，每种对应多个调度策略：Complete Fair Scheduler (CFS)、Real-Time Scheduler (RT)

经典调度 (Classical Scheduling)

1. 先来先得（First Come First Served）

规则：按作业或进程到达的先后顺序进行服务
优点：简单、直观
问题：平均周转、响应时间过长

2. 短任务优先（Shortest Job First）

规则：（服务时间）最短的作业或进程优先得到服务
优点：平均周转时间短
问题：
- 不公平，长任务饿死
- 平均响应时间过长
- 需要预知任务执行时间

抢占式调度 (Preemptive Scheduling)

规则：每次任务执行一定时间后会被切换到下一任务，而非执行至终止
实现：通过定时触发的时钟中断实现

3. Round Robin (时间片轮转)

规则：
- 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片
- 若进程未在一个时间片内执行完，则剥夺 CPU，将进程重新放到就绪队列队尾重新排队
优点：轮询，公平、平均响应时间短
问题：
- 牺牲周转时间
- 时间片过短会导致调度开销过大
- 时间片大小的影响：
- 时间片太大：退化为 FCFS 算法，会增大进程响应时间
- 时间片太小：导致进程切换过于频繁，实际用于进程执行的时间比例减少

优先级调度 (Priority Scheduling)

优先级：用于确保重要的任务被优先调度
- 操作系统中的任务是不同的
- 如果不加以区分，系统关键任务无法及时处理

4. 多级队列 (Multi-Level Queue, MLQ)

规则：
- 维护多个队列，每个对应静态设置好的优先级
- 高优先级的任务优先执行
- 同优先级内使用 Round Robin 调度（也可使用其他调度策略）
问题：
- 低资源利用率
- 需要预知任务是否为 I/O 密集型任务
高优先级任务：
- I/O 密集型任务：为了更高的资源利用率
- 用户主动设置的重要任务
- 时延要求极高（必须在短时间内完成）的任务
Linux Real-Time Scheduler：使用 Multi-level Queue 优先级调度
优先级的动态调整：
- 操作系统中的工作场景是动态变化的
- 静态设置的优先级可能导致：资源利用率低（优先级反转）、低优先级任务饥饿

5. 多级反馈队列 (Multi-Level Feedback Queue, MLFQ)

目标：一个无需先验知识的通用调度策略
- 周转时间低、响应时间低
- 调度开销低
思路：通过动态分析任务运行历史，总结任务特征
- 类似思想的体现：分支预测、缓存
- 需要注意：如果工作场景变化频繁，效果会很差
基本规则：
- 优先级高的任务会抢占优先级低的任务
- 每个任务会被分配时间片，优先级相同的两个任务使用时间片轮转
- 任务被创建时，假设该任务是短任务，为它分配最高优先级
- 一个任务时间片耗尽后，它的优先级会被降低一级
- 如果一个任务在时间片耗尽前放弃 CPU，那么它的优先级不变
  - 任务重新执行时，会被分配新的时间片
案例：
- 对于长任务：MLFQ 会逐渐降低它的优先级，并将它视为长任务
- 对于短任务：它会很快执行完，证明自己是个短任务
- 对于 I/O 密集型任务：它会在时间片执行完以前放弃 CPU，MLFQ 保持它的优先级不变即可
基本规则的问题1：
- 长任务饥饿：过多的短任务、I/O 密集型任务可能占用所有 CPU 时间
- 任务特征可能动态变化：如 CPU 密集型任务 -> 交互式任务
定时优先级提升：在某个时间段 S 后，将系统中所有任务优先级升为最高
- 避免长任务饿死：
  - 所有任务的优先级会定时地提升最高
  - 最高级队列采用 RR，长任务一定会被调度到
- 针对任务特征动态变化的场景：MLFQ 会定时地重新审视每个任务
基本规则的问题2：无法应对抢占 CPU 时间的攻击
- 恶意任务在时间片用完前发起 I/O 请求
- 避免 MLFQ 将该任务的优先级降低，并且每次重新执行时间片会被重置，几乎独占 CPU
更准确地记录执行时间：一个任务时间片耗尽后（无论它期间放弃了多次 CPU，它的时间片不会被重置），它的优先级会被降低一级
- MLFQ 会记录每个任务在当前优先级使用的时间片
- 当累计一个完整时间片被用完后，降低其优先级
MLFQ 的参数调试：
- 优先级队列的数量、不同队列的时间片长短、定时优先级提升的时间间隔
- 每个参数都体现了MLFQ的权衡：对于不同的工作场景，不同的参数会导致不一样的表现
MLFQ 各个队列时间片长短的选择：
- 高优先级队列时间片较短，针对短任务：提升响应时间
- 低优先级队列时间片较长，针对长任务：降低调度开销
MLFQ 小结：
- 通过观察任务的历史执行，动态确定任务优先级
  - 无需任务的先验知识
- 同时达到了周转时间和响应时间两方面的要求
  - 对于短任务，周转时间指标近似于 SJF
  - 对于交互式任务，响应时间指标近似于 RR
- 可以避免长任务的饿死

6. 高响应比优先（Highest Response Ratio Next）

规则：在每次调度时先计算各个作业或进程的响应比，选择响应比最高的作业或进程为其服务
响应比（Response Ratio）：一个任务的响应时间 $T_\text{Response }$ $T_{Response}$ 与其运行时间 $T_\text{Run }$ $T_{Run}$ 的比值
$\text { 优先级 }=\text { Response Ratio }=\frac{T_{\text {Response }}}{T_{\text {Run }}}=\frac{T_{\text {Waiting }}+T_{\text {Run }}}{T_{\text {Run }}}=\frac{T_{\text {Waiting }}}{T_{\text {Run }}}+1$
- 如果两个任务等待时间 $T_\text{Waiting }$ 相同，则运行时间越短越优先
- 如果两个任务运行时间相同，则等待时间越长，越优先
HRRN 策略通过结合 FCFS 策略和 SJF 策略，避免了 SJF 策略在公平性方面的问题

公平共享：
- 每个用户占用的资源是成比例的，而非被任务的数量决定
- 每个用户占用的资源是可以被计算的，设定“份额”以确定相对比例
方法：使用 ticket 表示任务的份额
- $T$ ：ticket 的总量

7. 彩票调度 (Lottery Scheduling)

规则：
- 每次调度时，生成随机数 $R \in [0,T)$
- 根据 $R$ ，找到对应的任务
彩票转让（Ticket Transfer）：
- 场景：在通信过程中，客户端需要等到服务端返回才能继续执行
- 客户端将自己所有的 ticket 转让给服务端
  - 确保服务端可以尽可能使用更多资源，迅速处理
- 同样适用于其他需要同步的场景
份额与优先级的异同：
- 份额影响任务对 CPU 的占用比例，不会有任务饿死
- 优先级影响任务对 CPU 的使用顺序，可能产生饿死
随机的利弊：
- 好处：简单
- 问题：不精确，伪随机非真随机；各个任务对 CPU 时间的占比会有误差

8. 步幅调度 (Stride Scheduling)

确定性版本的 Lottery Scheduling
Stride：步幅，任务一次执行增加的虚拟时间
$\text { stride }=\frac{\text { MaxStride }}{\text { ticket }}$
- $\text{ MaxStride }$ 是一个足够大的整数
Pass：累计执行的虚拟时间
规则：每次调度时，挑选 Pass 最小的任务

	Lottery Scheduling	Stride Scheduling
调度决策生成	随机	确定性计算
任务实际执行时间与预期的差距	大	小

Linux Complete Fair Scheduler：通过调整任务每次执行的时间，达成公平共享的方式
虚拟时间对调度行为的影响：
- 虚拟时间的意义：
  - 相对大小：对应了任务的优先级
  - 绝对值：对应了任务预期占用 CPU 的时间长度
- 问题：如果新创建/刚被唤醒的任务 vruntime 很小，会立即长时间占用 CPU
- 解决方案
  - 维护所有任务虚拟时间的最小值 min_vruntime
  - 当任务被创建、唤醒时，保证任务的 vruntime 不小于 min_vruntime

多核调度策略 (Multicore Scheduling Policy)

需要考虑的额外因素：一个进程的不同线程可以在不同 CPU 上同时运行
全局运行队列：
- 规则：所有 CPU 共享同一个全局运行队列
- 问题：
  - 所有 CPU 竞争全局调度器
  - 同一个线程可能在不同 CPU 上切换
    - 切换开销大：Cache、TLB、…
    - 缓存局部性差
本地运行队列：每个 CPU 核心维护本地运行队列
- 现被应用于 Linux、ChCore 等操作系统中
- 问题：负载不均衡
负载均衡：尽可能让每个 CPU 都同等忙碌
- 需要追踪 CPU 的负载情况
- 将任务从负载高的 CPU 迁移到负载低的 CPU
亲和性：尽量让一个进程调度到同一个 CPU 上运行，以发挥 CPU 中 Cache 的作用
- 通过操作系统暴露的任务亲和性接口，可以指定任务能够使用的 CPU 核心

Lecture 12: 进程间通信

IPC (Inter-Process Communication)：进程与进程间的通信方式
- 必要性：不同进程拥有不同的内存地址空间，进程与进程之间无法直接进行通信和交互
常见 IPC 的类型

简单 IPC 的设计与实现

简单 IPC 的消息接口：
- 发送消息：Send(message)
- 接收消息：Recv(message)
- 远程方法调用：RPC(req_message, resp_message)
- 远程方法调用的回复：Reply(resp_message)
简单 IPC 的两个阶段：
- 阶段1：准备阶段
  - 建立通信连接，即进程间的信道
    - 假设内核已经为两个进程映射了一段共享内存
- 阶段2：通信阶段
  - 数据传递
    - “消息”抽象：通常包含头部和数据内容（不能传指针）
  - 通信机制
    - 两个消息保存在共享内存中：发送者消息、接收者消息
    - 发送者和接收者通过轮询消息的状态作为通知机制
简单 IPC 数据传递的两种方法：
- 方法1：基于共享内存的数据传递
  - 操作系统在通信过程中不干预数据传输
  - 操作系统仅负责准备阶段的映射
  - 优势：
    - 无需切换到内核态即可完成 IPC（多核场景下）
    - 完全由用户态控制，定制能力更强
    - 可实现零内存拷贝（无需内核介入）
- 方法2：基于操作系统辅助的数据传递
  - 操作系统提供接口（系统调用）：Send、Recv
  - 通过内核态内存来传递数据，无需在用户态建立共享内存
  - 优势：
    - 抽象更简单，用户态直接调用接口，使用更方便
    - 安全性保证更强，发送者在消息被接收时通常无法修改消息
    - 多方（多进程）通信时更灵活、更安全
简单 IPC 的通知机制：
- 方法1：基于轮询（消息头部的状态信息）
  - 缺点：大量 CPU 计算资源的浪费
- 方法2：基于控制流转移
  - 由内核控制进程的运行状态
  - 优点：进程只有在条件满足的情况下才运行，避免 CPU 浪费
IPC 控制流：同步和异步
- 同步 IPC：IPC 操作会阻塞进程直到操作完成
  - 线性的控制流
  - 调用者继续运行时，返回结果已经 ready
- 异步 IPC：进程发起 IPC 操作后即可返回而不需要等待其完成
  - 通过轮询或回调函数（需内核支持）来获取返回结果
IPC 的超时机制：
- 超时可能的原因：
  - 被调用者是恶意的：故意不返回
  - 被调用者不是恶意的：运行时间过长、调度时间过长、请求丢失等
- 超时机制：
  - 应用可自行设置超时的阈值，但如何选择合适的阈值却很难
  - 特殊的超时机制：阻塞、立即返回（要求被调用者处于可立即响应的状态）
IPC 的权限检查：
- 宏内核：通常基于权限检查的机制实现
  - 如 Linux 中与文件的权限检查结合在一起
- 微内核：通常基于 Capability 安全检查机制实现
  - Capability 保存在内核中，与进程绑定
  - 进程发起 IPC 时，内核检查其是否拥有对应的 Capability

共享内存 (内存接口的 IPC)

基础实现：

共享区域：共享区域容量、共享状态

#define BUFFER_SIZE 10
typedef struct {
  . . .
} item;
item buffer[BUFFER_SIZE];
volatile int buffer_write_cnt = 0;
volatile int buffer_read_cnt = 0;
volatile int empty_slot = BUFFER_SIZE;
volatile int filled_slot = 0;

发送者(生产者)：当没有新消息时，接收者盲目等待

while (new_package) {
  /* Produce an item/msg */
  while (empty_slot == 0)
    ;   /* do nothing -- no free buffers */
  empty_slot --;
  buffer[buffer_write_cnt] = msg;
  buffer_write_cnt = (buffer_write_cnt + 1) % BUFFER_SIZE;
  filled_slot ++; 
  …
}

接收者：当没有新消息时，接收者盲目等待

while (wait_package) {
  while (filled_slot == 0)
    ; // do nothing -- nothing to consume
  filled_slot--; // remove an item from the buffer
  item = buffer[buffer_read_cnt];
  buffer_read_cnt = (buffer_read_cnt + 1) % BUFFER SIZE;
  empty_slot++;
  return item;
}

共享内存的问题：
- 缺少通知机制：
  - 若轮询检查，则导致 CPU 资源浪费
  - 若周期性检查，则可能导致较长的等待时延
  - 根本原因：共享内存的抽象过于底层；缺少 OS 更多支持
- TOCTTOU （Time-of-check to Time-of-use）问题：
  - 当接收者直接用共享内存上的数据时，可能存在被发送者恶意篡改的情况（发生在接收者检查完数据之后，使用数据之前）
  - 这可能导致 buffer overflow 等问题

消息传递（Message Passing）

消息队列：消息队列是间接消息传递方式，通过共享一个队列来建立连接
- 以链表的方式组织消息
- 任何有权限的进程都可以访问队列，写入或者读取
- 支持异步通信 (非阻塞)
消息的格式：类型 + 数据
消息队列的组织：
- 基本遵循 FIFO 先进先出原则
- 消息队列的写入：增加在队列尾部
- 消息队列的读取：默认从队首获取消息
允许按照类型查询: Recv(A, type, message)
- 如 type 为正数，则返回第一个类型为 type 的消息

轻量级远程方法调用 (LRPC)

LRPC 解决的问题：
- 控制流转换：Client 进程快速通知 Server 进程
- 数据传输：将栈和寄存器参数传递给 Server 进程
控制流转换：调度导致不确定时延
- 控制流转换需要下陷到内核
- 内核系统为了保证公平等，会在内核中根据情况进行调度
  - Client 和 Server 之间可能会执行多个不相关进程
迁移线程：将 Client 运行在 Server 的上下文
- 使用 Server 的代码和数据，使用 Server 的权限 (如访问某些系统资源)
- 只切换地址空间、权限表等状态，不做调度和线程切换
数据传输：数据拷贝的性能损失
- 大部分 Unix 类系统，经过内核的传输有(至少)两次拷贝 (Client -> 内核 -> Server)
- 数据拷贝：慢（拷贝本身的性能就不快）；不可扩展（数据量增大，时延增大）
共享参数栈和寄存器：
- 参数栈 (A-stack)：
  - 系统内核为每一对 LRPC 连接预先分配好一个 A-stack
  - A-stack 被同时映射在 Client 进程和 Server 进程地址空间
  - Client 进程只需要将参数准备到 A-stack 即可，不需要内核额外拷贝
- 执行栈 (E-stack)
- 共享寄存器：
  - 普通的上下文切换：保存当前寄存器状态 -> 恢复切换到的进程寄存器状态
  - LRPC 迁移进程：直接使用当前的通用寄存器，类似函数调用中用寄存器传递参数
通信连接建立：
- Server 进程通过内核注册一个服务描述符
  - 对应 Server 进程内部的一个处理函数
- 内核为服务描述符预先分配好参数栈
- 内核为服务描述符分配好调用记录，用于从 Server 进程处返回（类似栈）
- 内核将参数栈交给 Client 进程，作为一个绑定成功的标志
  - 在通信过程中，通过检查 A-stack 来判断 Client 是否正确发起通信
一次调用过程：
1. 内核验证绑定对象的正确性，并找到正确的服务描述符
2. 内核验证参数栈和连接记录
3. 检查是否有并发调用 (可能导致 A-stack 等异常)
4. 将 Client 的返回地址和栈指针放到连接记录中
5. 将连接记录放到线程控制结构体中的栈上 (支持嵌套 LRPC 调用)
6. 找到 Server 进程的 E-stack (执行代码所使用的栈)
7. 将当前线程的栈指针设置为 Server 进程的运行栈地址
8. 将地址空间切换到 Server 进程中
9. 执行 Server 地址空间中的处理函数

Binder IPC

Binder IPC：兼具IPC数据传输的高性能与高安全
- 框架层 Binder 服务框架：发现服务，接口封装
- 内核层 Binder 驱动：提供内核层 IPC 能力
Binder IPC 数据传输：通过内存映射减少 IPC数据拷贝
- 发送端一次数据拷贝，接受端零次数据拷贝
数据序列化：
- 问题：复杂数据结构无法直接跨进程传输
  - 数据结构嵌套
  - 指针、文件描述符等接收端无法访问
- 方案：序列化与反序列化
  - 序列化：将数据结构展开为一个字节串
  - 反序列化：将字节串转换为原有数据结构
Binder IPC 数据序列化：内核辅助完成特殊对象传输
- 文件描述符、句柄等
- 定位特殊对象位置 + 帮助接收端进程重构特殊对象
服务端线程数量：
- IPC 请求需要服务端线程的处理：一个 IPC Server 可能处理大量 Client 请求
- 少量服务线程 -> 无法应对高负载任务
- 大量服务线程 -> 低负载时浪费资源
Binder IPC 线程池模型：
- 服务端设置最大线程数量
- 内核动态创建服务线程：默认从服务线程池挑选处理线程，服务线程不足自动创建

Lecture 13: 同步原语

并发带来的同步问题：竞争条件

竞争条件：
- 当 2 个或以上线程同时对共享的数据进行操作，其中至少有一个写操作
- 该共享数据最后的结果依赖于这些线程特定的执行顺序

生产者消费者与多生产者消费者

临界区（Critical Section）：任意时刻，有且只有一个线程可以进入临界区执行
实现临界区抽象的三个要求：
- 互斥访问：在同一时刻，有且仅有一个线程可以进入临界区
- 有限等待：当一个线程申请进入临界区之后，必须在有限的时间内获得许可进入临界区而不能无限等待
- 空闲让进：当没有线程在临界区中时，必须在申请进入临界区的线程中选择一个进入临界区，保证执行临界区的进展
同步原语（Synchronization Primitives）：一个平台（如操作系统）提供的用于帮助开发者实现线程之间同步的软件工具
- 在有限的共享资源上正确的协同工作

互斥锁

互斥锁（Mutual Exclusive Lock）接口：保证同时只有一个线程能够拿到锁
- Lock(lock)：尝试拿到锁“lock”
  - 若当前没有其他线程拿着 lock，则拿到 lock，并继续往下执行
  - 若 lock 被其他线程拿着，则不断循环等待放锁（busy loop）
- Unlock(lock)：释放锁

条件变量

条件变量：利用睡眠/唤醒机制，避免无意义的等待
- 让操作系统的调度器调度其他进程/线程执行
等待的接口：void cond_wait(struct cond *cond, struct lock *mutex);
1. 放入条件变量的等待队列
2. 阻塞自己同时释放锁：即调度器可以调度到其他线程
3. 被唤醒后重新获取锁
唤醒的接口：void cond_signal(struct cond *cond);
1. 检查等待队列
2. 如果有等待者则移出等待队列并唤醒

信号量（Semaphore）

信号量（PV 原语）：协调（阻塞/放行）多个线程共享有限数量的资源
- 语义上：信号量的值 cnt 记录了当前可用资源的数量
- 提供了两个原语 P 和 V 用于等待/消耗资源
- P 操作：消耗资源
- V 操作：增加资源

void producer(void) {
	new_msg = produce_new(); 	
  sem_wait(&empty_slot_sem);
	buffer_add(new_msg); 	
  sem_signal(&filled_slot_sem);
}

void consumer(void) {
	sem_wait(&filled_slot_sem);
	cur_msg = buffer_remove(); 	
  sem_signal(&empty_slot_sem); 	
  handle_msg(cur_msg);
}

二元信号量：初始化的资源数量为 1
- 其计数器（counter）只有可能为 0、1 两个值
- 同一时刻只有一个线程能够拿到资源
计数信号量：初始化的资源数量大于 1
- 同一时刻可能有多个线程能够拿到资源

读写锁

互斥锁：所有的线程均互斥，同一时刻只能有一个线程进入临界区
- 对于部分只读取共享数据的线程过于严厉
读写锁：区分读者与写者，允许读者之间并行，读者与写者之间互斥

参考资料

本文参考上海交通大学并行与分布式系统研究所（IPADS）操作系统课程 CS3601 华志超老师的 PPT 课件整理。

操作系统

#操作系统 #课程笔记 #知识点整理

操作系统 SJTU 版(3)：进程管理

https://cny123222.github.io/2025/10/24/操作系统-SJTU-版-3-：进程管理/

Author

Nuoyan Chen

Posted on

October 24, 2025

Licensed under

Paper Reading #7: DIMES Previous

操作系统 SJTU 版(2)：内存管理 Next

操作系统 SJTU 版(3)：进程管理

Lecture 9: 进程

进程的表示: PCB

进程的创建

进程的退出与等待

进程的状态

案例分析：LINUX 进程创建

进程切换

Lecture 10: 线程

为什么需要线程

线程的使用：pthread 接口

线程

线程的实现

Lecture 11: 处理器调度

处理器调度

经典调度 (Classical Scheduling)

1. 先来先得（First Come First Served）

2. 短任务优先（Shortest Job First）

抢占式调度 (Preemptive Scheduling)

3. Round Robin (时间片轮转)

优先级调度 (Priority Scheduling)

4. 多级队列 (Multi-Level Queue, MLQ)

5. 多级反馈队列 (Multi-Level Feedback Queue, MLFQ)

6. 高响应比优先（Highest Response Ratio Next）

公平共享调度 (Fair-Share Scheduling)

7. 彩票调度 (Lottery Scheduling)

8. 步幅调度 (Stride Scheduling)

多核调度策略 (Multicore Scheduling Policy)

Lecture 12: 进程间通信

简单 IPC 的设计与实现

共享内存 (内存接口的 IPC)

消息传递（Message Passing）

轻量级远程方法调用 (LRPC)

Binder IPC

Lecture 13: 同步原语

并发带来的同步问题：竞争条件

生产者消费者与多生产者消费者

互斥锁

条件变量

信号量（Semaphore）

读写锁

参考资料

线程的使用：`pthread` 接口