Archive

Posts Tagged ‘系统开发’

如何设计一个内存分配器?

July 27th, 2015 2 comments

通常工程里不推荐自己写内存分配器,因为你费力写一个出来99%可能性没有内置的好,且内存出bug难调试
不过看书之余,你也可以动手自己试试,当个玩具写写玩玩:

1. 实现教科书上的内存分配器:

做一个链表指向空闲内存,分配就是取出一块来,改写链表,返回,释放就是放回到链表里面,并做好归并。注意做好标记和保护,避免二次释放,还可以花点力气在如何查找最适合大小的内存快的搜索上,减少内存碎片,有空你了还可以把链表换成伙伴算法,写着玩嘛。

2. 实现固定内存分配器:

即实现一个 FreeList,每个 FreeList 用于分配固定大小的内存块,比如用于分配 32字节对象的固定内存分配器,之类的。每个固定内存分配器里面有两个链表,OpenList 用于存储未分配的空闲对象,CloseList用于存储已分配的内存对象,那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户,释放又是从 CloseList 移回到 OpenList。分配时如果不够,那么就需要增长 OpenList:申请一个大一点的内存块,切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候,统一把先前向系统申请的内存块全部还给系统。

3. 实现 FreeList 池:

在你实现了 FreeList的基础上,按照不同对象大小(8字节,16字节,32,64,128,256,512,1K。。。64K),构造十多个固定内存分配器,分配内存时根据内存大小查表,决定到底由哪个分配器负责,分配后要在头部的 header 处(ptr[-sizeof(char*)]处)写上 cookie,表示又哪个分配器分配的,这样释放时候你才能正确归还。如果大于64K,则直接用系统的 malloc作为分配,如此以浪费内存为代价你得到了一个分配时间近似O(1)的内存分配器,差不多实现了一个 memcached 的 slab 内存管理器了,但是先别得意。此 slab 非彼 slab(sunos/solaris/linux kernel 的 slab)。这说白了还是一个弱智的 freelist 无法归还内存给操作系统,某个 FreeList 如果高峰期占用了大量内存即使后面不用,也无法支援到其他内存不够的 FreeList,所以我们做的这个和 memcached 类似的分配器其实是比较残缺的,你还需要往下继续优化。

Read more…

Categories: 编程技术 Tags: ,