《操作系统》课程设计报告

课题：

银行家算法

专业

计算机科学与技术

学生姓名

班级

计算机

学号

指导教师

信息工程学院

一、实验要求和实验目的实验目的：本课程设计是学生学习完《操作系统原理》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。

实验要求：从课程设计的目的出发，通过设计工作的各个环节，达到以下教学要求：两人一组，每组从所给题目中任选一个（如自拟题目，需经指导教师同意），每个学生必须独立完成课程设计，不能相互抄袭，同组者文档不能相同；设计完成后，将所完成的工作交由指导教师检查；要求写出一份详细的设计报告。

二、设计内容：

课题一、编制银行家算法通用程序，并检测所给状态的系统安全性。

1）银行家算法中的数据结构：

可利用资源向量Available。这是一个含有m个

元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj

类资源K个。

最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。

1.分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资料当前已分配给没一进程的资源数。如果Allocation[i，j]=K，则表示进程i当前已分得Rj类资源的数目为K。需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

上述三个矩阵存在如下关系：

Need[i,j]=

Max[i，j]-

Allocation[i，j]

2）银行家算法

设Request[i]

是进程Pi的请求向量，如果Request[i，j]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：如果Request[i，j]<=

Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

三、设计思路

设计思路A、设计进程对各在资源最大申请表示及初值确定。B、设定系统提供资源初始状态。C、设定每次某个进程对各类资源的申请表示。D、编制程序，依据银行家算法，决定其申请是否得到满足。

四、详细设计

1、初始化：由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。

2、银行家算法：在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前,判断系统是否是安全的;若是,才分配。它是最具有代表性的避免死锁的算法。

设进程cusneed提出请求REQUEST

[i]，则银行家算法按如下规则进行判断。

(1)如果REQUEST

[cusneed]

[i]<=

NEED[cusneed][i]，则转(2)；否则，出错。

(2)如果REQUEST

[cusneed]

[i]<=

AVAILABLE[cusneed][i]，则转(3)；否则，出错。

银行家算法的数据结构

假设有M个进程N类资源，则有如下数据结构:

#define

W

#define

R

int

M

;

//总进程数

int

N

;

//资源种类

int

ALL_RESOURCE[W];

//各种资源的数目总和

int

MAX[W][R];

//M个进程对N类资源最大资源需求量

int

AVAILABLE[R];

//系统可用资源数

int

ALLOCATION[W][R];

//M个进程已经得到N类资源的资源量

int

NEED[W][R];

//M个进程还需要N类资源的资源量

int

Request[R];

//请求资源个数

3.“安全性检测“算法

1)先定义两个变量,用来表示推算过程的数据.F[n]=A[n],表示推算过程中,系统中剩余资源量的变化.J[n]=False表示推算过程中各进程是否假设“已完成“

系统试探分配资源，修改相关数据：

AVAILABLE[i]-=REQUEST[cusneed][i];

ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];、NEED[cusneed][i]-=REQUEST[cusneed][i];

4、安全性检查算法

1)设置两个工作向量Work=AVAILABLE;FINISH

2)从进程集合中找到一个满足下述条件的进程，FINISH==false;

NEED<=Work;

如找到，执行(3)；否则，执行(4)

3)设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work+=ALLOCATION;

Finish=true;

GOTO

4)如所有的进程Finish=

true，则表示安全；否则系统不安全。

安全状态:

在某时刻系统中所有进程可以排列一个安全序列:{P1,P2,`````Pn},刚称此时,系统是安全的.所谓安全序列{P1,P2,`````Pn}是指对于P2,都有它所需要剩余资源数量不大于系统掌握的剩余的空间资源与所有Pi(j

最大需求

尚需

P1

P2

P3

4             2

在每一次进程中申请的资源,判定一下,若实际分配的话,之后系统是否安全.银行家算法的数据结构.五、代码清单

#include

#include

#include

#include

#include

#include

const

int

MAX_P=20;

const

int

MAXA=10;

//定义A类资源的数量

const

int

MAXB=5;

const

int

MAXC=7;

typedef

struct

node{

int

a;

int

b;

int

c;

int

remain_a;

int

remain_b;

int

remain_c;

}bank;

typedef

struct

node1{

char

name[20];

int

a;

int

b;

int

c;

int

need_a;

int

need_b;

int

need_c;

}process;

bank

banker;

process

processes[MAX_P];

int

quantity;

//初始化函数

void

initial()

{

int

i;

banker.a=MAXA;

banker.b=MAXB;

banker.c=MAXC;

banker.remain_a=MAXA;

banker.remain_b=MAXB;

banker.remain_c=MAXC;

for(i=0;i

strcpy(processes[i].name,““);

processes[i].a=0;

processes[i].b=0;

processes[i].c=0;

processes[i].need_a=0;

processes[i].need_b=0;

processes[i].need_c=0;

}

}

//新加作业

void

add()

{

char

name[20];

int

flag=0;

int

t;

int

need_a,need_b,need_c;

int

i;

cout<

cout<<“新加作业“<

cout<<“请输入新加作业名:“;

cin>>name;

for(i=0;i

if(!strcmp(processes[i].name,name)){

flag=1;

break;

}

}

if(flag){

cout<<“错误,作业已存在“<

}

else{

cout<<“本作业所需A类资源:“;

cin>>need_a;

cout<<“本作业所需B类资源:“;

cin>>need_b;

cout<<“本作业所需C类资源:“;

cin>>need_c;

t=1;

cout<

if(need_a>banker.remain_a){

cout<<“错误,所需A类资源大于银行家所剩A类资源“<

t=0;

}

if(need_b>banker.remain_b){

cout<<“错误,所需B类资源大于银行家所剩B类资源“<

t=0;

}

if(need_c>banker.remain_c){

cout<<“错误,所需C类资源大于银行家所剩C类资源“<

t=0;

}

if(t){

strcpy(processes[quantity].name,name);

processes[quantity].need_a=need_a;

processes[quantity].need_b=need_b;

processes[quantity].need_c=need_c;

quantity++;

cout<<“新加作业成功“<

}

else{

cout<<“新加作业失败“<

}

}

}

//为作业申请资源

void

bid()

{

char

name[20];

int

i,p;

int

a,b,c;

int

flag;

cout<

cout<<“要申请资源的作业名:“;

cin>>name;

p=-1;

for(i=0;i

if(!strcmp(processes[i].name,name)){

p=i;

break;

}

}

if(p!=-1){

cout<<“该作业要申请A类资源数量:“;

cin>>a;

cout<<“该作业要申请B类资源数量:“;

cin>>b;

cout<<“该作业要申请C类资源数量:“;

cin>>c;

flag=1;

if((a>banker.remain_a)||(a>processes[p].need_a-processes[p].a)){

cout<<“错误,所申请A类资源大于银行家所剩A类资源或该进程还需数量“<

flag=0;

}

if((b>banker.remain_b)||(b>processes[p].need_b-processes[p].b)){

cout<<“错误,所申请B类资源大于银行家所剩B类资源或该进程还需数量“<

flag=0;

}

if((c>banker.remain_c)||(c>processes[p].need_c-processes[p].c)){

cout<<“错误,所申请C类资源大于银行家所剩C类资源或该进程还需数量“<

flag=0;

}

if(flag){

banker.remain_a-=a;

banker.remain_b-=b;

banker.remain_c-=c;

processes[p].a+=a;

processes[p].b+=b;

processes[p].c+=c;

cout<<“为作业申请资源成功“<

}

else{

cout<<“为作业申请资源失败“<

}

}

else{

cout<<“该作业不存在“<

}

}

//撤消作业

void

finished()

{

char

name[20];

int

i,p;

cout<

cout<<“要撤消作业名:“;

cin>>name;

p=-1;

for(i=0;i

if(!strcmp(processes[i].name,name)){

p=i;

break;

}

}

if(p!=-1){

banker.remain_a+=processes[p].a;

banker.remain_b+=processes[p].b;

banker.remain_c+=processes[p].c;

for(i=p;i

processes[i]=processes[i+1];

}

strcpy(processes[quantity-1].name,““);

processes[quantity-1].a=0;

processes[quantity-1].b=0;

processes[quantity-1].c=0;

processes[quantity-1].need_a=0;

processes[quantity-1].need_b=0;

processes[quantity-1].need_c=0;

quantity--;

cout<<“撤消作业成功“<

}

else{

cout<<“撤消作业失败“<

}

}

//查看资源情况

void

view()

{

int

i;

cout<

cout<<“银行家所剩资源(剩余资源/总共资源)“<

cout<<“A类:“<

cout<<“

B类:“<

cout<<“

C类:“<

cout<

if(quantity>0){

for(i=0;i

cout<<“作业名:“<

cout<<“A类:“<

cout<<“

B类:“<

cout<<“

C类:“<

cout<

}

}

else{

cout<<“当前没有作业“<

}

}

//显示版权信息函数

void

version()

{

cout<

cout<<“

银行家算法

“<

cout<

}

void

main()

{

int

chioce;

int

flag=1;

initial();

version();

while(flag){

cout<<“1.新加作业

2.为作业申请资源

3.撤消作业“<

cout<<“4.查看资源情况

0.退出系统“<

cout<<“请选择:“;

cin>>chioce;

switch(chioce){

case

1:

add();

break;

case

2:

bid();

break;

case

3:

finished();

break;

case

4:

view();

break;

case

0:

flag=0;

break;

default:

cout<<“选择错误“<

}

}

}

六、使用说明

运行环境C-FREE4.0，新建任务。将编制好的代码输入此运行环境中。

按F5：出现如上图所示窗口。按照提示，新建一个作业：wujun。为作业分配资源，A：3；B：4；C：5。输入2，为作业分配资源。三种资源的数量分配分别为:A:3;B:5;C:4。输入4，查看资源情况。出现出错提示，所申请的B类资源超过银行家所剩B类资源或作业申请资源失败。输入0，退出系统。

重新加入一个作业：wujun1.并为作业分配资源分别为A:3;B:3;C:3，为该作业分配资源A:3;B:2;C:2.输入4查看资源情况。

显示输出，银行家算法所剩资源（剩余资源、总共资源）。

七、实验心得

八、参考文献

汤子瀛等.计算机操作系统.西安电子科技大学出版社.2024年5月

蒋静

徐志伟.操作系统原理•技术与编程『M』.北京:机械工业出版社,2024