bank.cpp

操作系统银行家算法的仿真实现生成可视化文件,便于理解程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 10
#define M 10
typedef struct{
 int ip;
 int able[N];
 int visited[N];
 int avail[M];
 int alloc[N][M];
 int need[N][M];
}WorkNode;   /*工作节点*/
FILE *fp=fopen("data.txt","w");

int claim[N][M],resource[M],request[N][M],top=-1,pnum=0,rnum=0;    

/*currnet为当前工作节点*/
WorkNode stack[N],current; 

int main(){
 int i,ct,ch,k,flag=1;
 void add(int [],int []);     /*进程完成,释放资源*/
 int small(int [],int []);      /*已有的资源是否能满足最大请求*/
 void init();                     /*初始化*/
 void output();/*输出堆栈中的一种可能*/
 int safe();/*银行家算法主要部分，回溯法*/

 init();
 while(flag){
 fprintf(fp,"初始化可用资源");
 for(i=0;i<rnum;i++)  fprintf(fp,"%d",current.avail[i]);
 current.ip=-1;
 memset(request,0,sizeof(request));
 printf("请选择哪个进程要求分配\n");
 scanf("%d",&k);
 printf("请输入该进程具体要求\n");
 printf("p%d ", k);
 for(i=0;i<rnum;i++)
	 scanf("%d", &request[k][i]);
 add(current.need[k],request[k]);
 for(i=0;i<pnum;i++)
  if(small(current.need[i],current.avail) )
   current.able[++current.ip]=i;
 if(current.ip==-1){
  fprintf(fp,"it is unsafe\n");
 }
 else if(ct=safe())
  fprintf(fp,"it is safe,and it has %d series\n",ct);
 else fprintf(fp,"\nit is unsafe\n");
 printf("是否继续申请资源？****1—是|2—否\n");
        do{  scanf("%d",&ch);
             if(ch==2)
             flag=0;
        }while(ch!=1&&ch!=2);
 } 
}


void init(){
 int i,j,sum=0;
 printf("process number:");
 scanf("%d",&pnum);
 printf("resource number:");
 scanf("%d",&rnum);
 printf("resource series:");
 for(i=0;i<rnum;i++)scanf("%d",&resource[i]);
 printf("alloc matrix:\n");
 for(i=0;i<pnum;i++){
  printf("p%d:",i);
  for(j=0;j<rnum;j++)
   scanf("%d",&current.alloc[i][j]);
 }
 printf("claim matrix:\n");
 for(i=0;i<pnum;i++){
  printf("p%d:",i);
  for(j=0;j<rnum;j++)
   scanf("%d",&claim[i][j]);
 }
 for(i=0;i<pnum;i++)
	for(j=0;j<rnum;j++)
	{ current.need[i][j]=claim[i][j]-current.alloc[i][j] ;} 
 memset(current.visited,0,sizeof(current.visited) );
 for(i=0;i<rnum;i++){
  for(j=0;j<pnum;j++)
   sum+=current.alloc[j][i];
  current.avail[i]=resource[i]-sum;
  sum=0;
 }

}

void output(){                                     
 int i;
 for(i=0;i<=top;i++)
  fprintf(fp,"p%d,",stack[i].able[stack[i].ip]);
 fprintf(fp,"\n");
}

void add(int x[],int y[]){
 int i;
 for(i=0;i<rnum;i++)
  x[i]+=y[i];
}

int small(int x[],int y[]){
 int i;
 for(i=0;i<rnum;i++){
  if(x[i]>y[i])break;
 }
 if(i==rnum)return 1;
 return 0;
}

int safe(){
 int i,j,ct=0;
 while(1){
  stack[++top]=current;
  current.visited[current.able[current.ip]]=1;
  fprintf(fp,"可选的进程为");
  for(i=0;i<=current.ip;i++)
  {fprintf(fp,"%d ",current.able[i]);} 
  fprintf(fp,"\n当前选择的进程 %d\n", current.able[current.ip]) ;
  add(current.avail,current.alloc[current.able[current.ip]]);
  for(i=0;i<rnum;i++)
  {current.alloc[current.able[current.ip]][i] =0;
  current.need[current.able[current.ip]][i] =0;} 
  fprintf(fp,"尝试分配后,可用资源为 avail:"); 
  for(i=0;i<rnum;i++)
  fprintf(fp,"%d ",current.avail[i]);
  fprintf(fp,"\n尝试分配后,已分配资源alloc:");
  for(i=0;i<pnum;i++) 
   { fprintf(fp,"\n"); 
   for(j=0;j<rnum;j++)
   fprintf(fp,"%d ",current.alloc[i][j]) ;}
  fprintf(fp,"\n尝试分配后,仍需分配资源 need:");
  for(i=0;i<pnum;i++)
  { fprintf(fp,"\n"); 
   for(j=0;j<rnum;j++)
   fprintf(fp,"%d ",current.need[i][j]) ;}
  fprintf(fp,"\n");
  current.ip=-1;
  for(i=0;i<pnum;i++)
   if(!current.visited[i] && small(current.need[i],current.avail) )
    current.able[++current.ip]=i;
  if(current.ip==-1)
  {
   if(top==pnum-1){     
    output();
	fprintf(fp,"该序列合理\n"); 
    ct++;
   }
   else if(top<0)break;
   current=stack[top--]; fprintf(fp,"这次选择不行,返回\n");
   while(current.ip==0){
	   if(top>=0) {
		   current=stack[top--];fprintf(fp,"前一次选择是唯一路径,再返回 \n");}
	   else return ct;} 

   current.ip--;
  }
 }
 return ct;
}