操作系统第二章的主线，是回答一个问题：多个程序同时运行时，操作系统如何管理它们、分配处理机、协调共享资源，并处理资源互相等待的情况？

本文从进程和线程出发，依次梳理进程控制、进程通信、处理机调度、同步互斥、信号量、管程和死锁。理解这些概念时，建议始终抓住三个对象：进程状态、PCB 信息、资源分配关系。

一、进程的基本概念

1.1 程序、进程与进程实体

程序是静态的指令集合，通常以可执行文件的形式保存在磁盘中。进程是程序的一次执行过程，是动态产生、运行和结束的过程。

进程实体（也叫进程映像）由三部分组成：

• PCB（进程控制块）：操作系统管理进程所需的信息，例如 PID、当前状态、寄存器现场、调度信息和资源清单。
• 程序段：进程要执行的程序代码。
• 数据段：运行过程中使用的全局变量、临时数据等。

进程是系统进行资源分配和处理机调度的独立单位。操作系统并不直接用一段程序代码代表一个正在运行的任务，而是通过 PCB 把代码、数据、状态和资源联系起来。

1.2 进程的特征

• 动态性：进程有创建、运行、阻塞和终止等过程，这是进程区别于静态程序的根本特征。
• 并发性：内存中可以同时存在多个进程，它们在宏观上同时推进。
• 独立性：进程可以独立获得资源、独立运行并接受调度。
• 异步性：每个进程按照自己的速度推进，执行顺序和完成时间具有不确定性。
• 结构性：每个进程都配置 PCB，进程实体由 PCB、程序段和数据段构成。

二、进程状态与进程控制

2.1 五种基本状态

1. 创建态：操作系统正在建立进程，分配资源并初始化 PCB。
2. 就绪态：进程已经具备运行条件，只等待处理机。
3. 运行态：进程正在占用 CPU 执行。
4. 阻塞态：进程因等待 I/O、信号或其他事件而暂时不能运行。
5. 终止态：进程执行结束或发生异常，操作系统正在回收资源。

PCB 中的 State 字段记录进程当前状态。典型转换包括：就绪态到运行态由调度程序触发，运行态到阻塞态通常由等待事件触发，阻塞态到就绪态由等待事件完成触发，运行态到终止态则可能由 exit 或异常引起。

2.2 进程的组织方式

链式组织方式按照进程状态建立多个队列，例如就绪队列、等待打印机的阻塞队列和等待磁盘的阻塞队列，操作系统保存各队列的指针。

索引组织方式则为不同状态建立索引表，再由操作系统保存各索引表的入口。两种方式的目的相同：让操作系统能够快速找到处于某种状态的 PCB。

2.3 原语与进程控制

进程控制会改变进程状态、更新 PCB、调整队列，并可能分配或回收资源。完成这些操作时必须保证中间状态不会被其他程序观察到，因此需要使用原语。

原语是一段执行过程具有原子性的程序，执行期间不能被中断。操作系统通常通过关中断指令和开中断指令保证原语一气呵成。

创建原语

1. 申请空白 PCB。
2. 为新进程分配所需资源。
3. 初始化 PCB。
4. 将 PCB 插入就绪队列。

用户登录、作业调度、系统提供服务以及应用程序请求，都可能触发进程创建。

终止原语

1. 找到目标进程的 PCB。
2. 如果进程仍在运行，先剥夺其 CPU。
3. 终止其子进程或子线程。
4. 回收进程占有的资源。
5. 删除 PCB。

阻塞与唤醒原语

阻塞时，操作系统保护进程运行现场，将状态改为阻塞态，再把 PCB 放入对应事件的等待队列。唤醒时，操作系统将 PCB 从等待队列移出，改为就绪态，并插入就绪队列。

阻塞和唤醒必须成对出现：阻塞表示等待某个事件，唤醒表示该事件已经发生。唤醒后进程进入的是就绪态，不会直接占用 CPU。

切换原语

进程切换包括保存原进程的运行环境、将其 PCB 放入相应队列、选择新进程、更新新进程 PCB，并恢复新进程的运行环境。切换本身有开销，过于频繁会降低系统有效执行时间。

三、进程通信与线程

3.1 进程通信

不同进程拥有相互独立的地址空间，进程之间不能直接读写对方的内存，因此需要操作系统提供进程通信机制（IPC）。

共享存储

操作系统在内存中划出共享区域，让多个进程通过该区域交换数据。基于数据结构的共享限制较多，属于低级通信方式；基于存储区的共享由进程自行决定数据格式和存放位置，速度更快，属于高级通信方式。

共享区同时只能被一个进程以互斥方式访问，否则会出现数据覆盖和读写冲突。同步工具可以使用信号量等机制。

消息传递

消息传递以格式化消息为单位，通过发送和接收原语完成数据交换。直接通信时，发送方直接指定接收进程；间接通信时，发送方和接收方通过信箱交换消息。

管道通信

管道是由系统调用建立的特殊共享文件，通常对应内存中的固定大小缓冲区。管道具有单向、先进先出和半双工特点，需要双向同时通信时应建立两个管道。

当管道写满时，写进程阻塞；当管道读空时，读进程阻塞。管道中的数据被读出后就会消失，因此多个进程读取同一管道时需要特别注意数据分配和同步。

3.2 线程

线程是程序执行流的最小单位，也是基本的 CPU 执行单位。引入线程后，进程主要负责分配除 CPU 之外的系统资源，线程负责接受处理机调度。

用户级线程由线程库管理，线程切换可以在用户态完成，开销较小；缺点是一个用户级线程阻塞时，整个进程可能被阻塞，而且多个用户级线程不能真正并行使用多核 CPU。

内核级线程由操作系统内核管理，内核为每个线程建立 TCB。一个线程阻塞后，同一进程中的其他线程仍可能运行，也可以在多核处理机上并行执行；代价是线程切换需要进入核心态，管理开销更大。

多线程模型描述用户级线程与内核级线程的映射关系：

• 一对一：一个用户级线程对应一个内核级线程，并发能力强，但内核线程数量多。
• 多对一：多个用户级线程对应一个内核级线程，切换开销小，但一个线程阻塞可能导致整个进程阻塞。
• 多对多：多个用户级线程映射到多个内核级线程，在并发能力和管理开销之间折中。

四、处理机调度

4.1 三个调度层次

• 高级调度（作业调度）：从外存后备队列选择作业调入内存并建立进程。每个作业通常只调入一次、调出一次。
• 低级调度（进程调度）：从就绪队列选择进程，把 CPU 分配给它。它是最基本、发生频率最高的调度。
• 中级调度：决定哪些挂起进程重新调入内存，一个进程可能多次被调出和调入。

调度程序需要决定两个问题：让哪个进程运行，以及它可以运行多长时间。没有可运行的普通进程时，系统会安排优先级最低的闲逛进程运行，避免 CPU 空转。

4.2 调度时机与调度方式

进程主动放弃 CPU 的情况包括正常终止、运行异常终止和主动请求阻塞，例如等待 I/O。时间片用完、更高优先级进程进入就绪队列或发生紧急 I/O 事件，则属于被动放弃。

处理中断、执行操作系统内核程序临界区以及执行原语时，不能随意进行进程调度和切换，否则可能破坏内核数据结构的一致性。

非剥夺调度只允许进程主动释放 CPU，实现简单、开销小，但响应紧急任务的能力较弱。剥夺调度允许系统暂停当前进程并分配 CPU 给更紧急的进程，更适合分时系统和实时系统。

4.3 调度算法的评价指标

• CPU 利用率 = CPU 忙碌时间 ÷ 总时间。
• 吞吐量 = 单位时间内完成的作业数。
• 周转时间 = 完成时间 - 到达时间。
• 带权周转时间 = 周转时间 ÷ 实际运行时间。
• 等待时间 = 进程处于等待处理机状态的时间总和。
• 响应时间 = 提交请求到首次得到响应的时间。

评价算法时不能只看一个指标。缩短平均等待时间的算法，未必能同时提供最好的公平性和响应速度。

4.4 常见调度算法

先来先服务（FCFS）

按照到达先后顺序调度，规则简单且公平。缺点是长作业排在前面时，会让后续短作业等待很久。

短作业优先（SJF）

每次选择当前已到达且运行时间最短的进程，目标是降低平均等待时间。它需要预估运行时间，长作业可能长期得不到服务，产生饥饿。

抢占式短作业优先也叫最短剩余时间优先。就绪队列发生变化时，如果新进程的剩余时间更短，就抢占当前进程。

最高响应比优先（HRRN）

响应比计算公式为：

响应比 = （等待时间 + 要求服务时间）÷ 要求服务时间

等待时间越长，响应比越高，因此 HRRN 在兼顾短作业的同时，可以缓解长作业饥饿。它通常属于非抢占式调度。

时间片轮转（RR）

就绪队列中的进程轮流执行一个时间片，常用于分时系统。时间片过大时，算法接近 FCFS；时间片过小时，进程切换频繁，保存和恢复运行环境的开销增加。

优先级调度

每次选择优先级最高的进程，可以是抢占式，也可以是非抢占式。系统进程通常高于用户进程，前台进程通常高于后台进程，I/O 型进程也可能获得更高优先级。优先级长期不变时，同样可能发生饥饿。

多级反馈队列

系统设置多个就绪队列，队列优先级从高到低，时间片从小到大。新进程先进入高优先级队列；时间片用完仍未结束时，降到下一级队列。只有高优先级队列为空，低一级队列才获得 CPU。

多级反馈队列不要求事先准确知道进程运行时间，能够较快响应新进程，也能让短作业较早完成，同时降低 CPU 密集型进程对交互式进程的影响。

五、进程同步与互斥

5.1 同步、互斥与临界区

同步是进程之间为完成共同任务而形成的直接制约关系，例如生产者必须先生产，消费者才能消费。互斥是多个进程访问临界资源时形成的间接制约关系。

临界资源是一次只允许一个进程使用的资源，访问临界资源的代码称为临界区。一个正确的互斥方案应满足：

1. 空闲让进：临界区空闲时，请求进程可以进入。
2. 忙则等待：已有进程进入临界区时，其他进程必须等待。
3. 有限等待：请求进程不能无限期等待。
4. 让权等待：等待时应释放 CPU，避免忙等。
   

5.2 软件实现方法

单标志法通过轮流赋予进入权限实现互斥，但临界区空闲时可能仍不允许某个进程进入，违反空闲让进。

双标志先检查法先检查对方标志，再设置自己的标志。检查和上锁不是原子操作，两个进程可能同时通过检查，违反忙则等待。

双标志后检查法先上锁再检查，避免了同时进入，但两个进程可能都先上锁，造成长期等待，违反空闲让进和有限等待。

Peterson 算法结合标志和谦让变量，能够满足空闲让进、忙则等待和有限等待，但仍可能忙等，不能完全满足让权等待。

5.3 硬件实现方法

中断屏蔽通过关中断保护临界区，简单高效，但只适合内核程序，且不适用于多处理机环境。

TestAndSet 和 Swap 指令由硬件保证原子性，把检查和上锁合并为不可分割的操作，适合多处理机系统。它们的共同缺点是可能让等待进程持续占用 CPU，形成忙等。

六、信号量与管程

6.1 信号量

信号量是表示系统中某类资源数量的变量，进程通过 wait 和 signal 原语对它进行操作。记录型信号量除了记录 value，还维护等待进程队列。

典型操作可以概括为：

wait(S)：S.value 减一；若结果小于 0，当前进程进入阻塞队列
signal(S)：S.value 加一；若仍有进程等待，则唤醒其中一个

wait 用于申请资源，signal 用于释放资源。操作必须是原子的，否则多个进程同时修改信号量会产生竞态。

6.2 用信号量实现互斥与同步

实现互斥时，把互斥信号量初始化为 1。进程进入临界区前执行 wait，离开临界区后执行 signal，因此同一时刻最多只有一个进程通过。

实现同步时，把同步信号量初始化为 0。前驱进程完成任务后执行 signal，后继进程执行 wait；由于初始值为 0，后继进程必须等前驱进程先释放信号。

前驱关系可以抽象为：前一个操作末尾执行 V，后一个操作开头执行 P。分析题目时，先找出“谁必须先完成”，再把 V 放在前驱操作之后，把 P 放在后继操作之前。

6.3 管程

管程把共享数据、对数据操作的过程以及同步机制封装在一起，并保证同一时刻只有一个进程在管程内执行某个内部过程。相比直接在业务代码中分散使用信号量，管程更容易集中维护互斥规则。

七、死锁及其处理

7.1 死锁与饥饿

死锁是并发进程相互等待对方占有的资源，导致所有相关进程都无法继续运行的状态，通常至少涉及两个进程。

饥饿是某个进程长期得不到所需资源或服务，但系统中其他进程仍可能继续运行。死锁强调循环等待，饥饿强调某个进程长期得不到机会。

7.2 死锁的四个必要条件

1. 互斥条件：资源一次只能被一个进程占用。
2. 不剥夺条件：资源未使用完之前，不能被强行夺走。
3. 请求和保持条件：进程已经保持部分资源，又继续请求其他资源。
4. 循环等待条件：存在进程资源的循环等待链。

四个条件同时成立，死锁才可能发生。因此预防死锁的基本思路，就是破坏其中至少一个条件。

7.3 预防死锁

• 破坏互斥条件：使用 SPOOLing 等技术，把独占设备改造成共享使用形式，但并非所有资源都能这样处理。
• 破坏不剥夺条件：当进程申请不到新资源时，主动释放已经占有的资源，或允许系统剥夺部分资源。
• 破坏请求和保持条件：采用静态分配，让进程运行前一次性申请全部资源。
• 破坏循环等待条件：规定资源的顺序，进程必须按编号递增顺序申请资源。

预防方法通常会降低资源利用率或并发度，所以实际系统还会结合避免和检测方法。

7.4 避免死锁：银行家算法

银行家算法在每次资源分配前，先假设分配发生，再检查系统能否找到一个安全序列。如果存在安全序列，说明所有进程仍有可能依次完成，可以进行分配；如果进入不安全状态，则暂缓本次分配。

安全状态不等于当前没有资源竞争，而是表示系统仍存在一条让所有进程完成的资源分配顺序。做题时应先计算各进程的剩余需求，再用当前可用资源逐步尝试满足某个进程，释放其资源后继续寻找下一个进程。

7.5 检测与解除死锁

系统也可以先允许资源分配，定期检测是否形成死锁。检测到死锁后，常见解除方式包括：

1. 资源剥夺：从部分进程中夺取资源，分配给其他进程。
2. 进程撤销：撤销一个或多个进程并回收其资源。
3. 进程回退：让进程回退到足够安全的检查点，再重新运行。

选择解除方式时，需要综合考虑进程优先级、已完成工作量、回退代价和系统损失。

总结

本章可以按一条链路理解：进程通过 PCB 被操作系统管理，线程提高程序的并发度，调度算法决定处理机的分配顺序；进程通信解决数据交换，同步互斥解决共享资源竞争，信号量和管程提供协作工具；当资源分配形成循环等待时，就需要通过预防、避免或检测解除死锁。

遇到具体题目时，可以先判断进程状态和资源关系，再选择对应工具：状态变化看原语，CPU 分配看调度算法，共享资源看互斥与信号量，资源互相等待看死锁四条件和安全序列。

参考资料

1. 王道操作系统第二章。