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 } 運作結果：
配置設定：
回收：