操作系统 银行家算法.doc

操作系统课程设计

银行家算法
第一章引言
课程设计目地:
操作系统是计算机系统的核心系统软件,它负责控制和管理整个系统的资源并组织用户协调使用这些资源,使计算机高效的工作。课程设计的目的是综合应用学生所学知识,通过实验环节,加深学生对操作系统基本原理和工作过程的理解,提高学生独立分析问题、解决问题的能力,增强学生的动手能力。
第二章银行家算法描述
银行家算法简介:
银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次分配资源的安全性,若分配不会导致系统进入不安全状态,则分配,否则等待。
要解释银行家算法,必须先解释操作系统安全状态和不安全状态。
安全状态:如果存在一个由系统中所有进程构成的安全序列P1,…,Pn,则系统处于安全状态。安全状态一定是没有死锁发生。
不安全状态:不存在一个安全序列。不安全状态不一定导致死锁。
那么什么是安全序列呢?
安全序列:一个进程序列{P1,…,Pn}是安全的,如果对于每一个进程Pi(1≤i≤n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
银行家算法描述:
我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。


先对用户提出的请求进行合法性检查,即检查请求的是不大于需要的,是否不大于可利用的。若请求合法,则进行试分配。最后对试分配后的状态调用安全性检查算法进行安全性检查。若安全,则分配,否则,不分配,恢复原来状态,拒绝申请。
银行家算法中用到的主要数据结构
可利用资源向量 int Available[j] j为资源的种类。
最大需求矩阵 int Max[i][j] i为进程的数量。
分配矩阵 int Allocation[i][j]
需求矩阵 int need[i][j]= Max[i][j]- Allocation[i][j]
申请各类资源数量 int Request i[j] i进程申请j资源的数量
工作向量 int Work[x] int Finish[y]
银行家算法bank()
进程i发出请求申请k个j资源,Request i[j]=k
(1)检查申请量是否不大于需求量:Request i[j]<=need[i,j],若条件不符重新输入,不允许申请大于需求量。
(2)检查申请量是否小于系统中的可利用资源数量:Request i[j]<=available[i,j],若条件不符就申请失败,阻塞该进程,用goto语句跳转到重新申请资源。
(3)若以上两个条件都满足,则系统试探着将资源分配给申请的进程,并修改下面数据结构中的数值:
Available[i,j]= Available[i,j]- Request i[j];
Allocation[i][j]= Allocation[i][j]+ Request i[j];
need[i][j]= need[i][j]- Request i[j];
(4)试分配后,执行安全性检查,调用safe()函数检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程;否则本次试探分配作废,恢复原来的资源分配状态,让该进程等待。
(5)用do{…}while 循环语句实现输入字符y/n判断是否继续进行资源申请。
(safe()函数)
(1)设置两个向量:
工作向量Work,它表示系统可提供给进程继续运行所需的各类资源数目,在执行安全性算法开始时,Work= Available。
Finish,它表示系统是否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]=0;当有足够的资源分配给进程时,再令Finish[i]=1。
(2)在进程中查找符合以下条件的进程:
条件1:Finish[i]=0;
条件2:need[i][j]<=Work[j]
若找到,则执行步骤(3)否则,执行步骤(4)
(