|
模拟内存动态管理——学习篇（原创）
本文简单讲讲操作系统对动态内存的管理策略，纯属个人粗浅认识，如果有错，还望指出。
如果转载，还请注明文章出处，谢谢！！
动态内存，即我们通过malloc/alloc等接口向操作系统申请到的内存。那操作系统是 如何管理的呢？ 操作系统将空闲内存块以“链表”的方式维护起来。当我们调用malloc等接口向操作系统 申请内存时候，操作系统会在空闲内存链上查找是否有足够的可用内存。如果找到这样 的节点，则将此节点的内存块分成请求内存块和剩余内存块，将请求内存块返回给"malloc"， 而将剩余内存块添加到空闲内存链上。
问题：在空闲内存链上搜索可用的内存块，操作系统会使用怎样的策略呢？ 请参考 我转载的一篇讲述操作系统内存管理算法的文章，在这里，我只是就两个简单 的算法——best fit & first fit 进行初步的分析下。
First Fit : 在free list里面搜索，当找到的block比请求的大的话,就分割这个block将剩余 的插入到free list中.我们可以看到,这样的话会使得前面的block越来越小,从而导致每次 搜索都会越来越远（假设每次都是请求这样大小的内存块）。 Best Fit : 每次在free list里面搜索，找到不小于请求大小的，最接近请求大小的 内存块。它是从生成的内存碎片来看,最好的一种策略,因为它会产生最小的碎片. 可是由于它会每次遍历所有block,所以它的效率比较低。当然，也可对free list 按照free node 的大小进行排序，但这样的话，也是比较耗时的。
下面的程序简单模拟了操作系统管理内存的best fit和first fit算法。
1. Best Fit 示例程序
#if 1
/* This is a program to simulate malloc/free function If we use "best fit " strategy when we alloc memory , the efficiency will be low when we look for the most proper size of memory block and when we collect memory fragments (we need to traverse the memory free list 2 times ,because the address order of nodes in the list is not in order) , But the possiblity to encounter memory fragment collection will be lower . If we use "first fit " strategy when we alloc memory , the efficiency will be higher , while the usage of memory may be inefficient. Here is 1 program using "Best Fit " Strategy . */ #include <stdio.h> #include <stdlib.h> #define HEAP_SIZE 320 char heap_mem[HEAP_SIZE]; struct mem_ctrl_blk { int node_size; struct mem_ctrl_blk * next; }; struct mem_ctrl_blk * phead = NULL; // phead : stands for the head node of memory list struct mem_ctrl_blk * pfree_list = NULL; int mem_ctrl_blk_size = sizeof(struct mem_ctrl_blk); int mem_has_inited = 0; extern void print_free_list(); void mem_init() { phead = (struct mem_ctrl_blk *)heap_mem; phead->node_size = 0; pfree_list = phead + 1; pfree_list->node_size = HEAP_SIZE - mem_ctrl_blk_size; pfree_list->next = NULL; phead->next = pfree_list; mem_has_inited = 1; } void list_insert(struct mem_ctrl_blk *pnode) { struct mem_ctrl_blk *p = pfree_list; struct mem_ctrl_blk *plast = phead; while(p) { if(p->node_size > pnode->node_size) { if(p == pfree_list) { pfree_list = pnode; } pnode->next = p; plast->next = pnode; return; } plast = p; p = p->next; } plast->next = pnode;
pnode->next = NULL; // in fact ,now p == NULL } void mem_frag_collect() { struct mem_ctrl_blk *p = pfree_list; struct mem_ctrl_blk *plast = phead; struct mem_ctrl_blk *q; printf(" enter mem_frag_collect \n"); // if only 1 node , there is no memory fragment
printf(" pfree_list = %p , phead = %p \n", pfree_list,phead); while(p)
{ q = p->next; printf(" q = %p, p = %p \n",q,p); if(q) { printf(" q->node_size = %d , p->node_size = %d \n", q->node_size,p->node_size); } if ((char *)p + p->node_size == (char *)q) { printf(" p + p_size = q \n"); p->node_size += q->node_size; p->next = q->next; } else { p = p->next; } } printf(" exit mem_frag_collect \n"); } // we use select sort ; sort by node size void mem_node_sort_after_collect() { struct mem_ctrl_blk *p,*plast; struct mem_ctrl_blk *q,*qlast,*qlast_prev; struct mem_ctrl_blk *pmax_node,*pmax_prev; struct mem_ctrl_blk *plist_end = NULL; printf(" enter mem_node_sort_after_collect \n"); p = pfree_list; plast = phead; while(p->next != plist_end) { pmax_node = p; qlast = p; q = p->next; pmax_prev = plast; qlast_prev = plast; while(q != plist_end) { if(pmax_node->node_size < q->node_size) { pmax_node = q; pmax_prev = qlast; } qlast_prev = qlast; qlast = q; q = q->next; } // do node switch
// the max node is close to the last node in // current list if(qlast == pmax_node->next) { pmax_node->next = qlast->next; qlast->next = pmax_node; pmax_prev->next = qlast; } else { pmax_prev->next = qlast; qlast->next = pmax_node->next; qlast_prev->next = pmax_node; pmax_node->next = plist_end; plist_end = pmax_node; } if(p == pmax_node) { pfree_list = p = qlast; } } printf(" exit mem_node_sort_after_collect \n");
} void mem_node_sort_by_address() { struct mem_ctrl_blk *p,*plast; struct mem_ctrl_blk *q,*qlast,*qlast_prev; struct mem_ctrl_blk *pmax_node,*pmax_prev; struct mem_ctrl_blk *plist_end = NULL; printf(" enter mem_node_sort_by_address \n"); p = pfree_list; plast = phead; while(p->next != plist_end) { pmax_node = p; qlast = p; q = p->next; pmax_prev = plast; qlast_prev = plast; while(q != plist_end) { if(pmax_node < q) { pmax_node = q; pmax_prev = qlast; } qlast_prev = qlast;
qlast = q; q = q->next; } // do node switch
if(qlast == pmax_node->next) { pmax_node->next = qlast->next;
qlast->next = pmax_node; pmax_prev->next = qlast; } else { pmax_prev->next = qlast; qlast->next = pmax_node->next; qlast_prev->next = pmax_node; pmax_node->next = plist_end; plist_end = pmax_node; } if(p == pmax_node) { pfree_list = p = qlast; } } printf(" exit mem_node_sort_by_address \n");
} void *mem_alloc(int num_bytes) { int alloc_blk_size = num_bytes + mem_ctrl_blk_size; struct mem_ctrl_blk *pcur,*pmem,*prev; if(!mem_has_inited)
{ mem_init(); } printf(" mem_alloc %d bytes \n",num_bytes);
printf(" alloc_blk_size = %d \n", alloc_blk_size); prev = phead; pcur = prev->next; // means pfree_list while(pcur) { if(pcur->node_size < alloc_blk_size) { prev = pcur; pcur = pcur->next; } else { if(pcur->node_size - alloc_blk_size <= mem_ctrl_blk_size) { // do not need to split the memory pmem = pcur; if(pfree_list == pcur) { pfree_list = pcur->next; } prev ->next = pcur->next; } else { // need to split the memory pcur->node_size = pcur->node_size - alloc_blk_size; printf("remaining node size is %d \n",pcur->node_size); pmem =(struct mem_ctrl_blk *)((char *)pcur + pcur->node_size); pmem->node_size = alloc_blk_size; pmem->next = NULL; // insert the left memory node into // free memory list,firstly we need to // remove this node from free memory list prev->next = pcur->next; list_insert(pcur); } printf(" mem alloced ,mcb_address = %p\n",pmem); printf(" mem alloc success , address = %p \n", (void *)(pmem+1)); return (void *)(pmem+1);
// skip the memory control block } } printf("not enough memory found in free memory list \n");
printf("we need to collect memory fragment and check \n"); printf(" before sort by address : \n"); print_free_list(); mem_node_sort_by_address(); printf(" after sort by address : \n"); print_free_list(); mem_frag_collect(); printf(" after memory fragment collection : \n"); print_free_list(); mem_node_sort_after_collect(); printf(" after select sort by block size : \n"); print_free_list(); printf(" after memory fragment collection & sort " " we try to alloc memory \n"); prev = phead; pcur = prev->next; // means pfree_list while(pcur)
{ if(pcur->node_size < alloc_blk_size) { prev = pcur; pcur = pcur->next; } else { if(pcur->node_size - alloc_blk_size <= mem_ctrl_blk_size) { // do not need to split the memory pmem = pcur; if(pfree_list == pcur) { pfree_list = pcur->next; } prev ->next = pcur->next; } else { // need to split the memory pcur->node_size = pcur->node_size - alloc_blk_size; pmem = pcur + pcur->node_size; pmem->node_size = alloc_blk_size; pmem->next = NULL; // insert the left memory node into
// free memory list,firstly we need to // remove this node from free memory list prev->next = pcur->next; list_insert(pcur); } printf(" mem alloced ,mcb_address = %p\n",pmem);
printf(" mem alloc success , address = %p \n", (void *)(pmem+1)); return (void *)(pmem+1);
// skip the memory control block } } printf(" Not enough memory , fail to alloc \n");
printf(" exit mem_alloc \n"); return NULL; } /* If the parameter we pass to "mem_free" is not the one we alloc memory , what will happen ? ((struct mem_ctrl_blk *)p - 1) , will not point to the memory control block ? For example : p = (char *) malloc (sizeof(char) * 100); free(p+3); */ void mem_free(void *p) { struct mem_ctrl_blk *pfree_mcb = ((struct mem_ctrl_blk *)p - 1); printf(" mem_free : data address = %p \n",p); printf(" mcb_address = %p \n",pfree_mcb); list_insert(pfree_mcb); } void print_free_list() { struct mem_ctrl_blk *p = pfree_list; printf("enter print_free_list \n"); while(p)
{ printf("address = %p \n",p); printf("block size = %d \n",p->node_size); p = p->next; } } struct tagpp { int x; int y; }; int main() { struct tagpp *pt_tag; char *p1,*p2,*p3,*p4,*p5; p1=p2=p3=p4=p5=NULL;
printf(" heap memory address = %p \n",heap_mem);
printf(" memory control block size is %d \n", mem_ctrl_blk_size); mem_init(); printf(" before alloc any memory \n"); print_free_list(); pt_tag =(struct tagpp*)mem_alloc(sizeof(struct tagpp)); if(!pt_tag) { printf(" fail to alloc memory \n"); print_free_list(); return 0; } pt_tag->x=1; pt_tag->y=2; printf("x = %d y = %d\n",pt_tag->x,pt_tag->y); mem_free(pt_tag); printf("after free tagpp \n"); print_free_list(); p1 = (char *)mem_alloc(100); if(!p1) { printf("fail to alloc memory for p1\n"); } p2 = (char *)mem_alloc(50); if(!p2) { printf("fail to alloc memory for p2\n"); } p3 = (char *)mem_alloc(30); if(!p3) { printf("fail to alloc memory for p3\n"); } p4 = (char *)mem_alloc(20); if(!p4) { printf("fail to alloc memory for p4\n"); } p5 = (char *)mem_alloc(4); if(!p5) { printf("fail to alloc memory for p5\n"); } print_free_list(); if(p5) { mem_free(p5); printf("p5 free \n"); } p5 = (char *)mem_alloc(200); if(!p5) { printf("fail to alloc memory for p5\n"); } if(p1) { mem_free(p1); printf("p1 free \n"); } if(p2)
{ mem_free(p2); printf("p2 free \n"); } if(p3) { mem_free(p3); printf("p3 free \n"); } if(p4) { mem_free(p4); printf("p4 free \n"); } if(p5) { mem_free(p5); printf("p5 free \n"); } print_free_list(); p5 = (char *)mem_alloc(200); if(!p5) { printf("fail to alloc memory for p5\n"); } if(p5)
{ mem_free(p5); print_free_list(); } system("PAUSE"); return 0; } #endif
DEVC++下的运行结果如下：
heap memory address = 00405070
memory control block size is 8
before alloc any memory
enter print_free_list
address = 00405078
block size = 312
mem_alloc 8 bytes
alloc_blk_size = 16
remaining node size is 296
mem alloced ,mcb_address = 004051A0
mem alloc success , address = 004051A8
x = 1 y = 2
mem_free : data address = 004051A8
mcb_address = 004051A0
after free tagpp
enter print_free_list
address = 004051A0
block size = 16
address = 00405078
block size = 296
mem_alloc 100 bytes
alloc_blk_size = 108
remaining node size is 188
mem alloced ,mcb_address = 00405134
mem alloc success , address = 0040513C
mem_alloc 50 bytes
alloc_blk_size = 58
remaining node size is 130
mem alloced ,mcb_address = 004050FA
mem alloc success , address = 00405102
mem_alloc 30 bytes
alloc_blk_size = 38
remaining node size is 92
mem alloced ,mcb_address = 004050D4
mem alloc success , address = 004050DC
mem_alloc 20 bytes
alloc_blk_size = 28
remaining node size is 64
mem alloced ,mcb_address = 004050B8
mem alloc success , address = 004050C0
mem_alloc 4 bytes
alloc_blk_size = 12
mem alloced ,mcb_address = 004051A0
mem alloc success , address = 004051A8
enter print_free_list
address = 00405078
block size = 64
mem_free : data address = 004051A8
mcb_address = 004051A0
p5 free
mem_alloc 200 bytes
alloc_blk_size = 208
not enough memory found in free memory list
we need to collect memory fragment and check
before sort by address :
enter print_free_list
address = 004051A0
block size = 16
address = 00405078
block size = 64
enter mem_node_sort_by_address
exit mem_node_sort_by_address
after sort by address :
enter print_free_list
address = 00405078
block size = 64
address = 004051A0
block size = 16
enter mem_frag_collect
pfree_list = 00405078 , phead = 00405070
q = 004051A0, p = 00405078
q->node_size = 16 , p->node_size = 64
q = 00000000, p = 004051A0
exit mem_frag_collect
after memory fragment collection :
enter print_free_list
address = 00405078
block size = 64
address = 004051A0
block size = 16
enter mem_node_sort_after_collect
exit mem_node_sort_after_collect
after select sort by block size :
enter print_free_list
address = 004051A0
block size = 16
address = 00405078
block size = 64
after memory fragment collection & sort we try to alloc memory
Not enough memory , fail to alloc
exit mem_alloc
fail to alloc memory for p5
mem_free : data address = 0040513C
mcb_address = 00405134
p1 free
mem_free : data address = 00405102
mcb_address = 004050FA
p2 free
mem_free : data address = 004050DC
mcb_address = 004050D4
p3 free
mem_free : data address = 004050C0
mcb_address = 004050B8
p4 free
enter print_free_list
address = 004051A0
block size = 16
address = 004050B8
block size = 28
address = 004050D4
block size = 38
address = 004050FA
block size = 58
address = 00405078
block size = 64
address = 00405134
block size = 108
mem_alloc 200 bytes
alloc_blk_size = 208
not enough memory found in free memory list
we need to collect memory fragment and check
before sort by address :
enter print_free_list
address = 004051A0
block size = 16
address = 004050B8
block size = 28
address = 004050D4
block size = 38
address = 004050FA
block size = 58
address = 00405078
block size = 64
address = 00405134
block size = 108
enter mem_node_sort_by_address
exit mem_node_sort_by_address
after sort by address :
enter print_free_list
address = 00405078
block size = 64
address = 004050B8
block size = 28
address = 004050D4
block size = 38
address = 004050FA
block size = 58
address = 00405134
block size = 108
address = 004051A0
block size = 16
enter mem_frag_collect
pfree_list = 00405078 , phead = 00405070
q = 004050B8, p = 00405078
q->node_size = 28 , p->node_size = 64
p + p_size = q
q = 004050D4, p = 00405078
q->node_size = 38 , p->node_size = 92
p + p_size = q
q = 004050FA, p = 00405078
q->node_size = 58 , p->node_size = 130
p + p_size = q
q = 00405134, p = 00405078
q->node_size = 108 , p->node_size = 188
p + p_size = q
q = 004051A0, p = 00405078
q->node_size = 16 , p->node_size = 296
p + p_size = q
q = 00000000, p = 00405078
exit mem_frag_collect
after memory fragment collection :
enter print_free_list
address = 00405078
block size = 312
enter mem_node_sort_after_collect
exit mem_node_sort_after_collect
after select sort by block size :
enter print_free_list
address = 00405078
block size = 312
after memory fragment collection & sort we try to alloc memory
mem alloced ,mcb_address = 004053B8
mem alloc success , address = 004053C0
mem_free : data address = 004053C0
mcb_address = 004053B8
enter print_free_list
address = 00405078
block size = 104
address = 004053B8
block size = 208
请按任意键继续. . .
小结 ： 在malloc的时候，我们会从内存链上找第一个符合大小要求的内存块，是因为我们在调用 free释放内存的时候，会将释放的内存块插入到空闲内存链的合适位置，使得此链表依然 是按内存块大小升序排列的，当然，其实在调用free释放内存时不应该做那么多事情；但 如果此时不做内存块插入的动作，那么就要在每次调用malloc的时候，进行内存块按大小 升序排列的动作，而对应的排序的时间复杂度为O(n2)，比起在free的时候进行插入排序 的时间复杂度O(n)，时间上实在太耗时了。 之所以要进行sort by address，是因为我们要进行memory collect，如果不排序，对链表 里面的节点按照地址进行merge，时间复杂度高，并且容易出错。 当在空闲内存链上找不到请求大小的内存块的时候，我们就要进行memory collect了， 然后再从链表上搜索是否有合适大小的内存块，如果有，则申请成功，否则申请失败。 当然，我们可以看到，进行memory collect是非常耗时的，需要排序，针对上面的 best fit策略，我们需要排序两次 （ sort by node address & sort by node size )。 ==============================================================
2.First Fit示例程序 #if 1
/* Here is 1 program using "First Fit " Strategy . */ #include <stdio.h> #include <stdlib.h> #define HEAP_SIZE 320 char heap_mem[HEAP_SIZE]; struct mem_ctrl_blk { int node_size; struct mem_ctrl_blk * next; }; struct mem_ctrl_blk * phead = NULL; // phead : stands for the head node of memory list struct mem_ctrl_blk * pfree_list = NULL; int mem_ctrl_blk_size = sizeof(struct mem_ctrl_blk); int mem_has_inited = 0; extern void print_free_list(); void mem_init() { phead = (struct mem_ctrl_blk *)heap_mem; phead->node_size = 0; pfree_list = phead + 1; pfree_list->node_size = HEAP_SIZE - mem_ctrl_blk_size; pfree_list->next = NULL; phead->next = pfree_list; mem_has_inited = 1; } void list_insert(struct mem_ctrl_blk *pnode) { pnode->next = phead->next; phead->next = pnode; pfree_list = pnode; } void mem_frag_collect() { struct mem_ctrl_blk *p = pfree_list; struct mem_ctrl_blk *plast = phead; struct mem_ctrl_blk *q; printf(" enter mem_frag_collect \n"); // if only 1 node , there is no memory fragment
printf(" pfree_list = %p , phead = %p \n", pfree_list,phead); while(p)
{ q = p->next; printf(" q = %p, p = %p \n",q,p); if(q) { printf(" q->node_size = %d , p->node_size = %d \n", q->node_size,p->node_size); } if ((char *)p + p->node_size == (char *)q) { printf(" p + p_size = q \n"); p->node_size += q->node_size; p->next = q->next; } else { p = p->next; } } printf(" exit mem_frag_collect \n"); } void mem_node_sort_by_address() { struct mem_ctrl_blk *p_unsorted_list_head,*psorted_list_end; struct mem_ctrl_blk *pmin_addr,*pmin_addr_last; struct mem_ctrl_blk *q,*qlast; printf(" enter mem_node_sort_by_address \n"); pmin_addr = p_unsorted_list_head = pfree_list; psorted_list_end = phead; while(p_unsorted_list_head) { pmin_addr = p_unsorted_list_head; q = p_unsorted_list_head->next; qlast = pmin_addr; while(q) { if(pmin_addr > q) { pmin_addr = q; pmin_addr_last = qlast; } qlast = q; q = q->next; } if(pmin_addr == p_unsorted_list_head) // min address node is the unsorted head
{ p_unsorted_list_head = p_unsorted_list_head->next; pmin_addr->next = NULL; psorted_list_end->next = pmin_addr; psorted_list_end = pmin_addr; } else // min address node is not the unsorted head { pmin_addr_last->next = pmin_addr->next; pmin_addr->next = NULL; psorted_list_end->next = pmin_addr; psorted_list_end = pmin_addr; } }
printf(" exit mem_node_sort_by_address \n"); } void *mem_alloc(int num_bytes) { int alloc_blk_size = num_bytes + mem_ctrl_blk_size; struct mem_ctrl_blk *pcur,*pmem,*prev; if(!mem_has_inited)
{ mem_init(); } printf(" mem_alloc %d bytes \n",num_bytes);
printf(" alloc_blk_size = %d \n", alloc_blk_size); prev = phead; pcur = prev->next; // means pfree_list while(pcur) { if(pcur->node_size < alloc_blk_size) { prev = pcur; pcur = pcur->next; } else { if(pcur->node_size - alloc_blk_size <= mem_ctrl_blk_size) { // do not need to split the memory pmem = pcur; if(pfree_list == pcur) { pfree_list = pcur->next; } prev ->next = pcur->next; } else { // need to split the memory pcur->node_size = pcur->node_size - alloc_blk_size; printf("remaining node size is %d \n",pcur->node_size); pmem =(struct mem_ctrl_blk *)((char *)pcur + pcur->node_size); pmem->node_size = alloc_blk_size; pmem->next = NULL; // insert the left memory node into // free memory list,firstly we need to // remove this node from free memory list prev->next = pcur->next; list_insert(pcur); } printf(" mem alloced ,mcb_address = %p\n",pmem); printf(" mem alloc success , address = %p \n", (void *)(pmem+1)); return (void *)(pmem+1);
// skip the memory control block } } printf("not enough memory found in free memory list \n");
printf("we need to collect memory fragment and check \n"); printf(" before sort by address : \n"); print_free_list(); mem_node_sort_by_address(); printf(" after sort by address : \n"); print_free_list(); mem_frag_collect(); printf(" after memory fragment collection : \n"); print_free_list(); printf(" after memory fragment collection "
" we try to alloc memory \n"); prev = phead; pcur = prev->next; // means pfree_list while(pcur)
{ if(pcur->node_size < alloc_blk_size) { prev = pcur; pcur = pcur->next; } else { if(pcur->node_size - alloc_blk_size <= mem_ctrl_blk_size) { // do not need to split the memory pmem = pcur; if(pfree_list == pcur) { pfree_list = pcur->next; } prev ->next = pcur->next; } else { // need to split the memory pcur->node_size = pcur->node_size - alloc_blk_size; pmem = pcur + pcur->node_size; pmem->node_size = alloc_blk_size; pmem->next = NULL; // insert the left memory node into
// free memory list,firstly we need to // remove this node from free memory list prev->next = pcur->next; list_insert(pcur); } printf(" mem alloced ,mcb_address = %p\n",pmem);
printf(" mem alloc success , address = %p \n", (void *)(pmem+1)); return (void *)(pmem+1);
// skip the memory control block } } printf(" Not enough memory , fail to alloc \n");
printf(" exit mem_alloc \n"); return NULL; } /* If the parameter we pass to "mem_free" is not the one we alloc memory , what will happen ? ((struct mem_ctrl_blk *)p - 1) , will not point to the memory control block ? For example : p = (char *) malloc (sizeof(char) * 100); free(p+3); */ void mem_free(void *p) { struct mem_ctrl_blk *pfree_mcb = ((struct mem_ctrl_blk *)p - 1); printf(" mem_free : data address = %p \n",p); printf(" mcb_address = %p \n",pfree_mcb); list_insert(pfree_mcb); } void print_free_list() { struct mem_ctrl_blk *p = pfree_list; printf("enter print_free_list \n"); while(p)
{ printf("address = %p \n",p); printf("block size = %d \n",p->node_size); p = p->next; } } struct tagpp { int x; int y; }; int main() { struct tagpp *pt_tag; char *p1,*p2,*p3,*p4,*p5; p1=p2=p3=p4=p5=NULL;
printf(" heap memory address = %p \n",heap_mem);
printf(" memory control block size is %d \n", mem_ctrl_blk_size); mem_init(); printf(" before alloc any memory \n"); print_free_list(); pt_tag =(struct tagpp*)mem_alloc(sizeof(struct tagpp)); if(!pt_tag) { printf(" fail to alloc memory \n"); print_free_list(); return 0; } pt_tag->x=1; pt_tag->y=2; printf("x = %d y = %d\n",pt_tag->x,pt_tag->y); mem_free(pt_tag); printf("after free tagpp \n"); print_free_list(); p1 = (char *)mem_alloc(100); if(!p1) { printf("fail to alloc memory for p1\n"); } p2 = (char *)mem_alloc(50); if(!p2) { printf("fail to alloc memory for p2\n"); } p3 = (char *)mem_alloc(30); if(!p3) { printf("fail to alloc memory for p3\n"); } p4 = (char *)mem_alloc(20); if(!p4) { printf("fail to alloc memory for p4\n"); } p5 = (char *)mem_alloc(4); if(!p5) { printf("fail to alloc memory for p5\n"); } print_free_list(); if(p5) { mem_free(p5); printf("p5 free \n"); } p5 = (char *)mem_alloc(200); if(!p5) { printf("fail to alloc memory for p5\n"); } if(p1) { mem_free(p1); printf("p1 free \n"); } if(p5)
{ mem_free(p5); printf("p5 free \n"); } if(p3)
{ mem_free(p3); printf("p3 free \n"); } if(p2)
{ mem_free(p2); printf("p2 free \n"); } if(p4) { mem_free(p4); printf("p4 free \n"); } print_free_list(); p5 = (char *)mem_alloc(200); if(!p5) { printf("fail to alloc memory for p5\n"); } if(p5)
{ mem_free(p5); print_free_list(); } system("PAUSE"); return 0; } #endif
VC++6.0下的运行结果为：
heap memory address = 0042AC78
memory control block size is 8 before alloc any memory enter print_free_list address = 0042AC80 block size = 312 mem_alloc 8 bytes alloc_blk_size = 16 remaining node size is 296 mem alloced ,mcb_address = 0042ADA8 mem alloc success , address = 0042ADB0 x = 1 y = 2 mem_free : data address = 0042ADB0 mcb_address = 0042ADA8 after free tagpp enter print_free_list address = 0042ADA8 block size = 16 address = 0042AC80 block size = 296 mem_alloc 100 bytes alloc_blk_size = 108 remaining node size is 188 mem alloced ,mcb_address = 0042AD3C mem alloc success , address = 0042AD44 mem_alloc 50 bytes alloc_blk_size = 58 remaining node size is 130 mem alloced ,mcb_address = 0042AD02 mem alloc success , address = 0042AD0A mem_alloc 30 bytes alloc_blk_size = 38 remaining node size is 92 mem alloced ,mcb_address = 0042ACDC mem alloc success , address = 0042ACE4 mem_alloc 20 bytes alloc_blk_size = 28 remaining node size is 64 mem alloced ,mcb_address = 0042ACC0 mem alloc success , address = 0042ACC8 mem_alloc 4 bytes alloc_blk_size = 12 remaining node size is 52 mem alloced ,mcb_address = 0042ACB4 mem alloc success , address = 0042ACBC enter print_free_list address = 0042AC80 block size = 52 address = 0042ADA8 block size = 16 mem_free : data address = 0042ACBC mcb_address = 0042ACB4 p5 free mem_alloc 200 bytes alloc_blk_size = 208 not enough memory found in free memory list we need to collect memory fragment and check before sort by address : enter print_free_list address = 0042ACB4 block size = 12 address = 0042AC80 block size = 52 address = 0042ADA8 block size = 16 enter mem_node_sort_by_address exit mem_node_sort_by_address after sort by address : enter print_free_list address = 0042AC80 block size = 52 address = 0042ACB4 block size = 12 address = 0042ADA8 block size = 16 enter mem_frag_collect pfree_list = 0042AC80 , phead = 0042AC78 q = 0042ACB4, p = 0042AC80 q->node_size = 12 , p->node_size = 52 p + p_size = q q = 0042ADA8, p = 0042AC80 q->node_size = 16 , p->node_size = 64 q = 00000000, p = 0042ADA8 exit mem_frag_collect after memory fragment collection : enter print_free_list address = 0042AC80 block size = 64 address = 0042ADA8 block size = 16 after memory fragment collection we try to alloc memory Not enough memory , fail to alloc exit mem_alloc fail to alloc memory for p5 mem_free : data address = 0042AD44 mcb_address = 0042AD3C p1 free mem_free : data address = 0042ACE4 mcb_address = 0042ACDC p3 free mem_free : data address = 0042AD0A mcb_address = 0042AD02 p2 free mem_free : data address = 0042ACC8 mcb_address = 0042ACC0 p4 free enter print_free_list address = 0042ACC0 block size = 28 address = 0042AD02 block size = 58 address = 0042ACDC block size = 38 address = 0042AD3C block size = 108 address = 0042AC80 block size = 64 address = 0042ADA8 block size = 16 mem_alloc 200 bytes alloc_blk_size = 208 not enough memory found in free memory list we need to collect memory fragment and check before sort by address : enter print_free_list address = 0042ACC0 block size = 28 address = 0042AD02 block size = 58 address = 0042ACDC block size = 38 address = 0042AD3C block size = 108 address = 0042AC80 block size = 64 address = 0042ADA8 block size = 16 enter mem_node_sort_by_address exit mem_node_sort_by_address after sort by address : enter print_free_list address = 0042AC80 block size = 64 address = 0042ACC0 block size = 28 address = 0042ACDC block size = 38 address = 0042AD02 block size = 58 address = 0042AD3C block size = 108 address = 0042ADA8 block size = 16 enter mem_frag_collect pfree_list = 0042AC80 , phead = 0042AC78 q = 0042ACC0, p = 0042AC80 q->node_size = 28 , p->node_size = 64 p + p_size = q q = 0042ACDC, p = 0042AC80 q->node_size = 38 , p->node_size = 92 p + p_size = q q = 0042AD02, p = 0042AC80 q->node_size = 58 , p->node_size = 130 p + p_size = q q = 0042AD3C, p = 0042AC80 q->node_size = 108 , p->node_size = 188 p + p_size = q q = 0042ADA8, p = 0042AC80 q->node_size = 16 , p->node_size = 296 p + p_size = q q = 00000000, p = 0042AC80 exit mem_frag_collect after memory fragment collection : enter print_free_list address = 0042AC80 block size = 312 after memory fragment collection we try to alloc memory mem alloced ,mcb_address = 0042AFC0 mem alloc success , address = 0042AFC8 mem_free : data address = 0042AFC8 mcb_address = 0042AFC0 enter print_free_list address = 0042AFC0 block size = 208 address = 0042AC80 block size = 104 请按任意键继续. . . 小结 ： 在malloc的时候，我们会从内存链上找第一个符合大小要求的内存块， 当然，此例中调用free释放内存时做的事情很少；但由此带来的sort by address 效率较低。当然，sort by address只会出现在需要memory collect的地方。 也就是说，当系统中memory collect出现次数较少时，此例中的free函数“比较高效”， 但一旦内存碎片较多，而memory collect出现的次数也不少时，建议还是在free结点 的时候，进行插入排序 （O(n)的时间复杂度），而不要等到memory collect，去调用 sort by address时，进行O(n2)的排序。 之所以要进行sort by address，是因为我们要进行memory collect，如果不排序， 对链表里面的节点按照地址进行merge，时间复杂度高，并且容易出错。 当在空闲内存链上找不到请求大小的内存块的时候，我们就要进行memory collect了， 然后再从链表上搜索是否有合适大小的内存块，如果有，则申请成功，否则申请失败。 可以看到，进行memory collect是非常耗时的，需要排序，针对上面的first fit策略， 我们需要排序（ sort by node address ）。 可改进的地方： 1.线程安全性 2. 函数效率 3.对申请的内存按大小（可以是8字节）进行对齐。
|
|
|
来自： happy123god > 《读书笔记及小结》
