动态内存分配算法实验报告

1、动态内存分配算法实验报告 院系:计算机与通信工程学院 班级:计科08-1班 姓名:胡太祥 学号:2一实验题目：动态内存分配算法二、实验目的深入了解动态分区存储管理方式内存分配与回收的实现三、实验要求熟悉存储管理中动态分区的管理方式及Windows环境下，VC+程序设计方法四、实验内容1，确定定内存空闲分配表和进程内存分配表2，采用首次适应算法完成内存空间的分配3，采用最佳适应算法完成内存空间的分配4，采用最坏适应算法完成内存空间的分配5，实现内存回收功能五、实验结果首次适应算法结果最佳适应算法最坏适应算法六、实验总结首次适应算法：从表头指针开始查找课利用空间表，将找到的第一个大小不小于“请求”

2、的空闲块的一部分分配给用户。最佳适应算法：将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。最坏适应算法：将可利用空间表中一个大小不小于“请求”且是链表中最大的空闲块的一部分分配给用户。 以上是动态内存分配的三种算法思想，算法采用数据结构中的双向链表实现。附录（算法代码）：#include#include#define Free 0 /空闲状态#define Used 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 32767 /最大内存空间为32767KBtypedef int Stat

3、us; /typedef将标识符Status定义成一个数据型标识符int n = 0;typedef struct freearea /定义一个结构体freearea,并对这个空闲分区进行说明 int ID; /分区号 long size; /分区大小 long address; /分区地址 int state; /当前状态 ElemType;typedef struct DuLNode /double linked list / 线性表的双向链表存储结构 ElemType data; struct DuLNode *prior; /前趋指针 struct DuLNode *next; /后继

4、指针 DuLNode, *DuLinkList;DuLinkList free_list; /空闲链表DuLinkList alloc_list; /已分配链表Status alloc(int);/内存分配void free_memory(int ID, int method); /内存回收Status first_fit(int ID, int size); /首次适应算法Status best_fit(int ID, int size); /最佳适应算法Status worst_fit(int ID, int size); /最坏适应算法void first_fit_insert(DuLN

5、ode *insert); /首次适应插入排序void best_fit_insert(DuLNode *insert); /最佳适应插入排序void worst_fit_insert(DuLNode *insert); /最坏适应插入排序DuLNode *independent_node(DuLNode *node); /断开节点node与相邻节点的联系，使其孤立/将节点node分割，返回分配的节点信息，node为剩余内存信息/node为双指针形式，因为可能需要对node的值进行修改DuLNode *slice_node(DuLNode *node, int ID, int size); v

6、oid show();/查看分配Status Initblock();/开创空间表Status Initblock()/开创带头节点的内存空间链表，头节点不用 alloc_list = (DuLinkList)malloc(sizeof(DuLNode); free_list = (DuLinkList)malloc(sizeof(DuLNode); /头节点不用 alloc_list-prior = alloc_list-next = NULL; free_list-prior = free_list-next = NULL; /空闲列表初始为整个内存大小，放到node节点中 DuLNode

7、 *node = (DuLNode*)malloc(sizeof(DuLNode); node-data.address = 0; node-data.size = MAX_length; node-data.ID = 0; node-data.state = Free; /将node节点放到空闲链表中 node-prior = free_list; node-next = NULL; free_list-next = node; return OK;/将所插入节点按首址从小到大顺序插入到空闲链表中void first_fit_insert(DuLNode *insert) /首次适应插入排序

8、 DuLNode *p = free_list-next; /空闲链表为空，则将节点放到头节点后 if (p = NULL) free_list-next = insert; insert-prior = free_list; return; /按首址从小到大的顺序插入节点 while (p) /找到插入位置: p之前 if (insert-data.address data.address) insert-next = p; insert-prior = p-prior; p-prior-next = insert; p-prior = insert; break; /插入位置为链表尾 if

9、 (p-next = NULL) p-next = insert; insert-prior = p; break; /还是提前退出循环的好，不然会再次进入循环 p = p-next; /搜索下一个节点 /最佳适应插入排序：/将所插入节点按空间从小到大插入链表void best_fit_insert(DuLNode *insert) DuLNode *p = free_list-next; /空闲链表为空，则插入到头节点后 if (p = NULL) free_list-next = insert; insert-prior = free_list; return; /按空间从小到大插入节点

10、while (p) /在p前插入 if (insert-data.size data.size) insert-next = p; insert-prior = p-prior; p-prior-next = insert; p-prior = insert; break; /插入位置为链表尾 if (p-next = NULL) p-next = insert; insert-prior = p; break; /还是提前退出循环的好，不然会再次进入循环 p = p-next; /搜索下一个节点 /最坏适应插入排序：/将所插入节点按空间从大到小插入链表void worst_fit_inser

11、t(DuLNode *insert) DuLNode *p = free_list-next; /链表为空，则插入到头节点后 if (p = NULL) free_list-next = insert; insert-prior = free_list; return; /按空间从大到小插入节点 while (p) /在p前插入节点 if (insert-data.size = p-data.size) insert-next = p; insert-prior = p-prior; p-prior-next = insert; p-prior = insert; break; /插入位置为链

12、表尾 if (p-next = NULL) p-next = insert; insert-prior = p; break; /还是提前退出循环的好，不然会再次进入循环 p = p-next; /搜索下一个节点 /断开节点node与相邻节点间的联系，使其孤立/返回 孤立后的节点指针DuLNode *independent_node(DuLNode *node) if (node != NULL) if (node-prior != NULL) node-prior-next = node-next; if (node-next != NULL) node-next-prior = node-

13、prior; node-prior = node-next = NULL; return node;/将节点node分片，其中一片allocnode为为用户所分配的内存片，/另一片为分配后原node节点所剩余的内存片，放到node中/若node节点原来大小等于所要开辟的大小，则node赋值为NULL/返回分配结果DuLNode *slice_node(DuLNode *node, int ID, int size) DuLNode *allocnode = NULL; /node的大小正好等于所要分配的大小， /则直接将该节点放到分配链表中，node赋值为NULL if (*node)-dat

14、a.size = size) /将node从空闲链表中分出来 independent_node(*node); /得到所分配的内存片 allocnode = (*node); allocnode-data.ID = ID; allocnode-data.state = Used; /没有剩余空间,这个地方导致必须用双重指针 (*node) = NULL; else if (*node)-data.size size) /node的大小大于所需的大小，故将node分为两片 /一片为所分配的内存片，分配地址和空间 allocnode = (DuLNode*)malloc(sizeof(DuLNod

15、e); allocnode-data.size = size; allocnode-data.address = (*node)-data.address; allocnode-data.ID = ID; allocnode-data.state = Used; allocnode-prior = allocnode-next = NULL; /另一片为分配后剩下的内存片，修改内存地址和大小 (*node)-data.address += size; (*node)-data.size -= size; /返回分配结果 return allocnode;/按不同的分配方法归还内存void fr

16、ee_memory(int ID, int method) /内存回收 DuLNode *p, *prior, *next, *freenode; p = prior = next = freenode = NULL; /从已分配链表中找到所要归还的内存信息 p = alloc_list-next; while (p) if (p-data.ID = ID) /找到所要归还的内存信息 freenode = p; freenode-data.state = Free; freenode-data.ID = Free; break; p = p-next; /继续查找 /将freenode从已分配

17、链表中分离出来 independent_node(freenode); if (freenode = NULL) /没有所要归还的内存 return; /合并空闲内存片 p = free_list-next; while (p) /找到先前合并内存节点prior if (p-data.address + p-data.size = freenode-data.address) prior = p; else if (freenode-data.address + freenode-data.size = p-data.address) /找到向后合并内存节点next next = p;/在这儿

18、，如果是 首次适应算法 可以直接中断循环了 p = p-next; /继续查找 /向前合并节点存在，则进行合并 if (prior != NULL) independent_node(prior); /将prior从空闲链表中分离出来 /freenode与prior合并 freenode-data.address = prior-data.address; freenode-data.size += prior-data.size; /释放prior节点 free(prior); /向后合并节点存在，则进行合并 if (next != NULL) independent_node(next);

19、 /将next从空闲链表中分离出来 /freenode与next合并 freenode-data.size += next-data.size; /释放next节点 free(next); /按不同的分配方式，重新插入合并后的节点 if (method = 1) first_fit_insert(freenode); else if (method = 2) best_fit_insert(freenode); else if (method = 3) worst_fit_insert(freenode); Status alloc(int ch) / 分 配 主 存 int ID, requ

20、est; cout ID; cout request; if (request 0 | request = 0) cout 分配数据不合适，请重新输入! endl; return ERROR; if (ch = 1) /首次适应算法 if (first_fit(ID, request) = OK) cout 分配成功! endl; else cout 内存不足，分配失败! endl; return OK; else if (ch = 2) /选择最佳适应算法 if (best_fit(ID, request) = OK) cout 分配成功! endl; else cout 内存不足，分配失败

21、! endl; return OK; else if (ch = 3) /最坏适应算法 if (worst_fit(ID, request) = OK) cout 分配成功! endl; else cout 内存不足，分配失败! next; DuLNode *allocnode = NULL; while (p) /找到合适空闲内存节点 if (p-data.size = size) break; p = p-next; if (p = NULL) /内存空间不足 return ERROR; /将p分片，返回所要分配的内存信息 /由于是按首址从小到大排列空闲内存节点 /故不需再重排剩余内存节点

22、 allocnode = slice_node(&p, ID, size); DuLNode *q = alloc_list-next; /将所分配节点放到已分配链表头节点后 if (q != NULL) allocnode-next = q; allocnode-prior = q-prior; q-prior-next = allocnode; q-prior = allocnode; else alloc_list-next = allocnode; allocnode-prior = alloc_list; return OK;Status best_fit(int ID, int s

23、ize) / 最佳适应算法 DuLNode *p = free_list-next; DuLNode *allocnode = NULL, *leftnode = NULL; while (p) /找到了合适的内存节点 if (p-data.size = size) break; p = p-next; if (p = NULL) /内存不足 return ERROR; /分片，剩余内存片需重新排序 allocnode = slice_node(&p, ID, size); leftnode = p; DuLNode *q = alloc_list-next; /将所分配节点放到已分配链表头节

24、点后 if (q != NULL) allocnode-next = q; allocnode-prior = alloc_list; q-prior-next = allocnode; q-prior = allocnode; else alloc_list-next = allocnode; allocnode-prior = alloc_list; /重新插入剩余内存片 if (leftnode != NULL) /分离剩余内存片 independent_node(leftnode); /插入该片 best_fit_insert(leftnode); return OK;Status w

25、orst_fit(int ID, int size) /最坏适应算法,直接找第一个节点 DuLNode *p = free_list-next; DuLNode *allocnode = NULL, *leftnode = NULL; if (p = NULL | p-data.size next; /将所分配节点放到已分配链表头节点后 if (q != NULL) allocnode-next = q; allocnode-prior = alloc_list; q-prior-next = allocnode; q-prior = allocnode; else alloc_list-next = allocnode; allocnode-prior = alloc_list; /重新插入剩余内存片 if (leftnode != NULL) /分离剩余内存片 independent_node(leftnode); /插入该片 worst_fit_insert(leftnode); return OK;void show()/ 显示主存分配情况 cout next; cout n 空闲分区 nn; while (p) cout 分 区 号：Fre