实验四主存空间的分配和回收

1.1. 实验目的

用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。

1.2. 实验要求

采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计。

（1）**设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行。

（2）或在程序运行过程，由用户指定申请与释放。

（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。把空闲区说明表的变化情况以及各作业的申请、释放情况显示。

2.实验内容

根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。

3.实验环境

可以选用Visual C++作为开发环境。也可以选用Windows下的VB，CB或其他可视化环境，利用各种控件较为方便。自主选择实验环境。

4.参考数据结构：

#include<stdio.h>

#include<conio.h>

#include<string.h>

#define MAX 24

struct partition{

char pn[10];

int begin;

int size;

int end; ////////

char status; //////////

};

typedef struct partition PART;

  1 #include <stdio.h>
  2 #include<conio.h>
  3 #include<string.h>
  4 #define MAX 100
  5 struct partition{
  6     char pn[10];
  7     int begin;
  8     int size;
  9     int end;   ////////
 10     char status;  //////////
 11     };
 12 typedef struct partition PART;
 13 PART p[MAX];
 14 int n;
 15 
 16 int msize = 7;
 17 int next = 0;
 18 
 19 void init()
 20 {
 21     p[0].begin = 0;
 22     p[0].end = 200;
 23     strcpy(p[0].pn, "SYSTEM");
 24     p[0].size = 200;
 25     p[0].status = 'u';
 26 
 27     p[1].begin = 200;
 28     p[1].end = 1024;
 29     strcpy(p[1].pn, "-----");
 30     p[1].size = p[1].end - p[1].begin;
 31     p[1].status = 'f';
 32 
 33     n = 2;
 34 }
 35 
 36 void show()
 37 {
 38     int x = 1;
 39 
 40     printf("空闲区表Free：
");
 41     printf("	No.	proname	begin	size	status
");
 42     for(int i = 0; i < n; i++)
 43     {
 44         if(p[i].status == 'f')
 45             printf("	No.%d	%s	%4d	%4d	%4c
", x++, p[i].pn, p[i].begin, p[i].size, p[i].status);
 46     }
 47     printf("

=========================================================
");
 48 
 49     printf("已分配分区表Used：
");
 50     printf("	No.	proname	begin	size	status
");
 51     for(i = 0, x = 1; i < n; i++)
 52     {
 53         if(p[i].status == 'u')
 54             printf("	No.%d	%s	%4d	%4d	%4c
", x++, p[i].pn, p[i].begin, p[i].size, p[i].status);
 55     }
 56 
 57     printf("

=========================================================
");
 58 
 59     printf("内存使用情况：
printf sorted by address:
");
 60     printf("	No.	proname	begin	size	status
");
 61     printf("	--------------------------------------
");
 62     for(i = 0, x = 1; i < n; i++)
 63     {
 64             printf("	No.%d	%s	%4d	%4d	%4c
", x++, p[i].pn, p[i].begin, p[i].size, p[i].status);
 65     }
 66 }
 67 
 68 void input(char name[], int * size)
 69 {    
 70     int x = 1;
 71 
 72     while(x)
 73     {
 74         printf("

请输入进程名称：");
 75         scanf("%s", name);
 76 
 77         for(int i = 0; i < n; i++)
 78         {    
 79             x = 0;
 80             if(strcmp(name, p[i].pn) == 0)
 81             {
 82                 x = 1;
 83                 printf("进程名称已存在，请重新输入!");                
 84                 break;
 85             }
 86         }
 87         
 88     }
 89     
 90     x = 1;
 91     scanf("!!!
");
 92     while(x)
 93     {
 94         printf("
请输入进程需要的空间大小：");
 95         scanf("%d", size);
 96 
 97         for(int i = 0; i < n; i++)
 98         {
 99             
100             if(p[i].size >= *size)
101             {
102                 x = 0;    
103                 break;
104             }
105         }
106         if(x)
107             printf("找不到适合的空间，请重新输入!");
108     }
109 
110 }
111 
112 int show_menu()
113 {
114     int x;
115     
116     printf("
(1)首次适应算法");
117     printf("
(2)循环首次适应算法");
118     printf("
(3)最佳适应算法");
119     printf("
(4)最坏适应算法");
120     printf("
请选择一种分配方式：");
121     scanf("%d", &x);
122     while(x < 1 || x > 4)
123     {
124         printf("
输入错误!");
125         printf("
请选择一种分配方式：");
126         scanf("%d", &x);
127     }
128 
129     return x;
130 }
131 
132 void first_fit(char name[], int size)
133 {
134     for(int i = 0; i < n; i++)
135     {
136         if(p[i].status == 'f')
137         {    
138             if(p[i].size - size < msize)
139             {
140                 strcpy(p[i].pn, name);
141                 p[i].status = 'u';
142                 break;
143             }
144             else
145             {
146                 strcpy(p[n].pn, p[i].pn);
147                 p[n].begin = p[i].begin + size;
148                 p[n].end = p[i].end;
149                 p[n].size = p[n].end - p[n].begin;
150                 p[n].status = 'f';
151                 strcpy(p[i].pn, name);
152                 p[i].end = p[i].begin + size;
153                 p[i].size = size;
154                 p[i].status = 'u';
155                 n++;
156                 break;
157             }
158         }
159     }
160     
161 }
162 
163 void next_fit(char name[], int size)
164 {
165     for(int i = next; i < n; i++)
166     {
167         if(p[i].status == 'f')
168         {    
169             if(p[i].size - size < msize)
170             {
171                 strcpy(p[i].pn, name);
172                 p[i].status = 'u';
173                 break;
174             }
175             else
176             {
177                 strcpy(p[n].pn, p[i].pn);
178                 p[n].begin = p[i].begin + size;
179                 p[n].end = p[i].end;
180                 p[n].size = p[n].end - p[n].begin;
181                 p[n].status = 'f';
182                 strcpy(p[i].pn, name);
183                 p[i].end = p[i].begin + size;
184                 p[i].size = size;
185                 p[i].status = 'u';
186                 n++;
187                 break;
188             }
189         }
190     }
191 }
192 
193 void best_fit(char name[], int size)
194 {
195     int x = 0;
196     int min = 10000;
197 
198     for(int i = 0; i < n; i++)
199     {
200         if(p[i].status == 'f')
201         {    
202             if(p[i].size < min && p[i].size >= size)
203             {
204                 min = p[i].size;
205                 x = i;
206             }
207         }
208     }
209 
210     if(p[x].size - size < msize)
211     {
212         strcpy(p[x].pn, name);
213         p[x].status = 'u';
214     }
215     else
216     {
217         strcpy(p[n].pn, p[x].pn);
218         p[n].begin = p[x].begin + size;
219         p[n].end = p[x].end;
220         p[n].size = p[n].end - p[n].begin;
221         p[n].status = 'f';
222         strcpy(p[x].pn, name);
223         p[x].end = p[i].begin + size;
224         p[x].size = size;
225         p[x].status = 'u';
226         n++;
227     }
228 }
229 
230 void worst_fit(char name[], int size)
231 {
232     int x = 0;
233     int max = 0;
234 
235     for(int i = 0; i < n; i++)
236     {
237         if(p[i].status == 'f')
238         {    
239             if(p[i].size > max)
240             {
241                 max = p[i].size;
242                 x = i;
243             }
244         }
245     }
246 
247     if(p[x].size - size < msize)
248     {
249         strcpy(p[x].pn, name);
250         p[x].status = 'u';
251     }
252     else
253     {
254         strcpy(p[n].pn, p[x].pn);
255         p[n].begin = p[x].begin + size;
256         p[n].end = p[x].end;
257         p[n].size = p[n].end - p[n].begin;
258         p[n].status = 'f';
259         strcpy(p[x].pn, name);
260         p[x].end = p[i].begin + size;
261         p[x].size = size;
262         p[x].status = 'u';
263         n++;
264     }
265 }
266 
267 void allocation()
268 {
269     char name[10];
270     int size;
271 
272     input(name, &size);
273     int x = show_menu();
274     
275     switch(x)
276     {
277     case 1:
278         first_fit(name, size);
279         break;
280     case 2:
281         next_fit(name, size);
282         break;
283     case 3:
284         best_fit(name, size);
285         break;
286     case 4:
287         worst_fit(name, size);
288         break;
289     }
290 
291     show();
292 }
293 
294 void move(int i)
295 {
296     while(i < n)
297     {
298         p[i-1] = p[i];
299         i++;
300     }
301     n--;
302 }
303 
304 void recycle()
305 {
306     char name[10];
307     int x = 0;
308 
309     printf("

请输入进程名称：");
310     scanf("%s", name);
311 
312     for(int i = 0; i < n; i++)
313     {    
314         if(strcmp(name, p[i].pn) == 0)
315         {
316             x = 1;    
317             break;
318         }
319     }
320     if(x == 0)
321         printf("

进程不存在。
");
322     else if(x == 1)
323     {
324         if(p[i-1].status == 'u' && p[i+1].status == 'u')
325         {
326             strcpy(p[i].pn, "-----");
327             p[i].status = 'f';
328         }
329         else if(p[i+1].status == 'f')
330         {
331             strcpy(p[i].pn, "-----");
332             p[i].status = 'f';
333             p[i].end = p[i+1].end;
334             p[i].size += p[i+1].size; 
335             move(i+2);
336             if(p[i-1].status == 'f')
337             {
338                 p[i-1].end = p[i].end;
339                 p[i-1].size += p[i].size;
340                 move(i+1);
341             }
342         }   
343         
344     }
345 
346     show();    
347 }
348 
349 int main(void)
350 {
351     int x = 0;
352 
353     printf("初始化：设置内存总容量为 1024k
系统从低地址部分开始占用 200k

");
354 
355     init();
356     show();
357     
358     printf("
1. 输入进程     2. 回收进程
");
359     scanf("%d", &x);
360     while(1)
361     {
362         if(x == 1)
363             allocation();
364         else if(x == 2)
365             recycle();
366 
367         printf("
1. 输入进程     2. 回收进程
");
368         scanf("%d", &x);
369     }
370     
371     
372 
373     return 0;
374 }