专业课程设计银行家算法报告.doc

《操作系统》课程设计

题 目
解决机调度模仿设计——短作业先调度、先来先服务调度、最高响应比调度算法
专 业

班 级

学 号

姓 名

指引教师

年

月

日

目 录
1、概述 1
1.1、设计目 1
1.2、设计内容 1
1.3、开发环境 1
1.4、任务分派 1
2、需求分析 2
2.1、死锁概念： 2
2.2、关于死锁某些结论： 2
2.3、资源分类： 2
2.4、产生死锁四个必要条件： 3
2.5、死锁解决方案 3
2.5.1 产生死锁例子 3
2.5.2死锁防止: 4
2.6．安全状态与不安全状态 5
3、数据构造设计 5
3.1、定义全局变量 5
3.2、函数声明 5
3.3、主函数构造 6
4、算法实现 7
4.1、初始化 7
4.2、银行家算法 7
4.3、安全性检查算法 7
4.4、程序模块划分 8
4.5 程序运营成果显示 9
4.6、各算法流程图 11
4.7、源程序清单 12
5、心得与体会： 22
6、参照文献 22

1、概述 
1.1、设计目
（1）理解多道程序系统中，各种进程并发执行资源分派。
（2）掌握死锁产生因素、产生死锁必要条件和解决死锁基本办法。
（3）掌握防止死锁办法，系统安全状态基本概念。
（4）掌握银行家算法，理解资源在进程并发执行中资源分派方略。
（5）理解死锁避免在当前计算机系统不常使用因素。
1.2、设计内容
运用银行家算法来实现资源分派。先对顾客提出祈求进行合法性检查，再进行预分派，运用安全性检查算法进行安全性检查。
1.3、开发环境
 操作系统
编译环境
生成文献
Windows7
Visual C++6.0
Bank.exe
Windows7
Code blocks 10.05
Bank.exe
源文献：Bank.cpp
 1.4、任务分派
设计人员
设计任务
刘新宇
负责重要代码编写
丁正宁
负责程序意见提取和进度安排
谭琼斐
课程设计报告重要书写
王正香
心得与体会书写

2、需求分析
2.1、死锁概念：
在多道程序系统中，虽可借助于各种进程并发执行，来改进系统资源运用率，提高系统吞吐量，但也许发生一种危险━━死锁。所谓死锁(Deadlock),是指各种进程在运营中因争夺资源而导致一种僵局(Deadly_Embrace),当进程处在这种僵持状态时，若无外力作用，它们都将无法再向前推动。一组进程中，每个进程都无限等待被该组进程中另一进程所占有资源，因而永远无法得到资源，这种现象称为进程死锁，这一组进程就称为死锁进程。

2.2、关于死锁某些结论：
a 参加死锁进程至少是两个（两个以上进程才会浮现死锁）
b 参加死锁进程至少有两个已经占有资源
c 参加死锁所有进程都在等待资源
d 参加死锁进程是当前系统中所有进程子集
注：如果死锁发生，会挥霍大量系统资源，甚至导致系统崩溃。

2.3、资源分类：
永久性资源：
可以被各种进程多次使用（可再用资源）
a 可抢占资源
b 不可抢占资源
暂时性资源：只可使用一次资源；如信号量,中断信号，同步信号等（可消耗性资源）
　　　　　　“申请—分派—使用—释放”模式

2.4、产生死锁四个必要条件：
1、互斥使用（资源独占）
一种资源每次只能给一种进程使用
2、不可强占（不可剥夺）
资源申请者不能强行从资源占有者手中夺取资源，资源只能由占有者自愿释放
3、祈求和保持（某些分派，占有申请）
一种进程在申请新资源同步保持对原有资源占有（只有这样才是动态申请，动态分派）
4、循环等待
存在一种进程等待队列
{P1 ，P2 ，… ，Pn}，
其中P1等待P2占有资源，P2等待P3占有资源，…，Pn等待P1占有资源，形成一种进程等待环路
2.5、死锁解决方案
2.5.1 产生死锁例子
  申请不同类型资源产生死锁
P1：
…
申请打印机
申请扫描仪
使用
释放打印机
释放扫描仪
…
P2：
…
申请扫描仪
申请打印机
使用
释放打印机
释放扫描仪
…
申请同类资源产生死锁（如内存）
设有资源R，R有m个分派单位，由n个进程P1,P2,…,Pn（n > m）共享。假设每个进程对R申请和释放符合下列原则：
* 一次只能申请一种单位
* 满足总申请后才干使用
* 使用完后一次性释放
m=2，n=3
资源分派不当导致死锁产生

2.5.2死锁防止：
定义:在系统设计时拟定资源分派算法，保证不发生死锁。详细做法是破坏产生死锁四个必要条件之一
①破坏“不可剥夺”条件
在容许进程动态申请资源前提下规定，一种进程在申请新资源不能及时得到满足而变为等待状态之前，必要释放已占有所有资源，若需要再重新申请
②破坏“祈求和保持”条件
规定每个进程在运营前必要一次性申请它所规定所有资源，且仅当该进程所要资源均可满足时才予以一次性分派
③破坏“循环等待”条件
采用资源有序分派法：
把系统中所有资源编号，进程在申请资源时必要严格按资源编号递增顺序进行，否则操作系统不予分派。

2.6．安全状态与不安全状态
安全状态： 如果存在一种由系统中所有进程构成安全序列P1，…Pn，则系统处在安全状态。一种进程序列{P1，…，Pn}是安全，如果对于每一种进程Pi(1≤i≤n），它后来尚需要资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和，系统处在安全状态 (安全状态一定是没有死锁发生)
不安全状态:不存在一种安全序列，不安全状态一定导致死锁。
 3、数据构造设计
3.1、定义全局变量
const int x=50,y=100；//定义常量，便于修改
int Available[x]；//各种资源可运用数量
int Allocation[y][y]；//各进程当前已分派资源数量
int Max[y][y]；//各进程对各类资源最大需求数
int Need[y][y]；//还需求矩阵
int Request[x]；//申请各类资源数量
int Work[x]；//工作向量，表达系统可提供应进程运营所需各类资源数量
int Finish[y]；//表达系统与否有足够资源分派给进程，0为否，1为是
int p[y]；//存储安全序列
int i,j；//全局变量，重要用于循环语句中
int n,m；//n为进程数量,m为资源种类数
int l=0,counter=0;
3.2、函数声明
int shuzi(int sz)；//数字判断函数
void chushihua()；//系统初始化函数
void safe()；//安全性算法函数
void bank()；//银行家算法函数
void showdata()；//函数showdata,输出当前资源分派状况
void sign()；//签名函数
3.3、主函数构造
int main()
{
system("color 06f")；//设立当前窗口背景色和前景色 0 = 黑色 8 = 灰色
cout<<endl<<endl;
cout<<"\t\t================================================"<<endl;
cout<<"\t\t|| ||"<<endl;
cout<<"\t\t|| 模仿银行家算法 ||"<<endl;
cout<<"\t\t|| ||"<<endl;
cout<<"\t\t|| 作者：lxy ||"<<endl;
cout<<"\t\t|| ||"<<endl;
cout<<"\t\t================================================"<<endl<<endl<<endl
<<endl;
chushihua()；//初始化函数调用
cout<<endl<<endl;
showdata()；//输出初始化后状态
//===判断当前状态安全性===
safe()；//安全性算法函数调用
if (l<n)
{
cout<<"\n当前状态不安全，无法申请,程序退出!!!!!"<<endl;
cout<<endl;
system("pause");
sign()；//调用签名函数
return 0；// break;
}
else
{
int i;
l=0;
cout<<"\n安全状态!!!"<<endl;
cout<<"安全序列为：";
cout<<endl<<"进程"<<"("<<p[0]<<")"；//输出安全序列，考虑显示格式，先输出第一种
for (i=1；i<n；i++)
{
cout<<"==>>"<<"进程"<<"("<<p[i]<<")";
}
for (i=0；i<n；i++) Finish[i]=0；//所有进程置为未分派状态
cout<<endl<<endl;
}

bank()；//银行家算法函数调用
return 0;
}
4、算法实现
4.1、初始化
 调用函数 chushihua()，输入进程数量，资源种类，各资源可用数量，各进程已分派、最大需求各资源数量等。
4.2、银行家算法
调用bank()函数，输入顾客祈求三元组（I，J，K），为进程I申请K个J类资源。
4.3、安全性检查算法
 调用函数safe()检查当前资源分派状态。 
（1）设立两个暂时变量。
FINISH[N]记录进程模仿执行结束状态，初值为0，如果可以模仿执行结束，则可设为1，也可设为其他非零值以表达执行先后顺序。WORK[M]记录模仿执行中资源回收状况，初值为AVAILABLE[M]值。
（2）在进程中查找符合如下条件进程。
条件1：FINISH[I]=0
条件2：NEED[I][J]〈=WORK[J]
（3）如果查找成功则进行资源模仿回收，语句如下：
WORK[J]=WORK[J]+ALLOCATION[I][J]；
FINISH[I]=1 或查找到顺序号；
（4）如果查找不成功，则检查所有进程FINISH[]，如果有一种为0，则系统不为0，返回不成功标志。否则返回成功标志。
4.4、程序模块划分
本程序共有如下六个模块：
4.4.1、字符判断模块：判断输入字符与否为数字，如果不是则提示出错并重新输入，重要解决输入为非数字时程序浮现运营错误现象。此模块功能由数字判断函数（ int shuzi(int sz)；）实现。
4.4.2、程序初始化模块：用于程序开始进行初始化输入数据：进程数量、资源种类、各种资源可运用数量、各进程各种资源已分派数量、各进程对各类资源最大需求数等。此模块功能在系统初始化函数（void chushihua()；）中实现。
4.4.3、当前安全性检查模块：用于判断当前状态安全性，依照不同地方调用提示解决不同，在安全性算函数（void safe()；）中实现。
4.4.4、银行家算法模块：进行银行家算法模仿实现模块，调用其她各个模块进行银行家算法模仿过程，在银行家算法函数（void bank();）中实现。
4.4.5、显示分派模块：显示当前资源分派详细状况，涉及：各种资源总数量(all)、系统当前各种资源可用数量、各进程已经得到资源数量、各进程还需要资源量，在显示分派状况函数（void showdata()；）中实现。
4.4.6、签名模块：用于程序结束时显示程序版权声明签名等，在签名函数（void sign()；）中实现。
4.5 程序运营成果显示

4.6、各算法流程图
开始
清除所有进程“能运营完毕”标志
系统剩余资源数与“能运营完”标志为0进程尚需资源数比较，找出一种系统能满足规定进程。
对申请者预分派
找到?
设立该进程“能运营完”标志并假设它归还所有资源。
检查与否有“能运营完”标志尚未设立进程。
有?
分派不安全
不能分派
Y
分派安全
进行实际分派
N
结束

4.7、源程序清单
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
using namespace std;

//===定义全局变量===
const int x=50,y=100；//定义常量，便于修改
int Available[x]；//各种资源可运用数量
int Allocation[y][y]；//各进程当前已分派资源数量
int Max[y][y]；//各进程对各类资源最大需求数
int Need[y][y]；//还需求矩阵
int Request[x]；//申请各类资源数量
int Work[x]；//工作向量，表达系统可提供应进程继续运营所需各类资源数量
int Finish[y]；//表达系统与否有足够资源分派给进程，0为否，非0为是
int p[y]；//存储安全序列
int i,j;
int n,m；//n为进程数量,m为资源种类数
int l=0,counter=0;

//===数字判断函数===
int shuzi(int sz) //输入数据并判断与否为数字
{
char *temp;
temp=new char；//暂时指针，存储输入字符
int len；//存储取字符长度
sz=0 ；//清零
char s；//
do //输入赌注，只能输入数字
{
cin>>temp;
len=strlen(temp)；//取字符长度
for(int i=0；i<len；i++)
{
s= *(temp+i);
if(s<'0' || s>'9')
{
cout<<" 笨蛋，输错了！你输入是数字吗?！\n\n";
cout<<"请重新输入：";
break;
}
}
}while(s<'0' || s>'9');
for(int i=0；i<len；i++) //输入字符串转化为整形数字
{
int t=1;
for(int j=1；j<len-i；j++) t*=10;
sz+=(*(temp+i)-48)*t;
}
return sz;
}
//===系统初始化函数===
void chushihua()
{
//===系统初始化输入===
cout<<"%% 程序开始，系统初始化输入 %%"<<endl；//<<endl
cout<<"==============================================================="<<endl<<endl;
cout<<"请输入进程数量：";//从此开始输入关于数据
n=shuzi(n);
cout<<"请输入资源种类数：";
m=shuzi(m);
cout<<endl<<endl<<"请输入各种资源可运用数量( "<<m<<" 种)："<<endl;
cout<<endl;
for (j=0；j<m；j++)
{
cout<<" 输入资源 "<<j<<" 可运用数量Available["<<j<<"]：";
Available[j]=shuzi(Available[j]);
Work[j]=Available[j]；//初始化Work[j]
}
cout<<endl;
cout<<"请输入各进程当前已分派资源数量Allocation["<<n<<"]["<<m<<"]："<<endl<<endl;
for (i=0；i<n；i++)
{
for (j=0；j<m；j++)
{
cout<<" 请输入进程 "<<i<<" 当前已分派资源 "<<j<<" 数量：";
Allocation[i][j]=shuzi(Allocation[i][j]);
}
cout<<endl;
Finish[i]=0;//初始化Finish[i]
}
cout<<endl<<endl;
cout<<"请输入各进程对各类资源最大需求数Max["<<n<<"]["<<m<<"]："<<endl<<endl;
for (i=0；i<n；i++)
{
for (j=0；j<m；j++)
{
cout<<" 请输入进程 "<<i<<" 对资源 "<<j<<" 最大需求数：";
Max[i][j]=shuzi(Max[i][j]);
if(Max[i][j]>=Allocation[i][j])
Need[i][j] = Max[i][j]-Allocation[i][j]；//计算还需求量
else
Need[i][j]=0;//最大需求量不大于已分派量时还需求量为0,即此类资源已足够不需再申请
}
cout<<endl;
}
cout<<endl<<"%% 初始化完毕！%%"<<endl;
}
//===安全性算法函数===
void safe()
{
l=0;
for (i=0；i<n;) //i++
{
if (Finish[i]==0) //寻找Finish[i]==0进程 条件一
{
counter=0；//记数器
/* 算法一：
for (j=0；j<m；j++){
if (Work[j]>=Need[i][j]) //可用不不大于等于需求
counter=counter+1;//记数
}
if(counter==m){…
*/ //算法二：
for (j=0；j<m；j++)
if (Work[j]>=Need[i][j])；//可用不不大于等于需求
else
{
counter=1;
break;
}
if(counter!=1) //进程每类资源量都符合条件Work[j]>=Need[i][j] 条件二
{
p[l]=i；//存储安全序列
Finish[i]=1；//标志为可分派
for (j=0；j<m；j++)
{
Work[j]=Work[j]+Allocation[i][j]；//释放资源
}
l=l+1；//记数,当L=N时阐明满足安全序列,即都符合条件Work[j]>=Need[i][j]
i= -1；//从第一种进程开始继续寻找满足条件一二进程
}
}
i++；//for循环继续寻找
}
}
//===显示分派状况函数 ===
void showdata() //函数showdata,输出当前资源分派状况
{
int i,j；//局部变量
int All[y]；//各种资源总数量
int l2；//局部变量 l1,

cout<<"==============================================================="<<endl<<endl;
cout<<"%% 系统当前状态如下：%%"<<endl<<endl;
cout<<"%% 各种资源总数量(all):"<<endl;
for (j=0；j<m；j++)
{
cout<<" 资源"<<j<<"：";
All[j]=Available[j]；//初始化 先赋值加上可运用量
for (i=0；i<n；i++)
{
All[j]+=Allocation[i][j]；//再加上每个进程已分派量计算J类资源总量
}
cout<<All[j]<<" ";
if ((j+1)%5==0 ) cout<<endl；//每行显示五个 && j!=0
}
cout<<endl<<endl;

cout<<"%% 系统当前各种资源可用数为(available):"<<endl;
for (j=0；j<m；j++)
{
cout<<" 资源"<<j<<"："<<Available[j]<<" ";
if((j+1)%5==0) cout<<endl；//每行最多显示五个 && j!=0
}
cout<<endl<<endl;

cout<<"%% 各进程已经得到资源量(allocation)："<<endl;
// l1=0；//归零
for(i=0；i<=m/5；i++) //设计每行最多显示五种资源
{
for (j=i*5；j<i*5+5 && j<m；j++) cout<<" 资源"<<j;
cout<<endl;
for(l2=0；l2<n；l2++)
{
cout<<"进程"<<l2<<":";
for (j=i*5；j<i*5+5 && j<m；j++) cout<<Allocation[l2][j]<<" ";
cout<<endl;
}
}
cout<<endl;
cout<<"%% 各进程还需要资源量(need):"<<endl;
//l1=0;
for(i=0；i<=m/5；i++) //设计每行显示五种资源
{
for (j=i*5；j<i*5+5 && j<m；j++)cout<<" 资源"<<j;
cout<<endl;
for(l2=0；l2<n；l2++)
{
cout<<"进程"<<l2<<":";
for (j=i*5；j<i*5+5 && j<m；j++)cout<<Need[l2][j]<<" ";
cout<<endl;
}
}

cout<<endl;
cout<<"==============================================================="<<endl;
cout<<endl;
system("pause")；// 暂停
}
//===签名函数 ===
void sign()
{
system("cls")；// 清屏
cout<<endl<<endl<<endl<<endl<<endl<<endl;
cout<<"\t\t ========================================="<<endl;
cout<<"\t\t =@ @="<<endl;
cout<<"\t\t =@ 本程序由刘新宇制作 @="<<endl;
cout<<"\t\t =@ 谢谢你使用 @="<<endl;
cout<<"\t\t =@ 版权没有，随便复制 @="<<endl;
cout<<"\t\t =@ @="<<endl;
cout<<"\t\t =@ 衡阳师院 12.5 @="<<endl;
cout<<"\t\t =@ @="<<endl;
cout<<"\t\t ========================================="<<endl;
cout<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl<<endl;

// getch()；//等待键盘输入，不返回任何值，用于设立程序运营界面
system("pause");//暂停 比较两种方式
/* 通过在不同编辑器中调试发现,不同调试器对函数执行顺序有差别
如在此处使用 getch() 和 system("pause") 函数时,在visual c++6.0中先执行此函数再显示,
而在dev-c++ 中则按顺序执行
对此问题我在诸多地方搜索查找均未找到满意答案,本次换用调试器才发现理解--4.29
本次调试格式时，将换行命令 "\n" 改为 endl 时，发现 system("pause") 函数执行变为顺序
执行，由此领悟到 "\n" 命令和system("pause")调用了同样系统函数，在调用顺序上system("pause")
优先因此它就先执行了
查找了一下有关协助：
在OSTREAM.H中有这样一种inline函数：
inline _CRTIMP ostream& __cdecl endl(ostream& _outs) { return _outs << '\n' << flush；}
也就是说
endl= return _outs << '\n' << flush;
endl除了写'\n'进外，还调用flush函数，刷新缓冲区，把缓冲区里数据写入文献或屏幕，
如果考虑效率就用'\n' */
cout<<"\t\t\t ";
}

//===银行家算法函数===
void bank()
{
cout<<"==============================================================="<<endl<<endl;
cout<<"%% 如下开始为进程进行资源分派申请 %%"<<endl<<endl;
//===申请资源===
int k=0;//用于输入进程编号
bool r=false；// 初值为假，输入Y继续申请则置为真
do
{
//输入祈求
cout<<"请输入申请资源进程编号(输入0--"<<n-1<<"之间)：";
k=shuzi(k);
cout<<endl;
while(k>n-1) //输入异常解决
{
cout<<endl<<"您输入了错误进程号，请重新输入!"<<endl;
cout<<endl<<"请输入申请资源进程编号(输入0--"<<n-1<<"之间)：";
k=shuzi(k);
cout<<endl;
}
cout<<endl<<"请输入该进程申请各类资源数量："<<endl;
for (j=0；j<m；j++)
{
do //do……while 循环判断申请输入状况
{
cout<<"进程 "<<k<<" 申请资源["<<j<<"]数量:";
Request[j]=shuzi(Request[j]);
cout<<endl;
if(Request[j]>Need[k][j]) //申请不不大于需求量时出错，提示重新输入（贷款数目不容许超过需求数目）
{
cout<<"申请不不大于需要量!!!"<<endl;
cout<<"您申请资源"<<j<<"数量为"<<Request[j]<<",不不大于进程"<<k<<"对该资源需求量"<<Need[k][j]<<"。"<<endl;
cout<<"请重新输入!!!"<<endl;
}
else //先判断与否申请不不大于需求量，再判断与否申请不不大于可运用量
if(Request[j]>Available[j]) //申请不不大于可运用量， 应当阻塞等待
{
cout<<"\n没有那么多资源，当前可运用资源"<<j<<"数量为"<<Available[j]<<",本次申请不成功，进程等待!!!"<<endl;
Finish[k]=0；//该进程等待
goto ppp；//goto语句 跳转，结束本次申请
}
}
while(Request[j]>Need[k][j])； //Request[j]>Available[j]||
}

//变化Avilable、Allocation、Need值
for (j=0；j<m；j++)
{
Available[j] = Available[j]-Request[j];
Allocation[k][j] = Allocation[k][j]+Request[j];
Need[k][j] = Need[k][j]-Request[j];
Work[j] = Available[j];
}
//判断当前状态安全性
safe()；//调用安全性算法函数
if (l<n)
{
l=0;
cout<<"\n当前状态不安全,不予分派!!!!!!"<<endl;
//恢复数据
for (j=0；j<m；j++)
{
Available[j] = Available[j]+Request[j];
Allocation[k][j] = Allocation[k][j]-Request[j];
Need[k][j] = Need[k][j]+Request[j];
Work[j] = Available[j];
}
for (i=0；i<n；i++)
Finish[i]=0；//进程置为未分派状态
}
else
{
l=0;
cout<<"\n申请资源成功!!!"<<endl;
//===========================================
/*
//如果该进程所有需要资源都已申请到，即NEED[k][j]均为零，则进程可以执行，执行完后需释放其所有拥有资源

//算法一：
for(j=0;j<m;j++) if(Need[k][j]==0) l=l+1;
if(l==m){ //此处借用 l 做下计数器
for (j=0;j<m;j++