04. 进程并发、PV 信号量机制与死锁避免

💡 交互图解

本章理论对应的动态微观仿真位于：👉 CS 10 图全屏走查 · FIG 04 并发互斥与银行家死锁算法

1. 信号量机制（Semaphores）核心语义

荷兰计算机科学家 Dijkstra 提出的信号量机制由一个整型变量 $S$ 和两个原子原语 $P$（wait）、$V$（signal）构成：

struct semaphore {
    int value;
    struct process_queue *L; // 阻塞等待队列
};

void P(semaphore S) {
    S.value--;
    if (S.value < 0) {
        // 当前可用资源已耗尽，将当前进程加入阻塞队列挂起
        block(S.L);
    }
}

void V(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        // 依然有等待者，从阻塞队列中唤醒一个进程进入就绪态
        wakeup(S.L);
    }
}

核心法则：

• $S.value>0$：表示系统中当前可用资源的空闲数量；
• $S.value==0$：表示资源恰好全部分配完毕，且无进程等待；
• $S.value<0$：$|S.value|$ 绝对值精确表示当前阻塞在等待队列中的进程总数！

---

2. 生产者-消费者（Producer-Consumer）模型精要

在大小为 $N$ 的环形缓冲区（Circular Buffer）中，生产者放入产品，消费者取走产品：

semaphore mutex = 1; // 临界区互斥锁 (保护对缓冲槽 in/out 的并发读写)
semaphore empty = N; // 资源信号量：当前空槽位总数
semaphore full  = 0; // 资源信号量：当前满槽位 (已有产品) 总数

// 生产者进程
void producer() {
    while (1) {
        Item item = produce_item();
        P(empty);   // 1. 先申请空槽位 (资源信号量)
        P(mutex);   // 2. 再锁临界区 (互斥信号量)
        
        buffer[in] = item;
        in = (in + 1) % N;
        
        V(mutex);   // 3. 释放临界区锁
        V(full);    // 4. 满槽位+1，唤醒阻塞的消费者
    }
}

// 消费者进程
void consumer() {
    while (1) {
        P(full);    // 1. 先申请满槽位
        P(mutex);   // 2. 进入临界区
        
        Item item = buffer[out];
        out = (out + 1) % N;
        
        V(mutex);
        V(empty);   // 唤醒生产者
        consume_item(item);
    }
}

408 核心警示：P 操作的顺序绝不能颠倒！ 若生产者写成 P(mutex); P(empty);： 当缓冲区已满时（empty == 0），生产者先拿到了 mutex 锁，接着执行 P(empty) 陷入阻塞。 此时消费者想去消费以释放空槽，但在第一步 P(mutex) 就会被挡在外面——生产者握着锁等空槽，消费者等锁来造空槽，系统陷入不可逆死锁！

---

3. 死锁的四大必要条件

死锁发生必须同时满足四个条件：

1. 互斥条件（Mutual Exclusion）：资源在一段时间内只能被一个进程独占；
2. 占有并等待（Hold and Wait）：进程持有了至少一个资源，同时又申请被其他进程占有的新资源；
3. 不可剥夺（No Preemption）：进程获得的资源在未使用完之前不能被强行夺走；
4. 循环等待（Circular Wait）：存在一个进程-资源循环等待环路 $\{P_0\to P_1\to \cdots \to P_n\to P_0\}$。

---

4. 银行家算法（Banker's Algorithm）推演法则

银行家算法属于**死锁避免（Deadlock Avoidance）**策略，在每次响应进程的资源请求前，先进行“安全性检查（Safety Algorithm）”。

核心数据结构

• 可利用资源向量 $Available[m]$
• 最大需求矩阵 $Max[n][m]$
• 已分配矩阵 $Allocation[n][m]$
• 尚需资源矩阵 $Need[n][m]=Max-Allocation$

安全性推演步骤

1. 设置工作向量 $Work=Available$，$Finish[n]=[false,\dots ]$；
2. 寻找满足 $Finish[i]==false$ 且 $Need[i]\le Work$ 的进程 $P_i$；
3. 若找到，假想该进程顺利获得资源并运行结束，释放其占有的全部资源：$$Work=Work+Allocation[i];Finish[i]=true;$$将 $P_i$ 追加到安全序列末尾，回到第 2 步；
4. 若所有进程的 $Finish$ 都为 $true$，则系统处于 安全状态（Safe State），找到的安全序列就是一条确保绝不死锁的调度路线！

---

5. 生产级实战：如何从架构上预防死锁？

在微服务分布式事务、MySQL 行锁、并发编程（如 Java ReentrantLock、Go sync.Mutex）中：

1. 打破循环等待（Lock Ordering）：为所有全局资源编上唯一全局递增 ID，所有线程必须严格按从小到大的顺序申请锁。只要不存在逆序申请，循环等待环路在拓扑上根本无法闭环！
2. 超时尝试获取锁（tryLock with timeout）：打破“占有并等待”和“不可剥夺”，如果一个线程在指定时间内没能获取全部锁，主动释放自己已占有的所有锁并随机退避重试（Exponential Backoff）。