题目

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

解析

答案：C. 信号量方法

本题考查同步机制是否满足 “让权等待”（Wait & Yield） 原则。

🔹 什么是“让权等待”？

当进程申请临界资源失败（如进入区失败）时，主动放弃 CPU（阻塞自己），进入等待队列，不占用处理机空转；
与之相对的是 “忙等待（Busy Waiting）”：进程循环测试条件，持续占用 CPU，浪费资源。

逐项分析：

A. Peterson 方法

❌ 忙等待

纯软件算法，通过 flag[] 和 turn 变量实现互斥；
进入临界区前循环检查条件：while (flag[j] && turn == j);
持续占用 CPU，不释放处理器 → 不满足让权等待。

B. swap 指令

❌ 忙等待

swap 是原子交换指令，常用于实现自旋锁（Spinlock）；
典型用法：
1
while (swap(&lock, 1) == 1); // 忙等
同样循环测试，不放弃 CPU → 忙等待。

C. 信号量方法

✅ 让权等待

信号量（Semaphore）由 Dijkstra 提出，标准实现包含：

wait(S) {
    S.value--;
    if (S.value < 0) {
        block();   // 阻塞当前进程，放入等待队列
    }
}
signal(S) {
    S.value++;
    if (S.value <= 0) {
        wakeup();  // 唤醒一个等待进程
    }
}

当 S.value < 0 时，进程主动阻塞（放弃 CPU），由 OS 调度器切换到其他进程；
恢复由其他进程 signal() 时唤醒；
→ 满足让权等待。

D. TestAndSet 指令

❌ 忙等待

硬件原子指令，用于实现自旋锁：

1	while (TestAndSet(&lock)); // 循环测试，直到为0

典型用于多核系统短临界区，但仍是忙等待；
不涉及进程阻塞/唤醒机制。

🎯 考点总结：

同步机制	是否让权等待	原因
Peterson	❌	纯软件忙等
swap / TAS	❌	自旋锁，忙等
信号量	✅	失败时 `block()`，进入阻塞态
管程（Monitor）	✅	条件变量 `wait()` 会阻塞

⚠️ 注意：信号量的具体实现可能有差异，但标准定义和教学语境下，信号量是支持让权等待的典型机制。

✅ 正确答案：C. 信号量方法

题目

下列准则中实现临界区互斥机制必须遵循的是

I、两个进程不能同时进入临界区
II、允许进程访问空闲的临界资源
III、进程等待进入临界区的时间是有限的
IV、不能进入临界区的执行态进程立即放弃 CPU
A. 仅Ⅰ、Ⅳ B. 仅Ⅱ、Ⅲ C. 仅Ⅰ、Ⅱ、Ⅲ D. 仅Ⅰ、Ⅲ、Ⅳ

解析

答案：C. 仅Ⅰ、Ⅱ、Ⅲ

本题考查 临界区互斥机制必须满足的基本准则（也称 Petri 准则或并发控制四原则）。

标准四条准则为：

互斥（Mutual Exclusion）：不能有两个或以上进程同时在临界区内；
有空让进（Progress）：若无进程在临界区，且有进程希望进入，则不应无限推迟其进入；
有限等待（Bounded Waiting）：任一进程从提出请求到进入临界区的等待时间有上界；
让权等待（可选，非必须）：等待进程应释放 CPU（阻塞），避免忙等待 —— 这是性能/实现要求，非正确性必要条件。

逐项对应题干：

I. 两个进程不能同时进入临界区

✅ 必须遵循 —— 对应 互斥原则，是临界区定义的核心。

II. 允许进程访问空闲的临界资源

✅ 必须遵循 —— 对应 有空让进（Progress）：若临界区空闲，不应阻止进程进入（即不能因调度策略导致“假死”）。

III. 进程等待进入临界区的时间是有限的

✅ 必须遵循 —— 对应 有限等待：防止饥饿（Starvation），确保公平性；若等待可无限长，则系统可能活锁或不公平。

IV. 不能进入临界区的执行态进程立即放弃 CPU

❌ 非必须遵循

这是 “让权等待” 的要求，属于实现优化，非正确性前提；
例如 Peterson 算法、TestAndSet 自旋锁 都是忙等待（不放弃 CPU），但仍能正确实现互斥；
在单处理机系统或短临界区场景下，忙等待可接受；
是否让权，取决于 OS 设计，不影响互斥机制的逻辑正确性。

🎯 考点总结：

准则	是否必须	说明
互斥（I）	✅ 是	核心要求
有空让进（II）	✅ 是	避免无谓阻塞
有限等待（III）	✅ 是	防止饥饿
让权等待（IV）	❌ 否	属于性能/实现策略

📚 参考：《操作系统概念》（Silberschatz）—— 临界区问题的三条件：Mutual Exclusion, Progress, Bounded Waiting
（注意：书中明确指出，忙等待算法可满足前三者，但违反“非忙等待”这一额外期望）

✅ 正确答案：C. 仅Ⅰ、Ⅱ、Ⅲ

题目

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

。(2010)
A．0、1 B．1、0 C．1、2 D．2、0

解析

答案：B．1、0

本题考查 信号量物理意义的理解。

设某类资源有 多个实例（如打印机、缓冲区），用计数信号量（Counting Semaphore） 管理。

信号量的值 S 表示：当前可用资源数（若 S ≥ 0）；
若 S < 0，则 |S| 表示等待该资源的进程数。

更精确地说：

$$
\begin{cases}
S > 0 &\Rightarrow \text{有 } S \text{ 个资源空闲}，\text{无进程等待} \
S = 0 &\Rightarrow \text{资源刚好用完}，\text{无进程等待} \
S < 0 &\Rightarrow \text{无空闲资源}，\text{有 } |S| \text{ 个进程阻塞等待}
\end{cases}
$$

题目条件：

信号量初值 = 3 → 系统共有 3 个该类资源
当前值 = 1

→ 因为 1 > 0，所以：

可用资源数 M = 1
等待进程数 N = 0

🔍 验证过程：

初始：S = 3（3 个空闲资源）
某进程执行 wait()（P 操作）：S = 2
再一个 wait()：S = 1
→ 此时 2 个资源已被占用，1 个空闲，无等待进程。

即：

已分配资源数 = 初值 − 当前值 = 3 − 1 = 2
可用资源 M = 当前值 = 1（因 S > 0）
等待进程 N = max(0, −S) = 0

❌ 排除干扰选项：

A（0,1）：对应 S = −1（1 个等待，0 个空闲）
C（1,2）：矛盾（有 1 个空闲，怎会 2 个等待？）
D（2,0）：对应 S = 2

🎯 考点总结：

信号量值 = 可用资源数（当 ≥ 0）
等待进程数 = max(0, −S)
资源总数 = 初值 = 可用 + 已分配
已分配 = 初值 − max(S, 0)

✅ 正确答案：B．1、0

题目

使用TSL(Test and Set Lock)指令实现进程互斥的伪代码如下所示。
do {
……
while(TSL(&lock))；
critical section；
lock=FALSE；
……
} while(TRUE)；
下列与该实现机制相关的叙述中，正确的是

A．退出临界区的进程负责唤醒阻塞态进程
B．等待进入临界区的进程不会主动放弃CPU
C．上述伪代码满足“让权等待”的同步准则
D．while(TSL(&lock))语句应在关中断状态下执行

解析

答案：B．等待进入临界区的进程不会主动放弃CPU

本题考查 TSL（Test-and-Set Lock）指令实现的互斥机制特性。

给出的伪代码是典型的自旋锁（Spinlock） 实现：

do {
    ...
    while (TSL(&lock));   // 忙等待：反复测试并设置 lock
    critical section;
    lock = FALSE;         // 退出临界区，释放锁
    ...
} while (TRUE);

其中 TSL(&lock) 是原子操作，等价于：

bool TSL(bool *lock) {
    bool old = *lock;
    *lock = TRUE;
    return old;   // 返回原值：若原为 FALSE（未锁），返回 FALSE，退出循环
}

即：只有当 lock 原为 FALSE 时，TSL 返回 FALSE，循环结束，进程进入临界区。

逐项分析选项：

A．退出临界区的进程负责唤醒阻塞态进程

❌ 错误。

TSL 实现的是忙等待，等待进程处于运行态（就绪/执行），并非阻塞态；
它们在 while 循环中不断执行 TSL，持续占用 CPU；
退出时只需 lock = FALSE，无需唤醒操作（无进程在等待队列中）；
唤醒机制存在于信号量、管程等阻塞式同步机制中，TSL 不具备。

B．等待进入临界区的进程不会主动放弃CPU

✅ 正确。

while (TSL(&lock)); 是一个空循环，进程反复测试 lock 状态；
只要 lock == TRUE，就继续循环，不调用 sleep、yield 或 block；
因此，CPU 一直被该进程占用，属于典型的忙等待（Busy Waiting）；
→ 符合 TSL/自旋锁的本质特征。

C．上述伪代码满足“让权等待”的同步准则

❌ 错误。

“让权等待”要求：进程等待时主动释放 CPU（进入阻塞态）；
而本代码是忙等待，违反让权等待；
满足“让权等待”的是信号量、条件变量等机制。

D．`while(TSL(&lock))`语句应在关中断状态下执行

❌ 错误。

TSL 是硬件提供的原子指令，其执行本身是不可中断的（原子性由 CPU 保证）；
不需要关中断；
关中断用于保护临界区本身（如修改内核数据结构），而非用于 TSL 测试；
若关中断执行长时间忙等待，会导致系统无法响应时钟中断，丢失调度，极其危险！

✅ 正确做法：TSL 本身是原子的，可开中断执行；但临界区若涉及内核数据，需关中断或使用更高级同步。

🎯 考点总结：

机制	是否忙等待	是否让权等待	是否需唤醒	典型场景
TSL / TAS / Swap	✅ 是	❌ 否	❌ 否	多核短临界区、内核自旋锁
信号量（block/wakeup）	❌ 否	✅ 是	✅ 是	用户态长临界区
Peterson 算法	✅ 是	❌ 否	❌ 否	单处理机软件互斥

✅ 正确答案：B

题目

下列关于管程的叙述中，错误的是______
。(2016)
A．管程只能用于实现进程的互斥
B．管程是由编程语言支持的进程同步机制
C．任何时候只能有一个进程在管程中执行
D．管程中定义的变量只能被管程内的过程访问

解析

答案：A．管程只能用于实现进程的互斥

本题考查对 管程（Monitor） 概念的理解。

管程是一种高级同步机制，由 Hoare 和 Brinch Hansen 提出，广泛用于操作系统和编程语言（如 Java 的 synchronized 基于管程思想）。

我们逐项分析：

A．管程只能用于实现进程的互斥

❌ 错误（本题答案）

管程不仅能实现互斥，更能实现进程同步（协作）；
关键在于 条件变量（condition variable）：
- wait(cv)：释放管程锁 + 阻塞进程
- signal(cv) / notify(cv)：唤醒等待进程
典型应用：
- 生产者-消费者问题
- 读者-写者问题
- 哲学家进餐问题
  → 管程是互斥 + 同步的统一机制，A 说法片面，错误。

B．管程是由编程语言支持的进程同步机制

✅ 正确

管程通常由语言层面提供语法支持：
- Pascal 的 monitor 关键字（早期）
- Java 的 synchronized 方法/块 + wait()/notify()
- C# 的 lock + Monitor 类
编译器/运行时负责生成进入/退出管程的同步代码；
→ 不同于信号量（需程序员手动调用 P/V），管程是语言级抽象。

C．任何时候只能有一个进程在管程中执行

✅ 正确

管程的核心语义：

“At most one process can be active in the monitor at a time.”
管程自带一个隐式互斥锁（mutex）：
- 进程进入管程内任何过程前，必须先获得锁；
- 退出时自动释放锁；
即使有多个条件变量，也只允许一个进程在管程内执行代码（调用 wait() 时会临时释放锁，但不算“执行中”）。

D．管程中定义的变量只能被管程内的过程访问

✅ 正确

这是管程的封装性（Encapsulation） 特征；
管程内部的共享变量（如 buffer、count）是私有（private） 的；
外部进程只能通过管程提供的入口过程（entry procedure） 间接访问；
→ 避免了竞争条件，保证数据一致性。

🎯 考点总结：

特性	说明
功能	互斥 + 同步（A 错在“只能互斥”）
实现层级	语言支持（B 正确）
并发控制	任一时刻最多一个进程活跃（C 正确）
数据封装	内部变量私有，仅通过过程访问（D 正确）

✅ 正确答案：A

题目

.进程P1和P2均包含并发执行的线程，部分伪代码描述如下所示。
下列选项中，需要互斥执行的操作是______
。(2016)
A．a=1与a=2 B．a=x与b=x
C．x+=1与x+=2 D．x+=1与x+=3

伪代码：

进程 P1：

int x=0;
Thread1() {
    int a;
    a=1;  x+=1;
}
Thread2() {
    int a;
    a=2;  x+=2;
}

进程 P2：

int x=0;
Thread3() {
    int a;
    a=x;  x+=3;
}
Thread4() {
    int b;
    b=x;  x+=4;
}

解析

注意：x 是全局共享变量（每个进程内定义一个 x，但 P1 和 P2 的 x 不共享；但在每个进程中，多个线程共享该进程内的 x）。

题目问：“需要互斥执行的操作” —— 即哪些操作对共享变量 x 的访问可能产生竞态条件（Race Condition），需加锁保护。

我们看每个选项：

A. `a=1` 与 `a=2`

a 是局部变量，每个线程有自己的栈空间 → 不共享
→ 无竞争 → ❌ 不需要互斥

B. `a=x` 与 `b=x`

在 P2 中：
- Thread3: a = x （读 x）
- Thread4: b = x （读 x）
两个都是读操作，即使并发执行，也不会破坏数据一致性（只要没有写入）
→ 无竞态 → ❌ 不需要互斥

C. `x+=1` 与 `x+=2`

在 P1 中：
- Thread1: x += 1
- Thread2: x += 2
x += n 是复合操作（读取 x → 计算 x+n → 写回 x），非原子操作

若并发执行，可能发生：

1 2	Thread1: 读 x=0 → 计算 0+1=1 → 写回 x=1 Thread2: 读 x=0 → 计算 0+2=2 → 写回 x=2 ← 覆盖了 Thread1 的结果！

→ 最终 x = 2，而不是期望的 3 → 竞态条件
✅ 需要互斥

D. `x+=1` 与 `x+=3`

x+=1 在 P1，x+=3 在 P2
P1 和 P2 是不同进程，各自有独立的 x 变量（进程间内存隔离）
→ 不共享同一个 x → 无竞争
❌ 不需要互斥

✅ 正确答案：C. x+=1 与 x+=2

题目

属于同一进程的两个线程 thread1 和 thread2 并发执行，共享初值为 0 的全局变量 x。 thread1 和 thread2 实现对全局变量 x 加 1 的机器级代
码描述如下,在所有可能的指令执行序列中，使 x 的值为 2 的序列个数是______
。(2018)
A. 1 B. 2 C.3 D.4

解析

我们来分析这道经典的并发线程竞态条件题目。

📜 题目描述：

同一进程内有两个线程：thread1 和 thread2
共享全局变量 x，初始值为 0
每个线程执行“对 x 加 1”的操作，用机器级指令实现：
- mov R, x → 将 x 的值读入寄存器
- inc R → 寄存器值加 1
- mov x, R → 将寄存器值写回 x

目标：在所有可能的指令交错序列中，有多少种序列最终使 x = 2？

✅ 关键点：

虽然每个线程都在做“x++”，但由于是非原子操作（三步），若两个线程交错执行，可能导致丢失更新，最终 x 可能为 1 或 2。

我们需要枚举所有可能的指令交错序列，并统计哪些最终得到 x = 2。

🔢 总指令数：

thread1：3 条指令（记为 A1, A2, A3）
thread2：3 条指令（记为 B1, B2, B3）
→ 总共 6 条指令，从中选 3 个位置给 thread1，其余给 thread2 → 总序列数 = $ \binom{6}{3} = 20 $ 种

但并非所有 20 种都导致不同结果 —— 我们只需关注最终 x 的值。

✅ 正确结果：x=2 当且仅当两个线程的写操作没有覆盖对方的结果

即：两个线程都成功将自己计算后的值写回 x，且没有被对方覆盖。

这要求：两个线程的“写回”指令（A3 和 B3）必须发生在对方“读取”之后、或不干扰彼此。

🧩 枚举关键情况：

我们用简写表示：

A1: mov R1, x
A2: inc R1
A3: mov x, R1
B1: mov R2, x
B2: inc R2
B3: mov x, R2

我们要找的是：最终 x=2 的序列。

🎯 情况 1：无交错（完全串行）

1. A1→A2→A3→B1→B2→B3

A 读 0 → 加 1 → 写 1
B 读 1 → 加 1 → 写 2
→ x=2 ✅

2. B1→B2→B3→A1→A2→A3

B 读 0 → 加 1 → 写 1
A 读 1 → 加 1 → 写 2
→ x=2 ✅

→ 2 种序列

🎯 情况 2：部分交错，但写操作未被覆盖

3. A1→B1→A2→B2→A3→B3

A 读 0
B 读 0
A 加 1 → R1=1
B 加 1 → R2=1
A 写 1 → x=1
B 写 1 → x=1 ❌ → 最终 x=1

4. A1→B1→A2→A3→B2→B3

A 读 0
B 读 0
A 加 1 → R1=1
A 写 1 → x=1
B 加 1 → R2=1
B 写 1 → x=1 ❌

5. A1→B1→B2→A2→A3→B3

A 读 0
B 读 0
B 加 1 → R2=1
A 加 1 → R1=1
A 写 1 → x=1
B 写 1 → x=1 ❌

6. A1→A2→B1→B2→A3→B3

A 读 0 → 加 1 → R1=1
B 读 0 → 加 1 → R2=1
A 写 1 → x=1
B 写 1 → x=1 ❌

7. A1→A2→B1→A3→B2→B3

A 读 0 → 加 1 → R1=1
B 读 0 → R2=0
A 写 1 → x=1
B 加 1 → R2=1
B 写 1 → x=1 ❌

8. B1→A1→B2→A2→B3→A3

B 读 0
A 读 0
B 加 1 → R2=1
A 加 1 → R1=1
B 写 1 → x=1
A 写 1 → x=1 ❌

9. B1→A1→B2→B3→A2→A3

B 读 0
A 读 0
B 加 1 → R2=1
B 写 1 → x=1
A 加 1 → R1=1
A 写 1 → x=1 ❌

10. B1→B2→A1→A2→B3→A3

B 读 0 → 加 1 → R2=1
A 读 0 → 加 1 → R1=1
B 写 1 → x=1
A 写 1 → x=1 ❌

🎯 唯一能使 x=2 的情况：

只有当一个线程写完后，另一个线程再读取该值，才能叠加。

即：

✅ 序列 1：A1→A2→A3→B1→B2→B3

A 写 1 → B 读 1 → 加 1 → 写 2

✅ 序列 2：B1→B2→B3→A1→A2→A3

B 写 1 → A 读 1 → 加 1 → 写 2

✅ 序列 3：A1→B1→B2→B3→A2→A3

A 读 0
B 读 0 → 加 1 → 写 1
A 加 1 → R1=1
A 写 1 → x=1 ❌

等等 —— 等等！有没有第三种？

让我们思考：

如果线程1先读 x=0，然后线程2完成全部操作（读0→加1→写1），然后线程1再加1→写1 → x=1 ❌

除非线程1在写之前，线程2已经写过，但线程1仍保留旧值。

所以唯一能让 x=2 的是：

两个线程的“读取”操作发生在不同的时间点，且后写的线程读到了前一个线程写入的值。

也就是说：

要么 A 先写，B 后读；
要么 B 先写，A 后读。

但注意：只要有一个线程在另一个线程写入后读取，就能得到 2。

🧠 正确方法：枚举所有 20 种序列，统计 x=2 的数量

我们用更系统的方法：

最终 x=2 的充要条件是：两个线程的写操作都没有被覆盖，即：

两个线程都成功将“自己的 +1 结果”写回 x，且没有被对方覆盖。

这要求：两个写操作（A3 和 B3）之间，不能有“读取+写入”的完整序列覆盖。

实际上，只有两种情况满足：

A 完整执行完毕（A1→A2→A3），然后 B 执行（B1→B2→B3）
B 完整执行完毕（B1→B2→B3），然后 A 执行（A1→A2→A3）

→ 这就是我们之前说的 2 种。

但等等 —— 还有一种可能：

✅ 序列 3：A1→A2→B1→B2→B3→A3

A 读 0 → 加 1 → R1=1
B 读 0 → 加 1 → R2=1
B 写 1 → x=1
A 写 1 → x=1 ❌

不行。

✅ 序列 4：A1→B1→A2→B2→B3→A3

A 读 0
B 读 0
A 加 1 → R1=1
B 加 1 → R2=1
B 写 1 → x=1
A 写 1 → x=1 ❌

还是 1。

🚫 有没有第三种？

考虑：

✅ 序列：A1→B1→B2→A2→B3→A3

A 读 0
B 读 0
B 加 1 → R2=1
A 加 1 → R1=1
B 写 1 → x=1
A 写 1 → x=1 ❌

还是 1。

💡 突破点：

其实，只有当一个线程的写操作发生在另一个线程的读操作之后，并且该读操作读到了前一个线程写入的值，才能叠加。

例如：

✅ 序列：A1→A2→A3→B1→B2→B3 → x=2

✅ 序列：B1→B2→B3→A1→A2→A3 → x=2

✅ 序列：A1→B1→B2→B3→A2→A3 → x=1 ❌

✅ 序列：B1→A1→A2→A3→B2→B3 → x=1 ❌

等等。

我们发现：只有完全串行的两种情况能得到 x=2。

但等等！看这个：

✅ 序列：A1→B1→A2→B2→A3→B3

A 读 0
B 读 0
A 加 1 → R1=1
B 加 1 → R2=1
A 写 1 → x=1
B 写 1 → x=1 ❌

还是 1。

📊 实际答案（参考标准解答）：

在所有 20 种可能的指令交错中，只有 2 种序列能得到 x=2：

A1→A2→A3→B1→B2→B3
B1→B2→B3→A1→A2→A3

其他 18 种都会导致 x=1。

✅ 正确答案：B. 2

🎯 考点总结：

“x++” 不是原子操作 → 并发时易发生丢失更新；
最终 x=2 仅当两个线程的写操作不互相覆盖，即一个线程写入后，另一个线程读到该值再写入；
这在指令交错中只发生在完全串行的情况下（2 种）。

✅ 正确答案：B. 2

题目

若 x 是管程内的条件变量，则当进程执行 x.wait() 时所做的工作是______
。(2018)
A. 实现对变量 x 的互斥访问
B. 唤醒一个在 x 上阻塞的进程
C. 根据 x 的值判断该进程是否进人阻塞状态
D. 阻塞该进程，并将之插入 x 的阻塞队列中

解析

答案：D. 阻塞该进程，并将之插入 x 的阻塞队列中

本题考查 管程中条件变量 wait() 操作的语义。

在管程（Monitor）中：

管程本身保证任一时刻最多一个进程在管程中执行（通过隐式互斥锁）；
条件变量（condition variable） 用于实现进程同步与协作（非互斥），典型如：
- x.wait()：当前进程暂时放弃管程所有权，进入等待状态；
- x.signal() / x.notify()：唤醒一个在 x 上等待的进程。

`x.wait()` 的标准行为（以 Hoare 管程为例）：

当一个进程在管程内执行 x.wait() 时，系统会：

释放管程的互斥锁（以便其他进程可进入管程）；
将当前进程阻塞（从运行态转为阻塞态）；
将该进程放入条件变量 x 的阻塞队列（等待队列）中；
调度器切换到其他就绪进程。

📌 注意：wait() 不检查 x 的值（条件变量本身没有“值”，它只是一个同步对象）；
判断是否等待应由程序员在 wait() 前用 while 循环检查条件，如：
1
2
3
while (buffer.isEmpty()) {
    notEmpty.wait();   // 进入等待
}

逐项排除：

A. 实现对变量 x 的互斥访问

❌ 错误。

互斥由管程本身保证（进入管程过程时自动加锁）；
条件变量 x 不提供互斥，只用于同步；
多个进程可同时在不同条件变量上等待，互不冲突。

B. 唤醒一个在 x 上阻塞的进程

❌ 错误。

这是 x.signal() 或 x.notify() 的功能；
wait() 是自己去等待，不是唤醒别人。

C. 根据 x 的值判断该进程是否进入阻塞状态

❌ 错误。

条件变量 x 没有数值属性，它只是一个同步机制；
是否等待由程序员逻辑决定（如 while (!condition) x.wait()）；
wait() 一旦调用，必然阻塞（除非信号量实现特殊优化，但标准语义是阻塞）。

D. 阻塞该进程，并将之插入 x 的阻塞队列中

✅ 正确。

完整描述了 wait() 的核心行为；
是管程条件变量的标准定义。

🎯 考点总结：

操作	行为
`x.wait()`	阻塞自己，入队 `x` 的等待队列，释放管程锁
`x.signal()`	唤醒一个在 `x` 上等待的进程（若无则忽略）
`x.broadcast()`	唤醒所有在 `x` 上等待的进程

📚 参考：《操作系统概念》—— “A condition variable allows a process to suspend execution until some condition is satisfied.”

✅ 正确答案：D

题目

和尚打水问题（辽宁大学2016年计算机专硕）
寺庙中有小和尚和老和尚若干,有一个水缸,由小和尚提水入缸供老和尚饮用.
水缸可以容纳10桶水,水取自同一口井中,由于水井口窄,每次只能容纳一个
水桶取水，水桶总数为3个。每次入水、取水仅为一桶,且不可同时进行。
试给出有关取水、入水的PV算法描述。

解析

我们来系统分析并设计 和尚打水问题 的 PV（信号量）同步算法。

🔍 问题建模

🧍 角色与资源：

实体	说明
小和尚	负责从井中打水 → 倒入水缸（生产者）
老和尚	从水缸中取水饮用（消费者）
水缸	容量为 10 桶水，缓冲区
水井	临界资源，每次仅允 1 个水桶取水（互斥）
水桶	共 3 个，有限资源（提水需先获得空桶）

⏳ 操作流程：

小和尚：
拿空桶 → 到井边打水（互斥）→ 提水到缸边 → 倒水入缸（互斥）→ 放回空桶
老和尚：
拿水桶（从缸取水需用水桶？题目未明确，但按常理：取水也需水桶）→
从缸取水（互斥）→ 饮用 → 放回空桶

📌 关键：题目说“水桶总数为 3 个”，且“每次入水、取水仅为一桶”，说明水桶是共用的临界资源，无论打水还是取水都需使用水桶。

但更合理的理解是：

小和尚用桶打水（1 桶/次），倒入缸后桶空闲；
老和尚直接从缸舀水饮用（不一定用水桶），题目未说老和尚需要桶；
水桶仅用于“从井打水”环节（因井口窄，需用桶打水）；

✅ 采用主流解法理解：

水桶是有限资源（3 个），仅小和尚打水时需要；
老和尚从水缸取水 不占用水桶（如用碗、直接饮），只消耗水缸中的水；
水缸本身是临界区（倒水/取水需互斥）；
井是临界资源（打水需互斥）。

✅ 信号量设计

信号量	初值	含义
`mutex_jing`	1	保护水井，互斥打水
`mutex_gang`	1	保护水缸，互斥倒水/取水
`empty`	10	水缸中空位数（可倒入的桶数）
`full`	0	水缸中水量（可取用的桶数）
`buckets`	3	空水桶数量（小和尚打水前需申请）

📝 注：empty 和 full 是典型的生产者-消费者信号量；
buckets 是额外资源限制（类似“有限缓冲区”的桶资源）。

✅ 进程描述（伪代码）

小和尚（生产者）：

semaphore mutex_jing = 1;   // 井互斥
semaphore mutex_gang = 1;   // 缸互斥
semaphore empty = 10;       // 水缸空位
semaphore full = 0;         // 水缸水量
semaphore buckets = 3;      // 空桶数

process 小和尚() {
    while (true) {
        P(buckets);         // 1. 申请一个空桶
        P(empty);           // 2. 等待水缸有空位
        P(mutex_jing);      // 3. 互斥访问水井
            // 从井中打一桶水（临界区）
        V(mutex_jing);      //   释放井
        
        P(mutex_gang);      // 4. 互斥访问水缸
            // 将水倒入水缸（1桶）
        V(mutex_gang);      //   释放水缸
        
        V(full);            // 5. 水量 +1
        V(buckets);         // 6. 归还空桶（倒完后桶空闲）
    }
}

老和尚（消费者）：

process 老和尚() {
    while (true) {
        P(full);            // 1. 等待水缸有水
        P(mutex_gang);      // 2. 互斥访问水缸
            // 从水缸取一桶水饮用
        V(mutex_gang);      //   释放水缸
        
        V(empty);           // 3. 水缸空位 +1
        // 老和尚不占用水桶，无需操作 buckets
    }
}

✅ 关键点说明

步骤	为什么需要？
`P(buckets)` 在 `P(empty)` 前？	✅ 合理：先拿桶，再看缸有没有空位；若顺序反过来，可能占着空位却没桶，降低并发性
井和缸分别加锁？	✅ 是：井（打水）和缸（倒/取）是两个不同临界资源，应独立互斥
老和尚不操作 `buckets`？	✅ 合理：题目中水桶用于“提水”，老和尚“饮用”不涉及提水，故无需桶；若题目明确老和尚也用水桶，则需在 `P(full)` 后加 `P(buckets)`，饮用后 `V(buckets)`，但题干未说明，按常规省略

🎯 若严格按“水桶总数为 3 个，每次入水、取水仅为一桶”理解：

“取水”也用水桶 → 老和尚需 P(buckets)；
可补充如下：

（可选）若老和尚也需用水桶：

process 老和尚() {
    while (true) {
        P(full);
        P(buckets);         // 取水也需用水桶
        P(mutex_gang);
            // 取水
        V(mutex_gang);
        V(empty);
        V(buckets);         // 归还桶
    }
}

但主流解法和考题惯例中，水桶仅用于“打水”环节，故推荐第一种。

✅ 答案总结（标准 PV 描述）

信号量定义：

mutex_jing = 1：互斥使用水井
mutex_gang = 1：互斥使用水缸
empty = 10：水缸空位数
full = 0：水缸水量
buckets = 3：空水桶数

小和尚：

P(buckets);
P(empty);
P(mutex_jing); 打水; V(mutex_jing);
P(mutex_gang); 倒水; V(mutex_gang);
V(full);
V(buckets);

老和尚：

1
2
3

P(full);
P(mutex_gang); 取水; V(mutex_gang);
V(empty);

✅ 完整、无死锁、无饥饿、满足题目所有约束。

题目

试画出下面四条语句的前趋图，并用wait和
signal原语描述前趋图
S1: x:=a+b
S2: y:=c+d
S3: z:=x*y
S4: w=z2
（注：a,b,c,d为常量）

解析

我们来逐步分析并画出这四条语句的前趋图（Precedence Graph），并用 wait / signal 原语（即 P/V 操作）实现同步。

🔍 一、分析语句间的数据依赖关系

给定语句：

S1: x := a + b
S2: y := c + d
S3: z := x * y
S4: w := z * 2   （注：z2 应为 z*2）

分析读写变量：

语句	写入变量	读取变量	依赖关系
S1	x	a, b	无输入依赖（a,b 为常量）
S2	y	c, d	无输入依赖
S3	z	x, y	依赖 S1（需 x）、依赖 S2（需 y）
S4	w	z	依赖 S3（需 z）

✅ 二、前趋图（依赖图）

前趋图是有向无环图（DAG），节点为语句，边 $ A \to B $ 表示 A 必须先于 B 执行。

S1        S2
 \       /
  \     /
   \   /
    S3
    |
    |
    S4

即：

S1 → S3
S2 → S3
S3 → S4

S1 与 S2 无依赖，可并发执行。

✅ 三、用 wait / signal 原语实现同步

🧩 思路：

为每条依赖边设置一个同步信号量（初值为 0）；
前驱执行完后 signal，后继执行前 wait。

📌 信号量设计：

信号量	含义	初值
`s1_done`	S1 是否完成	0
`s2_done`	S2 是否完成	0
`s3_done`	S3 是否完成	0

注意：S3 需等待 S1 和 S2 都完成，因此需两个 wait。

✅ 同步代码（用 P/V 表示，P = wait, V = signal）：

// 初始化信号量
semaphore s1_done = 0;
semaphore s2_done = 0;
semaphore s3_done = 0;

// 进程/线程并发执行以下代码：

// S1
x := a + b;
V(s1_done);        // 通知 S3：S1 已完成

// S2
y := c + d;
V(s2_done);        // 通知 S3：S2 已完成

// S3
P(s1_done);        // 等待 S1 完成
P(s2_done);        // 等待 S2 完成
z := x * y;
V(s3_done);        // 通知 S4：S3 已完成

// S4
P(s3_done);        // 等待 S3 完成
w := z * 2;

✅ 四、正确性说明

S1、S2 可并行执行（无同步约束）；
S3 在 P(s1_done) 和 P(s2_done) 后才执行，保证 x 和 y 已计算；
S4 在 P(s3_done) 后执行，保证 z 已计算；
所有数据依赖均被满足，无竞态条件。

📌 补充：若用四个线程分别执行 S1~S4

// 主程序初始化信号量后创建 4 个线程：

Thread1() { x = a+b; V(s1_done); }
Thread2() { y = c+d; V(s2_done); }
Thread3() { P(s1_done); P(s2_done); z = x*y; V(s3_done); }
Thread4() { P(s3_done); w = z*2; }

✅ 最终答案：

1. 前趋图：

1
2
3

S1 ───┐
      ├─→ S3 ──→ S4
S2 ───┘

2. wait/signal 描述：

信号量：s1_done = 0, s2_done = 0, s3_done = 0
S1 后：signal(s1_done)
S2 后：signal(s2_done)
S3 前：wait(s1_done); wait(s2_done)；后：signal(s3_done)
S4 前：wait(s3_done)

智浩的Blog

Linux操作系统-同步互斥

题目

解析

🔹 什么是“让权等待”？

逐项分析：

A. Peterson 方法

B. swap 指令

C. 信号量方法

D. TestAndSet 指令

🎯 考点总结：

题目

解析

逐项对应题干：

I. 两个进程不能同时进入临界区

II. 允许进程访问空闲的临界资源

III. 进程等待进入临界区的时间是有限的

IV. 不能进入临界区的执行态进程立即放弃 CPU

🎯 考点总结：

题目

解析

题目条件：

🔍 验证过程：

❌ 排除干扰选项：

🎯 考点总结：

题目

解析

逐项分析选项：

A．退出临界区的进程负责唤醒阻塞态进程

B．等待进入临界区的进程不会主动放弃CPU

C．上述伪代码满足“让权等待”的同步准则

D．while(TSL(&lock))语句应在关中断状态下执行

🎯 考点总结：

题目

解析

A．管程只能用于实现进程的互斥

B．管程是由编程语言支持的进程同步机制

C．任何时候只能有一个进程在管程中执行

D．管程中定义的变量只能被管程内的过程访问

🎯 考点总结：

题目

伪代码：

解析

题目问：“需要互斥执行的操作” —— 即哪些操作对共享变量 x 的访问可能产生竞态条件（Race Condition），需加锁保护。

A. a=1 与 a=2

B. a=x 与 b=x

C. x+=1 与 x+=2

D. x+=1 与 x+=3

✅ 正确答案：C. x+=1 与 x+=2

题目

解析

📜 题目描述：

✅ 关键点：

🔢 总指令数：

✅ 正确结果：x=2 当且仅当 两个线程的写操作没有覆盖对方的结果

🧩 枚举关键情况：

🎯 情况 1：无交错（完全串行）

1. A1→A2→A3→B1→B2→B3

2. B1→B2→B3→A1→A2→A3

🎯 情况 2：部分交错，但写操作未被覆盖

3. A1→B1→A2→B2→A3→B3

4. A1→B1→A2→A3→B2→B3

5. A1→B1→B2→A2→A3→B3

6. A1→A2→B1→B2→A3→B3

7. A1→A2→B1→A3→B2→B3

8. B1→A1→B2→A2→B3→A3

9. B1→A1→B2→B3→A2→A3

10. B1→B2→A1→A2→B3→A3

🎯 唯一能使 x=2 的情况：

✅ 序列 1：A1→A2→A3→B1→B2→B3

✅ 序列 2：B1→B2→B3→A1→A2→A3

✅ 序列 3：A1→B1→B2→B3→A2→A3

🧠 正确方法：枚举所有 20 种序列，统计 x=2 的数量

✅ 序列 3：A1→A2→B1→B2→B3→A3

✅ 序列 4：A1→B1→A2→B2→B3→A3

🚫 有没有第三种？

✅ 序列：A1→B1→B2→A2→B3→A3

💡 突破点：

✅ 序列：A1→A2→A3→B1→B2→B3 → x=2

✅ 序列：B1→B2→B3→A1→A2→A3 → x=2

D．`while(TSL(&lock))`语句应在关中断状态下执行

A. `a=1` 与 `a=2`

B. `a=x` 与 `b=x`

C. `x+=1` 与 `x+=2`

D. `x+=1` 与 `x+=3`

✅ 正确结果：x=2 当且仅当两个线程的写操作没有覆盖对方的结果

`x.wait()` 的标准行为（以 Hoare 管程为例）：