1. 目的和要求
1.1. 实验目的
用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。
1.2. 实验要求
采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计。
（1）**设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行。
（2）或在程序运行过程，由用户指定申请与释放。
（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。
把空闲区说明表的变化情况以及各作业的申请、释放情况显示。
2. 实验内容
根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。
3. 实验环境
可以选用Visual C++作为开发环境。也可以选用Windows下的VB，CB或其他可视化环境，利用各种控件较为方便。自主选择实验环境。
1 #include<stdio.h>
2 #include<conio.h>
3 #include<malloc.h>
4 #include<string.h>
5 #define MAX 24
6 struct partition{
7 char pn[10]; //作业名
8 int begin; //开始时间
9 int size; //内存大小
10 int end; //结束时间
11 char status; //状态
12 struct partition *next;
13 };
14 typedef struct partition PART;
15 PART *head;
16 //初始化used表
17 PART *InitListu()
18 {
19 PART *k;
20 k= (PART *)malloc(sizeof(PART));
21 strcpy(k->pn,"SYSTEM");
22 k->begin=0;
23 k->size=100;
24 k->end=100;
25 k->status='u';
26 k->next=NULL;
27 return k;
28 }
29 //初始化free表
30 PART *InitListf()
31 {
32 PART *k;
33 k= (PART *)malloc(sizeof(PART));
34 strcpy(k->pn,"------");
35 k->begin=100;
36 k->size=412;
37 k->status='f';
38 k->end=512;
39 k->next=NULL;
40 return k;
41 }
42 //输出空闲区表Free
43 void Printfree()
44 {
45 printf("空闲区表Free:\n");
46 printf("No. proname begin size status\n");
47 PART *free=head->next;
48 int i=1;
49 while(free!=NULL)
50 {
51 if(free->status=='f')
52 {
53 printf("No.%d\t%s\t%d\t%d\t%c",i,free->pn,free->begin,free->size,free->status);
54 i++;
55 printf("\n");
56 }
57 free=free->next;
58 }
59 }
60 //输出已分配分区表Used
61 void Printused()
62 {
63 printf("已分配分区表Used:\n");
64 printf("No. proname begin size status\n");
65 PART *used=head->next;
66 int i=1;
67 while(used!=NULL)
68 {
69 if(used->status=='u')
70 {
71 printf("No.%d\t%s\t%d\t%d\t%c",i,used->pn,used->begin,used->size,used->status);
72 i++;
73 printf("\n");
74 }
75 used=used->next;
76 }
77 }
78 //输出所以作业
79 void Print()
80 {
81 printf("内存使用情况，按起始地址增长的排:\n");
82 printf("printf sorted by address:\n");
83 printf("No. proname begin size status\n");
84 PART *total=head->next;
85 int i=1;
86 while(total!=NULL)
87 {
88 printf("No.%d\t%s\t%d\t%d\t%c",i,total->pn,total->begin,total->size,total->status);
89 i++;
90 printf("\n");
91 total=total->next;
92 }
93 }
94 //算法菜单
95 void menu()
96 {
97
98 printf("1) 首次适应算法\n");
99 printf("2) 循环首次适应算法\n");
100 printf("3) 最佳适应算法\n");
101 printf("4) 最坏适应算法:\n");
102
103 }
104 //查找是否已存在作业名
105 PART *searchname(char name[10])
106 {
107 PART *rear;
108 rear=head->next;
109 while((rear!=NULL)&&(strcmp(rear->pn,name)!=0))
110 rear=rear->next;
111 return rear;
112 }
113 //查找是否有足够大的空闲内存
114 PART *searchsize(int size,PART *temp)
115 {
116 PART *rear;
117 rear=head->next;
118 while(rear!=NULL)
119 {
120 if(rear->status=='f')
121 {
122 if(rear->size>=size)
123 {
124 return rear;
125 }
126 else
127 rear=rear->next;
128 }
129 else
130 rear=rear->next;
131 }
132 return rear;
133 }
134 // 首次适应算法
135 void FF(PART *p)
136 {
137 PART *q,*rear;
138 rear=q=head->next;
139 while(rear!=NULL)
140 {
141 if(rear->status=='f')//判断空闲区
142 {
143 if(rear->size>=p->size)//判断空闲区的大小
144 {
145 //添加结点（新作业）
146 p->status='u';
147 p->begin=rear->begin;
148 p->end=p->begin+p->size;
149 p->next=NULL;
150 q->next=p;
151 rear->begin=p->end;
152 if(rear->size==p->size)
153 p->next=rear->next;
154 else
155 {
156 rear->size=rear->size-p->size;
157 p->next=rear;
158 }
159 //打印输出
160 Printfree();
161 Printused();
162 Print();
163 return;
164 }
165 else
166 { //遍历结点
167 q=rear;
168 rear=q->next;
169 }
170
171 }
172 else
173 { //遍历结点
174 q=rear;
175 rear=q->next;
176 }
177
178 }
179
180 }
181 //查找满足新作业的最大或最小空闲区
182 void sear(PART *p,PART *temp,int n)
183 {
184 PART *rear=head->next;
185 while(rear!=NULL)
186 {
187 if(rear->status=='f')
188 {
189 if(rear->size>=p->size)
190 {
191 if(n==3)
192 {
193 if(rear->size<temp->size) //最小（最优）
194 temp=rear;
195 else
196 rear=rear->next;
197 }
198 if(n==4)
199 {
200 if(rear->size>temp->size) //最大（最坏）
201 temp=rear;
202 else
203 rear=rear->next;
204 }
205 }
206 else
207 rear=rear->next;
208 }
209 else
210 rear=rear->next;
211 }
212 }
213 // 最佳适应算法 和 最坏适应算法
214 void BF_WF(PART *p,PART *temp,int n)
215 {
216 PART *q,*rear;
217 sear(p,temp,n);
218 rear=head->next;
219 while((rear!=NULL)&&(rear!=temp)) //查找前一结点和当前结点
220 {
221 q=rear;
222 rear=q->next;
223 }
224 //添加新作业
225 p->status='u';
226 p->begin=rear->begin;
227 p->end=p->begin+p->size;
228 p->next=NULL;
229 q->next=p;
230 rear->begin=p->end;
231 if(rear->size==p->size)
232 p->next=rear->next;
233 else
234 {
235 rear->size=rear->size-p->size;
236 p->next=rear;
237 }
238 Printfree();
239 Printused();
240 Print();
241 }
242 //分配输入
243 void input()
244 {
245 PART *p,*temp;
246 char name[10];
247 int size;
248 int n;
249 temp = (PART *)malloc(sizeof(PART));
250 lab1: printf("输入作业名称:");
251 scanf("%s",name);
252 if(searchname(name)==NULL) //判断作业是否已经存在
253 {
254 p = (PART *)malloc(sizeof(PART));
255 strcpy(p->pn,name);
256 }
257 else
258 {
259 printf("作业已经存在，请重新输入:\n");
260 goto lab1;
261 }
262 lab2: printf("请输入作业所占空间大小:"); //判断是否有足够大的空闲区
263 scanf("%d",&size);
264 temp=searchsize(size,temp);
265 if(temp!=NULL)
266 {
267 p->size=size;
268 }
269 else
270 {
271 printf("没有剩余的空闲区域中，请重新输入:\n");
272 goto lab2;
273 }
274 //选择算法
275 menu();
276 printf("请选择算法:");
277 scanf("%d",&n);
278 switch (n)
279 {
280 case 1:
281 FF(p);
282 break;
283 /* case 2:
284 CF(p);
285 break;*/
286 case 3:
287 BF_WF(p,temp,n);
288 break;
289 case 4:
290 BF_WF(p,temp,n);
291 break;
292 }
293 }
294 //回收
295 void recycle()
296 {
297 PART *q,*rear,*temp;
298 char pname[10];
299 temp = (PART *)malloc(sizeof(PART));
300 lab3: printf("请输入要终止的作业名:");
301 scanf("%s",pname);
302 if(searchname(pname)==NULL) //判断是否存在该作业
303 {
304 printf("作业不存在，请重新输入:\n");
305 goto lab3;
306 }
307 else
308 {
309 rear=head->next;
310 temp=searchname(pname);
311 while((rear!=NULL)&&(rear!=temp))//查找前一节点和当前节点
312 {
313 q=rear;
314 rear=q->next;
315 }
316 if(q->status=='u'&&rear->next->status=='u')//前后被分配
317 {
318 strcpy(rear->pn,"------");
319 rear->status='f';
320 }
321 else if(q->status=='u'&&rear->next->status=='f')//前者分配后者空闲
322 {
323 strcpy(rear->pn,"------");
324 rear->status='f';
325 rear->size=rear->size+rear->next->size;
326 rear->end=rear->next->end;
327 rear->next=rear->next->next;
328 }
329 else if(q->status=='f'&&rear->next->status=='u')//前者空闲后者分配
330 {
331 q->end=rear->end;
332 q->size=rear->size+q->size;
333 q->next=rear->next;
334 }
335 else if(q->status=='f'&&rear->next->status=='f')//前后空闲
336 {
337 q->end=rear->next->end;
338 q->size=rear->size+q->size+rear->next->size;
339 q->next=rear->next->next;
340 }
341 Printfree();
342 Printused();
343 Print();
344 }
345 }
346 //主函数
347 void main()
348 {
349 int cho;
350 printf("初始化,设内存总容量512k\n");
351 printf("系统从低地址部分开始使用,占用100k\n");
352 head = (PART *)malloc(sizeof(PART));
353 head->next=InitListu();
354 head->next->next=InitListf();
355 Printfree();
356 Printused();
357 Print();
358 while(1)
359 {
360 lab4: printf("1 分配 2 回收 3 退出\n");
361 printf("请选择:");
362 scanf("%d",&cho);
363 if(cho==1)
364 input();
365 else if(cho==2)
366 recycle();
367 else if(cho==3)
368 return;
369 else
370 {
371 printf("输入错误,请重新输入:\n");
372 goto lab4;
373 }
374 }
375 printf("\n");
376 } 运行结果：
分配：
回收：