是什么

  • 定义:进程同步是指多个进程(或线程)在并发执行时,通过信号量(Semaphore)的 P 操作(wait)和 V 操作(signal),协调它们对共享资源的访问顺序,实现互斥(同一时刻只能一个进程用)和同步(按规定的先后顺序执行)。

  • 大白话:多个进程一起跑,有时候会“打架”(抢同一个东西,比如缓冲区),这时候要互斥;有时候需要“排队”(比如必须先做完A才能做B),这时候要同步。信号量就是一个“计数器+等待队列”,用来管这两件事。P操作相当于“申请/占用一个资源”,V操作相当于“归还/释放一个资源”。

核心内容

1. PV操作的本质(必须死记)

C

wait(S) / P(S) {
    S = S - 1;
    if (S < 0) {
        该进程进入S的等待队列;  // 阻塞
    }
}

signal(S) / V(S) {
    S = S + 1;
    if (S <= 0) {
        唤醒S等待队列中的一个进程;
    }
}

Warning

P操作永远是“先申请再用”,V操作永远是“用完再释放”,P和V在同一个进程内必须成对出现(但不一定在同一个函数里)。

信号量初值的物理含义:

  • 互斥信号量:初值一般为 1(表示资源“空闲”,谁都能抢一次)。

  • 同步信号量:初值一般为 0(表示事件“还没发生”,必须等别人 V 了才能往下走)。

  • 资源型信号量:初值为资源的数量(比如缓冲区大小、碗的个数)。

  • 的数值状态机:

    • :当前系统中可用的物理资源数;

    • :资源恰好用完,且当前没有人在排队;

    • : 的绝对值精确等于当前被阻塞挂起在等待队列中的进程数。

2. 核心命题突破:到底根据什么来设置“几个信号量”?(判断依据全景图)

做题时千万不要凭感觉“见一个变量设一个锁,见一个步骤设一个信号量”。决定信号量个数的唯一依据是底层约束关系(互斥冲突域、跨线程前趋弧、资源实体数、死锁门阀):

Plaintext

【决策流程图】
拿到题目,逐条排查以下 5 种约束,满足几个就设几个:

1. 找共享写冲突(互斥):
   └─ 是否有多个进程并发修改同一块内存/缓冲区/硬件?
      └─ 是 ──> 每个独立的互斥实体设 1 个互斥信号量(初值 1)

2. 找先后依赖顺序(同步):
   └─ 题中有没有“谁必须在谁之后执行”?
      ├─ 情况 A(无固定线程,各操作独立) ──> 前趋图中几条有向边,就设几个信号量(初值 0)
      └─ 情况 B(指定了固定线程分配)     ──> 仅跨线程的边设信号量(初值 0);同线程内部靠代码顺序保证,设 0 个!

3. 找有界容器与离散实体(资源):
   └─ 是否有池子、槽位、生产消耗?
      └─ 是 ──> 区分类型:空槽数 empty(初值容量 N),已放产品数 full(初值 0)

4. 找对称申请死锁(哲学家进餐):
   └─ 是否有多个对称进程同时申请多类资源形成环路?
      └─ 是 ──> 额外追加 1 个限制总准入人数的门阀信号量(初值 总人数 - 1)

5. 找连续占用特权(批量行为):
   └─ 是否要求“某个角色连续做 k 次,中途不可被打断”?
      └─ 是 ──> 额外追加 1 个控制连续操作权的互斥信号量(初值 1)

信号量设置法则与考点速查表

约束类型判定依据与题眼信号量设置数量法则初值规律典型真题与考点
共享数据互斥“共享一个缓冲区”、“修改同一数据”一个共享写入实体设 1 个1生产消费的 mutex=1,哲学家筷子 chopstick[i]=1
独立操作前趋仅给出多个操作(未分派线程),要求某操作在某操作之后前趋拓扑图有向边数 = 信号量数(每个箭头一个)02020 真题(第24题):4 条边设 4 个信号量
受限线程前趋明确指定了线程 T1、T2 分别跑哪些操作仅“跨线程的前趋边”设信号量;同线程内部的边设 0 个02022 真题(第26题):仅 2 处跨线程,设 2 个信号量
资源计数与容器“容量为 N 的环形缓冲”、“m 个碗”每类实体槽位或生成物各设 1 个容器大小 或初始可用数 empty=1000,full=0,bowl=m
死锁预防门阀多个进程环形竞争多份资源(哲学家)设 1 个全局并发门阀参与总人数减一()2019 真题(第23题):room = n - 1
连续原子占用“连续取出 10 件后其他人才可取”针对该连续执行过程额外设 1 个互斥量12014 真题(第20题):mutexC = 1

3. 这一章的题型分类与核心解法

题型识别表(看到关键词直接对应方法)

题型识别关键词核心方法
① 生产者-消费者变形“缓冲区”、“放入/取出”、“满了等待/空了等待”三个基础信号量 mutex/empty/full,再叠加题目的附加条件
② 前趋图/操作先后同步“A 完成后才能执行 B”、“必须在…之后”区分是否指定线程:独立操作按边设,指定线程仅跨线程设
③ 死锁预防型“多个进程竞争多份资源,还要求资源共享/循环等待”用一个“总量少 1”的信号量(room/turn),打破循环等待条件
④ 信号量原理/正确性辨析“开中断/关中断”、“是否正确”、“为什么必须互斥”不写代码,用操作系统底层原理做文字辨析
⑤ 多角色协作型(综合题)出现 3 个及以上角色,既有互斥又有先后顺序先画出“谁等谁、谁产谁、谁抢谁”的关系图,再逐条翻译成信号量

题型①:生产者-消费者变形

做题思路(四步法):

  1. 先写出最基础的三件套:

    • mutex = 1(互斥访问缓冲区本身)

    • empty = N(缓冲区还剩多少空位,N是缓冲区容量)

    • full = 0(缓冲区里已经有多少产品)

  2. 生产者的固定顺序:P(empty) → P(mutex) → 放产品 → V(mutex) → V(full)

  3. 消费者的固定顺序:P(full) → P(mutex) → 取产品 → V(mutex) → V(empty)

  4. 看题目有没有“附加限制”(比如“连续取 10 个才能换人”、“某种产品优先”):如果有,再加一个新的信号量专门控制这个附加条件,不要破坏原来三件套的结构。

Warning

  • P(empty)/P(full) 和 P(mutex) 的顺序绝对不能换! 一定是先申请资源名额,再申请互斥锁。如果反过来(先拿 mutex 再 P(empty)/P(full)),会导致死锁(一个进程占着 mutex 却在等资源,别人永远进不来释放资源)。

  • mutex 必须紧贴着“放/取产品”这几行代码,V(mutex) 一定要在解锁后才 V(empty)/V(full),否则会造成不必要的等待(虽然不算错,但不是最优解,标准答案通常要求顺序合理)。

题型②:前趋图/操作先后同步(2020 与 2022 真题的核心差异剖析)

做题思路:

  1. 找出题目中“谁必须在谁之后执行”的所有箭头依赖关系。

  2. 核心分水岭(为什么 2020 年和 2022 年答案形式截然不同?):

    • 若题目没有指定线程(如 2020 年第 24 题):每个操作是完全独立的并发实体,每一条箭头对应一个信号量,初值为 0。箭头的起点操作做完后 V,终点操作开始前 P。

    • 若题目明确划分了线程(如 2022 年第 26 题):

      • 同一线程内的先后关系,由单线程自身代码自上而下的顺序执行天然保证,绝对不要多设信号量!(多设会暴露不懂线程内指令是串行执行的)。

      • 只有跨线程的依赖箭头,才需要设置初值为 0 的同步信号量。

  3. 如果一个操作有多个前驱(比如“C 必须在 A 和 B 都完成后才能做”),就要 P 多个信号量。

Warning

这类题不需要 mutex!因为它考的不是互斥,是先后顺序。很多同学一看到信号量就习惯性加 mutex,反而是错的(除非题目明确说了有共享变量要互斥写入)。

题型③:死锁预防型(哲学家进餐及其变形)

做题思路:

  1. 先写出“每个人要拿哪些资源才能进餐”,每种资源一个信号量。

  2. 检查是否存在循环等待(比如 个人都拿着左手的东西等右手的东西)——如果存在,必须打破它。

  3. 打破循环等待的标准手段:加一个“最多允许 人同时申请资源”的信号量(相当于总有一个人进不去,链条就断了,不会死锁)。

Warning

  • 死锁的四个必要条件:互斥、占有且等待、不可剥夺、循环等待。破坏其中任意一个即可防止死锁。本题用的是“破坏循环等待”(room = n - 1),不是唯一解法(也可以规定奇数号先拿左筷子、偶数号先拿右筷子),但 room = n - 1 是王道最推荐、最好写的标准解法,建议直接记这个套路。

  • 别忘了同时限制“资源数量”(比如本题的碗数 ),别只顾着筷子忘了碗,多资源题容易漏写信号量。

题型④:信号量原理辨析题(不写代码,纯理论问答,新题型要重视)

这是 2021、2023 真题新出的考法,没有编程量,但很多人反而丢分,因为大家只顾着背套路代码,没理解“为什么”。

必背结论与底层机理:

  1. 为什么 wait/signal 对信号量 S 的访问必须互斥执行?

    • 因为 S = S - 1 或 S = S + 1 不是硬件原子操作(包含“读取 S 到寄存器 ALU 运算 写回内存 S”三步微指令)。

    • 如果两个进程同时执行,会发生数据覆盖与竞争冒险(例如两个进程同时读到 ,都减 1 写回,最终 变成 0 而不是预期的 -1),导致信号量值出错,破坏对等待队列的正确唤醒与计数。

  2. 开/关中断能不能实现临界区互斥?

    • 单处理器系统可以:因为关中断后当前 CPU 不会响应时钟中断,操作系统无法强制进行进程上下文切换,当前代码能一口气执行完。

    • 多处理器系统不行:因为开/关中断指令只能屏蔽当前 CPU 核心的中断,其他物理核心上的进程仍然可以并发访问共享内存变量 。

    • 用户态程序不行:开/关中断是特权指令,用户态程序执行会引发硬件中断(非法指令异常),无法在用户空间直接使用。

  3. 判断“某段代码是否为临界区”的标准:

    • 只要是多个并发实体共享、且存在写操作的临界资源(无论是全局变量、硬件设备还是缓冲区),访问它的这段代码就是临界区。判断依据不是“代码看起来像不像”,而是看“是否存在并发访问会导致结果不一致的共享状态”。

题型⑤:多角色综合题(植树问题、多线程协作)

做题思路(三步法):

  1. 先在草稿纸上画出“角色-资源-顺序”关系:谁要等谁、谁和谁互斥、谁控制什么资源数量。

  2. 列出需要几个信号量:一般是“资源数量型”(比如工具够不够、坑够不够)+“顺序型”(谁先谁后,初值 0)。

  3. 最后才翻译成 wait/signal 代码,顺序型信号量套用题型②的方法,资源数量型套用题型①③的方法,本质是前面几种题型的组合。

例题

例题①:生产者-消费者变形(2014 统考真题)

  • 题目:

    系统中有多个生产者进程和多个消费者进程,共享一个能存放 1000 件产品的环形缓冲区(初始为空)。缓冲区未满时,生产者进程可以放入其生产的一件产品,否则等待;缓冲区未空时,消费者进程可从缓冲区取走一件产品,否则等待。要求一个消费者进程从缓冲区连续取出 10 件产品后,其他消费者进程才可以取产品。请使用信号量 P、V(wait()、signal())操作实现进程间的互斥与同步,要求写出完整的过程,并说明所用信号量的含义和初值。

  • 分析:

    • 关键词“缓冲区”、“放入/取出”、“满了等待/空了等待” 题型①基础模型,设 mutex=1、empty=1000、full=0。

    • 附加条件“连续取 10 个后其他消费者才能取” 需要额外追加一个互斥信号量 mutexC = 1,锁定“连续取 10 个”的循环体,防止其他消费者插队。

  • 答案:

    C

    semaphore mutex = 1;    // 互斥信号量,控制对缓冲区的互斥访问,初值 1
    semaphore empty = 1000; // 同步信号量,表示缓冲区中的空闲单元数,初值 1000
    semaphore full = 0;     // 同步信号量,表示缓冲区中的产品数,初值 0
    semaphore mutexC = 1;   // 互斥信号量,保证一个消费者连续取 10 件的过程中其他消费者不能插入,初值 1
    
    producer() {
        while(1) {
            生产一件产品;
            P(empty);       // 申请一个空闲单元
            P(mutex);       // 申请互斥访问缓冲区
            将产品放入缓冲区;
            V(mutex);       // 释放缓冲区互斥权
            V(full);        // 释放一个满槽位(产品数加 1)
        }
    }
    
    consumer() {
        while(1) {
            P(mutexC);      // 抢占"连续消费权",保证接下来 10 次取出不被打断
            for (int i = 0; i < 10; i++) {
                P(full);    // 申请一个产品
                P(mutex);   // 申请互斥访问缓冲区
                从缓冲区取出一件产品;
                V(mutex);   // 释放缓冲区互斥权
                V(empty);   // 释放一个空槽位
                消费这件产品;
            }
            V(mutexC);      // 释放"连续消费权",允许其他消费者开始消费
        }
    }
    

    信号量含义与初值说明:

    • mutex:控制多个生产者/消费者对共享缓冲区的互斥访问,初值为 1。

    • empty:表示缓冲区中空闲单元的数量,初值为 1000。

    • full:表示缓冲区中已有产品的数量,初值为 0。

    • mutexC:保证同一时刻只有一个消费者能获得“连续取 10 件”的执行特权,初值为 1。

例题②-A:独立操作前趋图(2020 统考真题 第 24 题)

  • 题目:

    现有 5 个操作 A、B、C、D 和 E,操作 C 必须在 A 和 B 完成后执行,操作 E 必须在 C 和 D 完成后执行,请使用信号量的 wait()、signal() 操作描述上述操作之间的同步关系,并说明所用信号量的作用及其初值。

  • 分析:

    • 关键词“必须在…完成后执行” 判断为题型②:前趋图同步题,不涉及共享资源写入,不需要 mutex。

    • 题目未将操作划分到指定线程,A、B、C、D、E 均为独立并发实体。

    • 画出依赖拓扑弧:、、、 共 4 条有向边。

    • 规则:有向边数 = 信号量数。设置 4 个信号量,初值均为 0。

  • 答案:

    C

    semaphore sa = 0;  // 表示操作 A 是否已完成,初值 0
    semaphore sb = 0;  // 表示操作 B 是否已完成,初值 0
    semaphore sc = 0;  // 表示操作 C 是否已完成,初值 0
    semaphore sd = 0;  // 表示操作 D 是否已完成,初值 0
    
    cobegin
    A() {
        A;
        signal(sa);    // 通知 A 已完成
    }
    
    B() {
        B;
        signal(sb);    // 通知 B 已完成
    }
    
    C() {
        wait(sa);      // 等待 A 完成
        wait(sb);      // 等待 B 完成
        C;
        signal(sc);    // 通知 C 已完成
    }
    
    D() {
        D;
        signal(sd);    // 通知 D 已完成
    }
    
    E() {
        wait(sc);      // 等待 C 完成
        wait(sd);      // 等待 D 完成
        E;
    }
    coend
    

    信号量含义与初值说明:

    sa、sb、sc、sd 分别表示操作 A、B、C、D 是否已经执行完毕,初值均为 0。每个操作执行完毕后通过 signal() 唤醒后继操作;后继操作开始前通过 wait() 确保前趋操作已经完成。

例题②-B:固定线程的前趋同步(2022 统考真题 第 26 题)

  • 题目:

    某进程的两个线程 T1 和 T2 并发执行 A、B、C、D、E 和 F 共 6 个操作,其中 T1 执行 A、E 和 F,T2 执行 B、C 和 D。约束关系:C 在 A 和 B 完成后执行,D 和 E 在 C 完成后执行,F 在 E 完成后执行。请使用信号量的 wait()、signal() 操作描述 T1 和 T2 之间的同步关系,并说明所用信号量的作用及其初值。

  • 分析:

    • 操作分配:T1 = ,T2 = 。

    • 同线程内部依赖(无需信号量):

      • T2 内部:先写 B 再写 C 满足 ;先写 C 再写 D 满足 。

      • T1 内部:先写 E 再写 F 满足 。

    • 跨线程依赖(需要信号量):

      • :跨线程,设 。

      • :跨线程,设 。

    • 关键动作:在 T2 中,C 执行完后必须立刻 signal(S2),然后再去跑 D,绝不能等 D 跑完了才通知 E!

  • 答案:

    C

    semaphore S1 = 0; // 表示操作 A 是否已完成,用于 T1(A) 到 T2(C) 的同步,初值 0
    semaphore S2 = 0; // 表示操作 C 是否已完成,用于 T2(C) 到 T1(E) 的同步,初值 0
    
    cobegin
    void Thread1() {
        // 1. 执行操作 A
        A;
        signal(S1);  // 通知 T2:操作 A 已完成
    
        // 2. 执行操作 E(需等待操作 C 完成)
        wait(S2);    // 等待 T2 的操作 C 完成
        E;
    
        // 3. 执行操作 F(由线程内顺序性保证在 E 之后执行)
        F;
    }
    
    void Thread2() {
        // 1. 执行操作 B
        B;
    
        // 2. 执行操作 C(需等待 A 和 B 完成,B 已在本线程前面执行)
        wait(S1);    // 等待 T1 的操作 A 完成
        C;
        signal(S2);  // 【必须在此处立刻发出通知】:通知 T1 的 E 可以执行了
    
        // 3. 执行操作 D(由线程内顺序性保证在 C 之后执行)
        D;
    }
    coend
    

    信号量含义与初值说明:

    • 用于表示操作 A 是否完成,初值为 0。

    • 用于表示操作 C 是否完成,初值为 0。

    • 线程内操作( 到 、 到 、 到 )的时序由单线程内指令的顺序执行机制保证,不需设置额外信号量。

例题③:死锁预防型(2019 统考真题)

  • 题目:

    有 ()名哲学家围坐在一张圆桌边,每名哲学家交替地就餐和思考。在圆桌中心有 ()个碗,每两名哲学家之间有一根筷子。每名哲学家必须取到一个碗和两侧的筷子后,才能就餐,进餐完毕,将碗和筷子放回原位,并继续思考。为使尽可能多的哲学家同时就餐,且防止出现死锁现象,请使用信号量的 P、V 操作(wait()、signal() 操作)描述上述过程中的互斥与同步,并说明所用信号量及初值的含义。

  • 分析:

    • 关键词“多个进程竞争多份资源” + “防止死锁” 题型③:死锁预防型。

    • 每名哲学家需要“1个碗 + 左右两根筷子”才能就餐,存在对称死锁隐患( 个人全拿了左筷子,同时等待右筷子陷入死锁)。

    • 采用“限制同时申请资源的人数为 ”的门阀策略,打破循环等待条件。

  • 答案:

    C

    semaphore chopstick[n];  // 每个初值 1,表示第 i 根筷子是否可用,数组下标 0 ~ n-1
    semaphore bowl = m;      // 表示当前可用的碗数,初值 m
    semaphore room = n - 1;  // 表示最多允许 n-1 名哲学家同时申请资源,初值 n-1,用于打破循环等待、防止死锁
    
    Pi() {                   // 第 i 名哲学家的进程,i = 0, 1, ..., n-1
        while(1) {
            思考;
            P(room);               // 申请进入"就餐候选区",最多 n-1 人同时申请
            P(bowl);               // 申请一个碗
            P(chopstick[i]);       // 申请左手边的筷子
            P(chopstick[(i+1)%n]); // 申请右手边的筷子
            进餐;
            V(chopstick[i]);       // 归还左手边的筷子
            V(chopstick[(i+1)%n]); // 归还右手边的筷子
            V(bowl);               // 归还碗
            V(room);               // 退出"就餐候选区"
        }
    }
    

    信号量含义与初值说明:

    • chopstick[i]():表示第 根筷子是否可用,每个初值为 1。

    • bowl:表示当前可用的碗数,初值为 。

    • room:表示最多允许同时申请资源的哲学家人数,初值为 。这是防止死锁的关键——即使所有哲学家同时饥饿,也至少有一人无法进入申请流程,从而彻底打破了“所有人各占有一份资源并循环等待下一个资源”的死锁必要条件。

⚠️ 易错点(复习时反复过一遍)

Warning

  • 把同线程内的前后时序错误地多设信号量:在 2022 真题中,如果在 T2 内部给 或 设信号量,属于未理解线程内部指令串行执行的本质,会在规范性评分中扣分。

  • signal(S) 发送时机位置放错(致命逻辑时序倒挂):在 2022 真题 T2 中,C 执行完必须立刻 signal(S2),之后再去跑 D。如果写成先跑 D 再 signal(S2),就等于强加了“E 必须等 D 执行完才能执行”的错误约束,破坏了并发性。

  • 死锁诱因:P(资源) 与 P(互斥) 顺序倒置:必须先申请资源、后申请互斥锁:

    C

    // 错误代码:会引发死锁!
    wait(mutex);
    wait(empty); // 若此时无空槽阻塞,该进程将带着互斥锁入睡,导致生产者/消费者均无法进入
    
  • 前趋同步题滥用互斥信号量(mutex):纯流程先后约束题(如拓扑排序、纯操作图)只关注时序,根本没有写冲突的临界区,千万不要画蛇添足加 mutex = 1。

  • 死锁题只顾着局部资源,忘了限制“同时申请人数”:一定要记得加 room = n - 1 这种“少一个名额”的门阀信号量来打破循环等待。

  • 理论辨析题(题型④)容易只背结论不理解原因:一定要能自己清晰解释“为什么 P/V 操作要原子互斥执行”(非原子指令导致竞争覆盖)以及“为什么关中断不能在多核/用户态使用”(多核无法跨核屏蔽、开关中断是特权指令)。

  • 写答案时信号量含义和初值说明不能省略:统考真题评分标准里,“说明信号量含义及初值”通常单独占 2~4 分,光写对代码但不写文字说明会扣分,务必在代码后附带规范的文字说明。