银行家算法
介绍
概念
银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。
银行家算法中的数据结构
为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
- 可利用资源向量 Available：这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。
- 最大需求矩阵Max：这是一个n x m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj 类资源的最大数目为K。
- 分配矩阵 Allocation：这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,jl = K，则表示进程i当前己分得Rj类资源的数目为K。
- 需求矩阵Need：这也是一个n × m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。
上述三个矩阵间存在下述关系:
Need[i,j] = Max[i,j] - Allocation[i, j]
银行家算法详述：
设 Request；是进程Pi的请求向量，如果 Requesti[j] = K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检査:
- 如果 Requesti[j] ≤ Need[i,j]便转向步骤2 否则认为出错，因为它所需要的资源数已超过它所事先声明需要的最大值。
- 如果 Requesti[j] ≤ Available[j]，便转向步骤3；否则，表示尚无足够资源，Pi须等待。
- 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值
Available[j] = Available[j] - Requesti[j];
Allocation[i,j] = Allocation[i,j] + Requesti[j];
Need[i,j] = Need[i,j] - Requesti[j]; - 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待
安全性算法:
系统所执行的安全性算法可描述如下:
- 设置两个向量:
- 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work = Available；
- Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finish[i] = false；当有足够资源分配给进程时，再令Finish[i] = true。
- 从进程集合中找到一个能满足下述条件的进程
① Finish[i] = false;
② Need[i,j] ≤ Work[j];
若找到，执行步骤3，否则，执行步骤4。 - 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:
Work[j] = Work[j] + Allocation[i,j];
Finish[i] = true;
go to step 2; - 如果所有进程的 Finish[i] =true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
代码
我用C++手写了一份算法的具体实现代码
#include<iostream>
#define MAX 100
using namespace std;
int totalResource,totalProcess;
int Max[MAX][MAX]; // 最大需求矩阵max
int Allocation[MAX][MAX]; // 分配矩阵
int Need[MAX][MAX]; // 最多还需要资源矩阵
int Available[MAX]; // 可用资源向量
void inputMaxMartix() {
cout << "请输入Max矩阵的数据：" << endl;
for(int i=0; i<totalProcess; i++) {
for(int j=0; j<totalResource; j++) {
cin >> Max[i][j];
}
}
}
void inputAllocationMartix() {
cout << "请输入Allocation矩阵的数据：" << endl;
for(int i=0; i<totalProcess; i++) {
for(int j=0; j<totalResource; j++) {
cin >> Allocation[i][j];
}
}
}
void inputAvailable() {
cout << "请输入Available资源向量" << endl;
for(int i=0; i<totalResource; i++) {
cin >> Available[i];
}
}
// 通过Max矩阵和Allocation矩阵的数据来计算Need矩阵
void calculateNeed() {
for(int i=0; i<totalProcess; i++) {
for(int j=0; j<totalResource; j++) {
Need[i][j]=Max[i][j]-Allocation[i][j];
}
}
}
// 输出当前数据
void print() {
cout << "当前资源分配情况：" << endl;
cout << "进程ID" << "\t\t" << "Max" << "\t\t" << "Allocation" << "\t\t" << "Need" << endl;
for(int i=0; i<totalProcess; i++) {
cout << i << "\t\t\t";
for(int j=0; j<totalResource; j++) {
cout << Max[i][j] << " ";
}
cout << "\t\t\t";
for(int j=0; j<totalResource; j++) {
cout << Allocation[i][j] << " ";
}
cout << "\t\t\t";
for(int j=0; j<totalResource; j++) {
cout << Need[i][j] << " ";
}
cout << endl;
}
cout << "各类资源可用数量：" << endl;
for(int i=0; i<totalResource; i++) {
cout << Available[i] << " ";
}
cout << endl;
}
//安全性检查函数
bool check() {
int safeSeq[totalProcess];
int work[totalResource];
int count = 0; // 安全序列Cursor;
bool finish[totalProcess];
for(int i=0; i<totalProcess; i++) {
safeSeq[i] = 0;
finish[i] = false;
}
for(int i=0; i<totalResource; i++) {
work[i] = Available[i];
}
int unfinished = totalProcess;
bool flag;
do {
for(int i=0; i<totalProcess; i++) {
if(finish[i] == false) {
flag = true;
for(int j=0; j<totalResource; j++) {
if(Need[i][j] > work[j]) {
flag = false;
break;
}
}
if(flag) {
finish[i] = true;
safeSeq[count++] = i;
for(int j=0; j<totalResource; j++) {
work[j] += Allocation[i][j];
}
}
}
}
unfinished--;
} while(unfinished>0);
flag = true;
// 判断是否所有进程都完成
for(int i=0; i<totalProcess; i++) {
if(finish[i]==false) {
flag=false;
break;
}
}
// 判断是否安全
if(flag==false) {
cout << "系统处于不安全状态！" << endl;
} else {
cout << "系统当前为安全状态，安全序列为：" << endl;
for(int i=0; i<totalProcess; i++) {
cout << safeSeq[i] << " ";
}
cout << endl;
}
return flag;
}
void handleRequest() {
int requestPid;
int request[totalResource];
int snapShotOfAvailable[totalResource];
int snapShotOfAllocation[totalResource];
int snapShotOfNeed[totalResource];
cout << "请输入请求资源的ID：" << endl;
cin >> requestPid;
cout << "请输入请求向量Request：" << endl;
for(int i=0; i<totalResource; i++) {
cin >> request[i];
}
for(int i=0; i<totalResource; i++) {
if(request[i] > Need[requestPid][i]) {
cout << "请求资源数大于需要数量，分配失败" <<endl;
return;
}
if(request[i] > Available[i]) {
cout << "可用资源不足，分配失败" << endl;
return;
}
}
// 尝试分配
for(int i=0; i<totalResource; i++) {
//保存快照
snapShotOfAvailable[i] = Available[i];
snapShotOfAllocation[i] = Allocation[requestPid][i];
snapShotOfNeed[i] = Need[requestPid][i];
// 进行尝试分配
Available[i] -= request[i];
Allocation[requestPid][i] += request[i];
Need[requestPid][i] -= request[i];
}
// 打印当前资源情况
print();
if(check() == false) { // 不安全，返回分配
// 恢复快照
for(int i=0; i<totalResource; i++) {
// 进行尝试分配
Available[i] = snapShotOfAvailable[i];
Allocation[requestPid][i] = snapShotOfAllocation[i];
Need[requestPid][i] -= snapShotOfNeed[i];
}
}
}
int main() {
cout << "请输入进程数量：" << endl;
cin >> totalProcess;
cout << "请输入资源种类数量：" << endl;
cin >> totalResource;
inputMaxMartix();
inputAllocationMartix();
inputAvailable();
calculateNeed();
print();
check();
while(true){
char signal;
handleRequest();
cout << "输入Y继续，输入N退出" << endl;
cin >> signal;
if(signal == 'N'){
return 0;
}
}
}
文章评论
大发
wow
