模擬內(nèi)存管理設(shè)計(jì)與實(shí)現(xiàn).docx

內(nèi)存管理器1. 實(shí)驗(yàn)?zāi)康脑O(shè)計(jì)和實(shí)現(xiàn)關(guān)于內(nèi)存管理的內(nèi)存布局初始化及內(nèi)存申請分配、內(nèi)存回收等基本功能操作函數(shù)，嘗試對用256MB的內(nèi)存空間進(jìn)行動態(tài)分區(qū)方式模擬管理。內(nèi)存分配的基本單位為1KB，同時要求支持至少兩種分配策略，并進(jìn)行測試和對不同分配策略的性能展開比較評估。2. 實(shí)驗(yàn)設(shè)計(jì)2.1 實(shí)驗(yàn)要求l 1、設(shè)計(jì)一定的數(shù)據(jù)結(jié)構(gòu)以描述256MB內(nèi)存空間的使用狀況，并設(shè)計(jì)和構(gòu)建函數(shù)void ChuShuHuaNC (DIZHI zKS_KYNC, DIZHI zJS_KYNC)實(shí)現(xiàn)內(nèi)存布局的初始化。假定內(nèi)存空間的低址部分56MB（即056M-1）作為系統(tǒng)區(qū)和不參與分配過程。l 2、設(shè)計(jì)和實(shí)現(xiàn)內(nèi)存申請分配函數(shù)DIZHI ShenQingNC(unsigned long zDX)，內(nèi)存分配的基本單位為1KB，同時要求支持至少兩種分配策略（如首次適應(yīng)、循環(huán)首次適應(yīng)、最佳適應(yīng)、最壞適應(yīng)等），若分配失敗則返回NULL。l 3、設(shè)計(jì)和實(shí)現(xiàn)內(nèi)存回收函數(shù)void HuiShouNC(DIZHI zKSDZ) ，若回收分區(qū)與其它空閑分區(qū)相鄰接，則采取合并措施。l 4、基于不同的內(nèi)存分配策略形成不同版本的內(nèi)存管理器，并根據(jù)內(nèi)存平均利用率（指已分配內(nèi)存占總可分配內(nèi)存的平均比率）和分配查找分區(qū)比較次數(shù)等指標(biāo)展開測試和對不同分配策略的內(nèi)存管理器性能進(jìn)行評估。l 5、不妨設(shè)計(jì)測試?yán)炭蚣埽貉h(huán) 產(chǎn)生隨機(jī)數(shù)，并根據(jù)該值確定是申請內(nèi)存還是回收內(nèi)存； 若是申請內(nèi)存，還需進(jìn)一步產(chǎn)生申請內(nèi)存大?。ǚ恼龖B(tài)/均勻分布）；若是回收內(nèi)存還需產(chǎn)生隨機(jī)數(shù)和選擇回收區(qū)； 收集測試數(shù)據(jù)用于性能評價；2.2. 數(shù)據(jù)結(jié)構(gòu)/*內(nèi)存空閑分區(qū)結(jié)構(gòu)塊*/typedef struct nodeint addr; /空閑分區(qū)的首址int size; /空閑分區(qū)的大小int status; /空閑分區(qū)的狀態(tài)blockblock* arry_empty_block2048;block* arry_apply_block2048;空內(nèi)存塊結(jié)構(gòu)體數(shù)組已申請內(nèi)存塊結(jié)構(gòu)體數(shù)組2.3. 性能指標(biāo)計(jì)算指標(biāo)1：countcount為平均每次申請分配內(nèi)存時查找符合內(nèi)存大小的次數(shù)。計(jì)算公式：count=query_apply_countapply_countquery_apply_count:總的查詢比較次數(shù)apply_count:總的申請分配內(nèi)存次數(shù)指標(biāo)2：raterate為每1000次對存儲設(shè)備操作后的平均內(nèi)存利用率。計(jì)算公式： rate=all_rateall_countall_rate:總的對內(nèi)存每次操作后的內(nèi)存利用率之和all_conut:對內(nèi)存的操作次數(shù)包括回收和分配3. 程序清單1：變量解釋/*full:空閑分區(qū)的狀態(tài)為滿*empty：空閑分區(qū)的狀態(tài)為空*mix:允許產(chǎn)生的最大申請塊*min:允許申請的最小申請塊*memory_size：初始內(nèi)存大?。?56M-56M）*memory_locate：累計(jì)內(nèi)存使用量*query_count_all：累計(jì)比較次數(shù)*memory_empty_count:空閑分區(qū)的內(nèi)存塊數(shù)*memory_apply_count：申請成功的內(nèi)存塊數(shù)2：空間利用率函數(shù)*函數(shù)名：rate*功能： 求空間利用率*返回值 double*參數(shù)： 無*函數(shù)實(shí)現(xiàn)*double rate() int sizeloction=0; for (int i = 0; i size+ sizeloction; 求總的分配空間 return double(double(sizeloction) / 204800);*3：正態(tài)分布隨機(jī)函數(shù)*函數(shù)名稱：radomNumber*功能：產(chǎn)生服從正態(tài)分布的一組隨機(jī)數(shù)*函數(shù)參數(shù)：int average（平均數(shù)）, int variance（方差）*返回值：int *函數(shù)實(shí)現(xiàn)：*/ 根據(jù)均值和方差算正態(tài)分布隨機(jī)數(shù)double u = (double)rand() / (RAND_MAX) * 2 - 1;double v = (double)rand() / (RAND_MAX) * 2 - 1;double r = u * u + v * v;if (r = 0 | r 1) return radomNumber(average, variance);double c = sqrt(-2 * log(r) / r);double result = (u * v) * variance + average;return (int)result;*4：內(nèi)存空間初始化函數(shù)/*函數(shù)名：ChuShiHuaNC*功能： 內(nèi)存空間初始化函數(shù)，構(gòu)造空閑分區(qū)數(shù)組*參數(shù)： 無*返回值：無*函數(shù)實(shí)現(xiàn)：/*void ChuShiHuaNC()memory_locate = 0; /累計(jì)內(nèi)存使用量置0 query_count_all = 0;/累計(jì)比較次數(shù)置0 memory_apply_count = 0; /累計(jì)申請分配次數(shù)置0 memory_empty_count = 1;/空閑分區(qū)的內(nèi)存塊數(shù)置0block* block_start = (block*)malloc(sizeof(block);block_start-size = memory_size;block_start-addr = 0;/空閑分區(qū)的首址置0block_start-status = full;arry_empty_block0 = block_start;/*5首次適應(yīng)算法函數(shù)/*函數(shù)名：FirstFit*功能： 首次適應(yīng)算法*參數(shù)： int size 分配內(nèi)存空間的大小*返回值：int 申請的內(nèi)存空間的起始地址*函數(shù)流程圖：函數(shù)實(shí)現(xiàn)：*int FirstFit(int size)int returnResult;int flag = 0;int location_temp;for (int i=0;isize;if (size ceshi)i+;else if(size =arry_empty_blocki-size)location_temp = i;flag =1 ;break;else if(size addr;arry_apply_blockmemory_apply_count = arry_empty_blocklocation_temp;memory_apply_count+;/在空內(nèi)存數(shù)組中去掉該內(nèi)存塊if (location_temp = memory_empty_count - 1)memory_empty_count-;elsefor (int j = location_temp; j size = size;block_temp-addr = arry_empty_blocklocation_temp-addr;block_temp-status = empty;returnResult = arry_empty_blocklocation_temp-addr;/空內(nèi)存塊的修改，將大的塊改成小的空塊和申請塊arry_empty_blocklocation_temp-size = arry_empty_blocklocation_temp-size - size;/修改sizearry_empty_blocklocation_temp-addr = arry_empty_blocklocation_temp-addr + size;/修改addrarry_empty_blocklocation_temp-status = empty;/置空內(nèi)存塊狀態(tài)/申請塊加入到申請數(shù)組arry_apply_blockmemory_apply_count = block_temp;memory_apply_count+;else if(flag=0)使用冒泡排序使得按地址增加的順序排列/申請空間小于申請塊的大小returnResult = -1; /冒泡排序，按地址排序/排序，從a0開始排，從小到大 for (int i = 0; i memory_empty_count; i+)for (int j = i + 1; j addr arry_empty_blockj-addr)block * temp1;temp1= arry_empty_blocki;arry_empty_blocki = arry_empty_blockj;arry_empty_blockj = temp1;return returnResult;*6：最佳適應(yīng)算法函數(shù)/*功能： 最佳適應(yīng)算法*參數(shù)： int size 分配內(nèi)存空間的大小*返回值：int 申請的內(nèi)存空間的起始地址*函數(shù)流程圖：函數(shù)實(shí)現(xiàn)*int BestFit(int size)使用冒泡排序使得按內(nèi)存增加的順序排列int returnResult;int flag = 0;int location_temp;/首先對空內(nèi)存塊的值按塊內(nèi)存大小進(jìn)行排序，有小到大排序/冒泡排序for (int i = 0; i memory_empty_count; i+)for (int j = i + 1; j addr arry_empty_blockj-addr)block * temp1;temp1= arry_empty_blocki;arry_empty_blocki = arry_empty_blockj;arry_empty_blockj = temp1;for (int i = 0; isize;if (size ceshi)i+;else if (size = arry_empty_blocki-size)location_temp = i;flag = 1;break;else if (size addr;arry_apply_blockmemory_apply_count = arry_empty_blocklocation_temp;memory_apply_count+;/在空內(nèi)存數(shù)組中去掉該內(nèi)存塊if (location_temp = memory_empty_count - 1)memory_empty_count-;elsefor (int j = location_temp; j size = size;block_temp-addr = arry_empty_blocklocation_temp-addr;block_temp-status = empty;returnResult = arry_empty_blocklocation_temp-addr;/空內(nèi)存塊的修改，將大的塊改成小的空塊和申請塊arry_empty_blocklocation_temp-size = arry_empty_blocklocation_temp-size - size;/修改sizearry_empty_blocklocation_temp-addr = arry_empty_blocklocation_temp-addr + size;/修改addrarry_empty_blocklocation_temp-status = empty;/置空內(nèi)存塊狀態(tài)/申請塊加入到申請數(shù)組arry_apply_blockmemory_apply_count = block_temp;memory_apply_count+;else if (flag = 0)/申請空間小于申請塊的大小returnResult = -1;return returnResult;*7：最壞適應(yīng)算法函數(shù)/*功能： 最壞適應(yīng)算法*參數(shù)： int size 分配內(nèi)存空間的大小*返回值：int 申請的內(nèi)存空間的起始地址*函數(shù)流程圖函數(shù)實(shí)現(xiàn)：*int WorstFit(int size)int returnResult;int flag = 0;int location_temp;/首先對空內(nèi)存塊的值按塊內(nèi)存大小進(jìn)行排序,有大到小排序/冒泡排序使用冒泡排序使得按內(nèi)存減小的順序排列for (int i = 0; i memory_empty_count; i+)for (int j = i + 1; j addr arry_empty_blockj-addr)block * temp1;temp1= arry_empty_blocki;arry_empty_blocki = arry_empty_blockj;arry_empty_blockj = temp1;for (int i = 0; isize;if (size ceshi)i+;else if (size = arry_empty_blocki-size)location_temp = i;flag = 1;break;else if (size addr;arry_apply_blockmemory_apply_count = arry_empty_blocklocation_temp;memory_apply_count+;/在空內(nèi)存數(shù)組中去掉該內(nèi)存塊if (location_temp = memory_empty_count - 1)memory_empty_count-;elsefor (int j = location_temp; j size = size;block_temp-addr = arry_empty_blocklocation_temp-addr;block_temp-status = empty;returnResult = arry_empty_blocklocation_temp-addr;/空內(nèi)存塊的修改，將大的塊改成小的空塊和申請塊arry_empty_blocklocation_temp-size = arry_empty_blocklocation_temp-size - size;/修改sizearry_empty_blocklocation_temp-addr = arry_empty_blocklocation_temp-addr + size;/修改addrarry_empty_blocklocation_temp-status = empty;/置空內(nèi)存塊狀態(tài)arry_apply_blockmemory_apply_count = block_temp; /申請塊加入到申請數(shù)組memory_apply_count+;else if (flag = 0)/申請空間小于申請塊的大小returnResult = -1;return returnResult;*8：內(nèi)存回收函數(shù)/*函數(shù)名：HuiShouNC*功能： 內(nèi)存回收函數(shù)，用來回收分配出去的內(nèi)存，* 將其插入空閑分區(qū)數(shù)組中*參數(shù)： int type 使用的內(nèi)存分區(qū)分配算法的類型*返回值：block* 回收的分區(qū)對應(yīng)的節(jié)點(diǎn)信息*函數(shù)流程圖：函數(shù)實(shí)現(xiàn)：*block* HuiShouNC()int flag=1;/當(dāng)為情況2和3時flag為0，當(dāng)為情況1 時，flag為1；block * result;/隨機(jī)產(chǎn)生要回收的塊if (memory_apply_count 0)int n = Random(0, memory_apply_count-1);/首先在申請數(shù)組中找到該回收塊result = arry_apply_blockn;if (n = memory_apply_count - 1)memory_apply_count-;elsefor (int temp = n; temp addr;int size = arry_apply_blockn-size;for (int i = 0; i addr + arry_empty_blocki-size )= addr)flag = 0;if (i addr)/情況3,上下合并arry_empty_blocki-size = arry_empty_blocki-size + size + arry_empty_blocki + 1-size;result = arry_empty_blocki;/刪除i+1位置的空閑分區(qū)塊int tempi = i + 1;for (; tempi size = arry_empty_blocki-size + size;result = arry_empty_blocki;break;else if (i = memory_empty_count - 1)/如果為空分區(qū)的最后一個（特殊情況）arry_empty_blocki-size = arry_empty_blocki-size + size;result = arry_empty_blocki;break;else if (addr + size = arry_empty_blocki-addr)flag = 0;/情況2的下合并arry_empty_blocki-addr = addr;arry_empty_blocki-size = arry_empty_blocki-size + size;result = arry_empty_blocki;break;if (flag = 1)/情況1block* block_temp1 = (block*)malloc(sizeof(block);arry_empty_blockmemory_empty_count = block_temp1;arry_empty_blockmemory_empty_count-addr = addr;arry_empty_blockmemory_empty_count-size = size;arry_empty_blockmemory_empty_count-status = full;memory_empty_count+;result = arry_apply_blockn;return result;elsereturn NULL;*9：主函數(shù)/*函數(shù)名：Main*功能： 程序的入口和測試函數(shù)*參數(shù)： 無*返回值：無*函數(shù)流程圖：函數(shù)實(shí)現(xiàn)*int main()printf(選擇申請分配內(nèi)存方法n);printf(-n);printf(| 0 : |t 結(jié)束該程序運(yùn)行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);int rand_size; int rand_style;int circle = 1000;int apply_count=0;/申請內(nèi)存分配次數(shù)double rate1 = 0;/利用率block *p;srand(unsigned)time(NULL);/生成隨機(jī)數(shù)while (style!=0)ChuShiHuaNC();circle = 1000;rate1 = 0;while (circle 0)rand_style = Random(1, 20);if (rand_style17)rand_size = radomNumber(500,1000);/生成符合正態(tài)分布數(shù)/printf(%dn, rand_size);apply_count+;switch (style)case 1: FirstFit(rand_size);/最先適應(yīng)算法break;case 2:BestFit(rand_size);/最佳適應(yīng)算法case 3:WorstFit(rand_size);/最壞適應(yīng)算法break;default:break;elsep = HuiShouNC();/回收內(nèi)存rate1 = rate1 + rate();/計(jì)算內(nèi)存利用率之和circle-;rate1 = rate1 / 1000; /計(jì)算平均內(nèi)存利用率printf(-n);printf(查詢總次數(shù)n);printf(%dn, query_count_all);printf(申請內(nèi)存分配的次數(shù)n);printf(%dn, apply_count);printf(平均每次查詢的次數(shù)為%lfn, double(double)query_count_all / (double)apply_count);printf(平均空間利用率%lf%n, rate1 * 100);scanf(%d, &style); r