《操作系统导论》阅读笔记(十四)空闲空间管理

/ 0评 / 0

阅读笔记主要来自原书第 17 章。该章对内存的空闲空间管理进行了详细的介绍。

0、前言

本章讨论所有内存管理系统的一个基本方面,无论是 malloc 库(管理进程中堆的页),还是操作系统本身(管理进程的地址空间)。具体来说,会讨论空闲空间管理的一些问题。

让问题更明确一点。如果需要管理的空间被划分为固定大小的单元,就很容易。在这种情况下,只需要维护这些大小固定的单元的链表,如果有请求,就返回链表中的第一项。

如果要管理的空闲空间由大小不同的单元构成,管理就变得困难。这种情况出现在用户级的内存分配库(如 malloc() 和 free()),或者操作系统用分段的方式实现虚拟内存。在这两种情况下,出现了外部碎片的问题:空闲空间被分割成不同大小的小块,成为碎片,后续的请求可能失败,因为没有一块足够大的连续空闲空间,即使这时总的空闲空间超出了请求的大小。

上图展示了该问题的一个例子。在这个例子中,全部可用空闲空间是 20 字节,但被切成两个 10 字节大小的碎片,导致一个 15 字节的分配请求失败。所以本章需要解决的问题是:

要满足变长的分配请求,应该如何管理空闲空间?什么策略可以让碎片最小化?不同方法的时间和空间开销如何?

1、假设

本章的大多数讨论,将聚焦于用户级内存分配库中分配程序的辉煌历史。

假定基本的接口就像 malloc() 和 free() 提供的那样。具体来说,void * malloc(size t size) 需要一个参数 size,它是应用程序请求的字节数。函数返回一个指针(没有具体的类型,在 C 语言的术语中是 void 类型),指向这样大小(或较大一点)的一块空间。对应的函数 void free(void *ptr) 函数接受一个指针,释放对应的内存块。请注意该接口的隐含意义,在释放空间时,用户不需告知库这块空间的大小。因此,在只传入一个指针的情况下,库必须能够弄清楚这块内存的大小。稍后将介绍是如何得知的。

该库管理的空间由于历史原因被称为,在堆上管理空闲空间的数据结构通常称为空闲链表。该结构包含了管理内存区域中所有空闲块的引用。当然,该数据结构不一定真的是链表,而只是某种可以追踪空闲空间的数据结构。

进一步假设,我们主要关心的是外部碎片,如上所述。当然,分配程序也可能有内部碎片的问题。如果分配程序给出的内存块超出请求的大小,在这种块中超出请求的空间(因此而未使用)就被认为是内部碎片(因为浪费发生在已分配单元的内部),这是另一种形式的空间浪费。但是,简单起见,这里主要讨论外部碎片。

还假设,内存一旦被分配给客户,就不可以被重定位到其他位置。例如,一个程序调用 malloc(),并获得一个指向堆中一块空间的指针,这块区域就“属于”这个程序了,库不再能够移动,直到程序调用相应的 free() 函数将它归还。因此,不可能进行紧凑空闲空间的操作,从而减少碎片。但是,操作系统层在实现分段时,却可以通过紧凑来减少碎片。

最后假设,分配程序所管理的是连续的一块字节区域。在一些情况下,分配程序可以要求这块区域增长。例如,一个用户级的内存分配库在空间快用完时,可以向内核申请增加堆空间(通过 sbrk() 这样的系统调用),但是,简单起见,假设这块区域在整个生命周期内大小固定

2、底层机制

在深入策略细节之前,我来介绍大多数分配程序采用的通用机制。首先,探讨空间分割与合并的基本知识。其次,看看如何快速并相对轻松地追踪已分配的空间。最后,讨论如何利用空闲区域的内部空间维护一个简单的链表,来追踪空闲和已分配的空间

2.1、分割与合并

空闲链表包含一组元素,记录了堆中的哪些空间还没有分配。假设有下面的 30 字节的堆:

这个堆对应的空闲链表会有两个元素,一个描述第一个 10 字节的空闲区域(字节 0~9),一个描述另一个空闲区域(字节 20~29):

通过上面的介绍可以看出,任何大于 10 字节的分配请求都会失败(返回 NULL),因为没有足够的连续可用空间。而恰好 10 字节的需求可以由两个空闲块中的任何一个满足。但是,如果申请小于10字节空间,会发生什么?

假设我们只申请一个字节的内存。这种情况下,分配程序会执行所谓的分割动作:它找到一块可以满足请求的空闲空间,将其分割,第一块返回给用户,第二块留在空闲链表中。在我们的例子中,假设这时遇到申请一个字节的请求,分配程序选择使用第二块空闲空间,对 malloc() 的调用会返回 20(1 字节分配区域的地址),空闲链表会变成这样:

从上面可以看出,空闲链表基本没有变化,只是第二个空闲区域的起始位置由 20 变成 21,长度由 10 变为 9 了。因此,如果请求的空间大小小于某块空闲块,分配程序通常会进行分割。

许多分配程序中因此也有一种机制,名为合并。还是看前面的例子(10 字节的空闲空间,10 字节的已分配空间,和另外 10 字节的空闲空间)。

对于这个(小)堆,如果应用程序调用 free(10),归还堆中间的空间,会发生什么?如果只是简单地将这块空闲空间加入空闲链表,不多想想,可能得到如下的结果:

问题出现了:尽管整个堆现在完全空闲,但它似乎被分割成了 3 个 10 字节的区域。这时,如果用户请求 20 字节的空间,简单遍历空闲链表会找不到这样的空闲块,因此返回失败。

为了避免这个问题,分配程序会在释放一块内存时合并可用空间。想法很简单:在归还一块空闲内存时,仔细查看要归还的内存块的地址以及邻近的空闲空间块。如果新归还的空间与一个原有空闲块相邻,就将它们合并为一个较大的空闲块。通过合并,最后空闲链表应该像这样:

实际上,这是堆的空闲链表最初的样子,在所有分配之前。通过合并,分配程序可以更好地确保大块的空闲空间能提供给应用程序。

2.2、追踪已分配空间的大小

free(void *ptr) 接口没有块大小的参数。因此它假定对于给定的指针,内存分配库可以很快确定要释放空间的大小,从而将它放回空闲链表。

要完成这个任务,大多数分配程序都会在头块中保存一点额外的信息,它在内存中,通常就在返回的内存块之前。再看一个例子,如下图所示。在这个例子中,检查一个由 ptr 指着的 20 字节的已分配块,设想用户调用了 malloc(),并将结果保存在 ptr 中:ptr = malloc(20)。

该头块中至少包含所分配空间的大小(这个例子中是 20)。它也可能包含一些额外的指针来加速空间释放,包含一个幻数(magic number)来提供完整性检查,以及其他信息。这里假定一个简单的头块包含了分配空间的大小和一个幻数:

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

上面的例子看起来会像下图的样子。用户调用 free(ptr) 时,库会通过简单的指针运算得到头块的位置:

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

获得头块的指针后,库可以很容易地确定幻数是否符合预期的值,作为正常性检查(assert(hptr->magic 1234567)),并简单计算要释放的空间大小(即头块的大小加区域长度)。请注意前一句话中一个小但重要的细节:实际释放的是头块大小加上分配给用户的空间的大小。因此,如果用户请求 N 字节的内存,库不是寻找大小为 N 的空闲块,而是寻找 N 加上头块大小的空闲块

2.3、嵌入空闲链表

到目前为止,这个简单的空闲链表还只是一个概念上的存在,它就是一个链表,描述了堆中的空闲内存块。但如何在空闲内存内部建立这样一个链表呢?在更典型的链表中,如果要分配新节点,你会调用 malloc() 来获取该节点所需的空间。遗憾的是,在内存分配库内,你需要在空闲空间本身中建立空闲空间链表

假设需要管理一个 4096 字节的内存块(即堆是 4KB)。为了将它作为一个空闲空间链表来管理,首先要初始化这个链表。开始,链表中只有一个条目,记录了大小为 4096 的空间(减去头块的大小)。下面是该链表中一个节点描述:

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

现在来看一些代码,它们初始化堆,并将空闲链表的第一个元素放在该空间中。假设堆构建在某块空闲空间上,这块空间通过系统调用 mmap() 获得。这不是构建这种堆的唯一选择,但在这个例子中很合适。下面是代码:

// 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;

执行这段代码之后,链表的状态是它只有一个条目,记录大小为 4088。是的,这是一个小堆,但是一个很好的例子。head 指针指向这块区域的起始地址,假设是 16KB,如下图所示。

现在,假设有一个 100 字节的内存请求。为了满足这个请求,库首先要找到一个足够大小的块。因为只有一个 4088 字节的块,所以选中这个块。然后,这个块被分割为两块:一块足够满足请求(以及头块,如前所述),一块是剩余的空闲块。假设记录头块为 8 个字节(一个整数记录大小,一个整数记录幻数),堆中的空间如下图所示。

至此,对于 100 字节的请求,库从原有的一个空闲块中分配了 108 字节,返回指向它的一个指针(在上图中用 ptr 表示),并在其之前连续的 8 字节中记录头块信息,供未来的 free() 函数使用。同时将链表中的空闲节点缩小为 3980 字节(4088−108)。

现在再来看该堆,其中有 3 个已分配区域,每个 100(加上头块是 108)。这个堆如下图所示。

可以看出,堆的前 324 字节已经分配,该空间中有 3 个头块,以及 3 个 100 字节的用户使用空间。空闲链表只有一个节点(由 head 指向),在 3 次分割后,现在大小只有 3764 字节。但如果用户程序通过 free() 归还一些内存,会发生什么?

在这个例子中,应用程序调用 free(16500),归还了中间的一块已分配空间(内存块的起始地址 16384加上前一块的 108,和这一块的头块的 8 字节,就得到了 16500)。这个值在前图中用 sptr 指向。

库马上弄清楚了这块要释放空间的大小,并将空闲块加回空闲链表。假设将它插入到空闲链表的头位置,该空间如下图所示。

现在的空闲链表包括一个小空闲块(100 字节,由链表的头指向)和一个大空闲块(3764 字节)。

链表终于有不止一个元素了!是的,空闲空间被分割成了两段,但很常见。

最后一个例子:现在假设剩余的两块已分配的空间也被释放。没有合并,空闲链表将非常破碎,如下图所示。

从图中可以看出,现在一团糟!为什么?简单,忘了合并链表项,虽然整个内存空间是空闲的,但却被分成了小段,因此形成了碎片化的内存空间。解决方案很简单:遍历链表,合并相邻块。完成之后,堆又成了一个整体。

2.4、让堆增长

现在讨论最后一个很多内存分配库中都有的机制。具体来说,如果堆中的内存空间耗尽,应该怎么办?最简单的方式就是返回失败。在某些情况下这也是唯一的选择,因此返回 NULL 也是一种体面的方式。

大多数传统的分配程序会从很小的堆开始,当空间耗尽时,再向操作系统申请更大的空间。通常,这意味着它们进行了某种系统调用(例如,大多数 UNIX 系统中的 sbrk),让堆增长。操作系统在执行sbrk 系统调用时,会找到空闲的物理内存页,将它们映射到请求进程的地址空间中去,并返回新的堆的末尾地址。这时,就有了更大的堆,请求就可以成功满足。

3、基本策略

既然有了这些底层机制,现在来看看管理空闲空间的一些基本策略。

理想的分配程序可以同时保证快速和碎片最小化。遗憾的是,由于分配及释放的请求序列是任意的(毕竟,它们由用户程序决定),任何特定的策略在某组不匹配的输入下都会变得非常差。所以不会描述“最好”的策略,而是介绍一些基本的选择,并讨论它们的优缺点。

3.1、最优匹配

最优匹配策略非常简单:首先遍历整个空闲链表,找到和请求大小一样或更大的空闲块,然后返回这组候选者中最小的一块。这就是所谓的最优匹配(也可以称为最小匹配)。只需要遍历一次空闲链表,就足以找到正确的块并返回。最优匹配背后的想法很简单:选择最接近用户请求大小的块,从而尽量避免空间浪费。然而,这有代价。简单的实现在遍历查找正确的空闲块时,要付出较高的性能代价

3.2、最差匹配

最差匹配方法与最优匹配相反,它尝试找最大的空闲块,分割并满足用户需求后,将剩余的块(很大)加入空闲链表。最差匹配尝试在空闲链表中保留较大的块,而不是向最优匹配那样可能剩下很多难以利用的小块。但是,最差匹配同样需要遍历整个空闲链表。更糟糕的是,大多数研究表明它的表现非常差,导致过量的碎片,同时还有很高的开销

3.3、首次匹配

首次匹配策略就是找到第一个足够大的块,将请求的空间返回给用户。同样,剩余的空闲空间留给后续请求。首次匹配有速度优势(不需要遍历所有空闲块),但有时会让空闲链表开头的部分有很多小块。因此,分配程序如何管理空闲链表的顺序就变得很重要。一种方式是基于地址排序。通过保持空闲块按内存地址有序,合并操作会很容易,从而减少了内存碎片。

3.4、下次匹配

不同于首次匹配每次都从链表的开始查找,下次匹配算法多维护一个指针,指向上一次查找结束的位置。其想法是将对空闲空间的查找操作扩散到整个链表中去,避免对链表开头频繁的分割。这种策略的性能与首次匹配很接近,同样避免了遍历查找。

3.5、例子

下面是上述策略的一些例子。设想一个空闲链表包含 3 个元素,长度依次为 10、30、20(暂时忽略头块和其他细节,只关注策略的操作方式):

假设有一个 15 字节的内存请求。最优匹配会遍历整个空闲链表,发现 20 字节是最优匹配,因为它是满足请求的最小空闲块。结果空闲链表变为:

最差匹配类似,但会选择最大的空闲块进行分割,在本例中是 30。结果空闲链表变为:

在这个例子中,首次匹配会和最差匹配一样,也发现满足请求的第一个空闲块。不同的是查找开销,最优匹配和最差匹配都需要遍历整个链表,而首次匹配只找到第一个满足需求的块即可,因此减少了查找开销

4、其他方式

除了上述基本策略外,还提出了许多技术和算法,来改进内存分配。

4.1、分离空闲链表

分离空闲链表的基本想法很简单:如果某个应用程序经常申请一种(或几种)大小的内存空间,那就用一个独立的链表,只管理这样大小的对象。其他大小的请求都交给更通用的内存分配程序

这种方法的好处显而易见。通过拿出一部分内存专门满足某种大小的请求,碎片就不再是问题了。而且,由于没有复杂的链表查找过程,这种特定大小的内存分配和释放都很快

就像所有好主意一样,这种方式也为系统引入了新的复杂性。例如,应该拿出多少内存来专门为某种大小的请求服务,而将剩余的用来满足一般请求?超级工程师 Jeff Bonwick 为 Solaris 系统内核设计的厚块分配程序(slab allocator),很优雅地处理了这个问题。

具体来说,在内核启动时,它为可能频繁请求的内核对象创建一些对象缓存,如锁和文件系统 inode 等。这些的对象缓存每个分离了特定大小的空闲链表,因此能够很快地响应内存请求和释放。如果某个缓存中的空闲空间快耗尽时,它就向通用内存分配程序申请一些内存厚块(slab)(总量是页大小和对象大小的公倍数)。相反,如果给定厚块中对象的引用计数变为 0,通用的内存分配程序可以从专门的分配程序中回收这些空间,这通常发生在虚拟内存系统需要更多的空间的时候。

厚块分配程序比大多数分离空闲链表做得更多,它将链表中的空闲对象保持在预初始化的状态。Bonwick 指出,数据结构的初始化和销毁的开销很大。通过将空闲对象保持在初始化状态,厚块分配程序避免了频繁的初始化和销毁,从而显著降低了开销

4.2、伙伴系统

因为合并对分配程序很关键,所以人们设计了一些方法,让合并变得简单,一个好例子就是二分伙伴分配程序(binary buddy allocator)。

在这种系统中,空闲空间首先从概念上被看成大小为 2^N 的大空间。当有一个内存分配请求时,空闲空间被递归地一分为二,直到刚好可以满足请求的大小(再一分为二就无法满足)。这时,请求的块被返回给用户。在下面的例子中,一个 64KB 大小的空闲空间被切分,以便提供 7KB 的块:

在这个例子中,最左边的 8KB 块被分配给用户(如上图中深灰色部分所示)。请注意,这种分配策略只允许分配 2 的整数次幂大小的空闲块,因此会有内部碎片的麻烦。

伙伴系统运转良好的原因,在于很容易确定某个块的伙伴。怎么找?仔细想想上面例子中的各个块的地址。如果你想得够仔细,就会发现每对互为伙伴的块只有一位不同,正是这一位决定了它们在整个伙伴树中的层次。

4.3、其他想法

上面提到的众多方法都有一个重要的问题,缺乏可扩展性。具体来说,就是查找链表可能很慢。因此,更先进的分配程序采用更复杂的数据结构来优化这个开销,牺牲简单性来换取性能。例子包括平衡二叉树、伸展树和偏序树。

考虑到现代操作系统通常会有多核,同时会运行多线程的程序,因此人们做了许多工作,提升分配程序在多核系统上的表现。

5、小结

在本章中,讨论了最基本的内存分配程序形式。这样的分配程序存在于所有地方,编写的每个 C 程序,以及管理其自身数据结构的内存的底层操作系统。与许多系统一样,在构建这样一个系统时需要做许多折中。对分配程序提供的确切工作负载了解得越多,就越能调整它以更好地处理这种工作负载。在现代计算机系统中,构建一个适用于各种工作负载、快速、空间高效、可扩展的分配程序仍然是一个持续的挑战。

发表回复

您的电子邮箱地址不会被公开。