操作系统课程设计报告-银行家算法设计与实现.doc

《操作系统课程设计报告-银行家算法设计与实现.doc》由会员分享，可在线阅读，更多相关《操作系统课程设计报告-银行家算法设计与实现.doc（33页珍藏版）》请在三一文库上搜索。

1、操作系统课程设计报告操作系统课程设计报告 题目：银行家算法设计与实现题目：银行家算法设计与实现 院院 （系）：（系）： 计算机科学与工程学院计算机科学与工程学院 专专 业：业： 对日软件对日软件 班班 级：级： 080612 学学 生：生： 学学 号：号： 080608115 指导教师：指导教师： 2010 年 12 月 操作系统课程设计报告 1 银行家算法设计与实现银行家算法设计与实现 摘摘 要要 银行家算法是一个用来预防系统进入死锁状态的算法，用它可以判断系统 的安全性，如果系统当前处于安全状态，则可以为申请资源的进程分配资源， 如果不是安全状态，则不能为申请资源的进程分配资源。 银行家算

2、法执行过程中，首先判断申请资源的进程所申请的资源数目是否 合法，若是合法的，则可以为其进行试分配，再利用安全性算法求出安全序列， 如果存在安全序列，则说明可以给申请资源的进程分配资源，分配成功，继 续为其它进程服务。如果找不到安全序列，则说明为该进程分配资源后系统会 进入不安全状态，所以不能为该进程分配资源，使该进程进入阻塞状态。若申 请资源的进程申请的资源数目不合法，则不需要进行试分配，直接使其进入阻 塞状态，处理其他申请资源的进程。 论文首先对算法的设计从总体上进行了分析，然后分析各个细节，再对算 法分模块设计，并对各个模块的算法思想通过流程图表示，分块编写代码，并 进行调试和测试，最后进

3、行组装测试及系统测试，使其成为一个可以用来判断 系统安全状态的程序。 关键词：可用资源关键词：可用资源 最大需求矩阵最大需求矩阵 分配矩阵分配矩阵 需求矩阵需求矩阵 请求向量请求向量 试分配试分配 安全性算法安全性算法 安全序列安全序列 操作系统课程设计报告 2 目目 录录 银行家算法设计与实现1 摘 要1 目 录2 1 绪论5 1.1 课题背景5 1.2 课题意义5 1.3 运行环境5 2 需求分析1 2.1 问题描述1 2.2 基本要求1 2.3 概要分析2 3 算法思想3 3.1 安全性算法的算法思想.3 3.1.1 设置两个向量：3 3.1.2 安全性检测3 3.2 银行家算法的算法思

4、想.4 操作系统课程设计报告 3 3.2.1 银行家算法的思路.4 3.2.2 银行家算法4 3.2.3 安全性检查算法5 4 详细设计.6 4.1 银行家算法中用到的主要数据结构设计6 4.2 算法整体设计与调用.6 4.3 模块设计与时间复杂度分析.8 4.3.1 int check_distribution(int* p,int k)函数8 4.3.2 int check_safe()银行家算法.8 4.3.2 void print()输出函数.8 4.4 程序流程图.8 4.5.1 主函数 void main（）函数流程图9 4.5.2 判断试分配函数 int check_distri

5、bution(int* p,int k)流程图9 4.5.3 银行家算法 int check_safe()流程图.10 4.5.4 输出函数 void print() 流程图11 5 程序调试、分析与修改12 5.1 分模块调试与分析12 5.1.1 进程信息的输入与输出调试.12 5.1.2 进程请求资源输入出错提示信息处理.13 5.1.3 判断试分配函数 int check_distribution(int* p,int k).13 5.1.4 求安全序列函数 int check_safe()14 操作系统课程设计报告 4 6 结论15 7 小结16 参考文献17 附录（源代码）18 绪

6、论 5 1 绪论绪论 1.11.1 课题背景课题背景 在预防死锁的各种算法中，总的来说，都是施加了较强的限制条件，从而 使实现简单，但却严重地损害了系统的性能。在避免死锁的算法中，施加的条 件较较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安 全状态和不安全状态，只要能使系统处于安全状态，便可避免死锁的发生。 最具有代表性的避免死锁的算法是 Dijkstra 的银行家算法。这是因为该算 法能用于银行系统现金贷款的发放而得名，在这一次的课程设计中就要对银行 家算法从分析到实现，整体做一个详细的描述。 1.21.2 课题意义课题意义 （1）从课程设计上讲，提高自己的分析问题，解决问

7、题和动手能力； （2）从银行家算法上本身讲，通过算法可以判断系统的安全性，对申请资 源的进程进行限制，从而避免系统进入死锁状态。 1.31.3 运行环境运行环境 TurboTurbo C;C; VisualVisual C+C+ 6.06.0 2 需求分析 1 2 需求分析需求分析 2.12.1 问题描述问题描述 当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系 统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对 当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一 个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安 全状态，

8、将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分 配给该进程后系统会进入不安全状态，所以就使该进程进入阻塞状态，等待以 后可以分配资源时再执行该进程，然后系统继续服务其它进程。通过这样一个 过程，可以有效避免系统进入死锁状态。 2.22.2 基本要求基本要求 （1）对各个进程的进程名，最大需求资源，已分配资源，系统可用资源等进 行有序的输入。 （2）对申请资源的进程要有合法性判断（如进程名，申请资源数等） 。 （3）若有进程申请资源，首先要对它申请的资源数进行判断。 （4）在上面判断合法的前提下进行试分配，利用银行家算法求出安全序列。 如果可以求出安全序列，则为该进程分配资源，否则

9、使它进入阻塞状态。 2 需求分析 2 2.32.3 概要分析概要分析 在避免死锁的算法中，允许进程动态地申请资源，系统在进行资源分配之 前，先计算资源分配的安全性。若此次分配不会使系统进入不安全状态，便将 资源分配给该进程否则进程等待。 所谓安全状态是指系统能按某种顺序如（称 为安全序列） ，就这样来为每个进程分配资源，直至最大 需求。使每个进程都可以顺序地执行完毕。若系统不存在这样一个安全序列， 那么系统此时会进入不安全状态。 虽然并非所有的不安全状态都会产生死锁状态，但当系统进入不安全状态 后，便可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免 进入死锁状态。因此，避免死锁的

10、实质在于，如何使系统不进入不安全状态， 银行家算法就是用来判断某种情况会不会进入不安全状态。 操作系统课程设计报告 3 3 算法思想算法思想 3.1 安全性算法的算法思想安全性算法的算法思想 思想:系统在进行资源分配之前，应先计算此次资源分配后状态的安全性。 若此次分配后的状态是安全状态，则将资源分配给进程；否则，令进程等待。 3.1.13.1.1 设置两个向量设置两个向量 （1）工作向量Workm: 它表示系统可提供给进程继续运行所需的各类资源 数目， Work初=Available; （2） Finishn: 它表示系统是否有足够的资源分配给进程，使之运行完 成。 false表示未完成，

11、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; /初始为 Av

12、ailable,随寻找安全序列而变化，防 止安全序列未找到而丢了初始状态的值 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 s

13、afe=0; /标志系统是否出于安全状态,0 表示不安全，1 表示安全 int distribution=0; /标志是否可以进行试分配 0 表示可以，1 表示不 可以 char flag1; /标记是否有进程申请资源 /NeedNM =MaxNM-AllocationNM; char name; /要请求资源的进程名 printf(“银行家算法n“); printf(“ 请分别初始化各矩阵信息 n“); printf(“*请输入各进程的进程名n“); /进程名连续输入 附录（源代码） 19 for(i=0; iN; i+) scanf(“%c“, printf(“请输入现有各资源空闲个数n“

14、); 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+) Needij=Maxij-Allocationij; 附录（源代码） 20 prin

15、tf(“信息输入完毕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 = f

16、lag1 | y = flag1) printf(“请输入进程名:“); getchar(); while(1) 附录（源代码） 21 /name=; scanf(“%c“, for(i=0; iN; i+) /检查进程名输入是否正确 if(name = processnemai ) flag=1; /输入的进程名存在 k=i; break;/找到申请资源的进程序列号跳出 getchar();/将在此之前的一个回车接收了，不然会影响输入 if( flag != 1 )/进程名输入不合法 printf(“你输入的进程不存在，请重新输入:“); continue; else break;/进程名输

17、入合法，则执行下面操作 else if(N = flag1 | n = flag1) printf(“进程执行完毕，退出系统。n“); break; else if(N != flag1 continue; 附录（源代码） 22 printf(“请输入该进程请求各类资源的数量n“); for(i=0; iM; i+) scanf(“%d“, distribution=check_distribution(Request,k); /检查是否 可以试分配 if(1 = distribution) /*检查 safe=check_safe(); /可以试分配，则求安全序列 if(1 = safe)

18、/试分配成功 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“); cont

19、inue; 附录（源代码） 23 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;

20、i+) printf(“ %c “,processnemasequencei); for(j=0; jM; j+) printf(“%d “,Worksequenceij); printf(“ “); for(j=0; jM; j+) 附录（源代码） 24 printf(“%d “,Needsequenceij); printf(“ “); for(j=0; jM; j+) printf(“%d “,Allocationsequenceij); printf(“ “); for(j=0; jM; j+) printf(“%d “,Work_Allocationsequenceij); prin

21、tf(“ “); 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; 附录（源代码） 25 if(M = safe1 else return 0; int check_safe() /检查是否安全，求安全序列 int i=0,j=0,k=0,m=0; int finish=0;

22、for(i=0; iM; i+) Workki=Availablei;/-Requesti;/初始化 WOrk矩阵 for(m=0; mN; m+)/N 个进程最多找 N 趟 if(1 != finish) finish=1; for(i=0; iN; i+) /找 Need 小于 Work 的进程 if(0 = Finishi /找到一个满足条件的进程，记录其序号 k+; Finishi=1; /执行该进程 for(j=0; jM; j+) Workkj=Workk-1j+Allocationij; /更 附录（源代码） 26 新 WOrk 值 for(i=0; iN; i+)/检查是否所有

23、进程都执行完了 finish=finish*Finishi; if(1 = finish) break; else continue; /else / / break; / for(i=0; iN; i+) for(j=0; jM; j+) Work_Allocationij=Workij+Allocationij; for(i=0; iM; i+) 附录（源代码） 27 Availablei=Availablei-Requesti; return finish; /* 输入进程信息： 请分别输入每个进程对各类资源的最大需求数 7 5 3 3 2 2 9 0 2 2 2 2 4 3 3 请分别输入系统给每个进程已分配的各类资源数 0 1 0 2 0 0 3 0 2 2 1 1 0 0 2 请分别输入每个进程还需要每种资源的个数 7 4 3 1 2 2 6 0 0 0 1 1 4 3 1 信息输入完毕 */