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

1. 目的和要求

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 512
  5 
  6 struct partition {
  7     char    pn[10];
  8     int    begin;
  9     int    size;
 10     int    end;
 11     char    status;
 12 };
 13 struct partition    part[MAX];
 14 int            p = 0;   /*上次扫描结束处 */
 15 
 16 void Init()
 17 {
 18     int i;
 19     for ( i = 0; i < MAX; i++ )
 20         part[i].status = '-';
 21 
 22     strcpy( part[0].pn, "SYSTEM" );
 23     part[0].begin    = 0;
 24     part[0].size    = 100;
 25     part[0].status    = 'u';
 26 
 27     strcpy( part[1].pn, "-----" );
 28     part[1].begin    = 100;
 29     part[1].size    = 412;
 30     part[1].status    = 'f';
 31 
 32     for ( i = 0; i < MAX; i++ )
 33         part[i].end = part[i].begin + part[i].size;
 34 }
 35 
 36 
 37 void Output( int i ) /* 输出 */
 38 {
 39     printf( "	%s", part[i].pn );
 40     printf( "	%d", part[i].begin );
 41     printf( "	%d", part[i].size );
 42     printf( "	%d", part[i].end );
 43     printf( "	%c", part[i].status );
 44 }
 45 
 46 
 47 void ShowData() /* 显示数据 */
 48 {
 49     int    i;
 50     int    n;
 51      printf( "
================================================================" );
 52     printf( "
空闲分区表Free:" );
 53     printf( "
	No.	proname	begin	size	end	status" );
 54     printf( "
	------------------------------------------------" );
 55     n = 1;
 56     for ( i = 0; i < MAX; i++ )
 57     {
 58         if ( part[i].status == '-' )
 59             break;
 60         if ( part[i].status == 'f' )
 61         {
 62             printf( "
	No.%d", n );
 63             Output( i );
 64             n++;
 65         }
 66     }
 67     printf( "
" );
 68     printf( "
================================================================" );
 69     printf( "
已分配分区表Used:" );
 70     printf( "
	No.	proname	begin	size	end	status" );
 71     printf( "
	------------------------------------------------" );
 72     n = 1;
 73     for ( i = 0; i < MAX; i++ )
 74     {
 75         if ( part[i].status == '-' )
 76             break;
 77         if ( part[i].status == 'u' )
 78         {
 79             printf( "
	No.%d", n );
 80             Output( i );
 81             n++;
 82         }
 83     }
 84     printf( "
" );
 85     printf( "
" );
 86     printf( "
================================================================" );
 87     printf( "
内存使用情况，按起始址增长的排:" );
 88     printf( "
printf sorted by address:" );
 89     printf( "
	No.	proname	begin	size	end	status" );
 90     printf( "
	------------------------------------------------" );
 91     n = 1;
 92     for ( i = 0; i < MAX; i++ )
 93     {
 94         if ( part[i].status == '-' )
 95             break;
 96         printf( "
	No.%d", n );
 97         Output( i );
 98         n++;
 99     }
100     getch();
101 }
102 
103 
104 void Fit( int a, char workName[], int workSize ) /* 分配成'u'+'f' */
105 {
106     int i;
107     for ( i = MAX; i > a + 1; i-- )
108     {
109         if ( part[i - 1].status == '-' )
110             continue;
111         strcpy( part[i].pn, part[i - 1].pn );
112         part[i].begin    = part[i - 1].begin;
113         part[i].size    = part[i - 1].size;
114         part[i].end    = part[i - 1].end;
115         part[i].status    = part[i - 1].status;
116     }
117     strcpy( part[a + 1].pn, "-----" );
118     part[a + 1].begin    = part[a].begin + workSize;
119     part[a + 1].size    = part[a].size - workSize;
120     part[a + 1].end        = part[a].end;
121     part[a + 1].status    = 'f';
122     strcpy( part[a].pn, workName );
123     part[a].size    = workSize;
124     part[a].end    = part[a].begin + part[a].size;
125     part[a].status    = 'u';
126 }
127 
128 
129 void Allocation() /* 分配 */
130 {
131     int i;
132     int a;
133     int workSize;
134     char workName[10];
135     int pFree;
136     printf( "
请输入作业名称：" );
137     while(1)
138     {
139         scanf( "%s", &workName );
140         for(i=0;i<MAX;i++)
141         {
142             if(part[i].status=='u' && strcmp(workName,part[i].pn)==0)
143             {
144                 printf("该作业已存在，请重新输入作业名:");
145                 break;
146             }
147         }
148         if(i==MAX)
149             break;
150     }        
151     printf( "请输入作业大小(k)：" );
152     while(1)
153     {
154         scanf( "%d", &workSize );    
155         for ( i = 0; i < MAX; i++ )
156         {
157             if ( part[i].status == 'f' && part[i].size >= workSize )
158             {
159                pFree = i;
160               break;
161             }
162         }
163         if ( i == MAX )
164         {
165            printf( "
该作业大小超出最大可分配空间，请重新输入:" );    
166         }
167         else break;
168     }
169     printf( "
请选择分配算法：" );
170     printf( "
1、最先适应算法");
171     printf( "
2、下次适应算法" );
172     printf( "
3、最优适应算法" );
173     printf( "
请输入选项：" );
174     while ( 1 )
175     {
176         scanf( "%d", &a );
177         if ( a == 1 || a == 2 || a == 3 || a == 4 )
178             break;
179         else
180           printf( "输入错误，请重新输入：" );
181     }
182     switch ( a )
183     {
184     case 1:
185         for ( i = 0; i < MAX; i++ )
186             if ( part[i].status == 'f' && part[i].size >= workSize )
187                 break;
188         Fit( i, workName, workSize );
189         break;
190     case 2:
191         for ( p; p < MAX; p++ )
192         {
193             if ( p == MAX )
194                 p = 0;
195             if ( part[p].status == 'f' && part[p].size >= workSize )
196                 break;
197         }
198         Fit( p, workName, workSize );
199         break;
200     case 3:
201         for ( i = 0; i < MAX; i++ )
202             if ( part[i].status == 'f' && part[i].size >= workSize )
203                 if ( part[pFree].size > part[i].size )
204                     pFree = i;
205         Fit( pFree, workName, workSize );
206         break;
207     default:
208         break;
209     }
210     printf( "
分配成功！" );
211     getch();
212 }
213 
214 
215 void Merge() /* 合并连续的'f' */
216 {
217     int i = 0;
218     while ( i != MAX - 1 )
219     {
220         for ( i = 0; i < MAX - 1; i++ )
221         {
222             if ( part[i].status == 'f' )
223                 if ( part[i + 1].status == 'f' )
224                 {
225                     part[i].size    = part[i].size + part[i + 1].size;
226                     part[i].end    = part[i].begin + part[i].size;
227                     i++;
228                     for ( i; i < MAX - 1; i++ )
229                     {
230                         if ( part[i + 1].status == '-' )
231                         {
232                             part[i].status = '-';
233                             break;
234                         }
235                         strcpy( part[i].pn, part[i + 1].pn );
236                         part[i].begin    = part[i + 1].begin;
237                         part[i].size    = part[i + 1].size;
238                         part[i].end    = part[i + 1].end;
239                         part[i].status    = part[i + 1].status;
240                     }
241                     part[MAX - 1].status = '-';
242                     break;
243                 }
244         }
245     }
246 }
247 
248 
249 void Recovery() /* 回收分区 */
250 {
251     int    i;
252     char  workName[10];
253     printf( "
请输入回收的分区名称：" );
254     scanf( "%s", &workName );
255     if ( strcmp( workName, "SYSTEM" ) == 0 )
256     {
257         printf( "
该系统分区无法回收" );
258         return;
259     }
260   
261     for ( i = 0; i < MAX; i++ )
262     {
263         if ( strcmp( workName, part[i].pn ) == 0 )
264         {
265             strcpy( part[i].pn, "-----" );
266             part[i].status = 'f';
267             Merge();
268             printf( "
回收成功！" );
269             getch();
270             return;
271            
272         }
273     }
274     if ( i == MAX )
275     {
276         printf( "
找不到该分区" );
277         return;
278     }
279 }
280 
281 
282 void main()
283 {
284     int a;
285     Init();
286     printf( "
初始化，设内存容量%dk", MAX );
287     printf( "
系统从低地址部分开始使用，占用%dk", part[0].size );
288     printf( "
" );
289     while ( 1 )
290     {
291         printf( "
" );
292         printf( "
1、显示分区" );
293         printf( "
2、分配作业" );
294         printf( "
3、回收分区" );
295         printf( "
请输入选项：" );
296         while ( 1 )
297         {
298             scanf( "%d", &a );
299             if ( a == 1 || a == 2 || a == 3 )
300                 break;
301             printf( "输入错误，请重新输入：" );
302         }
303         switch ( a )
304         {
305         case 1:
306             ShowData();
307             break;
308         case 2:
309             Allocation();
310             break;
311         case 3:
312             Recovery();
313             break;
314         default:
315             break;
316         }
317     }
318 }

结果：