空闲内存管理

这是 《Operating System: Three Easy Pieces》 的第 6 篇读书笔记。

上篇笔记 介绍了管理内存的一种方式:分段式内存管理,它可以更灵活的分配和管理内存。

本章将讨论内存管理中另一个相当基础的部分——空闲内存的管理,无论是 glibc 的 malloc 库,还是操作系统自身。

当内存切片都是固定大小的时候,分配会比较简单些,只要保存一个数组就好了。

当切片大小不固定的时候,空闲内存的管理就变得复杂了。

外部碎片问题

如上图所示,整个空闲的可用空间有 20 字节,它被分为 10 字节一段,但不幸的是,一个 15 字节的内存申请请求会被拒绝,因为基于我们之前的策略,无法利用起这"碎片化"的 20 字节空间。

本节就重点来解决这个问题。

从假设开始

我们的讨论主要集中在用户态空间的内存分配。

void* malloc(size_t size)

函数的参数是一个指明所需内存大小的 size, 返回一个指向已配备内存起始地址的 void 指针。

与之对应的

void free(void* ptr)

函数的参数是一个指针,它会释放指针所指向的内存。函数的签名暗示我们,当释放的内存的时候,free() 函数并没有表明要释放多少内存的参数。因此,库 (指 提供 malloc()free() 函数的库)必须能够知道多大的内存被处理掉。

库管理的内存历史上被称作 堆( heap )。通常使用的管理空闲内存的数据结构是 空闲链表( free list )。这种数据结构包含了指向所管理的空闲内存块的引用。

当一块内存申请成功、被交给用户使用,这块内存实际上被用户所有了,它不能被库自动释放,除非用户程序自动调用 free() 函数。因此,如果寄希望于库会合并压缩( compaction )空闲内存来解决外部碎片问题是不可能的,虽然这是一种有效的办法。

当然啦,在分片的时候,使用压缩合并内存来减少外部碎片问题这一方式还是可以的,这点后面再讨论。

我们假设内存分配器( Allocator )管理着连续的内存区域,在某些情景下,分配器可以使得所管理的内存区域变大。比如说,一个工作在用户态的内存分配库在已申请内存不足的时候,可能会向通过 sbrk() 系统调用向内核申请堆的扩容。

为了简单起见,我们假设这块连续内存区域是固定大小的。

底层的工作机制

我们首先介绍一下大部分分配器的工作机制,讲解下它是如何跟踪所管理内存的大小以及跟踪它何时被申请、何时被释放。

切分与合并

空闲链表维护的元素其实也是在堆中的。

假设当前我们管理着下面的堆:

维护这个堆的分配情况的空闲链表里有两个元素,一个元素描述了第一个 10 字节的分段(0-9字节),另一个元素描述了另一个空闲分段(20-29字节)。

如前所述,一个超过 10 字节的内存申请会失败,那是因为没有连续的内存可供分配了。

如果刚好是 10 字节的内存申请那可以满足,但是,如果申请的内存比 10 字节小呢?

假设我们要申请一个字节的内存,这种情况下,分配器会进行 切分 动作——如果分配器找到一个空闲内存满足了内存申请的要求,它会把这块内存一分为二,第一块内存的起始地址就返回给调用者,第二块内存会继续留在空闲链表里。因此,空闲链表将变为下面这样:

上图的空闲链表中,与上上图不同的仅仅是第二个元素的起始地址从 21 字节处开始,大小是 9 字节而不是 10 字节了。

还是一开始的那个内存堆内存分配情况,如果此时调用 free(10),会发生什么呢?——分配器会合并空闲的内存,像下图那样子:

跟踪已分配空间的大小

在第二大节中,我们遗留了一个问题,free() 函数并没有参数指明多少内存需要释放,那么库是如何知晓的呢?

当然是使用额外的内存来跟踪这些信息啦。

大部分分配器的做法是保留一小部分额外的头部信息在已分配的内存块中。如下图:

对应的结构体应该就是这样:

typedef struct __header_t {
    int size;
    int magic;
} header_t;

当用户调用 free(ptr) 时候,库就进行简单的指针运算找到真正的 header 在哪里:

void free(void *ptr) {
    header_t *hptr = (void *)ptr - sizeof(header_t);
}

还有一个魔法数( magic ) 通常是用来做安全校验的。

深入空闲链表

假如我们有一块 4 KB 的内存要管理,如何初始化对应的空闲链表呢?刚开始的时候,空闲链表只有一个元素,元素的 size 应该是 4096(减去头部字节之后)。

它应当有如下的结构:

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

下面是具体的逻辑伪代码:

// mmap() returns a pointer to a chunk of free space
node_t* head = mmap(NULL, 4096, PROT_READ|PROT_WRITE,
                    MAP_ANON|MAP_PRIVATE, -1, 0);
head->size   = 4096 - sizeof(node_t);
head->next   = NULL;

在运行完上面代码之后,空闲链表里就有了一个元素,其 size 成员的值为 4088;head 指针指向这段地址的起始处,基本上如 Figure-17.3 所示:

下面,我们想要申请 100 字节。为了满足需求,库会搜索空闲链表,找到一块满足需求的内存;因为此时只有一块,大小是 4088,足以满足需求了,接下来就会进行 切分 动作。这时候地址空间如下图 Figure-17.4 所示:

为了满足 100 字节的内存申请,库实际从空闲链表里分配了 108 字节(8 字节的头部信息)。并把相应的空闲链表元素的 size 设置为 3980( 4088 - 108 )。

接下来我们看下连续的 100 字节申请之后,虚拟内存的堆空间变成了什么样子。

堆最开始的 324 字节是被分配了的,但是空闲链表依旧只有一个元素,由 head 指针指向,挺无聊的。

以上图为例,调用 free(16500)(the value 16500 is arrived upon by adding the start of the memory region, 16384, to the 108 of the previous chunk and the 8 bytes of the header for this chunk),这个值是由图中的 sptr 所指向的。

库会马上通过传入的指针 sptr 发现要释放的内存大小,然后把这块内存加入空闲内存列表中。完成这一系列的动作之后,内存空间如下图:

现在我们的空闲链表有了两个元素了,一个代表 100 字节的小块内存,一个代表 3764 字节的大块内存。也终于,空闲内存被切分成不等的分片了。如下图:

我们的最后一个例子是合并,当剩下的不空闲归还库的时候,库就会遍历空闲链表,合并链表中地址相邻的元素,最终堆的情况会如开始的一样。

堆的增长

大多数传统的分配器会先申请小块的堆内存,当用完了之后它会想 OS 请求很多的内存。在 Unix 系列的系统中通常是 sbrk() 系统调用。之后 OS 会茶盅可用的物理内存页,然后把它映射( map )到进程的虚拟地址空间中,这样内存的申请就得到了访问。

基本的策略

通常查找一些可用的内存通常有以下几种策略:

  • Bset Fit
  • Worst Fit
  • First Fit
  • Next Fit

比较简单,顾名思义就可以看出他们是如何工作的。

伙伴分配器

伙伴分配器即采用伙伴算法实现的分配器。

使用这个分配器的系统会把空闲内存的大小看成是 2 的 N 次方。当有内存申请请求时,分配器会递归地搜索空闲的内存,*它把内存一分为等份的俩份*,直到满足申请空间大小的最小空间被找到。

下图是 64 KB 的空闲堆,申请一个 7 KB 的内存:

最下角的 8 KB 空闲内存将会被分配使用。

伙伴分配器的美妙之处在于内存被释放的时候。

当把 8 KB 的内存归还到空闲链表时,分配器会检查它的 “伙伴”,也是 8 KB 内存大小的内存是否空闲,如果是,就合并两个空闲的内存块,成为一个 16 KB 的空闲内存。这个过程会一直递归像上的进行直到到达堆顶。

伙伴分配器之所以工作地比较好在于它简单的选择了和它一起合并的 ”伙伴“。伙伴之间的地址差值用二进制表示时仅差一个比特位。

更详细的请参见论文 《Dynamic Storage Allocation: A Survey and Critical Review》

这里还有一篇关于 glibc 中 malloc() 函数介绍的 文章

参考
《 Fact Segmentation 》
《 Program Organization and Record Keeping for Dynamic Storage 》
《 Virtual Memory Management in the VAX/VMS Operating System 》
http://pages.cs.wisc.edu/~remzi/OSTEP/vm-segmentation.pdf

Comments
Write a Comment