即实现一个 FreeList,每个 FreeList 用于分配固定大小的内存块,比如用于分配 32字节对象的固定内存分配
器,之类的。每个固定内存分配器里面有两个链表,OpenList 用于存储未分配的空闲对象,CloseList用于存
储已分配的内存对象,那么所谓的分配就是从 OpenList 中取出一个对象放到 CloseList 里并且返回给用户,
释放又是从 CloseList 移回到 OpenList。分配时如果不够,那么就需要增长 OpenList:申请一个大一点的内
存块,切割成比如 64 个相同大小的对象添加到 OpenList中。这个固定内存分配器回收的时候,统一把先前
向系统申请的内存块全部还给系统。
优点:简单粗暴,200行代码就可以搞定,分配和释放的效率高,解决实际中特定场景下的问题有效。
缺点:功能单一,只能解决定长的内存需求,另外占着内存没有释放。
范例:
一个简单O(1)定长内存池实现
3.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 类似的分配器其实是比较残缺的,你还需要往下继续优化。
优点:这个本质是定长内存池的改进,分配和释放的效率高。可以解决一定长度内的问题。
缺点:存在内碎片的问题,且将一块大内存切小以后,申请大内存无法使用。多线程并发场景下,锁竞争激
烈,效率降低。
范例:sgi stl 六大组件中的空间配置器就是这种设计实现的。