765 lines
15 KiB
Markdown
765 lines
15 KiB
Markdown
好，这一块你要是啃明白了，基本就把并发控制的“核心武器”拿下了。我们从“本质 → 抽象定义 → 操作语义 → 实现直觉 → 常见问题”一层一层讲清楚。
|
||
|
||
---
|
||
|
||
# 一、信号量到底是什么（直觉）
|
||
|
||
信号量（Semaphore）本质上是一个**带计数器的同步工具**，用于：
|
||
|
||
* 控制多个线程/进程对**共享资源**的访问
|
||
* 或者用于线程之间的**执行顺序协调**
|
||
|
||
你可以把它想象成：
|
||
|
||
> 一个“带库存的通行证系统”
|
||
|
||
* 有一个整数 `S`（库存）
|
||
* 每个线程想进入某个临界区，就必须“拿一个通行证”
|
||
* 如果还有库存，就进去
|
||
* 如果没有，就在门口等
|
||
|
||
---
|
||
|
||
# 二、形式化定义（操作系统里的标准说法）
|
||
|
||
信号量是一个整数变量 `S`，只能通过两个**原子操作**访问：
|
||
|
||
### 1. P操作（也叫 wait / down）
|
||
|
||
```c
|
||
P(S):
|
||
while S <= 0:
|
||
等待
|
||
S = S - 1
|
||
```
|
||
|
||
语义：
|
||
|
||
* 申请一个资源
|
||
* 如果资源不够 → 阻塞
|
||
|
||
---
|
||
|
||
### 2. V操作（也叫 signal / up）
|
||
|
||
```c
|
||
V(S):
|
||
S = S + 1
|
||
唤醒一个等待的线程（如果有）
|
||
```
|
||
|
||
语义：
|
||
|
||
* 释放一个资源
|
||
* 通知别人可以用了
|
||
|
||
---
|
||
|
||
注意一个关键点：
|
||
|
||
> **P/V 操作必须是原子的（不可中断）**
|
||
|
||
否则就会出严重竞态问题（比如两个线程同时看到 S>0）
|
||
|
||
---
|
||
|
||
# 三、两种常见信号量类型
|
||
|
||
## 1. 计数信号量（Counting Semaphore）
|
||
|
||
* S 可以是任意非负整数
|
||
* 表示**资源数量**
|
||
|
||
例子：
|
||
|
||
```text
|
||
S = 5 → 有5个资源
|
||
```
|
||
|
||
应用：
|
||
|
||
* 连接池
|
||
* 线程池
|
||
* 限流
|
||
|
||
---
|
||
|
||
## 2. 二值信号量（Binary Semaphore）
|
||
|
||
* S ∈ {0, 1}
|
||
* 类似锁（mutex）
|
||
|
||
```text
|
||
S = 1 → 可进入
|
||
S = 0 → 被占用
|
||
```
|
||
|
||
注意：
|
||
|
||
> Binary semaphore ≈ Mutex，但**不完全等价**
|
||
|
||
区别：
|
||
|
||
* mutex 有“所有权”（谁锁谁解）
|
||
* semaphore 没有
|
||
|
||
---
|
||
|
||
# 四、经典例子：生产者-消费者
|
||
|
||
这是信号量的“标志性应用”。
|
||
|
||
假设：
|
||
|
||
* 一个缓冲区
|
||
* 生产者往里放数据
|
||
* 消费者取数据
|
||
|
||
---
|
||
|
||
## 定义三个信号量：
|
||
|
||
```c
|
||
mutex = 1 // 互斥访问缓冲区
|
||
empty = N // 空位数量
|
||
full = 0 // 已占用数量
|
||
```
|
||
|
||
---
|
||
|
||
## 生产者：
|
||
|
||
```c
|
||
P(empty) // 等空位
|
||
P(mutex) // 进入临界区
|
||
|
||
放数据
|
||
|
||
V(mutex)
|
||
V(full) // 增加产品
|
||
```
|
||
|
||
---
|
||
|
||
## 消费者：
|
||
|
||
```c
|
||
P(full) // 等数据
|
||
P(mutex)
|
||
|
||
取数据
|
||
|
||
V(mutex)
|
||
V(empty) // 释放空间
|
||
```
|
||
|
||
---
|
||
|
||
### 这里体现了两个作用：
|
||
|
||
1. **同步**（empty / full）
|
||
2. **互斥**（mutex）
|
||
|
||
---
|
||
|
||
# 五、信号量解决了什么问题？
|
||
|
||
## 1. 互斥（Mutual Exclusion）
|
||
|
||
防止：
|
||
|
||
```c
|
||
count++ // 非原子
|
||
```
|
||
|
||
被多个线程同时执行 → 数据错误
|
||
|
||
---
|
||
|
||
## 2. 同步（Synchronization）
|
||
|
||
比如：
|
||
|
||
```text
|
||
线程A必须在B之后执行
|
||
```
|
||
|
||
可以用：
|
||
|
||
```c
|
||
S = 0
|
||
|
||
线程A:
|
||
P(S)
|
||
|
||
线程B:
|
||
...
|
||
V(S)
|
||
```
|
||
|
||
---
|
||
|
||
# 六、实现原理（操作系统怎么做的）
|
||
|
||
你要稍微从内核角度理解一下：
|
||
|
||
信号量结构大概是：
|
||
|
||
```c
|
||
struct semaphore {
|
||
int value;
|
||
queue<thread> wait_queue;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
### P操作真实行为：
|
||
|
||
```c
|
||
disable_interrupts()
|
||
|
||
S--
|
||
if (S < 0):
|
||
把当前线程加入等待队列
|
||
阻塞当前线程
|
||
|
||
enable_interrupts()
|
||
```
|
||
|
||
---
|
||
|
||
### V操作：
|
||
|
||
```c
|
||
disable_interrupts()
|
||
|
||
S++
|
||
if (S <= 0):
|
||
从等待队列唤醒一个线程
|
||
|
||
enable_interrupts()
|
||
```
|
||
|
||
---
|
||
|
||
关键点：
|
||
|
||
> S < 0 表示有多少线程在等
|
||
|
||
---
|
||
|
||
# 七、常见坑（非常重要）
|
||
|
||
## 1. 死锁（Deadlock）
|
||
|
||
典型错误：
|
||
|
||
```c
|
||
P(A)
|
||
P(B)
|
||
```
|
||
|
||
另一个线程：
|
||
|
||
```c
|
||
P(B)
|
||
P(A)
|
||
```
|
||
|
||
→ 互相等待
|
||
|
||
---
|
||
|
||
## 2. 忘记 V（释放）
|
||
|
||
```c
|
||
P(mutex)
|
||
// 忘记 V(mutex)
|
||
```
|
||
|
||
→ 永久锁死
|
||
|
||
---
|
||
|
||
## 3. 顺序错误
|
||
|
||
```c
|
||
P(mutex)
|
||
P(empty)
|
||
```
|
||
|
||
→ 可能死锁
|
||
|
||
---
|
||
|
||
## 4. 信号量滥用
|
||
|
||
信号量可以做任何同步，但：
|
||
|
||
> 写复杂了之后，人脑根本跟不上
|
||
|
||
所以现代系统更常用：
|
||
|
||
* mutex + condition variable
|
||
* monitor
|
||
|
||
---
|
||
|
||
# 八、和其他机制的关系（你必须搞清）
|
||
|
||
## vs Mutex
|
||
|
||
| 特性 | Semaphore | Mutex |
|
||
| --- | --------- | ----- |
|
||
| 计数 | 可以 >1 | 只能1 |
|
||
| 所有权 | 无 | 有 |
|
||
| 用途 | 同步+互斥 | 主要互斥 |
|
||
|
||
---
|
||
|
||
## vs Condition Variable
|
||
|
||
* semaphore：**带状态**
|
||
* condition variable：**不存状态**
|
||
|
||
---
|
||
|
||
# 九、一句话总结
|
||
|
||
> 信号量 = 一个原子计数器 + 阻塞队列，用来控制“能不能继续执行”
|
||
|
||
---
|
||
|
||
# 十、你可以这样理解（很关键）
|
||
|
||
把信号量抽象成：
|
||
|
||
```text
|
||
资源许可证系统
|
||
```
|
||
|
||
* P：拿许可证（没有就排队）
|
||
* V：归还许可证（叫醒别人）
|
||
|
||
---
|
||
|
||
如果你愿意，我们可以继续往下挖一层更硬核的内容：
|
||
|
||
* Linux 里的 `semaphore` vs `spinlock`
|
||
* futex 是怎么优化信号量的
|
||
* 为什么现代 C++ 很少直接用 semaphore
|
||
* 或者我给你画一个“内核调度 + 信号量阻塞”的完整流程图
|
||
|
||
你现在这个阶段，已经可以开始往“操作系统实现层”进化了。
|
||
|
||
---
|
||
|
||
你这个问题抓得非常关键，本质上是在问：
|
||
|
||
> **“信号量本身也是共享数据，那在修改 S 的时候，如果被别的线程同时访问，不就炸了吗？”**
|
||
|
||
答案是：
|
||
**如果没有额外机制，确实会炸。**
|
||
所以操作系统在设计上做了一件非常重要的事：
|
||
|
||
> **P/V 操作必须是“原子操作”（atomic）**
|
||
|
||
下面给你把这件事彻底讲透。
|
||
|
||
---
|
||
|
||
# 一、如果不原子，会发生什么？
|
||
|
||
假设我们有：
|
||
|
||
```c
|
||
S = 1
|
||
```
|
||
|
||
两个线程同时执行 `P(S)`：
|
||
|
||
---
|
||
|
||
### 理想情况（正确）
|
||
|
||
线程A：
|
||
|
||
```
|
||
读 S = 1
|
||
S-- → 0
|
||
```
|
||
|
||
线程B：
|
||
|
||
```
|
||
读 S = 0 → 阻塞
|
||
```
|
||
|
||
---
|
||
|
||
### 实际可能发生（竞态条件）
|
||
|
||
如果没有原子性：
|
||
|
||
线程A：
|
||
|
||
```
|
||
读 S = 1
|
||
```
|
||
|
||
线程B：
|
||
|
||
```
|
||
读 S = 1
|
||
```
|
||
|
||
然后：
|
||
|
||
线程A：
|
||
|
||
```
|
||
S-- → 0
|
||
```
|
||
|
||
线程B：
|
||
|
||
```
|
||
S-- → -1
|
||
```
|
||
|
||
结果：
|
||
|
||
```text
|
||
两个线程都进入了临界区 ❌
|
||
```
|
||
|
||
这就是经典的：
|
||
|
||
> **Race Condition（竞态条件）**
|
||
|
||
---
|
||
|
||
# 二、操作系统怎么解决这个问题？
|
||
|
||
核心原则：
|
||
|
||
> **对 S 的修改必须是“不可分割”的**
|
||
|
||
也就是：
|
||
|
||
```text
|
||
读 + 判断 + 修改 → 必须一口气做完
|
||
```
|
||
|
||
---
|
||
|
||
## 方法1：关中断（单核早期方案）
|
||
|
||
```c
|
||
disable_interrupts()
|
||
|
||
// P操作
|
||
S--
|
||
if (S < 0):
|
||
block()
|
||
|
||
enable_interrupts()
|
||
```
|
||
|
||
### 为什么有效？
|
||
|
||
* 单核CPU
|
||
* 没有中断 → 不会切换线程
|
||
* 所以不会被打断
|
||
|
||
---
|
||
|
||
### 但问题：
|
||
|
||
* 多核系统 ❌（别的CPU还在跑）
|
||
* 中断关太久会影响系统响应 ❌
|
||
|
||
---
|
||
|
||
## 方法2：硬件原子指令（现代方案）
|
||
|
||
现代CPU提供：
|
||
|
||
* `test-and-set`
|
||
* `compare-and-swap (CAS)`
|
||
* `fetch-and-add`
|
||
|
||
---
|
||
|
||
### 举个 CAS 例子
|
||
|
||
```c
|
||
while (true) {
|
||
old = S;
|
||
if (old <= 0)
|
||
block();
|
||
|
||
if (CAS(&S, old, old - 1))
|
||
break;
|
||
}
|
||
```
|
||
|
||
CAS 保证：
|
||
|
||
> “只有当 S 还是 old 时，才修改成功”
|
||
|
||
否则重试
|
||
|
||
---
|
||
|
||
## 方法3：自旋锁（spinlock）
|
||
|
||
内核里常见：
|
||
|
||
```c
|
||
lock()
|
||
S--
|
||
unlock()
|
||
```
|
||
|
||
但这个 lock 本身也是用原子指令实现的。
|
||
|
||
---
|
||
|
||
# 三、关键理解：P/V 不只是“减1/加1”
|
||
|
||
你不能把它理解成：
|
||
|
||
```c
|
||
S--
|
||
```
|
||
|
||
而应该理解为：
|
||
|
||
```text
|
||
一个“不可中断的操作块”
|
||
```
|
||
|
||
包括：
|
||
|
||
1. 检查 S
|
||
2. 修改 S
|
||
3. 决定是否阻塞/唤醒线程
|
||
|
||
---
|
||
|
||
# 四、再深入一层：阻塞是怎么安全发生的？
|
||
|
||
这是很多人忽略的重点。
|
||
|
||
看这个危险情况：
|
||
|
||
```text
|
||
线程A：
|
||
准备 block()
|
||
|
||
线程B：
|
||
V(S) → 唤醒线程
|
||
|
||
→ 如果顺序错了，就可能“丢唤醒”
|
||
```
|
||
|
||
---
|
||
|
||
## 操作系统怎么避免？
|
||
|
||
通过：
|
||
|
||
> **“修改 S + 入队/出队 + 状态切换” 是一个整体原子过程**
|
||
|
||
也就是说：
|
||
|
||
```c
|
||
P(S):
|
||
原子地：
|
||
S--
|
||
if (S < 0):
|
||
加入等待队列
|
||
切换为阻塞状态
|
||
```
|
||
|
||
不会出现：
|
||
|
||
```text
|
||
刚准备睡 → 别人已经唤醒你 → 你却没睡 → 信号丢了
|
||
```
|
||
|
||
---
|
||
|
||
# 五、总结成一句话
|
||
|
||
你刚才的问题可以总结为：
|
||
|
||
> “信号量自己怎么保证线程安全？”
|
||
|
||
答案是：
|
||
|
||
> **靠更底层的同步原语（原子指令 / 关中断 / 自旋锁）来保证 P/V 操作的原子性**
|
||
|
||
---
|
||
|
||
# 六、你现在可以形成一个完整认知链
|
||
|
||
```text
|
||
应用层：
|
||
semaphore（信号量）
|
||
|
||
依赖：
|
||
原子操作（CAS / test-and-set）
|
||
|
||
依赖：
|
||
CPU硬件保证原子性
|
||
```
|
||
|
||
---
|
||
|
||
# 七、一个很重要的提升（你现在这个阶段该理解的）
|
||
|
||
你可以这样看整个系统：
|
||
|
||
> **信号量并不是“最底层”的同步工具**
|
||
|
||
而是建立在：
|
||
|
||
* 硬件原子指令
|
||
* 内核调度机制
|
||
|
||
之上的一个**更高级抽象**
|
||
|
||
---
|
||
|
||
如果你愿意，我们可以再往下挖一个非常关键的点（强烈建议）：
|
||
|
||
* 为什么现代 Linux 更喜欢用 **futex**
|
||
* semaphore 在用户态是怎么避免频繁陷入内核的
|
||
* 自旋锁 vs 阻塞锁的性能边界
|
||
|
||
这几个点一打通，你对操作系统并发这一块就已经是“半个内核工程师水平”了。
|
||
|
||
---
|
||
|
||
这是一个非常经典的学习误区，你能敏锐地察觉到**理论定义**与**工程实现**的冲突，说明你已经在思考“代码是怎么在硬件上跑的”了。
|
||
|
||
简单直接的回答：**教科书上的 $P$、$V$ 定义为了逻辑清晰，常用 `while` 叙述；但工业级操作系统（如 Linux）为了性能，绝对不会真的用 `while` 忙等。**
|
||
|
||
---
|
||
|
||
### 1. 理论定义（Dijkstra 的原始逻辑）
|
||
在很多操作系统教材中，为了让你理解信号量的**原子性**，会写成这样：
|
||
|
||
$$
|
||
\text{P(S): } \text{while (S <= 0) \{ do nothing \}; } S = S - 1;
|
||
$$
|
||
$$
|
||
\text{V(S): } S = S + 1;
|
||
$$
|
||
|
||
这种写法叫 **忙等（Busy-waiting）**。如果 $S=0$，CPU 就会像疯了一样在这个 `while` 循环里空转。这在单核时代是灾难性的（占着 CPU 不放，别人没机会改 $S$），在多核时代也非常费电。
|
||
|
||
---
|
||
|
||
### 2. 真实流程：挂起与唤醒（Sleep & Wakeup）
|
||
在 Linux 内核（如 `semaphore.h`）中，信号量被定义为一个包含**计数器**和**等待队列**的结构体：
|
||
|
||
```c
|
||
struct semaphore {
|
||
unsigned int count; // 剩余资源数
|
||
struct list_head wait_list; // 正在“坐牢”的线程队列
|
||
};
|
||
```
|
||
|
||
#### $P$ 操作（对应 `sem_wait`）的真实动作：
|
||
1. **检查：** 如果 `count > 0`，直接 `count--`，打完收工。
|
||
2. **“坐牢”：** 如果 `count == 0`：
|
||
* 内核把当前线程的状态从 `TASK_RUNNING` 改为 `TASK_INTERRUPTIBLE`（**阻塞态**）。
|
||
* 把该线程的 PCB（进程控制块）挂到这个信号量的 `wait_list` 链表里。
|
||
* **重点：** 内核调用 `schedule()`，主动把 CPU 让给别人。**此时该线程不再消耗任何 CPU 指令。**
|
||
|
||
|
||
|
||
#### $V$ 操作（对应 `sem_post`）的真实动作：
|
||
1. **自增：** `count++`。
|
||
2. **放人：** 内核查看 `wait_list` 是否为空。
|
||
3. **唤醒：** 如果有人在排队，取回第一个线程，把它的状态改回 `TASK_RUNNING`（**就绪态**），扔进红黑树等 CPU 召唤。
|
||
|
||
---
|
||
|
||
### 3. 为什么会有 `while` 的错觉？
|
||
虽然内核不忙等，但在**用户态应用层**，有时你会看到类似这样的代码：
|
||
|
||
```c
|
||
while (sem_wait(&sem) != 0) { /* handle error */ }
|
||
```
|
||
|
||
这并不是在等信号量，而是在处理**信号中断（EINTR）**。比如线程在等信号量时突然收到了一个系统信号（Ctrl+C 之类的），`sem_wait` 会被强行返回。为了保证程序逻辑，我们需要用 `while` 重新去“等”。
|
||
|
||
---
|
||
|
||
### 4. 特例：自旋锁（Spinlock）
|
||
既然你提到了 `while`，有一种锁确实是这么干的——**自旋锁**。
|
||
* **适用场景：** 临界区非常短（比如只改一个变量），切来切去（上下文切换）比等几微秒还贵。
|
||
* **动作：** 真的就在 CPU 上 `while` 循环硬等。
|
||
* **注意：** 自旋锁通常用于多核系统，且严禁在持有自旋锁时睡觉。
|
||
|
||
---
|
||
|
||
### 总结
|
||
* **信号量/互斥量**：发现没资源 -> **睡觉（不费 CPU）** -> 被人叫醒。
|
||
* **自旋锁**：发现没资源 -> **死等（费 CPU）** -> 马上拿到。
|
||
|
||
你现在明白为什么面试官听到“信号量是用 while 循环实现的”会皱眉头了吗？因为他怕你把服务器的 CPU 跑冒烟了。
|
||
|
||
**最后考考你：既然 $P$、$V$ 操作涉及到修改 `count` 和操作 `wait_list`，如果两个 CPU 同时执行 $P$ 操作，会不会把 `count` 改乱？内核是如何保证 $P$、$V$ 操作本身是“原子”的？**（提示：这涉及到比信号量更底层的硬件指令。）
|
||
|
||
没错，你完全抓住了**现代操作系统实现同步的核心思想**：**用“通知-唤醒”机制替代“死循环查看”。**
|
||
|
||
我们可以把这种机制看作是一种**“订阅-发布”模式**：
|
||
|
||
1. **订阅（sem_wait/P操作）：** 线程 B 发现没资源了，它不是在大厅里一直喊“好了没？好了没？”，而是给内核留个**“回执”**（把自己的 TCB 挂在等待队列里），然后回宿舍**睡觉**（挂起）。
|
||
2. **发布（sem_post/V操作）：** 线程 A 生产完资源后，它执行 V 操作。这个操作本质上是告诉内核：“喂，货到了，去名单（等待队列）里挑个睡着的家伙叫醒它。”
|
||
3. **精准唤醒：** 内核收到 A 的信号，查名单，把 B 的状态从 `WAITING` 拨回到 `READY`。
|
||
|
||
---
|
||
|
||
### 解决最后的“原子性”谜题
|
||
|
||
你可能会问：**“那 P 和 V 操作内部修改 `count--` 或者操作队列时，如果两个 CPU 同时在改，不也乱套了吗？”**
|
||
|
||
为了保证 P 和 V 操作本身不被打断，操作系统动用了硬件级的“大杀器”：
|
||
|
||
#### 1. 硬件指令：CAS (Compare And Swap)
|
||
现代 CPU 提供了原子指令（如 x86 的 `LOCK CMPXCHG`）。
|
||
* **逻辑：** 它能在**一个指令周期**内完成“读取-比较-修改”三个动作。
|
||
* **效果：** 硬件保证在这一瞬间，没有其他 CPU 核心能修改这个内存地址。这就是所有高层锁（Mutex, Semaphore）的**物理地基**。
|
||
|
||
|
||
|
||
#### 2. 关中断 (Disable Interrupts)
|
||
在内核修改等待队列的短短几微秒内，CPU 会暂时**关闭硬件中断**。
|
||
* **逻辑：** 既然中断关了，就不会发生时钟中断，也就不会触发调度。
|
||
* **效果：** CPU 能够一口气把线程从队列里挪走，保证操作的连贯性。
|
||
|
||
---
|
||
|
||
### 总结你的“内核大图景”
|
||
|
||
现在你可以串联起整个叙述逻辑了：
|
||
|
||
* **宏观层：** 进程和线程在 CPU 上轮转（调度）。
|
||
* **中观层：** 遇到锁或信号量，线程不忙等，而是**阻塞入队**，让出 CPU 给别人，等待被信号**唤醒**。
|
||
* **微观层：** 内核利用 **CAS 指令** 和 **关中断** 确保“入队”和“唤醒”这些管理动作本身是绝对安全的（原子的）。
|
||
|
||
|
||
|
||
### 下一步建议
|
||
你已经从理论叙述跨越到了底层实现。如果你感兴趣，我们可以聊聊：
|
||
* **协程（Coroutine）**：比如 Go 语言或 Python 的 `async`，它们在用户态是怎么模拟这一套“挂起-唤醒”逻辑的？（这比内核切换更轻量）。
|
||
* **分布式锁**：如果不是一台电脑，而是两台服务器要争夺一个资源，信号量还管用吗？
|
||
|
||
**或者，你觉得关于“信号量 vs 忙等”这个点，还有哪里让你觉得不够直观吗？** |