deadlock.c

本程序是操作系统课程实验的死锁的检测与解除。解除方式采用撤销进程的方法。全部用数组实现。在ubuntu（linux）下编译通过。为本人原创。每次撤销个代价最小的死锁进程

#include<stdio.h>
//本程序内部的计数全部从0开始，如3个数记为0，1，2
int *Sc(int i,int m[]){
  switch(i){
    case 1:scanf("%d",&m[0]);break;
    case 2:scanf("%d %d",&m[0],&m[1]);break;
    case 3:scanf("%d %d %d",&m[0],&m[1],&m[2]);break;
    case 4:scanf("%d %d %d %d",&m[0],&m[1],&m[2],&m[3]);break;
    case 5:scanf("%d %d %d %d %d",&m[0],&m[1],&m[2],&m[3],&m[4]);break;
    case 6:scanf("%d %d %d %d %d %d",&m[0],&m[1],&m[2],&m[3],&m[4],&m[5]);break;
    case 7:scanf("%d %d %d %d %d %d %d",&m[0],&m[1],&m[2],&m[3],&m[4],&m[5],&m[6]);break;
    case 8:scanf("%d %d %d %d %d %d %d %d",&m[0],&m[1],&m[2],&m[3],&m[4],&m[5],&m[6],&m[7]);break;
    case 9:scanf("%d %d %d %d %d %d %d %d %d",&m[0],&m[1],&m[2],&m[3],&m[4],&m[5],&m[6],&m[7],&m[8]);break;
    case 10:scanf("%d %d %d %d %d %d %d %d %d %d",&m[0],&m[1],&m[2],&m[3],&m[4],&m[5],&m[6],&m[7],&m[8],&m[9]);break;
    default:{printf("wrong!input again:");}  
  }
  return m;
}

void Pr(int i,int *p)
{
  int t;
  for(t=0;t<i;t++){if(*(p+t)!=-1)printf("%d ",*(p+t));}
}

int test1(int *array,int num){//一0则0,无0则1
  int i,j=1;
  for(i=0;i<num;i++)
  {
    if(*(array+i)==0)
    j=0;
  }
  if(j==0)return 0;
  else return 1;
}

int test0(int *array,int num){//全0则0，一非0则1
  int i,j=0;
  for(i=0;i<num;i++)
  {
    if(*(array+i)!=0)
    j=1;
  }
  if(j==1)return 1;
  else return 0;
}
int test(int *array,int num){//判断数组的值的大小，全大于等于0则1，一负则0
  int i,j=0;
  for(i=0;i<num;i++)
  {
    if(*(array+i)<0)
    j=1;
  }
  if(j==1)return 0;
  else return 1;
}

int test12(int *array,int num){//判断数组的值是否全为0或2，不是则返回0，是则返回1
  int i,j=0;
  for(i=0;i<num;i++)
  {
    if( *(array+i) != 1 ) {if( *(array+i) != 2) j=1;}
  }
  if(j==1)return 0;
  else return 1;
}

int compare(int *array,int num)//找出一个数组中的最小元素，并返回该元素所在第几列
{
  int i,j=0,min=*array;
  for(i=0;i<num;i++)
  {
    if(min>(*(array+i))) {min=*(array+i);j=i;}
  }
  return j;
}

int main(){
  
  int rsn;		//resource number 资源种类数
  int prn;		//process number 进程数

  int i[100];		//作为所有for循环的计数器
  int pn=0;		//作为死锁进程的个数计数器
  int canprs;		//代表要撤销的进程
  int cn=0;		//取消进程的个数的计数器

  printf("请输入资源的种类数和进程的个数，用空格隔开：");
  scanf("%d %d",&rsn,&prn);
  int available[rsn];		//表示每类资源可利用的数目         
  int max[prn][rsn];		//表示每个进程中对每类资源的最大需求数量
  int allocation[prn][rsn];	//表示每类资源当前已分配给每一进程的资源数
  int need[prn][rsn];		//表示每个进程尚需的各类资源数  
  int work[rsn];		//工作向量，表示系统可提供给进程继续运行的各类资源数目
  int finish[prn],*fi;		//表示每个进程的完成与否，完成置为1，未完成置为0，撤销置为2
  int counter=0;		//系统状态检查时用来记录是否有进程更改状态
  int *av,*ma[prn],*all[prn],*nee[prn],*wo;//作为各数组的指针
  int value[rsn],*va;		//存放work减去need后的值
  int cost[prn],*co;		//每个进程的代价
  int lock[prn],*lo;		//死锁进程数组
  int cancel[prn],*ca;		//撤销的进程数组
  int costp[prn],*cop;		//死锁进程的代价数组
  int costadd=0;		//代价和

//定义用于检查的数组
  int sysadd[rsn],*sys;//系统拥有的各种资源的总数
  for(i[33]=0;i[33]<rsn;i[33]++){sysadd[i[33]]=0;}
  sys=sysadd;

//给available数组赋值
  printf("请依次输入%d种资源的可利用资源数目，用空格隔开：",rsn);
  av=Sc(rsn,available);
//给cost数组赋值
  printf("请依次输入%d个进程的代价，用空格隔开：",prn);
  co=Sc(prn,cost);
input:
//给max数组赋值
  for(i[1]=0;i[1]<prn;i[1]++){
    printf("请依次输入第%d个进程对每类资源（共%d类）的最大需求数，用空格隔开：",i[1]+1,rsn);
    ma[i[1]]=Sc(rsn,max[i[1]]);
  }

//给allocation数组赋值
  for(i[2]=0;i[2]<prn;i[2]++)
  {
    printf("请依次输入第%d个进程已占有的每类资源（共%d类）的个数，用空格隔开：",i[2]+1,rsn);
    all[i[2]]=Sc(rsn,allocation[i[2]]);
  }
  
//给need数组赋值
  for(i[3]=0;i[3]<prn;i[3]++)
  {
    for(i[4]=0;i[4]<rsn;i[4]++)
    {
      if(max[i[3]][i[4]]-allocation[i[3]][i[4]]>=0)
      {
        need[i[3]][i[4]]=max[i[3]][i[4]]-allocation[i[3]][i[4]];
      }
      else {printf("you inout a wrong number,please input again.\n");goto input;}  
    }
    nee[i[3]]=&need[i[3]][0];
  }
  
//打印输出的结果
  for(i[4]=0;i[4]<prn;i[4]++)
  {
    printf("进程P%d的信息如下：\n",i[4]+1);
    printf("对%d类资源的最大需求分别是：",rsn);
    Pr(rsn,max[i[4]]);
    printf("已占有的%d类资源数目分别是：",rsn);
    Pr(rsn,all[i[4]]);
    printf("尚需的%d类资源的数目分别是：",rsn);
    Pr(rsn,nee[i[4]]);
    printf("\n");
  }
  printf("目前每种资源的可利用数目为：");
  Pr(rsn,av);printf("\n");
//检查系统的所有资源是否满足各进程的最大需求之和
  for(i[31]=0;i[31]<prn;i[31]++)
    for(i[32]=0;i[32]<rsn;i[32]++)
    {
      sysadd[i[32]]+=allocation[i[31]][i[32]];
    }
  for(i[34]=0;i[34]<rsn;i[34]++){sysadd[i[34]]+=available[i[34]];}
  printf("系统资源总数为：");Pr(rsn,sys);printf("\n");
  for(i[35]=0;i[35]<prn;i[35]++)
    for(i[36]=0;i[36]<rsn;i[36]++)
    {
      if(sysadd[i[36]]<max[i[35]][i[36]])
      {
        printf("您输入的系统拥有的第%d种资源的总数目小于进程P%d的最大需求数量，请重新输入。\n",i[36]+1,i[35]+1);
        goto input;
      }
    }

  printf("\n");printf("系统开始自动从进程集合中寻找Request进程。\n");
  va=value;   
  fi=finish;//链表L
  for(i[13]=0;i[13]<prn;i[13]++){finish[i[13]]=0;}
  for(i[17]=0;i[17]<prn;i[17]++){lock[i[17]]=-1;}
  for(i[18]=0;i[18]<prn;i[18]++){cancel[i[18]]=-1;}
  for(i[19]=0;i[19]<rsn;i[19]++){work[i[19]]=available[i[19]];}
  for(i[20]=0;i[20]<prn;i[20]++){costp[i[20]]=-1;}
  wo=work;



//从头遍历各个进程，以寻找Request进程
  for(i[6]=0;i[6]<prn;i[6]++)//外循环遍历各进程
  {
    for(i[7]=0;i[7]<rsn;i[7]++)//内循环遍历各种类型的资源
    {
      value[i[7]] = work[i[7]]-need[i[6]][i[7]];
    }
    if(test(va,rsn))
    {
      printf("进程P%d完成，写入链表L。\n",i[6]+1);
      for(i[11]=0;i[11]<rsn;i[11]++)
      {
        work[i[11]]=work[i[11]]+allocation[i[6]][i[11]];
        available[i[11]]=work[i[11]];
        allocation[i[6]][i[11]]=0;
      }
      finish[i[6]]=1;
      goto check1;
    }
  }
  if(i[6]==prn){printf("系统当前已经是死锁状态。\n");goto answer;}

check1:
  for(i[14]=0;i[14]<prn;i[14]++)//外循环遍历各进程
  {
    for(i[15]=0;i[15]<rsn;i[15]++)//内循环遍历各种类型的资源
    {
      value[i[15]]=work[i[15]]-need[i[14]][i[15]];
    }
    if((test(va,rsn))&&(finish[i[14]]==0))
    {
      printf("进程P%d完成，写入链表L。\n",i[14]+1);
      for(i[16]=0;i[16]<rsn;i[16]++)
      {
        work[i[16]]=work[i[16]]+allocation[i[14]][i[16]];
        available[i[16]]=work[i[16]];
        allocation[i[14]][i[16]]=0;
      }
      finish[i[14]]=1;counter=1;
    }
  }
  if(counter==1){counter=0;goto check1;}
  if(test1(fi,prn)){printf("此系统状态的资源分配图是可以完全简化的，");goto end1;}
  else printf("此系统状态的资源分配图是不可完全简化的，因此该系统状态将发生死锁。\n");

answer:
  lo=lock;
  cop=costp;
  ca=&cancel[0];
  for(i[8]=0;i[8]<prn;i[8]++)
  {
   if(finish[i[8]]==0){lock[pn]=i[8]+1;costp[pn]=cost[i[8]];pn++;}
  }
  printf("死锁的进程有：");Pr(pn,lo);printf("\n");//死锁状态下的各进程名
  printf("对应的代价是：");Pr(pn,cop);printf("\n");//各死锁进程对应的代价
  printf("开始采取措施解除死锁。\n");
//死锁的解除
  i[22]=0;  

begin:   
   canprs=lock[compare(cop,pn)]-1;//将代价最小的进程名赋给参数canprs
   costadd+=cost[canprs];//总代价加上撤销进程的代价
   printf("撤销代价最小的进程P%d,代价为%d。总代价已达%d。\n",canprs+1,cost[canprs],costadd);
   for(i[21]=0;i[21]<rsn;i[21]++)
   {
     work[i[21]]=work[i[21]]+allocation[canprs][i[21]];
     available[i[21]]=work[i[21]];
     allocation[canprs][i[21]]=0;
   }
   finish[canprs]=2;//将撤销的进程的finish赋值为2
   cancel[i[22]]=canprs+1;//撤销进程的进程名
   cn++;
   i[22]++;

   pn=0;//重新计算死锁进程的个数
   for(i[23]=0;i[23]<prn;i[23]++)//重新给死锁数组和代价数组赋值，
   {
    if(finish[i[23]]==0){lock[pn]=i[23]+1;costp[pn]=cost[i[23]];pn++;}
   }
//printf("pn=%d\n",pn);
check2:
   for(i[24]=0;i[24]<prn;i[24]++)//外循环遍历各进程
   {
    for(i[25]=0;i[25]<rsn;i[25]++)//内循环遍历各种类型的资源
    {
      value[i[25]]=work[i[25]]-need[i[24]][i[25]];
//printf("value[%d]=work[%d]-need[%d][%d]=%d-%d=%d\n",i[25],i[25],i[24],i[25],work[i[25]],need[i[24]][i[25]],value[i[25]]);
    }
    if((test(va,rsn)==1)&&(finish[i[24]]==0))
    {
      printf("进程P%d完成，写入链表L。\n",i[24]+1);
      for(i[26]=0;i[26]<rsn;i[26]++)
      {
        work[i[26]]=work[i[26]]+allocation[canprs][i[26]];
        available[i[26]]=work[i[26]];
        allocation[canprs][i[26]]=0;
      }
      finish[i[24]]=1;counter=1;
    }
   }  
   if(counter==1){counter=0;goto check2;}
   if(test(fi,prn))
   {
     pn=0;
     for(i[29]=0;i[29]<prn;i[29]++)
     {
       if(finish[i[29]]==0){lock[pn]=i[29]+1;costp[pn]=cost[i[29]];pn++;}
     }
     if(!test1(fi,prn))printf("系统的死锁状态没有解除。\n");
     printf("完成的进程有：");
     for(i[30]=0;i[30]<prn;i[30]++){if(finish[i[30]]==1)printf("%d ",i[30]+1);}printf("\n");
     printf("死锁的进程有：");Pr(pn,lo);printf("\n");//死锁状态下的各进程名
     printf("对应的代价是：");Pr(pn,cop);printf("\n");//各死锁进程对应的代价
     printf("撤销的进程有：");Pr(cn,ca);printf("\n");
     printf("\n");
     if(test12(fi,prn))goto end;
     goto begin;
   }


end:
   printf("系统的死锁状态成功解除，所花费的总代价是%d。\n",costadd);
end1:
   printf("再见\n");return 0;
}