操作系统课设-银行家算法

《计算机操作系统》

课程设计报告

题 目： 银行家算法设计与实现 专 业： 软件工程 班 级： 09级（2）班 姓 名： XXX 学 号： XXX 指导老师： XXX 完成时间： 2012年2月20日

目录

一、课设题目要求 二、算法设计思路 三、主要数据结构及其说明 四、程序流程图 五、源程序代码 六、结果及数据分析 七、实验心得 八、参考资料

一、课设题目要求

模拟一个银行家算法，要求如下： 输入：

1.系统中各类资源表

2.每个进程需要各类资源总数 系统分配给各个进程各类资源数 输出：

1.判断T0时刻的安全性

2.如果系统是安全的，任意给出某个进程的一个资源请求方式并判断系统能否接受此请求，如果可以接受，其输出全部安全序列，反之，不予分配。

二、算法设计思路

银行家算法是一种最具代表性的避免死锁的算法。要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。

安全状态：如果存在一个由系统中所有进程构成的安全序列P1，?，Pn，则系统处于安全状态。安全状态一定没有死锁发生。

不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。 安全序列：一个进程序列{P1，?，Pn}是安全的，如果对于每个进程Pi（0≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj（j＜i）当前占有资源量之和。

先对系统从源文件中读取的数据进行安全性判断，然后对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，不大于系统可利用的资源。若请求合法，则进行试分配，最后对试分配状态调用安全性算法进行安全性检查。若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。

三、主要数据结构及其说明

进程数 i、M 资源种类数 j、N

最大需求矩阵 int Max[i][j];

分配矩阵 int Allocation[i][j];

需求矩阵 int Need[i][j]=Max[i][j]-Allocation[i][j]; 工作向量 int Work[N];

可利用资源矩阵 int Available[N]; 进程的数目 int n_pro=0;

标记安全序列 int flag[M]={-1}; 安全序列的个数 int w=0;

表示系统是否有足够的资源分配给进程 bool finish[M]; 安全性检查算法 ? Safe（）函数

只要求出了一种安全序列就可以说明系统是处于安全状态的，故： ① 设置了两个向量：工作向量Work，它表示系统可提供给进程继续运

行所需的各类资源数目，在执行安全性算法开始时，Work =

Available。Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时令Finish[i]=false，当有足够的资源分配给进程时，再令Finish[i]=1。

② 在进程中查找符合以下条件的进程：

条件1：Finish[i]=0;

条件2：Need[i][j]<=Work[j];

若找到，则执行步骤③，否则，执行步骤④

③ 当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资

源，故应执行：

Work[j] += Allocation[i][j]; Finish[i]= true; goto step 2;

④ 如果所有的Finish[i]=true，则表示系统处于安全状态，否则，处

于不安全状态。

? Safe1（int flag[],int n,int t）函数

用于输出所有的安全序列，使用了回溯法。 ? Request（）函数

用于进程请求资源。输入发出请求的进程号i，请求的资源数

Request[i][j]，系统按银行家算法进行检查：①所请求的资源小于等于所需要的资源，否则分配不合理，不予分配；②所请求的资源小于等于系统可利用资源，否则分配不合理，不予分配；③假设可为该进程分配资源，安全性检查，若有安全序列，分配资源，否则系统处于不安全状态，不予分配

四、程序流程图

整体流程图

开始从文件中读取数据判断系统是否是安全的是请求资源判断系统是否是安全的否是否分配资源资源不分配资源资源结束判断系统的安全性Safe（）

Safe（）开始初始化i，j，t,tempnFihish[i]=falseTempn==0?Fi=Need[i][0]) && (Work[1]>=Need[i][1]) && (Work[2]>=Need[i][2])tp==1?YFi++Finish[i]=true;Work[j]+=Allocation[i][j];Tempn--i=0i