搜索
3《操作系统原理》课程设计报告姓名：班级：BX1203学号：指导老师：范光宇2014年12月3目录1课程设计的概要...........................................................................................................................31.1前言....................................................................................................................................31.2目的....................................................................................................................................31.3要求....................................................................................................................................31.4研究意义............................................................................................................................42设计思想和需求分析...................................................................................................................52.1设计思想............................................................................................................................52.2需求分析............................................................................................................................52.3具体过程............................................................................................................................53数据结构的说明...........................................................................................................................23.1数据结构...........................................................................................................................23.2系统结构............................................................................................................................23.2.1系统主要过程流程图............................................................................................23.2.2初始化流程图........................................................................................................33.3.3安全性算法流程图...............................................................................................34结果分析与思考题.......................................................................................................................54.1结果分析............................................................................................................................54.2思考题...............................................................................................................................55小结..............................................................................................................................................7参考文献...........................................................................................................................................831课程设计的概要1.1前言Dijkstra(1965)提出了一种能够避免死锁的调度算法，称为银行家算法。它的模型基于一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，每个客户都有一个贷款额度，银行家知道不可能所有客户同时都需要最大贷款额，所以他只保留一定单位的资金来为客户服务，而不是满足所有客户贷款需求的最大单位。这里将客户比作进程，贷款比作设备，银行家比作系统。客户们各自做自己的生意，在某些时刻需要贷款。在某一时刻，客户已获得的贷款和可用的最大数额贷款称为与资源分配相关的系统状态。一个状态被称为是安全的，其条件是存在一个状态序列能够使所有的客户均得到其所需的贷款。如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。不安全状态并不一定导致死锁，因为客户未必需要其最大贷款额度，但银行家不敢抱这种侥幸心理。银行家算法就是对每一个请求进行检查，检查如果满足它是否会导致不安全状态。若是，则不满足该请求；否则便满足。检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户。如果可以，则这笔投资认为是能够收回的，然后接着检查下一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。1.2目的（1）进一步理解利用银行家算法避免死锁的问题。（2）在了解和掌握银行家算法。（3）理解和掌握安全序列、安全性算法1.3要求编程序模拟银行家算法。要求用用c/c语言在Linux操作系统环境下编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。编写安全性算法；编写银行家算法，并编制银行家算法通用程序，将调试结果显示在计算机屏幕上，再检测和笔算的一致性。31.4研究意义在多道程序系统中，多个进程的并发执行来改善系统的资源利用率，提高系统的吞吐量，但可能发生一种危险——死锁。所谓死锁(Deadlock)，是指多个进程在运行过程中因争夺资源而造成的一种僵局（DeadlyEmbrace），当进程处于这种状态时，若无外力作用，他们都无法在向前推进。32设计思想和需求分析2.1设计思想将一定数量的资金供多个用户周转使用，当用户对资金的最大申请量不超过现存资金时可接纳一个新客户，客户可以分期借款，但借款总数不能超过最大的申请量。银行家对客户的借款可以推迟支付，但是能够使客户在有限的时间内得到借款，客户得到所有的借款后能在有限的时间内归还。用银行家算法分配资源时，测试进程对资源的最大需求量，若现存资源能满足最大需求就满足当前进程的申请，否则推迟分配，这样能够保证至少有一个进程可以得到所需的全部资源而执行到结束，然后归还资源，若OS能保证所有进程在有限的时间内得到所需资源则称系统处于安全状态。2.2需求分析根据上述的设计思想可以建立不同的数据结构分别存放各个进程的最大需求数、已经分配的资源数和目前系统可用的资源数。通过编写安全性检验的算法，来判断系统当前的状态是否安全，是否可以正式分配资源。利用银行家算法模拟计算机系统分配资源的过程。以课本例题中数据为例，模拟资源分配过程。系统中资源种类，各类资源数目，进程申请资源数目可任意输入，模拟资源分配过程。2.3具体过程（1）可以输入某系统的资源以及T0时刻进程对资源的占用及需求情况的表项，以及T0时刻系统的可利用资源数。（2）对T0时刻的进行安全性检测，即检测在T0时刻该状态是否安全。（3）进程申请资源，用银行家算法对其进行检测，分为以下三种情况：A.所申请的资源大于其所需资源，提示分配不合理不予分配并返回。B.所申请的资源未大于其所需资源，但大于系统此时的可利用资源，提示分配不合理不予分配并返回。C.所申请的资源未大于其所需资源，亦未大于系统此时的可利用资源，预分配并进行安全性检查：a.预分配后系统是安全的，将该进程所申请的资源予以实际分配并打印后返回。b.与分配后系统进入不安全状态，提示系统不安全并返回。（4）对输入进行检查，即若输入不符合条件，应当报错并返回重新输入。23数据结构的说明3.1数据结构①可利用资源向量Available是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果AvailablejK，则表示系统中现有Rj类资源K个。②最大需求矩阵Max这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果MaxijK，则表示进程i需要Rj类资源的最大数目为K。③分配矩阵Allocation这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果AllocationijK，则表示进程i当前已分得Rj类资源的数目为K。④需求矩阵Need。这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果NeedijK，则表示进程i还需要Rj类资源K个，才可以完成其任务。3.2系统结构3.2.1系统主要过程流程图图3-1系统主要过程流程图在判断初始时刻系统出于安全的情况下，当有进程提出资源申请时，调用安3全性算法检测是否可以分配资源。检测为安全，分配；为不安全，让用户选择是否继续。并显示当前的资源分配情况。重复上述过程。3.2.2初始化流程图图3-2初始化流程图系统在已知目前的进程数和各个进程需要的资源数、已分配的资源数和系统当前可用的资源数后，进行T0时刻，即初始时刻系统是否安全的判断，若安全则进行进程资源的申请与分配；否则退出系统。3.3.3安全性算法流程图所谓安全状态，指系统中存在一个包括所有进程的进程序列（P1，P2…Pn），按照该序