操作系统课设银行家算法.docx

操作系统课设银行家算法.docx

《操作系统课设银行家算法.docx》由会员分享，可在线阅读，更多相关《操作系统课设银行家算法.docx（17页珍藏版）》请在冰点文库上搜索。

操作系统课设银行家算法

《计算机操作系统》

课程设计报告

题目：

银行家算法设计与实现

专业：

软件工程

班级：

09级

（2）班

姓名：

XXX

学号：

XXX

指导老师：

XXX

完成时间：

2012年2月20日

目录

1、课设题目要求

2、算法设计思路

3、主要数据结构及其说明

4、程序流程图

5、源程序代码

6、结果及数据分析

7、实验心得

8、参考资料

一、课设题目要求

模拟一个银行家算法，要求如下：

输入：

1.系统中各类资源表

2.每个进程需要各类资源总数系统分配给各个进程各类资源数

输出：

1.判断T0时刻的安全性2.如果系统是安全的，任意给出某个进程的一个资源请求方式并判断系统能否接受此请求，如果可以接受，其输出全部安全序列，反之，不予分配。

二、算法设计思路

银行家算法是一种最具代表性的避免死锁的算法。

要解释银行家算法，必须先解释操作系统的安全状态和不安全状态。

安全状态：

如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。

安全状态一定没有死锁发生。

不安全状态：

不存在一个安全序列。

不安全状态不一定导致死锁。

安全序列：

一个进程序列{P1，…，Pn}是安全的，如果对于每个进程Pi（0≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj（j＜i）当前占有资源量之和。

先对系统从源文件中读取的数据进行安全性判断，然后对用户提出的请求进行合法性检查，即检查请求的是不大于需要的，不大于系统可利用的资源。

若请求合法，则进行试分配，最后对试分配状态调用安全性算法进行安全性检查。

若安全，则分配，否则，不分配，恢复原来状态，拒绝申请。

三、主要数据结构及其说明

进程数i、M

资源种类数j、N

最大需求矩阵intMax[i][j];

分配矩阵intAllocation[i][j];

需求矩阵intNeed[i][j]=Max[i][j]-Allocation[i][j];

工作向量intWork[N];

可利用资源矩阵intAvailable[N];

进程的数目intn_pro=0;

标记安全序列intflag[M]={-1};

安全序列的个数intw=0;

表示系统是否有足够的资源分配给进程boolfinish[M];

安全性检查算法

ØSafe（）函数

只要求出了一种安全序列就可以说明系统是处于安全状态的，故：

1设置了两个向量：

工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，在执行安全性算法开始时，Work=Available。

Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。

开始时令Finish[i]=false，当有足够的资源分配给进程时，再令Finish[i]=1。

2在进程中查找符合以下条件的进程：

条件1：

Finish[i]=0;

条件2：

Need[i][j]<=Work[j];

若找到，则执行步骤③，否则，执行步骤④

3当进程获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

Work[j]+=Allocation[i][j];

Finish[i]=true;

gotostep2;

4如果所有的Finish[i]=true，则表示系统处于安全状态，否则，处于不安全状态。

ØSafe1（intflag[],intn,intt）函数

用于输出所有的安全序列，使用了回溯法。

ØRequest（）函数

用于进程请求资源。

输入发出请求的进程号i，请求的资源数Request[i][j]，系统按银行家算法进行检查：

①所请求的资源小于等于所需要的资源，否则分配不合理，不予分配；②所请求的资源小于等于系统可利用资源，否则分配不合理，不予分配；③假设可为该进程分配资源，安全性检查，若有安全序列，分配资源，否则系统处于不安全状态，不予分配

四、程序流程图

整体流程图

判断系统的安全性Safe（）

五、源程序代码

#include

#include

#include

#defineM10//最大进程数

#defineN3//系统所拥有的资源类型

intMax[M][N];//进程对各类资源的最大需求

intAllocation[M][N];//系统已为进程所分配的各类资源数

intNeed[M][N];//运行进程尚需的各类资源数

intWork[N];//运行进程时系统所拥有的资源数

boolfinish[M];//表示系统是否有足够的资源分配给进程

intAvailable[N];//系统可利用的资源数

intn_pro=0;//进程的数目

intflag[M]={-1};//用于标记安全序列

intReadfile（）;//从磁盘读文件

intSafe1（intflag[],intn,intt）;//输出所有安全状态

voidshow（）;

intSafe（）;//判断系统是否处于安全状态

intRequest（）;//请求资源分配函数

voidshow（）

{

printf（"\t%-9s\t%-9s\t%-9s\n","MAX","Allocation","Need"）;

printf（"\tABC\tABC\tABC\n"）;

for（inti=0;i

{

printf（"p%d\t%d%4d%4d\t",i,Max[i][0],Max[i][1],Max[i][2]）;

printf（"%d%4d%4d\t",Allocation[i][0],Allocation[i][1],Allocation[i][2]）;

printf（"%d%4d%4d\n",Need[i][0],Need[i][1],Need[i][2]）;

}

printf（"系统可利用资源数:

\n"）;

printf（"\tA\tB\tC\n"）;

printf（"\t%d\t%d\t%d\n",Available[0],Available[1],Available[2]）;

}

intReadfile（）//从磁盘读文件

{

inti=0,j=0;//i表进程，j表资源

ifstreaminFile;//文件

inFile.open（"test.txt"）;//打开输入文件，按照规定的格式提取线程等信息

for（j=0;j

inFile>>Available[j];

inFile.get（）;

printf（"系统最大资源数:

\n"）;

printf（"\tA\tB\tC\n"）;

printf（"\t%d\t%d\t%d\n",Available[0],Available[1],Available[2]）;

inFile>>n_pro;

inFile.get（）;

printf（"当前进程的数目:

%d\n",n_pro）;

while（i

{

for（j=0;j

inFile>>Max[i][j];

for（j=0;j

inFile>>Allocation[i][j];

for（j=0;j

{

Need[i][j]=Max[i][j]-Allocation[i][j];

Available[j]-=Allocation[i][j];

}

i++;

}

for（j=0;j

Work[j]=Available[j];

printf（"显示初始化资源分配表:

\n"）;

show（）;

printf（"\n"）;

return0;

}

intSafe（）//判断系统是否是安全的

{

inttempn=n_pro;

inti=0,j=0,t=0;

for（i=0;i

finish[i]=false;

while（tempn）

{

for（i=0;i

{

if（!

finish[i]）

{

inttp=0;

//注释部分用于调试程序

//printf（"%d\t%d%4d%4d\t",i,Work[0],Work[1],Work[2]）;

//printf（"%d%4d%4d\n",Need[i][0],Need[i][1],Need[i][2]）;

tp=（Work[0]>=Need[i][0]）&&（Work[1]>=Need[i][1]）&&（Work[2]>=Need[i][2]）;

if（tp）

{

finish[i]=true;

for（intj=0;j

Work[j]+=Allocation[i][j];

flag[t]=i;

//printf（"%d\tflag[%d]=%d",i,t,flag[t]）;system（"pause"）;printf（"\n"）;t++;

break;

}

}

}

tempn--;

}

for（i=0;i

if（finish[i]==false）

{printf（"系统不安全,不存在安全序列\n"）;return-1;}

printf（"系统是安全的,存在安全序列:

\n"）;

for（j=0;j

Work[j]=Available[j];

Safe1（flag,n_pro,0）;

printf（"\n"）;

return0;

}

intSafe1（intflag[],intn,intt）

{

intp,i,j;//p为标记

inttemp[N];//临时数组

for（i=0;i

{

inttp=0;

tp=（Work[0]>=Need[i][0]）&&（Work[1]>=Need[i][1]）&&（Work[2]>=Need[i][2]）;

if（tp）

{

for（j=0;j

Work[j]+=Allocation[i][j];

flag[t]=i;

p=1;

}

elsecontinue;

for（intj=0;j

if（flag[t]==flag[j]）

{

for（j=0;j

Work[j]-=Allocation[i][j];

p=0;break;

}

if（p==1）

{

if（t==n-1）

{

for（j=0;j

printf（"p%-5d",flag[j]）;

printf（"\n"）;

}

else

{

for（j=0;j

temp[j]=Work[j]-Allocation[i][j];

Safe1（flag,n,t+1）;

for（j=0;j

Work[j]=temp[j];

}

}

}

return0;

}

intRequest（）//进程提出请求后，判断系统能否将资源分配给它

{

intrq;//下标

intRequest[N];

printf（"请输入需要请求的进程号（0~4）:

"）;

scanf（"%d",&rq）;

printf（"请输入需要请求的资源数（ABC）:

"）;

scanf（"%d%d%d",&Request[0],&Request[1],&Request[2]）;

if（Need[rq][0]

{

printf（"进程p%d申请的资源大于它所需要的资源\n分配不合理，不予分配\n\n",rq）;

return-1;

}

if（Available[0]

{

printf（"进程p%d申请的资源大于系统现在可利用的资源\n分配不合理，不予分配\n\n",rq）;

return-1;

}

for（intj=0;j

{

Available[j]-=Request[j];

Allocation[rq][j]+=Request[j];

Need[rq][j]-=Request[j];

}

printf（"假定系统可为p%d分配，分配后的资源分配表:

\n",rq）;

show（）;

printf（"\n"）;

for（j=0;j

Work[j]=Available[j];

if（Safe（））

{

printf（"系统进入不安全状态，不予分配\n\n"）;

for（intj=0;j

{

Available[j]+=Request[j];

Allocation[rq][j]-=Request[j];

Need[rq][j]+=Request[j];

}

printf（"此刻的资源分配表为:

\n"）;

show（）;printf（"\n"）;

}

else

{

printf（"系统是安全的，以上序列是此刻所存在的安全序列!

\n"）;

printf（"系统已分配p%d所申请的资源!

\n\n",rq）;

}

return0;

}

intmain（）

{

printf（"从磁盘读取源文件…\n"）;

Readfile（）;

printf（"T0时刻的安全性:

\n"）;

if（Safe（））return-1;

while

（1）

{

Request（）;

}

return0;

}

六、结果及数据分析

①、本程序按下图建立.txt源文件，作为程序的初始化输入。

②、执行程序，读取源文件，并判断T0时刻所得结果:

③、T0时刻的安全序列以及输入P2进程Request（222）所得请求结果：

④、调用Request（）函数，测试该函数的可行性，如输入P1进程Request（102），所得结果：

5输入P0进程Request（020），所得结果:

七、心得体会

在程序进行编写之前，先对程序的要求进行分析，弄清楚程序所需要的功能，然后将每个功能分成一个功能模块即调用函数来实现，无需过多的画蛇添足。

编写这个简易的银行家算法让我知道了在资源一定的条件下为了让多个进程都能使用资源完成任务，避免死锁的产生可以从一开始就对系统进行安全性检查来判断是否将资源分配给正在请求的进程。

但是银行家算法会加大系统的开销。

此外，对于此算法，我想知道实际运用中会怎么使用。

在系统不分配进程所请求的资源的时候，是否会将此资源等待，直到拥有足够的资源的时候再来运行？

进程会请求资源是指在执行的过程中只有拥有了足够数量的资源才可以执行下去，但是资源有限，进程数又有足够多，我们期望所有进程都可以在最短的时间内执行完。

也许可以这样理解。

哦，题目中要求所系统随机给进程分配初始化的资源，这里我不太会。

系统随机分配？

可以是对系统各种资源的总数中对各个进程进行随机分配，直接使用随机分配函数？

在输出全部安全序列中使用了与八皇后问题相同的算法——回溯法。

本次课设让我对银行家算法和死锁都有了一定的理解。

操作系统的基本特征就是并发和共享，系统允许多个进程并发执行，并且共享系统的软、硬件资源。

为了最大限度的利用计算机资源，操作系统应采用动态分配的策略，但是这样就容易因资源不足、分配不当而引起“死锁”。

本次课程设计就是用银行家算法来避免“死锁”。

该算法就是一个资源分配过程，使分配序列不会产生死锁。

此算法的中心思想就是，每次分配后总存在着一个进程，如果让它单独的运行下去，必然可以获得它所需要的全部资源，而它结束后可以归还这类资源以满足其他申请者的需要。

8、参考资料

①、《计算机操作系统（第三版）》汤子瀛等西安电子科技大学出版社

②、《操作系统实验教程——基于windows和Linux》秦明等