admin管理员组文章数量:1567918
目录
1.算法思想的实现
1.1 安全性检查算法
【算法思想】
【算法实现】
1.2 银行家算法
【算法思想】
【算法实现】
2.完整的程序
3.运行结果展示
1.算法思想的实现
1.1 安全性检查算法
【算法思想】
| 安全性算法的主要思想如下： （1）设置两个向量 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有M个元素，在执行安全算法开始的时候，Work=Available；Finish：它表示系统是否有足够的资源分配给进程，让它能够运行完成。事先做Finish[i]=false;当有足够资源分配给进程时，再令Finish[i]=true。 （2）从进程集合中找到一个能够满足下面的条件的进程： ①Finish[i]=false; ②Need[i][j]<=Work[j] 如果找到了，执行步骤（3），否则，执行步骤（4） （3）当进程Pi获得资源后，可顺利执行，直到完成，并释放出分配给它的资源，则应该执行： ①Work[j]=Work[j]+Allocation[i][j]; ②Finish[i]=true ③继续执行步骤（2） （4）如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。 本实验的安全性算法实现细节如下： ①寻找可以执行的进程（searchPossibleProcess）：
②判断进程是否在安全序列中（isNotFound）：
③检查当前安全状态（checkSafeState）：
如果所有进程都能够执行并且安全地完成，那么系统处于安全状态，返回 true；否则返回 false，表示系统处于不安全状态。 |
【算法实现】
// 寻找可以执行的进程
int searchPossibleProcess(Banker *s){
Banker *banker=s; // 获取 Banker 结构体指针
for(int i=0;i<N;i++){ // 遍历每个进程
int j=0;
if(banker->Finish[i]==false){ // 如果进程未完成
for(;j<M;j++) // 遍历每类资源
if(banker->Need[i][j]>banker->Work[i][j])//Work<=Need
break; // 如果需求资源大于可用资源，则跳出循环
}
if(j>=M) {//找到了一个可以执行的进程
return i; // 返回可以执行的进程编号
}
}
return -1; // 如果没有可执行的进程，返回 -1
}
// 判断进程是否在安全序列中
boolean isNotFound(int k,int series[])
{
for(int i=0;i<N;i++)
{
if(k==series[i])
return false; // 如果进程在安全序列中，则返回 false
}
return true; // 如果进程不在安全序列中，则返回 true
}
// 检查当前安全状态
boolean checkSafeState(Banker *s, int *safeSequence)
{
Banker *banker = s; // 获取 Banker 结构体指针
for (int i = 0; i < N; i++) { // 遍历每个进程
// 将可用资源复制给工作向量
banker->Work[i][0] = banker->Available[0];
banker->Work[i][1] = banker->Available[1];
banker->Work[i][2] = banker->Available[2];
}
for (int i = 0; i < N; i++) { // 遍历每个进程
int label = searchPossibleProcess(banker);//找到可以执行的进程
if (label >= 0) {
// 计算工作向量加上已分配资源
banker->WorkPlusAllocation[label][0]=banker->Work[label][0] + banker->Allocation[label][0];
banker->WorkPlusAllocation[label][1]=banker->Work[label][1] + banker->Allocation[label][1];
banker->WorkPlusAllocation[label][2]=banker->Work[label][2] + banker->Allocation[label][2];
for(int k=0;k<N;k++) // 遍历每个进程
{
if(isNotFound(k,safeSequence)&&label!=k) // 如果进程不在安全序列中且不是当前进程
{ // 更新工作向量
banker->Work[k][0]= banker->WorkPlusAllocation[label][0];
banker->Work[k][1]= banker->WorkPlusAllocation[label][1];
banker->Work[k][2]= banker->WorkPlusAllocation[label][2];
}
}
banker->Finish[label] = true;//Finish设置为true
safeSequence[i] = label;//加入安全序列
}
}
for(int i=0;i<N;i++){
if(banker->Finish[i]==false)//只要有一个为false那么就会进入不安全状态
return false; // 如果有未完成的进程，则返回 false
}
return true; // 如果所有进程都完成，则返回 true
}1.2 银行家算法
【算法思想】
| 银行家算法的具体思想是通过预先判断系统在分配资源时是否会导致死锁，从而避免系统陷入不可恢复的状态。其主要原则包括资源分配的安全性和避免死锁的策略。具体来说，银行家算法的核心思想有以下几点： （1）资源分配的安全性：
（2）安全状态的定义：
（3）资源分配的策略：
（4）资源释放的重要性：
综上所述，银行家算法的具体思想是通过动态地分析系统中各进程的资源需求，预测资源分配后系统是否会处于安全状态，以此来避免系统陷入死锁的危险状态，保证系统的稳定性和可靠性。 以下是银行家算法实现的具体步骤： 设Requesti是进程Pi的请求向量，如果Requesti[j]=K，表示进程P|需要K个R类型的资源。当P发出资源请求后，系统按下述步骤进行检查: (1) 如果 Requesti[j]≤Need[i,j]，便转向步骤(2);否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果 Requesti[j]≤Available[j]，便转向步骤(3):否则，表示尚无足够资源，P须等待。 (3)系统试探着把资源分配给进程P，并修改下面数据结构中的数值: Available[j] =Available[j]-Requesti[j]; Allocation[i,j] = Allocation[i,j]+Requesti[j]; Need[i,j] = Need[i,j]- Requesti[j]; (4)系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程P，以完成本次分配;否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 P等待。
|
【算法实现】
// 银行家算法主要逻辑
boolean bankerAlgorithm(Banker *ban,request Request[],int i)
{
printf("\n收到进程P%d发来请求向量Request(",i);
for(int j=0;j<M-1;j++) printf("%2d,",Request[j]); // 输出请求向量中的资源数量
printf("%2d)\n",Request[M-1]); // 输出请求向量中的资源数量
Banker banker=*ban;//假设模拟的一个banker
int flag_N=0,flag_A=0;
for(int j=0;j<M;j++)
{
if(Request[j]>banker.Need[i][j])
{
//#1 Request<=Need
printf("出错，因为进程P%d所需要的资源数超过了它所宣布的最大值: Request_%c=%d > Need_%c=%d\n",
i,'A'+j,Request[j],'A'+j,banker.Need[i][j]); // 输出错误信息
flag_N=1;
break;
}
else if(Request[j]>banker.Available[j]) {
//#2 Request<=Available
flag_A=1;
printf("进程P%d Request_%c=%d > Available_%c=%d \n",i,'A'+j,Request[j],'A'+j,banker.Available[j]); // 输出错误信息
for(int t=0;t<M;t++)
{
banker.Available[t]-=Request[t]; // 更新可用资源数量
banker.Allocation[i][t]+=Request[t]; // 更新已分配资源数量
banker.Need[i][t]-=Request[t]; // 更新剩余需求资源数量
}
printf("尚无足够资源，进程P%d须等待。\n",i);//资源不够阻塞自己,等待
printBanker(banker);
break;
}
}
if(flag_N==0&&flag_A==0)//试探性分配资源
{
for(int j=0;j<M;j++)
{
banker.Available[j]-=Request[j]; // 更新可用资源数量
banker.Allocation[i][j]+=Request[j]; // 更新已分配资源数量
banker.Need[i][j]-=Request[j]; // 更新剩余需求资源数量
}
int safeSequence[N];
for(int i=0;i<N;i++) safeSequence[i]=-1; // 初始化安全序列
boolean judge=checkSafeState(&banker,safeSequence); //安全性检查
if(judge==true) { //judge为true表示找到了一个安全序列
printf("安全序列：{");
for(int i=0;i<N;i++){ //打印安全序列
printf("P%d",safeSequence[i]);
if(i < N - 1) printf(", ");
}
printf("}");
printBanker(banker); //输出在系统安全的情况下，每一个进程的资源情况
setFinishIsFalse(&banker); //重置Finish数组为false，为下一次的资源请求做准备
*ban=banker; //因为找到了一个安全序列,说明假设是正确的，则把ban指向的数据结构改为真实的数据
} else { //judge为false说明当前系统处于不安全的状态 ,假设失败，不更改ban指向的数据结构
printf("系统处于不安全状态。\n");
banker.safeTestTimer=0;
printBanker(banker); //这里可以打印假设处于不安全的状态下的banker数据结构情况
}
}
}2.完整的程序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define true 1 // 定义布尔值 true
#define false 0 // 定义布尔值 false
#define M 3 // 定义资源类型数
#define N 5 // 定义进程数
#define boolean int // 定义布尔类型
#define request int // 定义请求资源类型
// 银行家算法所需的数据结构
typedef struct Banker{
int Available[M]; // 可利用资源向量
int MAX[N][M]; // 最大需求矩阵
int Allocation[N][M]; // 分配矩阵
int Need[N][M]; // 需求矩阵
int Work[N][M]; // 工作向量
int WorkPlusAllocation[N][M]; // 工作向量加上已分配资源矩阵
boolean Finish[N]; // 完成向量，标记进程是否完成
int safeTestTimer; // 安全性测试计时器
} Banker;
// 创建一个新的 Banker 结构体并初始化
Banker *New_Banker(){
printf("初始化数据结构...\n");
Banker *banker=(Banker *)malloc(sizeof(Banker));
banker->safeTestTimer=0; // 初始化安全性测试计时器为 0
// 输入系统中每类资源的总数量
for(int i=0;i<M;i++){
printf("请输入%c类资源的总数量\n",'A'+i);
scanf("%d",&banker->Available[i]);
}
// 输入每个进程对资源的最大需求和已分配资源
for(int i=0;i<N;i++){
banker->Finish[i]=false; // 初始化进程状态为未完成
printf("请输入进程P%d对A、B、C类资源的最大需求量 MAX \n",i);
scanf("%d %d %d",&banker->MAX[i][0],&banker->MAX[i][1],&banker->MAX[i][2]); // 将用户输入的最大需求存入 MAX 数组中
printf("请为进程P%d分配A、B、C类资源，不能超过其最大值 MAX\n",i);
scanf("%d %d %d",&banker->Allocation[i][0],&banker->Allocation[i][1],&banker->Allocation[i][2]); // 将用户输入的分配资源存入 Allocation 数组中
printf("\n\n");
banker->Available[0]-=banker->Allocation[i][0]; // 更新可用资源数量
banker->Available[1]-=banker->Allocation[i][1]; // 更新可用资源数量
banker->Available[2]-=banker->Allocation[i][2]; // 更新可用资源数量
banker->Need[i][0]=banker->MAX[i][0]-banker->Allocation[i][0]; // 计算进程对每类资源的剩余需求
banker->Need[i][1]=banker->MAX[i][1]-banker->Allocation[i][1]; // 计算进程对每类资源的剩余需求
banker->Need[i][2]=banker->MAX[i][2]-banker->Allocation[i][2]; // 计算进程对每类资源的剩余需求
}
printf("初始化成功\n");
return banker; // 返回初始化后的 Banker 结构体指针
}
// 打印银行家的数据结构
void printBanker(Banker banker){
Banker temp=banker; // 创建临时的 Banker 结构体以避免修改原始数据
printf("\n\n");
char str[100]; // 创建一个字符数组用于格式化输出
if(banker.safeTestTimer==0){ // 初始状态下的输出
strcpy(str," P%d %d %d %d %d %d %d %d %d %d "); // 设置输出格式字符串
printf(" 资源情况 MAX Allocation Need Available\n"); // 输出表头
printf("进程 A B C A B C A B C A B C\n"); // 输出表头
for(int i=0;i<N;i++){ // 遍历每个进程
printf(str,i,temp.MAX[i][0],temp.MAX[i][1],temp.MAX[i][2],temp.Allocation[i][0],temp.Allocation[i][1],temp.Allocation[i][2], // 格式化输出最大需求、已分配和剩余需求
temp.Need[i][0],temp.Need[i][1],temp.Need[i][2]);
if(i==0) {
printf("%d %d %d \n",temp.Available[0],temp.Available[1],temp.Available[2]); // 输出可用资源
strcat(str,"\n"); // 追加换行符到格式化字符串
}
}
}
else if(banker.safeTestTimer>=1){
printf(" 资源情况 Work Need Allocation Work+Allocation Finish\n"); // 输出表头
printf("进程 A B C A B C A B C A B C\n"); // 输出表头
strcpy(str," P%2d %2d %2d %2d %2d %2d %2d %2d %2d %2d %2d %2d %2d "); // 设置输出格式字符串
for(int i=0;i<N;i++){ // 遍历每个进程
printf(str,i,banker.Work[i][0],banker.Work[i][1],banker.Work[i][2],banker.Need[i][0],banker.Need[i][1],banker.Need[i][2], // 格式化输出工作向量、剩余需求、已分配资源和工作向量加上已分配资源
banker.Allocation[i][0],banker.Allocation[i][1],
banker.Allocation[i][2],banker.WorkPlusAllocation[i][0],
banker.WorkPlusAllocation[i][1],banker.WorkPlusAllocation[i][2]);
if(banker.Finish[i]==false) printf("false\n"); // 如果进程未完成，输出 false
else printf("true\n"); // 如果进程已完成，输出 true
}
}
}
// 寻找可以执行的进程
int searchPossibleProcess(Banker *s){
Banker *banker=s; // 获取 Banker 结构体指针
for(int i=0;i<N;i++){ // 遍历每个进程
int j=0;
if(banker->Finish[i]==false){ // 如果进程未完成
for(;j<M;j++) // 遍历每类资源
if(banker->Need[i][j]>banker->Work[i][j])//Work<=Need
break; // 如果需求资源大于可用资源，则跳出循环
}
if(j>=M) {//找到了一个可以执行的进程
return i; // 返回可以执行的进程编号
}
}
return -1; // 如果没有可执行的进程，返回 -1
}
// 判断进程是否在安全序列中
boolean isNotFound(int k,int series[])
{
for(int i=0;i<N;i++)
{
if(k==series[i])
return false; // 如果进程在安全序列中，则返回 false
}
return true; // 如果进程不在安全序列中，则返回 true
}
// 检查当前安全状态
boolean checkSafeState(Banker *s, int *safeSequence)
{
Banker *banker = s; // 获取 Banker 结构体指针
for (int i = 0; i < N; i++) { // 遍历每个进程
// 将可用资源复制给工作向量
banker->Work[i][0] = banker->Available[0];
banker->Work[i][1] = banker->Available[1];
banker->Work[i][2] = banker->Available[2];
}
for (int i = 0; i < N; i++) { // 遍历每个进程
int label = searchPossibleProcess(banker);//找到可以执行的进程
if (label >= 0) {
// 计算工作向量加上已分配资源
banker->WorkPlusAllocation[label][0]=banker->Work[label][0] + banker->Allocation[label][0];
banker->WorkPlusAllocation[label][1]=banker->Work[label][1] + banker->Allocation[label][1];
banker->WorkPlusAllocation[label][2]=banker->Work[label][2] + banker->Allocation[label][2];
for(int k=0;k<N;k++) // 遍历每个进程
{
if(isNotFound(k,safeSequence)&&label!=k) // 如果进程不在安全序列中且不是当前进程
{ // 更新工作向量
banker->Work[k][0]= banker->WorkPlusAllocation[label][0];
banker->Work[k][1]= banker->WorkPlusAllocation[label][1];
banker->Work[k][2]= banker->WorkPlusAllocation[label][2];
}
}
banker->Finish[label] = true;//Finish设置为true
safeSequence[i] = label;//加入安全序列
}
}
for(int i=0;i<N;i++){
if(banker->Finish[i]==false)//只要有一个为false那么就会进入不安全状态
return false; // 如果有未完成的进程，则返回 false
}
return true; // 如果所有进程都完成，则返回 true
}
// 重置 Finish 数组为 false
void setFinishIsFalse(Banker *banker)
{
for(int i=0;i<N;i++)
banker->Finish[i]=false; // 将所有进程的状态设置为未完成
}
// 银行家算法主要逻辑
boolean bankerAlgorithm(Banker *ban,request Request[],int i)
{
printf("\n收到进程P%d发来请求向量Request(",i);
for(int j=0;j<M-1;j++) printf("%2d,",Request[j]); // 输出请求向量中的资源数量
printf("%2d)\n",Request[M-1]); // 输出请求向量中的资源数量
Banker banker=*ban;//假设模拟的一个banker
int flag_N=0,flag_A=0;
for(int j=0;j<M;j++)
{
if(Request[j]>banker.Need[i][j])
{
//#1 Request<=Need
printf("出错，因为进程P%d所需要的资源数超过了它所宣布的最大值: Request_%c=%d > Need_%c=%d\n",
i,'A'+j,Request[j],'A'+j,banker.Need[i][j]); // 输出错误信息
flag_N=1;
break;
}
else if(Request[j]>banker.Available[j]) {
//#2 Request<=Available
flag_A=1;
printf("进程P%d Request_%c=%d > Available_%c=%d \n",i,'A'+j,Request[j],'A'+j,banker.Available[j]); // 输出错误信息
for(int t=0;t<M;t++)
{
banker.Available[t]-=Request[t]; // 更新可用资源数量
banker.Allocation[i][t]+=Request[t]; // 更新已分配资源数量
banker.Need[i][t]-=Request[t]; // 更新剩余需求资源数量
}
printf("尚无足够资源，进程P%d须等待。\n",i);//资源不够阻塞自己,等待
printBanker(banker);
break;
}
}
if(flag_N==0&&flag_A==0)//试探性分配资源
{
for(int j=0;j<M;j++)
{
banker.Available[j]-=Request[j]; // 更新可用资源数量
banker.Allocation[i][j]+=Request[j]; // 更新已分配资源数量
banker.Need[i][j]-=Request[j]; // 更新剩余需求资源数量
}
int safeSequence[N];
for(int i=0;i<N;i++) safeSequence[i]=-1; // 初始化安全序列
boolean judge=checkSafeState(&banker,safeSequence); //安全性检查
if(judge==true) { //judge为true表示找到了一个安全序列
printf("安全序列：{");
for(int i=0;i<N;i++){ //打印安全序列
printf("P%d",safeSequence[i]);
if(i < N - 1) printf(", ");
}
printf("}");
printBanker(banker); //输出在系统安全的情况下，每一个进程的资源情况
setFinishIsFalse(&banker); //重置Finish数组为false，为下一次的资源请求做准备
*ban=banker; //因为找到了一个安全序列,说明假设是正确的，则把ban指向的数据结构改为真实的数据
} else { //judge为false说明当前系统处于不安全的状态 ,假设失败，不更改ban指向的数据结构
printf("系统处于不安全状态。\n");
banker.safeTestTimer=0;
printBanker(banker); //这里可以打印假设处于不安全的状态下的banker数据结构情况
}
}
}
int main(){
Banker *safeState_t0=New_Banker();
printBanker(*safeState_t0);
request Request[M]={0}; // 初始化请求向量
char enter;
while(true)
{
int pId;
printf("\n请输入要请求资源的进程:\n");
scanf("%d",&pId); // 输入要请求资源的进程编号
printf("请输入进程P%d的请求向量\n",pId);
for(int i=0;i<M;i++)
{
scanf("%d",&Request[i]); // 输入请求向量
}
printf("系统正在执行银行家算法...\n");
bankerAlgorithm(safeState_t0,Request,pId); // 执行银行家算法
printf("\n本轮执行结束,按下c键继续，按下e键退出 ");
while ((getchar()) != '\n');
enter=getchar();
getchar();
if(enter=='e')
{
printf("\n正在退出...");
break;
}
}
printf("\n退出成功");
return 0;
}
3.运行结果展示
| # 1测试数据如下： 假设系统中有5个进程{P0，P1，P2，P3，P4}，3类资源{A，B，C}，资源总数为10、5、7。
# 2程序运行结果如下列截图 # 3分析：整体来看，系统根据银行家算法的逻辑进行了资源请求处理，并根据当前的资源情况进行了安全性检查。在安全状态下，系统分配资源并更新资源情况；在不安全状态下，系统不会分配资源，保证了系统的稳定性和安全性。 |
版权声明：本文标题：银行家算法+安全性检查 【 死锁 】 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/dongtai/1724982804a1001041.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论