Notes@Tsukino

进程管理

2分钟阅读

操作系统

操作系统中最核心的概念是进程

进程管理是操作系统的核心模块，负责管理程序的动态执行过程。涵盖进程的基本概念与生命周期、进程控制原语、CPU 调度算法、并发执行中的同步与互斥问题（信号量、经典同步问题）、进程间通信机制以及死锁的处理策略（预防、避免、检测与解除）。

进程核心概念

进程概念

为什么要引入进程

  • 多道程序设计系统中，CPU 在各程序之间高速切换
  • 需要一种抽象实体来描述正在运行的程序，以便 OS 进行管理和调度
  • 顺序执行：I1 → C1 → P1 → I2 → C2 → P2 → …（无并发，资源利用率低）
  • 引入进程后，多道程序可并发执行，提高 CPU 和 I/O 利用率

进程的定义

  • 对正在运行程序的一个抽象
  • 进程是系统进行资源分配和调度的基本单位
  • 进程是程序在数据集合上的一次运行活动

PCB（进程控制块）

  • 进程在操作系统中的表示，OS 通过 PCB 管理进程
  • 包含以下信息：
    • 进程标识符（PID）：唯一标识一个进程
    • 状态：运行态、就绪态、阻塞态等
    • 优先级：调度依据
    • 寄存器上下文：程序计数器 PC、栈指针 SP、通用寄存器等
    • 内存指针：代码段、数据段、栈段指针
    • 资源清单：打开的文件、I/O 设备等
    • 父进程/子进程指针：维护进程家族关系
    • 其他：记账信息、消息队列指针等

进程存储器映像

  • 用户空间：
    • 代码段（Text）：程序代码，只读
    • 数据段（Data）：全局变量、静态变量
    • 栈段（Stack）：函数调用参数、返回地址、局部变量
  • 系统空间：
    • PCB 存储在内核空间，由 OS 维护

进程状态（5 状态模型）

  • 创建态（New）：进程正在被创建，OS 分配 PCB
  • 就绪态（Ready）：具备运行条件，等待 CPU 调度
  • 运行态（Running）：正在使用 CPU 执行指令
  • 阻塞态（Blocked/Waiting）：进程等待某个事件发生（如 I/O 完成）
  • 终止态（Terminated）：进程执行完毕，OS 回收资源

状态转换条件

转换条件
创建 → 就绪PCB 初始化完成，进入就绪队列
就绪 → 运行调度程序选中该进程
运行 → 就绪时间片用完 / 被高优先级进程抢占
运行 → 阻塞等待某事件（如 I/O、信号量）
阻塞 → 就绪所等待的事件发生
运行 → 终止进程执行完毕或被撤销

进程组织方式

  • 链接方式：按进程状态（就绪、阻塞等）将 PCB 链接成不同队列
  • 索引方式：建立就绪索引表、阻塞索引表，通过索引查找 PCB
  • 树形结构：UNIX/Linux 用树形结构组织进程，pstree 可见父子关系

当前进程指针

  • 系统中有一个指针指向当前正在运行的进程的 PCB
  • 调度切换时，该指针指向新选中的进程 PCB
指向原始笔记的链接

进程控制

进程控制

定义

  • 使用原语来创建、撤消进程，以及完成进程各状态之间的转换
  • 由操作系统内核实现

原语（Primitive）

  • 由若干条机器指令构成的可完成特定功能的程序段
  • 原子操作：要么全部完成，要么全都不做
  • 通过屏蔽各种中断保证原子性

分类

  • 进程控制原语
  • 进程通信原语
  • 进程管理原语

基本原语

创建原语

  • 创建新进程，分配 PCB
  • 步骤：
    1. 分配新的 PCB，获取唯一 PID
    2. 为进程分配内存空间，加载程序映像（代码 + 数据 + 栈）
    3. 初始化 PCB：填写 PID、状态（就绪）、优先级、寄存器上下文等
    4. 将 PCB 插入就绪队列

撤销原语

  • 终止进程，回收其所占用的所有资源（内存、文件、设备等）
  • 回收 PCB

阻塞原语

  • 进程从运行态 → 阻塞态
  • 保护当前 CPU 上下文到 PCB，将 PCB 移入等待队列

唤醒原语

  • 进程从阻塞态 → 就绪态
  • 将 PCB 从等待队列移到就绪队列

挂起原语

  • 将进程从内存移到外存（挂起态）
  • 用于缓解内存不足

激活原语

  • 将进程从外存调入内存（从挂起态恢复）

fork() 系统调用

  • UNIX/Linux 中创建进程的核心系统调用
  • 返回值语义：fork() 在父进程中返回子进程 PID，在子进程中返回 0，失败返回 -1
  • 父子进程并发执行：fork() 后父进程和子进程是独立的进程，调度顺序不确定
  • 写时复制（Copy-on-Write）：父子进程共享同一物理内存，仅当写入时复制新页

进程树结构

  • UNIX/Linux 中进程形成树形关系：init（PID=1）是所有进程的祖先
  • fork() 创建子进程后，可通过 exec() 系列函数替换进程映像

模式切换 vs 进程切换

  • 模式切换（Mode Switch）：在同一进程中，用户态 ↔ 内核态（如系统调用、中断），不改变当前进程
  • 进程切换（Process Switch/Context Switch）：从一个进程切换到另一个，需保存/恢复 PCB 上下文，开销更大
指向原始笔记的链接

进程调度

进程调度

定义

  • 按某种策略从就绪队列中选择一个进程，分配 CPU 给它运行
  • 调度的核心目标：公平、高效、低延迟、高吞吐

调度层次

  • 高级调度（作业调度）：从外存中选择作业调入内存，创建进程
  • 中级调度（交换调度）：进程在内/外存之间换入换出，缓解内存压力
  • 低级调度（进程调度）：从就绪队列选进程分配 CPU — 频率最高

调度时机

  • 进程从运行态 → 阻塞态（等待 I/O 或事件）
  • 进程从运行态 → 就绪态（时间片用完或被抢占）
  • 进程从阻塞态 → 就绪态（事件发生，可能抢占）
  • 进程终止

调度方式

  • 非抢占式：进程运行完毕或主动阻塞才切换，简单但响应慢
  • 抢占式：时间片用完或高优先级进程就绪时可强制切换，响应快但开销大

重点 调度算法

算法描述特点
先来先服务（FCFS）按到达顺序排队，类似银行排队叫号简单，平均等待时间长，长作业有利
短作业优先（SJF/SPF）选择执行时间最短的进程，非抢占/抢占两种平均等待时间最短，长作业可能饥饿
优先级调度分静态优先级（创建时确定）和动态优先级（随运行调整）通用，优先级低的可能饥饿
时间片轮转（RR）按时间片轮流分配 CPU，用完即切分时系统，响应时间均匀，时间片大小关键
多级反馈队列多个队列，优先级+时间片结合通用（重点），兼顾响应与吞吐

先来先服务（FCFS）

  • 就绪队列按到达先后排序，非抢占
  • 平均等待时间长，短作业排在长作业后时非常不利
  • 类比：银行柜台排队，不可插队

短作业优先（SJF/SPF）

  • 非抢占：进程到达时，选择预计运行时间最短的投入运行
  • 抢占（SRTF）：新进程到达时，如果其剩余时间比当前进程短，则抢占
  • 平均等待时间理论上最优（最优调度策略），但长作业可能无限期饥饿
  • 难点：需预知进程运行时间

优先级调度

  • 静态优先级：进程创建时确定，运行期间不变
  • 动态优先级：随进程运行时间调整（如老化机制），防止饥饿

时间片轮转（RR）

  • 每个进程分配一个固定时间片（Time Quantum），用完则切换
  • 时间片过大 → 退化为 FCFS；时间片过小 → 上下文切换开销过大
  • 典型值：10–100ms

多级反馈队列调度

  • 设置多个就绪队列，优先级从高到低，时间片从短到长
  • 新进程进入最高优先级队列
  • 用完时间片未完成则降入下一级队列
  • 优先级高的队列可抢占优先级低的队列中的进程
  • 兼顾短作业（快速响应）和长作业（不饥饿）

Linux CFS（Completely Fair Scheduler）

  • 使用红黑树（Red-Black Tree）组织就绪进程
  • vruntime：进程的虚拟运行时间，CFS 选择 vruntime 最小的进程运行
  • vruntime 受进程优先级（nice 值）影响：优先级高 → vruntime 增长慢
  • 保证每个进程获得公平的 CPU 份额

Linux 实时调度

  • SCHED_FIFO：先进先出实时调度，直到进程主动阻塞或结束
  • SCHED_RR：时间片轮转实时调度，同优先级间轮转
  • SCHED_DEADLINE：基于最早截止期限优先（EDF），保证实时任务按时完成
指向原始笔记的链接

进程并发

进程并发

并发需求

  • 两个层次的并发：
    1. 应用层并发：应用程序利用 OS 支持的进程/线程，安排可并行事务并发执行
    2. 操作系统内核层并发：OS 核心程序本身也要尽可能地并发（如设备驱动、文件系统并发访问）

并发编程方法

  • 自动并行检测：编译器自动识别可并行执行的部分
  • 并发编程语言：语言本身提供并行语法（如并发语句 cobegin/coend）
  • 传统语言 + OS API：使用 OS 提供的系统调用（如 fork、pthread_create）实现并发

并发表示法 — parbegin/parend

S1;
parbegin
  S2;
  S3;
parend
S4;
  • 表示 S2 和 S3 可以并发执行，S4 必须在两者都完成后才开始

并发执行特征

  • 间断性：执行—暂停—执行，运行过程不可预测
  • 失去封闭性：执行结果受并发环境和相对速度的影响
  • 不可再现性：多次执行可能得到不同结果（Race Condition）

并发产生的问题

  • 同步（Synchronization）— 直接约束：多个进程按一定顺序执行，存在协作关系
    • 例如：A 产生数据，B 消费数据，B 必须等待 A 完成
  • 互斥（Mutual Exclusion）— 间接约束：多个进程不能同时访问临界资源
    • 例如：两个进程不能同时写同一个打印机

任务图示例（S1 / S2 / S3）

S1 → 并发 S2、S3 → S4
  • S1 先执行
  • S2 和 S3 可并发执行
  • S4 必须在 S2 和 S3 都完成后执行
  • 同步约束：S1 与 S2/S3 之间为同步关系；S2/S3 无约束，可任意并发
指向原始笔记的链接

同步与互斥

进程同步互斥

临界区

  • 每个进程中访问临界资源的那段代码

重点 进入临界区的四个准则

  1. 互斥使用（Mutual Exclusion）：不能同时有两个进程在临界区内执行
  2. 让权等待：等待进入临界区的进程，应释放处理机后阻塞等待
  3. 有空让进：在临界区外运行的进程不可阻止其他进程进入临界区
  4. 有限等待：不应使要进入临界区的进程无限期等待在临界区之外

软件实现方法

  • Peterson 算法等

硬件实现方法

关中断

  • 进入临界区前关中断，退出后开中断
  • 缺点：不适用于多处理器系统（关中断只对当前 CPU 有效），且用户进程关中断风险高

Test-and-Set（TS）指令

  • 硬件原子指令：读旧值 → 写新值（设为 1），两个操作不可分割
  • 伪代码描述：
boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;   // 锁住
    return old;     // 返回原值
}
  • 用于实现 自旋锁（Spin Lock）：
// 自旋锁的典型实现
while (TestAndSet(&lock) == 1)  // 若锁被占用，忙等循环
    ;
// 进入临界区
lock = 0;  // 释放锁
  • 重点 忙等（Busy Waiting）：进程在等待锁时不断循环测试，CPU 空转，浪费处理机时间
    • 违背 ” 让权等待 ” 准则
    • 优点：无需上下文切换，在临界区执行时间很短时效率高

Swap 指令

  • 交换两个变量的值，同样是硬件原子操作
void Swap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

// 用 Swap 实现自旋锁
bool key = true;
while (key == true)
    Swap(&lock, &key);
// 进入临界区
lock = false;

信号量机制

指向原始笔记的链接

信号量

信号量

定义

  • 由 Dijkstra 提出的经典同步机制
  • 信号量 是一个整型变量，代表可用资源的数量
  • 除了初始化，信号量只能通过 P 操作 和 V 操作 修改（原子操作）

重点 P/V 操作

P 操作（wait / 申请资源）

P(S):
  S.value = S.value - 1
  if S.value < 0:
    进程进入等待队列（阻塞）

V 操作（signal / 释放资源）

V(S):
  S.value = S.value + 1
  if S.value <= 0:
    从等待队列唤醒一个进程

分类

按资源计数

  • 二进制信号量（Binary Semaphore）： 取值 0 或 1，相当于互斥锁
  • 计数信号量（Counting Semaphore）：，表示可用资源数量

按使用目的

  • 互斥信号量（公共信号量）：用于保护临界区，初值 = 1
  • 同步信号量（私有信号量）：用于进程间同步，初值 = 0

实现机制

  • 基于阻塞队列（非忙等）：当 P 操作无法获取资源时，进程主动阻塞并让出 CPU
  • 不使用忙等（while 循环），避免 CPU 浪费
  • 每个信号量关联一个等待队列（blocked queue）

临界区（Critical Section）四个原则

  1. 忙则等待（互斥）：临界区有进程时，其他进程不能进入
  2. 空闲则入（前进）：无进程在临界区时，应允许申请者进入
  3. 有限等待：等待进入临界区的进程不会无限等待
  4. 让权等待：不能进入临界区时应主动阻塞，而非忙等

P/V 使用模式

  • 互斥：P、V 成对出现在同一进程中，保护临界区 
    P(mutex);
  临界区
V(mutex);
  • 同步：P、V 出现在不同进程中 
    进程 A: V(sync);   进程 B: P(sync);
  • 参见 经典同步问题
指向原始笔记的链接

经典同步问题

经典同步问题

进程同步互斥

重点 生产者 - 消费者问题

问题描述

  • 生产者：生产数据放入缓冲区
  • 消费者：从缓冲区取数据消费
  • 同步关系：缓冲区满则生产者等待，缓冲区空则消费者等待
  • 互斥关系：对缓冲区的互斥访问

PV 解决方案（3 个信号量）

semaphore mutex = 1;   // 保护缓冲区互斥访问
semaphore empty = N;   // 空缓冲区数量
semaphore full  = 0;   // 满缓冲区数量
 
// 生产者
while (true) {
  produce(data);
  P(empty);       // 先申请空缓冲区（资源信号量）
  P(mutex);       // 再申请互斥访问
    put(data);
  V(mutex);
  V(full);        // 满缓冲区 +1
}
 
// 消费者
while (true) {
  P(full);
  P(mutex);
    get(data);
  V(mutex);
  V(empty);
  consume(data);
}

P 操作顺序

  • 必须先 P(资源信号量)，再 P(互斥信号量)
  • 如果顺序颠倒（先 P(mutex) 再 P(empty)），满缓冲区时生产者持有 mutex 阻塞，消费者无法进入，形成死锁

重点 读者 - 写者问题

读者优先

  • 多个读者可同时读
  • 写者必须独占访问，且只能等所有读者完成
  • 使用 readcount 统计读者数，mutex 保护 readcount，wrt 实现写者互斥
semaphore mutex = 1;
semaphore wrt = 1;
int readcount = 0;
 
// 读者
P(mutex);
  readcount++;
  if (readcount == 1) P(wrt);  // 第一个读者锁住写者
V(mutex);
  read;
P(mutex);
  readcount--;
  if (readcount == 0) V(wrt);  // 最后一个读者释放写者
V(mutex);
 
// 写者
P(wrt);
  write;
V(wrt);

写者优先

  • 当有写者等待时，新读者不能开始读
  • 需额外的信号量 read 来阻塞新读者

重点 哲学家就餐问题

问题描述

  • 5 个哲学家围坐，5 支筷子交替放置
  • 每个哲学家需要两支筷子才能进餐
  • 死锁风险：所有哲学家同时拿起左边筷子，导致循环等待

解决方案

  1. 限制并发人数：最多只允许 4 个哲学家同时就餐（信号量 limit = 4）
  2. 奇偶拿筷：奇数号先取左边筷子，偶数号先取右边筷子，打破循环等待
  3. AND 信号量：同时申请两支筷子（一次 P 操作获取全部所需资源）

重点 管程（Monitor）

  • 将共享数据和对该数据的操作封装在一起
  • 类似 OOP 中的类：共享变量 + 方法 + 条件变量
  • 同一时间只有一个进程能进入管程，自动保证互斥
  • 使用条件变量（Condition Variable）实现同步

信号量解决思路总结

  • 互斥信号量 保护临界区
  • 资源信号量 表示缓冲区状态
  • 同步信号量协调执行顺序
指向原始笔记的链接

进程通信

进程通信IPC

定义

  • 在进程间传输数据（交换信息）
  • 进程间通信（Inter-Process Communication，IPC）

分类

低级通信

  • 只能传递状态和整数值（控制信息）
  • P、V 操作
  • 缺点：信息量小，效率低，编程复杂

重点 高级通信（三种方式）

方式描述特点
共享内存模式多个进程共享一段内存区域最快，需信号量同步互斥
消息传递模式进程间通过消息发送/接收通信无共享内存，适用于分布式系统
共享文件模式（管道）通过文件作为中介传递数据简单，但效率较低

共享内存（Shared Memory）

  • 最快速的 IPC 方式：进程直接读写同一块物理内存
  • 无需数据拷贝（对比消息传递需要内核缓冲拷贝）
  • 需配合 信号量 实现同步互斥
  • 适用场景：大量数据传输

消息传递（Message Passing）

直接通信

  • 指名道姓：发送方明确指定接收方 PID，接收方明确指定发送方
  • 系统调用：send(dest, msg) / recv(src, msg)

间接通信

  • 通过消息队列/信箱（Mailbox）作为中介
  • 多个进程可共享同一个信箱
  • 系统调用：send(M, msg) / recv(M, msg)

管道（Pipe）

  • 单向数据流：数据从一端写入，从另一端读出
  • 无名管道：只用于父子进程或有亲缘关系的进程之间
  • 命名管道（FIFO）：通过文件系统中的特殊文件，可用于任意进程间通信
  • 管道本质是内核中的一个共享缓冲区

三种方式对比

方式速度同步需求适用场景
共享内存最快需同步大量数据、高性能
消息传递中等自动同步分布式、小数据
管道较慢自动同步简单通信、父子进程
指向原始笔记的链接

死锁

死锁

定义

  • 两个或多个进程相互等待对方释放资源，导致所有相关进程都无法继续执行
  • 若无外力作用，死锁进程将永远处于阻塞状态

死锁示例

  • 交通死锁：四个方向的车互不相让，形成环路
  • 哲学家就餐问题：5 个哲学家同时拿起左边筷子，循环等待右边筷子

重点 死锁产生的四个必要条件

  1. 互斥（Mutual Exclusion）：资源一次只能被一个进程使用
  2. 请求与保持（Hold and Wait）：进程已持有一个资源，又请求新的资源
  3. 不可剥夺（No Preemption）：资源在未使用完前不能被强行夺走
  4. 循环等待（Circular Wait）：存在进程 - 资源的循环等待链

重点 死锁处理策略对比

策略方法特点
死锁预防破坏四个必要条件之一实现简单，资源利用率低
死锁避免银行家算法，动态检查安全性资源利用率较高，需预知最大需求
死锁检测与恢复检测到死锁后强行恢复适用于容易回滚的系统

死锁预防（破坏必要条件）

  • 破坏互斥：非共享设备不能破坏（如打印机不能共享）
  • 破坏请求与保持：一次性申请所有资源（静态分配），资源利用率低
  • 破坏不可剥夺：资源可被系统抢占，但可能导致进程回退
  • 破坏循环等待：资源有序分配（给资源编号，必须按编号顺序申请）

重点 银行家算法（死锁避免）

基本思想

  • 系统维护各进程所需资源的最大量，每次分配前检查是否处于安全状态
  • 安全状态：存在安全序列使得所有进程最终能完成

单资源示例

  • 10 个可用资源，3 个进程 P、Q、R，分别最多需要 8、4、9
  • 当前已分配：P=5, Q=2, R=2（Available=1）
  • 安全序列：Q → P → R（Q 还需 2，可得 1 + 后续回收）

数据结构（5 进程 3 资源类型）

矩阵描述
Available每类资源当前可用数量
Max每个进程最多需要各类资源的数量
Allocation每个进程当前已分配的资源数量
Need每个进程还需要资源数量（Need = Max - Allocation）

安全性检查算法

  1. Work = Available，Finish[i] = false
  2. 找满足 Finish[i] = false 且 Need[i] ≤ Work 的进程 i
  3. Work = Work + Allocation[i]，Finish[i] = true，重复步骤 2
  4. 如果所有 Finish[i] = true，则系统安全

示例：T0 时刻 5 进程 3 资源

假设资源 A=10, B=5, C=7，当前系统处于安全状态，存在安全序列 P1→P3→P4→P2→P0 等

资源分配图（RAG）

  • 圆形节点 = 进程，矩形节点 = 资源类
  • 资源 → 进程（分配边），进程 → 资源（请求边）
  • 死锁检测：化简 RAG，如果存在不可化简的进程，则系统存在死锁
  • 连续化简所有不阻塞的进程，最终仍阻塞的进程是死锁进程

死锁检测与恢复

检测

  • 类似安全性检查算法，检测当前是否存在死锁进程
  • 周期性检测或资源请求失败时触发

恢复方法

方法描述缺点
重启系统强制重启所有进程简单粗暴，所有工作丢失
终止死锁进程终止部分或全部死锁进程可能丢失数据
剥夺资源从死锁进程处剥夺资源给其他进程可能导致进程回退
进程回滚将死锁进程回滚到某个安全检查点需系统支持 checkpoint
指向原始笔记的链接

线程

线程

定义

  • 线程（Thread）是 CPU 调度的基本单位，轻量级进程（Lightweight Process）
  • 一个进程可以包含多个线程
  • 同一进程的线程共享进程的地址空间和资源
  • 每个线程拥有独立的：线程 ID、程序计数器（PC）、寄存器集合、栈

TCB（线程控制块）

  • 包含：线程 ID、程序计数器、寄存器集合、栈指针
  • 相比 PCB，内容更少，切换更快

引入原因

  • 进程切换开销大（需切换地址空间、TLB 刷新）
  • 进程间通信复杂（需 IPC 机制）
  • 需要更轻量级的并发执行单元以支持高并发

进程 vs 线程

方面进程线程
资源拥有独立的地址空间和资源共享所属进程的资源
调度单位资源分配单位CPU 调度单位
切换开销大（需切换地址空间、刷新 TLB）小（仅保存/恢复寄存器+栈）
通信方式需 IPC 机制（管道、消息队列、共享内存等）直接读写共享内存/全局变量
拥有者操作系统管理用户库 或 操作系统管理
独立性进程间相互独立，一个崩溃不影响其他线程间共享，一个线程崩溃可能导致整个进程崩溃

线程优势

  • 低开销：创建和撤消线程的开销远小于进程
  • 快速切换：同一进程内的线程切换只需保存/恢复少量寄存器
  • 高效通信：线程间通过共享内存直接通信，无需内核介入
  • 高并发：一个进程可轻松创建成百上千个线程，适合高并发服务（如 Web 服务器）

线程分类

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

  • 由用户空间的线程库管理（如 POSIX Pthreads 用户态实现）
  • 内核完全不知晓线程的存在，内核调度的是进程
  • 线程切换无需陷入内核，切换速度极快
  • 缺点：一个线程阻塞（如 I/O）会导致整个进程所有线程阻塞

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

  • 由操作系统内核直接管理
  • 内核知道每个线程的存在，调度以线程为单位
  • 线程阻塞不影响同一进程中的其他线程
  • 缺点：线程切换需要陷入内核，开销比用户级大

混合模式（Combined）

  • 用户级线程复用到内核级线程上
  • 应用可创建大量用户级线程，映射到较少的内核级线程
  • 兼顾用户级的快速切换和内核级的阻塞不阻塞

线程切换开销分析

  • 同一进程内线程切换：仅需切换寄存器和栈，无需切换地址空间（TLB 有效），开销小
  • 不同进程间线程切换：需切换地址空间（TLB 刷新），开销大
指向原始笔记的链接

重点 进程调度算法对比

参考 重点 调度算法 中的 FCFS、SJF、RR、多级反馈队列对比

重点 死锁处理策略对比

参考 重点 死锁处理策略对比

关系图谱

反向链接