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

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

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

3、成为一个可以用来判断 系统安全状态的程序。 关键词：可用资源关键词：可用资源 最大需求矩阵最大需求矩阵 分配矩阵分配矩阵 需求矩阵需求矩阵 请求向量请求向量 试分配试分配 安全性算法安全性算法 安全序列安全序列 目目 录录 银行家算法设计与实现.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 3.2.1 银行

4、家算法的思路.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_distribution(int* p,int k)

5、流程图.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 6 结论.15 7 小结.16 参考文献.17 附录（源代码）.18 1 绪论绪论 1.11.1 课题背景课题背景 在预

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

7、断系统的安全性，对申请资 源的进程进行限制，从而避免系统进入死锁状态。 1.31.3 运行环境运行环境 turboturbo c;c; visualvisual c+c+ 6.06.0 2 需求分析需求分析 2.12.1 问题描述问题描述 当系统在进行资源管理时，如果对进城申请的资源分配不当，可能会使系 统进入死锁状态，因而后面到来的进程也无法顺利执行。银行家算法中，要对 当前申请资源的进程申请资源的数目进行判断，如果可以试分配，则试求出一 个安全序列，如果可以求出，则说明给这个进程分配资源后系统不会进入不安 全状态，将该进程申请的资源分配给他，若求不出安全序列，则说明将资源分 配给该进程后系

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

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

10、3 算法思想算法思想 3.1 安全性算法的算法思想安全性算法的算法思想 思想:系统在进行资源分配之前，应先计算此次资源分配后状态的安全性。 若此次分配后的状态是安全状态，则将资源分配给进程；否则，令进程等待。 3.1.13.1.1 设置两个向量设置两个向量 （1）工作向量workm: 它表示系统可提供给进程继续运行所需的各类资源 数目， work初=available; （2） finishn: 它表示系统是否有足够的资源分配给进程，使之运行完 成。 false表示未完成， true表示完成。 3.1.2 安全性检测安全性检测 available finish 根据根据need赋赋 值值 寻寻

11、找找进进程程i， ，满满足足 finish i false 且且need i=work 返回安全状返回安全状态态 y work=work+allocation i finish i true 找到找到 所有所有进进程的程的 finish i true？ 没找到没找到 n 返回不安全状返回不安全状态态 3.23.2 银行家算法的算法思想银行家算法的算法思想 3.2.13.2.1 银行家算法的思路银行家算法的思路 先对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，是 否不大于可利用的。若请求合法，则进行试分配。最后对试分配后的状态调用 安全性检查算法进行安全性检查。若安全，则分配，否则

12、，不分配，恢复原来 状态，拒绝申请。 3.2.23.2.2 银行家算法银行家算法 进程 i 发出申请资源请求： (1)调用 check_distribution(int* p,int k)检查申请量是否不大于需求量再 检查检查申请量是否小于系统中的可利用资源数量：若条件不符重新输入，不 允许申请大于需求量。 (2)若以上条件都满足，则系统试探着将资源分配给申请的进程，并修改下面 数据结构中的数值： availablei,j= availablei,j- request ij； allocationij= allocationij+ request ij； needij= needij- req

13、uest ij； (3)进行试分配，执行安全性检查，调用 check_safe()函数检查此次资源试分 配后系统是否处于安全状态。若安全，才正式将资源分配给进程；否则本次试 探分配作废，恢复原来的资源分配状态，让该进程等待。 (4)用 while 循环语句实现输入字符 y/n 判断是否继续进行资源申请。 3.2.33.2.3 安全性检查算法安全性检查算法 (1)设置向量： 工作向量 work，它表示系统可提供给进程继续运行所需的各类资源数目，在执 行安全性算法开始时，work= available。 finish，它表示系统是否有足够的资源分配给每个进程，使之运行完成。开 始时先做 finis

14、hi=0；当有足够的资源分配给进程时，再令 finishi=1。 (2)在进程中查找符合以下条件的进程： 条件 1：finishi=0； 条件 2：needij=workj 若找到，则执行步骤(3)否则，执行步骤(4) (3)当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故 应执行： workj= workj+ allocationij； finishi=1； goto step 2； (4)最后循环检查是否所有的 finishi=1 都满足，如果是，则返回 1 表示系统 处于安全状态，否则，返回 0 表示系统处于不安全状态。 4 详细设计详细设计 4.14.1银行家算法中用

15、到的主要数据结构设计银行家算法中用到的主要数据结构设计 (1）进程名向量 char processneman; /进程名 (2）可利用资源向量 int availablem; /资源清单系统中现有各资源 空闲个数。 (3）最大需求矩阵 int maxnm; /最大需求矩阵每个进程对各 资源的最大需求数分配矩阵 (4）已分配矩阵 int allocationnm;/分配矩阵系统给每个进程 已分配的各类资源数 (5）需求矩阵 int neednm; /需求矩阵每个进程还需要每 种资源的个数申请各类资源数量 (6）申请向量 int request m /进程申请资源的向量 (7）工作向量 int w

16、orknm; /初始第一个向量为 available,随寻找安全序列时为其余每个向量赋值，可 以防止安全序列未找到而丢了初始状态的值 (8）安全序列向量 int sequencen=0;/存放安全序列号 (9）标志向量 int finishn /求安全序列时记录每个进程是否可以 顺利执行 4.2 算法整体设计与调用算法整体设计与调用 主函数 void main()，首先输入每个进程信息，然后判断是否有进程申请 资源，若有，则调用 int check_distribution(int* p,int k)函数判断是否可以进行试 分配，如果满足试分配条件，调用 int check_safe()函数求

17、安全序列，如果可以 求出安全序列，则说明分配后系统不会进入不安全状态，正式将资源分配给申 请资源的进程，最后用 void print()函数输出分配资源后每个进程的信息。如果 求不出安全序列，说明分配后系统会处于不安全状态，则不能将资源分配给该 进程，让其等待，系统恢复原始状态。如果申请资源的数量不满足条件，则让 该进程等待。继续判断其他申请资源的进程。 （1）int check_distribution(int* p,int k)：这个函数用来判断是否可以 进行试分配，如果函数结果返回 1，说明可以进行试分配，如果行数返回 0，说 明申请资源的进程申请的资源数目不满足 request =ne

18、ed或 request =available条件，不能为该进程进行试分配。 （2）int check_safe()：这个函数用来求安全序列，首先初始化 work0i= availablei，然后循环找满足条件 finishi=0 im; i+)判断是否满足约束条件 pi = needki，时间复杂 度为 o(m)。 4.3.24.3.2 intint check_safe()check_safe()银行家算法银行家算法 (1) 用 for(i=0; im; i+)循环workki=availablei;/-requesti初始化 work 矩阵 (2) 用 for(m=0; mn; m+)循环

19、找出满足（0 = finishi in; i+)/检查是否所有进程都执行完了，如果所有进程都可执 行则 finish 值等于 1。 (4) 由上面执行可以得出 int check_safe()函数时间复杂度为 o(n)或 o(m)。 4.3.24.3.2 voidvoid print()print()输出函数输出函数 for(i=0; in; i+)for(j=0; jm; j+)循环输出每个进程的每一类资源信息， 时间复杂度为 o(n)或 o(m)。 4.44.4 程序流程图程序流程图 4.5.14.5.1 主函数主函数 voidvoid mainmain（）函数流程图（）函数流程图 （ 4

20、-4- 1 1） 4-1 4.5.2 判断试分配函数 int check_distribution(int* p,int k)流程图（4-2） 4-2 4.5.3 银行家算法银行家算法 int check_safe()流程图流程图 (4-3) 4-3 4.5.4 输出函数输出函数 void print() 流程图（流程图（4-4） 4-4 5 程序调试、分析与修改程序调试、分析与修改 5.15.1 分模块调试与分析分模块调试与分析 函数的书写分模块进行，每完成一个模块进行调试、测试直到该函数运行 无误。 5.1.1 进程信息的输入与输出调试进程信息的输入与输出调试 (1) 能正确无误的输入进程

21、名向量 processneman，输入系统现有各类资源数量 availablem向量，输入每个进程对各类资源的最大需求数 maxnm矩阵，输 入系统给每个进程已分配的各类资源数 allocationnm矩阵。输出程序过程如 下： (2) 在进程信息输入中没有出现多大问题，在进程信息输出时，按设计要求输 出的话应该是一个表格形式，在输出函数设计最初，由于有些部分分割或空格 没有填充好，导致输出表格比较乱，没有达到设计要求，经过修改后输出形式 才符合了设计要求，进程信息输入完成后，初始状态各进程信息输出如下： 5.1.25.1.2 进程请求资源输入出错提示信息处理进程请求资源输入出错提示信息处理

22、(1) 在系统询问是否有进程申请资源时，如果有输入信息出错，系统会给与出 错提示，如果输入信息正确则系统将继续执行下面操作，执行如下： 5.1.35.1.3 判断是否可以试分配函数判断是否可以试分配函数 intint check_distribution(int*check_distribution(int* p,intp,int k)k) (1) 在这个函数中主要是对申请资源的进程申请的资源数量是否满足约束条件 request =need或 request =available,如果不满足将打出提示信息， 如果满足，则返回 1 继续执行下面程序，执行结果如下： 5.1.45.1.4 求安全序

23、列函数求安全序列函数 intint check_safe()check_safe() (1) 如果申请资源的进程申请的资源数目满足试分配条件，则再用这个函数来 求试分配后的安全序列，如果可以求出安全序列，则说明这次分配不会使系统 进入不安全状态，正式将资源分配给该进程，修改系统资源信息。如果求不出 安全序列，说明这次分配后系统会进入不安全状态，不能给该进程分配资源， 系统恢复初始状态，打印出提示信息，执行结果如下： 6 结论结论 银行家算法是通过检查试分配，求安全序列，从而判断是否可以为申请资源 的进程分配资源，从而有效地避免系统进入死锁状态。 7 小结小结 虽然并非所有的不安全状态都会产生死

24、锁状态，但系统进入不安全状态时， 便可能进而进入死锁状态后，当系统在进行资源管理时，如果对进城申请的资 源分配不当，可能会使系统进入死锁状态，因而后面到来的进程也无法顺利执 行。银行家算法中，要对当前申请资源的进程申请资源的数目进行判断，如果 可以试分配，则试求出一个安全序列，如果可以求出，则说明给这个进程分配 资源后系统不会进入不安全状态，将该进程申请的资源分配给他，若求不出安 全序列，则说明将资源分配给该进程后系统会进入不安全状态，所以就使该进 程进入阻塞状态，等待以后可以分配资源时再执行该进程，然后系统继续服务 其它进程。通过这样一个过程，可以有效避免系统进入死锁状态。反之，只要 系统处

25、于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于； 如何使系统不进入不安全状态。 参考文献参考文献 1 数据结构实验指导书 网上资料 2 计算机操作系统 汤子瀛 哲凤屏 汤小丹，西安电子科技大学出 版社； 3 c 语言程序设计 谭浩强， 清华大学出版社； 附录（源代码）附录（源代码） #include #define n 5 /进程个数 #define m 3 /资源种类数 void print(); int check_safe(); int check_distribution(int* p,int k); char processneman; /进程名 int reques

26、tm; /请求向量 int finishn;/标记某一个进程是否可以执行 int worknm; /初始为 available,随寻找安全序列而变化，防 止安全序列未找到而丢了初始状态的值 int availablem; /资源清单系统中现有各资源空闲个数 int work_allocationnm; int maxnm; /最大需求矩阵每个进程对各类资源的最大需求数 int allocationnm;/分配矩阵系统给每个进程已分配的各类资源数 int neednm; /需求矩阵每个进程还需要每种资源的个数 int sequencen=0;/存放安全序列号 void main() int i=

27、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; /要请求资源的进程名 printf(银行家算法n); printf( 请分别初始化各矩阵信息 n); printf(*请输入各进程的进程名n); /进程名连续输入 for(i=0; in;

28、 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+) needij=maxij-alloca

29、tionij; 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 =

30、 flag1 | y = flag1) printf(请输入进程名:); 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;/进程名输入合法，则执行下面操作 els

31、e 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

32、); /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); continue; else /试分配失败 printf(试分配失败，有可能进入死锁状态，请等待

33、。 。 。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); printf( ); for(j=0; jm; j+) printf(%d ,needsequence