1. 死锁的定义
死锁：多个进程因竞争资源而相互等待，若无外力干预，永远都无法继续执行。
进程 P1 持有资源 A，等待资源 B
进程 P2 持有资源 B，等待资源 A
P1 ───持有──→ 资源 A
↑ │
│ ↓
等待 等待
│ ↓
P2 ←──持有─── 资源 B
2. 死锁的四个必要条件
| 条件 | 说明 | 破坏策略 |
|---|---|---|
| 互斥 | 资源一次只能被一个进程占用 | 共享资源（如只读文件） |
| 占有并等待 | 持有资源同时等待新资源 | 一次性申请所有资源 |
| 不可抢占 | 已分配的资源不能被强制剥夺 | 资源可被抢占 |
| 循环等待 | 进程-资源形成环 | 资源有序分配 |
四个条件必须同时满足才会死锁，破坏任一条件即可预防。
3. 死锁处理策略
3.1 死锁预防
策略 1：破坏"占有并等待"
→ 进程运行前一次性申请所有所需资源
→ 缺点：资源利用率低，可能长时间占用不急需的资源
策略 2：破坏"不可抢占"
→ 进程申请新资源失败时，释放已持有的所有资源
→ 适用于状态可保存/恢复的资源
策略 3：破坏"循环等待"
→ 给资源编号，进程必须按编号递增顺序申请
→ 例：先申请打印机(1)，再申请磁盘(2)
3.2 死锁避免（银行家算法）
在资源分配前检查系统是否处于安全状态，若可能导致不安全则不分配。
def bank_algorithm(available, max_claim, allocation):
"""
available: 可用资源向量
max_claim: 各进程最大需求矩阵
allocation: 当前分配矩阵
need = max_claim - allocation
"""
n = len(max_claim) # 进程数
m = len(available) # 资源种类数
need = [[max_claim[i][j] - allocation[i][j]
for j in range(m)] for i in range(n)]
work = available[:]
finish = [False] * n
safe_sequence = []
while len(safe_sequence) < n:
found = False
for i in range(n):
if finish[i]:
continue
# 检查 need[i] <= work
if all(need[i][j] <= work[j] for j in range(m)):
for j in range(m):
work[j] += allocation[i][j]
finish[i] = True
safe_sequence.append(i)
found = True
break
if not found:
return None # 不安全状态
return safe_sequence
# 示例
available = [3, 3, 2]
max_claim = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]]
print(bank_algorithm(available, max_claim, allocation))
# 输出: [1, 3, 4, 0, 2]（安全序列）
3.3 死锁检测与恢复
检测：定期运行死锁检测算法（资源分配图是否有环）
恢复：
1. 进程终止：逐个终止死锁进程直到环解除
2. 资源剥夺：从某进程抢占资源分配给其他进程
4. 同步机制
4.1 信号量（Semaphore）
#include <semaphore.h>
// 初始化
sem_t sem;
sem_init(&sem, 0, 1); // 第二个 0=线程间，1=初始值
// P 操作（等待/减 1）
sem_wait(&sem); // 值 > 0 则减 1 继续；= 0 则阻塞
// V 操作（信号/加 1）
sem_post(&sem); // 加 1，唤醒等待线程
// 销毁
sem_destroy(&sem);
用信号量实现互斥：
sem_t mutex; // 初始值 = 1
void critical_section() {
sem_wait(&mutex); // P，进入临界区
// 临界区代码
sem_post(&mutex); // V，离开临界区
}
用信号量实现生产者-消费者：
sem_t empty; // 空槽数量，初始 = N
sem_t full; // 满槽数量，初始 = 0
sem_t mutex; // 互斥访问缓冲区，初始 = 1
void producer() {
while (1) {
item = produce();
sem_wait(&empty); // 等待空槽
sem_wait(&mutex); // 进入临界区
buffer[in] = item;
in = (in + 1) % N;
sem_post(&mutex); // 离开临界区
sem_post(&full); // 满槽 + 1
}
}
void consumer() {
while (1) {
sem_wait(&full); // 等待满槽
sem_wait(&mutex); // 进入临界区
item = buffer[out];
out = (out + 1) % N;
sem_post(&mutex); // 离开临界区
sem_post(&empty); // 空槽 + 1
consume(item);
}
}
注意：
sem_wait(&empty)和sem_wait(&mutex)顺序不能交换，否则可能死锁。
4.2 互斥锁（Mutex）
#include <pthread.h>
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&mutex); // 加锁
// 临界区
pthread_mutex_unlock(&mutex); // 解锁
互斥锁 vs 信号量：
| 特性 | 互斥锁 | 信号量 |
|---|---|---|
| 初始值 | 1（解锁）或 0（锁定） | 任意非负整数 |
| 用途 | 互斥 | 互斥 + 同步 |
| 持有者 | 有（只有加锁者能解锁） | 无 |
| 可重入 | 不可（同一线程多次加锁会死锁） | 可以 |
4.3 读写锁（Reader-Writer Lock）
pthread_rwlock_t rwlock = PTHREAD_RWLOCK_INITIALIZER;
// 读锁（多个读者可同时持有）
pthread_rwlock_rdlock(&rwlock);
// 读操作
pthread_rwlock_unlock(&rwlock);
// 写锁（独占）
pthread_rwlock_wrlock(&rwlock);
// 写操作
pthread_rwlock_unlock(&rwlock);
适用：读多写少场景，如缓存系统。
4.4 条件变量（Condition Variable）
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int ready = 0;
// 等待方
void waiter() {
pthread_mutex_lock(&mutex);
while (!ready) { // 必须用 while（防止虚假唤醒）
pthread_cond_wait(&cond, &mutex); // 原子释放锁并阻塞
}
// 条件满足，继续执行
pthread_mutex_unlock(&mutex);
}
// 通知方
void notifier() {
pthread_mutex_lock(&mutex);
ready = 1;
pthread_cond_signal(&cond); // 唤醒一个等待线程
// pthread_cond_broadcast(&cond); // 唤醒所有等待线程
pthread_mutex_unlock(&mutex);
}
为什么用 while 不用 if：被唤醒后应重新检查条件，因为可能其他线程已修改条件（虚假唤醒）。
4.5 管程（Monitor）
管程 = 共享数据 + 操作这组数据的过程 + 互斥锁 + 条件变量，封装在一起。
// Java synchronized 即管程支持
public class BoundedBuffer<T> {
private final T[] buffer;
private int count = 0, putptr = 0, takeptr = 0;
public synchronized void put(T x) throws InterruptedException {
while (count == buffer.length) {
wait(); // 等待未满条件
}
buffer[putptr] = x;
putptr = (putptr + 1) % buffer.length;
count++;
notifyAll(); // 通知可能等待的 take()
}
public synchronized T take() throws InterruptedException {
while (count == 0) {
wait(); // 等待非空条件
}
T x = buffer[takeptr];
takeptr = (takeptr + 1) % buffer.length;
count--;
notifyAll(); // 通知可能等待的 put()
return x;
}
}
5. 经典同步问题
5.1 哲学家就餐问题
五位哲学家围桌而坐，每人需要左右两把叉子才能就餐。如何避免死锁？
解决方案：
- 最多允许 4 位哲学家同时拿叉（信号量限制）
- 左右编号不一致时按顺序拿（破坏循环等待）
- 使用互斥锁保护拿叉动作（原子化）
// 方案 3：线程互斥拿叉
pthread_mutex_t mutex;
void philosopher(int i) {
pthread_mutex_lock(&mutex); // 原子拿两把叉子
take_fork(i); // 左叉
take_fork((i + 1) % 5); // 右叉
pthread_mutex_unlock(&mutex); // 释放锁（叉仍拿着）
eat();
put_fork(i);
put_fork((i + 1) % 5);
}
5.2 读者-写者问题
允许多个读者同时读，但写者独占。
int reader_count = 0;
pthread_mutex_t rc_mutex = PTHREAD_MUTEX_INITIALIZER; // 保护 reader_count
pthread_mutex_t rw_mutex = PTHREAD_MUTEX_INITIALIZER; // 写者互斥 / 第一个读者/最后一个读者
void reader() {
pthread_mutex_lock(&rc_mutex);
reader_count++;
if (reader_count == 1) {
pthread_mutex_lock(&rw_mutex); // 第一个读者阻止写者
}
pthread_mutex_unlock(&rc_mutex);
// 读...
pthread_mutex_lock(&rc_mutex);
reader_count--;
if (reader_count == 0) {
pthread_mutex_unlock(&rw_mutex); // 最后一个读者释放
}
pthread_mutex_unlock(&rc_mutex);
}
void writer() {
pthread_mutex_lock(&rw_mutex);
// 写...
pthread_mutex_unlock(&rw_mutex);
}
6. 总结
死锁：
预防：破坏四个必要条件之一
避免：银行家算法（安全状态检查）
检测：资源分配图环路检测
恢复：终止进程 / 资源剥夺
同步原语选择：
简单互斥 → 互斥锁
计数限制 → 信号量
读多写少 → 读写锁
等待特定条件 → 条件变量 + 互斥锁
高级封装 → 管程 / 语言级同步（Java synchronized）
参考文章
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。