第三章

同步，通信与死锁

死锁产生

形成死锁的四个条件，全部满足才可能构成死锁：

（1）互斥：进程互斥使用资源；

（2）请求与保持：申请新资源时不释放已占有的资源；

（3）不可剥夺：一个进程不能抢夺其他进程占有的资源；

（4）循环等待：存在一组进程循环等待资源

死锁防止（破坏产生死锁的必要条件，防止死锁发生，将降低进程的并发度）

破坏死锁条件时：若破坏条件1（使资源可同时访问），条件2（静态分配：一个进程先申请所需的所有资源，都满足后再执行，效率低），条件3（请求新的资源前需要释放已占有资源）我们均不满意，考虑破坏条件4（按需分配策略）。

死锁避免

设系统有 $n$ 个进程和 $m$ 种资源：

死锁避免：通过合理的资源分配避免第四个条件（允许前三个条件发生），优点：并发度高。

死锁避免算法——银行家算法

银行家在贷款时，必须保证即便所有客户都同时来取款，银行手里的钱也足以支付（至少能满足一个人的最大需求，归还后再分给下一个人）。

银行家算法本质：在分配资源之前，先模拟分配后的结果。如果分配后系统处于“安全状态”，才真正分配；否则，拒绝请求并让进程等待。

安全状态：存在进程序列$P_1,P_2,\cdots,P_n$对进程$P_k$满足$$C_{ki}-A_{ki}\le V_i+\displaystyle \sum_{j=1}^{k-1}A_{ji},k=1,2,\cdots,n;i=1,2,\cdots,m$$，即对于$P_k$，若当前所剩的资源加上前面所有进程结束回收的所有资源满足其需求，可以顺次完成这些进程。
不安全状态：不存在这样的安全序列。不安全状态 $\neq$ 死锁，但它具有演变为死锁的风险。

实例：系统中共有5个进程和A，B，C三类资源，A类资源共有10个，B类资源共有5个，C类资源共有7个，在时刻$T_0$，系统目前资源分配情况如下：

进程	Allocation (已分配)	Claim (最大需求)	Need (还需资源)
	A B C	A B C	A B C
p0	0 1 0	7 5 3	7 4 3
p1	2 0 0	3 2 2	1 2 2
p2	3 0 2	9 0 2	6 0 0
p3	2 1 1	2 2 2	0 1 1
p4	0 0 2	4 3 3	4 3 1

A	B	C
3	3	2

该状态是安全的，存在安全序列 $\langle p1, p3, p0, p2, p4 \rangle$（序列不唯一，或$p_1,p_3,p_4,p_2,p_0$）。

当进程 $P_i$ 提出资源请求 $R_i$ 时（一个向量）：

判断这一分配后系统是否安全，若安全则执行分配，否则拒绝请求。

银行家算法在实际操作系统中很少直接使用，因其计算开销大。寻找安全序列时，最坏情况下需遍历所有进程。对 $n$ 个进程和 $m$ 种资源，总时间复杂度为 $O(m n^2)$。

局限性：

死锁检测和解除

（堵不如疏）系统对资源分配不做限制，允许死锁，并定期运行死锁检测程序，一旦发现死锁，将其解除。但太频繁运行则浪费处理器资源，太稀疏运行则影响死锁进程效率。

构造进程—资源分配图。

（1）进程—资源分配图无环，没有死锁

（2）进程—资源分配图有环，且每个资源类中仅有一个资源，则发生死锁

（3）进程—资源分配图有环，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件

如果能在进程—资源分配图中消去此进程的所有请求边和分配边，则其成为孤立结点。如果能使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的。

系统为死锁状态当且仅当该状态的进程—资源分配图是不可完全简化的

死锁解除方法：

（1）重启所有死锁进程方法

（2）逐个撤销陷于死锁的进程，回收其资源重新分派，直至死锁解除

（3）剥夺陷于死锁的进程占用的资源，但并不撤销它，直至死锁解除

（4）根据系统保存的检查点，让所有进程回退，直到足以解除死锁

（5）如果存在某些未卷入死锁的进程，而随着这些进程执行到结束，有可能释放足够的资源来解除死锁