1、了解什么是操作系统安全状态和不安全状态； 2、了解如何避免系统死锁； 3、理解银行家算法是一种最有代表性的避免死锁的算法，掌握其实现原理及实现过程。

Windows、g++

根据银行家算法的基本思想，编写和调试一个实现动态资源分配的模拟程序，并能够有效避免死锁的发生。

1、 画出银行家算法流程图； 2、 对算法所用的数据结构进行说明； 3、 测试数据随机产生。不可手工输入； 4、 编写程序并调试； 5、 多次测试程序，截屏输出实验结果； 6、 根据实验结果与理论课讲述的原理进行实验分析。

进程申请资源时，系统通过一定的算法判断本次申请是否不可能产生死锁（处于安全状态）。若可能产生死锁（处于不安全状态），则暂不进行本次资源分配，以避免死锁。算法有著名的银行家算法。 1、什么是系统的安全状态和不安全状态？ 所谓安全状态，是指如果系统中存在某种进程序列＜P1，P2，…，Pn＞，系统按该序列为每个进程分配其所需要的资源，直至最大需求，则最终能使每个进程都可顺利完成，称该进程序列＜P1，P2，…，Pn，＞为安全序列。 如果不存在这样的安全序列，则称系统处于不安全状态。 2、银行家算法 把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全，银行家规定: (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客; (2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量; (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时,对顾客的贷款可推迟支付,但总能使顾客在有限的时间里得到贷款; (4) 当顾客得到所需的全部资金后,一定能在有限的时间里归还所有的资金。

操作系统按照银行家制定的规则设计的银行家算法为： （1）进程首次申请资源的分配：如果系统现存资源可以满足该进程的最大需求量，则按当前的申请量分配资源，否则推迟分配。 （2）进程在执行中继续申请资源的分配：若该进程已占用的资源与本次申请的资源之和不超过对资源的最大需求量，且现存资源能满足该进程尚需的最大资源量，则按当前申请量分配资源，否则推迟分配。 （3）至少一个进程能完成：在任何时刻保证至少有一个进程能得到所需的全部资源而执行到结束。 银行家算法通过动态地检测系统中资源分配情况和进程对资源的需求情况来决定如何分配资源，并能在确保系统处于安全状态时才把资源分配给申请者，从而避免系统发生死锁。

因为是模拟程序，可以不使用系统调用函数。

该程序所用到的数据结构如下：

首先我定义了5类资源和5个进程，并把程序做成了菜单的形式（如图）

在程序运行之后，第一件事是随机生成当前的系统资源使用情况，因为后面我们还是需要对这个资源进行分配，所以我们生成数据的时候一定要保证当前系统是安全的，所以我们需要生成一个系统安全的数据，实现思路为：循环生成一段数据，直到生成的数据是系统安全的： 程序流程图如下：

检查当前系统是否安全，首先需要把available数组拷贝到work数组，拷贝的目的是为了在检查的过程中不破坏原来的available数组。检查当前系统是否安全，执行以下步骤：

先将finish数组全部置为false，表示目前没有进程已经完成。然后遍历全部进程，判断每个进程的need[i][j]是否为空，如果为空，则表示当前进程已经完成，执行finish[i] = true，finishNum += 1;

逐一遍历目前的进程，定义变量pid表示目前正在遍历到的进程，如果该pid满足以下条件，则跳到步骤3，否则pid+1后继续执行执行步骤2 ①finish[pid] = false; //当前进程未完成 ②对于每一个j∈[0, resources)，都满足need[pid][j] if(need[pid][j]){ return 0; } } return 1; } //目前资源使用情况 void info(){ printf("当前系统剩余资源："); for(int i = 0;i printf("%05d\t\t",i); //输出PID //输出maxRequest for(int j = 0;j printf("%-2d ",allocation[i][j]); } printf("\t\t"); //输出need for(int j = 0;j //初始化finish memset(finish,0,sizeof(finish)); int finishNum = 0; //已经完成的进程数量 int safeIndex = 0; //安全序列的下标 //复制available数组给work for(int i = 0;i if(isAllZero(i)){ finish[i] = 1; finishNum += 1; } } int lastFinishNum = -1;//上一趟循环之后完成的进程数量 int pid = 0; //当前是哪个进程 bool tag = 1; //标识系统是否安全 while(finishNum //pid==0，说明这是新的一趟循环 //如果一趟循环之后，完成的进程数量都还没有增加，那么剩下的资源都不可能有完成的了，所以不安全 if(finishNum == lastFinishNum){ tag = 0; break; } lastFinishNum = finishNum; } if(finish[pid]){ ++pid; continue; //当前进程已完成，跳过 } num = 0; for(int j = 0;j for(int j = 0;j printf("----------------------------------------------------\n"); printf("%d) 把当前系统资源分配给进程%05d\n",safeIndex,pid); printf(">>> 进程%05d目前还需要的资源为", pid); for(int j = 0;j printf("%-2d ", work[j]); } printf("\n"); } finishNum++; } ++pid; } if(showinfo){ if(tag){ printf("\n当前系统安全，安全序列为："); for(int i = 0;i printf("\n当前剩余资源无法使接下来的任一进程完成工作，所以当前系统不安全!\n"); } } return tag; } //初始化数据 void init(){ int i,j; //随机数种子 srand((unsigned long)time(0)); //写available数组 for(i = 0;i for(j = 0;j for(j = 0;j for(j = 0;j //随机数种子 srand((unsigned long)time(0)); int pid = 0; //随机一个进程，但是该进程不能是已经完成的进程 do{ pid = rand() % processNum; }while(isAllZero(pid)); //随机分配资源 for(int i = 0;i printf("%-2d ", request[j]); } printf("\n"); //分配资源 for(int j = 0;j printf("本次分配之后，已经能满足该进程的要求，同意分配！进程完成之后释放资源！\n"); for(int j = 0;j printf("本次分配之后，仍未能满足该进程的要求\n"); //检查分配之后是否安全 if(isSafe()){ //同意分配 printf("同意本次分配！\n"); }else{ printf("回滚本次分配！\n"); for(int j = 0;j printf("***************************\n"); printf("1. 查看系统当前资源使用情况\n"); printf("2. 分析当前系统安全性\n"); printf("3. 分配资源\n"); printf("4. 重新生成系统资源数据\n"); printf("0. 退出程序\n"); printf("***************************\n"); printf("请选择："); int a = -1; //当前选择 do{ scanf("%d",&a); if(a 4){ printf("请输入正确的数字！"); a = -1; } while(getchar() != '\n'){};//清空缓冲区 }while(a == -1); if(a == 0){ return 0; //退出程序 }else if(a == 1){ info(); }else if(a == 2){ info(); isSafe(); }else if(a == 3){ allot(); }else if(a == 4){ //初始化数据（要保证初始化之后系统是安全的！） do{ init(); }while(!isSafe(0)); printf("初始化数据完成！\n"); info(); } cout init(); }while(!isSafe(0)); //检查系统中是否已经有进程完成： for(int i = 0;i ++cnt; //释放资源 for(int j = 0;j //显示菜单 if(cnt >= processNum){ printf("当前所有进程已经完成，程序结束！\n"); break; } system("cls"); //清屏操作 } return 0; } 九、思考题： 1、 如何设计程序的输入模块才能满足实验要求，请举例说明；

答： 因为题目要求的是随机生成数据，所以随机生成数据时需要注意： ① 随机生成的allocation[i][j]一定要小于等于maxRequest[i][j]，因为一个进程占有的资源不能超过最大需求。 ② 因为初始化时一定要保证系统是安全状态的，所以随机生成的available要尽可能大一些，首先要保证剩余的资源至少能使一个进程完成。如果随机生成的available范围过小的话，初始化的时间会比较长。 ③ 在分配资源给进程时，一定要保证request[i]