当前位置：文档之家 › 银行家算法 递归求所有安全序列

银行家算法 递归求所有安全序列

  • 格式：txt
  • 大小：9.69 KB
  • 文档页数：4


#include
#include
#include
#include
#define MaxResourceNum 101 //最大资源数100，（下标0未用）
#define MaxProcessNum 101 //最大进程数100, （下标0未用）

char * Safety[MaxProcessNum];//安全序列

typedef struct Resource{ //资源结点
char name[10]; //名称
int num; //数量
}Resource;

Resource Available[MaxResourceNum]; //可利用资源向量

Resource WorkRecord[MaxProcessNum][MaxResourceNum]; //查找安全序列时的Word记录

int ResourceNum,ProcessNum; //资源数，进程数
bool IsSafe=false; //当前或满足进程请求后状态是否安全

typedef struct PCB{
char name[10]; //进程名
char status[10]; //状态
int Max[MaxResourceNum]; //最大需求向量
int Allocation[MaxResourceNum]; //分配向量
int Need[MaxResourceNum]; //需求向量
int Request[MaxResourceNum]; //请求向量
bool Finish; //进程是否获得资源已完成
struct PCB *next; //下一个结点
}PCB;

PCB *head=(PCB* )malloc(sizeof(PCB));//PCB链头指针
PCB *tail=head; //尾指针

//输入资源种类，数目
void PrintAvailable(){
printf("请输入资源种类数目:");
scanf("%d",&ResourceNum);
printf("请输入资源的名称：\n");
getchar();
for(int i=1;i<=ResourceNum;i++)
{
gets(Available[i].name);
}
printf("请输入资源的数目:\n");
for(i=1;i<=ResourceNum;i++)
scanf("%d",&Available[i].num);
}

//输入进程的资源情况
void InputPCB(){
void ShowStatus() ;
void CurrentCheck();
printf("请输入进程数");
scanf("%d",&ProcessNum);
getchar();
printf("输入%d个进程的资源分配情况:\n",ProcessNum);
for(int i=1;i<=ProcessNum;i++)
{
PCB *p=(PCB *)malloc(sizeof(PCB));
printf("请输入进程名:");
gets(p->name);
printf("输入最大需求向量:");
for(int i=1;i<=ResourceNum;i++)
scanf("%d",&p->Max[i]);
printf("输入分配向量:");
for(i=1;i<=ResourceNum;i++)
scanf("%d",&p->Allocation[i]);
printf("推得需求向量为:");
for( i=1;i<=ResourceNum;i++)
{
p->Need[i]=p->Max[i]-p->Allocation[i];
printf(" %d",p->Need[i]);
}
p->next=NULL;
p->Finish=false;
printf("\n");
getchar();
tail->next=p;
tail=p;
}
PCB *p=head->next;
for( i=1;i<=ProcessNum;i++)
{
for(int j=1;j<=ResourceNum;j++)
Available[j].num-=p->Allocation[j];
p=p->next;
}

printf("\n");
CurrentCheck();
printf("\n");
ShowStatus();
}

//检测当前状态是否安全
void CurrentCheck(){
void safety(PCB *head,Resource Work[],int n);
Resource Work[MaxResourceNum];
for(int i=1;i<=ResourceNum;i++)
{
strcpy(Work[i].name,Available[i].name);
Work[i].num=A

vailable[i].num;
}

safety(head,Work,1);
if(IsSafe)
{
printf("故系统安全 \n");
}
else
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED);
printf("当前时刻系统处于不安全状态，请重新设置\n");
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN);
}
}

//显示当前资源分配状态
void ShowStatus()
{
printf("当前系统状态:\n");
printf(" Max Allocation Need Available \n");
printf(" ");
for(int k=1;k<=4;k++){
for(int i=1;i<=ResourceNum;i++)
printf(" %s ",Available[i].name);
printf(" ");}
printf("\n");
PCB *p=head->next;
for(int i=1;i<=ProcessNum;i++)
{
printf("%s",p->name);
printf(" ");
for(int j=1;j<=ResourceNum;j++)
printf("%d ",p->Max[j]);
printf(" ");
for( j=1;j<=ResourceNum;j++)
printf("%d ",p->Allocation[j]);
printf(" ");
for(j=1;j<=ResourceNum;j++)
printf("%d ", p->Need[j]);
printf(" ");
if(i==1)
for( j=1;j<=ResourceNum;j++)
printf("%d ", Available[j].num);
printf("\n");
p=p->next;
}
}

//安全序列求解过程显示
void SafeShow(Resource Work[])
{

PCB *p;
for(int i=1;i<=ProcessNum;i++)
{

p=head->next;
printf("%s ",Safety[i]);
while(p!=NULL)
{
if(strcmp(p->name,Safety[i])==0) break;
p=p->next;
}

for(int j=1;j<=ResourceNum;j++)
printf("%d ", WorkRecord[i][j].num);
printf(" ");
for(j=1;j<=ResourceNum;j++)
printf("%d ", p->Need[j]);
printf(" ");
for(j=1;j<=ResourceNum;j++)
printf("%d ", p->Allocation[j]);
printf(" ");
if(ifor(int j=1;j<=ResourceNum;j++)
printf("%d ", WorkRecord[i+1][j].num);
else
for(int j=1;j<=ResourceNum;j++)
printf("%d ", Work[j].num);

if(p->Finish) printf(" true");

printf("\n");
}
}

//进程对资源的请求
void RequestResource(){
void safety(PCB *head,Resource Work[],int n);
char name[10];
getchar();
printf("请输入提出请求的进程名:\n");
gets(name);
PCB *p=head->next;
for(int i=1;i<=ProcessNum;i++)
{
p->Finish=false;
}
IsSafe=false;
p=head->next;
PCB *pre=head;//请求进程的前驱

while(p!=NULL)
{
if(strcmp(p->name,name)==0) break;
pre=p;
p=p->next;
}//产找请求进程的PCB

printf("请输入对资源的请求数：\n");

for(i=1;i<=ResourceNum;i++)
scanf("%d",&p->Request[i]);

for( i=1;i<=ResourceNum;i++) //判定Requst{
if(p->Request[i]>p->Need[i]||p->Request[i]>Available[i].num)
{
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED);
printf("资源数不够，不可响应请求，进程阻塞");
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN);
return;
}
}

Resource

Work[MaxResourceNum];
for( i=1;i<=ResourceNum;i++)
{
Work[i].num=Available[i].num;
strcpy(Work[i].name,Available[i].name);
}

//试分配资源
for( i=1;i<=ResourceNum;i++)
{
Work[i].num-=p->Request[i];
p->Allocation[i]+=p->Request[i];
p->Need[i]-=p->Request[i];
}

safety(head,Work,1);
//是否处于安全状态
if(IsSafe)
{//处于安全状态 进行分配

for( i=1;i<=ResourceNum;i++)
{
Available[i].num-=p->Request[i];
}

int end=0;
for(i=1;i<=ResourceNum;i++)
{
if(p->Need[i]==0) end++;
}
//若进程的Need为0，可视为其获得足够的资源，运行完成
if(end==ResourceNum){
printf("进程%s运行完毕",p->name);
pre->next=p->next;
free(p);
ProcessNum--;
}

printf("\n");
ShowStatus();
}
else{
//处于不安全状态 回退不分配
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_RED);

printf("若分配，则不存在安全队列，不可响应进程%s的请求\n",name);
for(int i=1;i<=ResourceNum;i++) //将之前试分配时对Allocation Need 的操作回退
{
p->Allocation[i]-=p->Request[i];
p->Need[i]+=p->Request[i];
}
SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),FOREGROUND_GREEN);
ShowStatus();
}
}

//安全性算法
void safety(PCB *head,Resource Work[],int n)
{
if(n>ProcessNum) //若进程已全部放在安全队列中，则输出安全队列
{
printf("进程 Work Need Allocation Work+Allocation Finish \n");
printf(" ");
for(int k=1;k<=4;k++){
for(int i=1;i<=ResourceNum;i++)
printf("%s ", Available[i].name);
printf(" ");
}
printf("\n");
SafeShow(Work);
printf("安全序列为：");
for(int i=1;i<=ProcessNum;i++)
printf("%s ",Safety[i]);
printf("\n\n");
IsSafe=true;
}

char * FoundFinish(PCB *head,Resource Work[]);

PCB *p=NULL;

char *c=FoundFinish(head,Work);//查找可分配资源的未完成的进程

while(strcmp(c,"end")!=0) //若没有遍历完PCB链，则继续
{

Safety[n]=c;//插入安全序列
for(int i=1;i<=ResourceNum;i++)
{
strcpy(WorkRecord[n][i].name,Work[i].name);//记录当前Work的状态
WorkRecord[n][i].num=Work[i].num;
}

p=head->next;
for( i=1;i<=ProcessNum;i++)
{

if(strcmp(c,p->name)==0) break;
p=p->next;
} //根据进程名查找PCB

for(int j=1;j<=ResourceNum;j++)
{
Work[j].num+=p->Allocation[j];

}
p->Finish=true;

safety(head,Work,n+1);//查找从n+1位置开始的安全子序列
if(!IsSafe) break; //如果未找到，则跳出 IsSafe=false

for(j=1;j<=ResourceNum;j++)
{
Work[j].num-=p->Allocation[j];
} //work将状态回退

c=FoundFinish(p,Work); //查

找在n位置的下一个满足条件的进程
p->Finish=false;
}
}

char * FoundFinish(PCB *head, Resource Work[]){ //产找满足条件的进程
bool F;
PCB * p=head->next;
while(p!=NULL)
{
F=true;
if(!p->Finish) //Finish=false 查找未完成的进程
{
for(int j=1;j<=ResourceNum;j++)
{
if(p->Need[j]>Work[j].num) //查找 needF=false;
}
}
else F=false;
if(F) return p->name;
p=p->next;
}
char *a={"end"}; //若从p开始的链中已无满足条件的进程 则返回end
return a;
}

void menu(){
int n;
printf("***********************银行家算法模拟**********************\n");
printf("* 1.输入资源数 *\n");
printf("* 2.输入个进程的资源分配情况 *\n");
printf("* 3.模拟进程请求资源 *\n");
printf("* 4.显示资源分配图 *\n");
printf("* 5.退出 *\n");
printf("***********************************************************\n");
printf("请选择:");
scanf("%d",&n);
printf("\n");
switch(n){
case 1:PrintAvailable();break;
case 2:InputPCB();break;
case 3:RequestResource();break;
case 4:ShowStatus();break;
case 5:exit(0);break;
}
}

int main()
{
while(true)
{
menu();
getchar();
getchar();
system("cls"); //清屏
}

return 0;
}




下载文档原格式

  / 4
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

相关主题