操作系统课程设计-银行家算法.docx

操作系统课程设计银行家算法操作系统课程设计题目名称： 银行家算法 姓 名 学 号 专 业 班 级 指导教师 编写日期 目录第一章 问题描述31.1课设题目重述31.2问题分析31.3实验环境3第二章 系统设计43.1主要数据结构43.2银行家算法43.3安全性检查算法63.4银行家算法安全性序列分析之例7第三章 源代码清单103.1函数清单103.2各函数的调用关系图12第四章 运行结果测试与分析134.1程序的正常输出结果134.2程序的差错控制15第五章 结论与心得18参考文献18第一章 问题描述1.1 课设题目重述设计目的：了解多道程序系统中，多个进程并发执行的资源分配。设计要求：管理员可以把一定数量的作业供多个用户周转使用，为保证作业的安全，管理员规定：当一个用户对作业的最大需求量不超过管理员现有的资金就要接纳该用户；用户可以分期贷款，但贷款的总数不能超过最大需求量；当管理员现有的作业不能满足用户的所需数时，对用户的请求可以推迟支付，但总能使用户在有限的时间里得到请求。当用户得到所需的全部作业后，一定能在有限的时间里归还所有的作业。1.2 问题分析银行家算法是最具有代表性的避免死锁的算法。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。在死锁的避免中，银行家算法把系统状态分为安全状态和不安全状态，只要能使系统始终处于安全状态，便可以避免发生死锁。所谓安全状态，是指系统能按某种顺序为每个进程分配所需资源，直到最大需求，使每一个进程都可以顺利完成，即可找到一个安全资源分配序列。所以我们需要解决问题有：1) 熟悉银行家算法的工作原理，明白如何判断系统处于安全状态，避免死锁。2) 在Windows操作系统上，如何利用Win32 API编写多线程应用程序实现银行家算法。3) 创建n个线程来申请或释放资源，如何保证系统安全，批准资源申请。4) 通过Win32 API提供的信号量机制，实现共享数据的并发访问。1.3 实验环境操作系统：windows 8.1实验语言：c+第二章 系统设计3.1 主要数据结构1) 可利用资源向量Available。如果Availablej=K，则表示系统中现有Rj类资源K个。2) 最大需求矩阵Max。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。3) 分配矩阵Allocation。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。4) 需求矩阵Need。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Needi,j=Maxi,j-Allocationi,j。3.2 银行家算法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。设进程cusneed提出请求REQUEST i，如果REQUEST cusneedi，表示进程Pi需要K个Rj类型的资源。则银行家算法按如下规则进行判断。1) 如果REQUEST cusneedi= NEEDcusneedi，则转向步骤(2)；否则，出错，为它所需要的资源数已超过它所宣布的最大值。2) 如果REQUEST cusneedi= AVAILABLEcusneedi，则转向步骤(3)；否则，出错，因为它所需要的资源数已超过它所宣布的最大值。3) 系统试探分配资源，修改相关数据：AVAILABLEi-=REQUESTcusneedi;ALLOCATIONcusneedi+=REQUESTcusneedi;NEEDcusneedi-=REQUESTcusneedi;4) 系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。5) 对于某一进程i，若对所有的j，有NEEDij=0，则表此进程资源分配完毕，应将占用资源释放。根据以上步骤，所以银行家算法流程图如下所示调用bank()函数 输入欲申请的资源的进程号与资源量输入是否合法？REQUEST cusneedi= NEEDcusneedi？REQUEST cusneedi= VAILABLEcusneedi？预分配安全性检查NEEDij=0?继续分配 / 退出释放资源NYYNNNYY 图1 银行家算法流程图3.3 安全性检查算法1) 设置了两个变量工作向量Work，表示系统可提供给进程继续运行所需的各类资源数目。开始时，Work:=Available。Finish，表示系统是否有足够的资源分配给进程，使之运行完成。开始时令Finishi：=false；当有足够的资源分配给进程时，再令Finishi：=true。2) 从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;go to step 2;4) 如果所有进程的Finishi=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。根据以上步骤，所以安全性检查算法流程图如下所示:调用safe()函数work=availablefinish=falseneed=workfinish=false ?work=work+allocationfinish=true所有进程的finish=true?输出安全序列，并打印出当前资源分配情况输出提示：系统不安全调用结束NYNY图2 安全性检查算法流程图3.4 银行家算法安全性序列分析假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如表1 所示：表1 T0时刻的资源分配表资源情况进程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 11) T0时刻的安全性： 表2 T0时刻的安全序列资源情况进程WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP13 3 21 2 22 0 05 3 2TRUEP35 3 20 1 12 1 17 4 3TRUEP47 4 34 3 10 0 27 4 5TRUEP27 4 56 0 03 0 210 4 7TRUEP010 4 77 4 30 1 010 5 7TRUE2) P1请求资源：P1发出请求向量Request1（1,0,2），系统按银行家算法进行检查： Request1（1, 0, 2）Need1（1, 2, 2） Request1（1, 0, 2）Available1（3, 3, 2） 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如表2所示：表3 系统先假定可为P1分配资源时刻的资源分配表资源情况进程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 32 3 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1 再利用安全性算法检查此时系统是否安全。表4 P1申请资源时的安全性检查资源情况进程WorkNeedAllocationWork+AllocationFinishA B CA B CA B CA B CP12 3 00 2 03 0 25 3 2TRUEP35 3 20 1 12 1 17 4 3TRUEP47 4 34 3 10 0 27 4 5TRUEP27 4 56 0 03 0 210 4 7TRUEP010 4 77 4 30 1 010 5 7TRUE3) P4请求资源：P4发出请求向量Request4（3，3，0），系统按银行家算法进行检查： Request4（3, 3, 0）Need4（4, 3, 1）; Request4（3, 3, 0） 3-0-2-4。进程1进行资源请求分配，请求资源数1,0,2。4) 第一次分配结果成功，存在一个安全序列：1-3-0-2-4。因为这是进程1所需资源数不为0，即NEED1!=0，所以系统不释放进程1的资源。 第二次分配，4号进程请求系统资源数1 ,2, 0。预分配后，系统进行安全性检测时，不存在一个安全序列，所以请求被拒绝。5) 进程1再次请求资源0,2,0。存在一个安全序列1-3-0-2-4。这时进程1的所需要的资源总数为0，即NEED1=0，所以系统释放进程1的资源。6) 按照一个安全序列，使所有进程都获得资源并释放资源。4.2 程序的差错控制1) 对进入银行家算法进行输入控制，输入1,0以外的字符，系统提示为非法输入，用户重新输入。2) 进程最多所需的资源数不能为负，下图为系统提示哪个进程的第几个资源输入错误。3) 进程已分配的资源数不能为负，同时已分配的资源数不能大于进程最多所需的资源数。下图为系统提示哪个进程的第几个资源输入错误。4) 输入的资源请求不能超过系统所有资源数，以及进程所需资源数。 第五章 结论与心得本次设计中首先要解决的问题是对所做题目的理解。简单的文字描述总是生涩难懂，像银行家算法这一问题，联系实际生活中银行贷款这一现象，再来看问题时，一切开始显得清晰，再根据书上对这个问题的描述，便可以把自己究竟该作何工作搞清楚。明白了需求，下一个难点是如何通过软件实现。因为这次是一个人一个题目，所以整个课程设计是自己独立完成的。本次课程设计对银行家算法的实现不同于以往简单的模拟，需要调用Win32的API来创建线程，以及调用Win32 API提供的信号量机制，实现共享数据的并发访问。这些我以前都没有尝试过，所以一开始不知道怎么下手，这也是本次课程设计中我遇到的最大的问题。所以在正式编程前我先着重了解了一下这些API的使用，编一些程序去实验这些API的功能作用，再进行银行家算法的编程。了解了这些API同时也帮助自己对信号量，线程有了更深的认识。除此之外，在程序中，我们也得强调一下对输入合法性的判断，比如，我们输入的的预申请资源的进程号没有在系统已存在的进程中，或者进程资源数不能为负数等等，我们需要对这些情况进行判断，让程序报错返回重新输入而不是因错误而中断。通过本次课程设计，我对软件的开发的过程有了较为深入的了解，虽然只是对