408真题解析-2010-27-操作系统-同步互斥/Peterson算法
一 真题2010-27
2010-27. 进程 P₀ 和 P₁ 的共享变量定义及其初值为：
bool flag[2]; int turn = 0; flag[0] = FALSE; flag[1] = FALSE;若进程P₀ 和 P₁ 访问临界资源的类C伪代码实现如下：
voidP0(){// 进程 P0while(TRUE){flag[0]=TRUE;turn=1;while(flag[1]&&(turn==1));临界区;flag[0]=FALSE;}}voidP1(){// 进程 P1while(TRUE){flag[1]=TRUE;turn=0;while(flag[0]&&(turn==0));临界区;flag[1]=FALSE;}}则并发执行进程P₀ 和 P₁时产生的情形是（）。
A. 不能保证进程互斥进入临界区，会出现“饥饿”现象
B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象
C. 能保证进程互斥进入临界区，会出现“饥饿”现象
D. 能保证进程互斥进入临界区，不会出现“饥饿”现象
二 题目要素解析
核心考点：Peterson 算法（彼得森算法）的核心逻辑与特性，属于操作系统进程同步与互斥模块的核心考点，考查对经典临界区问题解决方案的互斥性、无饥饿性的判定，是 408 统考选择题的经典常考题型。
考查知识点
- Peterson 算法的实现原理：
flag数组（进程申请进入临界区的标志）与turn变量（进程 “谦让” 标志）的协同作用； - 临界区互斥性的判定：是否能保证任意时刻仅有一个进程进入临界区；
- “饥饿” 现象的判定：是否存在某进程长期无法进入临界区的情况。
题型特征：算法逻辑分析类选择题，侧重对经典同步算法执行流程的理解，无复杂计算，易因混淆flag和turn的作用而出错。
易错点
- 误判
turn变量的 “谦让” 逻辑，认为算法无法保证互斥； - 混淆 “饥饿” 的定义，误认为算法存在进程长期等待的情况；
- 忽略 Peterson 算法 “有界等待” 的核心特性，错误判定饥饿现象。
大纲 / 教材对应
- 408 考研大纲：操作系统 - 进程管理 - 进程同步 - 临界区问题、经典同步算法；
- 参考教材：《计算机操作系统（汤小丹）》第三章 进程管理 - 3.4 进程同步 - 3.4.1 临界区问题。
三 哔哔详解
本题解题核心是拆解 Peterson 算法的两大核心逻辑：先判定算法是否能保证临界区互斥，再分析是否存在饥饿现象，结合算法 “有界等待” 的特性得出结论。
前置概念铺垫
题干中的代码是Peterson 算法（解决两个进程临界区问题的经典算法），其核心是通过flag数组和turn变量的协同，同时满足临界区问题的三大准则（互斥、空闲让进、有界等待）：
flag[i]：表示进程Pi想要进入临界区（flag[i]=TRUE）或不想进入（flag[i]=FALSE）；turn：表示 “当前该哪个进程谦让”，若turn=j，则进程Pi需要谦让进程Pj，等待Pj退出临界区；- 核心等待条件：
while (flag[对方进程] && (turn == 对方进程编号))，仅当对方进程想进入临界区且当前该自己谦让时，才等待。
✅ 1. 是否能保证互斥？（Mutual Exclusion）
假设：P₀ 和 P₁ 同时尝试进入临界区。
P₀ 执行：
bool flag[2]; int turn = 0; flag[0] = FALSE; flag[1] = FALSE;P₁ 执行：
bool flag[2]; int turn = 0; flag[0] = FALSE; flag[1] = FALSE;
由于turn是共享变量，最后写入的值生效。分两种情况：
情况①：P₀ 先写turn=1，P₁ 后写turn=0
- P₀ 检查：
while(flag[1] && turn==1)→turn=0，条件为假 →P₀ 进入 - P₁ 检查：
while(flag[0] && turn==0)→flag[0]=TRUE且turn=0→ 条件为真 →P₁ 循环等待
情况②：P₁ 先写turn=0，P₀ 后写turn=1
- P₁ 检查：
while(flag[0] && turn==0)→turn=1，条件为假 →P₁ 进入 - P₀ 检查：
while(flag[1] && turn==1)→flag[1]=TRUE且turn=1→ 条件为真 →P₀ 循环等待
✅结论：无论执行顺序如何，最多只有一个进程能进入临界区→互斥成立
✅ 2. 是否会出现“饥饿”？（No Starvation）
“饥饿”指某个进程无限期无法进入临界区。
- Peterson 算法中，
turn变量起到轮流让步作用：- 当双方都准备就绪（
flag[0]=flag[1]=TRUE），只有turn指向的进程能进入 - 但每次退出临界区后，
flag[i] = FALSE，对方将不再受阻 - 下次再请求时，
turn会被重新设置，机会均等
- 当双方都准备就绪（
🔍关键机制：
- 若 P₀ 刚退出，P₁ 立即请求，则 P₁ 可直接进入（因
flag[0]=FALSE）- 若 P₁ 持续请求，P₀ 下次请求时也会因
turn轮转获得机会
✅结论：不会发生饥饿，满足有限等待（Bounded Waiting）
🔄 补充：Peterson 算法满足的三大性质
| 性质 | 是否满足 | 说明 |
|---|---|---|
| 互斥（Mutual Exclusion） | ✅ 是 | 任意时刻仅一个进程在临界区 |
| 前进（Progress） | ✅ 是 | 无进程在临界区时，有请求者必能进入 |
| 有限等待（Bounded Waiting） | ✅ 是 | 进程请求后，最多等待对方一次进入即可 |
💡因此，该算法是正确的双进程互斥解决方案
四 参考答案
D ✅
五 考点精析
5.1 Peterson 算法概念
一、基本概念
Peterson 算法是由 Gary L. Peterson 于 1981 年提出的一种纯软件实现的双进程互斥算法，用于解决两个并发进程对共享临界资源的互斥访问问题，无需依赖硬件原子指令（如 test-and-set）。
核心思想：
- “我准备好进入，但主动让对方先走”
- 通过意愿标志（flag） + 轮转变量（turn）实现公平互斥
算法结构（类 C 伪代码）：
// 共享变量bool flag[2]={FALSE,FALSE};intturn=0;// 进程 Pi (i = 0 或 1)voidPi(){while(TRUE){flag[i]=TRUE;// 表示“我想进入”turn=j;// j = 1 - i，表示“我让对方先走”while(flag[j]&&turn==j);// 等待：对方想进 且 轮到对方/* 临界区 */flag[i]=FALSE;// 退出临界区/* 剩余区 */}}二、性质与特征
| 性质 | 说明 | 是否满足 |
|---|---|---|
| 互斥性（Mutual Exclusion） | 任意时刻最多只有一个进程在临界区 | ✅ 满足 |
| 空闲让进（Progress） | 若临界区空闲，则有请求的进程能立即进入 | ✅ 满足 |
| 有界等待（Bounded Waiting） | 进程请求后，最多等待对方执行一次临界区即可进入 | ✅ 满足 |
| 无饥饿（No Starvation） | 所有进程最终都能进入临界区 | ✅ 满足 |
| 适用范围 | 仅适用于两个进程 | ⚠️ 局限性 |
| 实现方式 | 纯软件，无需特殊硬件支持 | ✅ 优势 |
| 原子性要求 | flag[i]=TRUE与turn=j必须视为逻辑原子（实际需内存屏障或顺序一致性保证） | ⚠️ 隐含前提 |
5.2 Peterson 算法的核心原理与三大准则（408 必背）
| 准则 | 算法实现逻辑 | 核心保证 |
|---|---|---|
| 互斥性 | 任意时刻，仅当满足以下任一条件时，进程才能进入临界区： • 对方未请求（ flag[对方] == FALSE）• 当前轮到自己（ turn ≠ 对方编号） | 任意时刻最多只有一个进程在临界区 |
| 空闲让进 | 若临界区空闲（即无进程在临界区内），则任何想进入的进程因flag[对方] == FALSE而不满足等待条件，可立即进入 | 临界区不会被闲置，提高资源利用率 |
| 有界等待 | turn变量由双方交替设置（P₀ 设turn=1，P₁ 设turn=0），确保等待进程最多等待对方执行一次临界区即可获得机会 | 无饥饿现象，等待时间存在明确上限 |
5.3 Peterson 算法的执行流程拆解（以 P0 为例）
voidP0(){while(TRUE){flag[0]=TRUE;// 1. P0声明“我想进临界区”turn=1;// 2. P0声明“我谦让P1，该P1优先”// 3. 等待条件：P1想进临界区 且 当前该P0谦让 → 才等待while(flag[1]&&(turn==1));临界区;// 4. 满足条件，进入临界区flag[0]=FALSE;// 5. 退出临界区，声明“我不想进了”}}步骤 1-2：进程先 “申请”，再 “谦让”，避免抢占；
步骤 3：核心等待逻辑，仅当对方也申请且自己需谦让时，才等待；
步骤 5：退出后释放标志，保证对方进程能进入。
5.4 “饥饿” 现象的核心判定规则（408 高频考点）
判定进程是否出现饥饿，需抓住“无限期等待”这一核心特征，常见场景对比：
| 场景 | 是否饥饿 | 原因说明 |
|---|---|---|
| Peterson 算法 | ❌ 无饥饿 | 满足有界等待：turn机制确保任一进程最多等待对方执行一次临界区即可进入 |
| 仅用 flag 数组的算法（无 turn） | ✅ 可能饥饿 | 若两进程同时设flag[i]=TRUE，会互相等待对方释放，导致死锁或无限等待 |
| 仅用 turn 变量的算法（无 flag） | ❌ 无饥饿 | 不会饥饿，但违反空闲让进：即使临界区空闲，若turn未指向自己，仍需等待 |
| 优先级倒置（低优先级占临界区） | ✅ 可能饥饿 | 高优先级进程因等待低优先级进程释放资源而阻塞；若中等优先级进程持续抢占 CPU，低优先级进程无法运行 →高优先级进程无限等待 |
5.5 Peterson 算法的扩展与局限性
- 优势：软件实现、无忙等（改进了整型信号量的忙等缺陷）、满足三大准则；
- 局限性：仅适用于两个进程的临界区问题，无法直接扩展到多个进程；
- 408 考点：需区分 Peterson 算法与其他临界区解决方案（如硬件指令、信号量）的异同。
5.6 典型考点
| 考点 | 说明 |
|---|---|
| Peterson 算法结构 | 必须记住：flag[i] = true; turn = j;while (flag[j] && turn == j); |
flag与turn的作用 | flag[i]：表示“我想要进入”turn：表示“我让对方先走” |
| 与硬件方案对比 | Peterson 是纯软件方案，无需特殊指令（如 test-and-set），但仅适用于双进程 |
| 常见误区 | 误认为turn决定优先级 → 实际是“让权”信号忽略flag的必要性 → 单独用turn无法保证互斥 |
| 408 命题趋势 | 近十年多次以代码形式考查经典同步算法（如 Peterson、生产者-消费者） |
5.7与其他互斥方案对比
| 方案 | 类型 | 是否需硬件 | 是否支持多进程 | 是否无饥饿 |
|---|---|---|---|---|
| Peterson 算法 | 软件 | ❌ 否 | ❌ 仅双进程 | ✅ 是 |
| Test-and-Set | 硬件 | ✅ 是 | ✅ 是 | ❌ 可能忙等/饥饿 |
| 信号量 | 软件+内核 | ✅（P/V 原子） | ✅ 是 | ✅（记录型） |
💡命题趋势：强调 Peterson 是唯一满足三大准则的纯软件双进程方案
5.8 易错点
| 错误认知 | 正确认知 |
|---|---|
“turn决定谁优先” | ❌turn是“让权”信号，不是优先级 |
| “Peterson 可用于多进程” | ❌ 仅适用于两个进程（扩展复杂且低效） |
| “该算法完全无需硬件支持” | ⚠️ 需要顺序一致性内存模型，否则可能失效（现代 CPU 需内存屏障） |
| “只要互斥就正确” | ❌ 还需满足空闲让进和有界等待 |
六 对应408考研大纲和考研参考教材知识点章节
| 考试模块 | 408 考研大纲要求 | 《计算机操作系统》（汤小丹 第4版） | 《操作系统概念》（Silberschatz 中文版） | 王道 / 天勤考研辅导书 |
|---|---|---|---|---|
| 操作系统 → 进程管理 → 进程同步 → 临界区问题 | 理解临界区问题的基本结构（临界区、进入区、退出区、剩余区）； 掌握同步机制的三大准则： • 互斥（Mutual Exclusion） • 空闲让进（Progress） • 有界等待（Bounded Waiting）； 掌握经典解决方案：Peterson 算法（双进程软件互斥） | 第三章 进程管理 3.4 进程同步 ├─ 3.4.1 临界区问题 └─ 3.4.2 同步机制应遵循的原则 （注：部分版本将 Peterson 算法置于 3.5.2 节） | 第 5 章 进程同步 5.1 临界区问题 └─ 5.1.2 Peterson 解决方案 | 第二章 处理机管理 2.4 进程同步 ├─ 2.4.1 临界区问题与同步准则 └─ 2.4.2 软件实现互斥：Peterson 算法 |
七 考点跟踪
| 年份 | 题号 | 考查内容 | CSDN 参考链接 | VX参考链接 |
|---|---|---|---|---|
| 2010 | 第27题 | Peterson 算法 | ||
| 2016 | 第27题 | TEST AND SET LOCK算法 | ||
| 2018 | 第32题 | Peterson 算法 | ||
| 2021 | 第45题 | 同步互斥 | ||
| 2023 | 第45题 | 同步互斥 |
说明：本文内容基于公开资料整理，参考了包括但不限于《数据结构》（严蔚敏）、《计算机操作系统》（汤小丹）、《计算机网络》（谢希仁）、《计算机组成原理》（唐朔飞）等国内高校经典教材，以及其他国际权威著作。同时，借鉴了王道、天勤、启航等机构出版的计算机专业考研辅导系列丛书中的知识体系框架与典型题型分析思路。文中所有观点、例题解析及文字表述均为作者结合自身理解进行的归纳与重述，未直接复制任何出版物原文。内容仅用于学习交流，若有引用不当或疏漏之处，敬请指正。