零零散散学算法之浅析内存管理的方式

 

正文

 

       说到内存分配，我们立刻就会想到malloc()、calloc()等申请内存的接口，说到内存分配的算法，我们会想到Buddy和Slab等分配算法。那么你有没有思考过，申请的内存是如何管理的呢？管理的方式都有哪些？这就是本文将要讨论的。

 

       本文将介绍两种内存管理的方法：链表法和比特位法。

 

第零节 问题初始化

 

       假设现有一坨大小为M的内存，我们将它分为N块，那么每块的大小就是BLOCK_SIZE = M/N，如下图所示：

 

第一节 链表法

 

       所谓链表法内存管理，就是说将已经分好的一坨内存分成了许多的小块，然后将每个小块以链表的形式串起来。如下图：

 

       从图中可看到，我们在每个小块中添加了名为link的链表节点，它表示为：

[cpp]  

struct list_head  

{  

    struct list_head *next, *prev;  

};  

附注：在内核中该链表为双向链表，不过在上图中为了简洁，我将其表示为单链表。

 

       于是，我们就可以用一个名为head的头结点将这些小块串联起来了。当我们使用时，只需从链表上摘一个即可，用完之后就可还回。利用链表来管理内存的优点有以下两点：

 

       1. 即用即拿，用完即还（方便快捷）：就是说当我们需要在这坨申请好的内存中使用一个或者几个小块时，我们就可根据需要，从链表上摘下来一个或者几个，用完之后直接还回链表中即可。

 

       2. 管理流与数据流的融合与分离（节省空间）：当我们利用链表法管理内存时，我们只需知道每个块的link，这样我们就能利用link来管理每个块，我们说它们是融合的；当你要使用某个块时，将其从链表中摘下来，这个时候我们就用这个块来进行数据流操作，对于link我们并不关心，在这个角度上我们说它们是分离的。不论融合与分离，我们在操作时并没有用到额外的空间，而是在每个块的内部解决了管理流与数据流。

 

       好了，这就是链表法内存管理。节末，我还是给出链表法的代码：

[cpp]  

/** 

 *  链表法内存管理：内存初始化 

 

 *  addr: 表示块的起始地址 

 *  block_size: 表示每个块的大小 

 *  block_number: 表示块的个数 

 */  

void MemoryInit(void* addr, unsigned long block_size, unsigned int block_number)  

{  

    int i = 0;  

    struct list_head *link = (struct list_head*)addr;  

  

    for(; i < block_number; i++)  

    {  

        list_add_tail(link, head);//添加到链表尾部  

        addr += block_size;  

        link = (struct list_head*)addr;  

    }  

}  

[cpp]  

/** 

 *  链表法内存管理:内存块分配 

 */  

void* alloc_blkmem(void)  

{  

    struct list_head *link = NULL;  

    if(!list_empty(head))//链表不为空  

    {  

        link = head->next;  

        list_del_init(link);//从链表中摘除  

    }  

    return link;  

}  

[cpp]  

/** 

 *  链表法内存管理:内存块释放 

 * 

 *  addr: 表示块的起始地址 

 */  

void free_blkmem(void* addr)  

{  

    struct list_head *link = (struct list_head*)addr;  

    list_add_tail(link, head);//还回到链表中  

}  

第二节 比特位法

 

       和链表法相比，比特位法就更简单了。比特位的思想很简单，就是说当某个块没有被使用时，我们让该块对应位置的bit位为0，当这个块被使用时，就将它的bit位置为1。如下图：

 

       比特位法的确很直观，这是它的优点，但是和链表法相比，它在时间和空间上都不及链表法。我们来看看：

 

       在时间上：链表法是即用即拿，而比特位法则不然，它必须对bit表进行遍历，当bit位为0时方可取用；

 

       在空间上：链表法不需额外的空间，而比特位法则取额外的空间来存储bitmap表，有一个块就得对应一个bit位，当数据块很多时，这也是一笔不消的开销。

 

       虽然比特位法在时间上和空间上都不是很理想，但是它很直观，易理解。它也很常用！

 

       好了，比特位法就是个这，因为它很直观，所以我用很简单的几句话就说完了。节末，还是老办法，给出比特位法的代码，纵然它很简单！

[cpp] 

/** 设置bitmap的指定位 

 * 

 *  src: 表示bitmap 

 *  index：表示指定位 

 */  

void bitmap_set_bit(void *src, unsigned int index)  

{  

    unsigned short*    data_bitmap = (unsigned short *)src;  

    data_bitmap[index] |= 1 << index;  

}   www.zzzyk.com

[cpp]  

/** 清除bitmap的指定位 

 * 

 *  src: 表示bitmap 

 *  index：表示指定位 

 */  

void bitmap_clear_bit(void *src, unsigned int index)  

{  

    unsigned short*    data_bitmap = (unsigned short *)src;  

    data_bitmap[index]  &=  ~(1 << index);  

}  

第三节 结束语

 

       想想、写写、画画......

 

补充：软件开发 , C++ ,