考研笔记

信号量

前面所有方法都只解决了互斥，而且全都忙等。信号量一次性解决了这两个问题：它既能实现互斥，也能实现同步，并且满足让权等待。

它是第 2 章大题的核心工具，2.3.5 的经典问题全部用它来写。

机制

整型信号量：还差一步

最朴素的想法是用一个整数表示可用资源数，配两个原子操作：

int S = 1;                  // 可用资源数
 
void P(int *S) {            // wait
    while (*S <= 0)         // 没资源就一直等
        ;
    (*S)--;
}
 
void V(int *S) {            // signal
    (*S)++;
}

它能实现互斥，但仍然忙等——while (*S <= 0); 空转，违反让权等待。问题在于没资源时它只会转圈，不会把自己挂起。

记录型信号量：加一条等待队列

解决办法是给信号量配一条等待队列，没资源时就把自己挂进去：

typedef struct {
    int value;              // 剩余资源数
    struct process *L;      // 等待队列
} semaphore;
 
void P(semaphore *S) {
    S->value--;                     // 先减，表示"我要一个"
    if (S->value < 0) {             // 减完是负的 → 没资源了
        block(S->L);                // 自我阻塞，挂入等待队列，让出 CPU
    }
}
 
void V(semaphore *S) {
    S->value++;                     // 先加，表示"我还一个"
    if (S->value <= 0) {            // 加完仍 ≤0 → 队列里还有人在等
        wakeup(S->L);               // 唤醒一个
    }
}

block() 和 wakeup() 正是 2.1.4 的阻塞原语和唤醒原语。至此让权等待被满足——进程拿不到资源时会真正进入阻塞态，而不是占着 CPU 空转。

value 的物理含义——这是最重要的一条

S.value 的正负有完全不同的含义，读懂它，一大批选择题可以秒答：

当前还有个资源可用资源刚好分完，无人等待有个进程正在等待队列中阻塞

所以给定一个 S.value = -3，可以立刻断定：资源已全部分配完，且有 3 个进程正阻塞在这个信号量上。

由此还能推出两条常考结论：

  • P 操作可能导致进程阻塞（减完为负时），V 操作可能唤醒进程（加完仍 ≤0 时）。
  • V 操作永远不会导致执行它的进程阻塞——它只加不减。

三种用法

信号量的三种用法必须分清，区别全在初值和 P/V 的位置。

① 实现互斥：初值为 1，P/V 在同一进程内成对出现

semaphore mutex = 1;        // 初值 = 1
 
// 每个进程都这样写
P(mutex);
critical section;
V(mutex);

初值 1 表示”这个临界区同时只允许 1 个进程进入”。

关键特征：P(mutex) 和 V(mutex) 必然在同一个进程里，一前一后夹住临界区。

② 实现同步：初值为 0，P/V 分布在不同进程

要保证”进程 A 的语句 a 一定在进程 B 的语句 b 之前执行”：

semaphore S = 0;            // 初值 = 0
 
// 进程 A                    // 进程 B
a;                          P(S);       // 等 a 完成
V(S);                       b;

口诀是**“前 V 后 P”：在前面那个动作之后执行 V，在后面**那个动作之前执行 P。

为什么初值必须是 0？因为如果 B 先跑到 P(S)，此时 S 减为 −1，B 立即阻塞；等 A 执行完 a 再 V(S)，S 回到 0 并唤醒 B。初值 0 保证了”B 不可能抢在 A 前面”。

关键特征：P 和 V 出现在不同的进程里。 这是与互斥用法最直观的区别。

③ 实现前驱关系：每条前驱边设一个信号量

前驱关系就是同步的推广。若有前驱图 S1→S2、S1→S3、S2→S4、S3→S4：

semaphore a=0, b=0, c=0, d=0;   // 每条边一个信号量，初值全为 0
 
P1: S1; V(a); V(b);             // S1 完成，通知 S2 和 S3
P2: P(a); S2; V(c);             // 等 S1，做 S2，通知 S4
P3: P(b); S3; V(d);             // 等 S1，做 S3，通知 S4
P4: P(c); P(d); S4;             // 等 S2 和 S3 都完成

方法固定：图上有几条边，就设几个信号量，初值全为 0；每个结点在开头对所有入边做 P，在结尾对所有出边做 V。

用信号量解决问题的三步法

写 PV 代码题时按这个顺序，不容易乱：

第一步：分析有哪些同步/互斥关系。 逐条列出”谁必须在谁之前”（同步）、“什么资源不能同时用”（互斥）。

第二步：为每一条关系设一个信号量，定初值。

  • 互斥关系 → 初值 1
  • 同步关系 → 初值 0
  • 表示”有 n 个可用资源” → 初值 n

第三步：按”前 V 后 P”放置 P/V 操作。 互斥的一对夹住临界区；同步的分放在两个进程。

边界

P/V 的顺序：同步 P 必须在互斥 P 之前

这是 PV 大题最经典的失分点，也是唯一会导致死锁的顺序错误。

正确写法：

P(empty);       // 同步信号量在前
P(mutex);       // 互斥信号量在后
...
V(mutex);
V(full);

错误写法（两个 P 交换）：

P(mutex);       // ✗ 先拿了互斥锁
P(empty);       // ✗ 再等资源 —— 抱着锁睡着了

为什么会死锁：假设缓冲区已满，生产者先执行 P(mutex) 拿到了互斥锁，再执行 P(empty) 时因为没有空位而阻塞。此时它仍然持有 mutex。而消费者想取走数据腾出空位，第一步就要 P(mutex)——拿不到，也阻塞。

两个进程互相等待，永久死锁。

一句话记法：不要抱着锁去睡觉。 先确认资源到位，再进临界区。

顺带注意：两个 V 操作的顺序可以交换，不会引起死锁。V 永远不会阻塞执行者，所以先释放哪个都行。只有 P 的顺序是致命的。

互斥的 P/V 与同步的 P/V

互斥同步
初值1（或 n）0
P 和 V 的位置同一进程内，夹住临界区不同进程，前 V 后 P
目的不能同时必须按序
少写 V 的后果后续进程永远进不去等待方永远阻塞

判断题技巧：看到一对 P/V 在同一个进程里紧挨着夹住一段代码，那是互斥；看到 P 和 V 分散在两个进程里，那是同步。

整型信号量 vs 记录型信号量

整型信号量记录型信号量
结构一个整数整数 + 等待队列
等不到时忙等（while）阻塞，让出 CPU
让权等待违反满足
value 可否为负否（卡在 0）可以，负值表示等待人数

只有记录型信号量满足让权等待，这是它们最核心的区别。教材后面所有题目默认用的都是记录型。

P 操作一定会阻塞吗

不一定。 只有当 S.value 减完之后小于 0 时才阻塞。若原本 S.value > 0（还有资源），减完仍 ≥ 0，进程直接通过，不阻塞。

同理，V 操作也不一定唤醒进程——只有加完之后仍 ≤ 0（说明队列里确实有人等）时才唤醒。

对照速查

S.value含义
还有 S.value 个资源可用
资源刚好分完，无人等待
有 个进程阻塞在此
用法初值P/V 位置
互斥1同一进程，夹住临界区
同步0不同进程，前 V 后 P
n 个资源n视情况
前驱关系每条边一个，全 0入边 P，出边 V
操作是否可能阻塞自己是否可能唤醒别人
P可能（减完 < 0）否
V绝不可能（加完 ≤ 0）

考点

  • S.value < 0 时， 就是等待队列中的进程数（高频计算题）
  • 记录型信号量靠 block/wakeup 原语实现让权等待
  • 互斥初值 1、P/V 同进程；同步初值 0、前 V 后 P、P/V 分处两进程
  • 同步 P 必须在互斥 P 之前，否则死锁（“不要抱着锁睡觉”）
  • 两个 V 的顺序可以交换，不会死锁
  • P 不一定阻塞，V 不一定唤醒

链接

反向链接