信号量与生产者-消费者问题

一句话定义

信号量（semaphore）是 Dijkstra 提出的带原子 P（wait/down）与 V（signal/up）操作的整数计数器：P 在计数为零时阻塞、否则减一；V 加一并唤醒一个等待者，它是描述"资源计数 + 阻塞等待"的标准模型。

为什么重要

互斥锁只能表达"一次一人"，而现实中大量同步问题本质是资源计数：缓冲区剩多少空位、有几个可用连接。生产者-消费者是这一切的母题——线程池的任务队列、内核的块设备请求队列、日志系统的刷盘管道，全是它的变体。掌握信号量，等于掌握了把任意同步需求翻译成正确代码的语法。

前置知识

kp-011（临界区）；kp-009（共享内存需要自配同步）。

核心概念

• P 操作 / wait / down：value--; if (value < 0) 阻塞;
• V 操作 / signal / up：value++; if (value <= 0) 唤醒一个等待者;
• 二值信号量：取值 0/1，可当锁用，但与互斥锁语义不同（无所有者）。
• 计数信号量：表达 n 份同类资源。
• 有界缓冲（bounded buffer）：生产者放数据、消费者取数据的固定容量环形队列。
• 条件变量（condition variable）：POSIX 中与互斥锁搭配的"等待某条件成立"原语，管程（monitor）的构件，与信号量互为表达。

原理与机制

经典的有界缓冲方案用三个信号量：mutex（初值 1，保护缓冲区本身）、empty（初值 N，空位计数）、full（初值 0，已有数据计数）：

生产者:                          消费者:
loop:                            loop:
  P(empty)     // 等空位           P(full)      // 等数据
  P(mutex)     // 进临界区         P(mutex)
  放入数据                        取出数据
  V(mutex)     // 出临界区         V(mutex)
  V(full)      // 数据+1          V(empty)     // 空位+1

P 操作的顺序是正确性的全部：若生产者先 P(mutex) 再 P(empty)，当缓冲满且生产者持锁阻塞在 P(empty) 上时，消费者 P(full) 可通过、却被 P(mutex) 卡死——死锁（kp-014）。"资源信号量在外、互斥信号量在内"是必须背诵的纪律。

公式或模型

不变量：任意时刻 已存数据数 ≤ N；full 的值 = 当前数据数；empty 的值 = N − 当前数据数。信号量的每一对 P/V 恰好维持这两个等式，这就是"模型可验证"的含义——不靠跑测试，靠构造论证。

直观类比

信号量像停车场的空位显示屏：进场取号（P），满了在门口等；出场还号（V），并放一个等待者进去。mutex、empty、full 就是三块不同的牌子：大门闸机、空位屏、已停车计数屏。

实例或案例

POSIX 无名信号量版本（C，配合 kp-009 共享内存可跨进程）：

#include <semaphore.h>
#define N 8
int buf[N]; sem_t empty, full, mutex;
void init(void){ sem_init(&empty,0,N); sem_init(&full,0,0); sem_init(&mutex,0,1); }
void* producer(void* a){ for(int i=0;;i++){ sem_wait(&empty); sem_wait(&mutex);
  buf[i%N]=i; sem_post(&mutex); sem_post(&full);} }
void* consumer(void* a){ for(;;){ int d; sem_wait(&full); sem_wait(&mutex);
  d=buf[0]; sem_post(&mutex); sem_post(&empty);} }

观察实验：把生产者中两个 P 对调，程序在缓冲写满后必然挂死——用 gdb attach 或 pstack 能看到两个线程互相等待的栈，即 kp-014 的活体标本。

常见误区

• 混淆互斥锁与二值信号量：互斥锁有所有者、必须原持有者解锁且支持递归检测；二值信号量无所有者，甚至可由一方 P、另一方 V（这恰是事件通知的用法）。
• 交换 P 顺序：资源信号量必须在互斥信号量之前。
• 认为忙等版本与阻塞版本等价：忙等烧 CPU 且在单核上可能活锁；真正的信号量由内核阻塞实现。

与其他知识点的关系

P 顺序错误直接引入 kp-014 的死锁；信号量在内核中实现 I/O 请求队列的计数控制（kp-022、kp-027）；条件变量版本见管程思想的现代实践。

延伸阅读

Dijkstra 1965 论文原文（信号量与"晚餐哲学家"问题的出处）；《操作系统概念》第 6 章。

自测题

1. 用信号量实现"最多允许 5 个线程同时进入"的机制？

答：初值为 5 的计数信号量，进入前 P、退出后 V，无需额外互斥量（计数与阻塞由信号量自身原子维护）。

1. 生产者-消费者中 P(mutex) 与 P(empty) 顺序反了会发生什么？

答：缓冲满时生产者持有 mutex 阻塞在 P(empty)，消费者因拿不到 mutex 而无法消费，双方永久等待，构成死锁。

1. 信号量 value 为负数的含义是什么？

答：绝对值表示正在该信号量上等待的执行流数量（阻塞队列长度）。