BlueStore源码分析之Stupid分配器-创新互联

前言

前面介绍了 BlueStore的BitMap分配器,我们知道新版本的 Bitmap分配器的优势在于 使用连续的内存空间从而尽可能更多的命中CPU Cache以提高分配器性能。在这里我们了解一下基于区间树的 Stupid分配器(类似于Linux Buddy内存管理算法),并对比分析一下其优劣。

创新互联主要从事网站设计制作、成都网站制作、网页设计、企业做网站、公司建网站等业务。立足成都服务普宁,十余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18982081108

目录

  • 伙伴算法
  • 数据结构
  • 初始化
  • 插入删除
  • 空间分配
  • 空间回收
  • 优劣分析

伙伴算法

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;
};

网页名称:BlueStore源码分析之Stupid分配器-创新互联
网页地址:/article36/cooosg.html

成都网站建设公司_创新互联,为您提供网站设计公司网站排名标签优化品牌网站设计服务器托管域名注册

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

星空体育app最新版本(2024已更新)建设