银行家算法实现
一． 课程设计目的
1. 加深对死锁概念的理解。
2. 2. 能够利用银行家算法，有效避免死锁的发生，或检测死锁的存在 二． 课程设计摘要
三． 我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。三、开发环境
系统软件硬件环境
软件：Windows 7; VC++ 6.0 硬件：CPU 2.40GHz;2G内存 四、课程设计原理分析
在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。为保证系统中诸进程的正常运行，应事先采课程设计原理分析 在多道程序系统中，虽可借助于多个进程的并发执行，来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。为保证系统中诸进程的正常运行，应事先采取必要的措施，来预防死锁。最有代表性的避免死锁的方法，是Dijkstra的银行家算法。 死锁：
死锁的产生，必须同时满足四个条件，第一个为互斥条件，即一个资源每次只能由一个进程占用；第二个为请求和保持条件，指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但又对自己已获得的其他资源保持不放；第三个为非剥夺条件，即在出现死锁的系统中一定有不可剥夺使用的资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待它前一个进程所持有的资源。防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。 银行家算法原理：
银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。通过这个算法可以用来解决生活中的实际问题，如银行贷款等。 银行家算法，顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行家资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。把一个进程需要和已占有资源的情况记录在进程控制中，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共
要申请的资源量。显然，，每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁. 算法思想：
将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。 用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在 有限的时间内得到所需资源则称系统处于安全状态。 五. 算法实现
1、整个银行家算法的思路。 先对用户提出的请求进行合法性检查，再进行预分配，利用安全性检查算法进行安全性检查。 2、算法用到的主要数据结构和C语言说明。 （1）、可利用资源向量 INT AVAILABLE[M] M为资源的类型。 （2）、最大需求矩阵 INT MAX[N][M] N为进程的数量。 （3）、已分配矩阵 INT ALLOCATION[N][M] （4）、还需求矩阵 INT NEED[N][N] （5）、申请各类资源数量int Request[x]; // （6）、工作向量 int Work[x]; （7）、int Finish[y]; //表示系统是否有足够的资源分配给进程，0为否，非0为是 3、银行家算法 （主程序） （1）、系统初始化。输入进程数量，资源种类，各进程已分配、还需求各资源数量，各资 源可用数量等 （2）、输入用户的请求三元组（I，J，K），为进程I申请K个J类资源。 （3）、检查用户的请求是否小于还需求的数量，条件是 K<=NEED[I,J]。如果条件不符则 提示重新输入，即不允许索取大于需求量 （4）、检查用户的请求是否小于系统中的可利用资源数量，条件是K<=AVALIABLE[I,J]。 如果条件不符则申请失败，阻塞该进程，重新进行进程动态资源申请（使用goto语句） （5）、进行资源的预分配，语句如下： AVALIBLE[I][J]= AVALIBLE[I][J]-K； ALLOCATION[I][J]= ALLOCATION[I][J]+K； NEED[I][J]=NEED[I][J]-K； （6）、系统调用安全性检查算法（safe()函数）进行检查，如果检查通过，则不用回收，否 则进行回收，进程资源申请失败进入等待。 4、安全性检查算法（safe()子函数） （1）、设置两个临时变量。 FINISH[N]记录进程模拟执行的结束状态，初值为0，如果可以模拟执行结束，则可 设为1，也可设为其它非零值以表示执行的先后次序。 WORK[M]记录模拟执行中资源的回收情况，初值为AVAILABLE[M]的值。 （2）、在进程中查找符合以下条件的进程。 条件1：FINISH[I]=0 条件2：NEED[I][J]〈=WORK[J] （3）、如果查找成功则进行资
源的模拟回收，语句如下： WORK[J]=WORK[J]+ALLOCATION[I][J]； FINISH[I]=1 或查找到的顺序号 （4）、如果查找不成功，则检查所有进程的FINISH[]，如果有一个为0，则系统不为0， 返回不成功标志。否则返回成功标志。
操作系统(含课程设计)·平时作业2020春华南理工大学网络教育答案
