1. 目的和要求
1.1. 实验目的
用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。
1.2. 实验要求
采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计。
（1）**设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行。
（2）或在程序运行过程，由用户指定申请与释放。
（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。
把空闲区说明表的变化情况以及各作业的申请、释放情况显示。
2. 实验内容
根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。
3. 实验环境
可以选用Visual C++作为开发环境。也可以选用Windows下的VB，CB或其他可视化环境，利用各种控件较为方便。自主选择实验环境。
1 #include2 #include 3 #include 4 #include 5 #define MAX 24 6 struct partition{ 7 char pn[10]; //作业名 8 int begin; //开始时间 9 int size; //内存大小 10 int end; //结束时间 11 char status; //状态 12 struct partition *next; 13 }; 14 typedef struct partition PART; 15 PART *head; 16 //初始化used表 17 PART *InitListu() 18 { 19 PART *k; 20 k= (PART *)malloc(sizeof(PART)); 21 strcpy(k->pn,"SYSTEM"); 22 k->begin=0; 23 k->size=100; 24 k->end=100; 25 k->status='u'; 26 k->next=NULL; 27 return k; 28 } 29 //初始化free表 30 PART *InitListf() 31 { 32 PART *k; 33 k= (PART *)malloc(sizeof(PART)); 34 strcpy(k->pn,"------"); 35 k->begin=100; 36 k->size=412; 37 k->status='f'; 38 k->end=512; 39 k->next=NULL; 40 return k; 41 } 42 //输出空闲区表Free 43 void Printfree() 44 { 45 printf("空闲区表Free:\n"); 46 printf("No. proname begin size status\n"); 47 PART *free=head->next; 48 int i=1; 49 while(free!=NULL) 50 { 51 if(free->status=='f') 52 { 53 printf("No.%d\t%s\t%d\t%d\t%c",i,free->pn,free->begin,free->size,free->status); 54 i++; 55 printf("\n"); 56 } 57 free=free->next; 58 } 59 } 60 //输出已分配分区表Used 61 void Printused() 62 { 63 printf("已分配分区表Used:\n"); 64 printf("No. proname begin size status\n"); 65 PART *used=head->next; 66 int i=1; 67 while(used!=NULL) 68 { 69 if(used->status=='u') 70 { 71 printf("No.%d\t%s\t%d\t%d\t%c",i,used->pn,used->begin,used->size,used->status); 72 i++; 73 printf("\n"); 74 } 75 used=used->next; 76 } 77 } 78 //输出所以作业 79 void Print() 80 { 81 printf("内存使用情况，按起始地址增长的排:\n"); 82 printf("printf sorted by address:\n"); 83 printf("No. proname begin size status\n"); 84 PART *total=head->next; 85 int i=1; 86 while(total!=NULL) 87 { 88 printf("No.%d\t%s\t%d\t%d\t%c",i,total->pn,total->begin,total->size,total->status); 89 i++; 90 printf("\n"); 91 total=total->next; 92 } 93 } 94 //算法菜单 95 void menu() 96 { 97 98 printf("1) 首次适应算法\n"); 99 printf("2) 循环首次适应算法\n");100 printf("3) 最佳适应算法\n");101 printf("4) 最坏适应算法:\n");102 103 }104 //查找是否已存在作业名105 PART *searchname(char name[10])106 {107 PART *rear;108 rear=head->next;109 while((rear!=NULL)&&(strcmp(rear->pn,name)!=0))110 rear=rear->next;111 return rear;112 }113 //查找是否有足够大的空闲内存114 PART *searchsize(int size,PART *temp)115 {116 PART *rear;117 rear=head->next;118 while(rear!=NULL)119 {120 if(rear->status=='f')121 {122 if(rear->size>=size)123 {124 return rear;125 }126 else127 rear=rear->next;128 }129 else130 rear=rear->next;131 }132 return rear;133 }134 // 首次适应算法135 void FF(PART *p)136 {137 PART *q,*rear;138 rear=q=head->next;139 while(rear!=NULL)140 {141 if(rear->status=='f')//判断空闲区142 {143 if(rear->size>=p->size)//判断空闲区的大小144 {145 //添加结点（新作业）146 p->status='u';147 p->begin=rear->begin;148 p->end=p->begin+p->size;149 p->next=NULL;150 q->next=p;151 rear->begin=p->end;152 if(rear->size==p->size)153 p->next=rear->next;154 else155 {156 rear->size=rear->size-p->size;157 p->next=rear;158 }159 //打印输出160 Printfree();161 Printused();162 Print();163 return; 164 }165 else166 { //遍历结点167 q=rear;168 rear=q->next;169 }170 171 }172 else173 { //遍历结点174 q=rear;175 rear=q->next; 176 }177 178 }179 180 }181 //查找满足新作业的最大或最小空闲区182 void sear(PART *p,PART *temp,int n)183 {184 PART *rear=head->next;185 while(rear!=NULL)186 {187 if(rear->status=='f')188 {189 if(rear->size>=p->size)190 {191 if(n==3)192 {193 if(rear->size size) //最小（最优）194 temp=rear;195 else196 rear=rear->next;197 }198 if(n==4)199 {200 if(rear->size>temp->size) //最大（最坏）201 temp=rear;202 else203 rear=rear->next;204 }205 }206 else207 rear=rear->next; 208 }209 else210 rear=rear->next;211 }212 }213 // 最佳适应算法 和 最坏适应算法214 void BF_WF(PART *p,PART *temp,int n)215 { 216 PART *q,*rear;217 sear(p,temp,n);218 rear=head->next;219 while((rear!=NULL)&&(rear!=temp)) //查找前一结点和当前结点220 {221 q=rear;222 rear=q->next;223 }224 //添加新作业225 p->status='u';226 p->begin=rear->begin;227 p->end=p->begin+p->size;228 p->next=NULL;229 q->next=p;230 rear->begin=p->end;231 if(rear->size==p->size)232 p->next=rear->next;233 else234 {235 rear->size=rear->size-p->size;236 p->next=rear;237 }238 Printfree();239 Printused();240 Print();241 }242 //分配输入243 void input()244 {245 PART *p,*temp;246 char name[10];247 int size;248 int n;249 temp = (PART *)malloc(sizeof(PART));250 lab1: printf("输入作业名称:");251 scanf("%s",name);252 if(searchname(name)==NULL) //判断作业是否已经存在253 {254 p = (PART *)malloc(sizeof(PART));255 strcpy(p->pn,name);256 }257 else258 {259 printf("作业已经存在，请重新输入:\n");260 goto lab1;261 }262 lab2: printf("请输入作业所占空间大小:"); //判断是否有足够大的空闲区263 scanf("%d",&size);264 temp=searchsize(size,temp);265 if(temp!=NULL)266 {267 p->size=size;268 }269 else270 {271 printf("没有剩余的空闲区域中，请重新输入:\n");272 goto lab2;273 }274 //选择算法275 menu();276 printf("请选择算法:");277 scanf("%d",&n);278 switch (n)279 {280 case 1:281 FF(p);282 break;283 /* case 2:284 CF(p);285 break;*/286 case 3:287 BF_WF(p,temp,n);288 break;289 case 4:290 BF_WF(p,temp,n);291 break;292 }293 }294 //回收295 void recycle()296 {297 PART *q,*rear,*temp;298 char pname[10];299 temp = (PART *)malloc(sizeof(PART));300 lab3: printf("请输入要终止的作业名:");301 scanf("%s",pname);302 if(searchname(pname)==NULL) //判断是否存在该作业303 {304 printf("作业不存在，请重新输入:\n");305 goto lab3;306 }307 else308 {309 rear=head->next;310 temp=searchname(pname);311 while((rear!=NULL)&&(rear!=temp))//查找前一节点和当前节点312 {313 q=rear;314 rear=q->next;315 }316 if(q->status=='u'&&rear->next->status=='u')//前后被分配317 {318 strcpy(rear->pn,"------");319 rear->status='f';320 }321 else if(q->status=='u'&&rear->next->status=='f')//前者分配后者空闲322 {323 strcpy(rear->pn,"------");324 rear->status='f';325 rear->size=rear->size+rear->next->size;326 rear->end=rear->next->end;327 rear->next=rear->next->next;328 }329 else if(q->status=='f'&&rear->next->status=='u')//前者空闲后者分配330 {331 q->end=rear->end;332 q->size=rear->size+q->size;333 q->next=rear->next;334 }335 else if(q->status=='f'&&rear->next->status=='f')//前后空闲336 {337 q->end=rear->next->end;338 q->size=rear->size+q->size+rear->next->size;339 q->next=rear->next->next;340 }341 Printfree();342 Printused();343 Print();344 }345 }346 //主函数347 void main()348 {349 int cho;350 printf("初始化,设内存总容量512k\n");351 printf("系统从低地址部分开始使用,占用100k\n");352 head = (PART *)malloc(sizeof(PART));353 head->next=InitListu();354 head->next->next=InitListf();355 Printfree();356 Printused();357 Print();358 while(1)359 {360 lab4: printf("1 分配 2 回收 3 退出\n");361 printf("请选择:");362 scanf("%d",&cho);363 if(cho==1)364 input();365 else if(cho==2)366 recycle();367 else if(cho==3)368 return;369 else 370 {371 printf("输入错误,请重新输入:\n");372 goto lab4;373 }374 }375 printf("\n");376 }
运行结果：
分配：
回收：
