考研全科复习

Appearance

408 ​

操作系统 ​

实现互斥的方法（软件/硬件） ​

一、定位信息 ​

  • 所属圈层：核心层
  • 前置知识：了解同步与互斥的基本概念和临界区四原则（OS-02-09）
  • 知识网络位置：本单元介绍互斥的软件和硬件实现方法，是信号量机制（OS-02-11）的前置知识。Peterson算法是经典的软件互斥方案
  • 考点热度等级：H级（高频重点）——Peterson算法和硬件方法是408高频考点

二、知识点讲解 ​

2.1 软件实现方法 ​

单标志法 ​
  • 思路：用一个公共变量 turn 表示"轮到谁进入临界区"
  • 问题：违反"空闲让进"——如果 turn=0 但P0不想进入，P1即使想进入也必须等待
双标志先检查法 ​
  • 思路：每个进程设置一个标志 flag[i] 表示"我想进入临界区"，先检查对方标志再设置自己的
  • 问题：违反"忙则等待"——检查和设置之间可能被打断，两个进程同时进入临界区
双标志后检查法 ​
  • 思路：先设置自己的标志，再检查对方标志
  • 问题：可能导致双方都无法进入——都设置了标志，都在等对方退出
Peterson算法 ​

核心思想：结合"意愿标志"和"谦让变量"，主动谦让。

c
// 进程Pi (i=0或1, j=1-i)
flag[i] = true;    // 我想进入
turn = j;          // 谦让给对方
while (flag[j] && turn == j);  // 对方想进入且对方优先级高，则等待
// 临界区
flag[i] = false;   // 退出临界区
  • 满足全部四个原则：空闲让进、忙则等待、有限等待、让权等待（忙等待版本不满足让权等待）
  • 关键理解：turn 变量保证了"最后一刻的谦让者"必须等待

2.2 硬件实现方法 ​

中断屏蔽法 ​
  • 思路：进入临界区前关中断，退出后开中断
  • 优点：简单有效
  • 缺点：
    • 只适用于单处理器系统
    • 关中断时间过长会影响系统效率
    • 不适用于用户进程（关中断是特权指令）
硬件指令法（TestAndSet / Swap） ​

TestAndSet（TSL）指令：

c
boolean TestAndSet(boolean *lock) {
    boolean old = *lock;
    *lock = true;
    return old;
}
// 使用
while (TestAndSet(&lock));  // 忙等待
// 临界区
lock = false;

Swap（XCHG）指令：

c
void Swap(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}
// 使用
key = true;
do {
    Swap(&lock, &key);
} while (key);  // 忙等待
// 临界区
lock = false;
  • 优点：适用于多处理器系统，实现简单
  • 缺点：不满足"让权等待"（忙等待），可能导致饥饿

2.3 各方法对比表 ​

方法类型满足四原则多处理器优点缺点
单标志法软件否（缺空闲让进）是简单不实用
双标志先检查软件否（缺忙则等待）是简单有竞态条件
双标志后检查软件否（可能死锁）是简单双方可能都无法进入
Peterson算法软件是（忙等待版不满足让权等待）是完整互斥忙等待
中断屏蔽硬件是否简单高效仅限单处理器
TSL/Swap硬件否（缺让权等待）是简单可靠忙等待，可能饥饿

三、记忆与理解辅助 ​

  1. Peterson算法口诀："设标志→谦让→检查对方→进入"，核心是 turn 变量的谦让机制
  2. 硬件方法一句话："关中断最简单但只限单核，TSL/Swap多核也能用但要忙等"
  3. 软件方法演进：单标志→双标志先检查→双标志后检查→Peterson，逐步解决前一种的缺陷

四、例题与精解 ​

例题1（基础巩固） ​

题目：Peterson算法中，turn 变量的作用是（ ）

A. 记录哪个进程在临界区中 B. 当两个进程同时想进入时，决定谁优先 C. 记录临界区是否空闲 D. 记录进程的执行次数

命题意图：考查Peterson算法的核心机制。

精解：

  1. 审题分析：需要理解Peterson算法中 turn 的作用
  2. 解题思路：turn 是谦让变量，表示"我让给谁"
  3. 完整步骤：
    • 每个进程先设置 flag[i]=true 表示想进入，再设置 turn=j 表示谦让给对方
    • 如果两个进程都想进入（flag[0]=flag[1]=true），turn 决定了谁优先——turn 指向的进程需要等待
    • 这保证了不会出现两个进程同时进入临界区的情况
    • A选项错误（记录在临界区中的是 flag 标志），C选项错误，D选项错误
  4. 方法反思：turn 的本质是"最后一刻的谦让者必须等待"，解决了双标志后检查法的死锁问题

答案：B

例题2（中等提升） ​

题目：以下互斥实现方法中，能在多处理器系统中使用的是（ ）

A. 中断屏蔽法 B. Peterson算法 C. TestAndSet指令 D. 单标志法

命题意图：考查各种互斥方法的适用范围。

精解：

  1. 审题分析：需要判断哪些方法适用于多处理器系统
  2. 解题思路：中断屏蔽法只在单处理器有效（关中断无法阻止其他CPU执行），软件方法和硬件指令方法可以在多处理器使用
  3. 完整步骤：
    • A选项：中断屏蔽法只适用于单处理器系统。在多处理器中，关中断只影响当前CPU，其他CPU仍可进入临界区
    • B选项：Peterson算法适用于多处理器（但需要保证内存操作的原子性）
    • C选项：TestAndSet是硬件原子指令，适用于多处理器系统
    • D选项：单标志法虽然理论上可用于多处理器，但本身有缺陷不实用
    • 题目问"能使用"，B和C都可以，但C（TSL）是最典型的多处理器互斥方案
  4. 方法反思：多处理器互斥需要硬件支持（原子指令）或特殊的软件算法，单纯的中断屏蔽不够

答案：C（若单选则选C，若多选则B、C都对）

五、考情分析 ​

  • 考查频次：近5年约3–4次
  • 常见题型：选择题
  • 分值占比：2分/题
  • 命题趋势：Peterson算法的执行过程分析是高频考点，硬件方法（TSL/Swap）的原理也常考

六、易错点提醒 ​

  1. 错误表现：认为Peterson算法完全满足"让权等待" 错误原因：忙等待版本的Peterson算法不满足让权等待 正确理解：标准Peterson算法使用忙等待（while 循环），不满足让权等待。需要配合信号量等机制才能实现让权等待

  2. 错误表现：认为中断屏蔽法可以在多处理器系统中使用 错误原因：忽略了多处理器的独立中断机制 正确理解：关中断只影响当前CPU，其他CPU仍可执行临界区代码，因此中断屏蔽法不适用于多处理器

  3. 错误表现：混淆TSL指令和普通 if 检查 错误原因：不理解原子操作的概念 正确理解：TSL是一条原子硬件指令，"测试"和"设置"在一条指令中完成，不会被中断。普通 if 检查不是原子的

  4. 错误表现：认为Peterson算法只能用于两个进程 错误原因：标准教材只展示两个进程的版本 正确理解：Peterson算法可以扩展到N个进程（如Bakery算法），但两个进程版本最常考

七、来源标注 ​

  • 依据2026考研统考408大纲
  • 依据《计算机操作系统》（汤小丹/汤子瀛版）第2章
  • 依据《操作系统概念》（Silberschatz版）第6章

考研全科复习资料 - 基于2026考研统考大纲

仅供学习参考