《基于Linux的C编程与内核导读》连载（16）

4.1.3 linux对内存空间的分配与回收

1、数据结构

系统中有许多对物理页的请求。例如，当一个映像被装载入内存时操作系统需要分配页。当映像结束执行并卸载时这些页又将被释放。物理页的另一个使用是保存内核专用的数据结构，比如页表本身。用来进行页分配和回收的机制和数据结构或许是维持虚拟内存子系统高效的最关键的一点。

系统中所有物理页都用mem_map 数据结构描述，它是一个在启动时被初始化的mem_map_t结构的列表。每个mem_map_t，描述系统中一个物理页。一些重要的字段有：

•count 本页使用者计数。当该页被许多进程共享时计数将大于1。

•age 描述本页的年龄，用来判断该页是否为淘汰或交换的好的候选。

•map_nr 记录此men_map_t描述的物理页的页帧号。

    系统使用free_area数组管理整个缓冲，实现分配和释放页面。free_area的每个元素包含页块的信息。数组中第一个元素描述一页，下一个描述两页的一块，再下一个描述4页的一块，依此以2的幂增长。List元素用作一个队列头并含有指向mem _map数组中page数据结构的指针，空闲的页块在这里排成队列。map是指向一个位图的指针，该位图跟踪被分配的该大小的页组。如果第几个块空闲，则位图中第几位将被置位N。图4-4 展示了free_area结构。元素0有一个空闲页(页帧号0)，而元素2有两个空闲的4页块，第一个开始于页帧号4而第二个开始于页帧号56。

图4-4 free-area的数据结构 

2、页面分配

Linux使用Buddy算法来高效地分配和回收页块。页分配代码试图分配一个或多个物理页的一块。页面分配是以2的幂大小的块来进行，这意味着它可能分配1页块、2页块、4页块等。只要系统中有足够的空间页来满足请求(nr_free_pages> min_free_pages)，分配代码将搜索free_area来寻找请求大小的一个页块。例如，数组中元素2有一个内存映射来描述系统中4页长的块的空闲和分配。

分配算法首先搜索请求大小的页块。它沿free_area中list元素处排成队列的空闲页面链进行。如果没有所请求大小的页块是空闲的，下一个大小的块(两倍于所请求的大小)将被查找，这个过程一直进行到free_area整个被检查过或找到一个页块。若找到的页块比请求的大，则它必须被分开直到得到合适大小的一块。因为块大小都是2的幂，所以分块的过程很容易，只需把块等分。空闲的块排到合适的队列中，被分配的块返回给调用者。

例如，图4-4中如果一个2页块被请求，第一个4页块(开始于页帧号4 )将被分成两个2页块。第一个，也就是开始于页帧号4的将被作为分配的页返回给调用者；而第二块，开始于页帧号6，将作为空闲的2页块排进free_area数组的元素1的队列中。

3、页面回收

页块的分配可能会把内存分段，把大的空闲页块分开成小的。而页回收代码在可能的时候把页重新组合成大的空闲页块。事实上页块大小很重要，因为它使得可以容易地把块组合成更大的块。

当一个页块被释放时，将检查相邻的或称伙伴的同样大小的块是否空闲。如果是，它和新释放的页块被组合在一起形成一个新的下一个大小的空闲页块。每次两个页块被组合成更大的空闲页块时，页回收代码将试图再将该块组合成还要大的块。这样，空闲页块可以任意大，只要内存使用允许。

    例如在图4-4中，如果页帧号1被释放，那它将和已经空闲的页帧号0组合起来，并作为2页空闲块排进free_area的元素1的队列中。