🏷️ 知识点：信号量

共 14 道相关题目

模拟卷年第 24 题操作系统选择题

有一个计数信号量 S，若干个进程对 S 进行了 28 次 P 操作和 18 次 V 操作后，信号量 S 的值为 0。然后又对信号量 S 进行了 3 次 V 操作。此时有（）个进程等待在信号量 S 的队列中。

A. 2 B. 0 C. 3 D. 7

[tag_link]

正确答案：B

首先，设信号量 S 的初始值为 X。根据信号量的操作规则，P 操作会使 S 减 1，V 操作会使 S 加 1。经过 28 次 P 操作和 18 次 V 操作后，S 的值为 X - 28 + 18 = X - 10。已知此时 S 的值为 0，因此 X - 10 = 0，解得初始值 X = 10。
然后，在 S 值为 0 的情况下，又进行了 3 次 V 操作。每次 V 操作使 S 加 1，所以 S 变为 0 + 3 = 3。
在计数信号量中，当 S 的值大于或等于 0 时，表示没有进程等待在信号量的队列中。具体地，若 S > 0，表示有可用资源；若 S = 0，表示资源刚好用完且无进程等待；若 S < 0，其绝对值表示等待进程数。在 28 次 P 和 18 次 V 操作后 S = 0，说明等待队列已空。后续 3 次 V 操作使 S 变为 3，S 仍为正数，因此等待队列中依然没有进程。
故此时有 0 个进程等待在信号量 S 的队列中。

模拟卷年第 25 题操作系统选择题

N 个进程共享 M 台打印机（其中 N>M），假设每台打印机为临界资源，必须独占使用，则打印机共享的互斥信号量的取值范围为（）。

A. -(N-1)~M B. -(N-M)~M C. -(N-M)~1 D. -(N-1)~1

信号量

[tag_link]

正确答案：B

互斥信号量用于控制对临界资源的访问，初始值通常设置为可用资源的数量。

本题中有 M 台打印机，因此信号量初始值为 M，表示最初有 M 台打印机空闲可用。
当进程申请使用打印机时执行 P 操作，信号量减 1；当进程释放打印机时执行 V 操作，信号量加 1。信号量的值代表当前可用打印机的数量，如果为负数，其绝对值表示等待使用打印机的进程数。
由于进程总数 N 大于打印机数 M，在最坏情况下，所有 M 台打印机都被占用，此时信号量为 0。如果还有进程申请打印机，信号量将继续减小变为负值。最多可能有 N-M 个进程同时等待（因为 M 个进程正在使用打印机，其余 N-M 个进程等待），因此信号量的最小值为-(N-M)。
信号量的最大值出现在没有进程使用打印机时，所有 M 台打印机均空闲，此时信号量为 M。
综上，信号量的取值范围是从最小值-(N-M) 到最大值 M，对应选项 B。其他选项中，A 的等待进程数最多为 N-1，不符合实际； C 和 D 的最大值错误，应为 M 而非 1。

2010 年第 25 题操作系统选择题

设与某资源关联的信号量初值为3,当前值为1。若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M 、N分别是()。

A.0 、1 B.1 、0 C.1 、2 D.2 、0

[tag_link]

正确答案：B

信号量表示相关资源的当前可用数量。

当信号量 K>0 时，表示还有 K 个相关资源可用，所以该资源的可用个数是 1。

而当信号量 K<0 时，表示有 |K| 个进程在等待该资源。

由于资源有剩余，可见没有其他进程等待使用该资源，故进程数为 0。

模拟卷年第 26 题操作系统选择题

某系统有 3 台打印机，N 个进程共享使用。每个进程需先申请 1 台打印机，使用完毕后再释放。用 PV 操作管理时，设置信号量 S 的初值为 3，以下关于信号量 S 的叙述中，正确的是（）

A. 当前 S 的值表示系统中当前可用的打印机台数 B. 当前 S 的值表示系统中当前被占用的打印机台数 C. 当前 S 的值表示系统中当前阻塞等待打印机的进程数 D. 若当前 S 的值为 0，则一定没有进程正在使用打印机

信号量进程和线程

[tag_link]

正确答案：A

信号量 S 用于表示资源（打印机）的数量，采用**资源信号量**（或称记录型信号量）的典型用法。 > 初始时 S = 3，表示 3 台打印机都可用。 >
进程申请打印机时执行 P(S)：若 S > 0，则 S 减 1 并分配一台打印机； > 若 S = 0，则进程阻塞等待。 > 因此 **S 的当前值表示系统中当前可用的打印机数量**，A 正确。 >
B 错误，被占用的打印机数 = 3 − S。 >
C 错误，阻塞进程数由另一个等待队列记录，并不等于 S 的值（S 可能为负数，其绝对值表示阻塞进程数，但题目是记录型信号量的常规描述，一般 S 值不直接表示阻塞进程数，且通常教材中 S 的值可以小于 0，其绝对值为等待进程数，但本题强调“当前 S 的值”直接含义，应选 A）。 >
D 错误，S = 0 表示打印机已全部分配出去，可能正有多个进程在使用打印机。 >

模拟卷年第 26 题操作系统选择题

在使用信号量机制实现互斥和同步时，互斥信号量和同步信号量的初值分别为（）。

A. 0、1 B. 1、0 C. 1、1 D. 1、由用户确定

信号量

[tag_link]

正确答案：D

【解析】本题考查信号量机制。互斥信号量的初值都设置为 1，P 操作成功则将其改成 0，V 操作成功将其改成 1。实现同步时，信号量的初值应根据具体情况来确定，若期望的消息尚未产生，则对应的初值应设为 0；若期望的消息已经存在，则信号量的初值应设为一个非 0 的正整数。
注意：互斥信号量和同步信号量的区别。信号量机制是每年考题的重点，这就要求考生能在理解的基础上熟练应用和掌握信号量。

模拟卷年第 27 题操作系统选择题

有两个优先级相同的并发程序 P1 和 P2，它们的执行过程如下所示，假设当前信号量 s1=0，s2=0。当前的 z=2，进程运行结束后，x、y 和 z 的值分别是（　）。

A. 5,9,9 B. 5,9,4 C. 5,12,9 D. 5,12,4

信号量操作系统概念

[tag_link]

正确答案：C

首先分析进程同步关系。信号量 `s1` 和 `s2` 初始值为 0，因此 P2 中的 `P(s1)` 必须等待 P1 执行 `V(s1)` 后才能继续，而 P1 中的 `P(s2)` 必须等待 P2 执行 `V(s2)` 后才能继续。这强制了执行顺序：P1 必须先执行到 `V(s1)`，P2 才能执行 `P(s1)` 之后的代码； P2 必须执行到 `V(s2)`，P1 才能执行 `P(s2)` 之后的代码。
具体执行顺序如下：

P1 执行： $y = 1$ → $y = 1 + 2 = 3$ → $z = y + 1 = 3 + 1 = 4$ （覆盖初始 $z = 2$ ）→ `V(s1)` 使 $s 1 = 1$ 。 >
P1 执行 `P(s2)`，但 $s 2 = 0$ ，因此阻塞。 >
P2 执行： $x = 1$ → $x = 1 + 1 = 2$ → `P(s1)` 因 $s 1 = 1$ 而继续， $s 1 = 0$ → $x = x + y = 2 + 3 = 5$ （此时 $y = 3$ 来自 P1）→ $z = x + z = 5 + 4 = 9$ （此时 $z = 4$ 来自 P1）→ `V(s2)` 使 $s 2 = 1$ 。 >
P1 因 $s 2 = 1$ 而唤醒，执行 $y = z + y = 9 + 3 = 12$ （此时 $z = 9$ 来自 P2， $y = 3$ 来自之前）。 >

最终， $x = 5$ ， $y = 12$ ， $z = 9$ ，对应选项 C。 > 其他选项的数值与上述计算不符，因此 C 正确。 >

2018 年第 32 题操作系统选择题

在下列同步机制中，可以实现让权等待的是（）。

硬件互斥指令信号量

A. Peterson 方法 B. swap 指令 C. 信号量方法 D. TestAndSet 指令

[tag_link]

正确答案：C

硬件方法实现进程同步需要通过自旋锁，不能实现让权等待，故 B、D 错误；Peterson 算法满足有限等待但不满足让权等待，故 A 错误；记录型信号量由千引入阻塞机制，消除了不让权等待的情况，故 C 正确。

模拟卷年第 41 题数据结构综合题

（11 分）如下图所示：

（1）写出该图的邻接矩阵。

（2）写出全部拓扑序列。

（3）以 V1 为源点，以 V8 为终点，给出所有事件（和活动）允许发生的最早时间和最晚时间，并给出关键路径。

（4）求 V1 结点到各点的最短路径和距离。

信号量

[tag_link]

**【解析】** (1) 该图对应的邻接矩阵如下： $[图片] \infty \infty \infty \infty \infty \infty \infty \infty 2 \infty \infty \infty \infty \infty \infty \infty 3 \infty \infty \infty \infty \infty \infty \infty \infty 53 \infty \infty \infty \infty \infty \infty \infty 10 \infty \infty 2 \infty \infty \infty \infty \infty 4 \infty \infty \infty \infty \infty \infty \infty \infty 3 \infty \infty \infty \infty \infty \infty \infty \infty 61 \infty [图片]$

(2) 只有顶点 $V 1$ 的入度为 0，由此可以得到两个拓扑序列： $V 1, V 2, V 3, V 4, V 6, V 5, V 7, V 8$ 和 $V 1, V 3, V 2, V 4, V 6, V 5, V 7, V 8$ 。

(3) 关键路径共有 3 条，长 17。依次为： $V 1 \to V 2 \to V 4 \to V 6 \to V 8$ ， $V 1 \to V 3 \to V 5 \to V 7 \to V 8$ ， $V 1 \to V 2 \to V 4 \to V 6 \to V 5 \to V 7 \to V 8$ 。

事件	V1	V2	V3	V4	V5	V6	V7	V8
最早发生时间	0	2	3	7	13	11	16	17
最晚发生时间	0	2	3	7	13	11	16	17

活动	V2-V4	V3-V4	V3-V5	V4-V6	V6-V5	V5-V7	V6-V8	V7-V8
最早开始时间	2	3	3	7	11	13	11	16
最晚开始时间	2	4	3	7	11	13	11	16
时间余量	0	1	0	0	0	0	0	0

(4) 顶点 $V 1$ 到其他各顶点的最短路径和距离为：

$2 (V 1 \to V 2)$
$3 (V 1 \to V 3)$
$6 (V 1 \to V 3 \to V 4)$
$12 (V 1 \to V 3 \to V 4 \to V 6 \to V 5)$
$10 (V 1 \to V 3 \to V 4 \to V 6)$
$15 (V 1 \to V 3 \to V 4 \to V 6 \to V 5 \to V 7)$
$16 (V 1 \to V 3 \to V 4 \to V 6 \to V 5 \to V 7 \to V 8 或 V 1 \to V 3 \to V 4 \to V 6 \to V 8)$

模拟卷年第 41 题数据结构综合题

（10 分）下图所示是一带权有向图的邻接表。其中出边表中的每个结点均含有三个字段，依次为边的另一个顶点在顶点表中的序号、边上的权值和指向下一个边结点的指针。试求：

（1）该带权有向图的图形。（2）从顶点 V1 为起点的广度优先搜索的顶点序列及对应的生成树。（3）以顶点 V1 为起点的深度优先搜索生成树。（4）由顶点 V1 到顶点 V3 的最短路径。（5）若将该图看成无向图，用 Prim 算法给出图 G 的一棵最小生成树的生成过程。

最小生成树信号量

[tag_link]

**【解析】** (1) 该邻接表存储对应的带权有向图如下：

[图片]

(2) 以顶点 $V 1$ 为起点的广度优先搜索的顶点序列依次为 $V 1, V 2, V 4, V 6, V 3, V 5$ ，对应的生成树如下：

[图片]

(3) 生成树：顶点集合 $V (G) = {V 1, V 2, V 3, V 4, V 5, V 6}$ ，边的集合 $E (G) = {(V 1, V 2), (V 2, V 3), (V 1, V 4), (V 4, V 5), (V 5, V 6)}$ 。（图略）

(4) V1 到 V3 最短路径为 67: (V1—V4—V3)。

(5) 从 V1 点开始，第一趟寻找 V1 和点集 ${V 2, V 3, V 4, V 5, V 6}$ 之间的最小权值的边。(V5,V1)。

第二趟寻找点集 ${V 1, V 5}$ 和点集 ${V 2, V 3, V 4, V 6}$ 之间的最小权值的边。(V5,V6)。

第三趟寻找点集 ${V 1, V 5, V 6}$ 和点集 ${V 2, V 3, V 4}$ 之间的最小权值的边。(V1,V4)。

第四趟寻找点集 ${V 1, V 4, V 5, V 6}$ 和点集 ${V 2, V 3}$ 之间的最小权值的边。(V4,V2)。

第五趟寻找点集 ${V 1, V 2, V 4, V 5, V 6}$ 和点集 ${V 3}$ 之间的最小权值的边。(V2,V3)。

所以最小生成树的边集合为 ${(V 5, V 1), (V 5, V 6), (V 1, V 4), (V 4, V 2), (V 2, V 3)}$ （图形略）。

模拟卷年第 41 题数据结构综合题

（13 分）设有 $n$ 个不全为负的整型元素存储在一维数组 A[p] 中，它包含很多连续的子数组，例如数组 A = {1, -2, 3, 10, -4, 7, 2, -5}，请设计一个时间上尽可能高效的算法，求出数组 A 的子数组之和的最大值（例如数组 A 的最大的子数组为 {3, 10, -4, 7, 2}，因此输出为该子数组的和 18）。要求：

(1) 给出算法的基本设计思想。 (2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。

信号量复杂度分析

[tag_link]

**【答案】** (1) 基本设计思想：采用 Kadane 算法（动态规划思想）。遍历数组，维护两个变量：current_sum 记录以当前元素结尾的子数组的最大和，max_sum 记录全局最大子数组和。对于每个元素，若 current_sum 为负，则将其重置为当前元素值（因为负数会减小后续子数组的和），否则将当前元素加入 current_sum。然后更新 max_sum。遍历完成后，max_sum 即为所求。

(2) C 语言算法描述：

#include 
#include  // 使用 INT_MIN 初始化

int maxSubArray(int A[], int n) {
    int current_sum = 0;       // 当前子数组和
    int max_sum = INT_MIN;     // 最大子数组和，初始化为最小整数
    for (int i = 0; i < n; i++) {
        // 若当前子数组和为负，则从 A[i] 重新开始，否则累加
        if (current_sum < 0) {
            current_sum = A[i];
        } else {
            current_sum += A[i];
        }
        // 更新全局最大值
        if (current_sum > max_sum) {
            max_sum = current_sum;
        }
    }
    return max_sum;
}
`

(3) 时间复杂度：O(n)，其中 n 为数组长度，仅需一次遍历。空间复杂度：O(1)，仅使用常数个辅助变量。

**【解析】** 该算法基于动态规划，核心是确定以每个元素结尾的最大子数组和。设以元素 A[i] 结尾的最大子数组和为 f(i)，则状态转移方程为：f(i) = max(A[i], f(i-1) + A[i])。这是因为如果 f(i-1) 为负，其对 A[i] 无增益，故从 A[i] 重新开始；否则累加。算法中的 current_sum 即 f(i)，max_sum 记录所有 f(i) 的最大值。由于数组不全为负，max_sum 至少为非负，但算法也适用于全负情况。遍历一次即可求得结果，因此时间效率高，且仅需常数空间。

模拟卷 年第 45 题
操作系统
综合题

（8 分）在一间酒吧里有 3 个音乐爱好者队列，第 1 队的音乐爱好者只有随身听，第 2 队只有音乐磁带，第 3 队只有电池。而要听音乐就必须随身听、音乐磁带和电池这 3 种物品俱全。酒吧老板一次出售这 3 种物品中的任意两种。当一名音乐爱好者得到这 3 种物品并听完一首乐曲后，酒吧老板才能再一次出售这 3 种物品中的任意两种。于是第 2 名音乐爱好者得到这 3 种物品，并开始听乐曲。全部买卖就这样进行下去。试用 P、V 操作正确解决这一买卖。

信号量

[tag_link]

本题考查用 PV 操作解决进程的同步互斥问题。

第 1 队音乐爱好者要竞争“待出售的音乐磁带和电池”，而且在初始状态下，系统并无“待出售的音乐磁带和电池”，故可为该种资源设置一初值为 0 的信号量 `buy1`；同样，需设置初值为 0 的 `buy2`、`buy3` 分别对应“待出售的随身听和电池”、“待出售的随身听和音乐磁带”。另外，为了同步买者的付费动作和卖者的给货动作，还需设置信号量 `payment` 和 `goods`，以保证买者在付费后才能得到所需商品。信号量 `music_over` 用来同步音乐爱好者听乐曲和酒吧老师的下一次出售行为。具体的算法描述如下：

semaphore buy1 = buy2 = buy3 = 0;
semaphore payment = 0;
semaphore goods = 0;
semaphore music_over = 0;

cobegin {
    process boss() {                    // 酒吧老板
        while (TRUE) {
            拿出任意两种物品出售；
            if (出售的是音乐磁带和电池)   V(buy1);
            else if (出售的是随身听和电池) V(buy2);
            else if (出售的是随身听和音乐磁带) V(buy3);

            P(payment);                  // 等待付费
            V(goods);                    // 给货
            P(music_over);               // 等待乐曲结束
        }
    }

    process fan1() {                    // 第1队音乐爱好者
        while (TRUE) {                  // 因为一个进程代表一队，而不是一个爱好者，
                                        // 所以这里是 while(true)，下同
            P(buy1);                    // 等有音乐磁带和电池出售
            V(payment);                 // 付费
            P(goods);                   // 取货
            欣赏一曲乐曲；
            V(music_over);              // 通知老板乐曲结束
        }
    }

    process fan2() {                    // 第2队音乐爱好者
        while (TRUE) {
            P(buy2);                    // 等有随身听和电池出售
            V(payment);                 // 付费
            P(goods);                   // 取货
            欣赏一曲乐曲；
            V(music_over);              // 通知老板乐曲结束
        }
    }

    process fan3() {                    // 第3队音乐爱好者
        while (TRUE) {
            P(buy3);                    // 等有随身听和音乐磁带出售
            V(payment);                 // 付费
            P(goods);                   // 取货
            欣赏一曲乐曲；
            V(music_over);              // 通知老板乐曲结束
        }
    }
}
coend
`

模拟卷 年第 45 题
操作系统
综合题

（7 分）一个主修动物行为学、辅修计算机科学的学生参加了一个课题。调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索（假设为南北方向），这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向，同

一时刻可以有多只猴子通过。但是如果是相反的方向上同时有猴子通过则会发生死锁（这些猴子将被卡在绳索中间，假设这些猴子无法在绳索上从另一只猴子身上翻过去）。如果一只猴子想越过峡谷，它必须看当前是否有别的猴子在逆向通过。请用 P、V 操作来解决该问题。

信号量操作系统概念

[tag_link]

**【答案】** 信号量定义：

mutex：初值为 1，用于保护共享变量。
rope：初值为 1，用于控制绳索的访问。

共享变量：

SN_count：从南向北的猴子数量，初值为 0。
NS_count：从北向南的猴子数量，初值为 0。

`semaphore mutex = 1;
semaphore rope = 1;
semaphore SN_count = 0;
semaphore NS_count = 0;
`

从南向北的猴子执行以下操作：

`south_monkey() {
    P(mutex)
    SN_count++
    if (SN_count == 1) P(rope)
    V(mutex)
// 通过绳索

P(mutex)
SN_count--
if (SN_count == 0) V(rope)
V(mutex)
}
`

从北向南的猴子执行以下操作：

`north_monkey() {
    P(mutex)
    NS_count++
    if (NS_count == 1) P(rope)
    V(mutex)

    // 通过绳索

    P(mutex)
    NS_count--
    if (NS_count == 0) V(rope)
    V(mutex)
}
`

**【解析】**

该问题本质上是单车道桥梁同步问题的变体，需要防止两个方向的猴子同时使用绳索导致死锁，同时允许同一方向的多只猴子共享绳索。使用 P、V 操作（信号量）来实现同步。

首先，定义信号量 mutex 用于互斥访问共享变量 SN_count 和 NS_count，确保计数操作原子性。信号量 rope 用于控制绳索的访问权限，初值为 1 表示绳索空闲。

对于从南向北的猴子：当第一只猴子到达时，在 mutex 保护下增加 SN_count，由于 SN_count 从 0 变为 1，它执行 P(rope) 获取绳索访问权，阻止北向南的猴子进入。之后释放 mutex，允许其他南向北猴子进入，它们增加 SN_count 但不会再次 P(rope)，因此同一方向多只猴子可以同时通过绳索。当猴子通过后，在 mutex 保护下减少 SN_count，如果 SN_count 变为 0，表示该方向没有猴子了，则执行 V(rope) 释放绳索访问权，允许另一方向猴子使用。

对于从北向南的猴子，操作对称：第一只猴子获取 rope，后续猴子共享访问，最后一只猴子释放 rope。

这种设计确保：只要有一个方向的猴子在使用绳索，rope 信号量就被持有，另一方向的猴子会在执行 P(rope) 时阻塞，直到当前方向所有猴子离开并释放 rope。因此，相反方向的猴子不会同时通过，避免了死锁。同一方向的猴子可以共享绳索，符合问题要求。整个过程通过 P、V 操作实现了同步，且不会产生饥饿，除非一个方向持续有猴子到达，但问题未要求公平性，故解法可行。

2017 年第 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()）操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。

信号量

[tag_link]

先找出线程对在各个变量上的互斥、并发关系。如果是一读一写或两个都是写，那么这就是互斥关系。每一个互斥关系都需要一个信号量进行调节。

// 冲突：
// t1 和 t3 关于 y 有读写冲突
// t2 和 t3 关于 y, z 都有读写冲突

// 解决 t1 和 t3 关于 y 读写冲突
semaphore y_mutex1 = 1;

semaphore y_mutex2 = 1;
semaphore z_mutex = 1;


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

thread1()
{
  cnum w;
  // 读 x, y
  P(y_mutex1);
  w = add(x, y);
  V(y_mutex1);
  // ...
}

thread2()
{
  cnum w;
  // 读 y, z
  P(z_mutex);
  P(y_mutex2);
  w = add(y, z);
  V(y_mutex2);
  V(z_mutex);
  // ...
}

thread3()
{
  cnum w;
  w.a = 1;
  w.b = 1;
  // 写 z
  P(z_mutex);
  z = add(z, w);
  V(z_mutex);
  // 写 y
  P(y_mutex1);
  P(y_mutex2);
  y = add(y, w);
  V(y_mutex2);
  V(y_mutex1);
  // ...
}

【评分标准】① 各线程与变量之间的互斥、并发情况及相应评分见下表。

变量/线程对	thread1 和 thread2	thread2 和 thread3	thread3 和 thread4	给分
x	不共享	不共享	不共享	1 分
y	同时读	读写互斥	读写互斥	3 分
z	不共享	读写互斥	不共享	1 分

② 考生仅使用一个互斥信号量，互斥代码部分的得分最多给 2 分。③ 答案部分正确，酌情给分。

2024 年第 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 分）

进程概念信号量

[tag_link]

1）是的，实现 C1 的代码可以被视为临界区。临界区是指在并发编程中，当多个进程同时访问和修改共享数据时，必须进行互斥访问的代码区域。在这个例子中，进程 P1 和 P2 都需要执行 C1，即它们都需要将一个数据分组写入缓冲区 B。如果这两个进程同时执行 C1，那么它们可能会试图同时写入数据分组，这可能会导致数据的不一致性。因此，我们需要确保在任何时刻，只有一个进程可以执行 C1。这就需要将执行 C1 的代码区域定义为临界区，并使用适当的同步机制（如互斥锁或信号量）来保证在同一时刻只有个进程可以进入临界区。所以，实现 C1 的代码是临界区，因为它涉及到对共享资源（在这里是缓冲区 B) 的修改，而这个修改需要被同步，以防止数据的不一致性。

2）在这个问题中，我们可以使用两个信号量：一个用于保护缓使区 B（我们称之为 mutex），另一个用于同步进程 PI 和 P2（我们称之为 full）。mutex 用于确保在同一时刻只有一个进程可以访问缓冲区 B，而 full 用于表示缓冲区 B 是否已满。初始时，mutex 的值为 1，表示缓冲区 B 是可用的：fu1I 的值为 0，表示缓冲区 B 是空的。以下是进程 P1 和 P2 的代码：

semaphore mutex = 1;
semaphore full = 0;

// 进程 P1
P1() {
    wait(mutex);    // 请求访问缓冲区 B
    执行 C1，将一个数据分组写入 B 中
    signal(mutex);  // 释放缓冲区 B 的使用权
    signal(full);   // 表示缓冲区 B 已满
}

// 进程 P2
P2() {
    wait(full);     // 等待缓冲区 B 变满
    wait(mutex);    // 请求访问缓冲区 B
    执行 C1，从 B 中读出一个数组分组
    signal(mutex);  // 释放缓冲区 B 的使用权
}

在这个代码中，wait() 操作表示请求一个信号量，如果信号量的值大于 0，那么就将其减 1：如果信号量的值为 0，那么就阻塞，直到信号量的值大于 0。signal() 操作表示释放一个信号量，将其值加 1。

3）在这个问题中，我们可以使用一个信号量：一个用于保护缓冲区 B（我们称之为 mutex）。mutex 用于确保在同一时刻只有一个进程可以访问缓冲区 B。初始时，mutex 的值为 1，表示缓冲区 B 是可用的。以下是进程 P1 和 P2 的代码：

semaphore mutex=1;

// 进程 P1
P1() {
    wait(mutex);     // 请求访问缓冲区 B
    执行 C3,对 B 中的数据分组进行修改
    signal(mutex);   // 释放对缓冲区 B 的访问
}
// 进程 P2
P2() {
    wait(mutex);     // 请求访问缓冲区 B
    执行 C3,对 B 中的数据分组进行修
    signal(mutex);   // 释放对缓冲区 B 的访问
}

在这个代码中，wait() 操作表示请求一个信号量，如果信号量的值大于 0，那么就将其减 1；如果信号量的值为 0，那么就阻塞，直到信号量的值大于 0。signal() 操作表示释放一个信号量，将其值加 1。所以，实现 C3 的代码是临界区，因为它涉及到共享资源（在这里是缓冲区 B）的修改，而这个修改需要被同步，以防止数据的不一致性。

← 返回真题分析