第二章：进程和线程

约 2518 个字 3 行代码 预计阅读时间 8 分钟

进程是进程实体的 运行过程，是系统进行 资源分配 和 调度 的一个独立单位。

• 进程实体：程序段、数据段、PCB。
• 进程的特征：动态性，并发性，独立性，异步性，结构性。
• 进程最基本的特性：动态性

独立性：每个进程的空间是独立的，不能互相访问。

线程

• 线性是一个轻型实体，他不拥有系统资源
• 不同的线程可以执行相同的程序
• 统一进程中的各个线程共享该进程所用有的资源
• 线程时处理机的「独立调度」单位

进程和线程

进程的状态与转化

状态：创建态，运行态，阻塞态，就绪态，终止态。

• 就绪态：等 CPU，得到 CPU 转化为 运行态
• 阻塞态：等 IO，IO 完成后转化为 就绪态
• 运行态：占用 CPU。若遇到请求 IO，进程调用 ”system call“ ，转化为 阻塞态；若时间片结束，则转化为 就绪态。

进程控制

进程控制用 原语 来实现进程状态的转化，执行期间不允许中断。

• 进程的创建：申请空白 PCB，分配资源，初始化 PCB，将 PCB 插入就绪队列，等待 CPU 的调度
• 进程的切换：保存进程状态到 PCB 中，PCB 移入相应队列（如就绪、阻塞队列），选择在另一个进程执行，恢复进程状态
• 进程的阻塞与唤醒

1. 进程的阻塞：当进程请求某项资源但无法立即获得时（如 I/O 操作），操作系统会将其置为阻塞态，并转移到阻塞队列。

2. 进程的唤醒：当阻塞的原因消失（如 I/O 操作完成）时，操作系统将进程的状态改为就绪态，并重新加入就绪队列。

3. 进程的阻塞和唤醒 是 一对作用相反的操作。

• 进程的终止：终止请求，资源回收，删除 PCB

进程通信

共享存储，消息传递，管道通信

线程

线程的实现方式

1. 用户级线程：用户编写了一个关于线程的函数库，用函数库来实现线程；线程库写的多线程进程，但只能一次在一个 CPU 核心上运行，操作系统实际上不知道有这个的存在，调度的对象是「进程」
2. 内核级线程：在 kernel 里面的线程，每次调用都要切换到「内核态」，开销比较大捏，但能做到并行运行。
3. 内核级线程比用户级线程，系统开销大

多线程模型

1. 一对一模型
   • 一个用户级线程映射到一个内核级线程
   • 优：各个线程可分配到多核处理机并发执行，并发度高
   • 缺：线程管理都需要操作系统支持，开销大
2. 多对一模型
   • 多个用户级线程映射到一个内核级线程
   • 优：线程管理开销小效率高
   • 缺：一个线程阻塞会导致整个进程都被阻塞
3. 多对多模型
   • n 个用户级线程映射到 m 个内核级线程
   • 集二者之所长

处理机调度

调度的类型

1. 高级调度（作业调度）：将作业调入内存
2. 低级调度（进程调度）：将进程分配给处理机
3. 中级调度（内存调度）：暂时调入外存等待的进程处于「挂起状态」，将挂起状态的进程 「重新调入」内存。

调度的目标

1. CPU 利用率：\(\frac{CPU占用的时间}{总时间}\)
2. 系统吞吐量：\(\frac{作业数}{总时间}\)
3. 周转时间
   • 周转时间：作业完成时间 \(-\) 作业提交时间
   • 带权周转时间：\(\frac{作业周转时间}{作业实际运行的时间}\)
4. 等待时间：等待被服务的时间
5. 响应时间：从用户提交请求到首次产生相应所用的时间

进程调度的方式

非抢占式 和「抢占式」，抢占式可以优先处理更紧急的进程。

进程调度、切换是有代价的。

闲逛进程（idle）：没有其他就绪进程时，运行闲逛进程

调度算法

先来先服务（FCFS，first come first serve）

• 非抢占式的算法
• 按照作业/进程到达的「先后顺序」进行服务
• 长作业有利，短作业不利

短作业优先（SJF，shortest job first）

• 非抢占式的算法
• 每次调度选择「当前已到达」且「运行时间最短的」作业
• 对长作业不友好，会有「长作业饥饿」问题

最短剩余时间优先算法（SRTN）

• 抢占式的算法
• 调度时机
  1. 新进程加入就绪队列时
  2. 当前进程完成时
• 调度时，考虑 「剩余时间」最短的进程进行服务

高响应比优先（HRRN，highest response ratio next）

• 非抢占式的算法
• 综合考虑等待时间和服务时间，响应比 = \(\frac{等待时间 + 服务时间}{服务时间}\)
• 等待时间长的优先，服务时间短的优先
• 避免了「长作业饥饿」问题

时间片轮转调度算法（RR，round-robin）

• 抢占式的算法
• 运行完的进程，进入就绪队列的 「队尾」
• 若当 A 进程运行完当前时间片时，B 进程进入就绪队列，则下一个运行的进程为 B 进程，A 进程插入队尾。
• 时间片太大 --> 退化为先来先服务算法；时间片太小 --> 进程调度/切换的代价太大

优先级调度算法

• 抢占式/非抢占式 都有
• 非抢占式的，等当前进程运行完了，再选择优先级最高的
• 抢占式的，一旦就绪队列中有「优先级高于当前进程的」，则抢占
• 可能会导致饥饿

互斥与同步

一段时间内只允许一个进程使用的资源称为 「临界资源」

对临界资源的互斥访问，应遵循以下原则：

1. 空闲让进：「单标志法」违反空闲让进原则
2. 忙则等待：「双标志先检查法」违反忙则等待（先检查，后上锁）
3. 有限等待：「双标志后检查法」违反有限等待和空闲让进，会有饥饿问题（先上锁，后检查）
4. 让权等待：「Peterson法」违反让权等待

信号量机制

记录型信号量：semaphore S

1. 信号量的初值表示系统中「某种资源的数目」
2. P 操作中，先 S.value --，之后可能需要执行 block 原语
3. V 操作中，先 S.value ++，之后可能需要执行 wakeup 原语
4. S.value < 0 说明有多少个进程在阻塞队列

同步关系的实现：前 V 后 P（第一个进程 V 操作，第二个进程 P 操作，这样来实现先后关系）

PV 操作

P，V操作只是与临界资源有关，被临界资源阻塞了，和 CPU 调度无关

• P 操作：block，将进程从「运行态」到「阻塞态」
• V 操作：wake-up，将进程从「阻塞态」到 「就绪态」

管程

管程的特性保证了「进程互斥」，也可用于进程同步。

• 每次仅允许一个进程在管程内执行某个内部过程
• 只能通过管程提供的「特定入口」才能访问共享数据

将阻塞原因定义为「条件变量(condition)」，每个条件变量保有一个等待队列。

• 条件变量是 “没有值”的，只有一个等待队列，区别于「信号量」。
• 管程中，剩余资源数用共享数据结构记录。

经典同步问题

生产者消费者

生产者、消费者共享一个「初始为空、大小为 \(n\) 」的缓冲区

缓冲区是临界资源，各进程必须互斥地访问。

• 互斥信号量：临界资源
• 同步信号量：前 V 后 P。成对的写，先在生产者写 V，紧接着在对应的消费者写 P。

P的先后顺序：先同步，再互斥（要考虑有没有人用，再考虑能不能用）

V的先后顺序可以交换。

吸烟者问题

可以生产多个产品的单生产者

读者写者问题

要求：

1. 允许多个读者同时读
2. 写者只能自己一个写（不能有其他读者/写者）

semaphore rw = 1;    // 用于实现对共享文件的互斥访问
int count = 0;       // 记录 当前有几个读进程在访问文件
semaphore mutex = 1; // 用于保证对 count 变量的互斥访问

哲学家进餐问题

添加一些限制条件：当一名哲学家左右两边的筷子都可用时，才能吃饭

死锁

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

死锁的必要条件

• 互斥条件
• 不可剥夺条件
• 请求和保持条件
• 循环等待条件

只是「必要条件」捏。

死锁的处理策略

1. 预防死锁：破坏四个必要条件中的一个
2. 避免死锁：避免进入不安全状态，「银行家算法」
3. 死锁的检测和接触：允许死锁的发生，采取措施来解除。

银行家算法

安全序列：按照安全序列分配资源，每个进程都能顺序完成。

若找不到任何一个安全序列，系统就进入了「不安全状态」

系统处于安全状态，就 一定不会 发生死锁；处于不安全状态，可能 发生死锁。

银行家算法思想：在进程提出资源申请时，先判断此次分配是否会导致系统进入不安全状态。

• Max 表示各进程对资源的最大需求数
• Available 表示还有多少可用资源
• Allocation 表示已经给进程分配了多少资源
• Need = Max - Allocation 表示各进程最多还需要多少资源
• Request 表示进程此次申请的各种资源数

死锁的检测

资源分配图

死锁检测算法：依次消除边，直到无边可消。

死锁定理：当资源分配图是不可完全简化的（不能消除所有边），为死锁。

死锁解除：资源剥夺法，撤销进程法，进程回退法。

---

Created: April 24, 2026
Last update: April 24, 2026

Discussion