是什么
-
定义:临界资源是一段时间内只允许一个进程访问的物理或逻辑资源;临界区是每个进程中访问临界资源的代码段。操作系统利用信号量机制及
wait()(P操作)与signal()(V操作)原语,协调多个并发进程对临界资源的互斥访问(无序独占)与同步推进(依赖时序)。 -
大白话:互斥就是“同一个马桶同一时间只能一个人用,进去先锁门,出来再开门”;同步就是“炒菜和吃饭,必须先等菜炒好端上桌,后一个人才能动筷子”。
核心内容
1. 核心概念对比
| 概念 | 本质属性 | 核心特征 / 采分关键词 | 考场实例 |
|---|---|---|---|
| 临界资源 | 物理/逻辑实体 | 一段时间内只允许一个进程独占访问 | 打印机、共享变量 count、共享缓冲区 B |
| 临界区 | 程序代码段 | 进程中访问临界资源的那段代码,进前检查、出后释放 | buffer[in] = x;、count++; |
| 互斥关系 | 间接制约 | 非此即彼,没有先后顺序要求 | 两个进程都要向缓冲区写数据 |
| 同步关系 | 直接制约 | 先后顺序,前驱完成才能触发后继 | 先生产数据后消费数据 |
2. PV 操作万能解题 5 步流水线
-
找进程实体:找出题目中所有独立的并发操作主体,为每个实体定义独立函数(如
Producer()、Consumer()或P1()、P2()),并核对是否为while(1)持续循环或仅执行一次。 -
辨识关系与定初值:
-
互斥信号量:多个进程争夺独占资源。初值一般设为
mutex = 1。 -
同步信号量:存在依赖时序或容量限制。空闲量初值设为
empty = N,已有量初值设为full = 0。
-
-
卷首规范声明:集中写明信号量类型、初值及其物理意义。
-
组装代码骨架:
-
互斥操作:先 P 后 V 夹中间(在同一进程内包裹临界区)。
-
同步操作:前 V 后 P 跨进程(前驱事件结束执行
V(S)通知,后继事件开始前执行P(S)等待)。 -
嵌套原则:先同步 P,后互斥 P(先看是否有资格/资源,再拿互斥锁进临界区)。
-
-
死锁与变量自检:检查是否存在嵌套倒置导致的死锁,以及普通整型计数变量是否被锁保护。
例题
类型一:生产者-消费者模型(带容量缓冲区)
-
题目:某网络系统中缓冲区 B 用于存放一个数据分组,对 B 的操作有 C1(写)、C2(读)和 C3(改)。要求 B 为空时才能执行 C1,B 非空时才能执行 C2 和 C3。
-
假设进程 P1 和 P2 均需执行 C1,实现 C1 的代码是否为临界区?为什么?
-
假设 B 初始为空,进程 P1 执行 C1 一次,进程 P2 执行 C2 一次。请定义尽可能少的信号量,描述 P1、P2 的同步或互斥关系,说明信号量作用及初值。
-
假设 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--等整型计数器,它们并非硬件原子操作,必须单独用互斥信号量包裹保护。