操作系统教程
——银行家算法
院系 班级 学号 姓名
计算机与软件学院 08 软件工程 2 班
20081344066 何丽茗
一、实验目的
银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法 程序�进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念�并掌握避免死锁 的具体实施方法。
四、实验代码以及运行示例
1. 源代码�
#include<iostream>
#include<string.h>
#include<stdio.h>
#define False 0
#define True 1
using namespace std;
intMax[100][100]={0};//各进程所需各类资源的最大需求
for(j=0;j<N;j++)
cout<<Allocation[i][j]<<" ";
cout<<" ";
for(j=0;j<N;j++)
cout<<Need[i][j]<<" ";
cout<<endl;
}
}
intchangdata(inti)//进行资源分配 {
int j; for (j=0;j<M;j++) {
Y
i加1
提示 错误 重新 输入
所有进程运行 都结束
结束
初始化 need 矩阵 Y Need 矩阵为 0
N
任选一个进程作为当前进程
Need 向量为 0 N
Y 该进程已运行 结束
输入该进程的资源请求量
Request
调用银行家算法�及安全性算法� 完成分配�或并给出提示
2. 算法数据结构 1) 可利用资源向量 Available �它是一个最多含有 100 个元素的数组�其中的每一个元素
代表一类可利用的资源的数目�其初始值是系统中所配置的该类全部可用资源数目。其 数值随该类资源的分配和回收而动态地改变。如果 Available�j�=k�标是系统中现有 j 类资源 k 个。 2) 最大需求矩阵 Max�这是一个 n×m 的矩阵�它定义了系统中 n 个进程中的每一个进程 对 m 类资源的最大需求。如果 Max�i�j�=k�表示进程 i 需要 j 类资源的最大数目为 k。 3) 分配矩阵 Allocation�这也是一个 n×m 的矩阵�它定义了系统中的每类资源当前一分 配到每一个进程的资源数。如果 Allocation�i�j�=k�表示进程 i 当前已经分到 j 类资 源的数目为 k。Allocation i 表示进程 i 的分配向量�有矩阵 Allocation 的第 i 行构成。 4) 需求矩阵 Need�这还是一个 n×m 的矩阵�用以表示每个进程还需要的各类资源的数 目。如果 Need�i�j�=k�表示进程 i 还需要 j 类资源 k 个�才能完成其任务。Need i 表示进程 i 的需求向量�由矩阵 Need 的第 i 行构成。 5) 上述三个矩阵间存在关系�Need�i�j�=Max�i�j�-Allocation�i�j�� 3. 银行家算法 设 Request[i] 是进程 i 的请求向量�如果 Request[i�j]=K,表示进程 i 需要 K 个 j 类型的资 源。当 i 发出资源请求后�系统按下述步骤进行检查� 1) 如果 Request i ≤Need�则转向步骤 2�否则�认为出错�因为它所请求的资源数已超 过它当前的最大需求量。 2) 如果 Request i ≤Available�则转向步骤 3�否则�表示系统中尚无足够的资源满足 i 的 申请�i 必须等待。 3) 系统试探性地把资源分配给进程 i�并修改下面数据结构中的数值� Available = Available - Request i Allocation i= Allocation i+ Request i Need i= Need i - Request i 4) 系统执行安全性算法�检查此次资源分配后�系统是否处于安全状态。如果安全才正式 将资源分配给进程 i�以完成本次分配�否则�将试探分配作废�恢复原来的资源分配 状态�让进程 i 等待。
Avaliable[j]=Avaliable[j]-Request[j]; Allocation[i][j]=Allocation[i][j]+Request[j]; Need[i][j]=Need[i][j]-Request[j]; }
二、实验内容
根据银行家算法的基本思想�编写和调试一个实现动态资源分配的模拟程序�并能够有 效地防止和避免死锁的发生。
三、实验方法
1. 算法流程图
开始
输入资源数 m, 及各类资源总数�初始化 Available 向量
输入进程数 n� i=1
Y i≤n
N 输入进程 i 的最大需求向量 max。
N max≤资源总数
for(i=0;i<N;i++)
cout<<name[i]<<" ";
cout<<endl;
for (j=0;j<N;j++) cout<<Avaliable[j]<<"";//输出分配资源
cout<<endl;
cout<<" cout<<"进程名
Max ";
Allocation Need"<<endl;
int temp[100]={0};//存放安全序列 int Work[100]={0};//存放系统可提供资源 int M=100;//进程的最大数为 int N=100;//资源的最大数为 voidshowdata()//显示资源矩阵
{
int i,j; cout<<"系统目前可用的资源[Avaliable]:"<<endl;
intAvaliable[100]={0};//系统可用资源
charname[100]={0};//资源的名称
int Allocation[100][100]பைடு நூலகம்{0};//系统已分配资源
intNeed[100][100]={0};//还需要资源
intRequest[100]={0};//请求资源向量
for(j=0;j<3;j++){
for(i=0;i<N;i++)
cout<<name[i]<<" ";
cout<<" ";
}
cout<<endl;
for(i=0;i<M;i++){
cout<<" "<<i<<"
";
for(j=0;j<N;j++)
cout<<Max[i][j]<<" ";
cout<<" ";