概述

多线程合作靠共享内存，但是访问同一个资源会引发竞态条件，最终导致数据不一致，这里的“同一个资源”就是临界区。那么依据什么规则保护，这就是控制临界区的原则。用信号量这个工具也可以保护临界区。

在合作过程中遇到资源互相等待的情况（死锁）可以用银行家算法解决，但是没有线程在使用时都用银行家算法检测一次，代价比较大。也可以定时去用银行家算法检测死锁，但是出现死锁恢复比较麻烦。由于死锁问题出现的概率比较低，因此大多数客户端操作系统选择忽略。

信号量

信号记录的是一个状态，而信号量表达的是更丰富的信息 。用来解决进程之间的同步问题。光定义信号量不能完全解决问题。是实现互斥的工具。本质上和互斥锁一样，用来保护临界区。用来解决“生产者-消费者”这种需要排队等待的协同问题。

临界区

同时只有一个进程操作的区域。也就是共享资源。进入临界区的时候有对应的实现逻辑，退出临界区的时候也要实现对应的逻辑。相当于加锁和解锁。

控制临界区的原则

• 互斥
• 有限等待（不能让线程一直等待）
• 有空让进（有空闲的时候就能进入）
• 让权等待（进阶要求）：如果进不去，进程应主动释放 CPU，避免白白消耗系统资源。

死锁问题

现象：cpu利用率特别低，但是程序特别慢。cpu 是空闲的，进程有一种在等待，导致程序特别慢。

出现原因

• 互斥使用(Mutual exclusion) 资源的固有特性，如道口 n
• 不可抢占(No preemption) 资源只能自愿放弃，如车开走以后 n
• 请求和保持(Hold and wait) 进程必须占有资源，再去申请 n
• 循环等待(Circular wait) 在资源分配图中存在一个环路

上述条件缺一不可，也就是使用信号量时会出现问题。如图所示，A 依赖B,B依赖C,C依赖D,D依赖A。

---

解决方案

有以下四种思路：

• 死锁预防
• 死锁避免：银行家算法，每次使用资源时都要调用该算法检测是否有死锁，消耗比较大
• 死锁检测+恢复：定期使用银行家算法进行检测，但是恢复难度较大。
• 死锁忽略：普通客户端采用。

银行家算法（死锁避免）

首先试算一下调用银行家算法，查看是否造成死锁，如果没有造成死锁，就可以执行。

有三个关键指标Available（可用资源向量）、Allocation（已分配矩阵）、Need（需求矩阵）。根据进程需要的资源和系统现有的资源进行推演。

具体步骤如下：

• 设置两个向量：工作向量 Work=AvailableWork=Available ，Finish 向量初始全为 false。
• 从进程集合中寻找满足以下条件的进程 PiPi ：

• • Finish[i]==falseFinish[i]==false
  • Needi≤WorkNeedi≤Work （即系统手里的闲钱够它还完最后的债）

• 如果找到这样的进程 PiPi ：

• • 假设 PiPi 获得资源并运行完成，释放其占有的所有资源： Work=Work+AllocationiWork=Work+Allocationi 。
  • 标记 Finish[i]=trueFinish[i]=true 。
  • 重复上述寻找过程。

• 判定结果：如果所有进程的 Finish[i]Finish[i] 都变为 true，则系统是安全的，刚才的试探性分配变为真实分配；否则，系统是不安全的，恢复原状，让 PiPi 等待。

下面是一个求安全序列的过程：首先找到需要的资源和系统能满足的，执行该线程，释放该线程的资源，依次类推就能得到安全的队列。