一、死锁概述

1. 死锁定义

死锁是指多个进程在执行过程中，由于竞争资源或彼此通信而造成的一种互相等待的现象，若无外力作用，这些进程都将无法继续执行下去。

2. 死锁产生的必要条件（Coffman条件）

• ​​互斥条件​​：资源一次只能由一个进程占用

• ​​占有并等待​​：进程持有至少一个资源，并等待获取其他被占用的资源

• ​​非抢占条件​​：已分配给进程的资源不能被其他进程强行夺取

• ​​循环等待条件​​：存在一个进程等待的循环链

3. 死锁处理策略

1. ​​预防死锁​​：破坏死锁必要条件

2. ​​避免死锁​​：运行时检查资源分配状态（如银行家算法）

3. ​​检测死锁​​：定期检查系统状态

4. ​​解除死锁​​：强制剥夺资源或终止进程

二、银行家算法详解

1. 算法背景

由Dijkstra提出，用于避免死锁的资源分配算法，模拟银行家发放贷款时的谨慎策略。

2. 数据结构

• ​​Available​​：长度为m的向量，表示各类资源的可用数量

• ​​Max​​：n×m矩阵，表示每个进程对各类资源的最大需求

• ​​Allocation​​：n×m矩阵，表示当前分配给每个进程的各类资源数量

• ​​Need​​：n×m矩阵，表示每个进程还需要的各类资源数量（Need = Max - Allocation）

3. 安全性算法

检查系统是否处于安全状态：

1.初始化：

• Work = Available

• Finish[i] = false (i=1,2,...,n)

2.寻找满足以下条件的进程i：

• Finish[i] == false

• Need[i] ≤ Work

3.若找到这样的进程：

• Work = Work + Allocation[i]

• Finish[i] = true 重复步骤2

4.若所有Finish[i] == true，则系统安全；否则不安全

4. 资源请求算法

当进程Pi发出资源请求Request[i]时：

1.若Request[i] ≤ Need[i]，继续；否则报错

2.若Request[i] ≤ Available，继续；否则Pi必须等待

3.系统试探性分配资源：

• Available = Available - Request[i]

• Allocation[i] = Allocation[i] + Request[i]

• Need[i] = Need[i] - Request[i]

4.执行安全性算法：

• 若安全，则正式分配

• 不安全则恢复原状态，Pi等待

5. 算法示例

假设系统有3类资源(A,B,C)，总量为(10,5,7)，有5个进程：

进程   Allocation    Max       Available
       A  B  C     A  B  C     A  B  C
P0     0  1  0     7  5  3     3  3  2
P1     2  0  0     3  2  2
P2     3  0  2     9  0  2
P3     2  1  1     2  2  2
P4     0  0  2     4  3  3

计算Need矩阵(Max - Allocation):

P0: 7 4 3
P1: 1 2 2
P2: 6 0 0
P3: 0 1 1
P4: 4 3 1

安全性检查：可以找到一个安全序列如<P1,P3,P4,P2,P0>

6. 算法特点

• ​​优点​​：

  • 避免死锁，保证系统安全

  • 适用于资源类型较多的系统

• ​​缺点​​：

  • 要求进程数固定

  • 需要事先知道最大资源需求

  • 计算开销较大

三、实际应用考虑

1.​​资源类型​​：算法适用于多种资源类型，不限于内存

​​2.性能影响​​：频繁执行会增加系统开销

3.​​动态环境​​：在进程动态创建/终止时需要调整

​​4.替代方案​​：在某些系统中可能采用更简单的死锁预防策略