第二章 03同步与互斥（王道）

一、进程同步和进程互斥的概念

核心概念：介绍进程同步和进程互斥的基本定义及其相互关系

1.1 什么是进程同步？

• 异步性定义：各并发执行的进程以各自独立的、不可预知的速度向前推进
• 同步必要性：当进程间需要协调工作时，必须解决异步性带来的执行顺序不确定问题

• 典型场景：写进程和读进程并发执行
• 同步要求：必须保证”写数据”操作在”读数据”操作之前完成
• 同步定义：又称直接制约关系，指进程间需要协调工作次序的合作关系

1.2 什么是进程互斥？

• 互斥共享：一个时间段内只允许一个进程访问（如打印机）
• 同时共享：宏观上允许多个进程同时访问（微观上交替访问）

1.3 进程互斥访问的四个组成部分

临界资源的定义

• 定义：一次仅允许一个进程使用的系统资源
• 典型示例：打印机、摄像头等硬件设备，以及某些共享内存区域

对临界资源的互斥访问

• 四个逻辑部分：
  • 进入区：检查并上锁（设置访问标志）
  • 临界区：实际访问临界资源的代码段（又称临界段）
  • 退出区：解锁（清除访问标志）
  • 剩余区：其他处理代码
• 易混淆点：注意区分进入区（检查上锁）和临界区（实际访问）的功能差异

1.4 进程互斥的原则

• 四大原则：
  • 空闲让进：临界区空闲时应立即允许一个进程进入
  • 忙则等待：临界区被占用时其他进程必须等待
  • 有限等待：等待时间必须是有限的（防止饥饿）
  • 让权等待：无法进入时应释放处理机（防止忙等）

1.5 知识回顾

• 概念对比：
  • 同步（直接制约）：进程间有直接合作关系
  • 互斥（间接制约）：进程间因共享资源产生制约
• 关键记忆点：
  • 临界区访问的四个逻辑部分及其功能
  • 互斥访问的四个原则（空闲让进、忙则等待、有限等待、让权等待）

二、进程互斥的软件实现方式(高频考点)

进程互斥的软件实现方法包括单标制法、双标志先检查法、双标志后检查法和皮特森算法。其中，单标制法用变量表示谦让，双标志法用数组表示进入意愿，皮特森算法结合两者，通过主动争取和谦让实现互斥。这些算法各有优缺点，需理解其背后的逻辑和原理，并结合课后习题巩固。

2.1 如果没有进程互斥？

1.进程互斥的定义：确保多个进程在访问共享资源时不会相互干扰。

2.缺乏进程互斥的后果：可能导致数据不一致或其他错误。

3.进程互斥的实现方法：通过软件或硬件实现。

2.2 单标志法

1.算法思想：通过设置一个turn变量，表示当前允许哪个进程进入临界区。

2.算法步骤：每个进程在进入区检查turn的值，如果不等于自己的编号，则等待。

3.例子：通过谦让的方式，一个进程在退出区将turn的值设为另一个进程的编号。

4.缺点：只能轮流使用临界区，违反空闲让进原则。

2.3 双标志先检查法

1.算法思想：通过设置一个flag数组，标记各个进程是否想要进入临界区。

2.算法步骤：每个进程在进入区检查对方是否想要进入临界区，如果对方不想进入，则自己进入。

3.例子：通过上锁和解锁的方式，表示自己想要使用临界区的意愿。

4.缺点：在并发环境下可能违反忙则等待原则。

2.4 双标志后检查法

1.算法思想：先进行上锁操作，再进行检查操作。

2.算法步骤：每个进程在进入区先上锁，再检查对方是否想要进入临界区。

3.例子：通过上锁和解锁的方式，表示自己想要使用临界区的意愿。

4.缺点：可能违反空闲让进和有限等待原则。

2.5 Peterson 算法

1.算法思想：结合双标志法和单标志法的核心思想。

2.算法步骤：每个进程在进入区表达自己想要进入临界区的意愿，并进行谦让。

3.例子：通过谦让的方式，确保只有一个进程能够进入临界区。

4.优点：实现了空闲让进、忙着等待和有限等待原则。

5.缺点：没有遵循让权等待原则。

2.6 知识回顾

进程互斥软件实现方法重点要点分析

一、核心概念与重要性

1.1 互斥的必要性

• 问题背景：多个进程并发访问同一临界资源时，可能导致资源使用冲突
• 典型例子：两个进程同时使用打印机，导致打印内容混乱
• 解决目标：确保同一时刻只有一个进程能访问临界资源

1.2 考察重点

• 考试频率：非常高，经常出现在选择题和大题中
• 学习要求：
  • 理解各种算法的思想和原理
  • 掌握进入区、临界区、退出区的代码逻辑
  • 分析每种算法的优缺点
  • 结合互斥实现的四个原则进行评价

二、互斥实现的四个原则

2.1 空闲让进

• 当临界区空闲时，应允许想要进入的进程立即进入

2.2 忙则等待

• 当临界区被占用时，其他进程必须等待

2.3 有限等待

• 等待进程不能无限期等待，必须在有限时间内获得访问权

2.4 让权等待

• 等待的进程应释放CPU资源，不应占用CPU进行忙等

三、四种软件实现算法详解

3.1 单标志法（Single Flag Method）

核心思想

• 设置变量turn表示当前允许哪个进程进入临界区
• 进程访问完临界区后，将使用权转交给另一个进程

实现机制

进入区：while(turn != 自己的编号); // 检查是否轮到自己
临界区：// 访问临界资源
退出区：turn = 对方编号; // 谦让给对方
剩余区：// 其他处理

优点

• 可以实现互斥访问
• 逻辑简单清晰

缺点

• 违反空闲让进原则：必须轮流使用，即使对方不需要使用资源
• 缺乏灵活性

3.2 双标志先检查法（Double Flag Check-First Method）

核心思想

• 设置布尔数组flag[]标记各进程是否想要进入临界区
• 先检查对方是否想要进入，再表达自己的意愿

实现机制

进入区：
  while(flag[对方] == true); // 检查对方是否想要进入
  flag[自己] = true; // 表达自己想要进入的意愿
临界区：// 访问临界资源  
退出区：flag[自己] = false; // 表示不再需要访问

优点

• 思路合理：先检查后上锁

缺点

• 违反忙则等待原则：可能导致两个进程同时进入临界区
• 根本问题：检查和上锁两个动作不能一气呵成，中间可能发生进程切换

3.3 双标志后检查法（Double Flag Check-Last Method）

核心思想

• 与先检查法类似，但改为先上锁再检查

实现机制

进入区：
  flag[自己] = true; // 先表达自己想要进入的意愿
  while(flag[对方] == true); // 再检查对方是否想要进入
临界区：// 访问临界资源
退出区：flag[自己] = false; // 表示不再需要访问

优点

• 解决了忙则等待问题，不会有两个进程同时进入临界区

缺点

• 违反空闲让进原则：可能导致两个进程都无法进入临界区
• 违反有限等待原则：可能导致进程无限等待，产生饥饿现象

3.4 皮特森算法（Peterson’s Algorithm）

核心思想

• 结合双标志法和单标志法的精髓
• 每个进程既表达进入意愿，又主动谦让

实现机制

进入区：
  flag[自己] = true; // 表达想要进入的意愿
  turn = 对方编号; // 主动谦让，让对方优先
  while(flag[对方] == true && turn == 对方编号); // 检查条件
临界区：// 访问临界资源
退出区：flag[自己] = false; // 表示不再需要访问

算法逻辑分析

1. 主动争取：表达自己想要进入临界区的意愿
2. 主动谦让：表示愿意让对方先进入（类似说客气话）
3. 条件检查：检查对方是否也想要使用，且最后是否是自己说了”客气话”

优点

• 满足空闲让进：临界区空闲时，想要进入的进程可以进入
• 满足忙则等待：不会有两个进程同时进入临界区
• 满足有限等待：等待时间有限，不会无限等待

缺点

• 违反让权等待原则：等待进程仍占用CPU进行忙等（while循环）

四、算法核心思想总结

4.1 两个核心概念

1. 谦让：通过turn变量实现进程间的相互谦让
2. 表达意愿：通过flag数组表达进程想要进入临界区的意愿

4.2 生活化理解

• 可以用”排队使用马桶”的例子来理解
• 皮特森算法类似于”有礼貌的排队”：既表达需求，又主动谦让
• “最后说客气话的人失去优先权”这一原则很好地解释了算法逻辑

五、算法比较与评价

算法	空闲让进	忙则等待	有限等待	让权等待	主要问题
单标志法	❌	✅	✅	❌	必须轮流使用
双标志先检查法	✅	❌	✅	❌	可能同时进入
双标志后检查法	❌	✅	❌	❌	可能都无法进入
皮特森算法	✅	✅	✅	❌	忙等占用CPU

六、学习建议与解题技巧

6.1 学习方法

• 不要直接钻入代码细节，要理解算法背后的逻辑
• 结合生活实例（如排队使用资源）来理解
• 重点掌握每种算法的核心思想

6.2 解题技巧

• 遇到软件实现互斥的题目，抓住”谦让”和”表达意愿”两个核心思想
• 分析算法时，要考虑并发执行的情况
• 结合四个原则来评价算法的优缺点

6.3 课后巩固

• 多做相关练习题
• 尝试分析不同执行顺序下的算法行为
• 理解为什么需要硬件支持来实现”检查和上锁”的原子性

七、与后续内容的联系

7.1 问题引出

• 皮特森算法虽然在逻辑上最完善，但仍有忙等的问题
• 双标志先检查法的思路是好的，但缺乏原子性支持

7.2 解决方向

• 下一节将学习硬件实现方法
• 硬件可以保证”检查和上锁”操作的原子性
• 这为解决软件方法的根本问题提供了基础

这些内容构成了操作系统进程同步与互斥的重要理论基础，是理解更高级同步机制的前提。

三、进程互斥的硬件实现方法

• 实现方式：包括中断屏蔽方法、TestAndSet(TS/TSL)指令和Swap(XCHG)指令三种
• 学习要点：需要理解各方法原理并掌握其优缺点

3.1 中断屏蔽方法

• 实现原理：通过”关中断”和”开中断”指令实现，与原语实现思想相同
  • 进程访问临界区前执行关中断指令，禁止中断和进程切换
  • 访问完成后执行开中断指令，允许其他进程访问
• 执行流程：关中断→临界区→开中断
• 优点：
  • 实现简单高效
  • 逻辑清晰
• 缺点：
  • 仅适用于单处理机系统（多处理机环境下无法保证互斥）
  • 需要特权指令（只能在操作系统内核态下运行）
  • 不适用于用户进程

3.2 TestAndSet 指令

• 别名：TS指令/TSL指令（TestAndSetLock）
• 硬件特性：由硬件实现，执行过程不可中断
• 实现逻辑：
  • 使用布尔型共享变量lock表示临界区状态（true表示已加锁）
  • 指令操作：记录原锁状态→设置新锁状态→返回原状态
  • 代码实现：
• 优点：
  • 实现简单
  • 适用于多处理机环境
  • 检查和上锁操作一气呵成（解决软件方法的问题）
• 缺点：
  • 不满足”让权等待”原则（进程会“忙等”）

3.3 Swap指令

• 别名：Exchange指令/XCHG指令
• 硬件特性：由硬件实现，执行过程不可中断
• 实现逻辑：
  • 交换两个变量的值
  • 代码实现：
• 与TS指令比较：
  • 逻辑功能相同（都是检查原状态并设置新锁）
  • 硬件实现方式不同
• 优缺点：
  • 同TS指令（实现简单、适用多处理机、但不满足让权等待）

3.4 知识总结

进程互斥硬件实现方法 – 考研复习要点

一、中断屏蔽方法

实现原理： 利用开中断和关中断两个指令 进程访问临界区前执行关中断指令，访问完毕后执行开中断指令 关中断期间，进程不可被中断，无法发生进程切换

优点： 实现简单高效 逻辑清晰

缺点：

1. 不适用于多处理机系统 关中断指令只对执行该指令的处理机有效 其他处理机仍可正常切换进程，可能同时访问临界区
2. 只能由内核进程使用 开关中断属于特权指令，需要在内核态下运行 用户进程无权限执行

二、TestAndSet指令（TSL指令）

实现原理：

bool TestAndSet(bool *lock) {
    bool old = *lock;    // 记录原值
    *lock = true;        // 设置锁定状态
    return old;          // 返回原值
}

硬件实现，不可被中断

使用方式：

while(TestAndSet(&lock));  // 循环检查直到获得锁
// 临界区代码
lock = false;              // 释放锁

特点： 检查和上锁操作一气呵成，不可被中断 解决了软件方法中检查和上锁分离的问题

三、Swap指令（Exchange指令）

实现原理：

void Swap(bool *a, bool *b) {
    bool temp = *a;
    *a = *b;
    *b = temp;
}

硬件实现，不可被中断

使用方式：

bool old = true;
do {
    Swap(&lock, &old);
} while(old);              // 循环直到old为false
// 临界区代码
lock = false;              // 释放锁

四、TSL和Swap指令对比

共同特点： 都是硬件实现，执行过程不可被中断 逻辑上实现相同功能：检查旧值并设置新值 优缺点相同

优点： 实现简单 适用于多处理机环境 硬件保证原子性操作

缺点： 不满足让权等待原则 进程在等待时会一直占用CPU进行”盲等” 造成处理机资源浪费

五、考试重点

名词理解： TSL指令 = TestAndSet指令 = TestAndSetLock指令 Swap指令 = Exchange指令 在408真题中可能出现不同表述方式

核心考点：

1. 各方法的实现原理和执行过程
2. 优缺点对比分析
3. 适用场景和限制条件
4. 硬件方法相比软件方法的优势
5. 让权等待原则的理解

记忆要点： 中断屏蔽：简单但限制多（单处理机+内核进程） TSL/Swap：硬件原子操作，解决竞态条件，但存在忙等问题 共同问题：都不满足让权等待，会造成CPU资源浪费

六、与软件方法的对比优势

硬件方法解决了软件方法中检查和上锁操作非原子性的根本问题： 软件方法：检查→上锁（两步操作，可能被中断） 硬件方法：检查+上锁（一步完成，不可被中断）

四、互斥锁（新考点）

4.1 互斥锁的概念

• 基本概念: 互斥锁(mutex lock)是实现进程互斥的最简单工具，通过布尔变量available表示锁状态（true/false或1/0）
• 操作函数:
  • acquire(): 获取锁
  • release(): 释放锁
• 原子性要求: 获取和释放锁的操作必须通过硬件机制保证原子性执行

4.2 锁的特性

• 忙等机制: 当锁不可用时，进程会在acquire()中循环检查（while(!available)），直到锁被释放
• 主要缺点:
  • 违反”让权等待”原则，持续占用CPU资源
  • 单处理机系统中尤其低效，等待期间不可能解锁
• 适用场景:
  • 多处理器系统优势：一个核忙等不影响其他核工作
  • 临界区操作时间短时效率更高（避免上下文切换开销）
• 自旋锁分类:
  • 包括TSL指令、swap指令、单标志法等实现方式
  • 共同特征：都需要忙等待检查锁状态
• 时间片机制:
  • 忙等进程仍受时间片限制，用完会被强制下处理机
  • 并非持续独占CPU资源
• 性能权衡:
  • 不切换上下文的优势：多核系统中若临界区操作快，总等待时间可能短于进程切换时间
  • 典型应用：内核数据结构保护等短时操作场景

4.3 总结

锁机制与自旋锁 – 考研复习要点

一、锁的基本概念

定义： 锁是用于实现互斥的一种方法 可以简单理解为一个布尔型变量 只有true和false（或0和1）两种状态 分别表示当前已上锁或没有上锁

基本操作：

acquire();  // 上锁，获得锁
release();  // 释放锁

二、用锁实现互斥的缺点

主要缺点： 盲等问题 – 如果进不了临界区，会不断while循环被卡住 导致CPU资源浪费 违反了让权等待原则

三、自旋锁的概念

定义： 由于盲等过程中需要不断循环检查，这一类锁称为自旋锁 自己在原地旋转，不断检查锁状态

包含的方法： TSL指令 Swap指令 单标志法 互斥锁

共同特点： 都用于解决进程互斥问题 都有盲等问题 都违反让权等待原则

四、盲等的时间片机制

重要说明： 进程在盲等时并不会一直占用处理机 如果进程时间片用完，调度程序依然会让它下处理机 盲等不等于永远占用处理机

五、自旋锁的优点

优势： 等待锁期间不需要切换进程上下文 进程上下文切换代价较大 在特定条件下，自旋等待代价反而很低

六、自旋锁的适用场景

多处理器系统中的优势： 条件：对临界区上锁时间很短 原理：

• 进程P1在一个核心自旋等待，只占用这一个核的计算能力
• 上锁的进程P2在另一个核心运行，可以快速使用临界区并解锁
• P1在自旋等待过程中能够快速发现解锁，立即进入临界区
• 没有进程切换，盲等代价很低
• 其他核可以照常工作

单处理机系统中的劣势： 问题：

• P1进程占用唯一一个核进行自旋等待
• 在当前时间片内不可能等到解锁
• 只有P1时间片用完，上锁进程上处理机并解锁后，P1才可能获得锁
• 自旋等待期间无法获得锁，纯属浪费

七、考试重点

核心概念：

1. 锁的基本定义和操作
2. 自旋锁的概念和特点
3. 盲等问题及其影响
4. 让权等待原则的违反

适用性分析：

1. 多处理器系统 vs 单处理机系统
2. 临界区上锁时间长短的影响
3. 进程上下文切换成本考量

记忆要点： 自旋锁 = 盲等 = 违反让权等待 多处理器 + 短临界区 = 自旋锁有优势 单处理机 = 自旋锁效率低 时间片机制仍然有效，不会无限占用处理机