实验四 主存空间的分配和回收
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) 最坏适应算法
- 为该作业分配内存空间，分配处理流程图如下（size的值设定为1K）：
- 屏幕显示分配后的内存分区情况。
第三步：（第15周完成）
完成内存空间回收；
- 由用户输入作业的ID，决定所要终止的作业；
- 判断是否存在用户所输入的ID，如果存在则进行终止，否则提示作业不存在；
- 判断即将终止的作业前后是否有空闲区域，如果没有则作业所占的空间独立成为一个空闲块，在未分配区表中增加一项；
（思考：如何判断前后是否有空闲块？）
- 即将终止作业所占空间前后有空闲块的情况：（X代表即将被终止的作业，黑色代表内存中的空闲块）
程序中表示内存区块的结构体如下：
struct partition {
char pn[10];
int begin;
int size;
int end;
char status;
};
所以，判断某个即将被终止的作业所占空间前面是否有空闲块的方法是：作业空间的起始地址A.begin是否等于某个空闲块的结束地址B.end，若相等，则前面有空闲块，则需要合并；若不相等则再判断后面是否有空闲块。
回答：如何判断？
- 进行四种情况的判断，然后分别做出相应的区块回收操作。
回答：如何处理回收？
- 显示回收后的内存使用情况。
代码展示：
1 #include <iomanip> 2 #include<stdio.h> 3 using namespace std; 4 void begin(); 5 int kongjian(); 6 int pdname(char c); 7 void print(); 8 void fenpei(); 9 int ShouCi(char c,int i); 10 void reclaim(); 11 int huishou(char c); 12 int zuijia(char c,int i); 13 int zuihuai(char c,int i); 14 int xunhuan(char c,int i); 15 extern int xh=0;//记录循环首次适应时的开始id 16 //主存大小为512 17 //定义100个不定分区 可分配100工作 18 19 struct partition 20 { 21 int end;//分区号 22 char pn;//工作名 23 int size;//工作空间 24 int begin;//开始地址 25 char state;//状态 1 可用 0 已用 26 }; //主存表的初始化 27 partition PART[100]; 28 29 void begin() 30 { 31 PART[0].end=1; 32 PART[0].begin =0; 33 PART[0].state ='f'; 34 PART[0].pn =NULL; 35 PART[0].size =1024; 36 for(int i=1;i<100;i++) 37 { 38 PART[i].end =i+1; 39 PART[i].state ='f'; 40 PART[i].pn =NULL; 41 PART[i].begin =PART[i-1].begin +PART[i].size; 42 } 43 } 44 45 int kongjian()//返回空闲空间 46 { 47 int sizeAll=512;//主存总空间 48 int sizeUse=0;//已用空间 49 int sizeKY;//可用工作空间 50 for(int i=0;i<100;i++) 51 { 52 if(PART[i].state=='u') 53 sizeUse=sizeUse+PART[i].size; 54 } 55 sizeKY=sizeAll-sizeUse; 56 return sizeKY;//返回空空间 57 } 58 59 //判断作业名 60 int pdname(char name) 61 { 62 for(int i=0;i<100;i++) 63 { 64 if(PART[i].pn ==name) 65 { 66 printf(" 输入工作名重复！ "); 67 return 0; 68 } 69 } 70 return 1; 71 } 72 73 //输出函数 74 void print() 75 { 76 printf(" 分区号 工作名 开始地址 工作空间 状态 "); 77 for(int i=0;i<100;i++) 78 { 79 printf("%5d%7s%12d%12d%12s ",PART[i].end,&PART[i].pn,PART[i].begin,PART[i].size,&PART[i].state); 80 if(PART[i].state=='f'&&PART[i+1].state=='f'&&PART[i+2].state=='f') 81 break; 82 } 83 } 84 //主存分配各函数 85 void fenpei() 86 { 87 char name; 88 int size; 89 int c=1; 90 printf(" 请输入工作名: "); 91 scanf("%s",&name); 92 printf(" 请分配空间： "); 93 scanf("%d",&size); 94 if(pdname(name)) 95 { 96 printf(" 请选择要选的算法 1.首次适应算法 2.最佳适应算法 3.最坏适应算法 "); 97 scanf("%d",&c); 98 if(c!=1&&c!=2&&c!=3&&c!=4) 99 { 100 c=1; 101 } 102 switch(c) 103 { 104 case 1: 105 ShouCi(name,size); 106 break; 107 case 2: 108 zuijia(name,size); 109 break; 110 case 3: 111 zuihuai(name,size); 112 break; 113 } 114 } 115 } 116 //分配主存 117 int ShouCi(char name,int size) 118 { 119 for(int i=0;i<100;i++) 120 { 121 if(PART[i].size>=size&&PART[i].state=='f') 122 { 123 int temp=PART[i].size; 124 int sum=PART[i+1].begin; 125 PART[i].size =size; 126 PART[i].pn =name; 127 PART[i].begin =PART[i-1].begin +PART[i-1].size; 128 PART[i+1].begin =PART[i].begin +PART[i].size; 129 PART[i].state ='u'; 130 if(temp>size)//将i项分成两项 131 { 132 for(int j=100;j>i+1;j--) 133 { 134 PART[j].begin =PART[j-1].begin; 135 PART[j].state =PART[j-1].state; 136 PART[j].pn =PART[j-1].pn; 137 PART[j].size =PART[j-1].size; 138 } 139 PART[i+2].begin =sum; 140 PART[i+1].state ='f'; 141 PART[i+1].pn =NULL; 142 PART[i+1].size =temp-size; 143 } 144 printf(" 成功分配! "); 145 for(int j=i;j<100;j++) 146 if(PART[j].state =='f'&&PART[j+1].state =='f'&&PART[j+2].state =='f')//查找以后表 条件为3个连续空闲的空间 则视为以后都空闲 147 { 148 PART[j].size =kongjian();//将剩余空间放入j中 149 } 150 return 1; 151 } 152 } 153 if(i=100) 154 { 155 printf(" 主存空间已满！ "); 156 return 0; 157 } 158 return 0; 159 } 160 161 //回收工作各函数 162 void reclaim() 163 { 164 char name; 165 printf(" 请输入所需回收工作名: "); 166 scanf("%s",&name); 167 huishou(name); 168 } 169 170 //回收工作 171 int huishou(char name) 172 { 173 int j; 174 //查找要回收的工作 175 for(int i=0;i<100;i++) 176 { 177 if(PART[i].pn ==name) 178 { 179 printf(" 你所需回收的工作已找到，在%d分区中 ",PART[i].end); 180 break; 181 } 182 } 183 if(i==100) 184 { 185 printf(" 未找到你要回收的工作 "); 186 return 0; 187 } 188 int n=i;//第n个工作需要回收 189 //回收工作 4种情况 190 if(i==0&&PART[1].state =='f') 191 { 192 PART[0].begin=0; 193 PART[0].state ='f'; 194 PART[0].pn =NULL; 195 PART[0].size =PART[0].size +PART[1].size; 196 for(i=1;i<100;i++) 197 { 198 PART[i].begin =PART[i+1].begin; 199 PART[i].state =PART[i+1].state; 200 PART[i].pn =PART[i+1].pn; 201 PART[i].size =PART[i+1].size; 202 } 203 } 204 else if(PART[n-1].state =='f'&&PART[n+1].state =='u')//下有空 205 { 206 PART[n-1].size =PART[n-1].size +PART[n].size; 207 for(j=n;j<99;j++) 208 { 209 PART[j].begin =PART[j+1].begin; 210 PART[j].state =PART[j+1].state; 211 PART[j].pn =PART[j+1].pn; 212 PART[j].size =PART[j+1].size; 213 } 214 } 215 else if(PART[n-1].state=='u'&&PART[n+1].state=='f')//上有空 216 { 217 PART[n].size =PART[n].size +PART[n+1].size; 218 PART[n].pn =NULL; 219 PART[n].state ='f'; 220 for(j=n+1;j<99;j++) 221 { 222 PART[j].begin =PART[j+1].begin; 223 PART[j].state =PART[j+1].state; 224 PART[j].pn =PART[j+1].pn; 225 PART[j].size =PART[j+1].size; 226 } 227 } 228 else if(PART[n-1].state=='f'&&PART[n+1].state=='f')//上下都为空 229 { 230 PART[n-1].size =PART[n-1].size +PART[n].size +PART[n+1].size; 231 for(j=n;j<98;j++) 232 { 233 PART[j].begin =PART[j+2].begin; 234 PART[j].state =PART[j+2].state; 235 PART[j].pn =PART[j+2].pn; 236 PART[j].size =PART[j+2].size; 237 } 238 } 239 else //上下不为空 直接回收 240 { 241 PART[n].state ='f'; 242 PART[n].pn =NULL; 243 } 244 return 1; 245 } 246 247 //主函数 248 void main() 249 { 250 begin(); 251 int yes=1; 252 int c; 253 int t; 254 while(yes) 255 { 256 t=kongjian(); 257 printf("现在可用内存为：%d ",t); 258 if(t<20) 259 { 260 printf("内存可用空间太小，无法再存入!请回收内存"); 261 } 262 printf(" 请选择你想进行的操作： 1.分配工作 2.回收工作 3.打印主存 4.退出 "); 263 scanf("%d",&c); 264 if(c>4||c<1) 265 { 266 printf(" 输入错误！请重新输入！ "); 267 scanf("%d",&c); 268 } 269 switch(c) 270 { 271 case 1: 272 fenpei(); 273 break; 274 case 2: 275 reclaim(); 276 break; 277 case 3: 278 print(); 279 break; 280 case 4: 281 yes=0; 282 break; 283 } 284 } 285 } 286 //最佳适应分配算法 287 int zuijia(char name,int size) 288 { 289 //查找一个大于size的空闲空间,将此空间的end存入id，Worksize存入min 290 int min=1025; 291 int id=-1; 292 for(int i=0;i<100;i++) 293 { 294 if(PART[i].state =='f'&&PART[i].size <min&&PART[i].size>size) 295 { 296 id=i; 297 min=PART[i].size; 298 } 299 } 300 printf("最佳适应空间的id：%d",id+1); 301 printf("空间大小：%d ",&min); 302 //将作业存入PART[i]项 303 int temp=PART[id].size-size; 304 if(temp==0)//空闲空间大小恰好等于申请空间大小直接存入 305 { 306 PART[i].pn =name; 307 PART[i].state ='u'; 308 } 309 else if(temp>0)//空闲空区大于申请空间,需要将空闲分区分割 310 { 311 PART[id].pn =name; 312 PART[id].size =size; 313 PART[id].state ='u'; 314 for(int j=100;j>id+1;j--) 315 { 316 PART[j].begin =PART[j-1].begin; 317 PART[j].state =PART[j-1].state; 318 PART[j].pn =PART[j-1].pn; 319 PART[j].size =PART[j-1].size; 320 } 321 PART[id+1].begin =PART[id].begin +PART[id].size; 322 PART[id+1].state ='f'; 323 PART[id+1].size =temp; 324 PART[id+1].pn =NULL; 325 } 326 return 0; 327 } 328 int zuihuai(char name,int size) 329 { //查找一个大于size的空闲空间,将此空间的end存入id，size存入max 330 int max=size; 331 int id=-1; 332 for(int i=0;i<100;i++) 333 { 334 if(PART[i].state =='f'&&PART[i].size >max) 335 { 336 id=i; 337 max=PART[i].size; 338 } 339 } 340 printf(" 最坏适应空间的id：%d",id+1); 341 printf(" 空间大小：%d ",&max); 342 //将作业存入PART[i]项 343 int temp=PART[id].size -size; 344 if(temp==0)//空闲空间大小恰好等于申请空间大小直接存入 345 { 346 PART[i].pn =name; 347 PART[i].state ='u'; 348 } 349 else if(temp>0)//空闲空区大于申请空间,需要将空闲分区分割 350 { 351 PART[id].pn =name; 352 PART[id].size =size; 353 PART[id].state ='u'; 354 for(int j=100;j>id+1;j--) 355 { 356 PART[j].begin =PART[j-1].begin; 357 PART[j].state =PART[j-1].state; 358 PART[j].pn =PART[j-1].pn; 359 PART[j].size =PART[j-1].size; 360 } 361 PART[id+1].begin =PART[id].begin +PART[id].size; 362 PART[id+1].state ='f'; 363 PART[id+1].size =temp; 364 PART[id+1].pn =NULL; 365 } 366 return 0; 367 } 368
结果展示：
