3.7　避免死锁

本节概览：先建立「避免死锁」的框架，再依次展开下列小节。

1. 系统安全状态
2. 利用银行家算法避免死锁

安全状态：系统能按某种进程推进顺序（P1，P2，…，Pn）为每个进程分配所需资源，使每个进程都能顺利完成。此时称该序列为安全序列。

系统状态分为安全状态和不安全状态：安全状态可避免死锁，不安全状态可能进入死锁。

例：系统有三个进程 P1、P2、P3，共 12 台磁带机。T0 时刻存在安全序列（P1、P2、P3），按此序列分配资源每个进程都能顺利完成，故系统安全。

如果不按安全序列分配资源，系统可能由安全状态进入不安全状态。

例：T0 时刻后 P3 又请求一台磁带机，系统进入不安全状态。

银行家算法需设置四个数据结构，描述系统中可利用资源、所有进程的最大需求、资源分配情况以及各进程还需多少资源。

1. 可利用资源向量 Available
2. 最大需求矩阵 Max
3. 分配矩阵 Allocation
4. 需求矩阵 Need

设 Requesti 是进程 Pi 的请求向量，Pi 发出资源请求后系统按以下步骤检查。

1. 如果 Requesti[j]≤Need[i,j]，转向下一步；否则出错（超过所宣布最大值）
2. 如果 Requesti[j]≤Available[j]，转向下一步；否则等待
3. 系统试探分配并执行安全性检查

系统试探着把资源分配给进程 Pi，修改数据结构：Available[j] -= Requesti[j]; Allocation[i,j] += Requesti[j]; Need[i,j] -= Requesti[j]。

然后执行安全性算法检查分配后系统是否安全：若安全才正式分配；否则作废本次试探，恢复原状，Pi 等待。

安全性算法步骤。

1. 设置工作向量 Work := Available 和 Finish[i] := false
2. 找满足 Finish[i]=false 且 Need[i,j]≤Work[j] 的进程，若找到执行下一步，否则转步骤 4
3. 进程 Pi 获得资源后执行至完成并释放资源：Work[j] += Allocation[i,j]; Finish[i] := true，回到步骤 2
4. 若所有进程 Finish[i]=true 则系统安全，否则不安全

进程获得资源后可顺利执行直至完成，释放分配给它的资源：Work[j] = Work[j] + Allocation[i,j]; Finish[i] = true。

若所有进程 Finish[i]=true 都满足，则系统处于安全状态；否则不安全。

例：系统有五个进程 {P0,P1,P2,P3,P4} 和三类资源 {A,B,C}，数量分别为 10、5、7。T0 时刻的资源分配情况如图所示。

T0 时刻的安全性：利用安全性算法分析可知，存在安全序列 {P1,P3,P4,P2,P0}，故系统是安全的。

结合图 3-16 理解 T0 时刻的安全序列。

P1 请求资源：P1 发出请求向量 Request1(1,0,2)，系统按银行家算法检查。

1. Request1(1,0,2)≤Need1(1,2,2)
2. Request1(1,0,2)≤Available(3,3,2)
3. 系统试探分配并修改 Available、Allocation1、Need1 向量

结合图 3-17 理解 P1 申请资源时的安全性检查。

P4 和 P0 请求资源的情况。

1. P4 请求 Request4(3,3,0)：检查 Request4≤Need4 且 Request4≤Available，试探分配后做安全性检查
2. P0 请求 Request0(0,2,0)：检查 Request0≤Need0 且 Request0≤Available，试探分配后做安全性检查

结合图 3-18 理解为 P0 分配资源后的有关资源数据。

进行安全性检查：可用资源 Available(2,1,0) 已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。