信号量

互斥实现方法有两个明显问题：

  • 软件算法依赖普通语句组合，检查、上锁之间可能被进程切换打断。
  • TSL、Swap、自旋锁虽然能保证互斥，但等待者会反复占用 CPU，不能让权等待。

信号量把“申请资源”和“释放资源”做成操作系统提供的原语。原语执行时不可被中断，因此可以把关键操作一气呵成；记录型信号量还可以把不能继续的进程阻塞起来，而不是让它原地忙等。

信号量可以理解为一种受限变量：普通程序不能随便读写它，只能初始化，并通过 wait(S) / signal(S) 操作它。wait(S) 常记为 P(S)，signal(S) 常记为 V(S)。

操作 语义 可能导致死锁吗 典型位置
P(S) / wait(S) 申请一个单位的资源 S 可能 使用资源之前
V(S) / signal(S) 释放一个单位的资源 S 不会 使用资源之后，或产生条件之后

P(S) 可能会导致死锁，因此它的位置非常敏感；V(S) 不会有这个问题，因此多个 V 操作之间通常没有 P 操作那样强的顺序风险。

信号量表示什么

一个信号量对应一种资源，S.value 可以理解为这种资源的剩余数量或等待情况。

S.value 含义
S.value > 0 还有 S.value 个资源可用
S.value == 0 资源恰好分配完，没有剩余资源
S.value < 0 没有可用资源，且有 $\lvert S.value \rvert$ 个进程在等待
Example

系统有 2 台打印机，可以设置 S.value = 2。前两个进程执行 P(S) 后都能获得打印机；第三个进程再执行 P(S) 时，S.value 会变成 -1，该进程进入等待队列。

资源的初值
互斥信号量的初值通常是 1；同步信号量的初值通常是 0；多个同类资源的信号量初值就是资源数量。初值就是表示一开始有没有资源、有没有条件、有没有进入名额。

整型信号量

整型信号量只用一个整数表示资源数。它的 P 操作通常写成：

1
2
3
4
P(S):
	while (S <= 0)
		;
	S = S - 1;

V 操作通常写成：

1
2
V(S):
	S = S + 1;

整型信号量把检查资源是否可用和占用资源放在原语中执行，因此不会出现双标志先检查法的检查后还没上锁就被切换的问题。

但它仍然有忙等。若 S <= 0，进程会停在 while 中反复检查，不会主动释放处理机，因此不满足让权等待。

[!NOTE]
若没有特别说明，讨论 P/V 操作时通常默认使用下面的记录型信号量，而不是会忙等的整型信号量。

记录型信号量

记录型信号量把资源数和等待队列放在一起：

1
2
3
4
semaphore S {
    int value;       // 资源数；若为负，绝对值表示等待进程数
    queue L;         // 等待该资源的阻塞队列
}

P(S) 表示申请一个单位资源：

1
2
3
4
P(S):
	S.value--;    
	if (S.value < 0)    
	    block(S.L);

V(S) 表示释放一个单位资源：

1
2
3
4
V(S):
	S.value++;           
	if (S.value <= 0)    // 如果有进程在等待
	    wakeup(S.L);     // 唤醒一个进程

P 操作先把 S.value 减 1。若减完后仍不小于 0，说明申请者拿到了资源，可以继续执行；若减完后小于 0，说明资源已经不够，当前进程调用 block 原语，进入 S.L 对应的等待队列，从运行态变为阻塞态。

V 操作先把 S.value 加 1。若加完后大于 0，说明没有进程等待这种资源；若加完后仍小于等于 0，说明释放之前有人在等待，因此调用 wakeup 原语唤醒等待队列中的一个进程，被唤醒进程从阻塞态变为就绪态。

`V(S)` 后的判断为什么是 `S.value <= 0`?

如果释放前有等待进程，S.value 一定是负数；释放一个资源后，S.value 可能变成 0，也可能仍是负数。只要它不大于 0，就说明释放出来的资源应交给某个等待者。

# 信号量的应用

900

用信号量实现互斥

互斥信号量表示“进入临界区的名额”。同一时刻只允许一个进程进入临界区，所以互斥信号量初值通常为 1。

1
2
3
4
5
6
7
8
9
semaphore mutex = 1;

Pi 进程：
	P(mutex);
	{
		critical section;     // 临界区
	}
	V(mutex);
	remainder section;    // 剩余区

P(mutex) 放在进入区，表示申请进入临界区的名额；V(mutex) 放在退出区，表示归还这个名额。

Note

不同临界资源要使用不同的互斥信号量。打印机和摄像头是两个不同资源，就不能只用同一个 mutex 粗暴保护所有访问，否则会把本来可以并行的操作也串行化。

Warning

P/V 必须成对出现。缺少 P(mutex)，不能保证互斥；缺少 V(mutex)，临界区名额永远不归还，后续进程会一直等待。

## 用信号量实现同步

同步保证执行顺序。若要求 $S_2$ 必须在 $S_1$ 之后执行，就设置一个同步信号量 a，初值为 0。

1
2
3
4
5
6
7
8
9
semaphore a = 0;

P1 进程：
	S1;
	V(a);

P2 进程：
	P(a);
	S2;

规则是：前 V 后 P。

  • 前操作完成后执行 V(a)，表示“条件已经产生”。
  • 后操作之前执行 P(a)，表示“等待这个条件”。

若 $P_1$ 先执行到 V(a)，a 从 0 变成 1；之后 $P_2$ 执行 P(a) 时不会阻塞。若 $P_2$ 先执行到 P(a)，a 从 0 变成 -1，$P_2$ 阻塞；等 $P_1$ 执行 V(a) 后，$P_2$ 被唤醒。

用信号量实现前驱关系

前驱关系本质上是多组同步关系。前驱图中的每一条边，都表示一个“前操作必须先于后操作”的约束。

处理方法：

  1. 每一条前驱边设置一个同步信号量，初值为 0。
  2. 在边的起点操作之后执行 V。
  3. 在边的终点操作之前执行 P。

例如并行建立大根堆时，一个结点的左右子堆占用不同数组区间，可以并行调整；但父结点的下滤必须等左右子堆都已经成为大根堆后才能进行。这个约束可以用两个同步信号量表示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
semaphore left_done = 0;
semaphore right_done = 0;

左子堆任务：
	heapify(left_child);
	V(left_done);

右子堆任务：
	heapify(right_child);
	V(right_done);

父结点任务：
	P(left_done);
	P(right_done);
	siftDown(parent);

heapify(left_child) 和 heapify(right_child) 互不修改对方的子树，因此可以并行执行。siftDown(parent) 会比较父结点与左右子堆的根，并可能沿某一侧继续下滤；如果左右子堆还没调整好，父结点下滤的依据就不可靠。因此父结点任务前要连续执行两个 P 操作，等两条前驱边都完成后才能继续。

如果一个操作有多个前驱，就要在该操作前执行多个 P 操作；只有所有前驱都完成后，它才能继续。