一:实验题目
银行家算法的模拟与实现
二:实验目的
(1) 进一步了解进程的并发执行。
(2) 加强对进程死锁的理解,理解安全状态与不安全状态的概念。
(3) 掌握使用银行家算法避免死锁问题。
三、总体设计(含背景知识或基本原理与算法、或模块介绍、设计步骤等)
背景知识和基本原理:
1.进程的并发执行:多个进程同时运行,共享系统资源,可能导致资源竞争和死锁问题。
2.死锁:进程因为竞争资源而陷入无限等待的状态,无法继续执行。
3.安全状态与不安全状态:安全状态指系统能够找到一种资源分配顺序,使得所有进程都能顺利完成,不安全状态则表示无法找到这样的分配顺序。
银行家算法原理:
银行家算法是一种资源分配策略,用于避免进程死锁。它基于资源的最大需求量和已分配资源量,判断系统是否处于安全状态,如果是,则分配资源;如果不是,则等待。
设计步骤:
1.定义进程和资源的数据结构:需要表示进程的标识、最大需求量、已分配量和需求量等信息,以及资源的总量和可用量。
2.实现银行家算法的安全状态检查:遍历所有进程,模拟资源分配过程,判断系统是否处于安全状态。
3.实现资源分配策略:根据进程的最大需求量和已分配量,进行资源分配,并更新系统资源状态。
四.详细设计(含主要的数据结构、程序流程图、关键代码等)
主要的数据结构:
进程结构体:包含进程的标识、最大需求量、已分配量和需求量等信息。
资源结构体:包含资源的总量和可用量。
*进入循环,接收用户输入的资源请求。
*判断请求是否合法,如果合法则尝试分配资源。
*根据银行家算法进行安全状态检查,判断系统是否处于安全状态。
*如果系统处于安全状态,则分配资源并更新系统状态。
*输出分配结果和系统状态。
数据结构
进程个数n
资源类数m
可利用资源向量Available
含有m个元素的数组,其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K,则表示系统中现有Rj类资源K个。
最大需求矩阵Max
n×m的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K,则表示进程i需要Rj类资源的最大数目为K。
分配矩阵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]
安全检查算法
设置两个工作向量
Work 记录系统当前可用资源量,初值为Available;
finish 记录所有进程是否已被执行, 初值为长度为n,值均为False的向量。
从进程集合中找到一个满足下述条件的进程,
finish == False;
Need <= Work;
如找到,执行3;否则,执行4。
假设进程获得资源,可顺利执行,直至完成,从而释放资源。
Work += Allocation;
Finish=True;
执行2
如所有的进程finish= True,则表示安全;否则系统不安全。
*用户可以选择继续请求资源或结束程序。
关键代码:
void initial()
{
int i;
int j;
printf("请输入进程数:\n");
scanf("%d",&n);
printf("请输入资源类数:\n");
scanf("%d",&m);
printf("请输入可使用资源向量:\n");
Available = (int*)malloc(sizeof(int)*m);
for(i=0; i<m; i++)
scanf("%d",&Available[i]);
printf("请输入最大需求矩阵:\n");
Max = (int**)malloc(sizeof(int*)*n);
for(i=0; i<n; i++)
{
Max[i] = (int*)malloc(sizeof(int)*m);
for(j=0; j<m; j++)
scanf("%d",&Max[i][j]);
}
printf("请输入分配矩阵:\n");
Allocation = (int**)malloc(sizeof(int*)*n);
for(i=0; i<n; i++)
{
Allocation[i] = (int*)malloc(sizeof(int)*m);
for(j=0; j<m; j++)
scanf("%d",&Allocation[i][j]);
}
Need = (int**)malloc(sizeof(int*)*n);
for(i=0;i<n;i++)
{
Need[i] = (int *)malloc(sizeof(int)*m);
for(j=0;j<m;j++)
Need[i][j] = Max[i][j] - Allocation[i][j];
}
}
void request()
{
int i,id;
new_request = (Request*)malloc(sizeof(Request));
new_request->req_src = (int*)malloc(sizeof(int)*m);
printf("请输入进程的ID\n");
scanf("%d",&id);
new_request->id = id - 1;
printf("请输入进程申请资源向量\n");
for(i=0; i<m; i++)
scanf("%d",&new_request->req_src[i]);
}
void process()
{
int i = new_request->id;
if(vector_compare(Need[i],new_request->req_src,m))
{
if(vector_compare(Available,new_request->req_src,m))
{
vector_sub(Available,new_request->req_src,m);
vector_add(Allocation[i],new_request->req_src,m);
vector_sub(Need[i],new_request->req_src,m);
safe_detect();
}
else
{
printf("程序所申请资源大于系统当前所剩资源,推迟执行!\n");
return;
}
}
else
{
printf("程序所申请资源大于该程序所需资源,无法执行!\n");
return;
}
if(safe)
{
printf("系统安全,进程可以执行!\n");
return;
}
else
{
printf("系统不安全,进程无法执行!\n");
vector_add(Available,new_request->req_src,m);
vector_sub(Allocation[i],new_request->req_src,m);
vector_add(Need[i],new_request->req_src,m);
return;
}
}
bool safe_detect()
{
int *work = Available;
bool *finish = (bool*)malloc(sizeof(bool)*n);
int i;
//初始化finish
for(i=0; i<n; i++)
finish[i] = False;
for(i=0; i<n; i++)
{
if(finish[i]==False&&vector_compare(work,Need[i],m))
{
printf("尝试执行第%d进程\n",i+1);
vector_add(work,Allocation[i],m); //尝试执行该进程,释放资源
finish[i] = True;
i = -1; //尝试分配后,从头查找是否还有可以执行的进程,考虑到i++,故此处为-1
}
}
for(i=0; i<n; i++)
if(finish[i]==False)
break;
if(i==n)
safe = True;
else
safe = False;
}
五:实验结果与分析
这段代码实现了银行家算法(Banker's algorithm)的安全性检查部分。银行家算法是一种资源分配和调度算法,用于避免系统陷入死锁状态。它通过预先计算进程的最大资源需求和当前可用资源,来判断是否存在一种安全序列,使得所有进程都能完成执行。
以下是对代码的安全性检查部分的分析:
1.safe_detect() 函数用于进行安全性检查。它接受当前系统可用资源向量 Available、进程的最大需求矩阵 Max 和分配矩阵 Allocation 作为输入。
2.函数内部创建了辅助数组 work 和布尔数组 finish,用于记录工作向量和进程的完成状态。
3.初始化 finish 数组,将所有进程的完成状态初始化为 False。
4.进行安全性检查的主要逻辑是一个循环遍历。对于每个进程 i,判断其完成状态为 False 并且当前可用资源 work 大于等于进程 i 的需求向量 Need[i]。如果满足条件,说明进程 i 可以执行,即尝试执行该进程并释放相应的资源。
5.在尝试执行进程 i 后,将进程 i 的完成状态设为 True,并将可用资源向量 work 增加分配给进程 i 的资源量。
6.循环回到最开始,继续查找下一个满足条件的进程,直到找不到满足条件的进程或所有进程都被标记为已完成。
最后,检查是否所有进程都被标记为已完成。如果是,则认为系统是安全的,将变量 safe 设置为 True;否则,将 safe 设置为 False。
在实验中,可以通过模拟不同的进程和资源情况进行测试。根据输入的进程资源请求,系统会根据银行家算法进行资源分配,并输出分配结果和系统状态。可以观察系统是否处于安全状态,以及资源分配的情况。
六、小结与心得体会
通过本次实验,我进一步了解了进程的并发执行和死锁问题,并学习了银行家算法的原理和实现。通过实际编码实现银行家算法,加深了对算法的理解和程序设计能力的提升。同时,通过实验的过程,我对资源竞争和安全状态的概念有了更深入的认识,对如何避免死锁问题有了清晰的思路。通过分析实验结果,我可以更好地评估系统的安全性和资源分配策略的有效性,为实际系统设计和开发提供了有益的经验。