银行家算法（C++实现）

目录

一、银行家算法概述

二、银行家算法需要的数组结构

三、算法概述

1.安全性算法

2.银行家算法

四、代码实现

五、实验结果验证

---

一、银行家算法概述

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

二、银行家算法需要的数组结构

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]

三、算法概述

1.安全性算法

系统所执行的安全性算法可描述如下：

（1）设置两个向量：

        ① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false; 当有足够资源分配给进程时， 再令Finish[i]=true。

（2）从进程集合中找到一个能满足下述条件的进程：

        ① Finish［i］=false;

        ② Need［i，j］≤Work［j］； 若找到， 执行步骤3)；否则，执行步骤4)。

（3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

        Work［j］=Work［i］+Allocation［i,j］;

        Finish［i］=true;

        go to step 2;

（4）如果所有进程的Finish[i]=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。

2.银行家算法

设Requesti是进程Pi的请求向量，如果表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

(1) 如果 ≤ Need[i,j]，转向步骤(2)，否则认为出错，因为它所需的资源数目已超过它所宣布的最大值。

(2) 若  ≤ Available[j]，转向步骤(3)，否则表示尚无足够资源，Pi必须等待。

(3) 系统尝试把资源分配给进程Pi，并修改下面数据结构中的数值：

Available[j] = Available[j] – 

Allocation[i,j] = Allocation[i,j] + 

Need[i,j] = Need[i,j] – 

(4) 系统执行安全性算法，检查此次分配后系统是否处于安全状态。若安全，才正式分配给Pi，完成此次分配；否则，此次试分配作废，恢复原来资源的分配状态，进程Pi等待。

四、代码实现

#includeusing namespace std;const int p=5;//进程数const int r=4;//资源种类int num = 1;//需要分配资源的进程序号void init_request(int request[r]){    //初始化request矩阵    cout