模拟内存管理设计与实现.docx

内存管理器1. 实验目的设计和实现关于内存管理的内存布局初始化及内存申请分配、内存回收等基本功能操作函数，尝试对用256MB的内存空间进行动态分区方式模拟管理。内存分配的基本单位为1KB，同时要求支持至少两种分配策略，并进行测试和对不同分配策略的性能展开比较评估。2. 实验设计2.1 实验要求l 1、设计一定的数据结构以描述256MB内存空间的使用状况，并设计和构建函数void ChuShuHuaNC (DIZHI zKS_KYNC, DIZHI zJS_KYNC)实现内存布局的初始化。假定内存空间的低址部分56MB（即056M-1）作为系统区和不参与分配过程。l 2、设计和实现内存申请分配函数DIZHI ShenQingNC(unsigned long zDX)，内存分配的基本单位为1KB，同时要求支持至少两种分配策略（如首次适应、循环首次适应、最佳适应、最坏适应等），若分配失败则返回NULL。l 3、设计和实现内存回收函数void HuiShouNC(DIZHI zKSDZ) ，若回收分区与其它空闲分区相邻接，则采取合并措施。l 4、基于不同的内存分配策略形成不同版本的内存管理器，并根据内存平均利用率（指已分配内存占总可分配内存的平均比率）和分配查找分区比较次数等指标展开测试和对不同分配策略的内存管理器性能进行评估。l 5、不妨设计测试例程框架：循环 产生随机数，并根据该值确定是申请内存还是回收内存； 若是申请内存，还需进一步产生申请内存大小（服从正态/均匀分布）；若是回收内存还需产生随机数和选择回收区； 收集测试数据用于性能评价；2.2. 数据结构/*内存空闲分区结构块*/typedef struct nodeint addr; /空闲分区的首址int size; /空闲分区的大小int status; /空闲分区的状态blockblock* arry_empty_block2048;block* arry_apply_block2048;空内存块结构体数组已申请内存块结构体数组2.3. 性能指标计算指标1：countcount为平均每次申请分配内存时查找符合内存大小的次数。计算公式：count=query_apply_countapply_countquery_apply_count:总的查询比较次数apply_count:总的申请分配内存次数指标2：raterate为每1000次对存储设备操作后的平均内存利用率。计算公式： rate=all_rateall_countall_rate:总的对内存每次操作后的内存利用率之和all_conut:对内存的操作次数包括回收和分配3. 程序清单1：变量解释/*full:空闲分区的状态为满*empty：空闲分区的状态为空*mix:允许产生的最大申请块*min:允许申请的最小申请块*memory_size：初始内存大小（256M-56M）*memory_locate：累计内存使用量*query_count_all：累计比较次数*memory_empty_count:空闲分区的内存块数*memory_apply_count：申请成功的内存块数2：空间利用率函数*函数名：rate*功能： 求空间利用率*返回值 double*参数： 无*函数实现*double rate() int sizeloction=0; for (int i = 0; i size+ sizeloction; 求总的分配空间 return double(double(sizeloction) / 204800);*3：正态分布随机函数*函数名称：radomNumber*功能：产生服从正态分布的一组随机数*函数参数：int average（平均数）, int variance（方差）*返回值：int *函数实现：*/ 根据均值和方差算正态分布随机数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：内存空间初始化函数/*函数名：ChuShiHuaNC*功能： 内存空间初始化函数，构造空闲分区数组*参数： 无*返回值：无*函数实现：/*void ChuShiHuaNC()memory_locate = 0; /累计内存使用量置0 query_count_all = 0;/累计比较次数置0 memory_apply_count = 0; /累计申请分配次数置0 memory_empty_count = 1;/空闲分区的内存块数置0block* block_start = (block*)malloc(sizeof(block);block_start-size = memory_size;block_start-addr = 0;/空闲分区的首址置0block_start-status = full;arry_empty_block0 = block_start;/*5首次适应算法函数/*函数名：FirstFit*功能： 首次适应算法*参数： int size 分配内存空间的大小*返回值：int 申请的内存空间的起始地址*函数流程图：函数实现：*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+;/在空内存数组中去掉该内存块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;/置空内存块状态/申请块加入到申请数组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：最佳适应算法函数/*功能： 最佳适应算法*参数： int size 分配内存空间的大小*返回值：int 申请的内存空间的起始地址*函数流程图：函数实现*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+;/在空内存数组中去掉该内存块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;/置空内存块状态/申请块加入到申请数组arry_apply_blockmemory_apply_count = block_temp;memory_apply_count+;else if (flag = 0)/申请空间小于申请块的大小returnResult = -1;return returnResult;*7：最坏适应算法函数/*功能： 最坏适应算法*参数： int size 分配内存空间的大小*返回值：int 申请的内存空间的起始地址*函数流程图函数实现：*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+;/在空内存数组中去掉该内存块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;/置空内存块状态arry_apply_blockmemory_apply_count = block_temp; /申请块加入到申请数组memory_apply_count+;else if (flag = 0)/申请空间小于申请块的大小returnResult = -1;return returnResult;*8：内存回收函数/*函数名：HuiShouNC*功能： 内存回收函数，用来回收分配出去的内存，* 将其插入空闲分区数组中*参数： int type 使用的内存分区分配算法的类型*返回值：block* 回收的分区对应的节点信息*函数流程图：函数实现：*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);/首先在申请数组中找到该回收块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位置的空闲分区块int tempi = i + 1;for (; tempi size = arry_empty_blocki-size + size;result = arry_empty_blocki;break;else if (i = memory_empty_count - 1)/如果为空分区的最后一个（特殊情况）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：主函数/*函数名：Main*功能： 程序的入口和测试函数*参数： 无*返回值：无*函数流程图：函数实现*int main()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);int rand_size; int rand_style;int circle = 1000;int apply_count=0;/申请内存分配次数double rate1 = 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_style17)rand_size = radomNumber(500,1000);/生成符合正态分布数/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(查询总次数n);printf(%dn, query_count_all);printf(申请内存分配的次数n);printf(%dn, apply_count);printf(平均每次查询的次数为%lfn, double(double)query_count_all / (double)apply_count);printf(平均空间利用率%lf%n, rate1 * 100);scanf(%d, &style); r