内核内存管理

4.6　内核内存管理

通过4.5节的讨论我们发现，用页面分配器来分配内存时是以页为最小的单位，虽然对内核管理系统物理内存比较方便，但是由于内核自身在运行过程中需要大量而频繁地使用内存，如文件描述符，进程描述符，虚拟内存区域描述符等。内核这些内存有以下特点：不参与交换；使用时间较短；要求动态分配和回收；响应时间要快，尺寸很小，往往远小于一页的内存块。因此Linux采用了一套独立的机制来实现更细粒度的内存管理。

目前几种典型的内核内存分配方法如下：

（1）简单2次幂空闲表

它把内存分成不同的2的n次方大小（32，64，128……1024bytes）的块来管理。不过分配器保留这些块的最前面几个byte当做header，所以可供分配的空间略小于2的n次方。当这块内存不用时（free），header会指向下一个free的块，它们连接成一个list。而使用中块的header，也指向他所属的list。分配方法有个很大的缺点就是如果申请2的n次方的内存，要用2的n+1次方的块来存放，造成空间的大量浪费。

（2）Mckusic-Karels分配器

此方法是简单2次幂方法的改进。它把一段连续的内存都切成固定的大小，比如说32bytes，这样使用中的header就不用指出他所属的list了，因为由他的位置kernel就可以知道它属于谁。

（3）Buddy System

Buddy System是另外一种配置法，它也是以2的n次方作为分配内存大小的单位。优点是free()之后的相邻空间可以再聚集起来形成较大的可用内存空间，使得内核占用的内存空间可以动态地调整。上面两种方法在这方面做得不好。但是，由于每次回收内存都想把相邻空间合并，所以时间开销很大。

（4）Lazy Buddy

Lazy Buddy是修改后的buddy算法，用来分配内核事务。相对于Buddy System算法，它提高了free()时的性能，提高了硬件缓存的利用率。

（5）Zone分配器

Zone分配器配置法，不再以2的n次方作为单位来分配。它从页面分配器申请一块内存，把它按照对象的大小分成n份，把给一种对象的内存称为一个Zone。不同的对象使用不同的zone,不管它们的大小是否一样。

（6）Slab分配器

Slab分配器配置法和Zone分配器方法差不多，都以对象的大小作为分配内存的单位。它出现在20世纪90年代前期。Sun的工程师提出在Solaris2.4采用Slab分配算法，Linux 2.2.0以后的版本采用了这种全新的Slab分配器分配机制，从而拥有了更加快速的分配性能，有效地提高了的内存利用率，更细粒度地划分内存，进一步地考虑到机器缓存的利用率和总线的平衡。

Slab分配器的核心思想就是“缓冲池”的运用。在Slab分配器中，小内存块被看做对象，当使用完后，并不直接释放而是暂时存到“缓冲池”中，以备再次使用。这样有效地避免了频繁生成、频繁销毁带来的开销。

Slab分配器将按不同对象分类，同类中按照次序排成队列。而且同种的对象有相同的大小，所以回收再分配时，也是占用同样大小的空间，这样在对象这个粒度上，碎片问题不存在了。如果同类对象使用得越多，空间利用率越高。另外，由于这种排列使得获得对象位置变得简单，避免了访问多个对象增加定位时间。这个想法产生于Mckusick-Karels算法，被Zone算法继承。

与其他许多算法不同，在Slab分配器中，对象析构后，它的内存并不是立即回收，而是在一定的时间里保留这些对象的结构，这样便于对象复用。对象复用是Slab算法的基本特点。这个思想基于以下两方面：

（1）某些对象析构以前，已经回到了初始化的状态。例：一个链表的表头，在它析构前，链表中的其他节点一般都已经释放了，此时表头已经回到了初始状态（比如指针指向自己或者NULL）。

（2）同一类型的对象的初始状态都是一样的，不会因对象不同而改变。所以对于一个对象使用完毕后，并不是马上析构，而是等下一个同类型的对象来使用。这样后来的对象可以利用已经初始化的数据结构，从而节省了分配、构造、析构、回收的开销。

内核把分配器分配的各种内存块看做各式各样的临时对象，分配器对一个对象的操作顺序如下：

（1）分配内存。

（2）初始化对象。

（3）使用对象。

（4）析构对象。

（5）释放对象。

这样取消了重复的初始化、析构对象操作，大大提高了分配器性能。

基于Slab的内存管理器，基本的概念是Cache和Slab，其数目比如下所示：

Cache:Slab = 1:n

Slab:内存块= 1:n

Slab分配器由若干个Cache构成。每个Cache管理一个特定类型的对象。每个Cache由若干个Slab组成。这也是Slab分配器名字的由来。每个Slab是由若干个页面组成的页块。页块被分成许多的对象。图4-9是Slab分配器物理结构示意图。

图4-9　Slab分配器物理结构示意图

以上是基本的物理结构。逻辑上来看，是Cache-Slab-Object分配，每个Slab就是某种类型的多个对象的空间，由多个页面搭建的空间。

每个Cache包含一个Slab链表，kmem_cache_s中的成员变量c_firstp，c_lastp分别指向Slab链表的第一项和最后一项。一个Cache的所有Slab通过指针连成一个队列，这些Slab的排列一直保持一个固定的格局，也就是队列的前面部分是被填满的Slab，中间是部分满的Slab，后面是全部为空的Slab。

Cache描述符中有一个指针，指向第一个不满的Slab。这个Slab可能是部分满的，也可能是全空的。当它指向描述符本身的时候，说明此时Slab已经全满了。在Slab是否满的状态发生变化时，Cache会自动调整它的位置，保证保持上面队列的格局不变。例：当一个部分满的Slab最后一个使用的对象被设置为不使用时，它处于全空的状态，所以它将被调整到全空的Slab部分中。当一个满的Slab的某一个对象被设置为不使用时，它将被插到队列中不满的Slab部分中去。

当分配一个新的对象时，Cache首先通过firstnotfull找到它的第一个不满的Slab，再进行分配。如果此时Cache的alloc_new_slab指针指向Cache，则表示Cache中已经没有不满的Slab了，则向页面级分配器申请一个页块，然后初始化为一个Slab。

在回收对象后，该对象所在的Slab不管是否变成空，都不用回收该Slab所占用的页面分配器。这正是Slab分配器的高效所在。

Slab分配器算法有两种回收Slab的方式：

一种是回收某个特定Cache所有全空的Slab，直到由用户又在该Cache分配新的Slab为止（keme_cache_shrink）。

一种是对所有的Cache采用时钟算法，每次选择一个比较合适的Cache，回收它部分的空的Slab（keme_cache_reap）。

由于同一个Slab中的所有对象都是属于同类的，Slab中的对象链成链表。一个Slab通过自己的kmem_bufctl_t数组，来管理它的空闲对象；这个数组的元素和该Slab中的对象是一一对应的。

Linux定义结构kemem_slab_s管理Slab链表。kemem_slab_s的成员变量s_prevp，s_nextp指向keme_slab_s结构的前驱和后继。

Slab的尺寸大小一般是由内核根据Slab中对象的大小来决定。对象分为大对象和小对象。小对象，是指一个页帧中可以容纳8个以上对象。反之，则为大对象。Slab分配器针对大对象和小对象使用不同的技术。

除了Slab的管理结构kemem_slab_s之外，缓存还为每个对象分配一个对象管理结构Kemem_bufctl_s。该对象管理结构存放在名为c_index_cache缓存中。