操作系统综合性实验-死锁避免银行家算法.doc

操作系统综合性实验_死锁避免银行家算法

———————————————————————————————— 作者：
———————————————————————————————— 日期：

13

个人收集整理 勿做商业用途

华 南 农 业 大 学 信 息（软 件） 学 院
《操作系统》综合性、设计性实验成绩单
开设时间: 2010 学年第 1 学期
专业

班级

学号

姓名

实 验 题 目

死锁避免-—银行家算法
自 我 评 价

这个实验主要是按照课书上银行家算法的思路写出来的。虽然功能比较简单,但是也是经过努力才编写出来的程序，实验报告也写得很认真。对我来说，它是个比较完善的程序。

教 师 评 语

评价指标：
l 题目要求完成情况 优 □ 良 □ 中 □ 差 □
l 对算法原理的理解程度 优 □ 良 □ 中 □ 差 □
l 程序设计水平 优 □ 良 □ 中 □ 差 □
l 实验报告结构清晰 优 □ 良 □ 中 □ 差 □
l 流程图及内容表述清楚 优 □ 良 □ 中 □ 差 □
l 实验总结和分析详尽 优 □ 良 □ 中 □ 差 □

成绩

教师签名

一、 需求分析
1、系统目的：通过编写和调试一个系统动态分配资源的简单模拟程序，观察死锁产生的条件，模拟死锁避免的实现，加深对死锁避免,系统安全状态等的理解,体会和了解死锁和避免死锁的具体实施方法.并采用适当的算法,有效地防止和避免死锁地发生。
2、数据:本程序开始运行时,资源全部可用，此处的资源是已经定义好的矩阵内容,运行时,随机产生新的“进程资源需求向量”。
3、本题目的简化假设是：
(1）程序运行开始时，资源全部可用.资源种类约10种，每种资源数目为1～10。
（2）不断随机产生或手工输入新的“进程资源需求向量”，并填写到最大需求矩阵。
（3)在各进程的最大需求数量范围内(因此需作是否超出范围的检验），为各进程随机生成或手工输入资源请求。经银行家算法后输出系统是否安全的信息.当一个进程的资源请求全部发完后，认为它结束。

二、 概要设计
1、 定义：利用二维数组定义好最大分配需求矩阵、已分配矩阵、现在需求矩阵，用一维数组的形式存放好现可利用矩阵。

2、 本程序共10个模块,分别如下：
（1）生成确定范围内的随机数 random_num（)
（2）初始化数据 init0_data（)
（3）进程请求 proc_require0()
(4）请求资源超过需求资源 over_need()
（5）请求资源超过可利用资源 over_avail（)
（6）资源申请成功 apply_success（)
（7）安全性检查 check_security（）
（8）银行家算法主体 banker（)
(9）显示输出 output(）
（10）主函数 main（）

3、各程序模块之间的层次(调用）关系
void banker()
｛
check_security（)
｝
int main()
{ init0_data（)；
output()；
proc_require0(）;
apply_success(over_need（）,over_avail(））
banker();
}
4、程序模块之间流程图
init0_data();
output();
proc_require0();

apply_success(over_need(),over_avail())?
banker();
output();
继续吗？
system("pause");
no
yes
yes
no

三、详细设计
1、定义变量:
int max1［5][10]/＊最大分配需求矩阵*/
int allocation1［5］［10］ /＊已分配矩阵*/
int need1[5］［10］ /＊现在需求矩阵*/
int available1［10］ /＊现可利用矩阵*/
int max[20][20]，allocation［20］［20],need[20]［20］，available［20］;
int n_proc;/＊进程数＊/
int type_src;/＊资源种类数＊/
int request[20］［20]；/*进程请求资源*/
int work[20］；/＊可供进程继续运行所需资源的向量*/
int finish［20］;/＊标识是否有足够的资源分配给进程*/
int index[20]；/＊用于记录进程顺序*/
int t=0;/*记录当前的进程数＊/
int serial_proc=0;/*当前请求进程＊/
2、初始化数据init0_data()
输入值:无
返回值：无
操作变量:max［i]［j]；allocation[i］[j］；need［i］［j];available［j];index［i］
调用模块：无
详细设计：
for(范围不超过进程数）
for(范围不超过资源种类数）
max［i］[j]=初始化分配需求矩阵
for（范围不超过进程数)
for(范围不超过资源种类数）
allocation［i］［j］=初始化分配矩阵;
for（范围不超过进程数)
for（范围不超过资源种类数）
need［i］［j］=初始化需求矩阵
for（范围不超过资源种类数)
available[j］=初始化可用矩阵
for（范围不超过进程数）
index[i]=初始化进程顺序

3、进程请求proc_require0()
输入值：无
返回值:无
操作变量:serial_proc；tmp；
调用模块：无
详细设计：
if （当前请求进程〈0或当前请求进程〉进程数）
｛
输出错误
重新调用
｝
初始化tmp
for(范围不超过资源种类数）
tmp+=need[serial_proc][j］;
if (！tmp)
｛
输出该进程处于完成状态
重新调用
｝
输出进程,各资源要求
for(范围不超过资源种类数)
输入request［serial_proc］[j]

4、请求资源超过需求资源over_need（)
输入值：无
返回值：1或0
操作变量：request［serial_proc]［j];need［serial_proc］[j]
调用模块：无
详细设计： for（范围不超过资源种类数）
if（进程请求资源数>需求资源数)
{
输出错误信息
返回1；
}
返回 0；

5、请求资源超过可利用资源over_avail（)
输入值：无
返回值：1或0
操作变量：request［serial_proc］［j];available［j]
调用模块：无
详细设计： for(范围不超过资源种类数)
if（进程请求资源数>可利用资源数）
｛
输出错误信息
返回 1;
}
返回 0；
6、资源申请成功apply_success(）
输入值:over_need（）与over_avail()的返回值
返回值：1或0
操作变量：be_need；be_avail
调用模块:无
详细设计：
if （over_need（)返回值为0且over_avail(）返回值为0)
{
返回 1;
｝
返回 0；

7、安全性检查check_security（）
输入值：无
返回值：1或0
操作变量：work[20］;index［20]；finish[20]
调用模块：无
详细设计：
定义局部变量
for（范围不超过资源种类数)
可供进程继续运行所需资源的向量=现可利用矩阵
for（范围不超过进程数）
初始化标识是否有足够的资源分配给进程
标记位清零
L2:
for(范围不超过进程数）
if(没有进行安全检查)
{
for(范围不超过资源种类数)
if(现需求矩阵〉可供进程继续运行所需资源的向量)
｛
tmp=0;
break；
}
if（!tmp）
continue;
else
｛
for（范围不超过资源种类数)
可供进程继续运行所需资源的向量+=已分配矩阵
已进行安全性检查
for(范围不超过资源种类数）
tmp+=现需求矩阵;

if（tmp)
进程顺序增加
重新调用；
}
｝
for(范围不超过进程数)
if(没有进行安全检查）
返回 0;
返回 1;

8、银行家算法主体banker（)
输入值：无
返回值：无
操作变量：available,allocation，need
调用模块：check_security（）
详细设计： {
定义临时变量
定义局部变量

for（范围不超过资源种类数）
{
保留当前的资源分配
｝

for（范围不超过资源种类数）
｛
修改available,allocation，need矩阵
｝
if（通过安全性检查)
｛
tmp=0；
for(范围不超过资源种类数)
当前需求矩阵累加
if(!tmp）
for(范围不超过资源种类数)
现可利用矩阵+=已分配矩阵；
}

else
{
for（范围不超过资源种类数）
{
还原available，allocation,need矩阵
}
｝
}

9、显示输出output（)
输入值：无
返回值:无
操作变量：无
调用模块：无
详细设计：
定义局部变量
printf(”\n安全序列输出格式:[进程号，进程数］\n\n"）;
for（范围不超过当前的进程数)
{
输出进程顺序
｝
输出矩阵文字

for（范围不超过进程数)
{
printf(” ”);
for(范围不超过资源种类数)
输出最大矩阵
for（范围不超过资源种类数）
输出已分配矩阵
for（范围不超过资源种类数）
输出需求矩阵;
if (当前请求进程)
for(范围不超过资源种类数)
输出可用矩阵
}

10、主函数main（)
输入值：无
返回值：无
操作变量：无
调用模块：init0_data（);output（);proc_require0(）；apply_success（)；banker（）;output（）;
详细设计:
输出主界面
调用init0_data（)；初始化数据模块
output(）;显示输出模块
proc_require0(）;进程请求模块
apply_success（)；请求成功模块
banker(）；银行家模块
output（)显示输出模块

四、调试分析
1、调试过程中遇到的问题是如何解决的以及对设计与实现的讨论和分析
一开始接触这个实验,我感觉到无从下手,后来经过对书本中银行家算法的研究以及上网查阅了一些资料，初步确定使用C++实现这个程序的功能。经过仔细的分析，我确定了基本模块的使用以及各个模块之间的调用关系，逐渐地构建好了程序的框架。而在调试程序的过程中,经常出现了死循环，导致程序无法运行。分析后，原来是程序少了system（"pause”）的语句.而本程序涉及的模块较多，要随时看清实参的调用以及返回值的控制，不然在运行时极容易出错。有些指令C里可以用，但C++不能运用，这又要我查阅资料解决。
2、算法的时间复杂性与改进
本程序中，初始化模块，输出模块的时间复杂度都是0（n^2)。
改进：因本人知识有限，暂时没有改进的办法
3、设计过程的经验和体会
银行家算法在课上老师有详细的讲解和讨论,书本上也有详细的流程说明、方法指导，即使原来不甚了解,做起来也不会过于困难。在做银行家算法的模拟实现死锁避免课程设计前，必须要了解书中银行算法的基本原理，银行算法和安全性算法，实践离不开理论，足够的理论是实践的基础。通过这次实验，我对银行家算法的理解又深刻了,对其操作、各方面都有了提升。
这次综合性实验，使我对C++的了解又上升了一个层次,之前我对其二维数组的内容认识还不够深刻，而现在，我已经能熟练地运用了。
4、实现过程中出现的主要问题及解决方法
开始做的时候，没有把握好程序模块之间调用的先后，一度导致程序难以运行.后来我通过了画流程图的方法，清晰明了地掌握了程序的脉络，编写起来十分顺手。
在友好度方面，进行了不断的改进，以确保用户能清晰地看清程序的运行结果,运行过程。
在这次课程设计中，我还要特别感谢孙微微老师对我的指导.

五、用户使用说明
运行文件夹中的exe文件,即可看到欢迎界面
若输入超出4的数字，将会出现错误提示(进程号越界)
若输入的请求资源超过可利用资源或超过需求资源，将会出现错误提示
若要继续则输入“y”

六、测试与运行结果

欢迎界面

请求进程后

请求资源超过可利用资源或超过需求资源

请求资源没有超过可利用资源或超过需求资源

继续操作按’y’