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

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

专业：商业软件工程一班姓名：容杰龙学号：201406114157

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;

5、源代码

  1 #include <stdio.h>
  2 #include <conio.h>
  3 #include <string.h>
  4 #define MAX 512  //设置总内存大小为512k
  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     strcpy( part[0].pn, "SYSTEM" );
 22     part[0].begin    = 0;
 23     part[0].size    = 100;
 24     part[0].status    = 'u';
 25 
 26 
 27     strcpy( part[1].pn, "-----" );
 28     part[1].begin    = 100;
 29     part[1].size    = 100;
 30     part[1].status    = 'f';
 31     strcpy( part[2].pn, "A" );
 32     part[2].begin    = 200;
 33     part[2].size    = 50;
 34     part[2].status    = 'u';
 35     strcpy( part[3].pn, "-----" );
 36     part[3].begin    = 250;
 37     part[3].size    = 50;
 38     part[3].status    = 'f';
 39     strcpy( part[4].pn, "B" );
 40     part[4].begin    = 300;
 41     part[4].size    = 100;
 42     part[4].status    = 'u';
 43     strcpy( part[5].pn, "-----" );
 44     part[5].begin    = 400;
 45     part[5].size    = 112;
 46     part[5].status    = 'f';
 47     for ( i = 0; i < MAX; i++ )
 48         part[i].end = part[i].begin + part[i].size;
 49 }
 50 
 51 
 52 void Output( int i ) //以行的形式输出结构体的数据
 53 {
 54     printf( "	%s", part[i].pn );
 55     printf( "	%d", part[i].begin );
 56     printf( "	%d", part[i].size );
 57     printf( "	%d", part[i].end );
 58     printf( "	%c", part[i].status );
 59 }
 60 
 61 
 62 void Show() //显示分区 
 63 {
 64     int    i;
 65     int    n; //用n来记录分区的个数
 66     printf( "
================================================================" );
 67     printf( "
已分配分区表Used:" );
 68     printf( "
	No.	proname	begin	size	end	status" );
 69     printf( "
	------------------------------------------------" );
 70     n = 1;
 71     for ( i = 0; i < MAX; i++ )
 72     {
 73         if ( part[i].status == '-' )
 74             break;
 75         if ( part[i].status == 'u' )
 76         {
 77             printf( "
	No.%d", n );
 78             Output( i );
 79             n++;// 记录已分配使用的分区个数
 80         }
 81     }
 82     printf( "
" );
 83     printf( "
================================================================" );
 84     printf( "
空闲分区表Free:" );
 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         if ( part[i].status == 'f' )
 93         {
 94             printf( "
	No.%d", n );
 95             Output( i );
 96             n++;  //记录空闲分区的个数
 97         }
 98     }
 99     printf( "
" );
100     printf( "
" );
101     printf( "
================================================================" );
102     printf( "
内存使用情况，按起始址增长的排:" );
103     printf( "
printf sorted by address:" );
104     printf( "
	No.	proname	begin	size	end	status" );
105     printf( "
	------------------------------------------------" );
106     n = 1;
107     for ( i = 0; i < MAX; i++ )
108     {
109         if ( part[i].status == '-' )
110             break;
111         printf( "
	No.%d", n );
112         Output( i );
113         n++;//记录已分配分区以及空闲分区之和的总个数
114     }
115     getch();
116 }
117 
118 void Fit( int a, char workName[], int workSize ) //新作业把一个分区分配成两个分区：已使用分区和空闲分区 
119 {
120     int i;
121     for ( i = MAX; i > a + 1; i-- )
122     {
123         //通过逆向遍历，把在a地址后的所有分区往后退一个分区，目的在于增加一个分区
124         if ( part[i - 1].status == '-' )
125             continue;
126         part[i]=part[i-1];
127     }
128     strcpy( part[a + 1].pn, "-----" );
129     part[a + 1].begin    = part[a].begin + workSize;
130     part[a + 1].size    = part[a].size - workSize;
131     part[a + 1].end        = part[a].end;
132     part[a + 1].status    = 'f';
133     strcpy( part[a].pn, workName );
134     part[a].size    = workSize;
135     part[a].end    = part[a].begin + part[a].size;
136     part[a].status    = 'u';
137 }
138 
139 
140 void Allocation() // 分配 
141 {
142     int    i;
143     int    a;
144     int    workSize;
145     char    workName[10];
146     int    pFree;
147     printf( "
请输入作业名称：" );
148     scanf( "%s", &workName );
149     for(i=0;i<MAX;i++)
150     {
151         if(!strcmp(part[i].pn,workName))//判断作业名称是否已经存在
152         {
153             printf("
作业已经存在，不必再次分配！
");
154             return;
155         }
156     }
157     printf( "请输入作业大小(k)：" );
158     scanf( "%d", &workSize );
159     for ( i = 0; i < MAX; i++ )//通过循环在空闲区找是否有适合区间存储作业
160     {
161         if ( part[i].status == 'f' && part[i].size >= workSize )
162         {
163             pFree = i;
164             break;
165         }
166     }
167     if ( i == MAX )
168     {
169         printf( "
该作业大小超出最大可分配空间" );
170         getch();
171         return;
172     }
173     printf( "
请选择分配算法：" );
174     printf( "
1、首次适应算法(FF)" );
175     printf( "
2、循环首次适应算法(NF)" );
176     printf( "
3、最佳适应算法(BF)" );
177     printf( "
4、最坏适应算法(WF)" );
178     printf( "
请输入选项：" );
179     while ( 1 )
180     {
181         scanf( "%d", &a );
182         if ( a == 1 || a == 2 || a == 3 || a == 4 )
183             break;
184         printf( "输入错误，请重新输入：" );
185     }
186     switch ( a )
187     {
188     case 1:
189         for ( i = 0; i < MAX; i++ )//首次适应算法(按地址从低到高查找)
190             if ( part[i].status == 'f' && part[i].size >= workSize )
191                 break;
192         Fit( i, workName, workSize );
193         break;
194     case 2:
195         for ( p; p <= MAX; p++ )//循环首次适应算法
196         {
197             if ( p == MAX )//如果p指向地址末尾还没找到适合区间，则循环返回首地址0，继续寻找
198                 p = 0;      
199             if ( part[p].status == 'f' && part[p].size >= workSize )
200                 break;
201         }
202         Fit( p, workName, workSize );
203         break;
204     case 3:
205         for ( i = 0; i < MAX; i++ )//最佳适应算法
206             if ( part[i].status == 'f' && part[i].size >= workSize )
207                 if ( part[pFree].size > part[i].size )
208                     pFree = i;//通过遍历所有区间，每次都找到最小空闲分区进行分配
209         Fit( pFree, workName, workSize );
210         break;
211     case 4:
212         for ( i = 0; i < MAX; i++ )//最坏适应算法
213             if ( part[i].status == 'f' && part[i].size >= workSize )
214                 if ( part[pFree].size < part[i].size )
215                     pFree = i;//通过遍历所有区间，每次都找到最大空闲区分配
216         Fit( pFree, workName, workSize );
217         break;
218     default:
219         break;
220     }
221     printf( "
分配成功！" );
222     getch();
223 }
224 
225 
226 void Merge() //合并连续的空闲分区 
227 {
228     int i = 0;
229     while ( i != MAX - 1 )
230     {
231         for ( i = 0; i < MAX - 1; i++ )
232         {
233             if ( part[i].status == 'f' )
234                 if ( part[i + 1].status == 'f' )
235                 {
236                     part[i].size    = part[i].size + part[i + 1].size;
237                     part[i].end    = part[i].begin + part[i].size;
238                     i++;
239                     for ( i; i < MAX - 1; i++ )
240                     {
241                         if ( part[i + 1].status == '-' )
242                         {
243                             part[i].status = '-';
244                             break;
245                         }
246                        
247                         part[i]=part[i+1];
248                     }
249                     part[MAX - 1].status = '-';
250                     break;
251                 }
252         }
253     }
254 }
255 
256 
257 void Recovery() // 回收分区 
258 {
259     int    i;
260     int    number;
261     int    n=0;
262     printf( "
请输入回收的分区号：" );
263     scanf( "%d", &number );
264     if ( number == 1 )
265     {
266         printf( "
系统分区无法回收" );
267         return;
268     }
269     
270     for ( i = 0; i < MAX; i++ )//通过循环查找要回收的已使用分区区号
271     {
272         if ( part[i].status == 'u' )
273         {
274             n++;
275             if ( n == number )
276             {
277                 strcpy( part[i].pn, "-----" );
278                 part[i].status = 'f';
279             }
280         }
281     }
282     if ( i == MAX - 1 )
283     {
284         printf( "
找不到分区" );
285         return;
286     }
287     Merge();//合并连续的空闲分区
288     printf( "
回收成功！" );
289     getch();
290 }
291 
292 
293 void main()
294 {
295     int selection;
296     Init();
297     printf( "初始化，设内存容量%dk", MAX );
298     printf( "
系统从低地址部分开始使用，占用%dk", part[0].size );
299     while ( 1 )
300     {
301         printf( "
----------选择----------" );
302         printf( "
0、退出系统" );
303         printf( "
1、显示分区" );
304         printf( "
2、分配作业" );
305         printf( "
3、回收分区" );
306         printf( "
请选择：" );
307         while ( 1 )
308         {
309             scanf( "%d", &selection );
310             if ( selection == 0 ||selection == 1 || selection == 2 || selection == 3 )
311                 break;
312             printf( "输入错误，请重新输入：" );
313         }
314         switch ( selection )
315         {
316         case 0:
317             exit(0); //退出系统
318             break;
319         case 1:
320             Show(); //显示分区
321             break;
322         case 2:
323             Allocation(); //分配作业
324             break;
325         case 3:
326             Recovery();  //回收分区
327             break;
328         default:
329             break;
330         }
331     }
332 }

结果截图：

6、总结

通过本次实验对首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法有了进一步认识，可是在编程算法过程中用了大量的循环，算法效率较低。同时加深了对操作系统主存空间的分配和回收程序以及动态分区分配方式的理解。