內(nèi)存管理器實驗?zāi)康脑O(shè)計和實現(xiàn)關(guān)于內(nèi)存管理的內(nèi)存布局初始化及內(nèi)存申請分配、內(nèi)存回收等根本功能操作函數(shù)，嘗試對用256MB的內(nèi)存空間進行動態(tài)分區(qū)方式模擬管理。內(nèi)存分配的根本單位為1KB，同時要求支持至少兩種分配策略，并進行測試和對不同分配策略的性能展開比擬評估。實驗設(shè)計2.1．實驗要求1、設(shè)計一定的數(shù)據(jù)結(jié)構(gòu)以描述256MB內(nèi)存空間的使用狀況，并設(shè)計和構(gòu)建函數(shù)voidChuShuHuaNC(DIZHIzKS_KYNC,DIZHIzJS_KYNC)實現(xiàn)內(nèi)存布局的初始化。假定內(nèi)存空間的低址局部56MB〔即0~56M-1〕作為系統(tǒng)區(qū)和不參與分配過程。2、設(shè)計和實現(xiàn)內(nèi)存申請分配函數(shù)DIZHIShenQingNC(unsignedlongzDX)，內(nèi)存分配的根本單位為1KB，同時要求支持至少兩種分配策略〔如首次適應(yīng)、循環(huán)首次適應(yīng)、最正確適應(yīng)、最壞適應(yīng)等〕，假設(shè)分配失敗那么返回NULL。3、設(shè)計和實現(xiàn)內(nèi)存回收函數(shù)voidHuiShouNC(DIZHIzKSDZ)，假設(shè)回收分區(qū)與其它空閑分區(qū)相鄰接，那么采取合并措施。4、基于不同的內(nèi)存分配策略形成不同版本的內(nèi)存管理器，并根據(jù)內(nèi)存平均利用率〔指已分配內(nèi)存占總可分配內(nèi)存的平均比率〕和分配查找分區(qū)比擬次數(shù)等指標展開測試和對不同分配策略的內(nèi)存管理器性能進行評估。5、不妨設(shè)計測試例程框架：循環(huán){①產(chǎn)生隨機數(shù)，并根據(jù)該值確定是申請內(nèi)存還是回收內(nèi)存；②假設(shè)是申請內(nèi)存，還需進一步產(chǎn)生申請內(nèi)存大小〔服從正態(tài)/均勻分布〕；假設(shè)是回收內(nèi)存還需產(chǎn)生隨機數(shù)和選擇回收區(qū)；③收集測試數(shù)據(jù)用于性能評價；}數(shù)據(jù)結(jié)構(gòu)/*/*內(nèi)存空閑分區(qū)結(jié)構(gòu)塊*/typedefstructnode{ intaddr;//空閑分區(qū)的首址 intsize;//空閑分區(qū)的大小 intstatus;//空閑分區(qū)的狀態(tài)}blockblock*arry_empty_block[2048];block*arry_apply_block[2048];空空內(nèi)存塊結(jié)構(gòu)體數(shù)組已申請已申請內(nèi)存塊結(jié)構(gòu)體數(shù)組性能指標計算指標1：countcount為平均每次申請分配內(nèi)存時查找符合內(nèi)存大小的次數(shù)。計算公式：countquery_apply_count:總的查詢比擬次數(shù)apply_count:總的申請分配內(nèi)存次數(shù)指標2：raterate為每1000次對存儲設(shè)備操作后的平均內(nèi)存利用率。計算公式：rateall_rate:總的對內(nèi)存每次操作后的內(nèi)存利用率之和all_conut:對內(nèi)存的操作次數(shù)包括回收和分配程序清單1：變量解釋/**********************************************************************full:空閑分區(qū)的狀態(tài)為滿*empty：空閑分區(qū)的狀態(tài)為空*mix:允許產(chǎn)生的最大申請塊*min:允許申請的最小申請塊*memory_size：初始內(nèi)存大小〔256M-56M〕*memory_locate：累計內(nèi)存使用量*query_count_all：累計比擬次數(shù)*memory_empty_count:空閑分區(qū)的內(nèi)存塊數(shù)*memory_apply_count：申請成功的內(nèi)存塊數(shù)2：空間利用率函數(shù)******************************************************************************函數(shù)名：rate*功能：求空間利用率*返回值double*參數(shù)：無******************************************************************************函數(shù)實現(xiàn)******************************************************************************doublerate(){intsizeloction=0;for(inti=0;i<memory_apply_count;i++){sizeloction=arry_apply_block[i]->size+sizeloction;}求總的分配空間求總的分配空間}******************************************************************************3：正態(tài)分布隨機函數(shù)***********************************************************************函數(shù)名稱：radomNumber*功能：產(chǎn)生服從正態(tài)分布的一組隨機數(shù)*函數(shù)參數(shù)：intaverage〔平均數(shù)〕,intvariance〔方差〕*返回值：int************************************************************************函數(shù)實現(xiàn)：**********************************************************************//根據(jù)均值和方差算正態(tài)分布隨機數(shù) 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：內(nèi)存空間初始化函數(shù)/************************************************************************函數(shù)名：ChuShiHuaNC*功能：內(nèi)存空間初始化函數(shù)，構(gòu)造空閑分區(qū)數(shù)組*參數(shù)：無*返回值：無************************************************************************函數(shù)實現(xiàn)：/***********************************************************************voidChuShiHuaNC(){memory_locate=0;//累計內(nèi)存使用量置0query_count_all=0;//累計比擬次數(shù)置0memory_apply_count=0;//累計申請分配次數(shù)置0memory_empty_count=1;//空閑分區(qū)的內(nèi)存塊數(shù)置0 block*block_start=(block*)malloc(sizeof(block)); block_start->size=memory_size;block_start->addr=0;//空閑分區(qū)的首址置0 block_start->status=full; arry_empty_block[0]=block_start;}/***********************************************************************5．首次適應(yīng)算法函數(shù)/*************************************************************************函數(shù)名：FirstFit*功能：首次適應(yīng)算法*參數(shù)：intsize分配內(nèi)存空間的大小*返回值：int申請的內(nèi)存空間的起始地址**************************************************************************函數(shù)流程圖：函數(shù)實現(xiàn)：**************************************************************************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) {//申請空間剛好等于空塊 //此時空內(nèi)存塊剛好適宜，不用分割 //首先，在申請數(shù)組中添加申請塊 returnResult=arry_empty_block[location_temp]->addr; arry_apply_block[memory_apply_count]=arry_empty_block[location_temp]; memory_apply_count++;//在空內(nèi)存數(shù)組中去掉該內(nèi)存塊 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) {//申請空間小于空內(nèi)存塊的大小 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;//空內(nèi)存塊的修改，將大的塊改成小的空塊和申請塊 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;//置空內(nèi)存塊狀態(tài) //申請塊參加到申請數(shù)組 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：最正確適應(yīng)算法函數(shù)/****************************************************************************功能：最正確適應(yīng)算法*參數(shù)：intsize分配內(nèi)存空間的大小*返回值：int申請的內(nèi)存空間的起始地址***************************************************************************函數(shù)流程圖：函數(shù)實現(xiàn)***************************************************************************intBestFit(intsize){使用冒泡排序使得按使用冒泡排序使得按內(nèi)存增加的順序排列 intflag=0; intlocation_temp;//首先對空內(nèi)存塊的值按塊內(nèi)存大小進行排序，有小到大排序 //冒泡排序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) {//申請空間剛好等于空塊 //此時空內(nèi)存塊剛好適宜，不用分割 //首先，在申請數(shù)組中添加申請塊 returnResult=arry_empty_block[location_temp]->addr; arry_apply_block[memory_apply_count]=arry_empty_block[location_temp]; memory_apply_count++; //在空內(nèi)存數(shù)組中去掉該內(nèi)存塊 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) {//申請空間小于空內(nèi)存塊的大小 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;//空內(nèi)存塊的修改，將大的塊改成小的空塊和申請塊 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;//置空內(nèi)存塊狀態(tài)//申請塊參加到申請數(shù)組 arry_apply_block[memory_apply_count]=block_temp; memory_apply_count++; } elseif(flag==0) { //申請空間小于申請塊的大小 returnResult=-1; } returnreturnResult;}***************************************************************************7：最壞適應(yīng)算法函數(shù)/****************************************************************************功能：最壞適應(yīng)算法*參數(shù)：intsize分配內(nèi)存空間的大小*返回值：int申請的內(nèi)存空間的起始地址****************************************************************************函數(shù)流程圖函數(shù)實現(xiàn)：****************************************************************************intWorstFit(intsize){ intreturnResult; intflag=0; intlocation_temp;//首先對空內(nèi)存塊的值按塊內(nèi)存大小進行排序,有大到小排序 //冒泡排序使用冒泡排序使得按使用冒泡排序使得按內(nèi)存減小的順序排列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) {//申請空間剛好等于空塊 //此時空內(nèi)存塊剛好適宜，不用分割 //首先，在申請數(shù)組中添加申請塊 returnResult=arry_empty_block[location_temp]->addr; arry_apply_block[memory_apply_count]=arry_empty_block[location_temp]; memory_apply_count++;//在空內(nèi)存數(shù)組中去掉該內(nèi)存塊 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) {//申請空間小于空內(nèi)存塊的大小 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;//空內(nèi)存塊的修改，將大的塊改成小的空塊和申請塊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;//置空內(nèi)存塊狀態(tài)arry_apply_block[memory_apply_count]=block_temp;//申請塊參加到申請數(shù)組 memory_apply_count++; } elseif(flag==0) {//申請空間小于申請塊的大小returnResult=-1; } returnreturnResult;}****************************************************************************8：內(nèi)存回收函數(shù)/****************************************************************************函數(shù)名：HuiShouNC*功能：內(nèi)存回收函數(shù)，用來回收分配出去的內(nèi)存，*將其插入空閑分區(qū)數(shù)組中*參數(shù)：inttype使用的內(nèi)存分區(qū)分配算法的類型*返回值：block*回收的分區(qū)對應(yīng)的節(jié)點信息****************************************************************************函數(shù)流程圖：函數(shù)實現(xiàn)：****************************************************************************block*HuiShouNC(){ intflag=1;//當(dāng)為情況2和3時flag為0，當(dāng)為情況1時，flag為1； block*result;//隨機產(chǎn)生要回收的塊 if(memory_apply_count>0) { intn=Random(0,memory_apply_count-1);//首先在申請數(shù)組中找到該回收塊 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--; }//在空內(nèi)存數(shù)組中詳細處理 //存在三種情況//情況1：該會回收區(qū)上下都沒空內(nèi)存分區(qū)，單純的參加空內(nèi)存分區(qū)的數(shù)組就好//情況2：該內(nèi)存回收區(qū)或上面是或下面是空內(nèi)存分區(qū)，或上或下合并//情況3：該內(nèi)存回收區(qū)上面和下面都是空內(nèi)存分區(qū)，上下合并 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位置的空閑分區(qū)塊 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) {//如果為空分區(qū)的最后一個〔特殊情況〕 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：主函數(shù)/****************************************************************************函數(shù)名：Main*功能：程序的入口和測試函數(shù)*參數(shù)：無*返回值：無****************************************************************************函數(shù)流程圖：函數(shù)實現(xiàn)****************************************************************************intmain(){ printf("選擇申請分配內(nèi)存方法\n"); printf("--------------------------\n"); printf("|0:|\t結(jié)束該程序運行\(zhòng)t|\n"); printf("--------------------------\n"); printf("|1:|\t首次適應(yīng)算法\t|\n"); printf("--------------------------\n"); printf("|2:|\t循環(huán)適應(yīng)算法\t|\n"); printf("--------------------------\n"); printf("|3:|\t最正確適應(yīng)算法\t|\n"); printf("--------------------------\n"); printf("|4:|\t最壞適應(yīng)算法\t|\n"); printf("--------------------------\n"); printf("輸入要選擇的算法代號\n"); scanf("%d",&style); intrand_size; intrand_style; intcircle=1000; intapply_count=0;//申請內(nèi)存分配次數(shù) doublerate1=0;//利用率 block*p; srand((unsigned)time(NULL));//生成隨機數(shù) 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);//生成符合正態(tài)分布數(shù) //printf("%d\n",rand_size); apply_count++; switch(style) { case1: FirstFit(rand_size);//最先適應(yīng)算法 break; case2: BestFit(ran