文档介绍：《操作系统原理》期末实验报告
——银行家算法
实验目的
在多道程序系统中,多个进程的并发执行来改善系统的资源利用率,提高系统的吞吐量,但可能发生一种危险——死锁。所谓死锁(Deadlock),是指多个进程在运行过程中因争夺资源而造成的一种僵局(DeadlyEmbrace),当进程处于这种状态时,若无外力作用,他们都无法在向前推进。而最具代表性的避免死锁的算法,便是Dijkstra的银行家算法。利用银行家算法,我们可以来检测CPU为进程分配资源的情况,决定CPU是否响应某进程的的请求并为其分配资源,从而很好避免了死锁的产生。此次实验的目的即是为了加深对银行家算法理解。在实践的基础上,把所学知识应用于实际应用,更深刻的理解了银行家算法以及操作系统设计原理的实际应用。
实验内容
利用C语言以及Visual C++ ,实现银行家算法,完成以下功能:
添加进程作业;
实现银行家算法,为进程分配资源,并进行安全性检验;
查看当前资源分配情况
撤销进程;
总体设计
银行家算法是最具代表性的避免死锁的算法。在这个算法中,我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。但在系统进行资源分配之前,应先计算此次资源分配的安全性,即系统能按某种进程顺序为每个进程分配其所需资源,直至满足每个进程对资源的最大需求。若此次分配能使系统处于安全状态,则将资源分配给进程;否则,令进程等待。
其具体设计如下:
数据结构设计
可利用资源Available数组。Available[j]=M,则表示系统中可用的j类资源有M个。
定义client结构体类型数组:
struct client{
int Max[MAXSIZE]; //进程最大需求资源
int Allocation[MAXSIZE]; //进程已分得资源数
int Need[MAXSIZE]; //进程尚需资源
};
struct client Client[MAXSIZE];
那么,Client[i].Max[j]表示进程i所需的最大j类资源数;
Client[i].Allocation[j]表示进程i已分得的j类资源数;
Client[i].Need[j]表示进程i尚需j类资源数。
初始化initial()函数设计
用户输入进程数N,以及资源种类数M;
用户输入数据,为Available[j]赋值;
用户输入数据,为Client[i].Max[j]赋值;
用户输入输入,为Client[i].Allocation[j]赋值,并判断i进程的已分得j资源数是否大于其对j资源的最大需求,即Client[i].Allocation[j]>Client[i].Max[j]。若大于,需重新输入;若小于等于,转向步骤(5);
根据Client[i].Need[j] = Client[i].Max[j] - Client[i].Allocation[j],为Client[i].Need[j]赋值。
流程图设计如下:
图表 1 initial()函数流程图
添加进程add()函数设计
进程数加1;
用户输入新加作业的对j类资源的最大需求数Client[N-1].Max[j];
那么Client[N-1].Need[j]=Client[N-1].Max[j];Client[N-1].Allocation[j]=0;
银行家算法设计
定义请求向量Request[MAXSIZE];
用户输入请求资源进程的小标p,并检验是否存在该下标;
用户输入数据,初始化请求向量;
如果Request[j] > Client[p].Need[j],表示进程p所需的j类资源数超过它所宣布的最大值,令flag=0;
如果Request[i] > Available[i],表示目前尚无足够资源进行分配,进程p需等待,令flag=0;
判断flag是否为0。若不为0,则尝试将资源分配给进程p
Available[i] -= Request[i];
Client[p].Allocation[i] += Request[i];
Client[p].Need[i] -= Request[i];
若为0,跳出此函数;
执行安全性算法,检查此次资源分配后系统是否处于安全状态。
流程图设计如下:
图表 2 银行家算法流程图
算法实现如下:
void bid()
{
int p;
int flag=1;
int Request[MAXSIZE]; //请求向量
printf("为作业申请资源:\n");
printf("━━━━━━━━━━