一. 实验目的
（1）深入了解操作系统的安全状态和不安全状态；
（2）了解如何避免死锁；
（3）银行家算法是一种最有代表性的避免死锁的算法，掌握其原理及程序实现方法
二. 实验内容
（1）用银行家算法实现资源分配：假定系统中有5个进程{P0, P1, P2, P3, P4}和3类资源{A, B, C}，各类资源的数量分别为10、5、7。进程可以动态申请资源、释放资源，系统按进程的申请动态分配资源，要求程序具有显示和打印各进程的某一个时刻的资源分配表和安全序列；显示和打印各进程依次要求申请的资源号以及为某进程分配资源后的有关资源数据。
三. 实验步骤
（1）编写C程序：
#include<stdio.h> #include<string.h> typedef struct process{ char name[2]; int max[4],allocation[4],need[4]; bool flag; }p; void countNeed(p pro[],int available[],int available_01[],int proNumber,int sourNumber); int checkSafe(p pro[],int available[],int available_01[],int proNumber,int sourNumber,char requireName[],int requireSource[]); void printAll(p pro[],int available[],int proNumber,int sourNumber); int main(){ int proNumber,sourNumber,flag,i,j; scanf("%d",&proNumber); scanf("%d",&sourNumber); int available[sourNumber],available_01[sourNumber],requireSource[sourNumber]; p pro[proNumber]; char requireName[2]; //初始化资源总数 for(i=0;i<sourNumber;i++){ scanf("%d",&available[i]); } //初始化进程的资源使用情况 for(i=0;i<proNumber;i++){ scanf("%s",&pro[i].name); pro[i].flag = false; for(j=0;j<sourNumber;j++){ available_01[j] = available[j]; scanf("%d",&pro[i].max[j]); } for(j=0;j<sourNumber;j++){ scanf("%d",&pro[i].allocation[j]); } } //初始化请求进程及其资源请求数 scanf("%s",&requireName); for(j=0;j<sourNumber;j++){ scanf("%d",&requireSource[j]); } countNeed(pro,available,available_01,proNumber,sourNumber); flag = checkSafe(pro,available,available_01,proNumber,sourNumber,requireName,requireSource); if(flag == 0){ printf("可以找到安全序列，可以分配。\n"); printAll(pro,available_01,proNumber,sourNumber); } if(flag == 1){ printf("查无此进程。\n"); printAll(pro,available_01,proNumber,sourNumber); } if(flag == 2){ printf("需求不合理，不予分配。\n"); printAll(pro,available_01,proNumber,sourNumber); } if(flag == 3){ printf("剩余资源不足，不予分配。\n"); printAll(pro,available_01,proNumber,sourNumber); } if(flag == 4){ printf("找不到安全序列，不予分配。\n"); printAll(pro,available_01,proNumber,sourNumber); } return 0; } void countNeed(p pro[],int available[],int available_01[],int proNumber,int sourNumber){ int i,j; for(i=0;i<proNumber;i++){ for(j=0;j<sourNumber;j++){ pro[i].need[j] = pro[i].max[j] - pro[i].allocation[j]; available[j] -= pro[i].allocation[j]; available_01[j] = available[j]; } } } int checkSafe(p pro[],int available[],int available_01[],int proNumber,int sourNumber,char requireName[],int requireSource[]){ int i,j,sum=0,sum1=0,sum2=0,count=0,countRequire=-1; bool flagAll = false,flagAll_01 = false; //进行名称和请求资源数和need资源数的比较 for(i=0;i<proNumber;i++){ if(strcmp(requireName,pro[i].name) == 0) { countRequire=i; for(j=0;j<sourNumber;j++){ if(requireSource[j]<=pro[i].need[j]) sum1++; if(requireSource[j]<=available[j]) sum2++; } } } //printf("%d %d %d \n",countRequire,sum1,sum2); //countRequire != -1存在进程名称相等的进程 if(countRequire != -1&&sum1 == sourNumber &&sum2 == sourNumber){ //对请求的进程进行初始化 for(j=0;j<sourNumber;j++){ available[j] -= requireSource[j]; pro[countRequire].allocation[j] += requireSource[j]; pro[countRequire].need[j] -= requireSource[j]; } while(sum<proNumber){ for(i=0;i<proNumber;i++){ sum1 = 0; if(pro[i].flag == false){ for(j=0;j<sourNumber;j++){ if(pro[i].need[j]<=available[j]) sum1++; } if(sum1 == sourNumber) { for(j=0;j<sourNumber;j++) available[j] += pro[i].allocation[j]; pro[i].flag = true; sum++; } } } count+=6; if(count == 54) break; } } else if(countRequire == -1){ return 1; //1.若输入的进程的名字不正确，输出”查无此进程。“并输出当前系统状态。 }else if(sum1 != sourNumber) return 2; //2.若申请的资源数目大于最大需求，输出”需求不合理，不予分配。“并输出当前系统状态。 else if(sum2 != sourNumber) return 3; //3.若申请的资源数目大于剩余资源，输出”剩余资源不足，不予分配。“并输出当前系统状态。 if(sum == proNumber) { for(j=0;j<sourNumber;j++){ available_01[j] -= requireSource[j]; } return 0; //给人家分配！ } else if(sum != proNumber) { for(j=0;j<sourNumber;j++){ pro[countRequire].allocation[j] -= requireSource[j]; pro[countRequire].need[j] += requireSource[j]; } return 4; //4.若找不到安全序列，输出”找不到安全序列，不予分配。“并输出当前系统状态。 } } void printAll(p pro[],int available[],int proNumber,int sourNumber){ printf("name max allocation need available\n"); int i,j; for(i=0;i<proNumber;i++){ printf("%s ",pro[i].name); for(j=0;j<sourNumber;j++){ printf("%d ",pro[i].max[j]); } printf("| "); for(j=0;j<sourNumber;j++){ printf("%d ",pro[i].allocation[j]); } printf("| "); for(j=0;j<sourNumber;j++){ printf("%d ",pro[i].need[j]); } if(i == 0){ printf("| "); for(j=0;j<sourNumber;j++){ if(j == sourNumber-1) printf("%d",available[j]); else printf("%d ",available[j]); } }else printf("|"); printf("\n"); } }
四. 实验结果
五. 实验总结
银行家算法（Banker’s Algorithm）是一种用于避免死锁的资源分配算法，由荷兰计算机科学家Edsger Dijkstra在1965年提出。它的名字源于银行家在分配贷款时需要考虑资金的分配和回收。
银行家算法基于以下假设：每个进程都需要声明其对各类资源的最大需求量，系统有限数量的资源可供分配。银行家算法通过分析系统当前状态，判断是否存在安全序列，从而决定是否分配资源，以避免死锁发生。
具体而言，银行家算法分为两个阶段：安全性检查和资源分配。在安全性检查阶段，系统通过模拟分配资源给进程，并逐步回收，来判断是否存在安全序列。如果存在安全序列，即使分配资源后可能出现死锁，系统也会继续分配资源。否则，系统会拒绝分配资源，以避免死锁。在资源分配阶段，系统会根据安全性检查的结果分配资源给进程。
银行家算法的核心是安全性检查。安全性检查通过判断资源分配的可行性来避免死锁。它基于安全序列的概念，即一个进程执行完毕并释放资源后，系统能够找到一种资源分配的顺序，使得所有进程都能够正常执行完毕。如果存在安全序列，那么系统就可以继续分配资源；否则，系统会等待，直到存在安全序列。
银行家算法的优点是能够避免死锁，保证系统的安全性。但它的缺点是资源的分配需要满足严格的限制条件，可能导致资源利用率降低。
总之，银行家算法是一种用于避免死锁的资源分配算法，通过分析系统状态和判断安全序列来决定资源分配。它是操作系统中的重要算法之一，能够确保系统的安全性，提高系统的可靠性。
