计算机操作系统-银行家算法

操作系统课程设计题目：银行家算法的设计与实现系别：计算机信息与技术系专业：计算机科学与技术班级：B130601姓名：伏海龙学号：B13060105指导教师：魏少华×××2016年01月摘要此次课程设计的主要内容是模拟实现资源分配。同时要求编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，并用适当的算法，有效的防止和避免死锁的发生。银行家算法是一个避免死锁的一种重要方法，通过高级语言编写和调试一个简单的银行家算法程序。加深了解有关资源申请、避免死锁等概念，并体会了解死锁和避免死锁的具体实施方法。死锁的产生，必须同时满足四个条件，即一个资源每次只能由一个进程占用；第二个为等待条件，即一个进程请求资源不能满足时，他必须等待，但他仍继续保持已得到的所有其他资源；第四个为循环等待条件，系统中存在若干个循环等待的进程，即其中每一个进程分别等待他前一个进程所持有的资源。当不满足以上条件时就能防止系统的死锁，让系统流畅运行。通过该算法可以解决生活中的实际问题，如银行贷款等。通过对该算法的设计，让学生能够对书本的知识有更深刻的理解，在操作和其他方面有大幅度的提高。

2.2死锁的结论产生死锁的原因是：竞争资源和进程推进顺序不当处理死锁的基本方法是：预防死锁，避免死锁，检测死锁，解除死锁。2.3资源分类1.可剥夺性资源，某些进程在获得此类资源后，该资源可以被其他进程或系统比多。CPU和每寸均属于可剥夺性资源。2.不可剥夺性资源，当系统把类资源分配给进程后，不能强行收回，只能在进程用完后自动释放，如磁带机，打印机3.非剥夺性资源，在系统中所配置的非剥夺性资源，由于他们的数量不能满足诸进程的需要，会使进程在运行中，因争夺这些资源而陷入僵局。4.临时资源，他是指由一个进程产生，倍另一个进程使用短暂时间后便无用的资源，也称之为消耗性资源。2.4产生死锁的必要条件1.互斥条件：进程对他所分配的资源进行排他性使用，即在一段时间内摸个资源由一个进程占有。如果此时还有其他进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。2.请求和保持条件：进程已经保持了至少一个资源，但又提出新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞，但有对自己获得的其他资源保持不放。3.不剥夺条件：进程已获得的资源，在未使用完之前，不能剥夺，只有在使用完由自己释放。4环路等待条件：发生死锁时，必然存在一个进程一资源的环形链。2.5银行家算发的意义依次对进程测试，直到每一进程能够运行并释放，从而实现了避免死锁的功能。也能提供多种序列可完美实现要求。3.数据结构分析设计3.1可利用资源向量矩阵available[]这是一个含有m个元素的数组，其中每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源数目，起数值随该类资源的分配和回收而动态地改变。如果available[j]=k，则表示系统中现有R类资源K个3.2最大需求矩阵max[][]这是一个n*m的矩阵，用以表示每一个进程对m类资源的最大需求。如果max[i,j]=K，则表示进程i需要R类资源的数目为K。3.3分配矩阵allocation[][]这也是一个n*m的矩阵，他/她定义了系统中每一类资源当前已分配给每一进程的资源数。如果allocation[i，j]=K，则表示进程i当前已分得R类资源的数目为K。3.4需求矩阵need[][]这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果need[i，j]=K，则表示进程i还需要R类资源K个，才能完成其任务。上述矩阵存在下述关系:Need[i,j]=max[i,j]-allocation[i,j]4.算法的实现4.1初始化1.创建available[]数组，用以存放系统中可用的资源数目；2.创建max[][]数组，用以存放各个进程对各类资源的最大需求数目；3.创建allocation[][]数组，用以存放各个进程已经分得的各类资源数目；4.创建need[][]数组，用以存放个各个进程还需要的各类资源数目；5.创建allocationl[][]；need[][];availablel[][]，用以存放系统试分配资源前系统资源分配情况；4.2银行家算法设Request是请求P的请求向量，Request=K表示进程P需要K个j类资源。P发出资源请求后，按下列步骤进行检查：如果reques[j]<=need[i,j]，转向步骤②；否则报错，所需要的资源数已超过它所宣布的最大值；如果request[j]<=available[j]，转向步骤③；否则报错，尚无足够资源P需等待；尝试将资源分配给进程P，并修改下面数据结构中的数值：acailable[j]:=available[j]-request[j];allocation[i,j]:=allocation[i,j]]+request;need[i,j]:=need[i,j]-request[j];执行安全性算法，检查此次资源分配后，系统师傅处于安全状态。若安全，才正式将资源分配给P[i]，已完成本次分配；否则，将本溪试探分配作废，回复原来的资源分配状态，让P[i]等待。

4.3算法流程图4.3.1.初始化算法流程图：计算各个进程还需的资源数计算各个进程还需的资源数NEED[i][j]=Max[i][j]–Allocation[i][j]结束开始输入进程总数M输入资源种类个数N输入每个进程最大资源需求数Max[][]输入每个进程已分配的资源数Allocation输入现在可用资源数Available4.3.2银行家算法流程图：NONOYESYESNO开始录入请求资源数RQUEST[i]>NEED[i]或者REQUEST[i]>AVAILABLE[i]报错，重新输入AVAILABLE[i]-=REQUEST[i];

ALLOCATION[i]+=REQUEST[i];

NEED[i]-=REQUEST[i];初始化安全性检查安全AVAILABLE[i]+=REQUEST[i];

ALLOCATION[i]-=REQUEST[i];

NEED[i]+=REQUEST[i];保持原分配进程执行完释放资源继续分配结束YESNOYESNO测试与实例分析

实验总结多个进程同时运行时，系统根据各类系统资源的最大需求和各类系统的剩余资源