一、实验内容
银行家算法是避免死锁的一种重要方法，本实验要求编写和调试一个简单的银行家算法程序。
1．设计进程对各类资源最大申请表示及初值的确定。
2．设定系统提供资源的初始状况。
3．设定每次某个进程对各类资源的申请表示。
4．编制程序，依据银行家算法，决定其资源申请是否得到满足。
5．显示资源申请和分配时的变化情况。
二、背景知识
1．死锁的相关知识。在多道程序环境中，多个进程可以竞争有限数量的资源。当一个进程申请资源时，如果这时没有可用资源，那么这个进程进入等待状态。有时，如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态。这种情况称为死锁。
2．银行家算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
3．系统安全性检查。
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都满足， 则表示系统处于安全状态；否则，系统处于不安全状态;
三、思路
四、核心代码(添加注释)
#include#include #include using namespace std; struct p { int Max[100][100];//最大需求矩阵 int Allocation[100][100];//分配矩阵 int Need[100][100];//需求矩阵 int Available[100];//可利用资源 int Resource[100];//总资源 int Work[100];//正工作资源 int Finish[100]; //判断进程是否已完成 int List[100];//存放安全序列的下标序列 }; class yinhangjia { public: void initial(int N, int M, struct p* s); //输入数据 void printState(int N, int M, struct p* s);//输出当前状态表 int isfinish(int N, int M, struct p* s, int C);//判断是否满足资源更换条件 int issafe(int N, int M, struct p* s);//判断是否为合法资源 void printList(int N, int M, struct p* s);//输出安全序列表 void reqresource(int N, int M, struct p* s, int i, int Request[]);//输入更改资源，并判断是否合法 }; void yinhangjia :: initial(int N, int M, struct p* s) //创建初始状态：先输入 Resource、Max和 Allocation，再计算出 Need、Available。 { int i, j; cout << "Resource--输入M种资源的总数量:n"; for (i = 0; i < M; i++) { cin >> s->Resource[i]; s->Available[i] = s->Resource[i]; } cout << "Max--输入N个进程分别对M种资源的最大需求量:n"; for (j = 0; j < N; j++) for (i = 0; i < M; i++) cin >> s->Max[j][i]; cout << "Allocation--输入N个进程获得M种资源的数量:n"; for (j = 0; j < N; j++) for (i = 0; i < M; i++) cin >> s->Allocation[j][i]; for (j = 0; j < N; j++)//求出需求need量 ，通过最大需求量-已经占用的资源数量 for (i = 0; i < M; i++) s->Need[j][i] = s->Max[j][i] - s->Allocation[j][i]; for (j = 0; j < M; j++)//求出可用Available量 for (i = 0; i < N; i++) s->Available[j] = s->Available[j] - s->Allocation[i][j]; } void yinhangjia ::printState(int N, int M, struct p* s) //输出当前的状态表|Process |Max |Allocation |Need |Available | { int j, i; cout << "n状态表如下:n"; cout << "|Process "; cout << "|Max"; for (int k = 0; k < M * 4 - 3; k++) cout << " "; cout << "|Allocation"; for (int k = 0; k < M * 4 - 10; k++) cout << " "; cout << "|Need"; for (int k = 0; k < M * 4 - 4; k++) cout << " "; cout << "|Available"; for (int k = 0; k < M * 4 - 9; k++) cout << " "; cout << "|n"; for (i = 0; i < N; i++) { cout << i; for (int k = 0; k < M; k++) cout << s->Max[i][k]; cout << "|"; for (int k = 0; k < M; k++) cout << s->Allocation[i][k]; cout << "|"; for (int k = 0; k < M; k++) cout << s->Need[i][k]; cout << "|"; if (i == 0) { for (int k = 0; k < M; k++) cout << s->Available[k]; cout << "|"; } cout << endl; } } int yinhangjia :: isfinish(int N, int M, struct p* s, int C) //返回同时满足两个条件{①Finish[i]=false; ②Need[i][j]≤Work[j]}的进程下标 i(修改Finish[i]=true)，否则返回-1。 { int i, j, count, b = 0; static int k = 0; //printf("%dn",k); cout << k << endl; for (i = C; i < N; i++) { for (j = 0, count = 0; j < M; j++)//判断单个进程是否符合安全序列 if (s->Finish[i] == 0 && s->Need[i][j] <= s->Work[j]) { count++; } if (count == M) { for (j = 0; j < M; j++) s->Work[j] += s->Allocation[i][j];//进程完成后，释放的空间加到现在闲置的空间内 s->Finish[i] = 1;//将进程修改为已完成状态 k++; if (k == N) k = 0; //printf("%dn",k); cout << k << endl; return i; } if (i == N - 1 && k < N) { i = -1; b++; } if (b == 2) break; } return -1; } int yinhangjia :: issafe(int N, int M, struct p* s) //判定当前状态是否为安全状态 （返回 true 或 false），把安全序列的下标放入 List[N]数组。 { int i, a, count = 0, C = 0; for (i = 0; i < M; i++) s->Work[i] = s->Available[i];//工作资源数 for (i = 0; i < N; i++) s->Finish[i] = 0; for (i = 0; i < N; i++) { a = isfinish(N, M, s, C); //printf("%d ?an",a); //cout << a << endl; if (a != -1) { s->List[i] = a; C = a; count++; //printf("%d ,n",count); //cout << count << endl; } else if (a == -1) C = 0; } if (count == N) return 1; else return 0; } void yinhangjia :: printList(int N, int M, struct p* s) //输出安全序列表|Process |Work |Need |Allocation |Work+Alloc |Finish | { int i, j; cout << "n安全序列表如下:n"; cout << "|Process "; cout << "|Work"; for (int k = 0; k < M * 4 - 4; k++) cout << " "; cout << "|Need"; for (int k = 0; k < M * 4 - 4; k++) cout << " "; cout << "|Allocation"; for (int k = 0; k < M * 4 - 10; k++) cout << " "; cout << "|Work+Alloc"; for (int k = 0; k < M * 4 - 10; k++) cout << " "; cout << "|Finish"; for (int k = 0; k < M * 4 - 6; k++) cout << " "; cout << endl; for (j = 0; j < M; j++) { s->Work[j] = s->Available[j]; } for (i = 0; i < N; i++) { cout << s->List[i]; for (int k = 0; k < M; k++) cout << s->Work[k]; cout << "|"; for (int k = 0; k < M; k++) cout << s->Need[s->List[i]][k]; cout << "|"; for (int k = 0; k < M; k++) cout << s->Allocation[s->List[i]][k]; cout << "|"; for (int k = 0; k < M; k++) cout << s->Work[k] + s->Allocation[s->List[i]][k]; cout << "|true"; for (int k = 0; k < M * 4 - 4; k++) cout << " "; cout << "|n"; for (j = 0; j < M; j++) s->Work[j] += s->Allocation[s->List[i]][j]; } } void yinhangjia :: reqresource(int N, int M, struct p* s, int i, int Request[]) //表示第 i个进程请求 M类资源 request[M] { int flag, count1, count2; int j; //Step1: 判断条件 Request[j]≤Need[i][j] for (j = 0, count1 = 0; j < M; j++) if (Request[j] <= s->Need[i][j]) count1++; //Step2: 判断条件 Request[j]≤Available[j] for (j = 0, count2 = 0; j < M; j++) if (Request[j] <= s->Available[j]) count2++; if (count2 != M) cout << "n尚无足够的资源，第" << i << "个进程堵塞。n"; //Step3: 预先分配 if (count2 == M && count1 == M) { for (j = 0; j < M; j++) { s->Available[j] = s->Available[j] - Request[j]; s->Allocation[i][j] = s->Allocation[i][j] + Request[j]; s->Need[i][j] = s->Need[i][j] - Request[j]; //printf("%d %d %dn",s->Available[j],s->Allocation[i][j],s->Need[i][j]); //cout << s->Available[j]; //cout << s->Allocation[i][j]; //cout << s->Need[i][j]; //cout << endl; } if (issafe(N, M, s) == 0) { cout << "n不存在安全序列，不是安全状态。n"; for (j = 0; j < M; j++) { s->Available[j] = s->Available[j] + Request[j]; s->Allocation[i][j] = s->Allocation[i][j] - Request[j]; s->Need[i][j] = s->Need[i][j] + Request[j]; } } else { cout << "n是安全序列分配成功!n"; yinhangjia:printList(N, M, s); } } } int main(void) { int reqid = -1, j, req[100]; struct p s; int N, M; cout << "please input MAX resources and MAX processes :"; cin >> M >> N; yinhangjia a;//构造银行家类a a.initial(N, M, &s); //创建数据 if (a.issafe(N, M, &s) == 0) { printf("Initial state is unsafe!n"); } else { a.printState(N, M, &s); //输出当前状态表 cout << "nInitial state is safe!n" << endl; a.printList(N, M, &s); //输出安全序列表 cout << "Input the id of request process:" ; cin >> reqid; while (reqid >= 0 && reqid < N) //输入进程 id是否合法 { cout << "Input request resources:"; for (j = 0; j < M; j++) { cin >> req[j]; } a.reqresource(N, M, &s, reqid, req); a.printState(N, M, &s); cout << "Input the id of request process:"; cin >> reqid; } cout << "n输入错误，退出程序!n"; } return 0; }
五、运行结果
输出状态表和安全序列表
若有足够的资源给请求的资源，则输出新的状态表
若没有足够的资源给请求的资源，则显示进程堵塞并输出状态表
六、结论
1.银行家算法是一种用来避免操作系统死锁出现的有效算法。
2.死锁：是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
3.死锁的发生必须具备以下四个必要条件：
1）互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
2）请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
3）不抢占条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4）循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。
4.银行家算法是避免死锁的一种重要方法，防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。
5.为实现银行家算法，系统必须设置若干数据结构，同时要解释银行家算法，必须先解释操作系统安全状态和不安全状态。
6.安全序列:是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
7.安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。
8.安全状态一定是没有死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁
