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

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

结果：

初始化

输入作业

回收空间

总结：

经过这次的实验，我懂得了操作系统分配内存的一些基础知识，操作系统主要是寻找空闲区，然后有作业进来就自动寻找合适的空闲区，然后就插入此区域，释放内存后要观察此作业两边的情况，根据不同的情况，对回收的空间进行不一样的处理