跳转至

408 高频考点精讲:信号量

模块归属:操作系统 · 进程管理
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

1. 考查频次与题型分布

信号量机制是操作系统进程管理模块的核心基石,在 408 计算机学科专业基础综合考试中占据极高分值权重。 - 近十年考查频次:3 次(2017 年第 46 题、2018 年第 32 题、2024 年第 46 题) - 历年总考查频次:4 次(2009 年第 45 题、2017 年第 46 题、2018 年第 32 题、2024 年第 46 题) - 出题形式:单项选择题(考查概念机理、让权等待性质、信号量取值范围)、综合应用大题(考查多进程/线程并发控制、细粒度互斥设计、PV 伪代码实现)

2. 命题特点分析

  1. 底层机制与同步准则深度结合:客观题侧重考查记录型信号量如何通过内核原语(block() 及 wakeup())实现“让权等待”,精准辨析硬件自旋锁、软件轮询算法及记录型信号量在 CPU 占用状态上的本质差异。
  2. 细粒度设计追求最大并发度:综合大题已跳脱出教材中简单共享变量互斥的死板模板,转而强调分析复杂共享变量集合中各实体间的读写依赖关系,要求考生设计细粒度互斥锁以实现最大程度的并发执行(如 2017 年第 46 题)。
  3. 最简信号量设计与场景特化:命题愈发注重考查进程同步关系的本质前驱依赖,要求结合单次执行、有限执行等边界条件设计“尽可能少的信号量”,重点检验对临界区定义及前驱图映射的抽象能力(如 2024 年第 46 题)。

3. 近十年考查年份分布表格

+------+------+------+------+------+------+------+------+------+------+
| 2016 | 2017 | 2018 | 2019 | 2020 | 2021 | 2022 | 2023 | 2024 | 2025 |
+------+------+------+------+------+------+------+------+------+------+
|  --  | #46  | #32  |  --  |  --  |  --  |  --  |  --  | #46  |  --  |
+------+------+------+------+------+------+------+------+------+------+

二、 具体考察内容

1. 核心概念与工作机制

(1) 信号量的提出背景

在多道程序并发执行环境下,为了协调进程间对共享资源的争用以及步骤协同,Dijkstra 提出了信号量(Semaphore)机制。信号量是一种低级进程同步工具,通过一个整型变量或记录型数据结构结合两组原子操作(P 操作与 V 操作,亦称 wait() 与 signal() 操作)来控制并发进程对临界资源的互斥访问及顺序同步。

(2) 整型信号量

整型信号量被定义为一个用于表示资源数目的整型量 \(S\)$ \text{。对} $\(S\) 的操作仅能通过两个原子原语执行:

void wait(int S) {
    while (S <= 0); // 资源不足时循环等待(忙等)
    S--;
}

void signal(int S) {
    S++;
}
运行缺陷:整型信号量的 wait() 操作在资源不足时处于 while 循环空转状态,未遵循“让权等待”准则,持续消耗 CPU 计算资源,造成处理机资源的浪费。

(3) 记录型信号量

为了消除忙等现象,操作系统引入了记录型信号量。记录型信号量除了包含一个资源计数项 value 之外,还包含一个进程链表指针 list,用于链接所有因等待该资源而阻塞的进程控制块(PCB)。

数据结构定义:

typedef struct {
    int value;                         // 可用资源数或阻塞等待进程数
    struct process_control_block *list; // 等待该资源的进程阻塞队列头指针
} semaphore;

核心原语的工作流程: - wait(semaphore *S) 原语(P 操作):

void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // 当前无可分配资源,将调用进程置为阻塞态,插入等待队列
        block(S->list); 
    }
}
- signal(semaphore *S) 原语(V 操作):
void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // 说明等待队列中仍有受阻进程,从队列中移出并唤醒一个进程
        wakeup(S->list); 
    }
}

(4) 信号量取值的物理意义

记录型信号量 \(S.value\) 的符号及数值具有严格的系统状态语义: - \(S.value > 0\):表示系统中当前可用、未被占用的该类物理资源的剩余数量。此时若有进程申请资源,可立即获准分配并继续执行。 - \(S.value = 0\):表示系统中该类资源已被分配完毕,恰好全部占用,且当前等待队列为空,没有因等待该资源而被阻塞的进程。 - \(S.value < 0\)$ \text{:表示该类资源已全部耗尽,且其绝对值} $\(|S.value|\) 准确表示当前由于申请该资源失败而处于该信号量阻塞队列中的进程总数。


2. 核心定理推导与数学模型

(1) 互斥信号量动态取值范围推导

  • 场景设定:设系统中有 \(n\)$ \text{个并发进程竞争同一种互斥资源,该资源在任意时刻仅允许} $\(1\)$ \text{个进程使用。系统为该资源配置互斥信号量} $\(mutex\)$ \text{,其初值设为} $\(1\)。
  • 推导过程:
  • 上限情况:当系统中没有任何进程进入临界区,且无进程申请该资源时,\(mutex\)$ \text{保持初始值,即} $\(\max(mutex) = 1\)。
  • 临界运行态:当有 \(1\)$ \text{个进程进入临界区执行时,该进程先执行了} $\(P(mutex)\)$ \text{,计数器更新为} $\(1 - 1 = 0\)。此时资源完全占用,但阻塞队列为空。
  • 下限情况:在上述进程尚未退出临界区(未执行 \(V(mutex)\)$ \text{)期间,其余} $\(n - 1\)$ \text{个进程相继尝试进入临界区,各自执行一次} $\(P(mutex)\)$ \text{操作。每次操作均将} $\(mutex\)$ \text{自减} $\(1\)$ \text{,并将执行进程挂入阻塞队列。当其余} $\(n - 1\)$ \text{个进程全被阻塞时,} $\(mutex\) 达到最小值: $$\min(mutex) = 1

  • 1

  • (n

  • 1) = -(n

  • 1)$$

  • 结论:\(n\)$ \text{个并发进程竞争单一互斥资源时,互斥信号量} $\(mutex\) 的取值范围为: $\([-(n - 1), 1]\)$

(2) 通用资源信号量取值范围模型

  • 场景设定:设某类共享资源的可用物理实例数为 \(m\)$ \text{(信号量初值为} $\(m\)$ \text{),系统中并发进程数为} $\(n\)。每个进程最多申请该类资源的一个实例。
  • 数学模型分类:
  • 情形一(\(n \le m\)$ \text{):进程总数不超过资源总数。极端情况下所有} $\(n\)$ \text{个进程均申请资源,信号量递减} $\(n\)$ \text{次,取值达到最小值} $\(m - n \ge 0\)$ \text{。由于资源充裕,没有任何进程会被阻塞,信号量取值范围为} $\([m - n, m]\)。

  • 情形二(\(n > m\)$ \text{):进程总数超过资源总数。当} $\(m\)$ \text{个资源全部分配完毕后,信号量降为} $\(0\)$ \text{;随后剩余的} $$n

  • m$$ \text{个进程相继申请失败并被挂入阻塞队列,信号量取值达到最小值} $$m

  • n = -(n

  • m)$$ \text{。信号量取值范围为} $$[-(n

  • m), m]$。

(3) 同步机制的前驱关系数学映射

进程同步本质上是强制并发执行单元遵从偏序关系(Partial Order)。 - 设操作节点集合为 \(V = \{A, B\}\)$ \text{,前驱关系约束为} $\(A \to B\)$ \text{(即操作} $\(B\)$ \text{必须在操作} $\(A\) 完成之后方可执行)。 - 信号量建模规范: 1. 设立专属同步信号量 \(S_{A \to B}\)$ \text{,初值赋予} $\(0\)(表示前驱事件尚未完成)。 2. 在前驱进程完成操作 \(A\)$ \text{的代码后紧跟释放操作:} $\(V(S_{A \to B})\)。 3. 在后继进程执行操作 \(B\)$ \text{的代码前设置阻截操作:} $\(P(S_{A \to B})\)。 - 状态转移不变量: 若进程先调度至后继操作,执行 \(P(S_{A \to B})\)$ \text{使得} $\(S_{A \to B}.value = -1\)$ \text{,进程陷入阻塞;直至前驱进程执行完} $\(A\)$ \text{并调用} $\(V(S_{A \to B})\)$ \text{,触发} $\(wakeup()\)$ \text{唤醒后继进程,从而在任意可能的时间切片调度下严格保证时序} $\(A \to B\)。


3. 核心对比辨析

(1) 整型信号量与记录型信号量机制对比

比较维度 整型信号量 记录型信号量
数据结构组成 单一整型变量 \(S\) 资源计数器 value 与进程阻塞队列指针 list
P操作未满足时行为 处于 while 条件循环中空转(忙等) 执行 block() 原语,让出 CPU 进入阻塞态
V操作执行时行为 仅对整型变量 \(S\)$ \text{递增 递增 value;若} $\(\le 0\) 则调用 wakeup() 唤醒阻塞进程
同步准则满足度 违背“让权等待”准则 严格满足“空闲让进、忙则等待、有限等待、让权等待”
适用环境 适用于等待时间极短的多核自旋场景 现代通用操作系统进程同步的标准实现机制

(2) 常见临界区互斥实现机制对比

实现机制 实现方式 空闲让进 忙则等待 有限等待 让权等待 核心缺陷/特征
单标志法 纯软件轮询 否 是 是 否 违背空闲让进,资源利用率低
双标志先检查法 纯软件轮询 是 否 是 否 违背忙则等待,并发导致同时进临界区
双标志后检查法 纯软件轮询 是 是 否 否 违背有限等待,相互谦让导致死锁
Peterson 算法 纯软件标志协作 是 是 是 否 经典双进程互斥,但受阻进程处于忙等
TSL / Swap 指令 硬件原子指令 是 是 是 否 硬件保证原子性,但未获锁进程自旋忙等
记录型信号量 内核原语支持 是 是 是 是 引入等待队列和进程状态转换,全面满足准则

(3) 互斥信号量与同步信号量属性对比

特性属性 互斥信号量(Mutual Exclusion Semaphore) 同步信号量(Synchronization Semaphore)
核心解决目标 确保共享临界资源在任意时刻的独占性访问 协调进程间按既定依赖次序先后有序推进
初值设定规律 通常设为 \(1\)$ \text{(或允许并发进入的最大实体数} $\(k\)$ \text{) 通常设为} $\(0\)(或可用缓冲区格数、初始消息项数)
P/V 操作配对分布 紧密包裹临界区代码,在同一进程内部成对出现 分布在不同协作进程中,前驱进程执行 V,后继进程执行 P
临界区范围原则 遵从“紧贴原则”,临界区范围应尽可能精简 不涉及临界区包裹,充当事件通知栅栏

三、 近十年真题精讲(2016~2025)

【真题 1】2017 年 408 第 46 题 · 多线程共享变量细粒度互斥设计

题目:
某进程中有 3 个并发执行的线程 thread1、thread2、thread3,其伪代码如下所示。

// 复数的结构类型定义
typedef struct {
    float a;
    float b;
} cnum;

// 全局变量
cnum x, y, z;

// 计算两个复数之和
cnum add(cnum p, cnum q) {
    cnum s;
    s.a = p.a + q.a;
    s.b = p.b + q.b;
    return s;
}

thread1() {
    cnum w;
    w = add(x, y);
    ...
}

thread2() {
    cnum w;
    w = add(y, z);
    ...
}

thread3() {
    cnum w;
    w.a = 1;
    w.b = 2;
    z = add(z, w);
    y = add(y, w);
    ...
}
请添加必要的信号量和 P、V(或 wait()、signal())操作,要求确保线程互斥访问临界资源,并且最大程度地并发执行。

【解析】

  1. 知识定位与破题切入: 本题考查多线程并发环境下临界资源的识别、冲突类型划分(读-读共享、读-写互斥、写-写互斥)以及锁的细粒度划分。题目明确限制“最大程度地并发执行”,意味着严禁使用单一粗粒度全局互斥锁粗暴串行化。

  2. 共享资源与操作冲突矩阵分析: 系统中存在三个全局变量 \(x, y, z\)。各线程对变量的访问性质如下:

  3. 变量 \(x\):
    • thread1:读 \(x\)(执行 add(x, y));
    • thread2:不访问;
    • thread3:不访问。
    • 分析结论:\(x\) 仅有一个线程读取,不存在任何并发冲突,无需配置信号量保护。
  4. 变量 \(z\):
    • thread2:读 \(z\)(执行 add(y, z));
    • thread3:写 \(z\)(执行 z = add(z, w))。
    • 分析结论:thread2 与 thread3 存在“读-写”冲突,必须互斥访问。配置信号量 \(mutex_z\)$ \text{(初始值为} $\(1\))。
  5. 变量 \(y\):

    • thread1:读 \(y\)(执行 add(x, y));
    • thread2:读 \(y\)(执行 add(y, z));
    • thread3:写 \(y\)(执行 y = add(y, w))。
    • 分析结论:
    • thread1 与 thread2 均为“只读”,彼此之间完全兼容,必须允许同时并发读取;
    • thread1 与 thread3 存在“读-写”冲突,必须互斥;
    • thread2 与 thread3 存在“读-写”冲突,必须互斥。
  6. 信号量设计与最大并发策略推演: 若对 \(y\)$ \text{仅设置一个互斥信号量} $\(mutex_y\)$ \text{,则 thread1 和 thread2 读} $\(y\) 时也需互斥,破坏了读读并发,无法获得满分。 为了保证 thread1 和 thread2 能并发读取 \(y\):

  7. 设立互斥信号量 \(mutex_{y1} = 1\)$ \text{,用于协调 thread1(读} $\(y\)$ \text{)及 thread3(写} $\(y\));
  8. 设立互斥信号量 \(mutex_{y2} = 1\)$ \text{,用于协调 thread2(读} $\(y\)$ \text{)及 thread3(写} $\(y\));
  9. 设立互斥信号量 \(mutex_z = 1\)$ \text{,用于协调 thread2(读} $\(z\)$ \text{)及 thread3(写} $\(z\))。

工作逻辑验证: - thread1 读 \(y\)$ \text{时仅需获取} $\(mutex_{y1}\); - thread2 读 \(y\)$ \text{时仅需获取} $\(mutex_{y2}\)$ \text{。因此 thread1 与 thread2 可同时持有各自信号量并发读} $\(y\); - thread3 写 \(y\)$ \text{时必须同时申请} $\(mutex_{y1}\)$ \text{和} $\(mutex_{y2}\),确保此时既无 thread1 在读,亦无 thread2 在读。

  1. 死锁风险审查: thread2 需要访问 \(z\)$ \text{和} $\(y\)$ \text{;thread3 同样先后修改} $\(z\)$ \text{和} $\(y\)。
  2. thread3 的逻辑是先修改 \(z\)$ \text{,再修改} $\(y\)$ \text{。在修改完} $\(z\)$ \text{后立即执行} $\(V(mutex_z)\)$ \text{释放锁,之后才申请} $\(mutex_{y1}\)$ \text{与} $\(mutex_{y2}\)。
  3. 两个临界区是完全分离的,不存在嵌套持锁请求(Hold and Wait),因此绝不会引发循环等待死锁。

  4. 完整代码实现:

    // 信号量定义及初值赋予
    semaphore mutex_y1 = 1; // 控制 thread1 与 thread3 对变量 y 的读写互斥
    semaphore mutex_y2 = 1; // 控制 thread2 与 thread3 对变量 y 的读写互斥
    semaphore mutex_z  = 1; // 控制 thread2 与 thread3 对变量 z 的读写互斥
    
    thread1() {
        cnum w;
        P(mutex_y1);
        w = add(x, y);
        V(mutex_y1);
        ...
    }
    
    thread2() {
        cnum w;
        P(mutex_z);
        P(mutex_y2);
        w = add(y, z);
        V(mutex_y2);
        V(mutex_z);
        ...
    }
    
    thread3() {
        cnum w;
        w.a = 1;
        w.b = 2;
        // 互斥修改变量 z
        P(mutex_z);
        z = add(z, w);
        V(mutex_z);
    
        // 互斥修改变量 y,需同时排斥 thread1 和 thread2
        P(mutex_y1);
        P(mutex_y2);
        y = add(y, w);
        V(mutex_y2);
        V(mutex_y1);
        ...
    }
    


【真题 2】2018 年 408 第 32 题 · 进程同步机制让权等待准则辨析

题目:
在下列同步机制中,可以实现让权等待的是( )。
A. Peterson 方法
B. swap 指令
C. 信号量方法
D. TestAndSet 指令

【解析】

  1. 知识定位: 考查临界区互斥的四项准则(空闲让进、忙则等待、有限等待、让权等待)在不同软硬件实现方案下的支持情况。

  2. 核心原理推导:

  3. “让权等待”的严格学术定义:当进程不能进入自己的临界区时,应立即释放处理机执行权,进入等待(阻塞)状态,以免进程陷入忙等(Busy Waiting)持续占用 CPU。
  4. 硬件指令机制(TSL / Swap): 硬件互斥指令(如 swap、TestAndSet)是原子指令。当临界区已被占用时,未能获锁的进程在用户态下执行紧凑的 while 循环不断执行原子检测(自旋锁机制)。在此期间,进程始终处于运行态并占有处理机时间片,属于典型的“忙等”,不满足让权等待准则。因此 B、D 错误。
  5. 纯软件互斥算法(Peterson 方法): Peterson 算法利用 flag 标志数组和 turn 轮转变量实现双进程互斥。当一方试图进入临界区而另一方正在其中时,未获准进程受困于 while (flag[j] && turn == j); 空语句循环。该进程并未交出 CPU 控制权,同样属于忙等,不满足让权等待准则。因此 A 错误。
  6. 记录型信号量机制: 记录型信号量引入了显式的进程阻塞队列结构 list。当进程调用 \(P\)$ \text{操作导致} $\(S.value < 0\) 时,内核立即调用 block() 原语,直接将当前进程由运行态转入阻塞态,并主动触发操作系统的进程调度程序,将 CPU 分配给就绪队列中的其他就绪进程;待资源释放时通过 wakeup() 原语将其唤醒转入就绪态。此过程完全符合“让权等待”。因此 C 正确。

正确答案:C


【真题 3】2024 年 408 第 46 题 · 网络缓冲区访问控制与最小信号量设计

题目:
计算机系统中的进程之间往往需要相互协作以完成一个任务,在某网络系统中缓冲区 B 用于存放一个数据分组,对 B 的操作有 C1、C2 和 C3。C1 将一个数据分组写入 B 中,C2 从 B 中读出一个数据分组,C3 对 B 中的数据分组进行修改。要求 B 为空时才能执行 C1,B 非空时才能执行 C2 和 C3。请回答下列问题。
(1)假设进程 P1 和 P2 均需执行 C1,实现 C1 的代码是否为临界区?为什么?(2 分)
(2)假设 B 初始为空,进程 P1 执行 C1 一次,进程 P2 执行 C2 一次。请定义尽可能少的信号量。并用 wait(),signal() 操作描述进程 P1、P2 之间的同步或互斥关系,说明所用信号量的作用及初值。(3 分)
(3)假设 B 初始不为空,进程 P1 和 P2 各执行 C3 一次,请定义尽可能少的信号量。并用 wait()、signal() 操作描述进程 P1 和 P2 之间的同步或互斥关系,说明所用信号量的作用及初值。(3 分)

【解析】

第(1)小问

  • 结论:实现 C1 的代码是临界区。
  • 理论依据阐述: 临界区(Critical Section)是指进程中访问临界资源(即互斥共享变量、缓冲区或设备)的那段代码。本题中缓冲区 B 只能容纳一个数据分组,属于互斥共享的临界资源。操作 C1 的功能是向缓冲区 B 中写入数据。如果进程 P1 和 P2 同时并发执行 C1,将导致两个进程同时对缓冲区 B 进行写入覆盖,从而破坏数据的完整性与一致性。因此,为确保同一时刻至多只有一个进程向缓冲区 B 写入数据分组,实现 C1 的代码必须互斥执行,故其为临界区。

第(2)小问

  • 题目约束剖析:
  • 缓冲区 B 初始为空;
  • 进程 P1 仅执行 C1 一次(写);
  • 进程 P2 仅执行 C2 一次(读);
  • “要求定义尽可能少的信号量”。
  • 信号量推导: 由于缓冲区 B 初始状态已为空,P1 执行写入时初始条件已然满足,无需等待其他事件触发;而 P2 执行读取 C2 时,要求“B 非空”,必须等待 P1 完成 C1 的写入。 核心时序为前驱关系:$$ \text{P1\text{ 执行 }C1} \to \text{P2\text{ 执行 }C2} $$。 因为 P1 和 P2 各自仅执行一次,前驱同步关系天然杜绝了两进程在时间轴上重叠访问缓冲区 B 的可能性,二者绝无并发竞争条件。因此不需要额外的互斥信号量 mutex,仅需 \(1\) 个同步信号量即可完美解决。
  • 信号量定义: 定义同步信号量 full,初值为 \(0\)。其物理含义为:表示缓冲区 B 中是否存在可用数据分组(0 表示无数据,1 表示有数据)。
  • PV 同步代码实现:
    semaphore full = 0; // 初始缓冲区无数据分组
    
    // 进程 P1
    P1() {
        执行 C1;         // 将一个数据分组写入缓冲区 B
        signal(full);   // 发出信号,通知缓冲区已非空
    }
    
    // 进程 P2
    P2() {
        wait(full);     // 等待缓冲区 B 中出现数据分组
        执行 C2;         // 从缓冲区 B 中读出一个数据分组
    }
    

第(3)小问

  • 题目约束剖析:
  • 缓冲区 B 初始不为空;
  • 进程 P1 与 P2 各执行 C3 一次(对数据分组进行修改);
  • “要求定义尽可能少的信号量”。
  • 信号量推导: 因为缓冲区 B 初始已非空,已满足执行 C3 的前提条件。 P1 和 P2 均对缓冲区 B 执行修改操作(属于读后写),存在典型的“写-写”冲突,同一时刻只允许一个进程进入修改代码段。两进程之间不存在固定的先后时序偏序,属于纯粹的临界区互斥访问控制。 因此仅需 \(1\) 个互斥信号量即可保证安全。
  • 信号量定义: 定义互斥信号量 mutex,初值为 \(1\)。其物理含义为:控制对缓冲区 B 的互斥访问(1 表示缓冲区未被占用,0 表示已有进程正在访问/修改)。
  • PV 互斥代码实现:
    semaphore mutex = 1; // 缓冲区 B 的互斥访问信号量
    
    // 进程 P1
    P1() {
        wait(mutex);    // 申请进入缓冲区 B 的互斥使用权
        执行 C3;        // 对 B 中的数据分组进行修改
        signal(mutex);  // 释放缓冲区 B 的使用权
    }
    
    // 进程 P2
    P2() {
        wait(mutex);    // 申请进入缓冲区 B 的互斥使用权
        执行 C3;        // 对 B 中的数据分组进行修改
        signal(mutex);  // 释放缓冲区 B 的使用权
    }
    

四、 综合考法拓展

1. 408 综合大题中信号量设计的“四步解题法”

在 408 统考大题中,信号量设计题通常分值在 8~10 分。遵循以下四步解题范式可杜绝逻辑疏漏,确保拿满步骤分:

步骤一:角色与动作抽象 -> 划分进程集合与各进程内部循环体动作
步骤二:前驱与冲突矩阵分析 -> 明确所有“读写/写写互斥”与“先后执行同步时序”
步骤三:规范定义信号量 -> 给出确切变量名、初始值、详尽物理意义(踩分核心)
步骤四:组织 PV 代码块 -> 互斥紧密包裹,同步交叉联动,排查死锁隐患
  • 第一步:明确进程与循环模型
    根据题意区分参与协作的进程角色(如写进程、读进程、计算进程等),确定每个进程是“仅执行单次”还是“while(1) 持续循环执行”。
  • 第二步:分析关系依赖矩阵
  • 互斥关系:凡对同一共享资源(存储单元、硬件端口、临界变量)进行写入、修改,或不可同时调用的动作,标记为互斥。
  • 同步关系:凡动作之间存在因果逻辑(必须“先产生,后消费”、“先编号,后叫号”),标记为单向同步边 \(Action_A \to Action_B\)。
  • 第三步:信号量规范声明
    答题卷上必须清晰写出:
  • 信号量数据类型(如 semaphore);
  • 变量名称;
  • 初始数值;
  • 详尽的文字物理含义(评分标准中“说明所用信号量的作用及初值”独立占 2~3 分)。
  • 第四步:PV 操作组织准则
  • 互斥区“紧贴原则”:互斥的 \(P\)$ \text{操作与} $\(V\) 操作必须紧邻临界资源访问代码的前后,绝不能将不耗用互斥资源的繁重计算或 I/O 操作包进互斥区,否则将被判“无法最大程度并发”而扣分。
  • 嵌套顺序“同步在外,互斥在内”法则:当一个进程既需要获取资源(同步 \(P\)$ \text{),又需要加互斥锁(互斥} $\(P\))时,必须先申请同步资源信号量,再申请互斥信号量。颠倒次序将直接触发死锁。
    // 正确范式:同步在外,互斥在内
    P(empty);   // 先检查是否有空缓冲区(同步)
    P(mutex);   // 再加锁(互斥)
    // 临界区操作:写入缓冲区
    V(mutex);
    V(full);
    
    // 错误范式(致命死锁陷阱):
    P(mutex);   // 此时若 empty 为 0,该进程手握互斥锁并阻塞在 P(empty)
    P(empty);   // 其他生产者、消费者无法获得 mutex,系统全盘死锁!
    

2. 经典模型变式与跨知识点综合脉络

(1) 经典同步模型扩展图谱

  1. 生产者-消费者模型变式:
  2. 多类资源条件消费:如“盘子放苹果与橘子”、“缓冲区按奇偶数分类消费”。需配置多个同步信号量(如 empty, apple, orange),每个实体精准匹配前驱边。
  3. 单缓冲区特化:当缓冲区容量 \(N = 1\) 且仅有单个生产者与单个消费者时,互斥信号量可省略(由 empty 与 full 自然交替互斥,如 2024 年第 46 题的单次变式)。
  4. 读者-写者模型变式(细粒度与公平性):
  5. 细粒度共享访问(如 2017 年第 46 题):当读写涉及不同变量组合时,将粗粒度的大锁拆分为针对各变量维度的细粒度锁,兼顾互斥安全与并发性能。
  6. 公平排队策略:经典读者优先会导致写者饥饿。大题中常通过增加排队信号量 queue = 1,使新来的读者与写者在门外排队,实现先进先出的公平调度。
  7. 哲学家进餐模型变式(死锁规避机制):
  8. 考查如何打破死锁的四个必要条件(尤其是打破环路等待条件)。
  9. 常见考查解法:
    • 限制并发度:最多允许 \(N - 1\) 个哲学家同时拿叉子;
    • 奇偶编号非对称规则:奇数号哲学家先拿左后拿右,偶数号哲学家先拿右后拿左;
    • 原子多资源申请:使用 AND 信号量或利用互斥锁保护左右两侧叉子的一并申请。

(2) 综合题常见扣分陷阱清单

  1. 信号量初值设定错误:将互斥锁误设为 0,或将容量为 \(N\) 的资源信号量误设为 1。
  2. 信号量越权释放:互斥信号量被非加锁进程 \(V\) 操作释放(违背互斥锁所有权原则)。
  3. 临界区范围过宽:把非临界代码(如数据准备、局部变量计算)放入 \(P/V\) 之间,严重降低并发度。
  4. 死锁环路:多个互斥信号量在不同进程中的申请顺序不一致,导致交叉嵌套死锁。

五、 考点速记清单

1. 核心要点速记

  • 记录型信号量双属性:整型计数项 value 记录资源数;指针项 list 串接阻塞队列。
  • P 操作(wait)时序:先自减,后判断。执行 \(S.value\)$ \text{--;若} $\(S.value < 0\),立即调用 block() 主动让权阻塞。
  • V 操作(signal)时序:先自增,后判断。执行 \(S.value\)$ \text{++;若} $\(S.value \le 0\),调用 wakeup() 唤醒队首就绪进程。
  • 让权等待真谛:仅由内核级阻塞/唤醒机制保障的同步工具(记录型信号量)满足让权等待;纯软件算法(Peterson)、硬件指令(TSL、Swap)均为自旋忙等。

2. 信号量取值与计算公式速查

  • \(S.value > 0\):表示系统中可用物理资源数。
  • \(S.value = 0\):资源恰好用尽,且无进程阻塞。
  • \(S.value < 0\):\(|S.value|\) 即为阻塞队列中当前挂起的进程总数。
  • 互斥信号量取值区间:\(n\) 个并发进程竞争单一临界资源,初值为 1,动态区间为: $\([-(n - 1), 1]\)$
  • 多资源信号量取值区间:\(n\)$ \text{个进程竞争} $\(m\)$ \text{个资源(} $\(n > m\)$ \text{),初值为} $\(m\),动态区间为: $\([-(n - m), m]\)$

3. 解题核心口诀

互斥信号始为一,紧贴临界莫乱移。
同步信号始为零,前推后进次序清。
前驱操作紧接 V,后继代码前设 P。
同步在外互斥内,颠倒顺序锁中泪。
单次无竞可省锁,细分粒度并发多。