第四章：进程同步 学习笔记
一、 核心概念
1. 进程同步的必要性
在并发环境下，多个进程（或线程）共享系统资源（如CPU、内存、文件、I/O设备等）。若对它们的执行顺序不加控制，可能会导致竞争条件，即多个进程对同一共享数据进行操作，而最终结果取决于进程执行的特定时序，导致结果的不确定性和错误。
2. 临界区问题
- 临界资源：一次仅允许一个进程使用的资源（如打印机、共享变量）。
- 临界区：进程中访问临界资源的那段代码。
- 一个良好的进程同步机制需要满足三个条件：
- 互斥：同一时间只有一个进程可以进入临界区。
- 前进（空闲让进）：如果没有进程在临界区内，且已有进程申请进入，那么应允许其中一个申请者进入。
- 有限等待：一个进程申请进入临界区后，应在有限时间内获得许可，避免“饥饿”。
二、 进程同步的软件与硬件方法
1. 软件方法（算法）
- Peterson算法：一个经典的、基于软件的双进程互斥算法，通过设置turn和flag数组来实现互斥和有限等待。它证明了纯软件方法可以实现互斥，但通常只适用于两个进程，且在现代多核/多处理器环境下可能因内存访问顺序（内存模型）问题而失效。
- Dekker算法：早期的双进程互斥算法。
2. 硬件方法
- 关中断：进入临界区前关中断，离开后开中断。简单有效（对单核CPU），但不适用于多处理器系统，且将权力交给用户进程是危险的。
- 硬件指令：利用特殊的原子（不可分割）指令，如Test-and-Set指令和Swap指令。这些指令在硬件层面保证了读-改-写操作的原子性，是实现锁等高级同步原语的基础。
三、 高级同步机制（同步原语）
1. 信号量
由Dijkstra提出，是操作系统提供的一种功能强大的同步工具。
- 整型信号量：一个整型变量
S，仅能通过两个原子操作访问： wait(S)或P(S)：当S<=0时循环等待；否则S--。
signal(S)或V(S)：S++。
- 记录型信号量：为解决整型信号量“忙等”（占用CPU循环检查）问题，引入一个等待队列。
wait操作在资源不足时将进程阻塞并放入队列；signal操作释放资源后，若队列不空则唤醒一个等待进程。 - 应用：
- 互斥信号量：初始值通常为1（表示一个可用资源），用于实现互斥。
- 同步（资源计数）信号量：初始值可以是N（表示有N个可用资源），用于控制对多个实例的资源的访问。
2. 管程
一种高级语言层面的同步机制，将共享变量及其相关的操作（过程）封装在一个模块中。管程内部任何时刻只能有一个进程（或线程）活动，由编译器负责实现互斥。进程通过调用管程的过程来访问共享资源。为了处理更复杂的同步条件，管程引入了条件变量及相关操作（wait和signal）。
四、 经典同步问题
1. 生产者-消费者问题
- 描述：一组生产者进程向固定大小的缓冲区放入数据，一组消费者进程从中取出数据。
- 同步要点：
- 缓冲区空时，消费者必须等待生产者。
- 缓冲区满时，生产者必须等待消费者。
- 对缓冲区的访问（修改指针）必须互斥。
- 解决方案：通常使用三个信号量：
mutex（互斥，初值1）、empty（空缓冲区数，初值N）、full（满缓冲区数，初值0）。
2. 读者-写者问题
- 描述：多个读者和写者共享一个数据对象（如文件）。允许多个读者同时读，但写者必须独占访问（即写时不允许任何其他读者或写者）。
- 变体：
- 读者优先：只要有一个读者在读，后续读者可以直接读，可能导致写者“饥饿”。
- 写者优先：一旦有写者等待，新到的读者必须等待，直到所有等待的写者完成。
- 解决方案：使用信号量或读写锁。
3. 哲学家进餐问题
- 描述：五个哲学家围坐圆桌，交替思考和吃饭。每人左右各有一根筷子，吃饭需要同时拿起左右两根筷子。
- 挑战：如何设计协议，防止死锁（如每人拿起左边筷子后无限等待右边）和饥饿。
- 解决方案：
- 限制最多允许4个哲学家同时拿筷子。
- 要求哲学家同时拿起两根筷子（原子操作）。
- 非对称策略：奇数号哲学家先拿左筷再拿右筷，偶数号反之。
五、 与计算机系统服务的关系
进程同步机制是操作系统内核提供的最核心的系统服务之一。它直接支撑着：
- 并发执行服务：操作系统通过进程/线程管理提供并发执行的能力，而同步机制是保证这种并发正确、有序进行的基础。没有同步，并发将导致混乱。
- 资源共享服务：操作系统管理着所有系统资源。同步机制（如信号量、锁）是操作系统提供给用户进程安全、有序地共享这些资源（内存、文件、设备）的“工具包”。
- 进程间通信服务：许多IPC机制，如消息队列、共享内存，其底层实现都严重依赖于同步机制来保证数据传递的正确性。例如，共享内存区必须通过信号量或锁来保护。
- 死锁处理服务：同步机制使用不当（如对多个信号量的申请顺序不一致）是导致死锁的主要原因。操作系统在提供同步原语的也需要提供死锁的预防、避免、检测与解除策略（详见后续章节），这共同构成了完整的并发控制服务体系。
- 系统调用接口：
wait,signal, 以及各种锁（如互斥锁、读写锁、条件变量）的API，都是操作系统通过系统调用暴露给应用程序的系统服务。应用程序通过调用这些服务来编写正确的并发程序。
**：第四章的进程同步，是操作系统课程从理论走向实践的关键桥梁。它不仅仅是几个算法和问题，更是理解操作系统如何作为资源管理者和服务提供者**的核心视角。掌握进程同步，就是掌握了让多个任务在计算机中高效、和谐共舞的指挥棒，这是构建任何复杂、可靠软件系统的基石。
