操作系统课程设计银行家算法样本.docx

《操作系统课程设计》

题目：银行家算法设计与实现

院、 系： 计算机信息与技术系
学科专业： 计算机科学与技术
学 号： B10060123
学生姓名： 徐飞
指引教师 ： 姜虹

×××06月

目录
一、绪论 1
二、需求分析 2
2.1银行家算法的描述 2
2.2银行家算法模拟系统流程图 3
2.3模拟系统用况分析 4
2.4模拟系统用况规约 4
2.4.1用况名称：创建进程 4
2.4.2用况名称：执行进程 5
三、总体设计 7
3.1系统的分层模型 7
3.2系统部署 7
3.3系统的静态模型 8
四、详细设计 9
4.1交互层设计 9
4.2交互逻辑层设计 9
4.3控制层设计 11
4.3进程层设计 12
4.4资源层设计 12
五、系统实现 14
5.1交互层的实现 14
5.2交互逻辑层的实现 15
5.3控制层的实现 18
5.3进程层的实现 21
5.4资源层的实现 22
六、测试与分析 24
6.1系统资源初始化测试 24
6.2系统资源初始状态的设置 24
6.3进程初始化测试 24
6.4进程初始化设置 25
6.5执行进程测试 25
课程设计总结 26
参考文献 27
附录A 28

一、绪论
在具备多道程序并发执行能力系统中，系统资源运用率、进程执行效率都大幅增长，但也许发生“死锁”危险。所谓死锁，是指各种进程因竞争资源而导致一种僵局，若无外力作用，这些进程都将永远不能再向前推动。
而死锁产生因素有两点：竞争资源和进程推动顺序不合法。
为了避免死锁，使得进程执行可以顺利完毕，引入银行家算法进行解决。
银行家算法是具备代表性避免死锁算法，由于该算法能用于银行系统钞票贷款发放而得名。
银行家算法包括三个方面内容：
1) 相应数据构造。
2) 银行家算法。
3) 安全性算法。
其中相应数据构造定义了银行家算法中需要使用若干数据构造，银行家算法操作数据构造觉得安全性算法提供检测现场，安全性算法则是检测现场与否出于安全态。
系统安全状态是指可以按照某种顺序，来为每个进程分派其所需资源，直至最大需求，使每个进程都可顺序完毕。若系统不存在这样一种安全序列，则称系统出于不安全状态。

二、需求分析
问题描述：银行家算法是避免死锁有效办法，为了验证银行家算法可以避免死锁，需要编写程序模仿银行家算法并加以验证。
2.1银行家算法描述
银行家算法所涉及数据构造：
1) 可运用资源向量Avaliable
它是一种vector向量，可被初始化任意长度，其中每一种元素代表一类可运用资源数目。其值随着该类资源分派和回收而动态变化。
2) 最大需求矩阵Max
这是一种n×m矩阵，她定义了系统中n个进程中每一种进程对m类资源最大需求。
3) 分派矩阵Allocation
这是一种n×m矩阵，她定义了系统中每一类资源当前已分派给每一进程资源数。
4) 需求矩阵Need
它是一种n×m矩阵，用以表达每一种进程尚需各类资源数。
以上三个矩阵间存在下述关系：
Need=Max-Allocation
银行家算法：
设Request是某一进程祈求向量。当进程发出祈求后，系统按下列环节进行检查：
1) 如果Request≤Need，则转向环节2；否则以为出错，由于她所需要资源数已超过她所宣布最大值。
2) 如果Request≤Avaliable，则转向环节3；否则表达系统中尚无足够资源，进程必要等待。
3) 系统进行试分派：
Avaliable=Avaliable-Request
Allocation=Allocation=Request
Need=Need-Request
4) 系统执行安全性检查，若系统处在安全态，则正式将资源分派给进程；若处在不安全态，则将本次分派作废，回滚到分派前状态，并告知进程等待。
安全性算法：
1) 设立两个工作向量
工作向量Work。她表达系统可提供应进程继续运营所需要各类资源数目，她具有m个元素，执行安全性算法开始时，Work=Avaliable。
Finish。她表达系统与否有足够资源分派给进程，使之运营完毕，初始状态为Finish[i]=false；当有足够资源分派给进程时，Finish[i]=true。
2) 从进程集合中找到一种能满足下列条件进程：
Finish[i]=false
Need≤Work
如找到，执行环节3，否则，执行环节4
3) 当某一进程获得资源后，可顺利执行，直至完毕，并释放出分派给她资源，故应执行：
Work= Work+ Allocation
Finish[i]=true
Go to step 2
4) 如果所有进程Finish[i]＝true，则表达系统处在安全状态；否则系统处在不安全状态。
2.2银行家算法模仿系统流程图
银行家算法模仿系统流程图如图2.1所示

图 2.1 系统流程图
2.3模仿系统用况分析
银行家算法模仿系统用况图如图2.2所示

图 2.2 模仿系统用况图
2.4模仿系统用况规约
2.4.1用况名称：创立进程
1. 简要阐明
该用况描述顾客如何通过使用模仿系统进行创立进程工作。
2. 事件流
2.1 基本流
1. 数据合法性检查
顾客选取“创立进程”选项，系统对顾客输入合法性进行检查。
2. 提示顾客输入创立进程个数
顾客输入进程个数。
3. 数据合法性检查
对顾客输入数据进行合法性检查
4. 初始化进程所需资源量
提示顾客输入进程所需资源量。
5. 数据合法性检查
对顾客输入数据进行合法性检查
2.2 备选流
备选流一：在基本流环节1中，规则检查不通过，提示输入数据不合法，请重新输入。
备选流二：在基本流环节3中，规则检查不通过，提示输入数据不合法，请重新输入。
备选流三：在基本流环节5中，规则检查不通过，提示输入数据不合法，请重新输入。
3. 用例场景
3.1 成功场景
成功初始化进程信息：基本流。
3.2 失败场景
数据合法性检查不通过：备选流一。
数据合法性检查不通过：备选流二。
数据合法性检查不通过：备选流三。
4. 特殊需求
无
5. 前置条件
顾客已初始化系统。
6. 后置条件
显示安全序列。
显示各数据构造信息。
显示输入数据有误，请重新输入。
显示系统初始状态处在不安全态，进程创立失败，并退出系统。
7. 扩展点
无
2.4.2用况名称：执行进程
1. 简要阐明
该用况描述管理员如何使用执行进程功能测试银行家算法。
2. 事件流
2.1 基本流
1. 数据合法性检查
顾客选取“执行进程”选项，系统对顾客输入合法性进行检查。
2. 提示顾客需要执行进程编号
顾客输入进程号。
3. 数据合法性检查
对顾客输入数据进行合法性检查
4. 输入进程祈求向量
顾客按照提示输入祈求向量。
5. 数据合法性检查
检查顾客输入数据合法性。
6. 返回安全序列和各数据构造
系统解决进程祈求向量，并返回安全序列和数据构造。
2.2 备选流
备选流一：在基本流环节1中，规则检查不通过，提示输入数据不合法，请重新输入。
备选流二：在基本流环节3中，规则检查不通过，提示输入数据不合法，请重新输入。
备选流三：在基本流环节5中，规则检查不通过，提示输入数据不合法，请重新输入。
备选流四：在基本流环节6中，规则检查不通过，提示输入祈求向量有问题，请进程等待。
3. 用例场景
3.1 成功场景
进程成功被分派资源：基本流。
3.2 失败场景
数据合法性检查不通过：备选流一。
数据合法性检查不通过：备选流二。
数据合法性检查不通过：备选流三。
数据不满足系统规定：备选流四。
4. 特殊需求
无
5. 前置条件
顾客已创立进程。
6. 后置条件
显示安全序列。
显示各数据构造信息。
显示输入数据有误，请重新输入。
显示系统资源局限性进程需要等待。
显示系统处在不安全态，进程需要等待。
7. 扩展点
无

三、总体设计
3.1系统分层模型

图3.1 系统分层模型图
系统分层模型如图3.1所示。
交互层：重要功能是为了与顾客进行交互，涉及系统初始化，创立各种进程，置进程祈求向量。
交互逻辑层：负责将顾客交互信息与控制层互换。
进程层：重要功能是为了创立进程，并交给控制层进行管理。
控制层：负责管理进程与资源，是整个系统核心某些，银行家算法与安全性算法均在这一层中。
资源层：重要负责管理各种资源向量或矩阵。
3.2系统布置
系统被布置在控制台运营。之因此选取控制台是由于可以让咱们开发模仿系统时候更加专注于业务，而不是花太多精力在非业务功能上。
3.3系统静态模型

图3.2 系统静态模型图
模仿系统共有3个类、4中新数据类型（其中4种新数据类型用衍形加以定义）。
1) _Resource类掌管全局资源，各种数据构造都在其中定义，目是要把操作与数据分离，便于程序设计以及维护。其中M是资源种类数，Available是可运用资源向量，Max是最大需求矩阵，Allocation是分派矩阵，Need是需求矩阵。
2) _Process类是进程类，用来实例化进程。其中Request是需求向量。可用_Process来实例化任意个进程，从而使程序扩展性、安全性以及构造都得到极大提高。
3) _Control类负责对系统既有资源以及进程进行控制。其中add_Process办法负责将进程添加到控制类中，run_Process办法就是银行家算法，而safeChecked办法就是系统安全性算法。
四、详细设计
4.1交互层设计
由于系统是被布置在控制台上，因此交互层实现比较简朴。交互层界面显示如图4.1所示。

图4.1 模仿系统选取菜单
4.2交互逻辑层设计
交互逻辑层作用是将顾客输入信息与控制层进行协作。
vector<_Process> create(_Resource &r,_Control &c)（创立进程）设计如图4.2所示。

图4.2 create函数流程图
void run(vector<_Process> &p,_Resource &r,_Control &c)（执行进程）设计如图4.3所示。

图4.3 run函数流程图
void out(vector<_Process> &p,_Resource &r,_Control &c) 设计如图4.4所示。

图4.4 out函数流程图
4.3控制层设计
_Control类设计。
1) void add_Process(_Process &p,_Resource &r)办法设计如图4.5所示。

图4.5 add_Process办法流程图
2) int run_Process(_Process &p,int n,_Resource &r)（银行家算法）设计如图4.6所示。

图4.6 银行家算法流程图
3) bool safeChecked(_Resource &r_2)（安全性算法）设计如图4.7所示

图4.7 安全性算法流程图
4.3进程层设计
类_Process设计
void init(_Resource &r)办法设计如图4.8所示。

图4.8 init办法流程图
4.4资源层设计
类_Resource设计
void init()办法设计如图4.9所示。

图4.9 init办法流程图
五、系统实现
系统实现采用C++语言，并使用Microsoft Visual Studio 作为平台进行实现。
5.1交互层实现
交互层被直接设计成main函数：
int main(){
_Resource r;
r.init();
_Control c(r);
vector<_Process> p;
bool is=false;
while(true){
int x;
cout<<endl;
cout<<"1.创立进程"<<endl;
cout<<"2.执行一种进程"<<endl;
cout<<"3.退出"<<endl;
while(true) {/*输入数据合法性检查*/
cin>>x;
if(cin.fail()){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
else{
if(x<=0)
{
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
cin.clear();
cin.sync();
break;
}
}
switch(x){
case 1:p=create(r,c),is=true;break;
case 2:if(is)run(p,r,c);else{cout<<"您尚未创立进程！"<<endl;}break;
case 3:exit(0);
default:cout<<"输入数据不合法，请重新输入！"<<endl;
}
//输出各矩阵状态
out(p,r,c);
}
return 0;
}
5.2交互逻辑层实现
1. vector<_Process> create(_Resource &r,_Control &c)（创立进程）实现。
vector<_Process> create(_Resource &r,_Control &c){
cout<<"请输入需要创立进程数目："<<endl;
int i;
while(true) { /*输入数据合法性检查*/
cin>>i;
if(cin.fail()){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
else{
if(i<=0){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
cin.clear();
cin.sync();
break;
}
}
vector<_Process> p;
//进程初始化
_Process aaa;
for(int j=0;j<i;j++){
p.push_back(aaa);
}
int x=0;
for(vector<_Process>::iterator iter=p.begin();iter!=p.end();iter++){
cout<<"P"<<x<<"初始化"<<endl;
(*iter).init(r);
x++;
}
//添加进程
for(vector<_Process>::size_type index=0;index!=p.size();index++){
c.add_Process(p[index],r);
}
//初始安全态检查
if(c.safeChecked(r)){;}
else{
cout<<"系统初始状态不安全！"<<endl;
system("pause");
exit(0);
}
return p;
}

2. void run(vector<_Process> &p,_Resource &r,_Control &c)（执行进程）实现
void run(vector<_Process> &p,_Resource &r,_Control &c){
int i;
cout<<"请输入需要执行进程号："<<endl;
while(true) { /*输入数据合法性检查*/
cin>>i;
if(cin.fail()){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
else{
if(i<0){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
cin.clear();
cin.sync();
break;
}
}
cout<<"初始化第"<<i<<"个进程祈求向量："<<endl;
//置进程资源祈求向量
for(vector<int>::size_type sz=0;sz!=p[i].Request.size();sz++){
cout<<"请输入祈求向量第"<<sz<<"个值："<<endl；
int k;
while(true){/*输入数据合法性检查*/
cin>>k;
if(cin.fail())
{
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
else{
if(k<=0){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
cin.clear();
cin.sync();
break;
}
}
p[i].Request[sz]=k;
}
c.run_Process(p[i],i,r);
}

3. void out(vector<_Process> &p,_Resource &r,_Control &c) 实现。
void out(vector<_Process> &p,_Resource &r,_Control &c){
//输出Available矩阵
cout<<"Available:"<<endl;
for(vector<int>::size_type sz=0;sz!=r.Available.size();sz++){
cout<<r.Available[sz]<<" ";
}
cout<<endl;
//输出Max矩阵
cout<<"Max:"<<endl;
for(vector<Max_row>::size_type i=0;i<r.Max.size();i++){
for(vector<int>::size_type sz=0;sz<r.Max[i].size();sz++){
cout<<r.Max[i][sz]<<" ";
}
cout<<endl;
}
//Allocation矩阵
cout<<"Allocation:"<<endl;
for(vector<Allocation_row>::size_type i=0;i<r.Allocation.size();i++){
for(vector<int>::size_type sz=0;sz<r.Allocation[i].size();sz++){
cout<<r.Allocation[i][sz]<<" ";
}
cout<<endl;
}
//输出需求矩阵
cout<<"Need:"<<endl;
for(vector<Need_row>::size_type i=0;i<r.Need.size();i++){
for(vector<int>::size_type sz=0;sz<r.Need[i].size();sz++){
cout<<r.Need[i][sz]<<" ";
}
cout<<endl;
}
}
5.3控制层实现
_Control类实现。
1. void add_Process(_Process &p,_Resource &r)办法实现。
void add_Process(_Process &p,_Resource &r){
N++; //进程数加1
//置最大需求矩阵
Max_row mr;
for(vector<int>::iterator iter=p.Request.begin();iter!=p.Request.end();iter++){
mr.push_back(*iter);
}
r.Max.push_back(mr);
//置分派矩阵
Allocation_row ar;
for(int i=0;i<r.getM();i++){
ar.push_back(0);
}
r.Allocation.push_back(ar);
//置需求矩阵
Need_row nr;
for(vector<int>::iterator iter=p.Request.begin();iter!=p.Request.end();iter++){
nr.push_back(*iter);
}
r.Need.push_back(nr);}
2. int run_Process(_Process &p,int n,_Resource &r)（银行家算法）设计如图4.6所示。
int run_Process(_Process &p,int n,_Resource &r){
//先判断Request<=Need
bool temp_1=true;
for(vector<int>::size_type index=0;index!=p.Request.size();index++){
if(p.Request[index]>r.Need[n][index]){
cout<<"祈求出错！由于进程所需要资源数已超过它所宣布最大值。"<<endl;
return 1;
}
}
//再判断Request<=Available
for(vector<int>::size_type index=0;index!=p.Request.size();index++){
if(p.Request[index]>r.Available[index])
{
cout<<"系统中尚无足够资源，P"<<n<<"必要等待！"<<endl;
return 2;
}
}
//进行试分派
_Resource r_1=r;
vector<int>::iterator iter_2=r_1.Available.begin();
vector<int>::iterator iter_3=r_1.Allocation[n].begin();
vector<int>::iterator iter_4=r_1.Need[n].begin();
for(vector<int>::iterator iter_1=p.Request.begin();iter_1!=p.Request.end();iter_1++){
//Available:=Available-Request
*iter_2=*iter_2-*iter_1;
//Allocation:=Allocation+Request
*iter_3=*iter_3+*iter_1;
//Need:=Need-Request
*iter_4=*iter_4-*iter_1;
//迭代器移向下一种元素
iter_2++;
iter_3++;
iter_4++;
}
//执行安全性检查
if(safeChecked(r_1)){
r=r_1;
//判断此进程与否获得所有资源，若获得，则让其执行完毕后释放
bool temp=true;
for(int i=0;i<r.getM();i++)
{
if(r.Need[n][i]!=0){
temp=false;
break;
}
}
if(temp){
//置最大需求矩阵
for(int i=0;i<r.getM();i++){
r.Max[n][i]=0;
}
//且置可运用资源向量
for(int i=0;i<r.getM();i++){
r.Available[i]+=r.Allocation[n][i];
r.Allocation[n][i]=0;
}
cout<<"进程P"<<n<<"执行完毕，已释放资源！"<<endl;
}
return 0;
}
else{
cout<<"系统不处在安全态，P"<<n<<"进程需要等待"<<endl;
return 3;
}
}
3. bool safeChecked(_Resource &r_2)（安全性算法）实现。
bool _Control::safeChecked(_Resource &r_2){
vector<int> Work;
//初始化工作向量
for(vector<int>::iterator iter=r_2.Available.begin();iter!=r_2.Available.end();iter++){
Work.push_back(*iter);
}
vector<bool> Finish;
for(vector<Need_row>::iterator iter=r_2.Need.begin();iter!=r_2.Need.end();iter++){
Finish.push_back(false);
}
//找出Finish[i]=false且Need<=Work项
step2:
for(vector<int>::size_type i=0;i!=r_2.Need.size();i++){
if(!Finish[i]){
bool temp=false;
for(vector<int>::size_type index=0;index!=Work.size();index++){
if(r_2.Need[i][index]<=Work[index]){
temp=true;
}
else{
temp=false;
break;
}
}
if(temp){
vector<int>::iterator iter_2=r_2.Allocation[i].begin();
for(vector<int>::iterator iter_1=Work.begin();iter_1!=Work.end();iter_1++){
*iter_1=*iter_1+*iter_2;
iter_2++;
}
cout<<"P"<<i<<" ";
Finish[i]=true;
goto step2; //本来不应当使用goto语句，但由于在此使用goto语句更显以便，故破例用之
}
}
}
//判断所有进程Finish与否都为true，是则返回true，否则返回false
for(vector<bool>::size_type index=0;index!=Finish.size();index++){
if(Finish[index]);
else
return false;
}
return true;
}
5.3进程层实现
类_Process设计
void init(_Resource &r)办法实现。
void init(_Resource &r){
for(int i=0;i<r.getM();i++){
int temp;
while(true){ /*输入数据合法性检查*/
cout<<"请输入第"<<i+1<<"类资源需求量："<<endl;
cin>>temp;
if(cin.fail()){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
else{
if(temp<=0){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
cin.clear();
cin.sync();
break;
}
}
Request.push_back(temp);
}
}
5.4资源层实现
类_Resource设计
void init()办法实现。
void _Resource::init(){
while(true)/*输入数据合法性检查*/{
cout<<"请初始化系统资源种类数："<<endl;
cin>>M;
if(cin.fail()){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
else{
if(M<=0){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
cin.clear();
cin.sync();
break;
}
}
for(int i=0;i<M;i++)
{
int temp;
while(true){/*输入数据合法性检查*/
cout<<"请初始化系统中第"<<i+1<<"类资源数目："<<endl;
cin>>temp;
if(cin.fail()){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
else{
if(temp<=0){
cout<<"您输入数据不合法，请重新输入！"<<endl;
cin.clear();
cin.sync();
continue;
}
cin.clear();
cin.sync();
break;
}
}
Available.push_back(temp);
}
}
六、测试与分析
本测试均采用黑盒测试
6.1系统资源初始化测试
测试用例
预期成果
实际成果
请输入资源种类数：任意非数字字符
1.应提示“输入数据不和法，请重新输入！”

请输入资源种类数：负整数
1.应提示“输入数据不和法，请重新输入！”

6.2系统资源初始状态设立
Available={7,5,3}详细设立如图6.1所示。

图6.1 初始资源设立
6.3进程初始化测试
测试用例
预期成果
实际成果
请输入你所需要创立进程数：3
1.不应提示错误信息

初始化各类资源需求量P0Request={4,4,4}
P1Request={1,1,1}
P2Request={1,1,1}
1. 应提示“系统初始状态不安全！”
2. 提示“按任意键退出系统…”

6.4进程初始化设立
P0Request={1,2,3}
P1Request={1,2,2}
P2Request={1,2,2}
6.5执行进程测试
测试用例
预期成果
实际成果
请输入你所需要执行进程号：0并置Request={4,4,4}
1.应提示祈求出错信息，所需资源超过其所宣布最大值

请输入你所需要执行进程号：1并置Request={1,1,1}
1. 应直接输出安全序列
2. 输出各数据构造现状

请输入你所需要执行进程号：0并置Request={1,2,3}
1. 应提示系统资源局限性，P0进程需等待
2. 输出各数据构造现状

请输入你所需要执行进程号：0并置Request={1,2,2}
1. 应提示系统处在不安全态，P0进程需等待
2. 输出各数据构造现状

请输入你所需要执行进程号：1并置Request={0,1,1}
1. 输出安全序列
2. 提示进程P1执行完毕并释放资源
3. 输出各数据构造现状

课程设计总结
在这次课程设计中，我发现大多数状况下咱们在做一种项目时，并不是一开始就具备完毕这项项目所有知识。这就规定咱们学会如何去迅速学会做项目所需要所有知识。遇到有些不会解决，我会上网去查，查某些对象、容器用法，如vector等容器。此前我对这些对象或容器用法并不是太熟悉，但当前我不但掌握了她们用法，更重要是我学会了如何去学习，然后迅速地应用到我所需要项目当中。
在做这个银行家算法模仿系统时，我把它当作了一种产品去做，因此每个细节考虑虽不完全，但也周到。但这并不能阐明什么，由于诸多软件都是通过升级方式来弥补自身缺陷，我银行家算法模仿系统也是如此。在使用之中发现问题后再去积极修改问题，使得软件越来越完善。并且只有这样才是软件开发必经之路，由于没有什么事物毕生下来就是完美，都是在通过追求卓越过程中完善自己，继而达到巅峰。
在这次课程设计中我还领悟了一种重大问题：在开发一种软件过程中，把整个系统框架精确描述出来是非常重要。由于咱们背面编码式样在整个系统框架基本之上进行，如果系统框架在搭建时候浮现了模块冲突，那会影响整个软件开发进度，最后就会引起软件危机。而这是咱们所不但愿看到。因此，在软件开发之前，一定要详细讨论整个系统框架，保证合理状况下再进行下一步工作，严格把开