Segment 虽然提升了内存空间的利用率,但是也造成了内存空间的碎片化。各个 segment 分布在内存的不同位置,使内存管理变得更加复杂。这一章就是为了解决这个问题。

+----------+----------+----------+
|   free   |   used   |   free   |
+----------+----------+----------+
0          10         20         30

像上面这个图一样,这一块内存中,有 20 字节是空闲的,但是由于中间的十字节被分配了,导致这 20 字节被分成了两个 10 字节的空间而不连续。如果一个程序请求 15 字节的空间,即使这里有 20 字节的空闲空间,也无法分配。

空闲链表

一个解决的办法是维护一个空闲链表,这个链表记录着内存中所有的空闲的地址空间,每一个节点记录着空闲的区块的大小,和下一个区块的地址。

typedef struct __node_t {
    int size;
    struct __node_t *next;
} node_t;

allocator 的任务

  1. 拆分和合并内存空间。假定一个进程请求的地址空间的大小比 allocator 选定的内存空间要小,allocator 就需要将这块连续的空间拆分,一部分用于满足请求,另一部分作为空闲的空间重新插入到空闲链表中。当进程用完了 free 了之后,需要识别前后的是否和空闲空间相邻,如果相邻,要组合成一个连续的空间重新加入到空闲链表中。

  2. 进程申请的空间分配后,需要之后分配的空间的具体的大小。可以发现,free 函数是没有传入具体的内存大小的。

内存分配的策略

Best Fit

最佳适应算法。这个算法将空闲链表遍历一遍,找出一个可以分配且空间时最小的内存分配给进程。虽然这么做看起来是最优的,但实际上,会让内存中产生很多小空间,这些小空间,大多不能满足进程的需求,所以这也是另一种浪费。同时,这种分配方法,需要完整地遍历一遍空闲链表,这也是一个非常大的开销。

Worst Fit

最坏适应算法。这个算法同样是将空闲链表遍历一遍,只不过和 Best Fit 不同的是,它选择的是最大的空闲内存进行分配。这样的好处是,不会产生大量的小空闲空间。但是这样做也有缺陷,一个是可能没有办法未来产生的大地址空间的请求,因为大的空闲内存已经分配了。同时,它也需要完整地便利一遍空闲链表。

First Fit

第一次适应算法。这个算法,选取的第一个遍历到的满足请求的空闲内存。这样做的好处是,减少的遍历带来的开销。但是,这样会让低地址出现许多的小内存碎片。

Next Fit

下一次适应算法。这个算法,记录了上一次分配的空间,进行内存分配时,从上一次的节点开始遍历,像 First Fit 一样找到第一个满足需求的空间。这样做的好处,一个是不会让低地址出现大量的小内存碎片,也不可以避免遍历带来的开销。

独立的链表

这是另一方式。在计算机运行的过程中,有一些内存的大小被申请的次数非常多。由于定长的内存分配是非常容易的,内核就将这些常用的大小单独组成一个链表,以供使用。

伙伴分配器 (Buddy Allocation)

这个名字很有趣。这个分配是递归地将空闲空间分成两份,直到适合请求的内存大小时,将低地址的内存分配给进程。当释放时,可以直接将它们合并。这里方便的对释放内存的合并操作。