操作系统银行家算法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
",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
");
 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("
");
 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("
");
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("
");
132     }
133 }
134 int main()
135 {
136     int work[1000]= {0};
137     int pn,yn;
138     printf("Please input the number of the program
");
139     scanf("%d",&pn);
140     printf("Please input the number of the element
");
141     scanf("%d",&yn);
142     printf("Please input Max and Allocation of the program 
");
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 
");
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 
");
168         for(int i=0; i<pn; i++)
169             printf("%d  ",safeq[i]);
170         printf("
");
171         printf("is the one of the safe sequence 
");
172     }
173     else
174         printf("it is not safe now
");
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 
");
185             scanf("%d",&ex);
186             if(!ex)
187                 break;
188             printf("Please input the number of the request program 
");
189             scanf("%d",&num);
190             printf("Please input the Request 
");
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!
");
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!
");
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 
");
225                         for(int i=0; i<pn; i++)
226                             printf("%d  ",safeq[i]);
227                         printf("
");
228                         printf("is the one of the safe sequence 
");
229                         printf("complete !!!!!!!
");
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 
");
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 */