动态内存分配算法试验报告材料

1、实用标准文案精彩文档动 态 内 存 分 配算 法 实 验 报 告院系:计算机与通信工程学院班级:计科 08-1 班姓名:胡太祥实用标准文案精彩文档学号:200807010112一、实验题目：动态内存分配算法二、实验目的深入了解动态分区存储管理方式内存分配与回收的实现三、实验要求熟悉存储管理中动态分区的管理方式及Win dowsVC+程序设计方法四、实验内容1，确定定内存空闲分配表和进程内存分配表2，采用首次适应算法完成内存空间的分配3，采用最佳适应算法完成内存空间的分配4，采用最坏适应算法完成内存空间的分配5，实现内存回收功能五、实验结果环境下,实用标准文案精彩文档XJ-1010你有以下尊法可

2、供选择:fess应应应适适适次專田直日B B駆退收回回返K K!台-.KETT收回i i妝彎配看:籌功分查择入入成:选需配1313请请请命!e=洋AJ盘大.存区时XJfiB BK K *位1 1业要T T配看隼丙功分查择入入成；选鞘配请请请分收回回返 B BK4位SISI3士业要T T配看星而功分查择入入成=选3 3请请请分ZJ(T1 1业要配看;需功分查择入人应-请请请分i i业要配看證持功分查：择入入成:-择选藉配1313选注弔注nnnn请介注nnnn乳己1 1 3 3实用标准文案精彩文档Free92&67 KB首次适应算法结果、：30 KB慵选择J丄，議黔碍知 9413圭.并配3

3、=査看返回1：分配J-壬舀2：回收也返向1:分配3：查看3IS区分的X+益尸2更配S您分查择：il 3收回回返騒区大小；26 KB；Free I&KB2：回收0=KB一二11?4S实用标准文案精彩文档主存分配情况空闲分区B BK K2 21 1 8 8口小Z地大区始区LiJ2-kJFree 5010 KB分区号：Free胆始地址：10B分区大小；32667 KB已分配分区B B* Jr口小z地分区牛2趙始地血=20分反大水=30KB最佳适应算法收回回返配看分查1 1 3 3IBIB 位IIIT /Z业要L.1疔区大小:实用标准文案精彩文档主存分配情况 空闲分区分区号r Free起始地;

4、tL 50分区大小：10 MB:Free起始地址：8分区大水：12 KBFree1003266? KB已分配分区最坏适应算法2：回收0：返向KB14小Z地大分起分l(n0 04-6 4口一小区地大E始01小Z地大区地大区始区分停实用标准文案精彩文档王苻分配情况空闲分区分区号匕Free总始地L 100曲区大小：32fc67 KB分区号=Free起始地51分区大9 KB已分配分区iwl：20分図大小：30 KS六、实验总结首次适应算法：从表头指针开始查找课利用空间表， 将找到的第一个 大小不小于“请求”的空闲块的一部分分配给用户。最佳适应算法：将可利用空间表中一个大小不小于“请求”且最接近“请求”

5、的空闲块的一部分分配给用户。最坏适应算法：将可利用空间表中一个大小不小于“请求”且是链表 中最大的空闲块的一部分分配给用户。以上是动态内存分配的三种算法思想，算法采用数据结构中的双 向链表实现。e ee er rF F匸I一Z地大一区始区分-_E nK小区始区分起分-1.BK075 1I_*r区地大E始区0 0实用标准文案精彩文档附录（算法代码）：实用标准文案精彩文档#i nclude#i nclude#defi ne Free 0 / 空闲状态#defi ne Used 1 /已用状态#define OK 1/ 完成#defi ne ERROR 0 / 出错#defi ne MAX_le n

6、gth 32767 /最大内存空间为 32767KBtypedef int Status; /typedef 将标识符 Status 定义成一个数据型标识符int n = 0;typedef struct freearea / 定义一个结构体 freearea,并对这个空闲分区进行说明int ID;/分区号long size;/分区大小long address; / 分区地址int state; /当前状态 ElemType;typedefstructDuLNode /doublelinked list / 线性表的双向链表存储结构ElemType data;struct DuLNode *p

7、rior; / 前趋指针struct DuLNode*next; / 后继指针 DuLNode, *DuL in kList;DuLinkList free_list;/ 空闲链表DuLi nkList alloc_list; / 已分配链表Status alloc(i nt);/内存分配void free_memory(i nt ID, int method); /内存回收Status first_fit(i nt ID, i nt size); / 首 次适应算法Status best_fit(i nt ID, i nt size); /最佳适应算法实用标准文案精彩文档Status wor

8、st_fit(intID, int size); /最坏适应算法实用标准文案精彩文档voidfirst_fit_i nsert(DuLNode*insert); /首次适应插入排序voidbest_fit_i nsert(DuLNode*insert);/最佳适应插入排序voidworst_fit_i nsert(DuLNode*insert); /最坏适应插入排序DuLNode*in depe ndent_no de(DuLNode*node); / 断开节点 node 与相邻节点的联系，使其孤立/将节点 node 分割，返回分配的节点 信息，node 为剩余内存信息/node 为双指针形式

9、，因为可能需要 对node 的值进行修改DuLNode *slice_node(DuLNode*no de, int ID, int size);void show(); 查看分配Status In itblock(); 开创空间表Status Initblock()/开创带头节点的内存空间链表，头节点不用alloc_list(DuL in kList)malloc(sizeof(DuLNode);free_list(DuL in kList)malloc(sizeof(DuLNode);/头节点不用alloc_list-prioralloc_list- next = NULL; free_l

10、ist-priorfree_list- next = NULL;/空闲列表初始为整个内存大小，放至 U node 节点中DuLNode*n ode(DuLNode*)malloc(sizeof(DuLNod e);no de-data.address = 0;no de-data.sizeMAX_le ngth;实用标准文案in sert-prior = free_list;in sert-prior = p;精彩文档no de-data .ID = 0;no de-data.state = Free;/将 node 节点放到空闲链表中no de-prior = free_list;no de

11、-n ext = NULL;free_list- n ext = no de;return OK;/将所插入节点按首址从小到大顺序插入到空闲链表中voidfirst_fit_i nsert(DuLNode*insert) /首次适应插入排序DuLNode *p = free_list- next;/按首址从小到大的顺序插入节占八、while (p) /找到插入位置：p 之前if(in sert-data.addressdata.address) in sert- n ext = p;in sert-priorp-prior;p-prior- n extin sert;p-prior = in

12、sert;break;/空闲链表为空，则将节点放到头节点后if (p = NULL) free_list- n ext = in sert;插入位置为链表尾if (p-n ext = NULL) return;break; /还是提前退实用标准文案精彩文档p-n ext = in sert;出循环的好，不然会再次进入循环p = p-n ext; /搜索下一个节点/最佳适应插入排序：/将所插入节点按空间从小到大插入链表voidbest_fit_i nsert(DuLNode*in sert)DuLNode *p = free_list- next;/按空间从小到大插入节点while (p) /在

13、 p 前插入if(in sert-data.sizedata.size) in sert- n ext = p;in sert-prior=p-prior;p-prior- n ext=in sert;p-prior = in sert;break;/空闲链表为空，则插入到头节点后if (p = NULL) free_list- n ext = in sert;in sert-prior = free_list;return;插入位置为链表尾if (p-n ext = NULL) p-n ext = in sert;in sert-prior = p;break; /还是提前退出循环的好，不然

14、会再次进入循环实用标准文案精彩文档p = p-n ext; / 搜索下一个节点/最坏适应插入排序：/将所插入节点按空间从大到小插入 链表voidworst_fit_i nsert(DuLNode*in sert)DuLNode *p = free_list- next;/链表为空，则插入到头节点后if (p = NULL) free_list- n ext = in sert; insert-prior = free_list; return;/按空间从大到小插入节点while (p) /在 p 前插入节点if(in sert-data.size=p-data.size) in sert- n

15、 ext = p;in sert-prior=p-prior;p-prior- n ext=in sert;p-prior = in sert;break;插入位置为链表尾if (p-n ext = NULL) p-n ext = in sert;in sert-prior = p;break; /还是提前退出循环的好，不然会再次进入循环p = p- next; /搜索下一个节点实用标准文案if (* no de)-data.size = size)精彩文档/断开节点 node 与相邻节点间的联 系，使其孤立/返回孤立后的节点指针DuLNode*in depe ndent_no de(DuLN

16、ode*no de)if (node != NULL) if (node-prior != NULL) no de-prior- n extno de-n ext;if (node-next != NULL) no de-n ext-priorno de-prior;no de-priorno de-next = NULL;return no de;/将节点 n ode 分片， 其中一片 alloc node为为用户所分配的内存片，/另一片为分配后原 node 节点所剩余的内存片，放到 node 中/若 node 节点原来大小等于所要开辟的大小，贝 U node 赋值为 NULL/返回分配结果

17、DuLNode *slice_node(DuLNode*no de, int ID, int size)DuLNode *allocnode = NULL;/node 的大小正好等于所要分配的大小，/则直接将该节点放到分配链表中，node 赋值为 NULL实用标准文案alloc no de-data.size=method) / 内存回收精彩文档/将node从空闲链表中分 出来in depe ndent_no de(* no de);/得到所分配的内存片alloc node = (*no de);alloc no de-data .ID = ID;alloc no de-data.state=

18、Used;/没有剩余空间，这个地方导致必须用双重指针(*n ode) = NULL; else if (* no de)-data.size size)/node的大小大于所需的大小，故将 node 分为两片/ 一片为所分配的内存片，分配地址和空间alloc node=(DuLNode*)malloc(sizeof(DuLNode);alloc no de-data.address=(*no de)-data.address;alloc no de-data .ID = ID;alloc no de-data.state=Used;alloc no de-prior=alloc no de-n

19、 ext = NULL;/另一片为分配后剩下的内 存片，修改内存地址和大小(*no de)-data.address+= size;(*no de)-data.size-=size;/返回分配结果retur n alloc no de;/按不同的分配方法归还内存void free_memory(i nt ID, int实用标准文案alloc no de-data.size=method) / 内存回收精彩文档size;实用标准文案free no de-data.size精彩文档DuLNode *p, *prior,*n ext,*free no de;p = prior = n ext = f

20、ree node =NULL;/从已分配链表中找到所要归还 的内存信息p = alloc_list- n ext;while (p) if (p-dataD = ID) /找到所要归还的内存信息free node = p;free no de-data.state=Free;free no de-data .ID=Free;break;p = p-n ext; / 继续查找/将 free node 从已分配链表中分离出来in depe ndent_no de(free no de);if (freen ode = NULL) / 没有所要归还的内存return;/合并空闲内存片p = free

21、_list- n ext;while (p) /找到先前合并内存节点priorif (p-data.address +p-data.size=freeno de-data.address) prior = p;elseif实用标准文案精彩文档(free no de-data.address+实用标准文案精彩文档p-data.address) /找到向后合并内存节点 nextn ext = p;/在这儿，如果是首次适 应算法 可以直接中断循环了p = p-n ext; /继续查找/向前合并节点存在，则进行合并if (prior != NULL) in depe ndent_no de(prior

22、);/将 prior 从空闲链表中分离出来/freenode与 prior 合并free no de-data.address=prior-data.address;free no de-data.size+=prior-data.size;/释放 prior 节点/向后合并节点存在，则进行合并if (next != NULL) in depe ndent_no de( next);/将 next 从空闲链表中分离出来/freenode 与 next 合并free no de-data.size+=n ext-data.size;/释放 next 节点free( next);/按不同的分配方式

23、， 重新插入合 并后的节点if (method = 1) first_fit_i nsert(free no de); else if (method = 2) best_fit_i nsert(free no de);实用标准文案精彩文档 else if (method = 3) Status alloc(int ch) 分配主存int ID, request;cout ID;cout request;if (request 0 | request = 0)cout 分配数据不合适，请重新输入! endl;return ERROR;if (ch = 1) / 首次适应算法if (first_

24、fit(ID, request)=OK) cout 分配成功! en dl; else cout 内存不足，分配失败! endl;return OK; else if (ch = 2) / 选择最佳适应算法if (best_fit(ID, request)=OK) cout 分配成功! en dl; else cout 内存不足，分free(prior);worst_fit_in sert(free no de);实用标准文案精彩文档配失败! next;DuLNode *allocnode = NULL;/将 p 分片，返回所要分配的内 存信息/由于是按首址从小到大排列空 闲内存节点/故不需再

25、重排剩余内存节点alloc node = slice_ no de(&p, ID,size);DuLNode*q= else if (ch = 3) /最坏适应while (p) 算法/找到合适空闲内存节点if (worst_fit(ID,request)if (p-data.size = size) =OK) break;cout 分配成功!n ext;cout 内存不足，分配失败! n ext;/将所分配节点放到已分配链表 头节点后if (q != NULL) alloc no de-n ext = q;alloc no de-prior=q-prior;q-prior- n ex

26、t=alloc no de;q-prior = alloc no de; else alloc_list- n ext=alloc no de;alloc no de-prior=alloc_list;return OK;Status best_fit(i nt ID, i nt size) /最佳适应算法DuLNode *p = free_list- n ext;DuLNode *allocnode = NULL, *leftnode = NULL;while (p) /找到了合适的内存节点if (p-data.size = size) break;p = p-n ext;if (p = N

27、ULL) /内存不足return ERROR;/分片，剩余内存片需重新排序alloc node = slice_ no de(&p, ID,实用标准文案精彩文档size);left node = p;DuLNode*qalloc_list- n ext;/将所分配节点放到已分配链表 头节点后if (q != NULL) alloc no de-n ext = q;alloc no de-prioralloc_list;q-prior- n extalloc no de;q-prior = alloc no de; else alloc_list- n extalloc no de;al

28、loc no de-prioralloc_list;/重新插入剩余内存片if (left node != NULL) /分离剩余内存片in depe ndent_no de(left no de);插入该片best_fit_i nsert(left no de);return OK;Status worst_fit(i nt ID, int size) / 最坏适应算法，直接找第一个节点DuLNode *p = free_list- n ext;DuLNode *allocnode = NULL, *leftnode = NULL;if (p = NULL | p-data.size n ext;/将所分配节点放到已分配链表 头节点后if (q != NULL) alloc no de-n ext = q;alloc no de-prioralloc_list;q-prior- n extalloc no de;q-prior = alloc no de; else alloc_list- n extalloc no de;alloc_list;/重新插入剩余内存片if (left node != NULL) /分离剩余内存片in depe ndent_no de(left no de);插入该片worst