17. Free-Space Management

这节就接着上节来讲讲怎么进行内存管理。具体来说，我们要讨论的就是paging的概念。简单点的话，把内存分成固定大小的块，管理这些块即可。复杂点来说，当这些块的大小不固定时，变长时该如何管理？比如一个进程可能通过malloc()和free()来分配或销毁内存。还可能存在外部碎片的问题。
问题来了：如何在满足变长内存块的情况下进行内存管理？有什么策略可以用来最小化外部碎片？这些可用方法的时间和空间开销是多少？

17.1 Assumptions
假设我们通过malloc()和free()来对内存进行分配和销毁：

对于malloc()，接收一个size参数，用来代表需要分配多少字节的内存。

对于free()，接收一个指针作为参数，释放相关内存。那么free()怎么知道要释放多少的内存呢？稍后就知道了。

用free list，一种数据结构来管理空闲内存。

17.2 Low-level Mechanisms

有一个30字节的heap，它和free list 的对应关系如下：

假设我们请求分配1个字节的空间，这是分配器就会采取splitting：找到满足要求的chunk，并且把它分成两块，第一块用于返回给caller，第二块继续保存在list中。那么就会变成这样：

还是对于上述初始情况，假设我们调用free(10)会怎么样呢？如果简单的把10开始这个chunk加到list里去就是这种情况：

这时，虽然总和可用是30字节，但是任何一个超过10字节的请求都会被拒绝，因为一个chunk最大可用是10。所以采用coalescing的方法，变成下面这样：

有了coalescing，就可以保证最大程度利用内存。

就像之前说的，free()函数只接收了一个指针参数，但是系统也可以知道该chunk有多大，然后把它加到free list中去，那么是如何做到的？

为了满足上述目的，分配器需要额外保存一点信息在header中。看个图：

假设malloc(20)，那么下面的20字节是分配用的空间，上面的header是为了加速释放内存用的，具体来说，header中包括：

magic是用于提供额外的integrity和其他信息。当调用free时：

在获得指向头部的指针后，就可以通过magic number来检查 assert(hptr->magic == 1234567) ，并且计算出要释放的区域的大小（20字节+header）。因此当用户申请N字节的内存时，不是找大小满足N的chunk，而是找大小满足N+header大小的chunk。

假设内存空间一共4096字节，也就是4KB。对于free list，首先初始化，list中只有一个元素大小4096（减去header尺寸），list中的node：

我们通过系统调用mmap()来构建heap，

运行代码之后，list中就有了一个元素，size是4096-8=4088。我们假设heap的虚拟地址是从16KB开始的，那么就像：

假设用户请求分配100字节内存：

注意每个header是8个字节，因为包含了两个整数，每个整数是4字节。也就是说，lib实际分配的是100+8=106字节。

假设heap的分配情况是这样：

这时如果我们要释放中间那块chunk会发生什么？free(16500)也就是物理地址，free(16K+108+8)，也就是sptr指向的地方。free后就会把该chunk加到free list中去：

现在list中就有两个chunk。

现在我们再释放剩下两个chunk：

这种还没有合并，遍历list对相邻chunk进行合并，那么就是一个完整的heap了。

如果heap空间用完了咋办？可以通过系统效用，比如UNIX中sbrk来申请更多内存。

没有最好的策略，只能尽量采取合适的策略来减少外部碎片。
Best Fit：找到大小最合适chunk分配。优点简单，缺点时间复杂度较高。
Worst Fit：找到最大的chunk分配。优点可能减少了外部best fit带来的小的chunk，缺点时间复杂度较高。
First Fit：找到第一个满足要求的chunk分配。优点速度快，缺点可能污染free list的开头。比如说一个很大的chunk分配给很小的内存申请。
Next Fit：找到第二个满足要求的chunk分配。和first fit很像，避免污染开头。