一、进程同步算法题解法详解
1. 基本概念深入理解
临界资源：
- 定义：一次仅允许一个进程使用的共享资源
- 例子：打印机、共享变量、数据文件等
- 特性：必须互斥访问，否则会产生数据不一致
同步：
- 定义：多个进程为了完成共同任务而需要协调执行顺序
- 例子：生产者-消费者问题，生产者生产后消费者才能消费
互斥：
- 定义：保证多个进程不能同时进入临界区
- 实现方式：信号量、锁等机制
2. 信号量使用范式
二元信号量（互斥锁）：
Semaphore mutex = 1; // 初始值为1
Process(){
wait(mutex); // 进入临界区
// 临界区代码
signal(mutex); // 离开临界区
} 计数信号量（资源计数）：
Semaphore resources = N; // 初始有N个资源
Process(){
wait(resources); // 申请一个资源
// 使用资源
signal(resources); // 释放资源
} 3. 经典例题详细分析
例1：水果盘子问题（生产者-消费者变种）
问题定义：
- 一个盘子，每次只能放一个水果
- 爸爸：专门放苹果
- 妈妈：专门放橘子
- 儿子：专门吃橘子
- 女儿：专门吃苹果
- 同步关系：
- 盘子空时，爸爸或妈妈才能放水果
- 有对应水果时，儿子或女儿才能取水果
信号量设计：
Semaphore plate = 1; // 盘子互斥，初始有1个空位
Semaphore apple = 0; // 苹果数量，初始0个
Semaphore orange = 0; // 橘子数量，初始0个 代码逻辑：
// 爸爸进程：生产者（苹果）
Dad(){
while(1){
prepare_apple(); // 准备苹果（非临界区）
wait(plate); // 等待盘子空
put_apple(); // 放苹果到盘子
signal(apple); // 通知有苹果可用
// 注意：这里没有signal(plate)，因为盘子已被占用
}
}
// 女儿进程：消费者（苹果）
Daughter(){
while(1){
wait(apple); // 等待有苹果
take_apple(); // 从盘子取苹果
signal(plate); // 释放盘子
eat_apple(); // 吃苹果（非临界区）
}
}
// 妈妈和儿子的代码类似，只是操作的对象不同 关键点：
- plate信号量控制盘子访问的互斥
-
apple和orange信号量实现生产者-消费者同步
- 每个水果的放和取是配对的
例2：和尚打水问题（多资源同步）
问题定义：
- 资源：水井（1口）、水缸（容量10桶）、水桶（3个）
- 小和尚：从井打水倒入缸
- 老和尚：从缸取水喝
- 约束条件：
- 水井窄，每次只能一个桶取水
- 水缸不能同时入水和取水
- 水桶总数3个，要竞争使用
信号量设计：
Semaphore well = 1; // 水井互斥
Semaphore vat = 1; // 水缸互斥
Semaphore pail = 3; // 可用水桶数
Semaphore empty = 10; // 水缸剩余空间
Semaphore full = 0; // 水缸当前水量 老和尚取水逻辑：
Old_Monk(){
while(1){
wait(full); // 等待水缸有水
wait(pail); // 申请水桶
wait(vat); // 申请水缸访问权
take_water_from_vat(); // 从水缸取水
signal(vat); // 释放水缸
signal(empty); // 水缸空间+1
drink_water(); // 喝水
signal(pail); // 归还水桶
}
} 小和尚打水逻辑：
Young_Monk(){
while(1){
wait(empty); // 等待水缸有空间
wait(pail); // 申请水桶
wait(well); // 申请水井
fetch_water_from_well(); // 从井打水
signal(well); // 释放水井
wait(vat); // 申请水缸
pour_water_to_vat(); // 倒水入缸
signal(vat); // 释放水缸
signal(full); // 水缸水量+1
signal(pail); // 归还水桶
}
} 同步关系分析：
- 水井和水缸都是临界资源，需要互斥访问
- 水桶数量有限，需要信号量控制
- 水缸容量限制，通过empty/full信号量同步
例3：吸烟者问题（多生产者单消费者变种）
问题定义：
- 供应者：提供三种材料中的两种
- 三个吸烟者：各拥有一种固定材料
- 规则：
- 供应者随机放两种材料到桌子
- 拥有第三种材料的吸烟者可以卷烟抽烟
- 抽烟完成后通知供应者
信号量设计：
Semaphore offer1 = 0; // 烟草+纸组合就绪
Semaphore offer2 = 0; // 烟草+胶水组合就绪
Semaphore offer3 = 0; // 纸+胶水组合就绪
Semaphore finish = 0; // 抽烟完成信号 供应者逻辑：
Supplier(){
while(1){
int random = rand() % 3; // 随机选择组合
switch(random){
case 0: signal(offer1); break; // 提供烟草+纸
case 1: signal(offer2); break; // 提供烟草+胶水
case 2: signal(offer3); break; // 提供纸+胶水
}
wait(finish); // 等待吸烟完成
}
} 吸烟者逻辑：
// 拥有烟草的吸烟者（需要纸+胶水）
Smoker_Tobacco(){
while(1){
wait(offer3); // 等待纸+胶水组合
make_cigarette(); // 卷烟
smoke(); // 抽烟
signal(finish); // 通知完成
}
}
// 拥有纸的吸烟者（需要烟草+胶水）
Smoker_Paper(){
while(1){
wait(offer2); // 等待烟草+胶水组合
make_cigarette();
smoke();
signal(finish);
}
}
// 拥有胶水的吸烟者（需要烟草+纸）
Smoker_Glue(){
while(1){
wait(offer1); // 等待烟草+纸组合
make_cigarette();
smoke();
signal(finish);
}
} 关键特性：
- 供应者相当于生产者，吸烟者相当于消费者
- 但每个消费者只消费特定的”产品组合”
- 通过不同的信号量区分不同材料组合
例4：独木桥问题（读者-写者问题变种）
问题定义：
- 独木桥：一次只能通行一个方向的队伍
- 两个士兵队伍：分别有m和n个士兵
- 规则：
- 桥上不能有相反方向的士兵
- 同一队伍可以连续过桥
- 必须等前一队伍全部过完，另一队才能开始
这实际上是读者-写者问题的变种：
- 每个队伍相当于”读者”
- 关键是要保证同一时间只有一个方向的”读”
信号量设计：
int count1 = 0, count2 = 0; // 各队桥上人数计数
Semaphore mutex1 = 1, mutex2 = 1; // 保护count1, count2
Semaphore bridge = 1; // 桥的互斥访问 第一队士兵逻辑：
Soldier_Team1(){
wait(mutex1); // 申请count1的访问权
count1++; // 本队桥上人数+1
if(count1 == 1){ // 如果是本队第一个上桥
wait(bridge); // 申请桥的使用权（阻止另一队）
}
signal(mutex1); // 释放count1
// 过桥（临界区）
cross_bridge();
wait(mutex1); // 再次申请count1访问权
count1--; // 本队桥上人数-1
if(count1 == 0){ // 如果是本队最后一个下桥
signal(bridge); // 释放桥的使用权（允许另一队）
}
signal(mutex1); // 释放count1
} 第二队士兵逻辑类似，只是操作count2和mutex2。
工作原理：
- bridge信号量保证两个队伍不会同时使用桥
- count1和count2记录各队当前在桥上的人数
-
第一个上桥的士兵申请bridge，最后一个下桥的士兵释放bridge
- mutex1和mutex2保护各自的计数器
二、死锁详解
1. 死锁定义与实例
死锁定义：
一组进程因竞争资源而陷入相互等待的状态，每个进程都在等待另一个进程释放资源，导致所有进程都无法继续执行。
经典死锁例子：
// 两个进程，两个资源（A和B）
Semaphore A = 1, B = 1;
Process_P0(){
wait(A); // 持有A，等待B
wait(B);
// ...
}
Process_P1(){
wait(B); // 持有B，等待A
wait(A);
// ...
} 执行顺序可能导致死锁：
时间点 P0操作 P1操作 状态
t0 wait(A) P0获得A
t1 wait(B) P1获得B
t2 wait(B) P0等待B（但B被P1持有）
t3 wait(A) P1等待A（但A被P0持有）
→ 死锁发生！ 2. 死锁的四个必要条件
- 互斥（Mutual Exclusion）
- 资源只能独占使用
- 例子：打印机不能同时被多个进程使用
- 资源只能独占使用
- 持有并等待（Hold and Wait）
- 进程持有至少一个资源，同时等待其他资源
- 例子：P0持有A等待B，P1持有B等待A
- 进程持有至少一个资源，同时等待其他资源
- 不可抢占（No Preemption）
- 资源只能由持有进程自愿释放
- 系统不能强制收回资源
- 资源只能由持有进程自愿释放
- 循环等待（Circular Wait）
- 存在进程等待环：P0→P1→P2→…→P0
- 每个进程都在等待下一个进程持有的资源
- 存在进程等待环：P0→P1→P2→…→P0
四个条件必须同时满足才会发生死锁。
3. 资源分配图详解
资源分配图组成：
- 圆形节点：表示进程（P₁, P₂, …）
- 矩形节点：表示资源类型（R₁, R₂, …）
- 圆点：矩形中的圆点表示资源实例
- 请求边：从进程指向资源的箭头（Pᵢ → Rⱼ）
- 分配边：从资源实例指向进程的箭头（Rⱼ → Pᵢ）
具体例子（来自PDF第38页）：
R1 (有1个实例) R2 (有2个实例) R3 (有1个实例)
● ●● ●
| | |
| | |
P1 ---→ R2 P2 ---→ R3 P3 ---→ R1
| |
| |
P2 ---→ R1 P3 ---→ R2 这个图表示：
- P1：持有R1的一个实例，请求R2
- P2：持有R2的一个实例，请求R3
- P3：持有R3的一个实例，请求R1
图中有循环：P1→R2→P2→R3→P3→R1→P1
死锁判断：
- 有循环 + 每个资源只有一个实例 ⇒ 必然死锁
- 有循环 + 资源有多个实例 ⇒ 可能死锁（需要进一步分析）
4. 死锁处理方法对比
（1）死锁预防
策略：破坏四个必要条件中的至少一个
具体方法：
-
破坏互斥：让资源可共享（但很多资源本质不能共享）
- 破坏持有等待：进程开始前申请所有所需资源
- 优点：简单
- 缺点：资源利用率低，可能饥饿
- 破坏不可抢占：强制收回资源
- 实现复杂，适用于易保存恢复状态的资源
- 破坏循环等待：给资源编号，按序申请
- 常用方法，但可能降低资源利用率
(2) 死锁避免 (Deadlock Avoidance)
策略：系统在分配资源前，会预先判断这次分配是否会导致系统进入不安全状态 (Unsafe State)。如果不安全，则进程必须等待。
银行家算法详解 (Banker’s Algorithm)
核心思想：银行家在批准贷款（分配资源）前，必须确保即使所有客户（进程）都提出最大贷款需求（Max），银行（系统）仍然有办法（一个安全序列）让所有客户都能最终完成贷款（执行完毕）。
- 数据结构
Available(可用资源)：向量，表示当前每种资源有多少可用实例。- 示例:
Available = (3, 3, 2)(A有3个, B有3个, C有2个)。
- 示例:
Max(最大需求)：矩阵，表示总共需要多少 资源。 - 示例 (
): Max[0] = (7, 5, 3)。
- 示例 (
Allocation(已分配)：矩阵，表示当前已持有 资源。 - 示例 (
): Allocation[0] = (0, 1, 0)。
- 示例 (
Need(还需资源)：矩阵，表示还需多少 才能完成。 Need = Max - Allocation。示例 (
): Need[0] = (7, 5, 3) - (0, 1, 0) = (7, 4, 3)。
- 安全算法 (Safety Algorithm)
目的：检查当前系统状态是否安全。
步骤 1: 初始化
Work = Available，Finish[i] = false。- 示例:
Work = (3, 3, 2)。Finish = [F, F, F, F, F]。
- 示例:
步骤 2: 寻找一个进程
，满足 Finish[i] == false且Need[i] <= Work。示例 (第1轮):
? Need[0]=(7,4,3)(3,3,2)? 否。? Need[1]=(1,2,2)(3,3,2)? 是。
步骤 3: 找到
。模拟 执行完毕并释放资源。 Work = Work + Allocation[1]Work = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)Finish[1] = true。
步骤 2 (重复):
Work现在是(5, 3, 2)。? Need[0]=(7,4,3)(5,3,2)? 否。? Need[2]=(6,0,0)(5,3,2)? 否。? Need[3]=(0,1,1)(5,3,2)? 是。
步骤 3 (重复): 找到
。模拟 执行完毕并释放资源。 Work = Work + Allocation[3]Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)Finish[3] = true。
… (依此类推):
接下来，
Work = (7, 4, 3)，可以满足(Need=(7,4,3))。 Work变为(7, 5, 3)。接下来，
Work = (7, 5, 3)，可以满足(Need=(6,0,0))。 Work变为(10, 5, 5)。接下来，
Work = (10, 5, 5)，可以满足(Need=(4,3,1))。 Work变为(10, 5, 7)。
步骤 4: 检查
Finish数组是否全为true。示例:
Finish变为[T, T, T, T, T]。结论: 系统是安全的。安全序列之一为
。
- 资源请求算法 (Resource-Request Algorithm)
目的：当 Request_i 时，决定是否分配。
场景: 进程
请求 Request_1 = (1, 0, 2)。步骤 1: 检查请求是否超过最大需求：
Request_1(1,0,2)Need_1(1,2,2)? 是。继续。
步骤 2: 检查是否有足够可用资源：
Request_1(1,0,2)Available(3,3,2)? 是。继续。
步骤 3: 系统假装分配资源：
Available = (3,3,2) - (1,0,2) = (2, 3, 0)Allocation[1] = (2,0,0) + (1,0,2) = (3, 0, 2)Need[1] = (1,2,2) - (1,0,2) = (0, 2, 0)
步骤 4: 在这个新的假状态下，运行安全算法：
Work = (2, 3, 0)。检查发现，序列
仍然是一个安全序列。 结论: 因为假装分配后系统仍然安全，所以批准
的请求。如果（在另一个例子中）运行安全算法发现系统变为不安全，那么 必须等待，并且系统状态回滚到第3步之前。
(3) 死锁检测 (Deadlock Detection)
策略：允许系统进入不安全状态甚至死锁状态，但系统会周期性地运行检测算法来发现死锁。
等待图方法 (单实例资源)
节点是进程。
边
表示 正在等待 释放资源。 算法检测图中的环路。如果有环，就存在死锁。
检测算法 (多实例资源)
目的：检测当前系统状态是否已存在死锁。它与安全算法非常相似，但有关键区别：
安全算法检查
Need，看未来是否安全。检测算法检查
Request（当前请求），看现在是否已卡住。
算法步骤 (基于 PDF 第81-84页的例子)
初始化:
Work = Available，Finish[i] = false(如果持有资源)。 - 场景:
Available = (0, 0, 0)。Work = (0, 0, 0)。Finish = [F, F, F, F, F](因为到 都有 Allocation不为0)。
- 场景:
查找: 寻找一个进程
，满足 Finish[i] == false且Request[i] <= Work。示例:
? Request[0]=(0,0,0)Work(0,0,0)? 是。
模拟执行 (这就是你问的“为什么是加法”):
找到了
，意味着 不需要新资源就能执行完毕。 模拟
跑完并释放它持有的所有资源。 Work = Work + Allocation[0]。Work = (0, 0, 0) + (0, 1, 0) = (0, 1, 0)。Finish[0] = true。
重复查找:
Work现在是(0, 1, 0)。示例:
? Request[1]=(2,0,2)Work(0,1,0)? 否。? Request[2]=(0,0,1)Work(0,1,0)? 否。? Request[3]=(1,0,0)Work(0,1,0)? 否。? Request[4]=(0,0,2)$Work(0,1,0)? 否。
找不到任何可以执行的进程。
检查: 算法结束。检查
Finish数组。Finish[i] == false的是。 结论: 系统处于死锁状态，死锁的进程是
。
(4) 死锁恢复 (Recovery from Deadlock)
当检测到死锁后，系统必须打破它。
进程终止
终止所有死锁进程：最简单粗暴的方法。在我们的检测示例中，将
全部终止。 逐个终止进程：一次只终止一个进程，直到死锁环路被打破。选择终止谁，取决于：
进程的优先级。
进程已运行多久，还需多久。
进程占用了多少资源。
进程是交互式还是批处理。
资源抢占
选择牺牲者：选择一个进程（或资源）作为“牺牲者”，成本最低。
回滚 (Rollback)：将牺牲进程回滚到某个安全状态，并释放其资源。
饥饿 (Starvation)：必须防止同一个进程总是被选为牺牲者。
如果您喜欢我的文章，可以考虑打赏以支持我继续创作.
