操作系统-进程同步与死锁

进程同步的基本概念

进程同步的引入

进程同步的核心目的是解决并发执行带来的不确定性。其根本动因来源于并发进程之间的两种制约关系：

• 间接相互制约关系（互斥关系）：程序并发执行时，由于共享资源需要互斥访问而产生
• 直接相互制约关系（同步关系）：源于一组并发进程之间的相互合作，表现为对操作先后次序的约束

临界资源与临界区

临界资源

• 一次仅允许一个进程使用的资源
• 范围：包括硬件资源如打印机和软件资源如共享变量、数据文件

临界区（Critical Section）

每个进程进入临界区需经历以下四个部分：

• 进入区：检查并设置标志，申请进入临界区
• 临界区：访问临界资源的那段代码
• 退出区：清除标志，释放临界资源的使用权
• 剩余区：进程中除以上三部分外的其余代码

解决临界区互斥问题的四条准则

• 空闲让进：若临界区空闲，应允许申请进程立即进入
• 忙则等待：若已有进程在临界区，其他进程必须等待
• 有限等待：进程应在有限时间内获得进入资格，避免饥饿
• 让权等待（可选）：不能进入临界区时，应立即释放处理机并阻塞自己，防止忙等

进程同步机制

软件同步机制：Peterson 解决方案

• 适用范围：仅适用于两个进程交替进入临界区的情况
• 核心思想：设置两个关键变量协同控制
  1. 意愿标志 flag：表示当前进程是否请求进入临界区
  2. 谦让标志 turn：表示是否优先让对方进入临界区
• 执行逻辑：进程设置自己的 flag 为真，并将 turn 指向对方。循环检测：当检测到对方请求进入且轮到对方时，才进行等待。只要有一个条件不满足，当前进程即可进入临界区
• 准则满足情况：满足空闲让进、忙则等待和有限等待，但不满足让权等待，属于忙等

硬件同步机制

关中断（Interrupt Disable）

• 基本思路：在进入临界区之前关闭中断，直到退出临界区后再打开中断
• 原理：关中断期间，CPU 不响应任何中断信号，不会触发进程调度，当前进程独占 CPU，从而保证对临界资源的互斥访问
• 缺点：
  • 关中断属于特权指令，若进程滥用可能导致系统崩溃
  • 关中断时间过长会严重影响系统响应速度和整体效率
  • 关中断只能屏蔽本 CPU 的中断，无法阻止其他 CPU 上的进程同时进入相同临界区，因此多 CPU 环境下不适用

Test-and-Set 指令

• 本质：一条不可中断的原语，可视为一个不可分割执行的函数
• 核心变量：lock 为布尔型，false 表示临界资源空闲，true 表示正在被使用
• 执行逻辑：进程调用 TS 指令，原子性地检测 lock 状态。若为 false 则将 lock 置为 true 并进入临界区；若为 true 则持续测试，直到资源空闲
• 特点：实现简单，适用于多处理器环境，但属于忙等，不符合让权等待原则

Swap 指令

• 核心思想：与 TS 指令高度相似，区别在于通过值交换实现互斥
• 执行逻辑：每个进程维护一个局部标志位 key，通过 Swap 指令不断与全局变量 lock 进行值交换，当交换结果为 lock 等于 false 时方可进入临界区

TS / Swap 指令的局限性

• 需要进程不断循环测试，处于忙等状态
• 不符合让权等待原则，浪费处理机时间
• 难以用于解决复杂的进程同步和通信问题

锁机制

硬件方案复杂且程序员无法直接采用。锁的最基本功能是提供互斥访问，根据使用目的不同分为很多类型：

• 互斥锁：实现共享资源的互斥访问，有锁定和未锁定两种状态，试图获取锁定状态的锁的线程将被挂起
• 读写锁：允许多个线程同时读取共享资源，写入时只允许一个线程操作，适用读多写少的场景，提高并发度
• 自旋锁：线程不会进入睡眠状态等待锁可用，而是循环检查，适用于加锁时间非常短的情况
• 递归锁：允许同一个线程多次获取同一个锁而不造成死锁

每个互斥锁都有一个布尔变量 available，以及两个函数 acquire 和 release。当进程获取一个不可用锁时，其会被阻塞，直到该锁被释放。

需要注意，有的互斥锁在实现上实际是忙等，本质上属于自旋锁，需结合具体实现具体分析。

信号量机制

整型信号量

• 定义：仅用一个整数 $S$ 表示资源数量
• 操作逻辑：wait 操作使 $S$ 减 1，若 $S \leq 0$ 则循环测试即忙等；signal 操作使 $S$ 加 1
• 特点：未遵循让权等待原则

记录型信号量

• 改进点：解决整型信号量的忙等问题
• 结构：在整型量基础上增加进程链表指针 list，链接等待进程
• 核心变量：S.value 表示资源数目，若 value < 0，其绝对值代表等待队列中的进程数
• 操作逻辑：wait 时资源不足则阻塞进程并插入等待队列；signal 时释放资源，若有等待进程则唤醒
• 特殊场景：初值设为 1 时，转化为互斥信号量

AND 型信号量

• 解决痛点：多个共享资源可能引发死锁
• 核心思想：进程所需全部资源一次性全部分配，用完一起释放
• 操作特性：原子操作 Swait，所有资源满足才分配，否则一个也不分配

信号量集

• 扩展功能：支持一次申请和释放多个单位资源
• 操作格式：Swait(S, t, d)，其中 S 为信号量，t 为分配下限值，资源数小于 t 时不予分配，d 为需求值
• 特殊情况：
  • Swait(S, d, d) 属于一般信号量集
  • Swait(S, 1, 1) 退化为记录型或互斥信号量
  • Swait(S, 1, 0) 为可控开关，S ≥ 1 允许进入，S = 0 阻止进入

信号量的应用

• 互斥：利用信号量实现进程互斥
• 同步：利用信号量实现进程同步

管程机制

管程的定义

一个管程由四部分组成：

• 管程的名称
• 局限于管程内的共享数据结构说明
• 对该数据结构进行操作的一组过程或函数
• 设置这些共享数据结构初值的语句

从语言和设计视角看，管程体现了面向对象早期思想的三大特性（ADT）：

• 模块化：把共享数据和对其安全的操作封装成一个独立单元
• 抽象数据类型（ADT）：外部只看见管程提供的操作接口，不直接接触内部数据
• 信息掩蔽：共享数据结构细节对外不可见，只能通过管程过程访问

管程与进程的关键区别：

• 管程定义和管理的是公共数据结构；进程定义的是私有数据结构如 PCB
• 引入进程是为实现系统并发性；引入管程是为解决共享资源的互斥和安全访问
• 管程是被动工作方式，进程通过调用管程中的过程间接操作共享数据；进程才是主动工作方式
• 进程之间能并发执行；管程本身不与调用者并发，同一时刻只允许一个进程在管程内活跃

条件变量

管程已经由编译器或运行时保证了互斥，入口和出口机制确保至多一个活跃者。但当进程在管程内发现条件未成立时，需要一种手段把自己挂起，等别的进程做完某事再把它唤醒，这就是条件变量的用意。

• 条件变量本身不带值，区别于信号量，更像等待队列的句柄
• 典型操作：
  • x.wait：调用进程挂起自己，离开管程并释放管程互斥，进入 x 的等待队列
  • x.signal：若有进程等在 x 上，则唤醒其中一个
• 操作方法：在管程内，通常配合 while(条件不成立) x.wait(); 进行等待，由改变条件的一方在管程内调用 x.signal()

经典进程同步问题

生产者-消费者问题

模型：一组生产者生产数据放入缓冲区，一组消费者从缓冲区取走数据。核心约束是缓冲区容量有限。

关键约束：

• 缓冲区满时生产者必须等待
• 缓冲区空时消费者必须等待
• 对缓冲区的访问必须互斥（同一时刻只允许一个进程操作缓冲区）

信号量设置：

• $mutex = 1$：互斥信号量，保护缓冲区
• $empty = n$：空闲缓冲区数，初始为 $n$，生产者执行 wait
• $full = 0$：已占用缓冲区数，初始为 $0$，消费者执行 wait

易错点：wait 和 signal 的顺序不能反。生产者必须先 wait(empty) 再 wait(mutex)，反过来可能死锁——先拿了互斥锁，发现缓冲区满，卡在 empty 上等着被唤醒，但唤醒它需要消费者拿 mutex，而 mutex 被自己占着。

读者-写者问题

模型：多个读者可同时读，写者独占。核心是读写之间的互斥和写写之间的互斥。

两种变体：

• 读写优先：读者来了直接进，写者必须等所有读者走完。可能饿死写者
• 读写公平：写者来了之后，新来的读者必须排队，等当前读者走完、写者写完才能进。不会饿死写者

关键信号量：

• rw_mutex = 1：控制写者独占
• mutex = 1：保护读者计数变量 count
• count：当前正在读的读者数

选择题陷阱：读者内部用 count 计数，第一个进的读者负责加锁，最后一个走的负责解锁。如果两个读者同时读到 count=0，都会去执行 wait(rw_mutex)，这里需要 mutex 保护 count 的读写。

哲学家进餐问题

模型：5 个哲学家围坐，每人左右各一根筷子，同时拿起两边筷子才能吃饭。

经典死锁：每人同时拿起左手筷子，等右手，永远吃不上。

解法：

• 奇数编号先拿左后拿右，偶数编号先拿右后拿左——打破循环等待
• 至多允许 4 个哲学家同时坐下——破坏请求条件
• 用管程或信号量同时申请两根筷子

进程同步实例

Linux 进程同步涉及用户态的 futex 和内核态的 spinlock、信号量、completion、RCU、seqlock 等原语。Windows 进程同步包括用户态的 Critical Section、SRW Lock、Interlocked 函数，以及内核态的 Mutex、Semaphore、Event 等对象。

死锁

死锁概述

资源分类

• 可重用资源：不可共享，不可在进程运行期间创建或删除，使用前需申请，使用后需释放。如处理器、内存、I/O 设备
• 可消耗资源（临时性资源）：进程运行期间动态创建和消耗，用完即弃。典型例子是进程间通信的消息
• 可抢占资源：可以从持有者手中强行收回，不会引起死锁
• 不可抢占资源：不能被强行收回，只能由持有者主动释放，是死锁的潜在诱因

死锁的产生场景

• 竞争不可抢占资源引起死锁
• 竞争可消耗资源引起死锁
• 进程推进顺序不当引起死锁，如双方各持有一把锁再申请对方的锁

死锁的定义与必要条件

定义：如果一组进程中的每个进程都在等待仅由该组进程中的其它进程才能引发的事件的发生，那么该组进程是死锁的。

四个必要条件（缺一不可，同时满足才构成死锁）：

• 互斥条件：资源一次只能被一个进程使用
• 请求和保持条件：进程已持有至少一个资源，又提出新的资源请求，新资源被占用时请求进程阻塞，但对自己持有的资源不放手
• 不可抢占条件：已分配的资源不能被强行收回，只能由持有者主动释放
• 循环等待条件：存在一个进程资源的循环等待链，每个进程都在等待下一个进程所持有的资源

死锁的处理方法

方法	思路	代价
预防死锁	破坏四个必要条件之一（破坏任一即可）	限制强，资源利用率低
避免死锁	动态分配资源时判断分配后系统是否处于安全状态，不安全则拒绝	需要预知最大需求
检测与解除	允许死锁发生，定期检测资源分配图，发现死锁后解除	开销大，恢复代价高

资源分配图

资源分配图是描述进程和资源关系的有向图：圆点代表资源类型，矩形框代表实例数，有向边分为请求边（进程指向资源）和分配边（资源指向进程）。

简化规则：依次消去进程的请求边和分配边。若一个进程的所有请求都能被满足，即对应资源有空闲实例，则可以执行完成并释放所有资源。

死锁定理：当且仅当资源分配图不可完全简化时，存在死锁。

死锁预防

破坏”请求和保持”条件

• 第一种协议：进程运行前必须一次性申请全部所需资源，系统一次性分配，资源不足则全部不给。优点是简单，缺点是资源严重浪费且饥饿现象频发
• 第二种协议：进程只获得运行初期所需的资源便开始运行，在运行过程中逐步释放已用毕的资源，再请求新的所需资源。相比第一种，减少了饥饿概率，资源利用率也更高

破坏”不可抢占”条件

当一个持有某些不可抢占资源的进程提出新请求但无法满足时，必须释放已持有的所有资源，待以后需要时再重新申请。缺点是实现复杂且代价高——进程可能运行到一半被迫交出所有资源，之前的工作可能白费。

破坏”循环等待”条件

对系统所有资源类型进行线性排序，规定每个进程必须按序号递增的顺序请求资源。缺点是限制新类型设备的增加，可能造成资源浪费，编程复杂度提高。

死锁避免

安全状态

如果系统能按某种进程推进顺序为每个进程分配其所需资源，直至最大需求，使所有进程都能顺利完成，则系统处于安全状态。安全序列不唯一，只要存在至少一个安全序列，系统就不会死锁。不安全状态不等于已死锁，但不安全状态是死锁的必要条件——系统进入不安全状态后，若进程继续申请资源就可能死锁。

银行家算法

每次资源分配前，模拟分配后检查系统是否仍处于安全状态。安全则分配，不安全则让进程等待。

核心数据结构，设 $n$ 个进程，$m$ 种资源：

• $Available[m]$：各资源当前可用数量
• $Max[n][m]$：各进程对各资源的最大需求
• $Allocation[n][m]$：各进程当前已分配的资源数
• $Need[n][m]$：各进程还需要多少资源，$Need = Max - Allocation$

资源分配算法：进程 $P_i$ 请求资源 $Request_i$，先检查 $Request_i \leq Need_i$，即不能超过声明的最大值，再检查 $Request_i \leq Available$，即资源是否充足。都满足则试探性分配，调用安全性算法检查。

安全性算法：找一个满足 $Need \leq Work$ 的未完成进程，执行完后回收资源，即 $Work += Allocation$，重复直到所有进程完成或找不到满足条件的进程。若所有进程完成则安全，否则不安全并回滚试探性分配。

死锁的检测与解除

死锁的检测

死锁定理：当且仅当资源分配图不可完全简化时，存在死锁。

检测中的数据结构：

• $Available[m]$：可用资源向量
• $Allocation[n][m]$：已分配矩阵
• $Request[n][m]$：请求矩阵。注意这不是 Need，Request 记录的是当前正在等待的请求，Need 是剩余总需求

检测时机：每次资源分配后检测，或周期性检测，需权衡开销。

死锁的解除

• 抢占资源：从死锁进程中强行回收资源分配给其他进程，被抢占的进程回退到之前的安全状态
• 终止进程：终止所有死锁进程简单粗暴但代价最大；逐个终止每次终止一个后重新检测，代价更小但开销更高
• 选择终止对象的原则：优先级低的、已运行时间短的、已获资源少的、剩余执行时间长的——总之选代价最小的那个