是什么

  • 定义:临界资源是一段时间内只允许一个进程访问的物理或逻辑资源;临界区是每个进程中访问临界资源的代码段。操作系统利用信号量机制及 wait()(P操作)与 signal()(V操作)原语,协调多个并发进程对临界资源的互斥访问(无序独占)与同步推进(依赖时序)。

  • 大白话:互斥就是“同一个马桶同一时间只能一个人用,进去先锁门,出来再开门”;同步就是“炒菜和吃饭,必须先等菜炒好端上桌,后一个人才能动筷子”。

核心内容

1. 核心概念对比

概念本质属性核心特征 / 采分关键词考场实例
临界资源物理/逻辑实体一段时间内只允许一个进程独占访问打印机、共享变量 count、共享缓冲区 B
临界区程序代码段进程中访问临界资源的那段代码,进前检查、出后释放buffer[in] = x;、count++;
互斥关系间接制约非此即彼,没有先后顺序要求两个进程都要向缓冲区写数据
同步关系直接制约先后顺序,前驱完成才能触发后继先生产数据后消费数据

2. PV 操作万能解题 5 步流水线

  1. 找进程实体:找出题目中所有独立的并发操作主体,为每个实体定义独立函数(如 Producer()、Consumer() 或 P1()、P2()),并核对是否为 while(1) 持续循环或仅执行一次。

  2. 辨识关系与定初值:

    • 互斥信号量:多个进程争夺独占资源。初值一般设为 mutex = 1。

    • 同步信号量:存在依赖时序或容量限制。空闲量初值设为 empty = N,已有量初值设为 full = 0。

  3. 卷首规范声明:集中写明信号量类型、初值及其物理意义。

  4. 组装代码骨架:

    • 互斥操作:先 P 后 V 夹中间(在同一进程内包裹临界区)。

    • 同步操作:前 V 后 P 跨进程(前驱事件结束执行 V(S) 通知,后继事件开始前执行 P(S) 等待)。

    • 嵌套原则:先同步 P,后互斥 P(先看是否有资格/资源,再拿互斥锁进临界区)。

  5. 死锁与变量自检:检查是否存在嵌套倒置导致的死锁,以及普通整型计数变量是否被锁保护。

例题

类型一:生产者-消费者模型(带容量缓冲区)

  • 题目:某网络系统中缓冲区 B 用于存放一个数据分组,对 B 的操作有 C1(写)、C2(读)和 C3(改)。要求 B 为空时才能执行 C1,B 非空时才能执行 C2 和 C3。

    1. 假设进程 P1 和 P2 均需执行 C1,实现 C1 的代码是否为临界区?为什么?

    2. 假设 B 初始为空,进程 P1 执行 C1 一次,进程 P2 执行 C2 一次。请定义尽可能少的信号量,描述 P1、P2 的同步或互斥关系,说明信号量作用及初值。

    3. 假设 B 初始不为空,进程 P1 和 P2 各执行 C3 一次,请定义尽可能少的信号量描述同步或互斥关系。

  • 分析:

    • 第 (1) 问:缓冲区 B 为临界资源,执行 C1 的代码访问了该资源,属于临界区。

    • 第 (2) 问:初始为空且各执行一次,P1 无需等待空位直接写,仅需单向通知 P2 读,故只需 1 个同步信号量 full = 0,且不能加 while(1)。

    • 第 (3) 问:初始已有数据且各执行一次修改,两者核心冲突是不能同时修改 B,属于纯互斥关系,需 1 个互斥信号量 mutex = 1。

  • 答案: (1) 是临界区。缓冲区 B 是一次仅允许一个进程访问的临界资源,实现 C1 的代码涉及向共享缓冲区 B 中写入数据,并发执行会导致数据冲突,因此是临界区。 (2)

    C

    semaphore full = 0; // 作用:表示缓冲区B中数据分组的数量,初值为0
    
    void P1() {
        C1;             // 将数据分组写入B
        signal(full);   // 唤醒P2,告知B中有数据
    }
    
    void P2() {
        wait(full);     // 等待B中有数据
        C2;             // 从B中读出数据分组
    }
    

    (3)

    C

    semaphore mutex = 1; // 作用:实现对缓冲区B的互斥修改,初值为1
    
    void P1() {
        wait(mutex);    // 申请访问缓冲区B
        C3;             // 对B中的数据分组进行修改
        signal(mutex);  // 释放缓冲区B
    }
    
    void P2() {
        wait(mutex);    // 申请访问缓冲区B
        C3;             // 对B中的数据分组进行修改
        signal(mutex);  // 释放缓冲区B
    }
    

类型二:前趋图 / 流水作业模型(纯同步)

  • 题目:四门课的复习进度存在前后制约关系,任务安排如下: 完成后方可开始 和 ; 和 均完成后方可开始 。请使用 P、V 操作描述这 4 个任务的同步执行过程。

  • 分析:

    • 前趋图是有向无环图(DAG),属于纯同步问题,不涉及缓冲区与互斥。

    • 核心口诀:前 V 后 P,一条有向边对应一个信号量,初值均为 0。

    • 共有 4 条边:(信号量 )、(信号量 )、(信号量 )、(信号量 )。

  • 答案:

    C

    semaphore a = 0; // 控制 S1 -> S2 的执行顺序
    semaphore b = 0; // 控制 S1 -> S3 的执行顺序
    semaphore c = 0; // 控制 S2 -> S4 的执行顺序
    semaphore d = 0; // 控制 S3 -> S4 的执行顺序
    
    void Task1() {
        S1;
        signal(a);
        signal(b);
    }
    
    void Task2() {
        wait(a);
        S2;
        signal(c);
    }
    
    void Task3() {
        wait(b);
        S3;
        signal(d);
    }
    
    void Task4() {
        wait(c);
        wait(d);
        S4;
    }
    

类型三:读者-写者问题(分级互斥 / 计数器模型)

  • 题目:某系统维护一个共享文件 F,允许多个读者进程同时读该文件,但任一时刻只允许一个写者进程写文件,且任何写者在写文件时不允许任何读者读取。请用 P、V 操作实现读者优先的同步互斥方案。

  • 分析:

    • 写者与任何人互斥(写者与写者、写者与读者);读者之间不互斥。

    • 核心逻辑:第一个进门的读者加锁,最后一个出门的读者解锁。

    • 必须维护一个整型变量 readcount 统计当前读者数,由于多个读者会并发修改 readcount,修改该变量的代码段是临界区,必须配一把互斥锁 count_mutex。

  • 答案:

    C

    semaphore rw_mutex = 1;    // 互斥信号量:保证写者独占访问文件
    semaphore count_mutex = 1; // 互斥信号量:保证对 readcount 的互斥修改
    int readcount = 0;         // 记录当前正在读取文件的读者数量
    
    void Reader() {
        while (1) {
            wait(count_mutex);
            if (readcount == 0) {
                wait(rw_mutex);    // 第一个读者负责把门锁上,阻塞写者
            }
            readcount++;
            signal(count_mutex);
    
            读取文件 F;
    
            wait(count_mutex);
            readcount--;
            if (readcount == 0) {
                signal(rw_mutex);  // 最后一个读者离开时开门,唤醒写者
            }
            signal(count_mutex);
        }
    }
    
    void Writer() {
        while (1) {
            wait(rw_mutex);        // 申请独占写权限
            写入文件 F;
            signal(rw_mutex);      // 释放独占写权限
        }
    }
    

类型四:独木桥 / 转向排队模型(方向互斥 / 限额访问)

  • 题目:有一座向东和向西通行的单车道独木桥,桥上同一时间只允许同方向的汽车通行,但不能两向同时在桥上。同一方向每次最多允许 3 辆车在桥上。请用 P、V 操作实现桥上的行车管理。

  • 分析:

    • 本质是“双向读者-写者问题”加上“限额控制”。

    • 独木桥的占有权是一把互斥锁 bridge = 1。

    • 向东方向第一辆车占锁、最后一辆车还锁;向西方向同理。

    • “最多允许 3 辆车”通过限额信号量 quota_east = 3 与 quota_west = 3 实现容量控制。

  • 答案:

    C

    semaphore bridge = 1;        // 互斥信号量:表示独木桥的使用权
    semaphore mutex_east = 1;    // 互斥信号量:保护 count_east 变量
    semaphore mutex_west = 1;    // 互斥信号量:保护 count_west 变量
    semaphore quota_east = 3;    // 同步信号量:向东同时在桥上的车辆限额
    semaphore quota_west = 3;    // 同步信号量:向西同时在桥上的车辆限额
    int count_east = 0;          // 当前向东上桥的车辆数
    int count_west = 0;          // 当前向西上桥的车辆数
    
    void East_Car() {
        while (1) {
            wait(quota_east);    // 1. 检查向东桥上是否还有容量
            wait(mutex_east);
            if (count_east == 0) {
                wait(bridge);    // 第一辆向东的车抢夺桥的使用权
            }
            count_east++;
            signal(mutex_east);
    
            向东过桥;
    
            wait(mutex_east);
            count_east--;
            if (count_east == 0) {
                signal(bridge);  // 最后一辆向东的车释放桥的使用权
            }
            signal(mutex_east);
            signal(quota_east);  // 离开桥,归还向东容量
        }
    }
    
    void West_Car() {
        while (1) {
            wait(quota_west);    // 1. 检查向西桥上是否还有容量
            wait(mutex_west);
            if (count_west == 0) {
                wait(bridge);    // 第一辆向西的车抢夺桥的使用权
            }
            count_west++;
            signal(mutex_west);
    
            向西过桥;
    
            wait(mutex_west);
            count_west--;
            if (count_west == 0) {
                signal(bridge);  // 最后一辆向西的车释放桥的使用权
            }
            signal(mutex_west);
            signal(quota_west);  // 离开桥,归还向西容量
        }
    }
    

⚠️ 易错点

Warning

  • 死锁倒置陷阱:必须牢记“先同步 P,后互斥 P”。若误写成 wait(mutex); wait(empty);,当缓冲区满(empty=0)时生产者持锁阻塞,消费者因拿不到 mutex 无法取数据,直接导致系统死锁。

  • “执行一次”字眼陷阱:题干说明“执行一次”时,代码中绝对不要套 while (1),否则属于未按题意实现扣分。

  • “尽可能少的信号量”陷阱:单缓冲区初始为空且各执行一次时,写操作无需等待直接执行,不要多设 empty 信号量,仅需 full = 0 控制单向同步即可。

  • 临界资源 vs 临界区概念混淆:临界资源是数据/硬件实体(如缓冲区 B),临界区是访问该资源的代码(如操作 C1 的代码)。

  • 共享普通变量漏加锁:若代码中存在 readcount++、count_east-- 等整型计数器,它们并非硬件原子操作,必须单独用互斥信号量包裹保护。