我所理解的内存分配算法#1

内存分配从本质上来说是一种空间管理算法，给你一块连续的空间，提供存储服务，那么你的空间管理跟分配要采用什么样的算法才会比较高效？

Bump-the-Pointer

Bump-the-Pointer是最简单的算法。HotSpot的MM白皮书是这么描述btp的，

That is, the end of the previously allocated object is always kept track of. When a new allocation request needs to be satisfied, all that needs to be done is to check whether the object will fit in the remaining part of the generation and, if so, to update the pointer and initialize the object.

我们只需要一个指针来记录可用空间的起始地址，收到分配请求，先检查可用空间是否足够分配给这次请求，如果足够，则分配空间，并且更新指针；如果不够就需要进行垃圾回收了。我们再来看看HotSpot的SerialCollector是怎么使用btp的。

SerialCollector使用Mark-Sweep-Compact算法来对OldGen进行GC，对于OldGen的分配，简单的bump the pointer，如果这时候剩余的可用空间已经不够，SerialCollector需要Stop-the-World，然后执行Mark-Sweep-Compact，即标记活着的对象，清除死去的对象，最后做sliding compaction，将活着的对象全部压缩到一边，这样剩余的可用空间就可以继续简单的使用btp算法来分配空间了。

btp还有几个点说下，

  1. 对于多线程环境下，可以使用Thread-Local Allocation Buffers（TLABs）；
  2. 对于触发GC的时间点是可以优化的，不是非得等到有分配请求过来并且可用空间不足了才进行GC；
  3. Stop-the-World是硬伤；

Slab Allocator

现在让我们来看另外一种采用分治策略的管理方法。我们可以将连续空间划分成一个个的组，每个组内又包含若干个坑位，同组内每个坑位的空间大小都是一样的，至于坑位的大小是可以根据使用情况来进行调优的。

只需要再维护每个组的metadata，这样每次一有分配请求，先查看metadata就能做到Best Fit。

Slab Allocator便是以上述方式工作的。与Bumb-the-Pointer相比，Slab不需要Stop-the-World来做GC，但是会造成一定的空间浪费，因为我们只能做到Best Fit。

Memcached Slab

Talk is cheap，下面来看看Memcached中的Slab实现。先看SlabClass的定义和初始化的方法，

typedef struct {
    unsigned int size;      /* sizes of items */
    unsigned int perslab;   /* how many items per slab */

    void *slots;           /* list of item ptrs */
    unsigned int sl_curr;   /* total free items in list */

    unsigned int slabs;     /* how many slabs were allocated for this class */

    void **slab_list;       /* array of slab pointers */
    unsigned int list_size; /* size of prev array */

    unsigned int killing;  /* index+1 of dying slab, or zero if none */
    size_t requested; /* The number of requested bytes */
} slabclass_t;
void slabs_init(const size_t limit, const double factor, const bool prealloc) {
    int i = POWER_SMALLEST - 1;
    unsigned int size = sizeof(item) + settings.chunk_size;

    mem_limit = limit;

    if (prealloc) {
        /* Allocate everything in a big chunk with malloc */
        mem_base = malloc(mem_limit);
        if (mem_base != NULL) {
            mem_current = mem_base;
            mem_avail = mem_limit;
        } else {
            fprintf(stderr, "Warning: Failed to allocate requested memory in"
                    " one large chunk.\nWill allocate in smaller chunks\n");
        }
    }

    memset(slabclass, 0, sizeof(slabclass));

    while (++i < POWER_LARGEST && size <= settings.item_size_max / factor) {
        /* Make sure items are always n-byte aligned */
        if (size % CHUNK_ALIGN_BYTES)
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);

        slabclass[i].size = size;
        slabclass[i].perslab = settings.item_size_max / slabclass[i].size;
        size *= factor;
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }
    }

    power_largest = i;
    slabclass[power_largest].size = settings.item_size_max;
    slabclass[power_largest].perslab = 1;
    if (settings.verbose > 1) {
        fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                i, slabclass[i].size, slabclass[i].perslab);
    }

    /* for the test suite:  faking of how much we've already malloc'd */
    {
        char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
        if (t_initial_malloc) {
            mem_malloced = (size_t)atol(t_initial_malloc);
        }

    }

    if (prealloc) {
        slabs_preallocate(power_largest);
    }
}

slabs_init方法中可以看到我们上面所说的坑位大小的调优，Memcached是通过配置一个factor来实现，坑位的大小是按factor倍增长的。

需要注意这里的size是sizeof(item) + settings.chunk_size，item是Memcached所存储的数据，在memcache.h中定义。存储系统的数据结构设计又是另一个可以深究的话题，后面再探讨。

typedef struct _stritem {
    struct _stritem *next;
    struct _stritem *prev;
    struct _stritem *h_next;    /* hash chain next */
    rel_time_t      time;       /* least recent access */
    rel_time_t      exptime;    /* expire time */
    int             nbytes;     /* size of data */
    unsigned short  refcount;
    uint8_t         nsuffix;    /* length of flags-and-length string */
    uint8_t         it_flags;   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;       /* key length, w/terminating null and padding */
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
        uint64_t cas;
        char end;
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

每一个SlabClass里面有一组Slab，每个Slab又拆分为slabclass.perslab个大小为slabclass.size的坑位。 

static int grow_slab_list (const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    if (p->slabs == p->list_size) {
        size_t new_size =  (p->list_size != 0) ? p->list_size * 2 : 16;
        void *new_list = realloc(p->slab_list, new_size * sizeof(void *));
        if (new_list == 0) return 0;
        p->list_size = new_size;
        p->slab_list = new_list;
    }
    return 1;
}

static void split_slab_page_into_freelist(char *ptr, const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    int x;
    for (x = 0; x < p->perslab; x++) {
        do_slabs_free(ptr, 0, id);
        ptr += p->size;
    }
}

static int do_slabs_newslab(const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    int len = settings.slab_reassign ? settings.item_size_max
        : p->size * p->perslab;
    char *ptr;

    if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||
        (grow_slab_list(id) == 0) ||
        ((ptr = memory_allocate((size_t)len)) == 0)) {

        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }

    memset(ptr, 0, (size_t)len);
    split_slab_page_into_freelist(ptr, id);

    p->slab_list[p->slabs++] = ptr;
    mem_malloced += len;
    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);

    return 1;
}

使用FreeList，也就是slabclass.slots来管理这些可用的坑位， 

static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
    slabclass_t *p;
    item *it;

    assert(((item *)ptr)->slabs_clsid == 0);
    assert(id >= POWER_SMALLEST && id <= power_largest);
    if (id < POWER_SMALLEST || id > power_largest)
        return;

    MEMCACHED_SLABS_FREE(size, id, ptr);
    p = &slabclass[id];

    it = (item *)ptr;
    it->it_flags |= ITEM_SLABBED;
    it->prev = 0;
    it->next = p->slots;
    if (it->next) it->next->prev = it;
    p->slots = it;

    p->sl_curr++;
    p->requested -= size;
    return;
}

使用简单的互斥锁来应对并发情况。（为什么不是锁SlabClass而是需要直接锁住整个Slab Allocator？） 

void *slabs_alloc(size_t size, unsigned int id) {
    void *ret;

    pthread_mutex_lock(&slabs_lock);
    ret = do_slabs_alloc(size, id);
    pthread_mutex_unlock(&slabs_lock);
    return ret;
}

最后，上面说的都是逻辑结构，下面贴一下我整理的物理结构便于理解，其中slabclass[0].perslab=3。 

    mem_base                        slabclass[0].slots
       |                               |
       +---+---+---+---+---+---+---+---+---+---+
       | X | X | X | X |   |   |   | X |   |   |
       +---+---+---+---+---+---+---+---+---+---+
       |           |               |
  slabclass[0]  slabclass[1]    slabclass[0]
  .slab_list[0] .slab_list[0]   .slab_list[1]

Buddy Allocator

Buddy Allocator采用的策略与Slab类似，在我理解它只是一种特殊的Slab Allocator，坑位的大小是2的次幂，这样就导致了Buddy的空间浪费要比Slab严重得多，例如一个33K的分配请求会被分配到64K的空间。说到底其实还是要根据实际使用情况来调整坑位大小，减少空间的浪费。

参考资料

时间： 2024-11-02 20:25:31

我所理解的内存分配算法#1的相关文章

系统-最差适配内存分配算法模拟

问题描述 最差适配内存分配算法模拟 最差适配内存分配算法模拟 1.目的 用程序实现可变分区内存管理过程,并按最差适配算法进行分配. 2.内容 (1)基本思想 可变分区是指系统不预先划分固定分区,而是在装入程序的时候划分内存区 域,使得为程序分配的分区大小恰好等于该程序的需求量,且分区的个数是可变 的.显然可变分区有较大的灵活性,较之固定分区能获得好的内存利用率. (2)数据结构 可变分区管理可以用两种数据结构实现,一种是已分配区表和空闲区表,也 就是用预先定义好的系统空间来存放空间分配信息. 另

[jjzhu学java]之深入理解JVM之垃圾收集器与内存分配策略

深入理解JVM之垃圾收集器与内存分配策略 如何判断对象已经消亡 引用计数算法 根搜索算法 引用 深入理解JVM之垃圾收集器与内存分配策略 java中对象的创建需要的内存都是在java堆中申请的,所以垃圾收集的区域就是对java堆和方法区的内存区域进行GC. 如何判断对象已经消亡 垃圾收集器的主要任务就是找出已经"消亡"的对象,将其标记并清除其说用内存的过程,如何判断某个对象已经"消亡",不同的虚拟机有不同的判断策略 引用计数算法 引用计数(Reference Cou

深入理解Java之JVM堆内存分配

Java堆是被所有线程共享的一块内存区域,所有对象和数组都在堆上进行内存分配.为了进行高效的垃圾回收,虚拟机把堆内存划分成新生代.老年代和永久代(1.8中无永久代,使用metaspace实现)三块区域. Java把内存分成两种:栈内存和堆内存.关于堆内存和栈内存的区别与联系.简单的来讲,堆内存用于存放由new创建的对象和数组,在堆中分配的内存,由java虚拟机自动垃圾回收器来管理.而栈内存由使用的人向系统申请,申请人进行管理. 堆内存初始化 Java中分配堆内存是自动初始化的,其入口位于Univ

VMware内存机制的空闲内存税算法

我曾经在vmsky的论坛发表过一篇探讨VMware内存机制的帖子(见此http://bbs.vmsky.com/thread-23285-1-2.html),最后探讨的例子是一个考虑了空闲内存税(Idle Memory Tax,以下简称IMT)情况下的内存分配计算,但遗憾的是当时猜想的算法是错误的.今天在阅读了Carl的关于内存机制的论文后,深感有必要重新说明一下. 空闲内存税(Idle Memory Tax)是VMware为了更有效地利用主机内存而设置的,它在计算如何分配主机内存的时候,将VM

Android 优化二 Java内存分配机制及内存泄漏

Java内存分配机制及内存泄漏目录介绍 1.JVM内存管理 1.1 JVM内存管理图 1.2 Java采用GC进行内存管理. 2.JVM内存分配的几种策略 2.1 静态的 2.2 栈式的 2.3 堆式的 2.4 堆和栈的区别 2.5 得出结论 2.6 举个例子 2.7 调用 System.gc();进行内存回收 3.GC简单介绍 3.1 内存垃圾回收机制 3.2 关于GC介绍 3.3 如何监听GC过程 3.4 GC过程与对象的引用类型关系 4.内存泄漏简单介绍 4.1 内存泄漏的定义 4.2 内

Yarn 内存分配管理机制及相关参数配置

理解Yarn的内存管理与分配机制,对于我们搭建.部署集群,开发维护应用都是尤为重要的,对于这方面我做了一些调研供大家参考. 关于Yarn的详细介绍请参考[Hadoop Yarn详解] 一.相关配置情况 关于Yarn内存分配与管理,主要涉及到了ResourceManage.ApplicationMatser.NodeManager这几个概念,相关的优化也要紧紧围绕着这几方面来开展.这里还有一个Container的概念,现在可以先把它理解为运行map/reduce task的容器,后面有详细介绍.

垃圾收集器与内存分配策略

虚拟机如何判断对象是否存活? 1.引用计数算法   给对象中添加一个引用计数器,每当有一个地方引用它时,计数器就加1:当引用失效时,计数器值就减1:任何时刻计数器为0的对象就是不可能再被使用的.   考虑一种情形:对象objA和objB都有字段instance,赋值令objA.instance=objB和objB.instance=objA;除此之外,这两个对象再无任何引用,实际上这两个对象以及不可能再被访问,但是它们因为互相引用着对方,导致它们的引用计数都不为0,于是引用计数算法无法通知GC收

Linux 内存管理 块内存分配 slab分配器

Linux 内存管理之块内存分配 伙伴系统 伙伴系统是linux用于满足对不同大小块内存分配和释放请求的解决方案. 内存管理区 linux将内存分成三个内存管理区,分别为ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM,并使用三个管理区描述符管理这三个ZONE. 管理区描述符里,有一个元素数为11的free_area数组,分别对应1.2.4.8.16.....不同块的大小,其中的每个元素的类型都是一个名为free_area的结构体,代码位置mm/mmzone.h struct

C++ QVector 类介绍及内存分配策略

QVector 介绍 QVector类是一个提供动态数组的模板类. QVector<T>是Qt普通容器类的一种.它将自己的每一个对象存储在连续的内存中,可以使用索引号来快速访问它们.QList<T>.QLinkedList<T>和 QVarLengthArray<T>也提供了相似的功能,它们使用方法如下: l QList一般用得最多,它能满足我们绝大部分需求.像prepend()和insert()这样的操作通常比QVector要快些,这是由于QList存储它