【操作系统】主存空间的分配和回收

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

专业：商软一班姓名：黄敏鹏学号：201406114116

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;

第一步：（第13周完成）

完成程序数据结构的创建，初始化内存分配情况，创建空闲分区表和已分配分区表。

第二步：（第14周完成）

完成为某作业分配内存空间。

用户输入作业名称；
判断作业名称是否已经存在，如果存在则要求用户重新输入；
用户输入作业所占空间大小；
判断是否能够在剩余的空闲区域中找到一块放置该作业，如果不行则要求用户重新输入；
显示菜单，由用户选择使用哪一种分配算法：

1) 首次适应算法

2) 循环首次适应算法

3) 最佳适应算法

4) 最坏适应算法

6.为该作业分配内存空间，分配处理流程图如下（size的值设定为1K）：

7.屏幕显示分配后的内存分区情况。

第三步：（第15周完成）

完成内存空间回收；

由用户输入作业的ID，决定所要终止的作业；
判断是否存在用户所输入的ID，如果存在则进行终止，否则提示作业不存在；
判断即将终止的作业前后是否有空闲区域，如果没有则作业所占的空间独立成为一个空闲块，在未分配区表中增加一项；

程序中表示内存区块的结构体如下：

struct partition {

char pn[10];

int begin;

int size;

int end;

char status;

};

所以，判断某个即将被终止的作业所占空间前面是否有空闲块的方法是：作业空间的起始地址A.begin是否等于某个空闲块的结束地址B.end，若相等，则前面有空闲块，则需要合并；若不相等则再判断后面是否有空闲块。

回答：如何判断？

进行四种情况的判断，然后分别做出相应的区块回收操作。

回答：如何处理回收？

显示回收后的内存使用情况。

运行截图：

源代码：

  1 #include<stdio.h>
  2 //#include<conio.h>
  3 #include<windows.h>
  4 #include<string.h>
  5 #define MAX 24    //内存允许同时存在的空间数
  6 #define max_size 512    //内存空间的大小
  7 struct partition{
  8     
  9     char pn[10];    //空间名称
 10     int begin;    //空间的相对起始位置
 11     int size;    //空间的大小
 12     int end;    //空间的相对结束位置
 13     char status;  //通过该属性判断空间状态 : u 为已使用 ; f 为未分配作业 ; 0 为未初始化
 14     };
 15 typedef struct partition PART;
 16 
 17 char jobName[20];    //暂时保存用户输入的作业名
 18 int jobSize;    //暂时保存用户输入的作业所需空间大小
 19 
 20 int lastPost=0;    //保存循环首次适应算法的上次搜索的位置
 21 
 22 //初始化内存分配
 23 void newMemory(PART memory[MAX]);
 24 //输出内存分配情况
 25 void putoutMemory(PART memory[MAX]);
 26 //输入作业
 27 void inputJob(PART memory[MAX]);
 28 //回收指定作业
 29 void removeJob(PART memory[MAX]);
 30 //首次适应算法查找目标分区
 31 void findByFirstFit(PART memory[MAX],int jobSize,char jobName[20]);
 32 //循环首次适应算法查找目标分区
 33 void findByNestFit(PART memory[MAX],int jobSize,char jobName[20]);
 34 //最坏适应分配查找目标分区
 35 void findByWorstFit(PART memory[MAX],int jobSize,char jobName[20]);
 36 //最优适应分配查找目标分区
 37 void findByGoodFit(PART memory[MAX],int jobSize,char jobName[20]);
 38 
 39 /*
 40     主函数
 41 */
 42 void main(){
 43     PART memory[MAX];
 44     newMemory(memory);
 45 
 46     while(1){
 47         system("title 201402114116-黄敏鹏");
 48         system("mode con cols=80 lines=30");
 49         system("cls");
 50         int choose;
 51         printf("0.退出    1.回收内存    2.查看内存分配情况    3.回收指定作业 
");
 52         printf("4.首次适应分配    5.循环首次适应分配    6.最坏适应分配   7.最优适应分配
");
 53         printf("
请输入 : ");
 54         scanf("%d",&choose);
 55         switch( choose ){
 56         case 0:
 57             printf("

程序已停止运行，按任意键关闭窗口


");
 58             exit(1);
 59             break;
 60         case 1:
 61             newMemory(memory);
 62             printf("

还原内存分配成功



");
 63             break;
 64         case 2:    
 65             putoutMemory(memory);
 66             break;
 67         case 3:    
 68             removeJob(memory);
 69             break;
 70         case 4:    
 71             inputJob(memory);
 72             findByFirstFit(memory,jobSize,jobName);
 73             break;
 74         case 5:
 75             inputJob(memory);
 76             findByNestFit(memory,jobSize,jobName);
 77             break;
 78         case 6:
 79             inputJob(memory);
 80             findByWorstFit(memory,jobSize,jobName);
 81             break;
 82         case 7:
 83             inputJob(memory);
 84             findByGoodFit(memory,jobSize,jobName);
 85             break;
 86         default:
 87             printf("

输入错误，请重新输入!


");
 88         }
 89         system("pause");
 90     }
 91 }
 92 
 93 //初始化内存空间
 94 void newMemory(PART memory[MAX]){
 95     for(int i=0;i<MAX;i++){
 96         memory[i].status = '0'; //初始值为0,有用值为 f , u 
 97         memory[i].size = 0;
 98     }
 99     strcpy(memory[0].pn,"SYSTEM");
100     memory[0].begin = 0;
101     memory[0].status = 'f'; 
102     memory[0].size = max_size;
103     memory[0].end = memory[0].begin + memory[0].size;
104 }
105 
106 //输入作业
107 void inputJob(PART memory[MAX]){
108     printf("
请输入作业名称 : ");
109     scanf(" %s",&jobName);
110     printf("请输入作业所需空间 : ");
111     scanf("%d",&jobSize);
112 }
113 
114 void putoutMemory(PART memory[MAX]){
115     printf("

-------------------------内存分配-----------------------
");
116     printf("--------------------------------------------------------
");
117     printf("	 No.?	 pn      	 begin 	 size 	 status    
");
118     for(int i=0;i<MAX;i++){
119         if(memory[i].status != '0'){
120                 printf("	 No.%d	%7s 	 %5d 	 %4d 	 %6c    
",i,memory[i].pn,memory[i].begin,memory[i].size,memory[i].status);
121         }
122     }
123     printf("--------------------------------------------------------
");
124     printf("


");
125 }
126 
127 //回收指定作业
128 void removeJob(PART memory[MAX]){
129     char removeJobName[10];
130     int flag=0;
131     printf("
请输入作业名称 : ");
132     scanf(" %s",&removeJobName);
133     for(int i=0;i<MAX;i++){
134         if( strcmp(memory[i].pn,removeJobName) == 0 ){        
135             memory[i].status = 'f'; 
136             strcpy(memory[i].pn,"SYSTEM");
137             flag=1;
138         }
139     }
140     if(flag==1){
141         printf("

回收作业成功



");
142     }else{
143         printf("

该作业不存在



");
144     }
145 
146 }
147 
148 //首次适应算法查找目标分区
149 void findByFirstFit(PART memory[MAX],int jobSize,char jobName[20]){
150     int post=24,post2=24;
151     if( jobSize > max_size){
152         printf("

作业所需空间过大，系统无法满足您的需求

");
153         return ;
154     }
155     int i=0;
156     for(i=0;i<MAX;i++){
157         if(memory[i].size>=jobSize && memory[i].status == 'f'){
158             post=i;
159             break;
160         }
161     }
162     for(int j = 0; j<MAX;j++){
163         if(memory[j].status == '0'){
164             post2 = j;
165             break;
166         }
167     }
168     if(post>=24 ){
169         printf("
所需空间太大，系统无法满足您的需求

");
170         return ;
171     }
172     if(post2>=24){
173         printf("
已有的作业数太多，系统无法满足您的需求

");
174         return ;
175     }
176 
177     int memorySize=memory[post].size;
178     strcpy(memory[post].pn,jobName);
179     memory[post].size = jobSize;
180     memory[post].end = memory[post].begin + memory[post].size;
181     memory[post].status = 'u';
182 
183     memory[post2].begin = memory[post].end;
184     memory[post2].size = memorySize - jobSize;
185     memory[post2].end = memory[post2].begin + memory[post2].size;
186     memory[post2].status = 'f';
187     strcpy(memory[post2].pn,"SYSTEM");
188     
189     printf("

添加作业成功



");
190     
191 }
192 
193 //循环首次适应算法查找目标分区
194 void findByNestFit(PART memory[MAX],int jobSize,char jobName[20]){
195     int post=0,post2;
196     int i,j;
197 
198     if(lastPost<=24){        
199          post = lastPost;
200     }else{
201         lastPost = 0;
202     }
203 
204     if( jobSize > max_size){
205         printf("

作业所需空间过大，系统无法满足您的需求

");
206         return ;
207     }
208     for(i=post;i<MAX;i++){
209         if(memory[i].size>=jobSize && memory[i].status == 'f'){
210             post=i;
211             break;
212         }
213         if(i==MAX){
214             for(j=post;j<lastPost;j++){
215                 if(memory[j].size>=jobSize && memory[j].status == 'f'){
216                     post=j;
217                     break;
218                 }
219             }
220         }
221     }
222     for(j = 0; j<MAX;j++){
223         if(memory[j].status == '0'){
224             post2 = j;
225             break;
226         }
227     }
228 
229     if(post>=24 || memory[post].size < jobSize){
230         printf("

没有可以放置的空间

");
231         return;
232     }
233     if(post2>=24){
234         printf("

已有的作业数太多，系统无法满足您的需求

");
235         return;
236     }
237 
238     lastPost = post;
239 
240     int memorySize=memory[post].size;
241     strcpy(memory[post].pn,jobName);
242     memory[post].size = jobSize;
243     memory[post].end = memory[post].begin + memory[post].size;
244     memory[post].status = 'u';
245 
246     memory[post2].begin = memory[post].end;
247     memory[post2].size = memorySize - jobSize;
248     memory[post2].end = memory[post2].begin + memory[post2].size;
249     memory[post2].status = 'f';
250     strcpy(memory[post2].pn,"SYSTEM");
251     
252     printf("

添加作业成功



");
253 }
254 
255 //最坏适应分配查找目标分区
256 void findByWorstFit(PART memory[MAX],int jobSize,char jobName[20]){
257     int post=-1,post2;
258     if( jobSize > max_size){
259         printf("

作业所需空间过大，系统无法满足您的需求

");
260         return ;
261     }
262     int i=0;
263     for(i=0;i<MAX;i++){
264         if(memory[i].size>jobSize && memory[i].status == 'f'){
265             if( post == -1){
266                 post=i;
267             }else if(memory[i].size>memory[post].size){
268                 post=i;
269             }
270         }
271     }
272     for(int j = 0; j<MAX;j++){
273         if(memory[j].status == '0'){
274             post2 = j;
275             break;
276         }
277     }
278     if(post2>=24){
279         printf("

已有的作业数太多，系统无法满足您的需求
");
280         return ;
281     }
282     if(post>=24 || post ==-1){
283         printf("

所需空间太大，系统无法满足您的需求
");
284         return ;
285     }
286 
287     int memorySize=memory[post].size;
288     strcpy(memory[post].pn,jobName);
289     memory[post].size = jobSize;
290     memory[post].end = memory[post].begin + memory[post].size;
291     memory[post].status = 'u';
292 
293     memory[post2].begin = memory[post].end;
294     memory[post2].size = memorySize - jobSize;
295     memory[post2].end = memory[post2].begin + memory[post2].size;
296     memory[post2].status = 'f';
297     strcpy(memory[post2].pn,"SYSTEM");
298 
299     printf("

添加作业成功



");
300 }
301 
302 //最优适应分配查找目标分区
303 void findByGoodFit(PART memory[MAX],int jobSize,char jobName[20]){
304     int post=-1,post2;
305     if( jobSize > max_size){
306         printf("

作业所需空间过大，系统无法满足您的需求

");
307         return ;
308     }
309     int i=0;
310     for(i=0;i<MAX;i++){
311         if(memory[i].size > jobSize && memory[i].status == 'f' ){
312             if( post >= 0 ){
313                 if( memory[i].size < memory[post].size ){
314                     post=i;
315                     printf("%d----",i);
316                 }
317             }else if( post == -1 ){
318                 post=i;
319             }
320         }
321     }
322     for(int j = 0; j<MAX;j++){
323         if(memory[j].status == '0'){
324             post2 = j;
325             break;
326         }
327     }
328     if(post2>=24){
329         printf("

已有的作业数太多，系统无法满足您的需求

");
330         return ;
331     }
332     if(post>=24 || post == -1){
333         printf("

所需空间太大，系统无法满足您的需求

");
334         return ;
335     }
336 
337     int memorySize=memory[post].size;
338     strcpy(memory[post].pn,jobName);
339     memory[post].size = jobSize;
340     memory[post].end = memory[post].begin + memory[post].size;
341     memory[post].status = 'u';
342 
343     memory[post2].begin = memory[post].end;
344     memory[post2].size = memorySize - jobSize;
345     memory[post2].end = memory[post2].begin + memory[post2].size;
346     memory[post2].status = 'f';
347     strcpy(memory[post2].pn,"SYSTEM");
348 
349     printf("

添加作业成功



");
350 }