1、Linux 系统中SLAB 分配器内存回收算法分析和优化摘 要：SLAB 分配器在linux 系统中的使用大大提高了内核中分配内存对象的效率，并且解决了小对象分配内存时产生的内存碎片问题。而该分配器的“内存回收算法”更是保证了其内核空间的充分利用。本文首先简单地介绍了slab 分配器的总体结构及其与“内存回收算法”息息相关的关键数据结构，然后详细地描述了“内存回收算法”的具体机制，最后对该算法提出了优化策略并给出了其统计数据及仿真结果。关键词：SLAB 分配器；内存回收；优化策略中图分类号：TP316.811引言“内存回收”，又名“内存垃圾回收”，是操作系统内存管理中最重要的组成部分之一，而S
2、LAB 分配器管理的是linux 系统中宝贵的内核空间，因此其中的“内存回收”对内核空间的充分利用起着举足轻重的作用，但目前并没有介绍有关SLAB 分配器“内存回收”的学术论文。故本文在就linux 2.26.25 部分源代码进行细致分析后，对SLAB 分配器的“内存回收”进行了详细的分析与优化工作。2SLAB 分配器的关键数据结构SLAB 分配器4的总体结构如图1 所示，主要分为三层结构：高速缓存、slab、对象。其中，高速缓存是用来缓存某种特定内核变量的缓冲区；slab 则是高速缓存中的一个个大小固定的内存分区；对象是slab 中的一个个大小固定的小内存块，是存储变量的单位。SLAB分配器
3、通过将已经释放的对象缓存在高速缓存区中，而不是真正地释放回内存中，大大提高了LINUX 系统内核空间中“分配对象”的效率。- 2 -cache_chainslabs_partialslabs_fullslabs_free slabslabslab objmem/objsslabpointer/objsobjs pointerslabcpu图1 SLAB 分配器总体结构图2.1 l 3 链表如图1 所示，每个高速缓存包含slabs_free，slabs_partial，slabs_full 三个链表，本文将其称为“l3 链表”2。每个链表的后面都链接着多个slab，并标志着其属下slab 分区的
4、状态。当某slab 分区处于部分空闲状态（部分对象在使用，部分对象未使用）时，其将会被加入到slabs_partial 链表中；当某slab 分区处于全滿状态（所有对象全部被使用）时，其将会被加入到slabs_full 链表中；当某slab 分区处于空闲状态（所有对象全部未使用）时，其将会被加入到slabs_free 链表中。显然，一个新的对象申请到达时，slab_partial 链表中首个slab 分区的对象会被优先考虑，只有当slab_partial 链表中不存在任何slab 分区时，slabs_free 链表中的slab 分区才会被考虑；而一个对象使用完毕释放时，它将被释放回其原属sla
5、b 中。在申请或释放的过程中，如果一个slab 分区的状态（空闲状态、部分空闲状态、全滿状态）发生改变的话，必须将其从原先的链表转移到新的链表中。由于该slabs_free 链表中的所有slab 分区均处于空闲状态，“内存回收算法”可以方便从该链表中销毁其中的slab 分区来节省内存。2.2 空闲对象指针队列每当从slab 分区中取出或还回一个对象时，会有两项动作：第一，更新空闲对象索引表注1。第二，如果该slab 分区的状态发生了变化，还得将其从一个链表队列转移到另一个链表队列。显然这是非常费劲的。为了提高slab 分配器取还对象的效率，SLAB 分配器提出了一个概念：“空闲对象指针队列”1
6、，通过一次性的从多个slab 分区中取出大批对象，此时完成更新空闲对象索引表、转移队列的工作，并将这些对象的指针存放在“空闲对象指针队列”中。通过该方法在以后每- 3 -次取或还对象时，都可以直接操作“空闲对象指针队列”，从而大大提高效率。“空闲对象指针队列”包含三个部分：“每cpu 空闲对象指针队列”、“共享空闲对象指针队列”、“每节点空闲对象指针队列”。它们在取对象或还对象的时候扮演着重要角色，而这方面由于不是本文的重点，不作介绍。这三部分能存放指针的最大容量如下表所示，它们与对象的大小（size）有关，其中，ac-limit 表示“每cpu1空闲对象指针队列”的容量、share-limi
7、t表示“共享空闲对象指针队列” 的容量、alien-limit 表示“每节点空闲对象指针队列” 的容量。表1 “空闲对象指针队列”容量对象的大小范围 ac-limit share-limit alien-limitsize=256 120 480 12256size=1024 54 216 121024size=4096 24 0 124096size=131072 8 0 12131072size 1 0 1从表1 可以看出， 对某些高速缓存来说，三个“空闲对象指针队列”，特别是“每cpu 空闲对象指针队列”和“共享空闲对象指针队列” 容量巨大，如果该高速缓存使用不太频繁，但“空闲对象指针队
8、列”中又存放大量空闲对象指针，这会是一笔巨大的内存浪费。SLAB 分配器的“内存回收算法”会对这一情况进行处理。注1每个slab 分区都对应一张“空闲对象索引表”，通过该表，可用来查找该slab 分区中空闲对象。取对象时，从“空闲对象索引表”中检索出当前空闲对象，然后更新该表，以标志该对象已被使用。释放对象时，也要更新该表，以标志该对象空闲。3内存回收算法3.1 算法介绍随着SLAB 机制5在内核中的使用，频繁的对象申请会使得高速缓存中的slab 的数目越来越多，缓存区的空间会越来越大。而还回去的那部分对象也只是还到在其所属的“slab分区”中，并没有被真正的“释放”，故内存将会被耗尽。因此S
9、LAB 分配器需要合适的内存回收算法来回收高速缓存中部分无用的“slab 分区”，将其真正地释放。SLAB 分配将“内存回收”作内核中的一个工作任务，挂接着内核预定义的事件工作队器列调度器（scheduler）队列keventd_wq3，由内核中专门的内核线程eventd 去完成这个队列中的所有工作任务。内核线程eventd 首先循环遍历cache_chain 链表中的所有高速缓存，并对满足“回收条件”的各个高速缓存进行空闲页框回收。每完成一次这样的“内存回收”，或在试图完成“内存回收”时获取内核锁失败时，就延迟2s 后，再将该“内存回收”工作挂接到调度工作队列keventd_wq 中再次被调
10、度。其中“回收条件”有两个：1、该高速缓存已经达到了“回收时间reap_time”。该值为4 秒，即该高速缓存上次的“内存回收”与本次“内存回收”至少要事隔4s。2、该高速缓存中的“免回收标志位free_touch”没有置位。当某高速缓存中的空闲对象不够用时，其“免回收标志位free_touch”会被置位，此时，不需要对该高速缓存进行“内存回收”，否则就要进行内存回收。“内存回收”算法流程图6如图2 所示，具体描述如下：- 4 -1、清空“每节点空闲对象指针队列”中所有空闲对象指针，清理“本地空闲对象指针队列”和“共享空闲对象指针队列”中tofree 个空闲对象指针；将这些指针对应的对象释放回
11、其所属slab 中，这是为了保证尽可能多产生全空闲状态的slab 分区，从而达到最大程度的内存回收。其中，tofree 的值是根据经验公式所得：(lim 4) / 5 (lim 4) / 5( 1)/2 (lim 4)/5it avail ittofreeavail avail it + += + limit 的值加1 后除2 的结果。- 5 -开始结束获取内核锁cache_chain_mutex是否成功延时2s将任务挂载到工作队列keventd_wq中，等待此任务下一次执行循环遍历cache_chain链表，找到下一个高速缓存清空其每节点区空闲对象指针队列，清理其本地空闲对象指针队列中部分指针jiffiesreap_time清理其共享空闲对象指针队列中部分指针查看free_touched标志是否置位从slabs_free队列中销毁nr_free个slab是否遍历完cache_chain链表释放内核锁cache_chain_mutex清除free_touched标志否是是否否否是是查看高速缓存中的reap_time将reap_time定为从现在起4s图2 内存回收算法流程图3.2 算法优化从3.