西安邮电大学（计算机学院）课内实验报告实验名称：内存管理专业名称：软件工程班级：学生姓名：学号（8位）：指导教师：实验日期：2018年12月04日一.实验目的及实验环境1、实验环境Linux centos7系统gcc编译器 gdb调试2、实验目的(1)掌握内存分配FF，BF，WF策略及实现的思路；(2)掌握内存回收过程及实现思路；(3)参考本程序思路，实现内存的申请、释放的管理程序，调试运行，总结程序设计中出现的问题并找出原因，写出实验报告。

二.实验内容(1)掌握内存分配FF，BF，WF策略及实现的思路；(2)掌握内存回收过程及实现思路；(3)参考本程序思路，实现内存的申请、释放的管理程序，调试运行，总结程序设计中出现的问题并找出原因，写出实验报告。

三．方案设计----------------------------------------------------------Memory management experiment1 - Set memory size (default=1024)2 - Select memory allocation algorithm3 - New process4 - kill a process5 - Display memory usage0 - Exit----------------------------------------------------------一、首次适应算法（First Fit）：该算法从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。

然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。

特点：该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲区。

显然为以后到达的大作业分配大的内存空间创造了条件。

缺点：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销。

二、循环首次适应算法（Next Fit）：该算法是由首次适应算法演变而成的。

在为进程分配内存空间时，不再每次从链首开始查找，直至找到一个能满足要求的空闲分区，并从中划出一块来分给作业。

特点：使内存中的空闲分区分布的更为均匀，减少了查找时的系统开销。

缺点：缺乏大的空闲分区，从而导致不能装入大型作业。

三、最佳适应算法（Best Fit）：该算法总是把既能满足要求，又是最小的空闲分区分配给作业。

为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增顺序形成一个空白链。

这样每次找到的第一个满足要求的空闲区，必然是最优的。

孤立地看，该算法似乎是最优的，但事实上并不一定。

因为每次分配后剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。

同时每次分配后必须重新排序，这也带来了一定的开销。

特点：每次分配给文件的都是最合适该文件大小的分区。

缺点：内存中留下许多难以利用的小的空闲区。

四、最坏适应算法(Worst Fit)：该算法按大小递减的顺序形成空闲区链，分配时直接从空闲区链的第一个空闲区中分配（不能满足需要则不分配）。

很显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。

这种分配方法初看起来不合理，但它也有很强的直观吸引力：在大空闲区中放入程序后，剩下的空闲区常常也很大，于是还能装下一个较大的新程序。

最坏适应算法与最佳适应算法的排序正好相反，它的队列指针总是指向最大的空闲区，在进行分配时，总是从最大的空闲区开始查寻。

该算法克服了最佳适应算法留下的许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最佳适应算法一样复杂。

特点：给文件分配分区后剩下的空闲区不至于太小，产生碎片的几率最小，对中小型文件分配分区操作有利。

缺点：使存储器中缺乏大的空闲区，对大型文件的分区分配不利。

四．测试数据及运行结果五．总结本次实验使我受益匪浅，我不仅仅学习到了专业知识，更重要的是收获了经验与体会，这些使我一生受用不尽，记下来与大家共勉：1.多学多问，学会虚心求教。

在实验前内存管理的最佳适配算法不是很会计算，向班级同学请教后发现虽然思维上有点绕，但是并不是很难，很快就理解了原理思想。

2.善于思考，真正消化知识。

有知到识，永远不是那么简单的事，当你真正学会去思考时，他人的知识才能变成你自己的东西。

3.前人铺路，后人修路。

墨守陈规永远不会有新的建树，前人的道路固然重要，但是学会创新更为重要。

4.独立而不孤立。

学会独立思考，独立实验，但要记住与他人的交流也是十分重要的，实验和实验事永远不是你自己的。

5.认真仔细地做好实验纪录。

不要当你真正用到它时才知它的重要所在。

六．附录：源代码（电子版）#include <stdio.h>#include <stdlib.h>#include <ctype.h>#define PROCESS_NAME_LEN 32 //进程名长度#define MIN_SLICE 10 // 最小碎片大小#define DEFAULT_MEM_SIZE 1024 // 内存大小#define DEFAULT_MEM_START 0 // 起始地址//内存分配算法#define MA_FF 1#define MA_BF 2#define MA_WF 3//描述每一个空闲块的数据结构struct free_block_type{int size;int start_addr;struct free_block_type *next;};//每个进程分配到的内存块的描述struct allocated_block{int pid;int size;int start_addr;char process_name[PROCESS_NAME_LEN];struct allocated_block *next;};struct free_block_type *free_block;struct allocated_block *allocated_block_head = NULL;int mem_size=DEFAULT_MEM_SIZE; // 内存大小int ma_algorithm = MA_FF; // 当前分配算法static int pid = 0; // 初始pidint flag = 0;void display_menu();void do_exit();struct free_block_type *init_free_block(int mem_size); void set_mem_size();void set_algorithm();void new_process();void kill_process();void display_mem_usage();void rearrange(int choice);void rearrage_FF();void rearrage_BF();void rearrage_WF();int main(){char choice;pid=0;free_block = init_free_block(mem_size);display_menu();while(1){printf("Please choice: ");fflush(stdin);choice=getchar(); //获取用户输入switch(choice){case '1':set_mem_size(); //设置内存大小break;case '2':set_algorithm();//设置算法flag=1;break;case '3':new_process();//创建新进程flag=1;break;case '4':kill_process();//删除进程flag=1;break;case '5':display_mem_usage();//显示内存使用flag=1;break;case '0':do_exit();//释放链表并退出exit(0);default: break;}choice=getchar();}return 0;}//紧缩处理void free_memory_rearrage(int memory_reduce_size,int allocated_size) {struct free_block_type *p1,*p2;struct allocated_block *a1,*a2;if(memory_reduce_size!=0) //分配完还有小块空间{p1=free_block;p2=p1->next;p1->start_addr=0;p1->size=memory_reduce_size;p1->next=NULL;mem_size=memory_reduce_size;}else{p2=free_block;free_block=NULL;mem_size=0;}while(p2!=NULL)//释放节点{p1=p2;p2=p2->next;free(p1);}//allocated_block 重新修改链接a1=(struct allocated_block *)malloc(sizeof(struct allocated_block));a1->pid=pid;a1->size=allocated_size;a1->start_addr=memory_reduce_size; //已申请的开始地址，从memory_reduce_size开始sprintf(a1->process_name, "PROCESS-%02d", pid);a1->next=allocated_block_head;a2=allocated_block_head;allocated_block_head=a1;while(a2!=NULL){a2->start_addr=a1->start_addr+a1->size;a1=a2;a2=a2->next;}}int allocate_mem(struct allocated_block *ab){struct free_block_type *fbt, *pre;int request_size=ab->size;fbt = pre = free_block;while((pre!=NULL)&&(request_size>pre->size)){fbt=pre;pre=pre->next;}if(!pre){if(mem_size>=request_size){if(mem_size>=request_size+MIN_SLICE)free_memory_rearrage(mem_size-request_size,request_size);elsefree_memory_rearrage(0,mem_size);return 0;}elsereturn -1;}else{if((pre->size-request_size)>MIN_SLICE){pre->size=pre->size-request_size;ab->start_addr=pre->start_addr+pre->size;}else{if(pre==fbt){fbt=pre->next;free_block=fbt;}elsefbt->next=pre->next;ab->start_addr=pre->start_addr;ab->size=pre->size;free(pre);}mem_size-=ab->size;rearrange(ma_algorithm);return 1;}//创建新进程，分配内存void new_process(){struct allocated_block *ab;int size;int ret;if(mem_size==0){printf("the memory is all used！not to create new process,please release process！\n");return;}ab=(struct allocated_block *)malloc(sizeof(struct allocated_block));if(ab==NULL){printf("No Mem!\n");exit(1);}ab->next=NULL;pid++;sprintf(ab->process_name,"PROCESS-%02d",pid);//字符串格式化ab->pid=pid;while(1){printf("Please input the memory for %s(0-%d):",ab->process_name,mem_size);scanf("%d",&size);if(size<=mem_size&&size>0){ab->size=size;break;}printf("Please input again！\n");}ret=allocate_mem(ab);if((ret==1) &&(allocated_block_head == NULL))allocated_block_head=ab;else if(ret==1){ab->next=allocated_block_head;allocated_block_head=ab;}else if(ret==-1){printf("Allocation fail\n");free(ab);return;}printf("Allocation Success!\n");}//寻找已分配的内存块struct allocated_block *find_process(int pid){struct allocated_block *p;p=allocated_block_head;while(p){if(p->pid==pid)return p;p=p->next;}return p;}int free_mem(struct allocated_block *ab){int algorithm = ma_algorithm;struct free_block_type *fbt,*pre,*work;mem_size+=ab->size;fbt=(struct free_block_type *)malloc(sizeof(struct free_block_type));if(!fbt)return -1;fbt->size = ab->size;fbt->start_addr=ab->start_addr;fbt->next=NULL;rearrange(MA_FF);pre=NULL;work=free_block;while((work!=NULL)&&(fbt->start_addr>work->start_addr)){pre=work;work=work->next;}if(!pre)//插入开始位置{if (!work){free_block=fbt;}else{fbt->next=work;free_block=fbt;if(fbt->start_addr+fbt->size==work->start_addr){fbt->next=work->next;fbt->size=fbt->size+work->size;free(work);}}}else{if(!work){pre->next=fbt;if(fbt->start_addr==pre->start_addr+pre->size){pre->next=work;pre->size=fbt->size+pre->size;free(fbt);}}else{fbt->next=work;pre->next=fbt;if((fbt->start_addr==pre->start_addr+pre->size)&&(fbt->start_addr+fbt->size == work->start_addr)){pre->next=work->next;pre->size=pre->size+fbt->size+work->size;free(fbt);free(work);}else if(fbt->start_addr== pre->start_addr+pre->size){pre->next=work;pre->size=pre->size+fbt->size;free(fbt);}else if(work->start_addr==fbt->start_addr+fbt->size){fbt->next=work->next;fbt->size=work->size+fbt->size;free(work);}}}rearrange(ma_algorithm);return 1;}void dispose(struct allocated_block *free_ab){struct allocated_block *pre,*ab;if(free_ab==allocated_block_head){allocated_block_head=free_ab->next;free(free_ab);return ;}pre=allocated_block_head;ab=allocated_block_head->next;while(ab!=free_ab){pre=ab;ab=ab->next;}pre->next=ab->next;free(ab);}//终止进程，回收内存void kill_process(){struct allocated_block *ab;int pid;printf("Kill process,input pid = ");scanf("%d",&pid);ab=find_process(pid);if(ab!=NULL){free_mem(ab); //释放ab所表示的分配区dispose(ab); //释放ab数据结构节点printf("Kill Process Success!\n");return;}printf("Kill Process Failure!\n");}//显示当前内存的使用情况，包括空闲区的情况和已经分配的情况void display_mem_usage(){struct free_block_type *fbt=free_block;struct allocated_block *ab=allocated_block_head;/* 显示空闲区*/printf("----------------------------------------------------------\n");if(fbt==NULL)printf("success!\n");else{printf("Free Memory:\n");printf("%20s %20s\n", "\tstart_addr", " size");while(fbt!=NULL){printf("%20d %20d\n", fbt->start_addr, fbt->size);fbt=fbt->next;}}printf("----------------------------------------------------------\n");/* 显示已分配区*/if(ab==NULL)printf("尚未开始分配!\n");else{printf("\nUsed Memory:\n");printf("%10s %20s %10s %10s\n", "\tPID", " ProcessName", " start_addr ", "size");while(ab!=NULL){printf("%10d %20s %10d %10d\n", ab->pid, ab->process_name, ab->start_addr, ab->size);ab=ab->next;}}printf("----------------------------------------------------------\n");}//最佳适配算法void rearrage_BF(){struct free_block_type *p,*p1,*p2;struct free_block_type *last_flag;p1=(struct free_block_type *)malloc(sizeof(struct free_block_type));p1->next=free_block;free_block=p1;//不改变p1,free_block指向头p1if(free_block!=NULL){for (last_flag=NULL; last_flag!=free_block; last_flag=p){for (p=p1=free_block; p1->next!=NULL&&p1->next->next!=NULL&&p1->next->next!=last_flag; p1=p1->next){if (p1->next->size > p1->next->next->size){p2 = p1->next->next;p1->next->next = p2->next; //p2->next = p1->next;p1->next = p2;p = p1->next->next;}}}}p1 = free_block;free_block = free_block->next;free(p1);p1 = NULL;}//最差适配算法void rearrage_WF(){struct free_block_type *p,*p1,*p2;struct free_block_type *last_flag;p1=(struct free_block_type *)malloc(sizeof(struct free_block_type));p1->next=free_block;free_block=p1;//不改变p1,free_block指向头p1if(free_block!=NULL){for (last_flag=NULL; last_flag!=free_block; last_flag=p) {for (p=p1=free_block;p1->next!=NULL&&p1->next->next!=NULL&&p1->next->next!=last_flag; p1=p1->next){if (p1->next->size < p1->next->next->size){p2 = p1->next->next;p1->next->next = p2->next; //p2->next = p1->next;p1->next = p2;p = p1->next->next;}}}}p1 = free_block;free_block = free_block->next;free(p1);p1 = NULL;}//最快适配算法void rearrage_FF(){struct free_block_type *p,*p1,*p2;struct free_block_type *last_flag;p1=(struct free_block_type *)malloc(sizeof(struct free_block_type));p1->next=free_block;free_block=p1;//不改变p1,free_block指向头p1if(free_block!=NULL){for (last_flag=NULL; last_flag!=free_block; last_flag=p){for(p=p1=free_block;p1->next!=NULL&&p1->next->next!=NULL&&p1->next->next!=last_flag; p1=p1->next){if (p1->next->start_addr > p1->next->next->start_addr){p2 = p1->next->next;p1->next->next = p2->next;p2->next = p1->next;p1->next = p2;p = p1->next->next;}}}}p1 = free_block;free_block = free_block->next;free(p1);p1 = NULL;}//初始化空闲块struct free_block_type *init_free_block(int mem_size){struct free_block_type *fb;fb=(struct free_block_type *)malloc(sizeof(struct free_block_type));if(fb==NULL){printf("No Mem!\n");exit(1);}fb->size=mem_size;fb->start_addr=DEFAULT_MEM_START;fb->next=NULL;return fb;}void display_menu(){printf("\n");printf("----------------------------------------------------------\n");printf(" Memory management experiment \n");printf("1 - Set memory size (default=%d)\n", DEFAULT_MEM_SIZE);printf("2 - Select memory allocation algorithm\n");printf("3 - New process \n");printf("4 - kill a process \n");printf("5 - Display memory usage \n");printf("0 - Exit\n");printf("----------------------------------------------------------\n");}//选择分配算法void rearrange(int choice){switch(choice){case 1:rearrage_FF();break;case 2:rearrage_BF();break;case 3:rearrage_WF();break;}}//选择分配算法void set_algorithm(){int algorithm;printf("\t1 - First Fit\n");printf("\t2 - Best Fit \n");printf("\t3 - Worst Fit \n");scanf("%d", &algorithm);if(algorithm>=1 && algorithm <=3)ma_algorithm=algorithm;rearrange(ma_algorithm); //按指定算法重新排列空闲区链表}//设置内存大小void set_mem_size(){int size;if(flag!=0){printf("Cannot set memory size again or you have already started using the memory!\n");return;}printf("Total memory size =");scanf("%d", &size);if(size>0){mem_size = size;free_block->size = mem_size;}flag=1;}//退出void do_exit(){struct free_block_type *p1,*p2;struct allocated_block *a1,*a2;p1=free_block;if(p1!=NULL){p2=p1->next;for(;p2!=NULL;p1=p2,p2=p2->next){free(p1);}free(p1);}a1=allocated_block_head;if(a1!=NULL){a2=a1->next;for(;a2!=NULL;a1=a2,a2=a2->next){free(a1);}free(a1);}}。