内存管理实验报告.doc

操作系统实验报告专业 网络工程 班级 08102 学号 姓名 课程名称操作系统 学年20102011 学期 下课程类别专业必修 限选任选实践实验时间 2010年12月9日实验名称实验三：内存管理实验目的和要求1、 加深对动态内存分区的理解2、 掌握3种常用的分配方式3、 编写程序完成实验内容及实验报告实验软硬件要求Pentium | 450以上 CPU 64MB以上 内存WINDOWS XP Visual C+6.0实验内容、方法和步骤（可附页）1、 设计结构体模拟物理内存块2、 分别模拟FF、BF、WF三种适应算法动态地创建进程3、 能够动态地销毁进程并更新可用表与已分配表4、 显示出各个时间段内存块中已分配表与可用表的情况实验结果（可附页）见截图小结这次的内存管理实验让我对动态内存分区管理的3种常用算法，即FF、BF、WF适应算法有了更为深刻的认识，也进一步锻炼了自己解决实际问题的能力。动态内存分区需解决找到可用分配内存块、分配内存、更新可用表与已分配表以及在销毁进程时完成相邻空闲区的合并。实验中遇到的问题的是不能实现进程的动态销毁并刷新可用表与已分配表，后面通过向同学请教，加上不断地编写调试，终于得到了理想的效果。评定成绩：批阅教师： 年月日 1、 问题概述动态分区的分配与回收主要解决3个问题：（1） 对于请求表中的要求内存长度，从可用表或自由链寻找出合适的空闲区分配程序（2） 分配空闲区之后，更新可用表或自由链（3） 进程或作业释放内存资源时，合并相邻空闲区并刷新可用表动态分区时的分配方法有最先适应法（FF）、最佳适应法（BF）及最坏适应法（WF）三种：FF适应法要求可用表按起始地址递增次序排列，一旦找到大于或等于要求内存长度的可用块时立即分配；BF适应算法要求从小到大的次序组成可用表，每次分配可用表中长度与要求分配的内存块最接近的内存块；WF适应法要求可用表按长度大小递减排列，每次分配可用表中长度最大的内存块。二、 设计流程图主要流程： 开 始初始化内存块功能选择输入1输入2创建进程销毁进程更新可用表与已分配表WF适应法BF适应法FF适应法打印输出内存状态结 束图1 主流程图FF适应法流程图：开 始按内存块的起始地址递增排列可用表空闲表是否为空？是否从可用表队首开始找地址长度大于要求长度的地址块否找到可分配的内存块？是没有可用的内存块进行地址分配，修改已分配表与可用表结 束图2 FIFO适应法流程图开 始BF适应法流程图：按内存块的长度递增排列可用表是空闲表是否为空？否从可用表队首开始找地址长度大于要求长度的地址块否找到可分配的内存块？是没有可用的内存块进行地址分配，修改已分配表与可用表结 束图3 BF适应法流程图WF适应法流程图：开 始按内存块的长度递减排列可用表是空闲表是否为空？否从可用表队首开始找地址长度大于要求长度的地址块否找到可分配的内存块？没有可用的内存块是进行地址分配，修改已分配表与可用表结 束图4 WF适应法流程图3、 数据定义struct allocatedint id;/分配的进程号int size;/地址长度int start;/起始地址struct allocated *next;struct all_blockint size;/整个内存块长度int select;/分配方式struct free *f;struct allocated *a;struct all_block *all;/内存块头指针struct free *f;struct allocated *al;int number;/进程个数int pid;4、 源程序1、 首次适应算法 int FF(int size) /*首次适应算法*/ struct free *free_f1,*free_f2;int mem_size=size; free_f1=all-f; free_f2=free_f1-next; for(free_f1=all-f;free_f1!=NULL;free_f1=free_f1-next) for(free_f2=free_f1-next;free_f2!=NULL;free_f2=free_f2-next) if(free_f2-startstart) free_f1-start=free_f2-start; ree_f1-size=free_f2-size; /*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size0) set_pro_mem(mem_size);return 1; 2、 最佳适应算法 int BF(int size) /*最佳适应算法*/ struct free *free_f1,*free_f2; int mem_size=size; free_f1=all-f; free_f2=free_f1-next; for(free_f1=all-f;free_f1!=NULL;free_f1=free_f1-next) for(free_f2=free_f1-next;free_f2!=NULL;free_f2=free_f2-next) if(free_f2-sizesize) free_f1-start=free_f2-start; free_f1-size=free_f2-size; /*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size0)set_pro_mem(mem_size); return 1;3、 最坏适应算法 int WF(int size) /*最坏分配算法*/ struct free *free_f1,*free_f2; int mem_size=size; free_f1=all-f; free_f2=free_f1-next; for(free_f1=all-f;free_f1!=NULL;free_f1=free_f1-next) for(free_f2=free_f1-next;free_f2!=NULL;free_f2=free_f2-next) if(free_f2-sizesize) free_f1-start=free_f2-start; free_f1-size=free_f2-size; /*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size0) set_pro_mem(mem_size); return 1;5、 运行结果初始化内存块空间如下：（15K） JI（20K）J2（25K）J3（8K） 0 15 30 45 55 80 90 100则该内存块的可用内存块有4块，其地址分别为015K，2545K，5580K，92100K，长度分别为15K、20K、25K、8K运行截图如下：图5 初始化内存块截图1、 用FF适应法为J4分配内存，大小为16K，按照FF适应算法，应该从第二块空闲块中分出16K给J4，然后更新已用表与可用表，结果如下：（15K） JIJ4（4K）J2（25K）J3 （8K） 0 15 25 41 45 55 80 92 100截图如下:图6 FF适应法运行截图2、 继续用BF适应法为J5分配内存，大小为6K，按照BF适应算法，应该从第四块空闲块中分出6K给J5，然后更新已用表与可用表，结果如下： （15K）JIJ4 （4K）J2 （25K）J3J5 （2K） 0 15 25 41 45 55 80 92 98 100截图如下：图7 BF适应法运行截图3、 继续用WF适应法为J6分配内存，大小为15K，按照WF适应算法，应该从第块空闲块中分出6K给J5，然后更新已用表与可用表，结果如下: （15K）JIJ4 （4K）J2J6 （10K）J3J5 （2K） 0 15 25 41 45 55 70 80 92 98 100截图如下：图8 WF适应法运行截图4、 销毁进程J1、J3，刷新已用表与可用表，结果如下： （25K）J4 （4K）J2J6 （22K）J5 （2K） 0 25 41 45 55 70 92 98 100运行截图如下：图9 FF适应法运行截图分析以上各图，可知结果正确。附:#include#include#include#include#include struct freeint size;/地址长度int start;/起始地址struct free *next;struct allocatedint id;/分配的进程号int size;/地址长度int start;/起始地址struct allocated *next;struct all_blockint size;/整个内存块长度int select;/分配方式struct free *f;struct allocated *a;struct all_block *all;/内存块头指针struct free *f;struct allocated *al;int number;/进程个数int pid;void chushi_all(int s)all=(struct all_block *)malloc(sizeof(struct all_block);all-f=(struct free *)malloc(sizeof(struct free);all-a=(struct allocated *)malloc(sizeof(struct allocated);all-size=s;all-f-size=s; all-f-start=0; all-f-next=NULL;all-a-next=NULL;void chushi_allocated()struct allocated* ab;struct free *f1;f1=all-f;ab=all-a;int size;int start;while(ab-next!=NULL)ab=ab-next;ab-next=(struct allocated *)malloc(sizeof(struct allocated);ab-next-id=pid;printf(n进程%d:,pid);printf(n分配的地址长度:);scanf(%d,&size);ab-next-size=size;printf(分配的起始地址:);scanf(%d,&start);ab-next-start=start;ab-next-next=NULL;while(f1-next!=NULL)if(startf1-start)&(start+size)size+f1-start)struct free* f2;f2=(struct free *)malloc(sizeof(struct free);f2-next=f1-next;f2-size=(f1-size-size);f1-size=(f1-size-size);f2-start=(size+start);f1-next=f2;break;f1=f1-next;int set_pro_mem(int mem_size) struct free *f1,*f2; struct allocated *a1; f1=all-f; f2=f1; a1=all-a; while(f1!=NULL & f1-sizenext; else f1=f1-next;f2=f2-next; if(f1=NULL) printf(没有足够分配的空间!n); return 0; if(f1-size=mem_size ) while(a1-next!=NULL) a1=a1-next; a1-next=(struct allocated *)malloc(sizeof(struct allocated); a1-next-id=pid; a1-next-size=f1-size; a1-next-start=f1-start; /sprintf(a1-next-process_name,PROCESS-%02d,pid); a1-next-next=NULL; if(f1=f2) all-f=f1-next; free(f1); else f2-next=f1-next; free(f1); else if(f1-sizemem_size) while(a1-next!=NULL)a1=a1-next; a1-next=(struct allocated*)malloc(sizeof(struct allocated); a1-next-id=pid; a1-next-size=mem_size; a1-next-start=f1-start; /sprintf(a1-next-process_name,PROCESS-%02d,pid); a1-next-next=NULL; f1-size=(f1-size)-mem_size; f1-start=(f1-start)+mem_size; return 1;int FF(int size) /*首次适应算法*/ struct free *free_f1,*free_f2; int mem_size; mem_size=size; free_f1=all-f; free_f2=free_f1-next; for(free_f1=all-f;free_f1!=NULL;free_f1=free_f1-next) for(free_f2=free_f1-next;free_f2!=NULL;free_f2=free_f2-next) if(free_f2-startstart) free_f1-start=free_f2-start; free_f1-size=free_f2-size; /*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size0) set_pro_mem(mem_size); return 1;int BF(int size) /*最佳适应算法*/ struct free *free_f1,*free_f2; int mem_size; mem_size=size; free_f1=all-f; free_f2=free_f1-next; for(free_f1=all-f;free_f1!=NULL;free_f1=free_f1-next) for(free_f2=free_f1-next;free_f2!=NULL;free_f2=free_f2-next) if(free_f2-sizesize) free_f1-start=free_f2-start; free_f1-size=free_f2-size; /*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size0)set_pro_mem(mem_size); return 1;int WF(int size) /*最坏分配算法*/ struct free *free_f1,*free_f2; int mem_size; mem_size=size; free_f1=all-f; free_f2=free_f1-next; for(free_f1=all-f;free_f1!=NULL;free_f1=free_f1-next) for(free_f2=free_f1-next;free_f2!=NULL;free_f2=free_f2-next) if(free_f2-sizesize) free_f1-start=free_f2-start; free_f1-size=free_f2-size; /*用冒泡排序法实现对空闲链表内空闲区的按起始地址的递增排序*/ if(mem_size0) set_pro_mem(mem_size); return 1;void menu1()int select;int size;printf(请输入所需内存大小:);scanf(%d,&size);printf(选择内存分配方式:);printf(1 FF 2 BF 3 WF);scanf(%d,&select);switch(select)case 1:FF(size);break;case 2:BF(size);break; case 3:WF(size);break;default:break;struct allocated* find(int id)/*进程查找函数*/ struct allocated *allo; allo=all-a-next; while(allo!=NULL&allo-id!=id) allo=allo-next; return allo;int free_block(struct allocated *ab)/释放空间，修改可用表 struct free *ftb,*work,*work_f,*temp; ftb=(struct free*)malloc(sizeof(struct free); ftb-start=ab-start; ftb-size=ab-size; ftb-next=all-f; all-f=ftb; ftb=all-f; work_f=all-f; work=work_f-next; while(work!=NULL) if(ftb-start+ftb-size=work-start) ftb-size=ftb-size+work-size; temp=work; work_f-next=work-next; work_f=all-f; work=work_f-next; free(temp); else if(work-start+work-size=ftb-start) ftb-start=work-start; ftb-size=ftb-size+work-size; temp=work; work_f-next=work-next; work_f=all-f; work=work_f-next; free(temp); else work=work-next; work_f=work_f-next; return 1;int menu2()int id;struct allocated *ab,*allo;ab=all-a;printf(输入要销毁的进程号: );scanf(%d,&id);allo=find(id); if(allo=NULL) printf(没有该进程!n); return 0;if(ab=ab)all-a=all-a-next;return 1; while(ab-next