信号量 | Notes@Tsukino

定义

由 Dijkstra 提出的经典同步机制
信号量 $S$ 是一个整型变量，代表可用资源的数量
除了初始化，信号量只能通过 P 操作 和 V 操作 修改（原子操作）

重点 P/V 操作

P 操作（wait / 申请资源）

P(S):
  S.value = S.value - 1
  if S.value < 0:
    进程进入等待队列（阻塞）

V 操作（signal / 释放资源）

V(S):
  S.value = S.value + 1
  if S.value <= 0:
    从等待队列唤醒一个进程

分类

按资源计数

二进制信号量（Binary Semaphore）： $S$ 取值 0 或 1，相当于互斥锁
计数信号量（Counting Semaphore）： $S \geq 0$ ，表示可用资源数量

按使用目的

互斥信号量（公共信号量）：用于保护临界区，初值 = 1
同步信号量（私有信号量）：用于进程间同步，初值 = 0

实现机制

基于阻塞队列（非忙等）：当 P 操作无法获取资源时，进程主动阻塞并让出 CPU
不使用忙等（while 循环），避免 CPU 浪费
每个信号量关联一个等待队列（blocked queue）

临界区（Critical Section）四个原则

忙则等待（互斥）：临界区有进程时，其他进程不能进入
空闲则入（前进）：无进程在临界区时，应允许申请者进入
有限等待：等待进入临界区的进程不会无限等待
让权等待：不能进入临界区时应主动阻塞，而非忙等

P/V 使用模式

互斥：P、V 成对出现在同一进程中，保护临界区
```
P(mutex);
  临界区
V(mutex);
```

同步：P、V 出现在不同进程中

进程 A: V(sync);   进程 B: P(sync);

参见经典同步问题