银行家算法课程设计报告.doc

1 操作系统课程设计报告操作系统课程设计报告 题目：银行家算法题目：银行家算法 院 （系）： 计算机科学与工程学院 专 业： 计算机科学与技术 班 级： 120605 学 生： 蔡学利 学 号： 120605101 指导教师： 姜红 2015 年 1 月 2 摘摘 要要 银行家算法是一个用来避免系统进入死锁状态的算法，用它可以判断系统 的安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源， 如果不是安全状态，则不能为申请资源的进程分配资源。 银行家算法执行过程中，首先判断申请资源的进程所申请的资源数目是否 合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列， 如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继 续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会 进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申 请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻 塞状态，处理其他申请资源的进程。 论文首先对算法的设计从总体上进行了分析，然后分析各个细节，再对算 法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并 进行调试和测试，最后进行组装测试及系统测试，使其成为一个可以用来判断 系统安全状态的程序。 关键词：可用资源关键词：可用资源 最大需求矩阵最大需求矩阵 分配矩阵分配矩阵 需求矩阵需求矩阵 请求向量请求向量 试分配试分配 安全性算法安全性算法 安全序列安全序列 3 目目 录录 摘摘 要要2 目目 录录3 1 绪论绪论5 1.1 课题背景5 1.2 课题意义5 1.3 运行环境5 2 需求分析需求分析6 2.1 问题描述6 2.2 基本要求6 2.3 概要分析6 3 算法思想算法思想8 3.1 安全性算法的算法思想.8 3.1.1 设置两个向量：8 3.1.2 安全性检测8 3.2 银行家算法的算法思想.9 3.2.1 银行家算法的思路.9 3.2.2 银行家算法9 3.2.3 安全性检查算法9 4 详细设计详细设计.11 4 4.1 银行家算法中用到的主要数据结构设计11 4.2 算法整体设计与调用.11 4.3 模块设计与时间复杂度分析.13 4.3.1 int check_distribution(int* p,int k)函数13 4.3.2 int check_safe()银行家算法.13 4.3.2 void print()输出函数.13 4.4 程序流程图.13 4.5.1 主函数 void main（）函数流程图14 4.5.2 判断试分配函数 int check_distribution(int* p,int k)流程图14 4.5.3 银行家算法 int check_safe()流程图.15 4.5.4 输出函数 void print() 流程图15 5 程序调试、分析与修改程序调试、分析与修改16 5.1 分模块调试与分析17 5.1.1 进程信息的输入与输出调试.17 5.1.2 进程请求资源输入出错提示信息处理.18 5.1.3 判断试分配函数 int check_distribution(int* p,int k).18 5.1.4 求安全序列函数 int check_safe()19 6 结论结论20 7 小结小结21 参考文献参考文献22 附录（源代码）23 5 1 绪论绪论 1.11.1 课题背景课题背景 在预防死锁的各种算法中，总的来说，都是施加了较强的限制条件，从而 使实现简单，但却严重地损害了系统的性能。在避免死锁的算法中，施加的条 件较较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安 全状态和不安全状态，只要能使系统处于安全状态，便可避免死锁的发生。 最具有代表性的避免死锁的算法是 Dijkstra 的银行家算法。这是因为该算 法能用于银行系统现金贷款的发放而得名，在这一次的课程设计中就要对银行 家算法从分析到实现，整体做一个详细的描述。 1.21.2 课题意义课题意义 （1）从课程设计上讲，提高自己的分析问题，解决问题和动手能力； （2）从银行家算法上本身讲，通过算法可以判断系统的安全性，对申请资 源的进程进行限制，从而避免系统进入死锁状态。 1.31.3 运行环境运行环境 TurboTurbo C;C; VisualVisual C+C+ 6.06.0 6 2 2 需求分析需求分析 2.12.1 问题描述问题描述 当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系 统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对 当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一 个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安 全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分 配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以 后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个 过程，可以有效避免系统进入死锁状态。 2.22.2 基本要求基本要求 （1）对各个进程的进程名，最大需求资源，已分配资源，系统可用资源等进 行有序的输入。 （2）对申请资源的进程要有合法性判断（如进程名，申请资源数等） 。 （3）若有进程申请资源，首先要对它申请的资源数进行判断。 （4）在上面判断合法的前提下进行试分配，利用银行家算法求出安全序列, 如果可以求出安全序列，则为该进程分配资源，否则使它进入阻塞状态。 2.3 概要分析概要分析 7 在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之 前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将 资源分配给该进程否则进程等待。 所谓安全状态是指系统能按某种顺序如（称 为安全序列） ，就这样来为每个进程分配资源，直至最大需 求。使每个进程都可以顺序地执行完毕。若系统不存在这样一个安全序列，那 么系统此时会进入不安全状态。 虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态 后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免 进入死锁状态。因此，避免死锁的实质在于，如何使系统不进入不安全状态， 银行家算法就是用来判断某种情况会不会进入不安全状态。 8 3 算法思想算法思想 3.1 安全性算法的算法思想安全性算法的算法思想 思想:系统在进行资源分配之前，应先计算此次资源分配后状态的安全性。 若此次分配后的状态是安全状态，则将资源分配给进程；否则，令进程等待。 3.1.13.1.1 设置两个向量设置两个向量 （1）工作向量Workm: 它表示系统可提供给进程继续运行所需的各类资源 数目， Work初=Available; （2） Finishn: 它表示系统是否有足够的资源分配给进程，使之运行完 成。 false表示未完成， true表示完成。 3.1.2 安全性检测安全性检测 WorkAvailable Finish 根据根据Need赋赋 值值 寻找进程寻找进程i，满足，满足 Finish i false 且且Need i #define N 5 /进程个数 #define M 3 /资源种类数 void print(); int check_safe(); int check_distribution(int* p,int k); char processnemaN; /进程名 int RequestM; /请求向量 int FinishN;/标记某一个进程是否可以执行 int WorkNM; /初始为 Available,随寻找安全序列而变化，防 止安全序列未找到而丢了初始状态的值 int AvailableM; /资源清单系统中现有各资源空闲个数 int Work_AllocationNM; int MaxNM; /最大需求矩阵每个进程对各类资源的最大需求数 int AllocationNM;/分配矩阵系统给每个进程已分配的各类资源数 int NeedNM; /需求矩阵每个进程还需要每种资源的个数 int sequenceN=0;/存放安全序列号 void main() int i=0,j=0,k=0;/记录申请资源的进程的序列号 int flag=0; /标记输入的进程名是否存在 int safe=0; /标志系统是否出于安全状态,0 表示不安全，1 表示安全 int distribution=0; /标志是否可以进行试分配 0 表示可以，1 表示不 可以 char flag1; /标记是否有进程申请资源 /NeedNM =MaxNM-AllocationNM; char name; /要请求资源的进程名 25 printf(“银行家算法n“); printf(“ 请分别初始化各矩阵信息 n“); printf(“*请输入各进程的进程名n“); /进程名连续输入 for(i=0; iN; i+) scanf(“%c“, printf(“请输入现有各资源空闲个数n“); for(i=0; iM; i+) scanf(“%d“, printf(“请分别输入每个进程对各类资源的最大需求数n“); for(i=0; iN; i+) for(j=0; jM; j+) scanf(“%d“, printf(“请分别输入系统给每个进程已分配的各类资源数n“); for(i=0; iN; i+) for(j=0; jM; j+) scanf(“%d“, /printf(“请分别输入每个进程还需要每种资源的个数n“); for(i=0; iN; i+) for(j=0; jM; j+) 26 Needij=Maxij-Allocationij; printf(“信息输入完毕n“); for(i=0; iN; i+) sequencei=i; print(); safe=check_safe(); /检查初始状态是否安全 if(0 = safe) printf(“系统现处于不安状态，不能为进程分配资源，进入死锁状态。 。 。n“); exit(0); else if(1 = safe) printf(“系统处于安全状态，可以为进程分配资源。n“); while(1) safe=0; getchar(); printf(“是否有进程请求系统资源.? (Y/N) n“); flag1=getchar(); /scanf(“%c“, if(Y = flag1 | y = flag1) printf(“请输入进程名:“); 27 getchar(); while(1) /name=; scanf(“%c“, for(i=0; iN; i+) /检查进程名输入是否正确 if(name = processnemai ) flag=1; /输入的进程名存在 k=i; break;/找到申请资源的进程序列号跳出 getchar();/将在此之前的一个回车接收了，不然会影响输入 if( flag != 1 )/进程名输入不合法 printf(“你输入的进程不存在，请重新输入:“); continue; else break;/进程名输入合法，则执行下面操作 else if(N = flag1 | n = flag1) printf(“进程执行完毕，退出系统。n“); break; else if(N != flag1 continue; printf(“请输入该进程请求各类资源的数量n“); for(i=0; iM; i+) scanf(“%d“, distribution=check_distribution(Request,k); /检查是否 可以试分配 if(1 = distribution) /*检查 safe=check_safe(); /可以试分配，则求安全序列 if(1 = safe) /试分配成功 printf(“试分配成功，可以为该进程分配资源。n“); /distribution /是否给申请资源的进程分配资源 for(i=0; iM; i+) Allocationki=Allocationki+Requesti; / 为进程分配资源后修改该进程的有关资源数 Needki=Needki-Requesti; printf(“分配后各资源数量如下:n“); print(); printf(“分配成功!n“); printf(“系统剩余资源数各为: “); for(i=0; iM; i+) printf(“%d “,Availablei); printf(“n“); 29 continue; else /试分配失败 printf(“试分配失败，有可能进入死锁状态，请等待。 。 。n“); /未求出安全序列 continue; else /试分配失败 printf(“该进程申请的资源太多，无法分配，请等待。 。 。n“); continue; void print() int i,j; printf(“ 资源 Work NeedtAllocationtWork+Allocationt Finishnn“); printf(“ 进程名 A B C A B C t A B C t A B Cn“); printf(“ n“); for(i=0; iN; i+) printf(“ %c “,processnemasequencei); for(j=0; jM; j+) printf(“%d “,Worksequenceij); 30 printf(“ “); for(j=0; jM; j+) printf(“%d “,Needsequenceij); printf(“ “); for(j=0; jM; j+) printf(“%d “,Allocationsequenceij); printf(“ “); for(j=0; jM; j+) printf(“%d “,Work_Allocationsequenceij); printf(“ “); printf(“%d“,Finishi); printf(“nn“); int check_distribution(int* p,int k) int i=0; int safe1=0,safe2=0; for(i=0; iM; i+) if(pi = Needki) safe1=safe1+1; if(pi = Availablei) safe2=safe2+1; 31 if(M = safe1 else return 0; int check_safe() /检查是否安全，求安全序列 int i=0,j=0,k=0,m=0; int finish=0; for(i=0;