银行家算法C--代码实现.docx

编号：
实验
一
二
三
四
五
六
七
八
九
十
总评
教师签名
成绩

武汉大学计算机学院

课程实验(设计)报告

专业(班)： 计算机科学与技术 计科6班
学 号： 2013301500217
姓 名： 张伟
课程名称： 操作系统设计
任课教师： 宋伟

2015年12 月22日

银行家算法实现
一、 实习内容
编写实现银行家算法，实现资源的安全分配。
通过本实验熟悉银行家算法，对预防死锁有更深刻的认识。

二、 实习题目
初始状态下，设置数据结构存储可利用资源向量（Available），最大需求矩阵（MAX），分配矩阵（Allocation），需求矩阵（Need），输入待分配进程队列和所需资源。
设计安全性算法，设置工作向量表示系统可提供进程继续运行的可利用资源数目。
如果进程队列可以顺利执行打印输出资源分配情况，如果进程队列不能顺利执行打印输出分配过程，提示出现死锁位置。

三、 设计思想
数据结构
class process //定义 进程
{
public :
bool finish = false; //完成状态
int need[max_resources]; //还需要分配的资源
int allocation[max_resources]; //已经分配的资源
int max_need[max_resources]; //最大需求量
int request[max_resources]; //本次需求量
public:
process(int _need[max_resources], int _allocation[max_resources], int _max_need[max_resources])
{
for (int i = 0; i < max_resources; i++)
{
need[i] = _need[i];
allocation[i] = _allocation[i];
max_need[i] = _max_need[i];
}
}
//构造函数
void set(int _need[max_resources], int _max_need[max_resources])
{
for (int i = 0; i < max_resources; i++)
{
need[i] = _need[i];
allocation[i] = 0;
max_need[i] = _max_need[i];
}
} //赋值函数
process()
{

}

};
主要函数
（1）bool check_safe(int work[max_process], process my_process[max_process]) //安全性算法
（2）bool destribute(int available[max_resources], process the_process, process my_process[max_process]) //是否分配空间成功的算法
(3) void init(int available[max_resources], process my_process[max_process]) //初始化函数
Main函数
int main()
{
int _need[max_resources];
int _allocation[max_resources];

int available[max_resources];
process my_process[max_process];
int i,j;
int choice=1;
init( available, my_process);
while (true)
{
cout << " 选项\n 1：继续分配\n 2:查看当前available资源数\n其他字符：退出\n";
scanf_s("%d", &choice);
switch (choice)
{ case 1:
{
cout << "请输入本次请求分配给第i个进程的资源，格式：进程号 xx xx xx xx，空格隔开" << endl;
scanf_s("%d", &i);
for (j = 0; j < max_resources; j++)
{

scanf_s("%d", &my_process[i].request[j]);
}
if (destribute(available, my_process[i], my_process) == true)
{
cout << "此次destribute成功" << endl;
}
else cout << "此次destribute不成功" << endl;
}
break;
case 2:
{ for (i = 0; i < max_resources; i++)
cout << "第" << i << "个资源还剩" << available[i] << "个\n";
break;
}
default: break;

}

}
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
return 0;
}银行家算法操作部分
银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。 
设进程cusneed提出请求REQUEST [i]，则银行家算法按如下规则进行判断。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，则转(2)；否则，出错。 
(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，则转(3)；否则，出错。 
(3)系统试探分配资源，修改相关数据： 
         AVAILABLE[i]-=REQUEST[cusneed][i]; 
         ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];          NEED[cusneed][i]-=REQUEST[cusneed][i]; 
(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
安全性算法检验部分
1)设置两个工作向量Work=AVAILABLE;FINISH (2)从进程集合中找到一个满足下述条件的进程， 
FINISH==false; NEED<=Work; 
如找到，执行(3)；否则，执行(4) 
(3)设进程获得资源，可顺利执行，直至完成，从而释放资源。 
Work+=ALLOCATION; Finish=true; GOTO 2 
(4)如所有的进程Finish= true，则表示安全；否则系统不安全。
结果显示部分
在屏幕上面打印本次分配资源是否成功或者失败
或者打印当前available资源状态

四、 源代码
/*C++ Source File*/
/*开发环境为Microsoft Visual Studio 2015*/
#include<iostream>
using namespace std;
#define max_process 5
#define max_resources 4

class process
{
public :
bool finish = false; //完成状态
int need[max_resources]; //还需要分配的资源
int allocation[max_resources]; //已经分配的资源
int max_need[max_resources]; //最大需求量
int request[max_resources]; //本次需求量
public:
process(int _need[max_resources], int _allocation[max_resources], int _max_need[max_resources])
{
for (int i = 0; i < max_resources; i++)
{
need[i] = _need[i];
allocation[i] = _allocation[i];
max_need[i] = _max_need[i];
}
}
//构造函数
void set(bool _finish, int _need[max_resources], int _allocation[max_resources], int _max_need[max_resources],int _request[max_resources])
{
for (int i = 0; i < max_resources; i++)
{
finish = _finish;
need[i] = _need[i];
allocation[i] = _allocation[i];
max_need[i] = _max_need[i];
request[i] = _request[i];
}
} //赋值函数
process()
{

}

};

bool check_safe(int work[max_process], process my_process[max_process]) //安全性算法
{
int temp_work[max_process];
process temp_process[max_process];
for (int no = 0; no < max_process; no++)
{
temp_work[no] = work[no];
temp_process[no].set(my_process[no].finish, my_process[no].need, my_process[no].allocation, my_process[no].max_need, my_process[no].request);
} //先把每个进程的状态存储在临时数组，最后在拷贝回去
int i = 0;
int x = 0;
bool check_everyone[max_process] = { true ,true,true,true,true};
bool check = false;
int num = 0;
while (check == false&&num<max_process*max_process/2)
{
num++;
for (i = 0; i < max_process; i++) //找到一个可以完成的资源
{
for ( x = 0; x < max_resources; x++) //对于每个进程，检查资源是否够
{
if (my_process[i].finish == false)
{
check_everyone[i] = work[x] >= my_process[i].need[x];
}
else break;
if (check_everyone[i] == false)
break;
}
if (check_everyone[i] == true)
{ /*先把资源分配给i进程，然后运行完后释放掉*/

for (x = 0; x < max_resources; x++)
{
work[x] = work[x] + my_process[i].need[x];
}
break;
}

}

/*检查是否所有的进程都为true，如果是，那么check置为true*/
for (int temp = 0; temp < max_process; temp++)
{
if (check_everyone[temp] == false)
{
check = false; break;
}
else check = true;
}
/*cout << "check" << endl;*/
}
for (int no = 0; no < max_process; no++)
{
work[no] = temp_work[no];
my_process[no].set(temp_process[no].finish, temp_process[no].need, temp_process[no].allocation, temp_process[no].max_need, temp_process[no].request);
} //安全性算法检测完毕，把数据拷贝回来
return check;
}

bool destribute(int available[max_resources], process the_process, process my_process[max_process])
{ //是否分配成功的算法
int i = 0;
int enough = 1;
for (i = 0; i < max_resources; i++)
{
if (the_process.request[i] <= the_process.need[i] && the_process.request[i] < available[i])
enough = enough * 1;
else enough = 0;
} //检查request的值是不是小于need和available
if (enough > 0)
{

for (i = 0; i < max_resources; i++)
{
available[i] = available[i] - the_process.request[i];
the_process.allocation[i] = the_process.allocation[i] + the_process.request[i];
the_process.need[i] = the_process.need[i] - the_process.request[i];
}
}
else
{
cout << "请求资源超过宣布最大值或者资源不足，无法分配" << endl;
return false;

}

if (check_safe(available, my_process) == true)
{
cout << "此次分配成功" << endl;
return true;
}
else
{
cout << "此次寻找失败" << endl;
for (i = 0; i < max_resources; i++)
{
available[i] = available[i] + the_process.request[i];
the_process.allocation[i] = the_process.allocation[i] - the_process.request[i];
the_process.need[i] = the_process.need[i] + the_process.request[i];
}
the_process.finish = false; //安全性算法检测错误，则回档
return false;
}
}
void init(int available[max_resources], process my_process[max_process]) //初始化函数
{
int _max_need[max_resources];
int i;
int temp[max_resources] = { 0,0,0,0 };
cout << "初始化available数组值，请输入" << max_resources << "个值代表每个资源初始数目,空格隔开" << endl;
for ( i = 0; i < max_resources; i++)
{
scanf_s("%d", &available[i]);
}

for (i = 0; i < max_process; i++)
{
cout << "进程初始化" << endl;
cout << "请输入第" << i << "个进程的最大所需每个资源的值,共计" << max_resources << "个资源，用空格隔开" << endl;
for (int j = 0; j < max_resources; j++)
{

scanf_s("%d", &_max_need[j]);
}
my_process[i].set(false, _max_need, temp, _max_need,temp);
}
}
int main()
{
int _need[max_resources];
int _allocation[max_resources];

int available[max_resources];
process my_process[max_process];
int i,j;
int choice=1;
init( available, my_process);
while (true)
{
cout << " 选项\n 1：继续分配\n 2:查看当前available资源数\n其他字符：退出\n";
scanf_s("%d", &choice);
switch (choice)
{ case 1:
{
cout << "请输入本次请求分配给第i个进程的资源，格式：进程号 xx xx xx xx，空格隔开" << endl;
scanf_s("%d", &i);
for (j = 0; j < max_resources; j++)
{

scanf_s("%d", &my_process[i].request[j]);
}
if (destribute(available, my_process[i], my_process) == true)
{
cout << "此次destribute成功" << endl;
}
else cout << "此次destribute不成功" << endl;
}
break;
case 2:
{ for (i = 0; i < max_resources; i++)
cout << "第" << i << "个资源还剩" << available[i] << "个\n";
break;
}
default: break;

}

}
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
cin.get();
return 0;
}

五、 运行实例
为了便于模拟，默认是5个进程，4个公共资源
首先是available资源的初始化（如图1 ）

图1
初始化每个进程对于每个资源的max_need值

图2

开始进行资源分配：
此数据设计为可以成功的数据：

图3

图4
查看下剩余的available值

接下来测试一些非法数据：
如图，为request>need值的报错

图5
这是request>available值的时候报错:

图6
接下来再次进行分配：

可见并未通过安全性算法，显示失败
图7

六、 心得与体会
通过本次实验，我通过亲身实践实现了模拟银行家算法的实现来预防进程死锁，本次实验需要考虑很周全，我在编程的过程中出现了不少错误，由于考虑不周，刚开始总是顾此失彼，在经过系统的排查错误和对流程的分析，最终一个一个排除错误，得到正确的银行家算法的代码实现。

14