靠谱:保证实时的动态内存分配

靠谱:保证实时的动态内存分配五一在家没有出门,研究了一下TLSF动态内存分配算法。缘起要说清楚TLSF,得从动态内存分配开始说起。动态内存分配是所有系统中都要考虑的问题,我们从学C语言开始就知道用的malloc函数就是用来申请动态内存的。其基本原理就是malloc时系统从堆中拿出一块内存分配给你用,用完之后通过free再还回去。这个过程有点像借钱,比如最近疫情手头紧,没钱吃饭了,于是找朋友malloc点钱去吃饭,比…

大家好,欢迎来到IT知识分享网。

五一在家没有出门,研究了一下 TLSF 动态内存分配算法。

缘起

要说清楚TLSF,得从动态内存分配开始说起。动态内存分配是所有系统中都要考虑的问题,我们从学C语言开始就知道用的malloc函数就是用来申请动态内存的。其基本原理就是malloc时系统从堆中拿出一块内存分配给你用,用完之后通过free再还回去。

这个过程有点像借钱,比如最近疫情手头紧,没钱吃饭了,于是找朋友malloc点钱去吃饭,比如说10块吧,等我打工挣了钱再free给朋友,这就是动态分配,而朋友就是那个拥有很多钱(内存)的壕。

那么问题就来了,既然朋友是个壕,必然有很多钱,我去malloc 10块钱的时候,他可能没有零钱,都是100的,于是他直接扔给了我100,我拿着这100也不敢都花了,毕竟现在疫情紧张能有饭吃就不错了,标准都是10块,所以其实还有90块给我是浪费掉了,明明这90块还可以再去帮助9个像我这样的,于是资源利用效率就降低了。朋友虽然壕,但架不住我这样的人多啊,资源慢慢就被耗尽,还利用率低,系统就开始卡了。

这就是现在嵌入式系统经常遇到的问题:资源有限。物联网的发展带火了嵌入式系统,因为价格便宜,但同时也导致资源有限,不好好用有可能就跑不动了,换高端的又要多花钱,所以需要研究如何更有效的利用资源。动态内存分配就是用来管理分配内存资源的。

如何来管理分配内存呢?其实这就是我的朋友壕怎么管钱的问题。壕的钱太多,所以借钱的人也多,为了记住谁借了多少,壕就要记账,于是他就会有一个账本。比如我之前找他借10块,他给了我100,于是他就会在账本上记上这100已经借出了。借钱的人一多,可能每个人要借的钱有多有少,有的借10000,有的借200,有的借42,各种各样的需求都有。朋友开始一笔一笔按顺序记,后来慢慢发现有不少人每次都借10000,这个人借了10000还回来,那个人正好来借10000,于是不用把这10000放回去了,直接借给那个人更方便,方便了自己管理。于是朋友壕想到了一个办法,规定了借钱的规格,比如借钱只能借10、100、1000、10000,其他的数量都不借,他自己只需要把钱按这个规格提前分好,然后用几个链表来管理就可以了。这就是一种动态分配内存的方法。

碎片

前面说的朋友的这个方法好不好呢?比一笔一笔的顺序记肯定要好多了。但是会有个问题:比如我要借20,按朋友的规格,没有20的,我只能借100,其实浪费了80,这80我也不用,朋友想用却用不上,这就是内部碎片。可以想象,随着长时间的使用,因为每个人的需求各种各样,内部碎片可能会越来越多,造成了整体利用率下降。

前面说了那80是内部碎片,既然有内部碎片,就肯定有外部碎片。外部碎片不太好用钱来举例,因为它涉及到了内存连续的问题。我们知道系统中没有碎片的时候内存都是连续的,假设有三个进程分别申请了相连的1,2,3三块内存,而进程2因为执行完毕,把内存2释放了,此时1和3之间就空出了一块内存,如果这块空出的区域无法满足其他进程申请的需要,那它就只能一直在这空着,造成了浪费,这就是外部碎片

长时间的使用会导致越来越碎片化,那这些碎片怎么解决呢?

对于内部碎片,一个很容易想到的办法就是把借钱的规格分得更细,比如规格可以有1,2,3,4,…,10000,这样借钱的数量只要在这个范围内(我们只考虑借整数元的情况),就不会有内部碎片产生。但是这个代价就是原本只要几个链表就可以管理的,现在需要10000个链表,朋友壕觉得太累了。于是考虑折中的方法,不要分那么多规格,就分一些常用的规格,比如总有人借42块,就定一个42的规格,于是链表数量也不会那么多。但是总有不符合规格的,所以也还是会有碎片,只是碎片不会那么多。这就是Linux内核中slab机制所采取的办法。

对于外部碎片,可以用著名的伙伴算法。其思想是把分配的规格定为2的幂次,即1,2,4,8,16,32,64,128,256,512,1024,2048,…,这样链表的数量不多。用的时候,若要分配内存,就给能满足要求的最小的,比如申请42,就给64,若没有64的,就找128的,拆成2个64的,给一个,留一个;若128的也没有,就继续往上找,以此类推。若找到头若还找不到,则分配失败。释放内存的时候,则看紧邻的内存块是否空闲,若为空闲,则进行合并。因为小块都是大块2分出来的,所以紧邻的一定有一块跟它一样大,就等着合并那一块,合并成一块大的之后还可以再看紧邻的是否空闲,若是可以再合并,以此类推。这就是为什么规格要为2的幂次。这样就不会产生外部碎片了。Linux内核中就采取了这个办法。很明显,这种方式虽然能够完全避免外部碎片的产生,但却产生了内部碎片。所以Linux内核才用了slab机制来优化。

实时

动态内存分配的另一个问题是实时性。比如前面讲的伙伴算法,若是最坏的情况,申请1可能要一直找到2048去,然后要不断拆出来。当然这种情况很少见,所以平均来说效率还不错。对于Linux这种实时性要求不高的系统来说,也就一直用着了。

但对于一起实时嵌入式系统来说,实时性的要求就高得多,举个没那么恰当的例子,比如刹车系统平均响应时间是0.1s,但最坏情况下可能要2s,这种刹车你敢用吗?实时系统需要有可预期的时间保证,必须要保证在最坏的情况下多少时间内操作要完成。我们要说的TLSF就可以保证其最坏执行(分配、释放)时间是 O ( 1 ) O(1) O(1) 的。

TLSF (Two-Level Segregate Fit)

终于说到TLSF了。TLSF号称实现了三大目标:实时性(可预期的时间保证)、执行速度快、利用率高(碎片少)。怎么实现的呢?结合下图来说。

tlsf

在划分的规格上,TLSF改进了伙伴算法,它分了两层,第一层(图中First Level)跟伙伴算法一样,也是采用2的幂次,但这样很容易产生很多内部碎片,所以TLSF进行了第二层(图中Second Level)划分,比如64这一级规格,再细分为8个区间,64-71,72-79,80-87,88-95,96-103,104-111,112-119,120-127,这样虽然不能完全没有碎片,但碎片可以尽量小,同时也尽量不会浪费内存,保证了内存的利用率。

为了方便管理,对每一层都用位图来表示相应的规格是否有空闲块,每种规格的空闲块都用一个链表来管理。相关结构体代码如下,其中fl_bitmap和sl_bitmap分别是第一层和第二层位图,matrix是所有规格的链表。

typedef struct TLSF_struct { 
   
    /* the TLSF's structure signature */
    u32_t tlsf_signature;

#if TLSF_USE_LOCKS
    TLSF_MLOCK_T lock;
#endif

#if TLSF_STATISTIC
    /* These can not be calculated outside tlsf because we * do not know the sizes when freeing/reallocing memory. */
    size_t used_size;
    size_t max_size;
#endif

    /* A linked list holding all the existing areas */
    area_info_t *area_head;

    /* the first-level bitmap */
    /* This array should have a size of REAL_FLI bits */
    u32_t fl_bitmap;

    /* the second-level bitmap */
    u32_t sl_bitmap[REAL_FLI];

    bhdr_t *matrix[REAL_FLI][MAX_SLI];
} tlsf_t;

申请内存

申请内存的时候用如下malloc_ex函数。先调整要申请的内存大小size,然后通过MAPPING_SEARCH找到对应这个size的位图的位置索引,再调用FIND_SUITABLE_BLOCK去找到可用的合适的内存块。这里FIND_SUITABLE_BLOCK中会先在size对应的那个链表去找看是否有空闲的,若找不到就到比size大的那些链表中去找,一般都会找到有空的,找不到则返回空指针。malloc_ex中找到空闲块之后就获取它的信息,看它是否太大以至于需要分割,若需要分割就分割一下,把多的做成一个空闲块放到该放的链表中;若不需分割就标记一下并返回。

void *malloc_ex(size_t size, void *mem_pool)
{ 
   
    tlsf_t *tlsf = (tlsf_t *) mem_pool;
    bhdr_t *b, *b2, *next_b;
    int fl, sl;
    size_t tmp_size;

    size = (size < MIN_BLOCK_SIZE) ? MIN_BLOCK_SIZE : ROUNDUP_SIZE(size);

    /* Rounding up the requested size and calculating fl and sl */
    MAPPING_SEARCH(&size, &fl, &sl);

    /* Searching a free block, recall that this function changes the values of fl and sl, so they are not longer valid when the function fails */
    b = FIND_SUITABLE_BLOCK(tlsf, &fl, &sl);
    if (!b)
        return NULL;            /* Not found */

    EXTRACT_BLOCK_HDR(b, tlsf, fl, sl);

    /*-- found: */
    next_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
    /* Should the block be split? */
    tmp_size = (b->size & BLOCK_SIZE) - size;
    if (tmp_size >= sizeof(bhdr_t)) { 
   
        tmp_size -= BHDR_OVERHEAD;
        b2 = GET_NEXT_BLOCK(b->ptr.buffer, size);
        b2->size = tmp_size | FREE_BLOCK | PREV_USED;
        next_b->prev_hdr = b2;
        MAPPING_INSERT(tmp_size, &fl, &sl);
        INSERT_BLOCK(b2, tlsf, fl, sl);

        b->size = size | (b->size & PREV_STATE);
    } else { 
   
        next_b->size &= (~PREV_FREE);
        b->size &= (~FREE_BLOCK);       /* Now it's used */
    }

    TLSF_ADD_SIZE(tlsf, b);

    return (void *) b->ptr.buffer;
}
static __inline__ bhdr_t *FIND_SUITABLE_BLOCK(tlsf_t * _tlsf, int *_fl, int *_sl)
{ 
   
    u32_t _tmp = _tlsf->sl_bitmap[*_fl] & (~0 << *_sl);
    bhdr_t *_b = NULL;

    if (_tmp) { 
    //找到空闲的了
        *_sl = ls_bit(_tmp);
        _b = _tlsf->matrix[*_fl][*_sl];
    } else { 
     //没找到空闲的
        *_fl = ls_bit(_tlsf->fl_bitmap & (~0 << (*_fl + 1))); //找比其大的有空闲的最小的
        if (*_fl > 0) { 
            /* likely 一般都能找到*/
            *_sl = ls_bit(_tlsf->sl_bitmap[*_fl]);
            _b = _tlsf->matrix[*_fl][*_sl];
        }
    }
    return _b;
}

释放内存

释放内存的时候用如下free_ex函数。首先更新待释放的内存块的状态,然后查找其下一个块是否也是空闲,若是则将两块合并成一个大块;再查找其前一块是否是空闲的,若是则与前一块也合并;根据情况合并前后内存块之后,将自身插入到对应的空闲链表中,并更新下一块的相应标志。

void free_ex(void *ptr, void *mem_pool)
{ 
   
    tlsf_t *tlsf = (tlsf_t *) mem_pool;
    bhdr_t *b, *tmp_b;
    int fl = 0, sl = 0;

    if (!ptr) { 
   
        return;
    }
    b = (bhdr_t *) ((char *) ptr - BHDR_OVERHEAD);
    b->size |= FREE_BLOCK;

    TLSF_REMOVE_SIZE(tlsf, b);

    b->ptr.free_ptr.prev = NULL;
    b->ptr.free_ptr.next = NULL;
    /* 查找其下一个块是否是空闲,若是则合并 */
    tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
    if (tmp_b->size & FREE_BLOCK) { 
   
        MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
        EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
        b->size += (tmp_b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
    }
    /* 查找其前一个块是否是空闲,若是则合并 */
    if (b->size & PREV_FREE) { 
   
        tmp_b = b->prev_hdr;
        MAPPING_INSERT(tmp_b->size & BLOCK_SIZE, &fl, &sl);
        EXTRACT_BLOCK(tmp_b, tlsf, fl, sl);
        tmp_b->size += (b->size & BLOCK_SIZE) + BHDR_OVERHEAD;
        b = tmp_b;
    }
    MAPPING_INSERT(b->size & BLOCK_SIZE, &fl, &sl);
    INSERT_BLOCK(b, tlsf, fl, sl);

    /* 更新下一块的相应标志 */
    tmp_b = GET_NEXT_BLOCK(b->ptr.buffer, b->size & BLOCK_SIZE);
    tmp_b->size |= PREV_FREE;
    tmp_b->prev_hdr = b;
}

分析

从代码可以看出,申请和释放内存的过程中没有任何循环,所以其时间复杂度为 O ( 1 ) O(1) O(1),有实时性的保证。而执行过程,因为没有循环,正常都挺快的。至于内存利用率,主要取决于第二层又细分了多少级,比如若分了8级,最坏情况下利用率也高于7/8。

需要源码的同学可以去 http://www.gii.upv.es/tlsf/ 自行下载。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/22476.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信