避免死锁之银行家算法

编程入门行业动态更新时间:2024-10-21 04:08:47

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

一、操作系统安全状态和不安全状态
要解释银行家算法，必须先解释操作系统安全状态和不安全状态。

安全状态指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量（后边会谈到安全性算法来判断是否为安全状态）
不安全状态指不存在这样的一个安全序列。

安全状态一定不产生死锁，不安全状态不一定会产生死锁。

下面以一个小例子解释安全状态：

答案是按照 <P2,P1,P3>的推进序列使用磁带机就是安全的。

安全序列判断过程：
1、现在的可用（可以分配）的资源数是 3 ，而 P2 需要的资源数是 2，所以可以分配
2、待 P2 执行完毕后，释放资源数为 4，变成可用资源，加上之前剩余的可用资源数，一共是 5 个
3、观察到 P1 需要 5 个，所以分配给 P1
4、P1 执行完后释放资源数为 10，变成可用资源
5、而 P3 只需要 7 个，所以分配 7 个可用资源个 P3
6、P3 运行完毕

二、银行家算法

1、数据结构
1）可利用资源向量Available
是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
4）需求矩阵Need。
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]

2、检测过程
1）假设 P1 进程提出请求 K 个资源
2）如果 K <= Need，就继续步骤；否则出错，因为请求资源 K 不能超过还需要获得的资源
3）如果 K <= Available，就继续步骤；否则出错，因为请求资源 K 不能超过系统还可以分配的资源 Available
4）系统试探分配资源，并修改下列数据
Available = Available - K；表示分配给 P1 K 个资源后，还剩多少系统可分配资源
Allocation = Allocation + K；表示 P1 已经获得的资源
Need = Need - K；表示进程 P1 还需要获得的资源
5）此时系统执行安全性算法，计算进程是否处于安全性状态