• https://tingwu.aliyun.com/doc/transcripts/pev8qdb6xl2j9kga?sl=1# 《2-4 同步与互斥 720P》
• 《メモリ管理》

操作系统核心笔记：进程同步与互斥

在多道程序设计时代，进程的并发执行带来了极大的资源利用率提升，但同时也引入了非对称性与随机性。本篇笔记将围绕进程同步与互斥的核心概念、实现方案（软件/硬件/信号量）以及经典例题进行深度整理。

一、 同步与互斥的基本概念

1.1 并发执行下的“不可再现性”

在单道程序系统中，程序具有封闭性与可再现性（即初始条件相同，无论运行多少次，结果都完全相同）。 然而在并发环境下，多个进程共享系统资源，由于失去封闭性，并发执行的进程也将失去可再现性。

📌 【例题一】并发执行不确定性实例分析（经典 $counter$ 冲突）

【题目背景】 设有两个并发进程：生产者进程 $A$ 执行 counter++（即 $counter = counter + 1$），消费者进程 $B$ 执行 counter--（即 $counter = counter - 1$）。 在汇编或机器指令级别，这两个操作通常被拆分为三步：

• counter++ 拆分指令：

  • $I_1$: register1 = counter; (将变量读入寄存器)

  • $I_2$: register1 = register1 + 1; (寄存器自增)

  • $I_3$: counter = register1; (写回内存)

• counter-- 拆分指令：

  • $D_1$: register2 = counter; (将变量读入寄存器)

  • $D_2$: register2 = register2 - 1; (寄存器自减)

  • $D_3$: counter = register2; (写回内存)

假设 $counter$ 初始值为 $2$，试分析在没有任何保护措施的情况下，若按照以下交错时序并发执行，最终 $counter$ 的值是多少？

【执行时序】

1. 进程 $A$ 执行 $I_1$

2. 进程 $A$ 执行 $I_2$

3. 进程 $B$ 执行 $D_1$

4. 进程 $B$ 执行 $D_2$

5. 进程 $A$ 执行 $I_3$

6. 进程 $B$ 执行 $D_3$

【详细解析与步骤追踪】

• 步骤 1 ($I_1$): 进程 $A$ 将 $counter$ ($2$) 读入其专用寄存器 register1。此时 register1 = 2。

• 步骤 2 ($I_2$): 进程 $A$ 计算 register1 + 1 并存回寄存器。此时 register1 = 3。(注意：此时尚未写回内存 $counter$)。

• 步骤 3 ($D_1$): 此时发生进程调度，切换至进程 $B$。$B$ 将当前的 $counter$ ($2$) 读入 register2。此时 register2 = 2。

• 步骤 4 ($D_2$): 进程 $B$ 计算 register2 - 1 并存回寄存器。此时 register2 = 1。(注意：此时尚未写回内存 $counter$)。

• 步骤 5 ($I_3$): 进程调度回进程 $A$。$A$ 执行写回指令，将 register1 ($3$) 赋给 $counter$。此时内存中 $counter = 3$。

• 步骤 6 ($D_3$): 进程 $B$ 获得 CPU，执行写回指令，将 register2 ($1$) 赋给 $counter$。此时内存中 $counter = 1$。

【结论与答案】 经过一加一减，正常逻辑下 $counter$ 应保持为 $2$。但由于并发冲突导致进程 $A$ 的写回结果被进程 $B$ 覆盖，最终 $counter = 1$。 若时序改变，结果亦可能为 $3$。这就是并发的不可再现性。要解决该问题，必须对共享变量（即临界资源）实施互斥访问保护。

1.2 临界资源与临界区

• 临界资源 (Critical Resource)： 在一段时间内只允许一个进程访问的资源（如：打印机、共享变量 $counter$、共享缓冲区）。

• 临界区 (Critical Section)： 每个进程中访问临界资源的那段代码。

虽然进程并发执行，但对临界区的访问必须是互斥的。进程在代码结构上通常分为四个部分：

while(TRUE) {
    进入区 (Entry Section);      // 检查临界资源是否正被访问，若无则上锁，准备进入
    临界区 (Critical Section);   // 访问临界资源的代码段（独占执行）
    退出区 (Exit Section);       // 释放锁，将临界资源正被访问的标志恢复
    剩余区 (Remainder Section);  // 与临界资源无关的其他代码段
};

1.3 同步与互斥的关系

1. 同步关系（直接制约关系）： * 概念： 协调多个并发进程的执行顺序。源于进程间的合作。

   • 手写笔记妙喻： “同步：二者间有缓冲区”。

   • 经典场景： 生产者进程 $A$ 与计算进程 $B$ 共享缓冲区。当缓冲区满时，$A$ 必须阻塞等待；当缓冲区空时，$B$ 必须阻塞等待。$B$ 的读取行为必须发生在 $A$ 的写入行为之后（强次序性）。

2. 互斥关系（间接制约关系）：

   • 概念： 保证多个并发进程不能同时进入临界区访问同一临界资源。源于资源共享。

   • 经典场景： 两个进程竞争同一台打印机，一个进程在使用时，另一个必须在临界区外等待。

1.4 同步机制遵循的四条原则 (Dijkstra 准则)

为了设计出安全、高效的同步机制，必须严格遵守以下四条基本原则：

1. 空闲让进： 当临界区空闲时，应允许一个请求进入临界区的进程立即进入，以有效利用资源。

2. 忙则等待： 当已有进程进入临界区时，其他试图进入的进程必须等待，以保证对资源的互斥访问。

3. 有限等待： 对要求访问临界资源的进程，应保证其在有限时间内能进入临界区，避免陷入“死等”（无休止等待）状态。

4. 让权等待： 当进程不能进入临界区时，应立即释放处理机（CPU），以免进程陷入“忙等”（占着 CPU 却只做无用检查）状态。

二、 软件同步机制的演进历程

在不借助硬件和特殊指令的条件下，纯靠编写软件算法来解决互斥问题。这一演进过程极具启发性。

2.1 单标志法 (轮流轮换法)

• 核心思想： 设置一个整型公用变量 turn，指示允许进入临界区的进程编号。例如 turn = 0 允许 $P_0$ 进入；turn = 1 允许 $P_1$ 进入。

• 算法代码：

// 进程 P0
while (turn != 0); // 进入区：忙等
critical section;  // 临界区
turn = 1;          // 退出区：将使用权赋予对方
remainder section; // 剩余区

// 进程 P1
while (turn != 1); // 进入区：忙等
critical section;  // 临界区
turn = 0;          // 退出区：将使用权赋予对方
remainder section; // 剩余区

• 缺陷分析： 违背了“空闲让进”原则。

  • 手写笔记痛点： “两个必须交替进入。无法闲时进入。”

  • 场景推演： 假设初始 turn = 0，$P_0$ 先进入临界区并安全退出，将 turn 设为 $1$。此时 $P_0$ 进入剩余区去“吃麦当劳”（不再想进临界区）。

  • 若此时 $P_1$ 也无进入临界区需求，临界区实际上完全空闲。

  • 但如果 $P_0$ 突然想再次进入临界区，它会被卡在 while(turn != 0)。因为 $P_1$ 始终没有进去并修改 turn 为 $0$。临界区明明空闲，$P_0$ 却无法进入。

2.2 双标志先检查法

• 核心思想： 设置一个布尔型数组 flag[2]。flag[i] = true 表示进程 $P_i$ 想要进入临界区。每个进程在进入前先检查对方的意愿，若对方不想进，则自己设为 true 后进入。

• 手写笔记妙喻： “可以修改对方的红绿灯”。对方的标志就是自己的红绿灯（flag[j] 为 true 代表红灯，自己必须等待）。

• 算法代码：

// 进程 Pi
while (flag[j]);   // 进入区：检查对方是否想进。若想，则循环等待（先检查）
flag[i] = true;    // 进入区：标志自己想进（踩红线改红绿灯）
critical section;  // 临界区
flag[i] = false;   // 退出区：标志自己不想进了
remainder section; // 剩余区

• 缺陷分析： 违背了“忙则等待”原则。

  • 手写笔记痛点： “无法互斥”。

  • 原因： “先检查”和“后设置”这两个操作无法一气呵成（非原子操作）。

  • 场景推演： 初始 flag[0] = flag[1] = false。

    1. $P_0$ 检查 flag[1]，发现为 false，准备往下执行。

    2. 就在此时，发生进程切换，CPU 调度给 $P_1$。

    3. $P_1$ 检查 flag[0]，也发现为 false，亦准备往下执行。

    4. 结果：两个进程都通过了 while 检查，随后分别将自己的 flag 设为 true，并同时进入临界区。互斥防线彻底崩溃！

2.3 双标志后检查法

• 核心思想： 既然“先检查后设置”会导致同时进入，那我们改变策略：“先踩线改红绿灯（先设置），再观察自己的红绿灯（后检查）”。

• 算法代码：

// 进程 Pi
flag[i] = true;    // 进入区：先设自己想进
while (flag[j]);   // 进入区：后检查对方是否也想进。若想，则等待
critical section;  // 临界区
flag[i] = false;   // 退出区：置为不进
remainder section; // 剩余区

• 缺陷分析： 违背了“有限等待”原则，会导致“饥饿”或死锁。

  • 手写笔记痛点： “先修改，再检查。导致饥饿。”

  • 场景推演： 初始 flag[0] = flag[1] = false。

    1. $P_0$ 先将 flag[0] = true（表明自己要进）。

    2. 此时发生进程切换，$P_1$ 获得 CPU，也将 flag[1] = true（表明自己也要进）。

    3. 接下来，不管调度谁执行，都会卡在各自的检查语句（$P_0$ 卡在 while(flag[1])，$P_1$ 卡在 while(flag[0])）。

    4. 两个进程互不相让，都卡在临界区外疯狂忙等，陷入死锁，产生“饥饿”现象。

2.4 皮特森算法 (Peterson’s Algorithm)

皮特森算法是纯软件互斥方案的集大成者，它用一种极其巧妙的方式解决了上述所有互斥算法的缺陷。

• 手写笔记妙喻： “红绿灯 + 公告牌”。

  • flag[i] 是红绿灯：用来表示进程 $P_i$ 有没有通过这个路口的意愿。

  • turn 是公告牌：用来进行谦让（单标志法）。在同时有强意愿进入时，公告牌上的编号是谁，谁就拥有通行权。

• 算法代码：

// 进程 P0
flag[0] = true;                     // 1. 设置自己的红绿灯为红（表达进入意愿）
turn = 1;                           // 2. 谦让：主动将公告牌设为对方的通道号（你先请）
while (flag[1] && turn == 1);       // 3. 检查：只有当对方“想进”且公告牌依然指着“对方”时，我才等待。
critical section;                   // 临界区
flag[0] = false;                    // 退出区：释放意愿
remainder section;

// 进程 P1
flag[1] = true;                     // 1. 表达意愿
turn = 0;                           // 2. 谦让：你先请
while (flag[0] && turn == 0);       // 3. 检查
critical section;                   // 临界区
flag[1] = false;                    // 退出区
remainder section;

📌 【例题二】Peterson 算法互斥性证明与分析

【题目】 试证明：当 $P_0$ 和 $P_1$ 两个进程同时尝试进入临界区时，Peterson 算法能够确保它们的互斥。

【证明步骤】

1. 假设反证法： 假设 $P_0$ 和 $P_1$ 能够同时进入临界区。

2. 若 $P_0$ 在临界区，说明 $P_0$ 跳出了 while 循环。跳出条件为：

   $\neg (flag[1] \land turn 1) \implies (flag[1] false) \lor (turn == 0)$

3. 若 $P_1$ 在临界区，说明 $P_1$ 跳出了 while 循环。跳出条件为：

   $\neg (flag[0] \land turn 0) \implies (flag[0] false) \lor (turn == 1)$

4. 由于双方都在全力争取进入临界区，所以 flag[0] == true 且 flag[1] == true。

5. 因此，要让双方都在临界区，必须满足：

   $(turn 0) \land (turn 1)$

6. 然而，turn 是一个单一的共享整型变量，在任何时刻都不可能既等于 0 又等于 1。

7. 因此，假设不成立。Peterson 算法成功实现了互斥。

• 缺陷： * 虽然 Peterson 完美解决了空闲让进、忙则等待、有限等待。

  • 但它依然没有解决“让权等待”原则。当进程无法进入临界区时，它会在 while 循环中一直耗费 CPU 时间进行忙等。

三、 硬件同步机制

纯软件方案实现繁琐、理解成本高，且存在忙等开销。为此，计算机设计了特殊的硬件指令来支撑互斥。

3.1 关中断 (Disable Interrupts)

• 核心思想： 进程进入临界区前关闭中断，退出临界区后打开中断。

• 手写笔记总结： * “有进程在临界区执行期间，计算机系统关中断，从而不会引发调度，也就不会有进程或线程切换”。

• 缺点：

  1. 滥用特权后果严重： 关中断是一条高特权指令，如果允许用户程序调用，若程序在临界区内死循环，系统将直接卡死。

  2. 多 CPU 系统下失效： 关中断只能对当前执行指令的单个 CPU 核心有效，其他 CPU 核心上的进程仍能同时访问相同代码，无法提供多核互斥。

  3. 影响系统效率： 关中断会延迟紧急中断（如时钟中断、异常中断）的响应。

3.2 Test-and-Set 指令 (TS/TSL 指令)

• 手写笔记妙喻： “Test-and-set 指令就是上锁”。

• 核心思想： TSL 是一条原子性的硬件指令（硬件保证其执行过程不可被打断）。它测试并设置一个全局布尔变量 lock（代表一把锁）。

• TSL 原理仿真代码：

// 硬件指令的模拟实现（不可拆分，不可中断）
boolean TS(boolean *lock) {
    boolean old = *lock;  // 1. 记下原锁状态（FALSE表示空闲，TRUE表示上锁）
    *lock = TRUE;         // 2. 无论原本锁状态如何，都给锁强行置为 TRUE (即上锁)
    return old;           // 3. 返回原锁状态
}

• 使用方式：

while (TS(&lock));   // 进入区：如果原来是TRUE（已被上锁），则返回TRUE，陷入循环等待。
                     //       如果原来是FALSE（空闲），返回FALSE，跳出循环，且在TS内部悄悄锁上了！
critical section;    // 临界区
lock = FALSE;        // 退出区：解锁
remainder section;

3.3 Swap 指令 (交换指令)

• 核心思想： 原子性交换两个字的内容。

• 原理仿真代码与使用方式：

// 硬件交换指令
void swap(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}

// 使用方式
key = TRUE;
do {
    swap(&lock, &key); // 不断用自己的 TRUE (key) 去交换 lock 的值
} while (key != FALSE); // 只要交换出 FALSE，说明拿到了锁，锁变成了 key 里的 TRUE 即可进入
critical section;
lock = FALSE;          // 退出区：释放锁
remainder section;

• 硬件机制的共同缺陷：

  • 无论是 TS 还是 Swap，由于利用了 while 循环进行锁状态检测，都违背了“让权等待”原则。

  • 不能进入临界区的进程会陷入“忙等”，造成极大的 CPU 资源浪费。

四、 现代同步核心：信号量机制 (Semaphore)

为了彻底解决“忙等”和“让权等待”之间的矛盾，Dijkstra 提出了信号量机制。信号量从根本上避免了忙等。

4.1 整型信号量

• 定义： 定义一个整型量 $S$，用来表示某种资源的数目。

• 操作： 只有初始化、wait(S)（即 $P$ 操作）和 signal(S)（即 $V$ 操作）三种原子操作。

wait(S) {
    while (S <= 0);  // 资源不足时，依然只能在CPU里循环忙等
    S--;
}
signal(S) {
    S++;
}

• 缺陷： 依然存在“忙等”现象。

4.2 记录型信号量

• 手写笔记提炼： “增加个链表。（不存在忙等）”

• 核心思想： 当一个进程申请资源而资源不足时，信号量不会让它执行 while 忙等，而是通过 block 原语将其主动阻塞，并将其挂入等待该资源的进程队列 $L$ 中。当其他进程释放资源时，会通过 wakeup 原语唤醒队列中的一个进程。

• 数据结构定义：

typedef struct {
    int value;           // 资源计数器：代表某种物理资源的可用数目
    struct process *L;   // 进程等待链表：存放所有等待该资源的阻塞进程
} semaphore;

• $wait(S)$ / $P(S)$ 原子实现：

void wait(semaphore S) {
    S.value--;           // 1. 资源数自减一（申请资源）
    if (S.value < 0) {   // 2. 若自减后小于 0，说明原本没有资源，必须等待
        add this process to S.L; // 挂入等待队列
        block(S.L);      // 3. 自我阻塞，主动让出 CPU 核心（实现让权等待！）
    }
}

• $signal(S)$ / $V(S)$ 原子实现：

void signal(semaphore S) {
    S.value++;           // 1. 资源数自增一（释放资源）
    if (S.value <= 0) {  // 2. 自增后若仍然小于等于 0，说明队列里有进程在阻塞等待
        remove a process P from S.L; // 从链表中取出一个阻塞进程
        wakeup(P);       // 3. 唤醒它
    }
}

📌 【例题三】记录型信号量状态与值变化跟踪

【题目】 设有一个记录型信号量 $S$，初始值 $S.value = 1$（代表某种单一资源，如单通道打印机）。 当前有 3 个进程 $A, B, C$ 陆续发起对 $S$ 的操作。请写出在每一步操作后，$S.value$ 的具体数值以及等待队列 $S.L$ 的状态。

【详细步骤解析】

1. 初始状态： $S.value = 1$，等待链表 $S.L = \emptyset$。

2. 进程 $A$ 调用 $wait(S)$：

   • $S.value$ 自减 1，变为 $0$。

   • 判断 $S.value < 0$ 结果为 false。进程 $A$ 成功拿到资源，正常进入临界区。

   • 状态： $S.value = 0$，等待队列 $S.L = \emptyset$。

3. 进程 $B$ 调用 $wait(S)$：

   • $S.value$ 自减 1，变为 $-1$。

   • 判断 $S.value < 0$ 结果为 true。进程 $B$ 被放入队列 $S.L$，并执行 block 挂起。

   • 状态： $S.value = -1$，等待队列 $S.L = \{B\}$。

4. 进程 $C$ 调用 $wait(S)$：

   • $S.value$ 自减 1，变为 $-2$。

   • 判断 $S.value < 0$ 结果为 true。进程 $C$ 被放入队列 $S.L$，并执行 block 挂起。

   • 状态： $S.value = -2$，等待队列 $S.L = \{B, C\}$。

5. 进程 $A$ 运行完毕，调用 $signal(S)$：

   • $S.value$ 自增 1，由 $-2$ 变为 $-1$。

   • 判断 $S.value \le 0$ 结果为 true（表明有阻塞进程）。

   • 从队列 $S.L$ 取出排在最前面的进程 $B$，调用 wakeup(B)。

   • 状态： $S.value = -1$，等待队列 $S.L = \{C\}$。(此时 $B$ 已经就绪，开始在临界区执行)。

【关于 $S.value$ 含义的考研高频结论】

• 当 $S.value \ge 0$ 时，表示系统中可用资源的数目。

• 当 $S.value < 0$ 时，其绝对值 $|S.value|$ 表示由于无资源而处于阻塞等待队列中的进程数目。

4.3 信号量的经典应用场景

① 实现进程互斥 (Mutex)

• 实现步骤：

  1. 设一个互斥信号量 mutex，其初值为 $1$。

  2. 将临界区代码夹在 $P(mutex)$ 与 $V(mutex)$ 之间。

• 代码模版：

semaphore mutex = 1; // 只有一个进入名额

PA() {
    while(1) {
        wait(mutex);      // 申请进入权
        critical section; // 临界区
        signal(mutex);    // 归还进入权
        remainder section;
    }
}

PB() {
    while(1) {
        wait(mutex);      // 申请进入权
        critical section; // 临界区
        signal(mutex);    // 归还进入权
        remainder section;
    }
}

② 实现进程同步 (Synchronization)

• 实现步骤：

  1. 设置一个同步信号量 S，其初值为 $0$。

  2. 在需要先执行的语句后面调用 $V(S)$（即发出通知信号）。

  3. 在后执行的语句前面调用 $P(S)$（即等待信号，被动阻塞）。

• 手写笔记经典例题：先穿袜子再穿鞋

  • 要求： 必须等进程 $PC$ 先完成“穿袜子”后，进程 $PD$ 才能执行“穿鞋”。

semaphore S = 0; // 同步信号量，初始没有“穿袜子好”的信号

PC() {
    穿袜子;
    signal(S);  // V(S)：释放信号，S.value 变为 1
}

PD() {
    wait(S);    // P(S)：申请信号。若PC未执行，S.value此时为0，自减后为-1，PD主动自我阻塞
    穿鞋;        // 只有当 PC 执行完并发出 signal 唤醒 PD 后，PD 才能穿鞋
}

📌 【例题四】综合实战：生产者-消费者基础问题

【题目描述】 设有一个容量为 $1$ 的缓冲区，生产者进程不断生产数据并存入该缓冲区；消费者进程不断从缓冲区取走数据进行消费。试用记录型信号量机制实现两个进程的同步与互斥。

【思路剖析（起承转合）】

1. 互斥关系： 缓冲区是一块共享内存（临界资源），同一时刻只能允许一个进程访问。需要一个互斥信号量 $mutex = 1$。

2. 同步关系：

   • 当缓冲区空时，生产者可以放入数据，消费者不能取出数据（消费者等生产者放入）。设置同步信号量 $full = 0$（代表缓冲区中数据的数量）。

   • 当缓冲区满时，生产者不能放入数据，必须等消费者取走。设置同步信号量 $empty = 1$（代表缓冲区空位的数量，初始有 1 个空位）。

【代码设计】

semaphore mutex = 1;  // 互斥信号量：保护对缓冲区的独占式访问
semaphore empty = 1;  // 同步信号量：指示空位数
semaphore full = 0;   // 同步信号量：指示满位数

void producer() {
    while(1) {
        produce an item;   // 生产一个数据
        
        wait(empty);       // 1. 申请一个空位（由1变0）
        wait(mutex);       // 2. 锁定缓冲区
        
        buffer[in] = item; // 3. 将数据放入缓冲区
        
        signal(mutex);     // 4. 解锁缓冲区
        signal(full);      // 5. 释放一个“满”数据信号（由0变1，唤醒可能阻塞的消费者）
    }
}

void consumer() {
    while(1) {
        wait(full);        // 1. 申请一个满位（由1变0）
        wait(mutex);       // 2. 锁定缓冲区
        
        item = buffer[out];// 3. 从缓冲区取出数据
        
        signal(mutex);     // 4. 解锁缓冲区
        signal(empty);     // 5. 释放一个空位信号（由0变1，唤醒可能阻塞的生产者）
        
        consume the item;  // 消费数据
    }
}

【考研高频警示点】 在 PV 操作中，$wait(empty)$ 和 $wait(mutex)$ 的执行顺序绝不能调换。 如果调换，假设缓冲区已满（$empty=0$），生产者执行 $wait(mutex)$ 成功拿到缓冲区锁，接着执行 $wait(empty)$ 因无空位而阻塞。 此时消费者尝试获取 CPU 执行 $wait(full)$，然后执行 $wait(mutex)$ 时发现缓冲区已被死死锁住，消费者也陷入阻塞。 双方互相等待对方释放资源，导致系统陷入死锁 (Deadlock)！