前言
前面介绍了BlueStore的BitMap分配器，我们知道新版本的Bitmap分配器的优势在于使用连续的内存空间从而尽可能更多的命中CPU Cache以提高分配器性能。在这里我们了解一下基于区间树的Stupid分配器（类似于Linux Buddy内存管理算法），并对比分析一下其优劣。
目录
- 伙伴算法
- 数据结构
- 初始化
- 插入删除
- 空间分配
- 空间回收
- 优劣分析
伙伴算法
Linux内存管理算法为了能够快速响应请求，尽可能的提高内存利用率同时减少外部内存碎片，引入了伙伴系统算法Buddy-System。该算法将所有的空闲页分组为11个链表，每个链表分别包含1、2、4、8、16、32、64、128、256、512、1024个连续的页框块，每个页框块的第一个内存页的物理地址是该块大小的整数倍。伙伴的特点是：两个块大小相同、两个块地址连续、第一块的第一个页框的物理地址是两个块总大小的整数倍（同属于一个大块，第1块和第2块是伙伴，第3块和第4块是伙伴，但是第2块和第3块不是伙伴）。具体内存分配和内存释放可自行Google。
优点：
- 较好的解决外部碎片问题，不能完全解决。
- 针对大内存分配设计，可以快速的分配连续的内存。
缺点：
- 合并的要求过于严格，只能是满足伙伴关系的块才可以合并。
- 一块连续的内存中仅有一个页面被占用，就导致整个内存不具备合并的条件。
- 算法页面连续性差，DMA申请大块连续物理内存空间可能失败，此时需要
CMA(Contiguous Memory Allocator, 连续内存分配器)。 - 浪费空间，可以通过slab、kmem_cache等解决。
数据结构
Stupid分配器使用了区间树组织数据结构，高效管理Extent(offset, length)。
class StupidAllocator : public Allocator { CephContext* cct; // 分配空间用的互斥锁 std::mutex lock; // 空闲空间总大小 int64_t num_free; // 最后一次分配空间的位置 uint64_t last_alloc; // 区间树数组，初始化的时候，free数组的长度为10，即有十颗区间树 std::vector<interval_set_t> free; // extent: offset, length typedef mempool::bluestore_alloc::pool_allocator< pair<const uint64_t, uint64_t>> allocator_t; // 有序的 btree map，按顺存放extent。 typedef btree::btree_map<uint64_t, uint64_t, std::less<uint64_t>, allocator_t> interval_set_map_t; // 区间树，主要的操作有 insert、erase等。 typedef interval_set<uint64_t, interval_set_map_t> interval_set_t;};免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
软考中级精品资料免费领
历年真题答案解析
备考技巧名师总结
高频考点精准押题
- 资料下载
- 历年真题
193.9 KB下载数265
191.63 KB下载数245
143.91 KB下载数1142
183.71 KB下载数642
644.84 KB下载数2755
相关文章
发现更多好内容猜你喜欢
AI推送时光机BlueStore源码分析之Stupid分配器
Redis之quicklist源码分析
