admin 管理员组文章数量: 887019
前言：本程序从本人报告拷贝过来，格式可能稍有问题，但应该不影响阅读。
一、题目与要求题目：实现银行家算法
要求：提交电子档报告
二、需求分析
思想：面向对象程序设计
数据结构：一维数组、二维数组等（注：该算法可以引进队列，但由于队列相关知识的遗忘，所以就没有用到队列，后面会加强这一方面的学习！）
三、银行家算法
3.1算法思想
申请者事先说明对各类资源的最大需求量。在进程活动期间动态申请某类资源时，由系统审查系统现有的该类资源的数目是否满足当前进程的最大需求量，如能满足就给予分配，否则拒绝。
3.2数据结构
(1) 可利用资源向量available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。
如果available[j]=K，则表示系统中现有Rj类资源K个。
(2) 最大需求矩阵max。这是一个m×n的矩阵，它定义了系统中m个进程中的每一个进程对n类资源的最大需求。如果max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
(3) 分配矩阵allocation。这也是一个m×n的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。
如果allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
(4) 需求矩阵need。这也是一个m×n的矩阵，用以表示每一个进程尚需的各类资源数。如果need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
上述三个矩阵间存在下述关系：need[i, j]=max[i, j]-allocation[i,j]
3.3算法
在这里算法主要有两种：1、银行家算法 2、安全算法
3.3.1银行家算法：
设request i是进程Pi的请求向量，如果request i[j]=K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查：
(1) 如果requesti[j]>=need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果requesti[j]≤available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
(3) 系统试探着把资源分配给进程P i，并修改下面数据结构中的数值：
available[j]:= available[j]-request i[j]；
allocation[i,j]:= allocation[i,j]+request i[j]；
need[i,j]:= need[i,j]-request i[j]；
(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
3.3.2安全算法
系统所执行的安全性算法可描述如下：
(1) 设置两个向量：
① 工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有n个元素，在执行安全算法开始时，work:=available。
② finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做finish[i]:=false；当有足够资源分配给进程时，再令finish[i]:=true。
(2) 从进程集合中找到一个能满足下述条件的进程：
① finish[i]=false；
② need[i,j]≤work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。
(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
work[j]:= work[j]+allocation[i,j]；
finish[i]:=true；
go to step （2）；
(4) 如果所有进程的finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
3.4死锁的定义及死锁发生的条件
银行家算法是为了解决死锁问题而产生的一种算法：
3.4.1死锁的定义
死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
银行家算法是避免死锁的一种重要方法。 操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
3.4.2死锁的发生条件
① 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
② 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
③ 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
④ 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。
四、设计
4.1设计思想
（1）包含各头文件以及声明命名空间
（2）声明一个bank类，该类中有Init()、Banker()、Display()、Safe()函数
（3）实现bank类中的各个函数
（4）主函数
4.2设计表示
|
|
|
|
|
|
|
|
|
|
4.3 详细设计
（1）包含各头文件以及声明命名空间
#include<iostream>
using namespace std;
const int Max_process = 50;//最大进程数
const int Max_source = 50;//最大资源数
（2）声明一个bank类，该类中有Init()、Banker()、Display()、Safe()函数
class bank
{
private:
int available[Max_source];//可用资源数
int max[Max_process][Max_source];//最大需求
int allocation[Max_process][Max_source];//已分配资源数
int need[Max_process][Max_source];//还需资源数
int request[Max_process][Max_source];//进程需要资源数
bool finish[Max_process];//判断系统是否有足够的资源分配
int p[Max_process];//记录序列
int m;//用来表示进程
int n;//表示资源
public:
void Init();//完成对变量的初始化
bool Safe();//安全检测算法
void Banker();//银行家算法
void Display(int ,int );//显示进程与资源状态
};
void bank::Init()//实现对各个数组的初始化
void bank::Display(int n, int m)//实现对数组的输出
void bank::Banker()//实现银行家算法
bool bank::Safe()//实现安全性算法五、调试分析
为了增加程序的鲁棒性，我后面对程序进行了改进，主要体现在对need数组的取值上，当need数组中有个值小于0时，程序会跳出本次循环，并且j--,即忽略本次need值的取值，同时提醒用户重新输入allocation数组的值
for (int i = 0; i < m;i++)
for (int j = 0; j < n;j++)
{
cin >> allocation[i][j];
need[i][j]= max[i][j] - allocation[i][j];//注意这里的need可能小于0；要进行报错并重新输入，可以用continue来跳出当前循环
if (need[i][j] < 0)
{
cout <<"你输入的第"<<i+1<<"个进程的第"<<j+1<<"个资源数有问题！\n请重新输入！";
j--;//忽略这个资源数
continue;//跳出本次循环
}
}此外，之前写的程序缺点在于进程和资源数比较固定（分别是5个进程和3个资源），后来干脆采用了定义两个全局常量，来使得进程数和资源数可以有更多的选择，而且方便后期对程序的调试（一次又一次的输入一个个5X3矩阵真的很麻烦，而当我们输入1个进程一个资源的时候可以测试程序的可行
六、用户手册
用户需要按照系统提示，进行相关输入操作，依次输入，
七、测试数据及检测结果
自动生成安全序列：
资源申请操作：（其中安全序列是随着资源申请操作动态变化的）
（至此资源分配完毕！）
八、源程序清单
#include<iostream>
using namespace std;
const int Max_process = 50;//最大进程数
const int Max_source = 50;//最大资源数
class bank
{
private:
int available[Max_source];//可用资源数
int max[Max_process][Max_source];//最大需求
int allocation[Max_process][Max_source];//已分配资源数
int need[Max_process][Max_source];//还需资源数
int request[Max_process][Max_source];//进程需要资源数
bool finish[Max_process];//判断系统是否有足够的资源分配
int p[Max_process];//记录序列
int m;//用来表示进程
int n;//表示资源
public:
void Init();//完成对变量的初始化
bool Safe();//安全检测算法
void Banker();//银行家算法
void Display(int ,int );//显示进程与资源状态
};
void bank::Init()
{
cout << "请输入进程的数目：";
cin >> m;
cout << "请输入资源的数目:";
cin >> n;
cout << "请输入每个进程最多所需的各资源数，按照"<<m<<'X'<<n<<"矩阵格式输入"<<endl;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> max[i][j];
cout << "请输入每个进程已分配的各资源数，按照" << m << 'X' << n << "矩阵格式输入" << endl;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
cin >> allocation[i][j];
need[i][j] = max[i][j] - allocation[i][j];//注意这里的need可能小于0；要进行报错并重新输入，可以用continue来跳出当前循环
if (need[i][j] < 0)
{
cout << "你输入的第"<<i+1<<"个进程的第"<<j+1<<"个资源数有问题！\n请重新输入！";
j--;//忽略这个资源数
continue;//跳出本次循环
}
}
cout << "请输入各个资源现有的数目"<<endl;
for (int i = 0; i < n; i++)
{
cin >> available[i];
}
}
//m表示进程，n表示资源
void bank::Display(int n, int m)
{
cout << endl << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++" << endl;
cout << "系统可用的资源数为： ";
for (int i = 0; i < n; i++)
{
cout << available[i] << " ";
}
cout << endl << "各进程还需要的资源量：" << endl;
for (int i = 0; i < m; i++)
{
cout << " 进程" << i << ":";
for (int j = 0; j < n; j++)
cout << " " << need[i][j];
cout << endl;
}
cout << endl << "各进程已经得到的资源: " << endl;
for (int i = 0; i < m; i++)
{
cout << " 进程" << i << ":";
for (int j = 0; j < n; j++)
{
cout << " " << allocation[i][j];
}
cout << endl;
}
cout << endl << endl;
}
void bank::Banker()
{
int i, cusneed, flag = 0;//cusneed表示资源进程号
char again;//键盘录入一个字符用于判断是否继续请求资源
while (1)
{
Display(n,m);
cout << endl;
/*请求资源*/
while (true)
{
cout << "请输入要申请的进程号"<<endl;
cin >> cusneed;
if (cusneed > m)
{
cout << "没有该进程，请重新输入"<<endl;
continue;
}
cout << "请输入进程所请求的各资源数" << endl;
for (int i = 0; i < n; i++)
cin >> request[cusneed][i];
for (int i = 0; i < n; i++)
{
if (request[cusneed][i] > need[cusneed][i])
{
cout << "你输入的资源请求数超过进程数需求量！请重新输入"<<endl;
continue;
}
if (request[cusneed][i] > available[i])
{
cout << "你输入的资源请求数超过系统当前资源拥有数！" << endl;
break;
}
}
break;
}
/*上述是资源请求不合理的情况，下面是资源请求合理时则执行银行家算法*/
for (int i = 0; i < n; i++)
{
available[i] -= request[cusneed][i];//可用资源减去成功申请的
allocation[cusneed][i] += request[cusneed][i];//已分配资源加上成功申请的
need[cusneed][i] -= request[cusneed][i];//进程还需要的减去成功申请的
}
/*判断分配申请资源后系统是否安全，如果不安全则将申请过的资源还给系统*/
if (Safe())
cout << "同意分配请求！";
else
{
cout << "你的请求被拒绝！ ！！"<<endl;
/*进行向系统还回资源操作*/
for (int i = 0; i < n; i++)
{
available[i]+= request[cusneed][i];
allocation[cusneed][i] -= request[cusneed][i];
need[cusneed][i] += request[cusneed][i];
}
}
/*对进程的需求资源进行判断，是否还需要资源，简言之就是判断need数组是否为0*/
for (int i = 0; i < n; i++)
if (need[cusneed][i] <= 0)
flag++;
if (flag == n)
{
for (int i = 0; i < n; i++)
{
available[i] += allocation[cusneed][i];
allocation[cusneed][i] = 0;
need[cusneed][i] = 0;
}
cout << "进程" << cusneed << "占有的资源已释放！！"<<endl;
flag = 0;
}
for (int i = 0; i < m; i++)
finish[i] = false;
/*判断是否继续申请*/
cout << "你还想再次请求分配吗？是请按Y/y，否请按其他键！" << endl;
cin >> again;
if (again == 'Y' || again == 'y')
continue;
break;
}
}
bool bank::Safe()
{
int l = 0, j, i;
int work[Max_source];
/*对work数组进行初始化，初始化时和avilable数组相同*/
for (int i = 0; i < n; i++)
work[i] = available[i];
/*对finish数组初始化全为false*/
for (int i = 0; i < m; i++)
finish[i] = false;
for (int i = 0; i < m; i++)
{
if (finish[i] == true)
continue;
else
{
for (j = 0; j < n; j++)
{
if (need[i][j] > work[j])
break;
}
if (j ==n)
{
finish[i] = true;
for (int k = 0; k < n; k++)
work[k] += allocation[i][k];
p[l++] = i;//记录进程号
i = -1;
}
else
continue;
}
}
if (l == m)
{
cout << "系统是安全的" << endl;
cout << "安全序列：" << endl;
for (int i = 0; i < l; i++)
{
cout << p[i];
if (i != l - 1)
cout << "-->";
}
cout << endl << endl;
return true;
}
}
int main()
{
bank peter;
peter.Init();
peter.Safe();
peter.Banker();
return 0;
}版权声明：本文标题：操作系统实习：银行家算法（C++面向对象的思想实现） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1727377675h1111093.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论