操作系统银行家算法C语言代码实现

大家好，又见面了，我是你们的朋友全栈君。

　　　　计算机操作系统课设需要，写了两个下午的银行家算法（陷在bug里出不来耽误了很多时间），参考计算机操作系统（汤子瀛）

　　　　实现过程中不涉及难度较大的算法，仅根据银行家算法的思想和步骤进行实现。以下为详细步骤：　　

　定义：

max1[ ][ ] : 最大需求矩阵,max1[i][j]为第i条进程的第j项资源的最大需求数目；

　　　 allocation[ ][ ] : 分配矩阵，allocation[i][j]为第i条进程已分得的第j项资源的数目；

　　　 need[ ][ ] : 需求矩阵，need[i][j]为第i条进程尚需要的第j项资源的数目；

　　　 available[ ] : 可利用资源量，available[i]为系统中第i项资源的可分配数目；

　　　request[ ][ ] : 请求矩阵，request[i][j]表示第i条进程对第j项资源的请求数目；//可以改成一维数组

　　　　int safe (int n,int m,int work) : n条进程，m项进程，返回值为1时当前状态安全，否则不安全；

　程序流程：

键盘输入max1矩阵，allocation矩阵，available数组，计算出need矩阵。
判断当前时刻系统的状态是否安全。true 转向3，false转向7　
判断当前时刻request<=need。true 转向4，false 转向7　
判断当前时刻request<=available。true 转向5，false 转向7
进行安全性算法检测。true 转向6，false 转向7
系统分配资源并继续等待指令。
系统不予分配资源并输出原因。

安全性算法：每次从第一个进程开始检测，如遇到所有的m项资源都可以满足时，work+=allocation，否则转入下一个进程的检测。两种情况跳出第20行的循环。

所有finish均为1，i无法置为-1 ，i==N时跳出循环
存在为0的finish，但直至i==N时，仍未有新的work<need出现(从最近的一次i==-1算起)，i==N时跳出循环

　　第50行进行检测区分上述两种情况，如安全返回1，否则返回0；

以下为完整的代码实现：(另附测试数据)

 1 #include<bits/stdc++.h>  2 int max1[1000][1000]= { 0};  3 int allocation[1000][1000]= { 0};  4 int need[1000][1000]= { 0};  5 int finish[1000]= { 0};  6 int available[1000]= { 0};  7 int request[1000][1000]= { 0};  8 int waitq[1000]= { 0};  9 int waitnum=0;  10 int safeq[1000]= { 0};  11 int safe (int N , int M ,int work[])  12 {  13 int s=0;  14 memset(finish,0,1000*sizeof(int));  15 for(int i=0; i<M; i++)  16  {  17 work[i]=available[i];  18  }  19 int flag=1;  20 for(int i=0; i<N; i++)  21  {  22 flag=1;  23 if(!finish[i])  24  {  25 for(int j=0; j<M; j++)  26  {  27 if(need[i][j]>work[j])  28  {  29 flag=0;  30 break;  31  }  32  }  33 if(flag)  34  {  35 for(int j=0; j<M; j++)  36  {  37 work[j]+=allocation[i][j];  38 printf(" %d ",work[j]);  39  }  40 for(int j=0; j<3; j++)  41 printf("%d ",available[j]);  42 printf("program %d\n",i);  43 safeq[s++]=i;  44 finish[i]=1;  45 i=-1;  46  }  47  }  48  }  49 int te=1;  50 for(int i=0; i<5; i++)  51 if(!finish[i])  52 te=0;  53 return te;  54 }  55 void print(int pn,int yn)  56 {  57 printf("current status\n");  58 char a='A';  59 int i2=0;  60 for(i2=0; i2<4; i2++)  61  {  62 switch(i2)  63  {  64 case 0:  65 printf("Max:");  66 for(int i=0; i<yn-1; i++)  67 printf(" ");  68 printf(" ");  69 break;  70 case 1:  71 printf("Allocation:");  72 for(int i=0; i<yn-3; i++)  73 printf(" ");  74 printf(" ");  75 break;  76 case 2:  77 printf("Need:");  78 for(int i=0; i<yn-1; i++)  79 printf(" ");  80 break;  81 case 3:  82 printf("Available:");  83 for(int i=0; i<yn-2; i++)  84 printf(" ");  85 printf(" ");  86 printf("\n");  87 break;  88  }  89  }  90 for(i2=0; i2<4; i2++)  91  {  92 switch(i2)  93  {  94 case 0:  95 for(int j=0; j<yn; j++)  96 printf("%c ",a+j);  97 break;  98 case 1:  99 for(int j=0; j<yn; j++) 100 printf("%c ",a+j); 101 break; 102 case 2: 103 for(int j=0; j<yn; j++) 104 printf("%c ",a+j); 105 break; 106 case 3: 107 for(int j=0; j<yn; j++) 108 printf("%c ",a+j); 109 break; 110 111  } 112  } 113 printf("\n"); 114 for(int i=0; i<pn; i++) 115  { 116 for(int j=0; j<yn; j++) 117  { 118 printf("%d ",max1[i][j]); 119  } 120 for(int j=0; j<yn; j++) 121  { 122 printf("%d ",allocation[i][j]); 123  } 124 for(int j=0; j<yn; j++) 125  { 126 printf("%d ",need[i][j]); 127  } 128 if(i==0) 129 for(int j=0; j<yn; j++) 130 printf("%d ",available[j]); 131 printf("\n"); 132  } 133 } 134 int main() 135 { 136 int work[1000]= { 0}; 137 int pn,yn; 138 printf("Please input the number of the program\n"); 139 scanf("%d",&pn); 140 printf("Please input the number of the element\n"); 141 scanf("%d",&yn); 142 printf("Please input Max and Allocation of the program \n"); 143 for(int i=0; i<pn; i++) 144  { 145 for(int j=0; j<yn; j++) 146  { 147 scanf("%d",&max1[i][j]); 148  } 149 for(int j=0; j<yn; j++) 150  { 151 scanf("%d",&allocation[i][j]); 152  } 153 for(int j=0; j<yn; j++) 154  { 155 need[i][j]=max1[i][j]-allocation[i][j]; 156  } 157  } 158 printf("Please input the Available \n"); 159 for(int i=0; i<yn; i++) 160  { 161 scanf("%d",&available[i]); 162 work[i]=available[i]; 163  } 164 165 if(safe(pn,yn,work)) 166  { 167 printf("it is safe now \n"); 168 for(int i=0; i<pn; i++) 169 printf("%d ",safeq[i]); 170 printf("\n"); 171 printf("is the one of the safe sequence \n"); 172  } 173 else 174 printf("it is not safe now\n"); 175 176 177 if(safe(pn,yn,work)) 178  { 179 while(1) 180  { 181 int num; 182 int ex; 183 int judge=1; 184 printf("if you want to exit , please input 0 else input 1 \n"); 185 scanf("%d",&ex); 186 if(!ex) 187 break; 188 printf("Please input the number of the request program \n"); 189 scanf("%d",&num); 190 printf("Please input the Request \n"); 191 for(int i=0; i<yn; i++) 192  { 193 scanf("%d",&request[num][i]); 194 if(request[num][i]>need[num][i]) 195  { 196 judge=0; 197 printf("error!\n"); 198 break; 199  } 200  } 201 if(judge) 202  { 203 int wait=0; 204 for(int i=0; i<yn; i++) 205  { 206 if(request[num][i]>available[i]) 207  { 208 wait=1; 209 printf("wait because request>available!\n"); 210 break; 211  } 212  } 213 if(!wait) 214  { 215 216 for(int j1=0; j1<yn; j1++) 217  { 218 available[j1]-=request[num][j1]; 219 allocation[num][j1]+=request[num][j1]; 220 need[num][j1]-=request[num][j1]; 221  } 222 if(safe(pn,yn,work)) 223  { 224 printf("it is safe now \n"); 225 for(int i=0; i<pn; i++) 226 printf("%d ",safeq[i]); 227 printf("\n"); 228 printf("is the one of the safe sequence \n"); 229 printf("complete !!!!!!!\n"); 230  } 231 else 232  { 233 for(int j1=0; j1<yn; j1++) 234  { 235 available[j1]+=request[num][j1]; 236 allocation[num][j1]-=request[num][j1]; 237 need[num][j1]+=request[num][j1]; 238  } 239 printf("wait because it is not safe \n"); 240  } 241  } 242 243  } 244  } 245  } 246  print(pn,yn); 247 } 248 249 /* 250 5 251 3 252 7 5 3 0 1 0 253 3 2 2 2 0 0 254 9 0 2 3 0 2 255 2 2 2 2 1 1 256 4 3 3 0 0 2 257 3 3 2 258 1 259 1 260 1 0 2 261 1 262 4 263 3 3 0 264 1 265 0 266 0 2 0 267 0 268 269 270 */