银行家算法
介绍
概念
银行家算法(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
