Buddy memory allocation (伙伴内存分配器)
今天吃晚饭的时候想到,我需要一个定制的内存分配器。主要是为了解决 共享内存 中的字符串池的管理。
这个内存分配器需要是非入侵式的,即不在要分配的内存块中写 cookie 。
而我的需求中,需要被管理的内存块都是很规则的,成 2 的整数次幂的长度。buddy memory allocation 刚好适用。
算法很简单,就是每次把一个正内存块对半切分,一直切到需要的大小分配出去。回收的时候,如果跟它配对的块也是未被使用的,就合并成一个大的块。标准算法下,分配和释放的时间复杂度都是 O(log N) ,N 不会特别大。算法的优点是碎片率很小。而且很容易做成非入侵式的,不用在被管理的内存上保存 cookie 。只需要额外开辟一个二叉树记录内存使用状态即可。
我吃完饭简单 google 了一下,没有立刻找到满足我要求的现成代码。心里估算了一下,C 代码量应该在 200 行以下,我大概可以在 1 小时内写完。所以就毫不犹豫的实现了一份。
然后,自然是开源了。有兴趣的同学可以去 github 拿一份。这样就省得到再需要时再造轮子了。嘿嘿。
btw, 当然这块代码有许多值得优化的地方,比如可以把里面的递归优化成循环回溯。这个算法我读初中时经常写。因为那个时候最早参加信息学奥赛时用的 basic 且不支持局部变量,全部变量都是全局的,很难实现递归。所以早期我都不用递归遍历二叉树的,感觉写起来好麻烦。
不过循环回溯遍历树应该是比递归快不少的,因为减少了许多不必要的环境变量压栈,尤其对不支持 closure 的 C 语言尤其是。
这个库用起来很简单。它并不实际管理内存(它不侵入被管理的内存)。你可以设想你另外有一大块内存是由许多最小单位块合起来的。你可以假设最小单位是 1K 。那么用 buddy_new(10) 就可以帮你管理 1024K 内存。
buddy_alloc 可以请求若干个最小单位块,返回一个序号。然后用户可以自己去大内存上索引出来用。用完调用 buddy_free 归还即可。
为了调试方便,我还提供了 buddy_dump 打印二叉树的细节,可以直观的看出那些内存区域未被使用,哪些已经被占用。
ps. 果然,写这篇 blog 花掉的时间比完成这些代码时间更长。代码也如我所料的没有超过 200 行。看看,把东西描述清楚就是比实现一个东西要花更长的时间,这就是项目人多反而做的慢的原因之一吧。
建议继续学习:
- Linux内存点滴 用户进程内存空间 (阅读:11426)
- ps - 按进程消耗内存多少排序 (阅读:11249)
- Linux Used内存到底哪里去了? (阅读:9956)
- Linux操作系统的内存使用方法详细解析 (阅读:8861)
- linux内核研究笔记(一)内存管理 – page介绍 (阅读:8569)
- 几个内存相关面试题(c/c++) (阅读:8011)
- 内存越界的概念和调试方法 (阅读:6283)
- Innodb分表太多或者表分区太多,会导致内存耗尽而宕机 (阅读:6150)
- 必看!linux系统如何查看内存使用情况 (阅读:6144)
- 如何查看Linux 硬件配置信息 (阅读:5864)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:云风的 BLOG 来源: 云风的 BLOG
- 标签: 内存
- 发布时间:2011-12-20 23:50:33
- [55] IOS安全–浅谈关于IOS加固的几种方法
- [54] 如何拿下简短的域名
- [54] 图书馆的世界纪录
- [54] android 开发入门
- [52] Oracle MTS模式下 进程地址与会话信
- [52] Go Reflect 性能
- [49] 【社会化设计】自我(self)部分――欢迎区
- [48] 读书笔记-壹百度:百度十年千倍的29条法则
- [41] 程序员技术练级攻略
- [35] 视觉调整-设计师 vs. 逻辑