专业课程设计银行家算法报告.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<
cout<<"\t\t|| ||"<dl<0;
cout<<"\n安全状态!!!"<>"<<"进程"<<"("<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
#include
#include
#include
#include
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'9')
{
cout<<" 笨蛋，输错了！你输入是数字吗?！\n\n";
cout<<"请重新输入：";
break;
}
}
}while(s<'0' || s>'9');
for(int i=0；i数字
{
int t=1;
for(int j=1；j"<huzi(Available[j]);
Work[j]=Available[j]；//初始化Work[j]
}
cout<cation[i][j]=shuzi(Allocation[i][j]);
}
cout<<<" 对资源 "<=Allocation[i][j])
Need[i][j] = Max[i][j]-Allocation[i][j]；//计算还需求量
else
Need[i][j]=0;//最大需求量不大于已分派量时还需求量为0,即此类资源已足够不需再申请
}
cout<
cout<=Need[i][j]) //可用不不大于等于需求
counter=counter+1;//记数
}
if(counter==m){…
*/ //算法二：
for (j=0；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 }
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<<"==============================================================="< for (i=0；i cout<<" 资源"< cout<) //设计每行显示五种资源
{
for (j=i*5；j
cout<<"==============================================================="<l;
cout<<"\t\t =@ @="<"<对此问题我在诸多地方搜索查找均未找到满意答案,本次换用调试器才发现理解--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<<"==============================================================="<l;
cout<<"%% 如下开始为进程进行资源分派申请 %%"<n-1) //输入异常解决
{
cout< {
cout<<"进程 "<Need[k][j]) //申请不不大于需求量时出错，提示重新输入（贷款数目不容许超过需求数目）
{
cout<<"申请不不大于需要量!!!"< cout<<"您申请资源"<Available[j]) //申请不不大于可运用量， 应当阻塞等待
{
cout<<"\n没有那么多资源，当前可运用资源"<Need[k][j])； //Request[j]>Available[j]||
}

//变化Avilable、Allocation、Need值
for (j=0；jj];
}
//判断当前状态安全性
safe()；//调用安全性算法函数
if (lAllocation[k][j] = Allocation[k][j]-Request[j];
Need[k][j] = Need[k][j]+Request[j];
Work[j] = Available[j];
}
for (i=0；i<<"\n申请资源成功!!!"<