操作系统课程设计—银行家算法—c++描述
1.目的和要求
在熟练掌握死锁发生原理和解决死锁问题的基础上，利用一种程序设计语言模拟实现利用银行家算法实现死锁避免，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。
2.设计内容
模拟实现银行家算法实现死锁避免。
3.设计思想。
银行家算法描述：
银行家算法中的数据结构
为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
(1) 可利用资源向量 Available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。
(2) 最大需求矩阵Max。这是一个n x m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj 类资源的最大数目为K。
(3) 分配矩阵 Allocation。这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,jl = K，则表示进程i当前己分得Rj类资源的数目为K。
(4) 需求矩阵Need.这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。
上述三个矩阵间存在下述关系:
Need[i,j] = Max[i,j] - allocation[i, j]
银行家算法详述：
设 Request；是进程Pi的请求向量，如果 Requesti[j] = K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检査:
(1) 如果 Requesti[j] ≤ Need[i,j]便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
(2) 如果 Requesti[j] ≤ Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值
Available[j] = Available[j] - Requesti[j];
Allocation[i,j] = Allocation[i,j] + Requesti[j];
Need[i,j] = Need[i,j] - Requesti[j];
(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
安全性算法:
系统所执行的安全性算法可描述如下:
(1) 设置两个向量:①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，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都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
本实验的设计思路：
- 根据教材上银行家算法的描述定义一些模拟数据：
系统中资源的种数（假设：n）；
每类资源的数量（假设：m1，m2,…,mn）；
当前系统中资源的使用情况等。 - 给出一个当前系统资源的使用情况的模拟数据矩阵（该数据可事先保存于磁盘文件，程序执行后从该磁盘文件读入矩阵数据），然后通过用户手工输入下一个进程的资源申请要求的一维向量（控制台输入，此方式可以输入各种资源请求的可能情况,以检测当前的资源申请后是否系统处于安全状态）。Work和Available向量为全局函数。
4.源程序
// F:\debug\c++debug\OperatingSystem\BankerBlgorithm\Debug\BankerBlgorithm.exe
// author:aaa@qq.com
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <ctime>
#include <windows.h>
#include <fstream>
using namespace std;//使用默认命名空间
//以下是进程类的定义与实现
class process
{
friend void BankerAlgorithm(process *&headptr,int processnumber,int QuantityOfResources,int Available[],int Work[],int num);//友元函数，银行家算法
friend int SecurityAlgorith(process *&headptr,int processnumber,int QuantityOfResources,int Available[],int Work[]);//友元函数，安全性算法
protected:
int Max[3];
int Allocation[3];
int Need[5];
int Request[3];
bool Finish[3];
public:
process(){} //默认构造函数
process(process &p){}//默认拷贝构造函数
~process(){}
void setMax(process *headptr,int i,int temp)//设置最大需求
{
headptr->Max[i] = temp;
}
void setAllocation(process *headptr,int i,int temp)//设置分配
{
headptr->Allocation[i] = temp;
}
void setNeed(process *headptr,int i,int temp)//设置需求
{
headptr->Need[i] = temp;
}
void setRequest(process *&headptr,int num,int i)//设置请求
{
int temp;
cout<<"请输入您修改后的資源"<<i<<"的请求资源数目：";
cin>>temp;
(headptr+num)->Request[i]=temp;
}
void display(process *headptr,int Available[])//显示进程信息
{
cout<<"Max"<<"\t"<<"Allocation"<<"\t"<<"Need"<<"\t"<<"Available"<<endl;
cout<<headptr->Max[0]<<" "<<headptr->Max[1]<<" "<<headptr->Max[2]<<"\t"<<headptr->Allocation[0];
cout<<" "<<headptr->Allocation[1]<<" "<<headptr->Allocation[2]<<"\t"<<headptr->Need[0]<<" "<<headptr->Need[1];
cout<<" "<<headptr->Need[2]<<"\t"<<Available[0]<<" "<<Available[1]<<" "<<Available[2]<<endl;
}
};//process
void BankerAlgorithm(process*& headptr, int processnumber, int QuantityOfResources, int Available[],int Work[],int num)//输入请求，得到安全序列
{
cout << "(正在执行银行家算法)" << endl;
int temp = 0;
for(int i = 0;i < QuantityOfResources;i++)//设置请求
{
(headptr+num)->setRequest(headptr,num,i);
}
//到目前為止完成了參數的輸入、传递工作
for(int j = 0; j < QuantityOfResources;j++)//顺次执行资源分配
{
if((headptr+num)->Request[j] <= (headptr+num)->Need[j])
{
if((headptr+num)->Request[j] <= (headptr+num)->Need[j])
{
Available[j] = Available[j] - (headptr+num)->Request[j];
(headptr+num)->Allocation[j] = (headptr+num)->Allocation[j] + (headptr+num)->Request[j];
(headptr+num)->Need[j] = (headptr+num)->Need[j] - (headptr+num)->Request[j];
temp++;
}
else
{
cout <<"error:"<<"进程"<<num<<"资源"<<j<< "所需要资源已超过它所宣布的最大值"<<endl;
}
}
else
{
cout <<"error:"<<"进程"<<num<<"资源"<<j<< "尚无足够资源"<<endl;
}
}
if(temp == 3)
{
if(SecurityAlgorith(headptr,processnumber,QuantityOfResources,Available,Work))//执行安全性算法
{
cout<<"资源分配成功！"<<endl;
}
else//归还资源
{
for(int j = 0;j < QuantityOfResources;j++)
{
Available[j] = Available[j] + (headptr+num)->Request[j];
(headptr+num)->Allocation[j] = (headptr+num)->Allocation[j] - (headptr+num)->Request[j];
(headptr+num)->Need[j] = (headptr+num)->Need[j] + (headptr+num)->Request[j];
}
cout<<"资源分配失败！"<<endl;
}
}
else//归还资源
{
for(int j = 0;j < QuantityOfResources;j++)
{
Available[j] = Available[j] + (headptr+num)->Request[j];
(headptr+num)->Allocation[j] = (headptr+num)->Allocation[j] - (headptr+num)->Request[j];
(headptr+num)->Need[j] = (headptr+num)->Need[j] + (headptr+num)->Request[j];
}
cout<<"资源分配失败！"<<endl;
}
}//BankerAlgorithm
int SecurityAlgorith(process*& headptr, int processnumber, int QuantityOfResources, int Available[], int Work[])//安全性算法
{
cout << "（正在执行安全性算法）" << endl;
int list[5],temp,tempWork[3]; //安全序列
for(int i=0;i < processnumber;i++)//初始化程序
{
for(int j = 0;j < QuantityOfResources;j++)
{
Work[j] = Available[j];
(headptr+i)->Finish[j] = false;
}
}
for(i = 0;i < processnumber;i++)//初始化安全序列
list[i] = -1;
for(int k = 0;k < processnumber;k++)//寻找安全序列
{
for(int i = 0;i < processnumber;i++)
{
if( (list[k] == -1) )//进程是否已经存在于安全序列中
{
temp = 0;//临时变量置0
for(int j = 0;j < QuantityOfResources;j++)
{
if( ((headptr+i)->Finish[j] == false) && ((headptr+i)->Need[j] <= Work[j]) )
{
tempWork[j] = Work[j];
Work[j]=Work[j] + (headptr+i)->Allocation[j];
(headptr+i)->Finish[j] = true;
temp++;
}
else
{
//cout <<"error:"<<"进程"<<i<<"资源"<<j<<"导致系统处于不安全状态"<<endl;
}
}
if( temp == 3 )//是否3种资源都符合条件
{
list[k]=i;
cout<<"当前符合条件的进程p"<<i<<":Work+Allocation:";
for(i = 0;i<QuantityOfResources;i++)
{
cout<<Work[i]<<" ";
}
cout<<endl;
}
else if( (temp <=2) && (temp >=1))//不符合条件的需要归还资源，别忘记了
{
for(int j = 0;j < QuantityOfResources;j++)
{
if( ((headptr+i)->Need[j] <= tempWork[j]) && ((headptr+i)->Finish[j] == true) )
{
Work[j]=Work[j] - (headptr+i)->Allocation[j];
(headptr+i)->Finish[j] = false;
}
}
}
}
else//若存在，退出该轮循环
{
break;
}
}
}
cout<<"安全序列为";
for(i = 0;i < processnumber;i++)
{
if(list[i] != -1 )
cout<<list[i]<<" ";
else
return 0;
}
cout<<endl;
cout<<"恭喜您当前系统处于安全状态!"<<endl;
return 1;
}//SecurityAlgorithm
const int processnumber = 5; //进程数量
const int QuantityOfResources = 3; //资源种类
int Available[3]; //可用资源
int Work[3]; //工作向量
//以下是主函数的定义与实现
int main(int argc,char **argv)
{
int num;
time_t Time;
time(&Time);
int control;
process *headptr = new process[5];
if(argc != 2)//若打开文件失败,输出错误信息
{
cout<<"Usage:'"<<argv[0]<<".exe DataFile.txt'\n";
return -1;//输入参数不对
}
else//从文件读入数据
{
cout<<"(从文件中读入数据)"<<endl;
FILE *fp;
int temp[9];
//cout<<argv[1]<<endl;
if ((fp = fopen("F:\\debug\\C++Debug\\OperatingSystem\\BankerBlgorithm\\DataFiletxt.txt","rt")) == NULL)//若打开文件失败
{
printf("FILE OPEN ERROR!\n");
exit(0);//异常退出
}
for (int i = 0 ; i < processnumber ; i++)
{
fscanf(fp,"%d %d %d %d %d %d %d %d %d",&temp[0],&temp[1],&temp[2],&temp[3],&temp[4],&temp[5],&temp[6],&temp[7],&temp[8]);
for(int j = 0 ; j < QuantityOfResources ; j++)
{
(headptr+i)->setMax((headptr+i),j,temp[j]);
(headptr+i)->setAllocation((headptr+i),j,temp[j+3]);
(headptr+i)->setNeed((headptr+i),j,temp[j+6]);
}
}
fscanf(fp,"%d %d %d",&temp[0],&temp[1],&temp[2]);
for(int j = 0 ; j < QuantityOfResources ; j++)
Available[j] = temp[j];
for(j = 0;j < 5;j++)
(headptr+j)->display((headptr+j),Available);
if (fclose(fp))//关闭文件异常
{
printf("can not close the file!\n");
exit(0);//异常退出
}
}
do
{
cout << "当前系统时间:" << ctime(&Time) <<endl;
cout<<"|======================银行家算法演示系统===================|"<<endl
<<"| 1.进程0 |"<<endl
<<"| 2.进程1 |"<<endl
<<"| 3.进程2 |"<<endl
<<"| 4.进程3 |"<<endl
<<"| 5.进程4 |"<<endl
<<endl;
cout<<"请输入你的指令";
cin>>control;
switch(control)
{
case 1:
system("cls");
num = 0;
BankerAlgorithm(headptr,processnumber,QuantityOfResources,Available,Work,num);
break;
case 2:
system("cls");
num = 1;
BankerAlgorithm(headptr,processnumber,QuantityOfResources,Available,Work,num);
break;
case 3:
system("cls");
num = 2;
BankerAlgorithm(headptr,processnumber,QuantityOfResources,Available,Work,num);
break;
case 4:
system("cls");
num = 3;
BankerAlgorithm(headptr,processnumber,QuantityOfResources,Available,Work,num);
break;
case 5:
system("cls");
num = 4;
BankerAlgorithm(headptr,processnumber,QuantityOfResources,Available,Work,num);
break;
case 0:
cout<<" 感谢使用！ 3秒后程序结束"<<endl;
Sleep(3000);
break;
default:
cout<<" 输入错误！请重新输入：";
Sleep(1000);
system("cls");
}
}
while(control!=0);
delete[] headptr;
return 0;
}
5.实验运行结果
读取文件数据，初始化银行家算法配置信息
选择进程1，分别对资源0、资源1、资源2申请1、0、2种资源后
安全序列为1 3 0 2 4
6.实验总结
- 熟悉了上学期面向对象程序设计c++语言的基本语法；
- 利用文件指针输入输出让程序演示更直观；
- 输出信息时可以利用/t转义符号提高程序的可读性与界面显示的友好性;
- 适当设置友元函数直接访问私有成员，减少工作量；
- 使用int main(int argc,char **argv)来向main函数传入参数。