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