银行家算法(Banker’s Algorithm)是一个避免死锁(Deadlock)的著名算法,是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统的安全运行。
多个进程动态地共享系统的资源可能会产生死锁现象。死锁的产生,必须同时满足四个条件,第一个是互斥条件,即一个资源每次只能由一个进程占用;第二个为请求和保持条件,即一个进程请求资源不能满足时,它必须等待,但它仍继续保持已得到的所有其它资源;第三个是不剥夺条件,任何一个进程不能抢占另一个进程已经获得且未释放的资源;第四个为循环等待条件,系统中存在若干个循环等待的进程,即其中每一个进程分别等待它前一个进程所持有的资源,防止死锁的机构只须确保上述四个条件之一不出现,则系统就不会发生死锁。在实验中假定系统中任一资源在每一时刻只能由一个进程使用,任何进程不能抢占其它进程正在使用的资源,当进程得不到资源时必须等待。因此只要资源分配策略能保证进程不出现循环等待,则系统就不会发生死锁。
二、算法背景简介 在银行中,客户申请贷款的数量是有限的,每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量,在满足所有贷款要求时,客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时,都应尽量满足客户的需要。在这样的描述中,银行家就好比 *** 作系统,资金就是资源,客户就相当于要申请资源的进程。
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。为实现银行家算法,系统必须设置若干数据结构。
要解释银行家算法,必须先解释 *** 作系统安全状态和不安全状态。
安全序列是指一个进程序列{P1,…,Pn}是安全的,即对于每一个进程Pi(1≤i≤n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
三、测试数据测试题目如下图所示:
测试数据文件banker.dat:
banker.cpp
#include#include #include #include using namespace std; const int M = 100; int pro = 0;//线程数目 int source = 0;//资源数目 queue safeq;//安全序列 //安全性算法 bool check(int available[], int max[][M], int allocation[][M], int need[][M]) { bool finished[100] = { false };//标记某一线程是否已经完成所有资源的借贷 int available2[100];//可利用资源向量available int max2[100][100];//最大需求矩阵max int allocation2[100][100];//分配矩阵allocation int need2[100][100];//需求矩阵need //为四个矩阵赋值 for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { available2[j] = available[j]; max2[i][j] = max[i][j]; allocation2[i][j] = allocation[i][j]; need2[i][j] = need[i][j]; } } while (1) { int sumNeed = 0; for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { sumNeed += need2[i][j]; } if (sumNeed != 0) { break; } } //如果need矩阵中所有的值都为0,即所有的需求都已经被满足 if (sumNeed == 0) { return true; } //用于标记是否满足了某个线程的请求,如果都无法满足,则出现了不安全队列 bool needflag = false; for (int i = 0; i < pro; i++) { bool flag = true; for (int j = 0; j < source; j++) { if (need2[i][j] > available2[j]) { flag = false; } } if (flag && !finished[i]) { needflag = true; safeq.push(i); for (int j = 0; j < source; j++) { allocation2[i][j] = allocation2[i][j] + need2[i][j]; need2[i][j] = 0; available2[j] = available2[j] + allocation2[i][j]; finished[i] = true; } } else { continue; } } if (!needflag) { cout << "出现了不安全序列!!n"; return false; } } return false; } //主函数 int main() { int available[100];//可利用资源向量available int max[100][100];//最大需求矩阵max int allocation[100][100];//分配矩阵allocation int need[100][100];//需求矩阵need cout << "正在读取数据文件n"; Sleep(2000); ifstream inFile; inFile.open("banker.dat"); if (!inFile.is_open()) cout << "文件打开时候出错!!" << endl; inFile >> pro >> source; cout << "共有" << pro << "个线程," << source << "种资源n"; if (pro >= 100 || source >= 100) { cout << "输入的线程或资源数目过大!!"; exit(0); } while (!inFile.eof()) { // 若未到文件结束一直循环 //读入available for (int i = 0; i < pro; i++) { inFile >> available[i]; } //读入max for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { inFile >> max[i][j]; } } //读入allocation for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { inFile >> allocation[i][j]; } } //读入need for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { need[i][j] = max[i][j] - allocation[i][j]; } } } inFile.close(); //打印提示信息 cout << "************************************************n"; cout << " 操作系统实验模拟银行家算法n"; cout << " 作者:CSDN Carmelo_7 主页: https://blog.csdn.net/Carmelo_7?spm=1000.2115.3001.5343n"; cout << "************************************************n"; cout << "AVAILABLE:n"; for (int i = 0; i < pro; i++) { cout << available[i] << " "; } cout << "n"; cout << "MAX:n"; for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { cout << max[i][j] << " "; } cout << "n"; } cout << "ALLOCATION:n"; for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { cout << allocation[i][j] << " "; } cout << "n"; } cout << "NEED:n"; for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { cout << need[i][j] << " "; } cout << "n"; } //检查当前状态是否安全 if (check(available, max, allocation, need) == true) { cout << "操作系统现有状态安全!n" << "安全序列为:"; while (!safeq.empty()) { cout << "P" << safeq.front() << " "; safeq.pop(); } } else { cout << "操作系统现有状态不安全!n"; exit(0); } //线程开始请求相应的资源 bb: while (true) { int proNo; int request[100]; cout << "输入请求的线程号:"; cin >> proNo; for (int i = 0; i < source; i++) { cout << "n输入线程对于资源" << i << "的请求数量:n"; cin >> request[i]; } //复制一份四个矩阵 int available2[100];//可利用资源向量available int max2[100][100];//最大需求矩阵max int allocation2[100][100];//分配矩阵allocation int need2[100][100];//需求矩阵need //为四个矩阵赋值 for (int i = 0; i < pro; i++) { for (int j = 0; j < source; j++) { available2[j] = available[j]; max2[i][j] = max[i][j]; allocation2[i][j] = allocation[i][j]; need2[i][j] = need[i][j]; } } for (int i = 0; i < source; i++) { if (available2[i] 测试数据文件banker.dat:
4 4 1 5 2 0 0 0 1 2 1 7 5 0 2 3 5 6 0 6 5 6 0 0 1 2 1 0 0 0 1 3 5 4 0 0 1 4欢迎分享,转载请注明来源:内存溢出
评论列表(0条)