模擬內存管理設計與實現(xiàn).docx

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