模拟内存管理设计与实现

内存管理器实验目的设计和实现关于内存管理的内存布局初始化及内存申请分配、内存回收等根本功能操作函数，尝试对用256MB的内存空间进行动态分区方式模拟管理。内存分配的根本单位为1KB，同时要求支持至少两种分配策略，并进行测试和对不同分配策略的性能展开比拟评估。实验设计2.1．实验要求1、设计一定的数据结构以描述256MB内存空间的使用状况，并设计和构建函数voidChuShuHuaNC(DIZHIzKS_KYNC,DIZHIzJS_KYNC)实现内存布局的初始化。假定内存空间的低址局部56MB〔即0~56M-1〕作为系统区和不参与分配过程。2、设计和实现内存申请分配函数DIZHIShenQingNC(unsignedlongzDX)，内存分配的根本单位为1KB，同时要求支持至少两种分配策略〔如首次适应、循环首次适应、最正确适应、最坏适应等〕，假设分配失败那么返回NULL。3、设计和实现内存回收函数voidHuiShouNC(DIZHIzKSDZ)，假设回收分区与其它空闲分区相邻接，那么采取合并措施。4、基于不同的内存分配策略形成不同版本的内存管理器，并根据内存平均利用率〔指已分配内存占总可分配内存的平均比率〕和分配查找分区比拟次数等指标展开测试和对不同分配策略的内存管理器性能进行评估。5、不妨设计测试例程框架：循环{①产生随机数，并根据该值确定是申请内存还是回收内存；②假设是申请内存，还需进一步产生申请内存大小〔服从正态/均匀分布〕；假设是回收内存还需产生随机数和选择回收区；③收集测试数据用于性能评价；}数据结构/*/*内存空闲分区结构块*/typedefstructnode{ intaddr;//空闲分区的首址 intsize;//空闲分区的大小 intstatus;//空闲分区的状态}blockblock*arry_empty_block[2048];block*arry_apply_block[2048];空空内存块结构体数组已申请已申请内存块结构体数组性能指标计算指标1：countcount为平均每次申请分配内存时查找符合内存大小的次数。计算公式：countquery_apply_count:总的查询比拟次数apply_count:总的申请分配内存次数指标2：raterate为每1000次对存储设备操作后的平均内存利用率。计算公式：rateall_rate:总的对内存每次操作后的内存利用率之和all_conut:对内存的操作次数包括回收和分配程序清单1：变量解释/**********************************************************************full:空闲分区的状态为满*empty：空闲分区的状态为空*mix:允许产生的最大申请块*min:允许申请的最小申请块*memory_size：初始内存大小〔256M-56M〕*memory_locate：累计内存使用量*query_count_all：累计比拟次数*memory_empty_count:空闲分区的内存块数*memory_apply_count：申请成功的内存块数2：空间利用率函数******************************************************************************函数名：rate*功能：求空间利用率*返回值double*参数：无******************************************************************************函数实现******************************************************************************doublerate(){intsizeloction=0;for(inti=0;i<memory_apply_count;i++){sizeloction=arry_apply_block[i]->size+sizeloction;}求总的分配空间求总的分配空间}******************************************************************************3：正态分布随机函数***********************************************************************函数名称：radomNumber*功能：产生服从正态分布的一组随机数*函数参数：intaverage〔平均数〕,intvariance〔方差〕*返回值：int************************************************************************函数实现：**********************************************************************//根据均值和方差算正态分布随机数 doubleu=((double)rand())/(RAND_MAX)*2-1; doublev=((double)rand())/(RAND_MAX)*2-1; doubler=u*u+v*v; if(r==0||r>1)returnradomNumber(average,variance); doublec=sqrt(-2*log(r)/r); doubleresult=(u*v)*variance+average; return(int)result;************************************************************************4：内存空间初始化函数/************************************************************************函数名：ChuShiHuaNC*功能：内存空间初始化函数，构造空闲分区数组*参数：无*返回值：无************************************************************************函数实现：/***********************************************************************voidChuShiHuaNC(){memory_locate=0;//累计内存使用量置0query_count_all=0;//累计比拟次数置0memory_apply_count=0;//累计申请分配次数置0memory_empty_count=1;//空闲分区的内存块数置0 block*block_start=(block*)malloc(sizeof(block)); block_start->size=memory_size;block_start->addr=0;//空闲分区的首址置0 block_start->status=full; arry_empty_block[0]=block_start;}/***********************************************************************5．首次适应算法函数/*************************************************************************函数名：FirstFit*功能：首次适应算法*参数：intsize分配内存空间的大小*返回值：int申请的内存空间的起始地址**************************************************************************函数流程图：函数实现：**************************************************************************intFirstFit(intsize){ intreturnResult; intflag=0; intlocation_temp; for(inti=0;i<memory_empty_count;i++) { query_count_all++; intceshi=arry_empty_block[i]->size; if(size>ceshi) {i++;} elseif(size==arry_empty_block[i]->size) { location_temp=i; flag=1; break; } elseif(size<ceshi) { location_temp=i; flag=2; break; } } if(flag==1) {//申请空间刚好等于空块 //此时空内存块刚好适宜，不用分割 //首先，在申请数组中添加申请块 returnResult=arry_empty_block[location_temp]->addr; arry_apply_block[memory_apply_count]=arry_empty_block[location_temp]; memory_apply_count++;//在空内存数组中去掉该内存块 if(location_temp==memory_empty_count-1) { memory_empty_count--; } else { for(intj=location_temp;j<memory_empty_count-1;j++) { arry_empty_block[location_temp]=arry_empty_block[location_temp+1]; } memory_empty_count--; } } elseif(flag==2) {//申请空间小于空内存块的大小 block*block_temp=(block*)malloc(sizeof(block)); block_temp->size=size; block_temp->addr=arry_empty_block[location_temp]->addr; block_temp->status=empty; returnResult=arry_empty_block[location_temp]->addr;//空内存块的修改，将大的块改成小的空块和申请块 arry_empty_block[location_temp]->size=arry_empty_block[location_temp]->size-size;//修改size arry_empty_block[location_temp]->addr=arry_empty_block[location_temp]->addr+size;//修改addr arry_empty_block[location_temp]->status=empty;//置空内存块状态 //申请块参加到申请数组 arry_apply_block[memory_apply_count]=block_temp; memory_apply_count++; } elseif(flag==0)使用冒泡排序使得按地址使用冒泡排序使得按地址增加的顺序排列//申请空间小于申请块的大小 returnResult=-1; }//冒泡排序，按地址排序 //排序，从a[0]开始排，从小到大for(inti=0;i<memory_empty_count;i++)for(inti=0;i<memory_empty_count;i++) { for(intj=i+1;j<memory_empty_count;j++) { if(arry_empty_block[i]->addr>arry_empty_block[j]->addr) { block*temp1; temp1=arry_empty_block[i]; arry_empty_block[i]=arry_empty_block[j]; arry_empty_block[j]=temp1; } } } returnreturnResult;}**************************************************************************6：最正确适应算法函数/****************************************************************************功能：最正确适应算法*参数：intsize分配内存空间的大小*返回值：int申请的内存空间的起始地址***************************************************************************函数流程图：函数实现***************************************************************************intBestFit(intsize){使用冒泡排序使得按使用冒泡排序使得按内存增加的顺序排列 intflag=0; intlocation_temp;//首先对空内存块的值按块内存大小进行排序，有小到大排序 //冒泡排序for(inti=0;i<memory_empty_count;i++)for(inti=0;i<memory_empty_count;i++) { for(intj=i+1;j<memory_empty_count;j++) { if(arry_empty_block[i]->addr>arry_empty_block[j]->addr) { block*temp1; temp1=arry_empty_block[i]; arry_empty_block[i]=arry_empty_block[j]; arry_empty_block[j]=temp1; } } } for(inti=0;i<memory_empty_count;i++) { query_count_all++; intceshi=arry_empty_block[i]->size; if(size>ceshi) { i++; } elseif(size==arry_empty_block[i]->size) {location_temp=i; flag=1; break; } elseif(size<ceshi) { location_temp=i; flag=2; break; } } if(flag==1) {//申请空间刚好等于空块 //此时空内存块刚好适宜，不用分割 //首先，在申请数组中添加申请块 returnResult=arry_empty_block[location_temp]->addr; arry_apply_block[memory_apply_count]=arry_empty_block[location_temp]; memory_apply_count++; //在空内存数组中去掉该内存块 if(location_temp==memory_empty_count-1) { memory_empty_count--; } else { for(intj=location_temp;j<memory_empty_count-1;j++) { arry_empty_block[location_temp]=arry_empty_block[location_temp+1]; } memory_empty_count--; } } elseif(flag==2) {//申请空间小于空内存块的大小 block*block_temp=(block*)malloc(sizeof(block)); block_temp->size=size; block_temp->addr=arry_empty_block[location_temp]->addr; block_temp->status=empty; returnResult=arry_empty_block[location_temp]->addr;//空内存块的修改，将大的块改成小的空块和申请块 arry_empty_block[location_temp]->size=arry_empty_block[location_temp]->size-size;//修改size arry_empty_block[location_temp]->addr=arry_empty_block[location_temp]->addr+size;//修改addr arry_empty_block[location_temp]->status=empty;//置空内存块状态//申请块参加到申请数组 arry_apply_block[memory_apply_count]=block_temp; memory_apply_count++; } elseif(flag==0) { //申请空间小于申请块的大小 returnResult=-1; } returnreturnResult;}***************************************************************************7：最坏适应算法函数/****************************************************************************功能：最坏适应算法*参数：intsize分配内存空间的大小*返回值：int申请的内存空间的起始地址****************************************************************************函数流程图函数实现：****************************************************************************intWorstFit(intsize){ intreturnResult; intflag=0; intlocation_temp;//首先对空内存块的值按块内存大小进行排序,有大到小排序 //冒泡排序使用冒泡排序使得按使用冒泡排序使得按内存减小的顺序排列for(inti=0;i<memory_empty_count;i++)for(inti=0;i<memory_empty_count;i++) { for(intj=i+1;j<memory_empty_count;j++) { if(arry_empty_block[i]->addr>arry_empty_block[j]->addr) { block*temp1; temp1=arry_empty_block[i]; arry_empty_block[i]=arry_empty_block[j]; arry_empty_block[j]=temp1; } } } for(inti=0;i<memory_empty_count;i++) { query_count_all++; intceshi=arry_empty_block[i]->size; if(size>ceshi) { i++; } elseif(size==arry_empty_block[i]->size) { location_temp=i; flag=1; break; } elseif(size<ceshi) { location_temp=i; flag=2; break; } } if(flag==1) {//申请空间刚好等于空块 //此时空内存块刚好适宜，不用分割 //首先，在申请数组中添加申请块 returnResult=arry_empty_block[location_temp]->addr; arry_apply_block[memory_apply_count]=arry_empty_block[location_temp]; memory_apply_count++;//在空内存数组中去掉该内存块 if(location_temp==memory_empty_count-1) {memory_empty_count--;} else {for(intj=location_temp;j<memory_empty_count-1;j++) {arry_empty_block[location_temp]=arry_empty_block[location_temp+1]; } memory_empty_count--; } } elseif(flag==2) {//申请空间小于空内存块的大小 block*block_temp=(block*)malloc(sizeof(block)); block_temp->size=size; block_temp->addr=arry_empty_block[location_temp]->addr; block_temp->status=empty; returnResult=arry_empty_block[location_temp]->addr;//空内存块的修改，将大的块改成小的空块和申请块arry_empty_block[location_temp]->size=arry_empty_block[location_temp]->size-size;//修改sizearry_empty_block[location_temp]->addr=arry_empty_block[location_temp]->addr+size;//修改addrarry_empty_block[location_temp]->status=empty;//置空内存块状态arry_apply_block[memory_apply_count]=block_temp;//申请块参加到申请数组 memory_apply_count++; } elseif(flag==0) {//申请空间小于申请块的大小returnResult=-1; } returnreturnResult;}****************************************************************************8：内存回收函数/****************************************************************************函数名：HuiShouNC*功能：内存回收函数，用来回收分配出去的内存，*将其插入空闲分区数组中*参数：inttype使用的内存分区分配算法的类型*返回值：block*回收的分区对应的节点信息****************************************************************************函数流程图：函数实现：****************************************************************************block*HuiShouNC(){ intflag=1;//当为情况2和3时flag为0，当为情况1时，flag为1； block*result;//随机产生要回收的块 if(memory_apply_count>0) { intn=Random(0,memory_apply_count-1);//首先在申请数组中找到该回收块 result=arry_apply_block[n]; if(n==memory_apply_count-1) { memory_apply_count--; } else { for(inttemp=n;temp<memory_apply_count-1;temp++) { arry_apply_block[n]=arry_apply_block[n+1]; } memory_apply_count--; }//在空内存数组中详细处理 //存在三种情况//情况1：该会回收区上下都没空内存分区，单纯的参加空内存分区的数组就好//情况2：该内存回收区或上面是或下面是空内存分区，或上或下合并//情况3：该内存回收区上面和下面都是空内存分区，上下合并 intaddr=arry_apply_block[n]->addr; intsize=arry_apply_block[n]->size; for(inti=0;i<memory_empty_count;i++) {if((arry_empty_block[i]->addr+arry_empty_block[i]->size)==addr) { flag=0; if(i<memory_empty_count-1) { if(addr+size==arry_apply_block[i+1]->addr) { //情况3,上下合并arry_empty_block[i]->size=arry_empty_block[i]->size+size+arry_empty_block[i+1]->size; result=arry_empty_block[i];//删除i+1位置的空闲分区块 inttempi=i+1; for(;tempi<memory_empty_count;tempi++) { arry_empty_block[tempi]=arry_empty_block[tempi+1];} memory_empty_count--; break;}else{//情况2的上合并 arry_empty_block[i]->size=arry_empty_block[i]->size+size; result=arry_empty_block[i]; break;}} elseif(i==memory_empty_count-1) {//如果为空分区的最后一个〔特殊情况〕 arry_empty_block[i]->size=arry_empty_block[i]->size+size; result=arry_empty_block[i];break;}}elseif(addr+size==arry_empty_block[i]->addr){flag=0;//情况2的下合并arry_empty_block[i]->addr=addr;arry_empty_block[i]->size=arry_empty_block[i]->size+size;result=arry_empty_block[i];break;} } if(flag==1) {//情况1 block*block_temp1=(block*)malloc(sizeof(block)); arry_empty_block[memory_empty_count]=block_temp1; arry_empty_block[memory_empty_count]->addr=addr; arry_empty_block[memory_empty_count]->size=size; arry_empty_block[memory_empty_count]->status=full; memory_empty_count++; result=arry_apply_block[n]; } returnresult; } else returnNULL;}***************************************************************************9：主函数/****************************************************************************函数名：Main*功能：程序的入口和测试函数*参数：无*返回值：无****************************************************************************函数流程图：函数实现****************************************************************************intmain(){ printf("选择申请分配内存方法\n"); printf("--------------------------\n"); printf("|0:|\t结束该程序运行\t|\n"); printf("--------------------------\n"); printf("|1:|\t首次适应算法\t|\n"); printf("--------------------------\n"); printf("|2:|\t循环适应算法\t|\n"); printf("--------------------------\n"); printf("|3:|\t最正确适应算法\t|\n"); printf("--------------------------\n"); printf("|4:|\t最坏适应算法\t|\n"); printf("--------------------------\n"); printf("输入要选择的算法代号\n"); scanf("%d",&style); intrand_size; intrand_style; intcircle=1000; intapply_count=0;//申请内存分配次数 doublerate1=0;//利用率 block*p; srand((unsigned)time(NULL));//生成随机数 while(style!=0) { ChuShiHuaNC(); circle=1000; rate1=0; while(circle>0) { rand_style=Random(1,20); if(rand_style<17) { rand_size=radomNumber(500,1000);//生成符合正态分布数 //printf("%d\n",rand_size); apply_count++; switch(style) { case1: FirstFit(rand_size);//最先适应算法 break; case2: BestFit(ran