银行家问题及其解决

银行家算法及其实现

对于每种资源类型由多个实例的资源分配系统，资源分配图算法就不再适用。银行家算法时一种适用于这种系统的死锁避免算法。这个项目实现了一个银行家算法。其实该算法的想法很简单，只是实现起来要注重很多细节。下面来分别讲述。

一.数据读入

基本的数据结构如下：

1
2
3
4
int available[NUMBER_OF_RESOURCES];
int maximum[NUMBER_OF_CUTSOMERS][NUMBER_OF_RESOURCES];
int allocation[NUMBER_OF_CUTSOMERS][NUMBER_OF_RESOURCES];
int need[NUMBER_OF_CUTSOMERS][NUMBER_OF_RESOURCES];

读入分为三部分，首先从命令行中读入资源总量，然后从文件中读入每个进程可能申请到的最多资源，最后不断接收用户轮询。读入的时候比较繁琐，这又是一个纯处理字符串的范例，我们就架while循环来做就好。还是要注意读入数据时使用的函数。我们这里使用fgetc()来一个一个的读入。要输出来看可以用fputs().他们的参数都是输入流和输出流。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int index=0;
   char current;
   int linenum=0;
   current = fgetc(readin);
   
   while(current!='\0'&&current!=EOF)
   {
      if(current=='\n')
      {
          index=0;++linenum;
           current = fgetc(readin);
          continue;
      }
      if(current==',')
      {
           current = fgetc(readin);
          continue;
      }
      if(current>='0'&&current<='9')
      {
          int temp=current-'0';
           current = fgetc(readin);
          while(current>='0'&&current<='9')
          {
              temp=temp*10+(current-'0');
               current = fgetc(readin);
          }
          maximum[linenum][index]=need[linenum][index]=temp;
          ++index;
      }
   }

然后关于轮询，我们这里用fgets()函数一股脑的读入指令再处理。比较指令的时候采用strncmp()函数。这里的细节是要加上一些异常判断，比如看一看输入的用户ID是否不合法，然后对于那种两位数的输入，要再套一个while循环处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
if(!strncmp(command,"RQ",2))
       {
           int customernum;
           int request[NUMBER_OF_RESOURCES];

           int index=0;
           int i=3;
           int temp=command[i]-'0';
           ++i;
           while(command[i]!='\0'&&command[i]!=' ')
           {
               temp=temp*10+(command[i]-'0');
               ++i;
           }
           customernum=temp;
           temp=0;
           while(command[i]!='\0'&&command[i]!='\n')
           {
               if(command[i]>'9'||command[i]<'0')
               {
                   ++i;
                   continue;
               }
                while(command[i]!='\0'&&command[i]!=' '&&command[i]!='\n')
               {
                   temp=temp*10+(command[i]-'0');
                   ++i;
               }
               request[index]=temp;
               temp=0;
               ++index;
           }
           //customernum and request[] is ready
           if(request_resources(customernum,request)==0)
           {
               printf("request success\n");
           }
           else printf("This request is denied\n");
           printf("banker@_@>");
           continue;
       }

二.算法实现

1.安全算法及其实现

哎哟，这个你就看恐龙书照着打嘛。

2.资源请求算法及其实现

哎哟，这个你也看恐龙书照着打嘛。首先我们假定系统可以分配给进程$$p_i$$请求的资源，并修改状态。如果该修改过的状态是安全的（调用一次我们的安全检查函数），那就执行，并保留该状态。如果不安全，注意要把修改过的状态改回来。

1
2
3
4
5
6
7
8
if(issafe())return 0;
   for(int i=0;i<NUMBER_OF_RESOURCES;i++)
  {
      available[i]+=request[i];
      allocation[customer_num][i]-=request[i];
      need[customer_num][i]+=request[i];
  }
    return -1;

三.测试程序

给每种资源数量都设置为10，用*命令查看一下系统状态：

然后我们就创建了一些进程来疯狂消耗我们的系统资源，注意到我的程序还是比较鲁棒的，它可以针对不合法的输入进行批判

可以看到最后资源终于苟不住了。我们再来查看一下系统状态：

于是我们尝试着释放一些资源再来查看一下系统状态：

可以看到该测试总体来说是比较成功的。

四.完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<unistd.h>
#include<math.h>
#define NUMBER_OF_CUTSOMERS 5
#define NUMBER_OF_RESOURCES 4

//data structures
int available[NUMBER_OF_RESOURCES];
int maximum[NUMBER_OF_CUTSOMERS][NUMBER_OF_RESOURCES];
int allocation[NUMBER_OF_CUTSOMERS][NUMBER_OF_RESOURCES];
int need[NUMBER_OF_CUTSOMERS][NUMBER_OF_RESOURCES];

int min(int a,int b)
{
    return (a<b)?a:b;
}
int lessthan(int vector1[], int vector2[])
{
    for(int i=0;i<NUMBER_OF_RESOURCES;i++)
    {
        if(vector1[i]>vector2[i])return 0;
    }
    return 1;
}
int issafe()
{
    int work[NUMBER_OF_RESOURCES];
    for(int i=0;i<NUMBER_OF_RESOURCES;i++)
    {
        work[i]=available[i];
    }
    int finish[NUMBER_OF_CUTSOMERS];
    for(int i=0;i<NUMBER_OF_CUTSOMERS;i++)
    {
        finish[i]=0;
    }
    int numoffinish=0;
    while(numoffinish<NUMBER_OF_CUTSOMERS){
        int customer_index;
      for(customer_index=0;customer_index<NUMBER_OF_CUTSOMERS;customer_index++)
        {
            if(!finish[customer_index]&&lessthan(need[customer_index],work))
                {
                    finish[customer_index]=1;
                    for(int i=0;i<NUMBER_OF_RESOURCES;i++)
                    {
                        work[i]+=allocation[customer_index][i];
                    }
                    ++numoffinish;
                    break;
                }
        
        }
        if(customer_index==NUMBER_OF_CUTSOMERS)return 0;
    }
    return 1;
}
//functions
int request_resources(int customer_num,int request[])
{
    if(customer_num>=NUMBER_OF_CUTSOMERS||customer_num<0)
    {
        printf("invalid customer ID\n");
        return -1;
    }
  if(!lessthan(request,need[customer_num]))
  {
      printf("request exceeds need\n");
      return -1;
  }
  if(!lessthan(request,available))
  {
      printf("no sufficient resource ,wait\n");
      return -1;
  }
  for(int i=0;i<NUMBER_OF_RESOURCES;i++)
  {
      available[i]-=request[i];
      allocation[customer_num][i]+=request[i];
      need[customer_num][i]-=request[i];
  }
  if(issafe())return 0;
   for(int i=0;i<NUMBER_OF_RESOURCES;i++)
  {
      available[i]+=request[i];
      allocation[customer_num][i]-=request[i];
      need[customer_num][i]+=request[i];
  }
    return -1;
}


void release_resources(int customer_num,int release[])
{
    if(customer_num>=NUMBER_OF_CUTSOMERS||customer_num<0)
    {
        printf("invalid customer ID\n");
        return ;
    }
   for(int i=0;i<NUMBER_OF_RESOURCES;i++)
   {
       int offset = min(release[i],allocation[customer_num][i]);
       allocation[customer_num][i]-=offset;
       available[i]+=offset;
   }
}
void tell()
{
    printf("avaliable resources:\n");
    for(int i=0;i<NUMBER_OF_RESOURCES;i++)
    {
        printf("the number of resource type %d is %d \n",i,available[i]);
    }
    printf("maximum request is \n");
    for(int i=0;i<NUMBER_OF_CUTSOMERS;i++)
    {
        for(int j=0;j<NUMBER_OF_RESOURCES;j++)
        {
            printf("%d ",maximum[i][j]);
        }
        printf("\n");
    }
    printf("current allocation is \n");
    for(int i=0;i<NUMBER_OF_CUTSOMERS;i++)
    {
        for(int j=0;j<NUMBER_OF_RESOURCES;j++)
        {
            printf("%d ",allocation[i][j]);
        }
        printf("\n");
    }
    printf("resource still in need is \n");
    for(int i=0;i<NUMBER_OF_CUTSOMERS;i++)
    {
        for(int j=0;j<NUMBER_OF_RESOURCES;j++)
        {
            printf("%d ",need[i][j]);
        }
        printf("\n");
    }

}
int main(int argc,char* argv[])
{
    if(argc!=1+NUMBER_OF_RESOURCES)
    {
        printf("What are you doing?Please reinput\n");
        return 0;
    }
    //initialization
    for(int i=0;i<NUMBER_OF_RESOURCES;i++)
    {
        available[i]=atoi(argv[i+1]);
    }
    
    FILE *readin;
    readin = fopen("max.txt","r");
    if(!readin)
    {
        printf("Please make sure the file ->max.txt<- is of\n ");
        return 0;
    }
    
    int index=0;
    char current;
    int linenum=0;
    current = fgetc(readin);
    
    while(current!='\0'&&current!=EOF)
    {
       if(current=='\n')
       {
           index=0;++linenum;
            current = fgetc(readin);
           continue;
       }
       if(current==',')
       {
            current = fgetc(readin);
           continue;
       }
       if(current>='0'&&current<='9')
       {
           int temp=current-'0';
            current = fgetc(readin);
           while(current>='0'&&current<='9')
           {
               temp=temp*10+(current-'0');
                current = fgetc(readin);
           }
           maximum[linenum][index]=need[linenum][index]=temp;
           ++index;
       }

    }
    //test input
    /*for(int i=0;i<NUMBER_OF_CUTSOMERS;i++)
    {
        for(int j =0;j<NUMBER_OF_RESOURCES;j++)
        printf("%d ",maximum[i][j]);
        printf("\n");
    }*/
    char command[20];printf("banker@_@>");
    while(fgets(command,20,stdin))
    { 
        if(!strncmp(command,"exit",4)){printf("goodbye world!"); return 0;}
        if(!strncmp(command,"*",1)){tell();printf("banker@_@>");continue;}
        if(!strncmp(command,"RQ",2))
        {
            int customernum;
            int request[NUMBER_OF_RESOURCES];

            int index=0;
            int i=3;
            int temp=command[i]-'0';
            ++i;
            while(command[i]!='\0'&&command[i]!=' ')
            {
                temp=temp*10+(command[i]-'0');
                ++i;
            }
            customernum=temp;
            temp=0;
            while(command[i]!='\0'&&command[i]!='\n')
            {
                if(command[i]>'9'||command[i]<'0')
                {
                    ++i;
                    continue;
                }
                 while(command[i]!='\0'&&command[i]!=' '&&command[i]!='\n')
                {
                    temp=temp*10+(command[i]-'0');
                    ++i;
                }
                request[index]=temp;
                temp=0;
                ++index;
            }
            //customernum and request[] is ready
            if(request_resources(customernum,request)==0)
            {
                printf("request success\n");
            }
            else printf("This request is denied\n");
            printf("banker@_@>");
            continue;
        }
        if(!strncmp(command,"RL",2))
        {
            int customernum;
            int release[NUMBER_OF_RESOURCES];
            int index=0;
            int i=3;
            int temp=command[i]-'0';
            ++i;
            while(command[i]!='\0'&&command[i]!=' ')
            {
                temp=temp*10+(command[i]-'0');
                ++i;
            }
            customernum=temp;
            temp=0;
            while(command[i]!='\0'&&command[i]!='\n')
            {
                if(command[i]>'9'||command[i]<'0')
                {
                    ++i;
                    continue;
                }
                 while(command[i]!='\0'&&command[i]!=' '&&command[i]!='\n')
                {
                    temp=temp*10+(command[i]-'0');
                    ++i;
                }
                release[index]=temp;
                temp=0;
                ++index;
            }
            release_resources(customernum,release);
            printf("banker@_@>");
            continue;
        }
        printf("Wrong command,shu ni ma ne\n");
        printf("banker@_@>");
    }
return 0;
}
计算机科学
操作系统

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！